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

.С. Альховик ческий институт 71) Заявител енинградскии ордена Ленина им. В.И. Ульяно(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕжет реа- ие Наиболее близ шением к изобрет ство для выполне разования Фурье счетчик, три сдви на четность, два памяти, блок пам ких коэффициенто блок и блок упраНедостатком и является относит аппаратурных зат их реализации. Изобретение относится к автоматике и вычислительной технике и мо быть использовано в устройствах, лизующих дискретное преобразован Фурье.Известно устройство для выполнени быстрого преобразования Фурье, содер жащее счетчики, блоки оперативной памяти и блок управления 11. ким техническим реению является устройния быстрого преоб- (БПФ), содержащее гателя, блок анализаблока оперативной яти тригонометричесв, арифметический вления 21.звестных устройств ельно большой объем рат, необходимых для 2Цель изобретения - упрощение устройства для выполнения быстрогд преобразования фурье.Поставленная цель достигается %ем, что в устройстве для выполнения быстрого преобразования Фурье, содержащем счетчик, три сдвигателя, блок анализа на четность, два коммутатора, арифметический блокдва блока оперативной памяти, блок памяти тригонометрических коэффициентов и блок управления, состоящий из задающего генератора, дешифратора, элемента:И, вычитателя и регистра, причем выход задающего генератора и выход дешифратора через элемент И подключены к входу счетчика, выходы старших разрядов которого подключены к входу вычитаемого вычитателя и управляющим входам первого и второго сдвигателей, вход уменьшаемого вычитателя подключен к выходу регистра, выход вычитателя подключен к входу дешифратора и к управляюще у3 95508входу третьего сдвигателя, выходымладших разрядов счетчика подключеныК информационным входам первого, второго и третьего сдвигателей, выходарифметического блока через первый зкоммутатор подключен к информационным входам первого и второго блоковоперативной памяти, выходы которыхчерез второй коммутатор подключенык первому входу арифметического бло Ока, управляющие входы первого и второго коммутаторов подключены к прямому выходу блока анализа на четность 1адресный вход блока памяти тригонометрических коэффициентов и его выход подключены соответственно к выходу третьего сдвигателя и к второмувходу арифметического блока, вь 1 ходымладших разрядов счетчика подключенык входу блока анализа на четность, 2 впрямой и инверсный выходы которогоподключены к дополнительному информационному входу .первого и второгосдвигателей соответственно, выходыпервого и второго сдвигателей подклюцены к адресным входам первого и второго блоков оперативной памяти соответственно.На Фиг. 1 представлена функциональная схема устройства; на фиг. 2 - звфункциональная схема блока уп 9 авления.Устройство содержит счетчик 1,сдвигатели 2-4, блок 5 управления,блок 6 анализа на четНость, блок 7 па-мяти тригонометрических коэффициентов, коммутаторы 8 и 9, блоки 10 и 11.оперативной памяти, арифметическийблок 12.Блок 5 управления состоит иэ задаю.щего генератора 13, дешифратора 14,элемента И 15, вычитателя 16 и регистра 17.Арифметический блок производит вьчисления в соответствии с выражениямиК, 45В =А-УкВ,1где И = ехр(-3 2 п/й);й - число дискрет входного сигнала;50К - показатель степени поворачивающего множителя;А и В - комплексные числа, определен"ные на предыдущем шаге вычислений.Для выполнения БПФ над й входнымидискретами требуется и = ВодИ шагов.На каждом из шагов производится М/2 5 4элементарных операций. Обозначим черезномер шага, а через 3 - номерэлементарной операции.0,1,2(п);0,1,2. (й/2-1),Адреса операндов А и В, участвующих в одной элементарной операции,различаются по признаку четности р,Значение р определяется следующим образом: р = 0, если число единиц вдвоичном коде адреса операнда четное; р = 1 в противном случае.Устройство работает следующим образом.В младших разрядах счетчика 1 записывается текущее значение 3, а встарших - текущее значение . Число 3 поступает на информационные входы сдвигателей 2-4, а число- науправляющие входы сдвигателей 2 и 3.В сдвигателях 2 и 3 из кода 3 в соответствии с текущим номером шагаБПФи с учетом четности кода формируются адреса операндов А и В, которые считываются из блоков 10 й 11оперативной памяти.Пусть 3 333 д - двоичныйкод 3, На информационные входы сдви"гателя 2 поступает код Р 33.31.она информационные входы сдвйгателя 3 Р 333,3. Сигналы р и р вырабатываются блоком 6 анализа на четность в зависимости от четности кода3. Сдвигатели 2 и 3 осуществляют циклический сдвиг кода, поступающегона их информационные входы, наразрядов вправо. Старший разряд навыходе сдвигателей не используется,остальные разряды подаются на адресные входы блоков 10 и 11 оперативнойпамяти.В сдвигателе 4 определяется адресвеличины Ч", считываемой иэ блока 7памя ти три гономе три ческих коэффи ци ентов в арифметический блок 12. Этотадрес получается из числа 3 посредством записи нулей в (и-1) младшихразрядов последнего. На и нформационные входы сдвигателя 5 поступает код,состоящий из 2 разрядов, где 1разрядность кода 3. В 3 старших разрядов этого кода записаны нули, вмладших - код 3 . Входной код сдвигателя подвергается циклическому сдвигуна (и-) разрядов влево, при этомна выходе используются 1 младших разрядов сдвигателя.Число (и"1) определяется вычитателем, входящим в состав блока 4Формула изобретения 5 9550 управления посредством вычитания из, кода (п), хранящегося в регистре блока управления, кода 1, поступающего со счетчика 1. Задающий генера. тор 13 блока управления формирует тактовые импульсы, поступающие на счетчик 1 в продолжение цикла вычислений и запрещаемые дешифратором 11 через элемент И 15 по его окончании.Значения А и В поступают в виде 10 результата вычислений по формуле (1) на предыдущем цикле из арифметического блока 12 через коммутатор 8 в блоки 10 и 11 оперативной памяти. Операнды для данного цикла вычислений 1 считываются:в арифметический блок 12 из блоков 10 и 11 оперативной памяти (А и В) и из блока 7 памяти тригонометрических коэффициентов (ЧК), Коммутаторы 8 и 9 осуществляют адресацию о блоков 10 и 11 оперативной памяти с учетом признака четности рВ предлагаемом устройстве проверке на четность подвергается код ), так как его признак четности р равен со- И ответствующему признаку для адреса одного из операндов и инверсии соответствующего признака для адреса дру" гого операнда, участвующего в эле-. ментарной операции. 39Контроль четности кода ) позво-, ляет в предложенной структуре непосредственно использовать выходные коды сдвигателей 2 и 3 дпя адресации блоков 10 и 11 оперативной памяти без дополнительного переключения этих кодов. Таким образом, отпадает необходимость в использовании коммутатора, что позволяет упростить устройство и повысить его быстродействие. 4 в Устройство для выполнения быстрого 4 преобразования фурье, содержащее счетчик, три сдвигателя, блок анализа на четность, два коммутатора, ариф" метический блок, два блока оперативной памяти, блок памяти тригонометри 85 6 ческих коэффициентов и блок управления, состоящий из задающего генератора, дешифратора, элемента И, вычитателя и регистра, причем выход задающего генератора и выход дешифратора через элемент И подключены к вхо"ду счетчика, выходы старших разрядовкоторого подключены к входу вычитаемого вычитателя, управляющим входампервого и второго сдвигателей, входуменьшаемого вычитателя подключен квыходу регистра, выход вычитателяподключен к входу дешифратора и куправляющему входу третьегь сдвигателя, выходы младших разрядов счетчикаподключены к информационным входампервого, второго и третьего сдвигателей, выход арифметического блока через первый коммутатор подключен к информационным входам первого и второго блоков оперативной памяти, выходыкоторых через второй коммутатор подключены к первому входу арифметического блока, управляющие входы первого и второго коммутаторов подклюцены к прямому выходу блока анализана четность, адресный вход блока памяти тригонометрических коэффициентов и его выход подключены соответственно к выходу третьего сдвигателяи к второму входу арифметическогоблока, о т л и ч а ю щ е е с я тем,что, с целью упрощения,в нем выходымладших разрядов счетчика подключе"ны к входу блока анализа на четность,прямой и инверсный выходы которогоподключены к дополнительному информационному входу первого и второго сдви.гателей соответственно, выходы перового и второго сдвигателей подключены1к адресным входам первого и второгоблоков оперативной памяти соответст"венно,.Источники информации,принятые во внимание при экспертизе955085 иг,Г рофеев Составитель И, ДоРедактор С, Тараненко Техред М.Тепер Корректор А. Гриценко Заказ 6439/5 иал ППП "Патент", г, Ужгород, ул. Проектная, 4 Под ного комитета ний и открыти Раушская наб. Тираж 731 ВНИИПИ Государстве по делам изобрет 13035, Москва, Ж, писноеСССРй