Устройство для формирования адресов процессора быстрого преобразования фурье

 

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее первый и второй реверсивные счетчики , дадифратор, регистр, N узлов блокировки, блок управления, вькоды переноса и эаема первого реверсивного счетчика соединены соответственно с суммирующим и вычитакщим входами второго реверсивного счетчика , информационный выход которого соединен со входом дешифратора, информационный выход регистра является информационньол выходом устройства , каждьл из Н узлов блокировки содержит элемент 2И-НЕ, элемент. 2ИЛИ-НЕ и два сумматора по модулр . два, причем выход элемента 2 ИЛИ-НБ подключен к первому входу первого сумматора по модулю два, выход которого подключен к первому входу второго сумматора по модулю два, второй вход первого сумматора по модулю два соеДинен с выходом элемента 2И-НЕ, первый вход которого объединен с первым входом элемента 2 ИЛИ-НЕ, при этом втор вход элемента 2 ИЛИ-НЕ л-го (i«l,N) узла блокировки соединен с выходом i го разряда первого реверсивного счетчика , выход второго сумматора по модулю два i-го узла блокировки соединен со входом -го разряда регистра и входим-i-го разряда первого реверсивного счетчика, отличающееся тем, что, с целью расширения функционсшьных возможностей за счет реализации алгоритмов с различными основаниями, в него введен вычитающий счетчик, выход j-го (jri,Eog к, к-основанйе алгоритма) разряда котоГрого подключен ко второму входу элемента 2И-НЕ с-го ( bj Щг) +2EogjX«,N) узла блокировки , а 8 -ый ( I 0, М-1) выход дешифратора подключен к первому входу элемента 2 ИЛИ-НЕ -го (is - og4lcH, Eog) узла блокировки, причём елок управления содержит счетчик, узел постоянной памяти и четыре элемента 2И-НЕ, при этом тактовый вход счетчика и первые вхо (О ды элементов 2И-НЕ объединены между собой и являются тактовымчвходом С устройства, информационный выход счетчика подключен к. адресному вхоQ ду узла постоянной памяти, вход С старшего разряда адресного входа которого подключен к выходу старше .го разряда дешифратора, первый информационный выход узла постоянной эо памяти подключен ко второму входу . первого элемента 2И-НЕ, выход которого подключен к суммирующему входу первого реверсивного счет чика, второй информационный выход х узла постоянной памяти соединен со вторьм входом втброго элемента 2ИНЕ , выход которого подключён к вычитающему входу первого реверсивного счетчика, третий информационный выход узла постоянной памяти соединен со вторь входом третьего эле-, мента 2И-НЕ, выход которого подключен ко входу занесения информации первого реверсивного счетчика, четвертый информационный выход узла постоянной псмяти подключен к тактовому входу регистра, пятый информационный выход узла постоянной па

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

3(51) 06 15 332 к

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ГЮ ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЬГГИЙ (21) 3538476/18-24 (22) 12. 01. 83 (46) 15.03.84. Бюл. 9 10 „ (72) A.H.Øåìàðîâ (71) Минский радиотехнический институт (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

Р 548863, кл. Cj 06 F 15/332, 1976.

2. Авторское свидетельство СССР

9 922763, кл. G 06 F 15/332, 1982 (прототип); (54)(57) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ПРОЦЕССОРА БЬ СТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее первый и второй реверсивные счетчики, дешифратор, регистр, М узлов блокировки, блок управления, выходы переноса и заема цервого реверсивного счетчика соединены соответственно с суммирующим и вычитакшим входами второго реверсивного счетчика, информационный выход которого .соединен со входом дешифратора, информационный выход регистра является информационным выходом устройст ва, каждый из М узлов блокировки содержит элемент 2И-НЕ, элемент.

2ИЛИ-НЕ к два сумматора по модулю два, причем выход элемента 2 ИЛИ-НЕ подключен к первому входу первого сумматора по.модулю два, высод которого подключен к первому входу второго сумматора по.модулю два, второй вход. первого сумматора по модулю два соеДинен с выходом элемента 2И-НЕ, первый вход которого объединен с первым входом элемента

2 ИЛИ-НЕ, при этом .второй вход эле мента 2 ИЛИ-НЕ i -ro (i l,й) узла блокировки соединен с выходом -го разряда первого реверсивного счет; чика, выход второго сумматора по модулю два 1 -го узла блокировки соединен со входом j --го разряда регист

:ра и входом 1-го разряда первого

l реверсивного счетчика, о т л и ч аю щ е е с я тем, что, с целью расширения функциональных возможностей за счет реализации алгоритмов с различными основаниями, в него введен иичитактаие счетчик, иапсод j -го (j=1,top к, к-осиоиаиие алгоритма) разряда которого подключен ко второму входу элемента 2И-НЕ i,-ro (4 = j,p +Ьф,К,j +2Rog>K„,-М) узла блокировки, а 6 -ый (F =0, М-1) выход дешифратора подключен к первому входу элемента 2 ИЛИ-НЕ i -го (i=8 Eogqk+s,(0+%) 0og К ) узла блокировкк, причем блок управления содержит счетчик, узел постоянной памяти и четыре элемента 2И-НЕ, при этом тактовый вход счетчика и первые входы элементов 2И-HE объединены между собой и являются тактовьэа :входом устройства, информационный выход счетчика подключен к адресному входу узла постоянной памяти, вход

Ф старшего разряда адресного входа которого подключен к выходу старшего разряда дешифратора, первый инФормационный выход узла постоянной памяти подключен ко второму входу первого элемента 2И-НЕ, выход которого подключен к суммирукщему входу первого реверсивного счетчика, второй информационный выход узла постоянной памяти соединен со вторьм входом второго элемента 2ИНЕ, выход которого подключен к вычитакицему входу первого. реверсивного счетчика, третий информационный выход узла постоянной. памяти соединен со вторым входом третьего элемента 2И-НЕ, выход которого подключен ко входу занесения информации первого реверсивного счетчика, четвертый информацконный выход .узла постоянной памяти подключен к тактовому входу регистра, пятый информационный выход узла постоянной па1080149

45 мяти соединен со вторым входом четвертого элемента 2И-НЕ, выход которого подключен к управлякщему входу вычитакщего счетчика, шестой инфор1

Изобретение относится к вычислительной технике и может быть использовано в составе процессора быстрого преобразования Фурье (БПФ),применяемого в спектроанализаторах генераторах. 5 широкополосного случайного процесса, синтезаторах речевых сигналов, а также как устройство адресации процессоров быстрого преобразования в базис других ортогональных функ- (О ций (например, функций Уолша).

Известнб устройство формирования адресов, содержащее узел реконфигурации счетчика, выход которого соединен с управлякщим входом счетчи. ка, блок выдачи адресов, первый информационный вход которого соединен с выходом счетчика, а выход— с выходом устройства, причем вход узла реконфигурации счетчИка, первый и второй счетные входы счетчика и первый управлякщий вход блока вццачи адресов соединены соответственно с первым, вторым, третьим и четвертым входами блока, регистр и группу элементов ИЛИ, выход регистра и группа элементов ИЛИ соединены соответственно с вторым и третьим информационными входами узла выдачи адресов, второй и третий управляющий входы которого, управля- ЗО .киций вход; регистра и второй вход группы элементов ИЛИ соединены соответственно с пятьм, шестым, седьмым и первым входами устройства. На второй, третий, четвертый, 35 пятый, шестой, седьмой входы устройства подаются сигналы, которые вырабатываются блоком управления данного устройства. На. первый вход устройства поступает информация 40 о номере слоя алгоритма. БПФ,в котором в данный момент времени функционирует устройство. Для получения данной .информации устройство должно содержать второй счетчик и де(якфратор, причем выход счетчика соединен с входом дешифратора, вы-. ход которого соединен с первьэе входом устройства. Управлякщий вход вто. рого счетчика должен быть соединен с выходом блока управления устройства (1) .

Недостатки известного блока— сложность его построения, невозможмационный выход узла постоянной па-. мяти подключен ко второму входу . второго сумматора по модулю два

ro узла блокировки.

2 ность -организации перекрытия циклов, а также невозможность формирования адресов алгоритма БПФ с основанием выше двух (четыре, восемь и т.д.) .

Наиболее близким к изобретению по технической сущности является устройство формирования адресов процессора БПФ, содержащее первый и второй счетчики, дешифратор, регистр и блок управления, первый, второй и третий выходы которого соединены соответственно с входом суммирования, входом вычитания и тактовым входом первого реверсивного счетчика, выход переноса и выход заема которого соединены соответственно с суммирующим и вычитакщим входами второго реверсивного счетчика, выходы которого соединены с входами дешифратора, выход старшего разряда которого подключен к первому входу блока управления, второй вход которого . является тактовым входом устройст-ва, а четвертый выход блока управления соединен с тактовым входом регистра, выходы которого являются выходами устройства, И узлов блЬкировки, каждый из которых содержит .элемент ИЛИ-НЕ, элемент И-НЕ и два сумматора по модулю два, причем выход элемента ИЛИ-НЕ подклкгчен к первому входу первого сумматора по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первого сумматора по модулю. два соединен с выходом элемента И-НЕ, первый вход которого объединен с первым входом элемента ИЛИ-НЕ, при этом второй вход элемента ИЛИ-НЕ

j-ro ((= 1,N) узла блокировки соединен с -ым информационным выходом первого реверсивного счетчика, второй вход элемента И-НЕ -ro узла блокировки (i-..Öß) соединен с пятым выходом блока управления, второй вход второго сумматора по модулю два е -го (i-1,N) узла блокировки соединен с шестым выходом блока управления, а выход второго сумматора по модулю два i -го (<=I,N) узла блокировки соединен с 1 -ым (. 1,N) информационным входом регистра и т -ым ((= 1,N) информационным входом первого реверсивного счет, чика, причем ю-ый выход (-IP-1) 1080149 дешифратора подключен к первому входу элемента ИЛИ-НЕ g +1-ro 6=0,N-1) узла б,локировки (21 .

Недостаток известного устройства - невозможность формирования адресов процессора БПФ с основанием выае двух.

Цель изобретения — расширение функциональных воэможностей устройства эа счет реализации алгоритмов с различными основаниями.

Поставленная цель достигается тем, что в устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее первый и второй реверсивные счетчи ки, дешифратор, регистр, М узлов блокировки, блок управления, выходы переноса .и заема первого реверсивного ечетчика соединены соответственно с суммирукщим и вычитакщим входами второго реверсивного счетчика, информационный выход которого со- единен со входом дешифратора, информационный выход регистра является информационным выходом устройства, . каждый,из М узлов блокировки содержит элемент 2И-HE элемент

2 ИЛИ-НЕ и два. сумматора по модулю два, причем выход элемента 2 ИЛИ-НЕ подключен к первому входу первого. суммаТора по модулю два, выход которого подключен к первому входу второго сумматора по модулю два, второй вход первого сумматора по модулю два соединен с выходом эле- 35 мента.2И-НЕ, первый вход которого обьединен с первым входом элемента

2 ИЛИ-НЕ, при этом второй вход элемента 2 ЙЛИ-НЕ i -го (< = 3 H ) узла блокировки соединен с выходом1 -ro 4p разряда пе рв ого реверс ив ного счетчика, выход второго сумматора по модулю два i -ro узла блокировки соединен со входом i.-ro разряда регистра и входом i -го разряда пер- 45 вого реверсивного счетчика, введен вычитакщий счетчик, выход ) -го (.)=1 7®q.к, к - основание алгоритма)

Разряда которого подключен к второму входу элемента 2И-НЕ i -ro(<=j,j+

:+Ь к, j +2P+ xc+„.а я ) узла блокиров ки, à f -ый (Р- О,М-1) выход дешифратора подключен к первому входу элемента 2 ИЛИ-НЕ i -ro 6 Yhg Ü1,(Ñ Ùô) узла блркировки, причем блок управ-. ления содержит счетчик, узел посто- 55 янной памяти и четыре элемента

2И-,НЕ, при этом тактовый вход счет чика и первые входы элементов 2И-HE объединены.между собой и являются

:тактовым входом устройства, инфор- 6() мационный выход счетчика подключен к адресному входу узла постоянной

;памятк, вход старшего разряда. адресного входа которого подключен

rc выходу старшего разряда дешифра-. 65 тора, первый информационный выход узла постоянной памяти подключен ко второму входу первого элемента

2И-НЕ, выход которого подключен к суммирукщему входу первого реверсивного счетчика, второй информационный выход узла постоянной памяти соединен со вторым входом второго элемента 2И-НЕ,.выход которого подключен к вычитакщему входу первого реверсивного счетчика, третий информационный выход узла постоянной памяти соединен со вторым входом третьего элемента 2И-НЕ, выход которого подключен ко входу занесения информации первого,реверсивного счетчика, четвертый информационный выход узла постоянной памяти

;подключен к тактовому входу регист ра, пятый информаицонный выход узла постоянной памяти соединен со вторым входом четвертого элемента 2И-НЕ, выход которого подключен к управлякщему входу вычитакщего счетчика, шестой информационный выход узла постоянной памяти подключен ко второму входу второго сумматора по модулю два s -ro узла блокировки.

Принцип работы устройства заключается в следукщем.

Если в алгоритме БПФ с основани,ем два при выполнении базовой опера,ции обрабатываются два операнда, то р алгоритме с основанием четыре, восемь и т.д. обрабатываются четыре, восемь и т.д. операндов, адреса которых отличаются информацией для алгоритма.с основанием два в одном разряде, а с основанием четыре, восемь и т.д. в двух, трех и т.д. разрядах. Номера заблокированных разрядов соответствуют номеру слоя алгоритма БПФ, если рассматривать два, три и т.д. разряда как. один разряд в четвертичной, восьмиричной и т.д. системах счисления.

Если заблокировать данные раз- ряды, т.е. не пропускать информацию данных разрядов на выход устройства, а вместо информации заблокированных разрядов на выход устройства подавать в двоичном коде номер операнда базовой операции, то мож но адресовать четыре операнда, во семь операндов и т..д. Каждое состояние счетчика адресует четыре, восемь и т.д. операндов, поэтому счетчик обладает избыточностью, для устранения которой вводится операция восстановления счетчика, описанная в прототипе. Единицы или нули восстанавливаются во всех заблокированных разрядах одновременно.

При работе в;специальном слое безызбыточного алгоритма БПЖ ни один кз разрядов не блокируется,к устройство функционирует так же, как

1080149

30

В первоначальном состояиии все счетчики обнулены. На с Ixpoвход счетчика 12 поступают актовые импульсы, по каждому и котоРых счетчик переключается в новое состояние. Каждое состояние счетчи- 35 ка определяет адрес, по которому из узла 13 происходит считывание информации, которая с помощью комбйнационной схемы на элементах 14

17 формирует управляющие сигналы 40 на выходах блока управления 1, согласно временной диаграмме, представленной на фиг.4, где ТИ вЂ” тактовые импульсы; Al — A4 - разрядные выходы счетчика 12; 18 - сигнал на первом входе блока управления 1;

19 — 24 — сигналы на первом, втором, третьем, четвертом, пятом, шестом выходах блока управления 1.

Рассмотрим функционирование устройства при обработке и -ой пары

3 -го слоя алгоритма БПФ.

Пусть в данном цикле {16 тактов) обрабатывается и -ая четверка -ro слоя алгоритма БПФ с основанием четыре. Во время обработки И -ой четверки операндов должна быть адресована Ь -1 четверка операндов для записи их в запоминакщее устройство (эта четверка операндов была обработана в предыдущем цикле) и 0+1 60 четверка операндов для считывания их иэ запоминающего устройства (эта пара обрабатывается в следукщем цикле). Номеру слоя соответствует состояние счетчика 3. В соответст-, 65 и устройство адресации, описанное в прототипе.

На фиг.l представлена функциональная схема предлагаемого устройства1 на фиг. 2 — функциональная схема узла- блокировки, на фиг.3— функциональная схема блока управления/ на фиг. 4 — временные диаграммы работы блока управления при формировании адресов алгоритма БПФ с основанием четыре.

Устройство для формирования адресов процессора БПФ содержит блок

1 управления, первый реверсивный счетчик 2, второй реверсивный счетчик 3, дешифратор 4, g узлов блоки- 15 ровки (разряда) 5, регистр б и вычитакщий счетчик 7.

Каждый узел блокнровки 5 (фиг.2) содержит элемент 2И-НЕ 8, элемент

2 ИЛИ-HE 9 и два (двухвходовых) сумматора по модулю два 10> 11.

Блок управления (фиг.3) содержит счетчик 12, узел постоянной памяти

13 и четыре элемента 2И-НЕ 14 — 17 °

Устройство для.формирования адресов процессора БПФ функционирует следующим образом (для примера рассмотрим алгоритм с основанием четыре). вин с этим блокируются 2<и 2 +1 разряды счетчика. В незаблокирован- ных разрядах информация с выходов счетчика 2 через два инвертора (элемент 2 ИЛИ-HE и первый двухвходовой сумматор по модулю два) и повторитель (второй двухвходовой сумматор по модулю два) поступает на выход устройства. В заблокированных разрядах информация с выходов счетчика 7 через инвертор (элемент

2 И-НЕ) и два повторителя (первый и второй двухвходовые сумматоры по модулю два) поступает на выход уст.ройства. В счетчике 2 хранится информация, адресующая четверку операндов алгоритма БПФ с основанием четыре, а в счетчике 7 - информация, адресующая операнд в четверке выбранных операндов (состояние счет( чика 7 fllj адресует первый операнд, Π— второй операнд, 10) - третий

1операнд, (00) — четвертый операнд) .

Все счетчики переключаются по положительному перепаду импульса, т.е. из 0 в 1. В первом такте на пятом выходе блока управления 1 вырабатывается сигнал, по которому из счетчика 7 вычитается единица, чем адресуется первый операнд четверки операндов. Во втором такте на третьем входе блока управления вырабатывается сигнал, по которому в заблокированныхых разрядах восстанавливается значение 00, и сигнал на втором выходе блока управления l, по которому из счетчика 2 вычитается единица, чем адресуется Il -1 четверка операндов . Также вырабатывается сигнал на четвертом выходе блока управ- ления 1, по отрицательному перепаду которого в регистр б заносится . адрес первого операнда (h-1)-ой четверки операндов. В третьем такте вырабатывается сигнал на пятом выходе блока управления 1, по которому из счетчика 7 вычитается единица, чем адресуется второй операнд четверки операндов. В четвертом такте вырабатывается сигнал на четвертом выходе блока управления 1, по которому в регистр б заносится адрес второго операнда (и-1)-ой четверки операндов. В пятом такте вырабатывается сигнал на пятом выходе блока управления 1, по которому из счетчика 7 вычитается единица, чем адресуется третий операнд четверки операндов. В шестом такте на четвертом выходе блока управления 1 вырабатывается сигнал, по которому в регистр б заносится адрес третьего операнда (п-1)-ой четверки операндов °

В седьмом такте на пятом выходе блока управления 1 вырабатывается сигнал, по которому из счетчика 7

1080149 вычитается единица, чем адресуется четвертый операнд четверки операндов. В восьмом такте вырабатывается сигнал на четвертом выходе блока управления 1, по которому в регистр 6 заносится адрес четвертого операнда (q-1)-ой четверки операндов. В девятом такте на третьем выходе блока управления 1 вырабатывается сигнал, по которому в заблокированных разрядах восстанавливается значение (llew, н сигнал на первом выходе блока управления 1, по которому в счетчик 2 добавляется единица, чем адресуется я -ая четверка операндов. В десятом такте вырабатывается сигнал на третьем выходе блока управления 1, по которому в-заблокированных разрядах счетчика 2 восстанавливается значение (ll), и сигнал на первом выходе блока управления 1, по которому в счетчик 2 добавляется единица, чем адресуется(И+1) -ая четверка операндов, кроме того, в этом такте вырабатывается сигнал на пятом выходе блока управления 1, по которому иэ счетчика 7 вычитается единица, чем адресуется первый операнд четверки. операндов . Также

B десятом такте вырабатывается сигнал на четвертом выходе блока управления 1, по которому в регистр

6 заносится первый операнд (я+1)-ой четверки операндов. В одиннадцатом такте вырабатывается сигнал на пятом выходе блока управления 1, по которому иэ счетчика 7 вычитается единица, чем адресуется второй операнд четверки операндов. В двенадцатом такте на четвертом выходе блока управления 1 вырабатывается сигнал, по которому в регистр 6 эаносится адрес второго операнда (Л+1) -ой четверки операндов. В триннадцаТоМ такте вырабатывается сигнал на пятом выходе блока управления

1i по которому из счетчика 7 вычитается единица, чем адресуется третий операнд (11+1)-ой четверки операндов. В четырнадцатом такте на четвертом выходе блока управления

1 вырабатывается сигнал „по. которому в регистр 6 заносится третий операнд (0+1) -ой четверки операндов.

В пятнадцатом такте вырабатывается сигнал на пятом выходе блока управления 1, по которому иэ счетчика 7

15 вычитается единица, чем адресуется четвертый операнд четверки операндов. В шестнадцатом такте вырабатывается сигнал на четвертом выходе блока управления 1, по которому

2() в регистр 6 заносится четвертый операнд (и+1)-ой четверки операндов.

Цикл повторяется снова и снова до тех пор, пока не будут обработаны все четверки операндов по всем

25 слоям, после чего устройство начи нает вырабатывать адреса пар операндов специального слоя беэиэбыточного алгоритма БПФ. В этом случае устройство функционирует аналогич-. но устройству, описанному в прототипе. На временной диаграмме работы блока управления 1 (фиг.4) изображены два цикла по восемь тактов.

После обнуления. счетчиков устрой35 . Таким образом, предлагаемое устройство позволяет формировать адреса алгоритма БПФ с основанием выше двух (четыре, восемь, шестнадцать

4О и т.д.), что расширяет его функциональные возможности.

1080149

1080149 .У . P. К

i вео(с = И м)уездов Аммирю/ми

7аллм ти

Af

?t

72

BHHHGH Эаказ 1339/49 Тираж 699 Подписное

Филиал ППП "Патент", г. Ужгород, ул.Проектная, 4