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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК ЗСМ) 06 15 33 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРГЮ ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЬГГИЙ 0 вхо(21) 3538476/18-24 реверсивного счетчика, о т л и ч а(22) 12. 01. 83 ю щ е е с я тем, что, с целью рас- (46) 15.03.84. Бюл. 9 1 ширения функциональных возможностей (72) А.ИЛ 3 емаров за счет реализации алгоритмов с раз(71) Минский радиотехнический личными основаниями, в него введен институт иичитактаие счетчик, икиод-го (53) 681. 32 (088.8) (г 1,1 аС кр к-осиоиаиие алгоритма (56) 1. Авторское свидетельство СССР Разряда которого подключен ко вто- Р 548863, кл. С( 06 Р 15/332, 1976, рому входу элемента 2 И-НЕ (,-го2. Авторское свидетельство СССР ( 4 = 3 т) +ЬфК,3 +2 ЕофК.;-Н) узла бло 922763, кл. ч 06 Р 15/332, 1982 кировки, а (-ый ( В =О, М) выход (прототип); дешифратора подключен к первому (54)(57) УСТРОЙСТВО ДЛЯ ФОРМИРОВА- входу элемента 2 ИЛИ-НЕ 1 -го НИЯ АДРЕСОВ ПРОЦЕССОРА БЬ 1 СТРОГО (1 и 09 К 1,01) Ы К) Узла блокиРовки, ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее причем блок Управления содержитки, дешифратор,. регистр, я узлов четыре элемента 2 И-НЕ, при этом блокировки, блок управления, выхо- Тактовый вход счетчйка и первые входы переноса и заема цервого ревер- ды элементов 2 И-НЕ объединены между сивного счетчика соединены соответсобой и являются тактовьзк:входомственно с суммирующим и вычитакшим усройства, информационный выход входами второго реверсивного счет- счетчика подключен к адресному чика, информационный выход которо- ду узла постоянной памяти, входР го соединен со входом дешифратора, стаРшего разряда адресного входа информационный выход регистра явля- .которого подключен к выходу старше- ется информационньаа выходом устройст. .го разряда дешифратора, первый инва, каждый из )( узлов блокировки формационный выход узла постоянной содержит элемент 2 И-НЕ, элемент. памяти подключен ко второму входу 2 ИЛИ-НЕ и два сумматора по модулю первого элемента 2 И-НЕ, выход кодва, причем выход элемента 2 ИЛИ-НЕ торого подключен к суммирукщему подключен к первому входу первого входу первого реверсивного счет- сумматора по модулю два, вьвсод ко- чика, второй информационный выход торого подключен к первому входу узла постоянной памяти соединен со второго сумматора по.модулю два, вторьм входом второго элемента 2 И- второй вход. первого сумматора по НЕ, выход которого подключен к вычимодулю два соединен с выходом эле- тащцему входу первого реверсивного мента 2 И-НЕ, первый вход которого счетчика, третий информационный выобъединен с первым входом элемента ход узла постоянной. памяти соеди ИЛИ-НЕ, при этом второй вход эле нен со вторым входом третьего эле-, мента 2 ИЛИ-НЕ 1 -го (3,Н) узламента 2 И-НЕ, выход которого подклюблокировки соединен с выходом-го чен ко входу занесения информации разряда первого реверсивного счет; первого реверсивного счетчика, четчика, выход второго сумматора по вертый информационный выход узла модулю два 1 "го узла блокировки со- постоянной памяти подключен к тактоединен со входом-го разряда регист- ному входу регистра, пятый информа:ра и входОм 1-го разряда первого. ционный выход узла постоянной па1080149 45 мяти соединен со вторым входом четвертого элемента 2 И-НЕ, выход которого подключен к управлякщему входу вычитакщего счетчика, шестой инфор- г 1Изобретение относится к вычислительной технике и может быть использовано в составе процессора быстрогопреобразования Фурье (БПФ),применяемого вспектроанализаторахгенераторах 5широкополосного случайного процесса,синтезаторах речевых сигналов, атакже как устройство адресации процессоров быстрого преобразованияв базис других ортогональных Функций (например, функций Уолша).Известнб устройство формированияадресов, содержащее узел реконфигурации счетчика, выход которого соединен с управлякщим входом счетчи. ка, блок выдачи адресов, первыйинформационной вход которого соединен с выходом счетчика, а выход -с выходом устройства, причем входузла реконфигурации счетчИка, первый и второй счетные входы счетчика и первый управлякщий вход блока выдачи адресов соединены соответственно с первым, вторым, третьими четвертым входами блока, регистри группу элементов ИЛИ, выход регистра и группа элементов ИЛИ соединены соответственно с вторым итретьим информационными входамиузла выдачи адресов, второй и третийуправляющий входы которого, управля- З 0.киций вход; регистра и второй входгруппы элементов ИЛИ соединенысоответственно с пятж, шестым,седьмым и первым входами устройства. На второй, третий, четвертью, 35пятый, шестой, седьмой входы устройства подаются сигналы, котороевырабатываются блоком управленияданного устройства. На. первый входустройства поступает информация 40о номере слоя алгоритма. БПФ,в котором в данный момент временифункционирует устройство. Для получения данной .информации устройстводолжно содержать второй счетчик иде(якфратор, причем выход счетчикасоединен с входом дешифратора, вы-.ход которого соединен с первьэю входом устройства. Управлякщий вход второго счетчика должен быть соединенс выходом блока управления устройства (1) . Недостатки известного блока -сложность его построения, невозмож мационный выход узла постоянной па-.мяти подключен ко второму входу. второго сумматора по модулю дваго узла блокировки. 2ность организации перекрытия циклов, а также невозможность формированияадресов алгоритма БПФ с основанием выше двух (четыре, восемь и т.д.) .Наиболее близким к изобретению по технической сущности является устройство формирования адресов процессора БПФ, содержащее первый и второй счетчики, дешифратор, регистр и блок управления, первый, второй и третий выходы которого соединены соответственно с входом сумчирования, входом вычитания и тактовым входом первого реверсивного счетчика, выход переноса и выход заема которого соединены соответственно с суммирующим и вычитакщим входами второго реверсивного счетчика, выходы которого соединены с входами дешифратора, выход старшего разряда которого подключен к первому входу блока управления, второй вход которого является тактовым входом устройст.ва, а четвертый выход блока управления соединен с тактовым входом регистра, выходы которого являются выходами устройства, И узлов блЬ- кировки, каждый из которых содержит .элемент ИЛИ-НЕ, элемент И-НЕ и два сумматора по модулю два, причем выход элемента ИЛИ-НЕ подклкгчен к первому входу первого сумматора по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первого сумматора по модулю два соединен с выходом элемента И-НЕ, первый вход которого объединен с первым входом элемента ИЛИ-НЕ, при этом второй вход элемента ИЛИ-НЕ -го = 1,Й) узла блокировки соединен с"ым информационным выходом первого реверсивного счетчика, второй вход элемента И-НЕ-го узла блокировки -, Цй) соединен с пятым выходом блока управления, второй вход второго сумматора по модулю два-го (1-1,И) узла блокировки соединен с шестым выходом блока управления, а выход второго сумматора по модулю два-го (:1,М) узла блокировки соединен с 1 -ым ( 1,Н) информационным входом регистра и т -ым 6= 1,М) информационным входом первого реверсивного счет,чика, причем -ый выход 6-.1-1)дешифратора подключен к первомувходу элемента ИЛИ-НЕ (, +1-го 6=0,Н)узла блокировки 2) .Недостаток известного устройства - невозможность формированияадресов процессора БПФ с основаниемвьые двух,Цель изобретения - расширениефункциональных воэможностей устройства эа счет реализации алгоритмов с различными основаниями.Поставленная цель достигаетсятем, что в устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее первый и второй реверсивные счетчи ки, дешифратор, регистр, )( узловблокировки, блок управления, выходыпереноса .и заема первого реверсивного ечетчика соединены соответственно с суммирукщим и вычитакщим входами второго реверсивного счетчика,информационный выход которого со-единен со входом дешифратора, информационный выход регистра являетсяинформационнымвыходом устройства,. каждый,из Я узлов блокировкисодержит элемент 2 И-НЕ, элемент2 ИЛИ-НЕ и два. сумматора по модулюдва, причем выход элемента 2 ИЛИ-НЕподключен к первому входу первого.суммаТора о модулю два, выход которого подключен к первому входу второго сумматора по модулю два,второй вход первого сумматора помодулю два соединен с выходом элемента.2 И-НЕ, первый вход которогообьединен с первым входом элемента2 ИЛИ-НЕ, при этом второй вход элемента 2 ЙЛИ-НЕ 1 -го (1 = ГЧ ) узлаблокировки соединен с выходом 1 -го 4 Оразряда пе рв ого реверс ив ного счетчика, выход второго суьюатора помодулю два-го узла блокировкисоединен со входом 1 -го разрядарегистра и входом 1 -го Разряда первого реверсивного счетчика, введенвычитакщий счетчик, выход ) -го(.) =1 7 к, к - основание алгоритма)разряда которого подключен к второму входу элемента 2 И-НЕ 1-го 6=Й+,+Со к, 3 +2 Цк+,й я ) узла блокировки, - а Е -ый (Е- О,М) выход дешиф-ратора подключен к первому входуэлемента 2 ИЛИ-НЕ 1 -го 6 Гб,М,ОЩф)узла блркировки, причем блок управ-.ления содержит счетчик, узел посто- Яянной памяти и четыре элемента2 И-,НЕ, при этом тактовый вход счет"чика и первые входы элементов 2 И-НЕобъединены.между собой и являютсятактовым входом устройства, инфор- бОмационный выход счетчика подключенк адресному входу узла постоянной,памятк, вход старшего разряда,адресного входа которого подключенк выходу старшего разряда дешифра тора, первый информационный выходузла постоянной памяти подключен ковторому входу первого элемента2 И-НЕ, выход которого подключен ксуммирунщему входу первого реверсивного счетчика, второй информационный выход узла постоянной памятисоединен со вторым входом второго элемента 2 И-НЕ,.выход которогоподключен к вычитакщему входу первого реверсивного счетчика, третийинформационный выход узла постоянной памяти соединен со вторым входомтретьего элемента 2 И-НЕ, выход которого подключен ко входу занесения информации первого,реверсивного счетчика, четвертый информационный выход узла постоянной памяти;подключен к тактовому входу регистра, пятый информаицонный выход узлапостоянной памяти соединен со вторым входом четвертого элемента 2 И-НЕ,выход которого подключен к уп"равлякщему входу вычитакщего счетчика, шестой информационный выходузла постоянной памяти подключен ковторому входу второго сумматора помодулю два 1 -го узла блокировки.Принцип работы устройства заключается в следукщем.Если в алгоритме БПФ с основани,ем два при выполнении базовой опера,ции обрабатываются два операнда, тор алгоритме с основанием четыре,восемь и т.д. обрабатываются четыре,восемь и т.д. операндов, адресакоторых отличаются информацией дляалгоритма.с основанием два в одномразряде, а с основанием четыре,восемь и т,д. в двух, трех и т.д.Разрядах. Номера заблокированныхразрядов соответствуют номеру слояалгоритма БПФ, если рассматриватьдва, три и т.д. разряда как,одинразряд в четвертичной, восьмиричной и т.д. системах счисления.1,Если заблокировать данные раз-ряды, т.е. не пропускать информацию данных разрядов на выход устройства, а вместо информации заблокированных разрядов на выход устройства подавать в двоичном коде номероперанда базовой операции, то можно адресовать четыре операнда, восемь операндов и т,.д. Каждое состояние счетчика адресует четыре, восемь и т.д. операндов, поэтомусчетчик обладает избыточностью, дляустранения которой вводится операция восстановления счетчика, описанная в прототипе. Единицы или нули восстанавливаются во всех заблокированных разрядах одновременно.При работе в,специальном слое безызбыточного алгоритма БПЙ ни одинкз разрядов не блокируется,к устройство функционирует так же, как0 В первоначальном состояииивсе счетчики обнулены. На с хровход счетчика 12 поступают актовые импульсы, по каждому и котоРыхсчетчик переключается в новое состояние. Каждое состояние счетчика определяет адрес, по которомуиз узла 13 происходит считываниеинформации, которая с помощью комбйнационной схемы на элементах 1417 Формирует управляющие сигналы 40на выходах блока управления 1, согласно временной диаграмме, представленной на фиг.4, где ТИ - тактовые импульсы; А 1 - А 4 - разрядныевыходы счетчика 121 18 - сигнал напервом входе блока управления 1 у19 - 24 - сигналы на первом, втором, третьем, четвертом, пятом,шестом выходах блока управления 1,Рассмотрим функционирование устройства при обработке й -ой пары1 -го слоя алгоритма БПФ.Пусть в данном цикле (16 тактов)ббрабатывается и -ая четверка 1 -гослоя алгоритма БПФ с основанием четыре. Во время обработки Ь -ой четверки операндов должна быть адресована Ь -1 четверка операндов длязаписи их в запоминакщее устройство (эта четверка .операндов былаобработана в предыдущем цикле)и 0+1 60четверка операндов для считыванияих иэ запоминающего устройства (этапара обрабатывается в следувщемцикле). Номеру слоя соответствуетсостояние счетчика 3. В соответст-, 65 30 и устройство адресации, описанное в прототипе,На фиг.1 представлена Функциональная схема предлагаемого устройства; на Фиг, 2 - функциональная схема узла блокировкина фиг.3 - функциональная схема блока управления на Фиг. 4 - временные диаграммы работы блока управления при формировании адресов алгоритма БПФ с основанием четыре.Устройство для формирования адресов процессора БПФ содержит блок 1 управления, первый реверсивный счетчик 2, второй реверсивный счетчик 3, дешифратор 4,)( узлов блоки ровки (разряда) 5, регистр б и вычитакщий счетчик 7.Каждый узел блокйровки 5 (Фиг.2) содержит элемент 2 И-НЕ 8, элемент 2 ИЛИ-НЕ 9 и два (двухвходовых) сум- р 0 матора по модулю два 10, 11.Блок управления (фиг.3) содержит счетчик 12, узел постоянной памяти 13 и четыре элемента 2 И-НЕ 14 - 17Устройство для.формирования адре сов процессора БПФ функционирует следующим образом (для примера рассмотрим алгоритм с основанием четыре). вин с этим блокируются 2 и 2 +1 разряды счетчика. В незаблокирован- ( ных разрядах информация с выходов счетчика 2 через два инвертора (элемент 2 ИЛИ-НЕ и первый двухвходовой сумматор по модулю два) и повторитель (второй двухвходовой сумматор по модулю два) поступает на выход устройства. В заблокированных разрядах информация с выходов счетчика 7 через инвертор (элемент 2 И-НЕ) и два повторителя (первый и второй двухвходовые сумматоры по модулю два) поступает на выход устройства. В счетчике 2 хранится инФормация, адресующая четверку операндов алгоритма БПФ с основанием четыре, а в счетчике 7 - информация, адресующая операнд в четверке выбранных операндов (состояние счетчика 7 11( адресует первый операнд, О - второй операнд, 10) - третий 1 операнд, 00( - четвертый операнд), Все счетчики переключаются по положительному перепаду импульса, т.е. из 0 в 1. В первом такте на пятом выходе блока управления 1 вырабатывается сигнал, по которому из счетчика 7 вычитается единица, чем адресуется первый операнд четверки операндов. Во втором такте на третьем входе блока управления вырабатывается сигнал, по которому в заблокированных разрядах восстанавливается значение 00, и сигнал на втором выходе блока управления 1, по которому из счетчика 2 вычитается единица, чем адресуется О -1 четверка операндов . Также вырабатывается сигнал на четвертом выходе блока управ- ления 1, по отрицательному перепаду которого в регистр б заносится . адрес первого операнда Ь)-ой четверки операндов. В третьем такте вырабатывается сигнал на пятом выходе блока управления 1, по которому из счетчика 7 вычитается единица, чем адресуется второй операнд четверки операндов. В четвертом такте вырабатывается сигнал на четвертом выходе блока управления 1, по которому в регистр б заносится адрес второго операнда (и)-ой четверки операндов. В пятом такте вырабатывается сигнал на пятом выходе блока управления 1, по которому из счетчика 7 вычитается единица, чем адресуется третий операнд четверки операндов. В шестом такте на четвертом выходе блока управления 1 выраба. тывается сигнал, по которому в регистр б заносится адрес третьего операнда (и)-ой четверки операндовВ седьмом такте на пятом выходе блока управления 1 вырабатывается сигнал, по которому из счетчика 7вычитается единица, чем адресуется четвертый операнд четверки операндов. В восьмом такте вырабатывается сигнал на четвертом выходеблока управления 1, по которомув регистр б заносится адрес четвертого операнда (1-1)-ой четверкиоперандов. В девятом такте на третьем выходе блока управления 1 вырабатывается сигнал, по которому взаблокированных разрядах восстанавливается значение 11, н сигнална первом выходе блока управления 1,по которому в счетчик 2 добавляется единица, чем адресуется в -аячетверка операндов. В десятом такте вырабатывается сигнал на третьем выходе блока управления 1, покоторому в.заблокированных разрядах счетчика 2 восстанавливаетсязначение 11, и сигнал на первом выходе блока управления 1, покоторому в счетчик 2 добавляетсяединица, чем адресуется(я+1)-аячетверка операндов, кроме того,в этом такте вырабатывается сигнална пятом выходе блока управления 1,по которому иэ счетчика 7 вычитается единица, чем адресуется первыйоперанд четверки операндов . Такжев десятом такте вырабатываетсясигнал на четвертом выходе блокауправления 1, по которому в регистрб заносится первый операнд (я+1)-ойчетверки операндов. В одиннадцатомтакте вырабатывается сигнал на пятом выходе блока управления 1, покоторому иэ счетчика 7 вычитаетсяединица, чем адресуется второй операнд четверки операндов. В двенадцатом такте на четвертом выходеблока управления 1 вырабатываетсясигнал, по которому в регистр б эаносится адрес второго операнда 01.+1) -ойчетверки операндов. В триннадцатом такте вырабатывается сигнална пятом выходе блока управления1, по которому из счетчика 7 вычитается единица, чем адресуетсятретий операнд (11+1)-ой четверкиоперандов. В четырнадцатом тактена четвертом выходе блока управления1 вырабатывается сигнал по которому в регистр б заносится третийоперанд (П+1)-ой четверки операндов.В пятнадцатом такте вырабатываетсясигнал на пятом выходе блока управления 1, по которому иэ счетчика 7 15 вычитается единица, чем адресуетсячетвертый операнд четверки операндов. В шестнадцатом такте вырабатывается сигнал на четвертом выходеблока управления 1, по которому 20 в регистр б заносится четвертый операнд (и+1)-ой четверки операндовЦикл повторяется снова и сновадо тех пор, пока не будут обработаны все четверки операндов по всем 25 слоям, после чего устройство начинает вырабатывать адреса пар операндов специального слоя беэиэбыточного алгоритма БПФ. В этом случаеустройство функционирует аналогич-. Зо но устройству, описанному в прототипе. На временной диаграмме работыблока управления 1 (фиг,4)иэображе"ны два цикла по восемь тактов.После обнуления. счетчиков устройство нова готово к работе.. Таким образом, предлагаемое устройство позволяет формировать адреса алгоритма БПФ с основанием вышедвух (четыре, восемь, шестнадцать 40 и т,д.), что расширяет его функциональные возможности.