Блок формирования адресов для устройства,реализующего быстрое преобразование Уолша Советский патент 1984 года по МПК G06F9/34 G06F17/14 

I Изобретение относится к вычислительной технике и может быть ислоль зовано при построении устройств, ре лнэую1цих быстрое преобразование Уолша, Известно устройство, реализующее алгоритм, быстрого преобразования Уояша, содержащее в своем составе аналого-цифровой преобразователь, первый цифровой накопитель для накопления входных данных, арифметическое устройство и. второй цифровой накопитель для накопления резул татов преобразования входных данных СП. Однако адресация данных в накопи телях может производиться арифметическим устройством, что снижает скорость преобразования входных данных из-за отвлечения арифметического устройства на адресацию дан ных или может использоваться отдель ный блок адресации, адресующей дан ные в накопителе в соответствии с алгоритмом быстрого преобразования Уолша. Наиболее близким по технической сущности к изобретению является блок формирования адресов для устро ства, реализующего быстрое преобразование Фурье, содерхкащий счетчик, регистр, группу элементов MJBi, и узел выдачи адресов, первый и второ входы КОТОРОГО соединены соответствен но с выходами группы элементовИЛН и счетчика, счетный вход которого является счетным входом блока, выхо узла выдачи адресов является информ ционным выходом блока, а первые входы элементов ИЛИ являются группо информационных входов блокаС21. Однако при применении его в качестве адресного блока в устройст ве быстрого преобразования Уолша в результате преобразования получаются коэффициенты преобразования, упорядоченные по Адамару и расположенные не в порядке возрастания частости.. Это следует из того, что графы быстрого преобразования Фурье и Уолша-Адамара совпадают. При спектральном анализе сигналов желательно, чтобы коэффициенты преобразования располагались в по;рядке возрастания частости. Это упрощает получение спектра мощности сигнапов до простого суммирования квадратов соседнихкоз(1 фициентов. 261 Переупорядочение коэффициентов преобразования Уолша-Адамара по частости при использовании известного блока в качестве адресного блока устройства быстрого преобрвазования Уолша приводит к значительным аппаратурным затратам. Кроме того, необходимо тратить дополнительное время на переупорядочение коэффициентов, что снижает быстродействие устройства, реализующего быстрое преобразование Уолша. Цель изобретения - повышение быстродействия. Указанная цель достигается тем, что в блок формирования адресов для устройства, реализующего быстрое преобразование Уолша,содержащий регистр, первый счетчик, Л iN 2, где N- размер преобразования) элементов ИЛИ, выходы которых подключены соответственно к разрядам первого информационного входа мультиплексора выход которого является информационным выходом блока, разряды второго информационного входа мультиплексора соединены соответственно с разрядными выходами первого счетчика, счетный вход которого является первым синхровходом, а первые входы П элементов ИЛИ являются группой информационных входов блока, введены второй счетчик, 2 (h - О элементов И и () элементов ИЛИ 5 причем выход х-го (г-2,и разряда второго счетчика соединен с первыми входами (2 г - 3)-го и(Zг-2)-гo элементов И, выходы и(21 + П-го (2 1,1Л-) элементов И подключены соответственно к первому и второму входам (i+nj-ro элемента I-fflM, выход которого соединен с З+П-м разрядом третьего ин4юрмационного входа мультиплексора и подключен к второму входу(g + l)-го элемента ИЛИ, выходы первого и 2(vi-l)-ro элементов И соединены с вторыми входами соответственно первого и п -го элементов ИЛИ и подключены соответственно к первому и п-му разрядам третьего информационного входа мультиплексора, разряды четвертого информационного входа которого соединены соответственно с разрядными выходами второго счетчика, счетный вход которого является вторым синхровходом блока, прямой выход к,-го(. 1 , V -1 разряда регистра соединен с вторым входом 2к-го элемента И, второй вход (2к-1)-го элемента И подключен к инверсному выходу К-го разряда регистра, вход установки в ноль которого подключен к ;, первому информационному входу блока, а вход установки в единицу (Ъ-,- разряда регистра соединен с irn-M (п 2 ,vi1 информационным входом группы блока, управляющий вход мультиплексора является входом задания режима блока. На фиг. 1 показана функциональная схема блока адресации для устройства реализующего быстрое преобразование Уолша; на фиг. 2 - схема, поясняющая принцип объединения в блоке адресации выходных сигналов второго счетчика, регистра, группы элементов И и групп элементов ИЛИ для случая обработки выборок входного сигнала, а также формирование последовательности адресов для указанного случая. На фиг. I широкими стрелками изображены информационные потоки группы сигналов, а тонкими - отдельные сигналы. Блок адресации фиг. Мсостоит из (двоичных) счетчиков I и 2, регист 3,2() (двухвходовых) элементов И 4 () элементов ИЛИ 5,н элементов ИЛИ 6, мульт«плексатора 7, информационно го выхода 8 блока, управляющих входов 9 и 10 мультиплексора, синхр входов(счетных входон) и 12 блока (счетчиков 1 и 2 соответственно) и информационного входа 13 блока. Блок работает следующим образом. Двоичный счетчик 1 разрядностью (Vi-i-l) ( число обрабатываемых входн данных и формируемых коэ()фициснтов) формирует последовательности адресо входных данных, передаваемых от аналого-цифрового преобразователя в накопитель данных. Старший () -и разряд его служит для выбора одного из двух буферов входных данных. Двоичный счетчик 2 разрядностыо V формирует последовательность адресов результата алгебраического суммирования двух операндов в процессе выполнения алгоритма быстрого преобразования Уолша. Регистр 3 разрядностью (vi-11 управляет сдвигом информационных сигналов счетчика 2, осуществляемым группой элементов И 4. Группа элементов ИЛИ 5 осуществляет объединение соответствующих сигналов группы элементов И 4 и формировЛ1ие на своих выходах разрядов с 2-го по(и-1)-й адреса первого операнда. При этом младшим и старшим разрядом адреса первого операнда являются выходные сигналы первого и последнего элементов группы элементов И 4. Группа элементов ИЛИ 6 осуществляет объединение входных информационных сигналов блока, представляющих собой позиционный код номера итерации и соответствующих разрядов адреса первого операнда,и 4 ормирует на своих выходах адрес второго операнда. Мальтиплексор 7 представляет собой цифровой четырехканальный мульиплексор и осуществляет выдачу на информационный выход 8 блока одного из четырех i.v + 2 -разрядных адресов: адреса входных данных, адреса первого операнда, адреса нторого операнда и адреса результата. Комбинация старших двух paзpядoв( и (i + 1) -го определяет один из трех буферов емкостью 2/1 слов, к которым происходит обращение в процессе выполнения быстрого преобразования Уолша или записи входных данных и зависит от состояния(+П-го разряда счетчика 1 и номера итерации в соответствии с табл. I. Таблица I.

БЛОК ФОРМИРОВАНИЯ АДРЕСОВ ДЛЯ УСТРОЙСТВА, РКАЛИЗУЮЩЕГО БЫСТРОЕ ПРЕОБРАЗОВАНИЕ YOJllllA, содержащий регистр, первый счетчик, п(ы 2, где Ы - размер преобразования элементо1з ИЛИ, ныходы которых подключены соответственна к разрядам перього информационного входа мультиплексора, выход которого является информационным выходом блока, разряды второго информационного входа мультиплексора соединены соответс- -венн( с разрядными выходами первого счетчика, счетный вход которого является первым синхровходом, а ггервые входы у элеменчов ИЧИ являются 1рупг1ой информационных входов блока, отличаю щ и йс я тем, что, с целью повышения быстродействия, в него введены второй счетчик, - I) э.пеме1Г1ов И и (п -2) элементов ИЛИ, причем выход i-го (г 2ii) разряда второго счетчика соединен с первыми входами

00 00

01 10

10 01

01

00 10

10 00 01 Графы табл.1 означают: 1 - состояние ) -го разряда счетчика 1; 2 - состояние младшего разряда двоич ного кода номера итерации, считая, что код первой итерации 0...0; 3 состояние(м 4-2)-го и( разрядов кода адреса записываемых входных дан ных; 4 - состояние(у + 2)-го и(у%+1)-го разрядов кода адреса операнда; 5 состояние(м 4-2)-го и()-го разрядов кода адреса результата. Интерпретация табЛ. 1 следующая. Если в текущий момент .времени ()-й разряд счетчика 1 находится в состоянии О, то запись входных данных от аналого-цифрового преобразователя производится в первый буфер (код 00 в графе 3. При этом, если код номера итерации четный(О в гра фе 2), то операнды извлекаются из второго буфера(код О графе 4), а результаты помещаются в третий буфер(код 1 графе 5). Если же код номера итерации нечетный{М в графе 21, то операнды извлекаются из третьего буфера Скод 1 О в графе 4) а реэгультаты помещаются во второй буфер(код О 1 в графе 5). Если в текущий момент времени (vn-0-й разряд счетчика 1 находится в состоянии 1, то запись входных данных от аналого-цифрового преобразователя производится во второй буфе (код О I в графе 3), операнды в четных итерациях (О в графе 2)извле каются из первого буфера(код О О в графе 4), а результаты записываютс в третий буфер код 1 О в графе 5 8нечетных итерациях в графе 2) операнды извлекаются из третьего буфера(код 1 О в графе 4), а резул помещаются в буфер первьй (код О в графе 5). В процессе функционирования по алгоритму быстрого преобразования Уолша блок управления циклически вырабатывает на управляющих входах 9и 10 мультиплексора 7(фиг. 1) последовательность кодов: 1 О, О О, I 1. При этом мультиплексор 7 передает со своих 3-го, 2-го и 4-го информационных -входов на выход 8 последовательно адреса 1-го и 2-го операндов и результата. После съема адреса результата блок управления генерирует импульс на счетном входе 12 счетчика 2, увеличивая его содержимое на +1 и подготавливая его к новому циклу выдачи адресов. 1 66 После 2 циклов текущая итерация быстрого преобразования Уолша заканчивается, счетчик 2 переполняется (переходит в состояние 0...), на входе 13 блока появляется новый код номера итерации, который вызывает установку в I очередного триггера регистра 3, начиная с младшего , разряда. Начинается генерация, последовательности адресов на новой итерации. К началу последней л-и итерации последний из триггеров регистра 3 устанавливается в 1. После 2 счетных импульсов, поступивших на счетчик 2, заканчивается весь цикл генерации адресов по алгоритму быстрого преобразования Уолша. Параллельно с функционированием по алгоритму быстрого преобразования Уолша предлагаемый блок может адресовать один из двух накопителей (буферов входных данных с помощью счетчика 1. При обращении к аналогоцифровому преобразователю за входными данными блок управления генерирует код О 1 на входах 9 и 10 мультиплексора 7. При зтом состояние VI младших разрядов счетчика 1 передается с 1-го информационного входа на выход 8 мультиплексора 7 в качестве адреса входных данных. Код номера буфера вырабатывается в старших 2-х разрядах адреса в соответствии с табл. 1. После записи входных данных в соответствующий буфер блок управления наращивает на +1 содержимое счетчика I по входу I и может продолжить съем адресов для алгоритма быстрого преобразования Уолша с прерванного места путем генерации последовательности кодов на входах 9 и 10 узла 7 выдачи адресов. Рассмотрим принцип объединения сигналов счетчика 2, регистра 3, группы элементов И 4 и групп элементов ИЛИ 5 и 6 для случая обработки массива из 1 6-тн(4 входных слов, представленный на фиг. 2. Последовательность адресов 1-го, 2-го операндов и результата обработки для четырех итераций указанного случая представлена в табл. 2. Знаки + и - перед адресами дают представление о знаке, с которым берутся операнды, извлекаемые из указанных адресов. Группа двухвходовых элементов И содержит 2(-0 элементов 1-1 - 1-6, для рассматриваемого случая). Первые входы каждой пары элементов

i(- и 1-2, 1-3 и 1-4, 1-5 и 1-6} группы элементов И соединены со старшими (л-О разрядами счетчика 2, которые подаются на входы 5-2 - 5-4. При этом иа вход 5-2 подается выход 2-го разряда, а на вход 5-4 - старшего 4-го разряда счетчика 2, а младший разряд счетчика 2, поступающий на вход 5-1, не подвергается преобразованию. На вторые входы 7-1-,7-3 всех нечетных элементов группы И подаются прямые выходы регистра 3, а на вторые входы 6-1 - 6-3 всех четных элементов группы И подаются инверсные выходы регистра 3.

Выходы элементов 1-2 - 1-5 группы элементов И, кроме первого 1-1 и последнего 1-6, объединяются С2 ( -|)-21:2 элементами 2-1 и 2-2 второй группы элементов ИЛИ. Выходные сигналы второй группы 2-1 и 2-2 элементов ИЛИ совместно с выходными сигналами первого 1-1 и последнего 1-6 элементов группы элементов И представляют собой адрес первого операнда. При этом сигнал с выхода элемента 1-6 является младшим, а с выхода элемента 1-1 - старшим раэрядом кода адреса первого операнда. Код адреса первого операнда с выхо да второй группы элементов 2-1 и 2-2 ИЛИ и первого 1-1 и последнего 1-6 эле ментов группы элементов И объединяется с кодом номера итерации, поступающим из блока управления на входы 8-1 - 8-4. При этом номера итераций с 1-й по 4-ю представляются кодами: 0001, 0010,0100 и 1000. Вес разрядов справа налево 1,2,4,8.

На выходах 4-1 - 4-4 группы п, элементов ИЛИ 3-1 - 3-4 формируются адреса второго операнда с младшим разрядом на выходе 4-4. Адресом

результата является состояние выходов счетчика 2.

В к-й итерации табл. 2 разряды адреса первого операнда можно получить из (п-1) старших разрядов счетчика 2 (адреса результата в табл. 2) путем-передачи (к-1) младщих из указанных разрядов счетчика 2 в качает™ ве младщих разрядов адреса первого операнда и сдвига остальных(м-к указанных разрядов счетчика 2 на один разряд в сторону старших разрядов. В предлагаемом устройстве это достигается тем, что на к-й итерации {1C-П младших разрядов регистра 3 установлены в 1 и разрешают передачу (к-П младших из( старших разрядов счетчика 2 через нечетные элементы группы элементов И без сдвига, а остальные ( разрядов счетчика 2 сдвигаются на один разряд в сторону старших разрядов через четные элементы группы элементов И за счет того, что старшие из ( разрядов регистра 3 находятся в О.

Адрес второго операнда в соответствии с табл. 2 получается путем объединения разрядов адреса первого операнда с разрядами кода номера итерации: 0001, 0010, 0100 и 1000 с помощью первой группы fv двухвходовых элементов ИЛИ.

Таким образом, благодаря введению новых узлов и новых взаимосвязей предлагаемый блок позволяет адресовать устройства, выполняющие алгоритм быстрого преобразования Уолша с упорядочением коэффициентов преобразования по частости. Благодаря этому, получение спектральных коэффициентов мощности упрощается до суммирования квадратов соседних пар коэффициентов, что позволит повысить быстродействие.

Таблица 2

TV

Ш

7V

7Vl

7

«u

:s

CM

v

Т

8-1 8-3 8-2 8-1

6-31-1

vamfaamtm

A

7-3

l

Д

6-2

1-5

7-2

1-й

1-5

6-1

5-2

7-11-6

S-1

«-/

3-1 1

2

3-2

2-1

«-J

2-2

3-3

f

J-«

Фив.2