Устройство для выполнения быстрого преобразования Фурье Советский патент 1982 года по МПК G06F17/14 

1

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, реализующих дискретное преобразование Фурье.5

Известно устройство для выполнения быстрого преобразования Фурье, содержащее счетчики, блоки оперативной памяти и блок управления l.

Наиболее близким техническим решением к изобретению является устройство для выполнения быстрого преобразованйя Фурье (БПФ), содержащее с.четчик, три сдвигателя, блок анализа s на четность, два блока оперативной памяти, блок Памяти тригонометрических коэффициентов, арифметический блок и блок управления 2j .

Недостатком известных устройств 20 является относительно большой объем аппаратурных затрат, необходимых для. их реализации.

Цель изобретения - упрощение устройства для выполнения быстрогб преобразования Фурье.

Поставленная цель достигается С)-ем, что в устройстве для выполнения быстрого преобразования Фурье, содержащем счетчик, три сдвигателя, блок анализа на четность, два коммутатора, арифметический блока оперативной памяти, блок памяти тригонометрических коэффициентов и блок управления, состояний из задающего reHepatopa, дешифратора, элемента И, вычитателя и регистра, причем выход задающего генератора и выход дешифратора через элемент И подключены к входу счетчика, выходы старших разрядов которого подключены к входу вычитаемого вычитателя и управляющим входам первого и второго сдвигателей, вход уменьшаемого вычитателя подключен к выходу регистра, выход вычитателя подключен к входу дешифратора и к управляющему входу третьего сдвигателя, выходы младших разрядов сметчика подключены к информационным входам первого, вто рого и третьего сдвигателей, выход арифметического блока через первый коммутатор подключен к информационным входам первого и второго блоков оперативной памяти, выходы которых через второй коммутатор подключены к первому входу арифметического блока, управляющие входы первого и второго коммутаторов подключены к прямому выходу блока анализа на четност адресный вход блока памяти тригонометрических коэффициентов и его выход подключены соответственно к выхо ду третьего сдвигателя и к второму входу арифметического блока, выходы младших разрядов счетчика подключены к входу блока анализа на четность, прямой и инверсный выходы которого подключены к дополнительному информа ционному входу .первого и второго сдвигателей соответственно, выходы первого И второго сдвигателей подклю чены к адресным входам первого и вто рого блоков оперативной памяти соответственно. На фиг. 1 представлена функционал ная схема устройства; на фиг, 2 функциональная схема блока управления . Устройство содержит счетчик 1, сдвигатели 2-, блок 5 управления, блок 6 анализа на четность, блок 7 n мяти тригонометрических коэффициентов, коммутаторы 8 и 9, блоки 10 и 1 оперативной памяти, арифметический блок 12. Блок 5 управления состоит из. задаю щего генератора 13, дешифратора 1, элемента И 15, вычитателя .16 и регистра 17Арих1)метический блок производит вычисления в соответствии с выражениями А 4 W В; А - w . в, где W exp(-j2n/N); J лРТ;N - число дискрет входного си|- К - показатель степени поворачивающего множителя; А и В - комплексные числа, определен ные на предыдущем шаге вычис лении. Для выполнения БПФ над N входными дискретами требуется п BogjiN шагов На каждом из шагов производится N/2 9 5 ,4 элементарных операций. Обозначим через i номер шага, а через j - номер элементарной операции. i 0,1,2,...,(п-1); j 0,1,2,...,(N/24). Адреса операндов А и В, участвующих в одной элементарной операции, различаются по признаку четности р. Значение р определяется следующим образом: р О, если число единиц в двоичном коде адреса операнда четное; р 1 в противном случае. Устройство работает следующим образом. В младших разрядах счетчика 1 записывается текущее значение J, а в старших - текущее значение i. Число j поступает на информационные входы сдвигателей 2-4, а число - на управляющие входы сдвигателей 2 и 3. В сдвигаталях 2 и 3 из кода j в соответствии с текущим номером шага БПФ i и с учетом четности кода формируются адреса операндов А и В, которые считываются из блоков 10 и 11 оперативной памяти. Пусть Jn jn-K -J Jo двоичный код j. На информационные входы сдвигателя 2 поступает код . J(J07 на информационные входы сдвигателя 3 PJnJt - JjJd- Сигналы р и р вырабатываются блоком 6 анализа на четность в зависимости от четности .кода j. Сдвигатели 2 и 3 осуществляют циклический сдвиг кода, поступающего на их информационные входы, на i разрядов вправо. Старший разряд на выходе сдвигателей не используется, остальные разряды подаются на адресные входы блоков 10 и 11 оперативной памяти. В сдвигателе k определяется адрес велиуины W, считываемой из блока 7 памяти тригонометрических коэффициентов в арифметический блок 12. Этот адрес получается из числа j. посредством записи нулей в (n-1-i) младших разрядов последнего. На информационные входы сдвигателя 5 поступает код, состоящий из 2 разрядов, где 8 разрядность кода j. Вб старших разрядов этого кода записаны нули, в 6 младших - код j. Входной код сдвигателя подвергается циклическому сдвигу на {n-1-i) разрядов влево, при этом на выходе используются f младших разрядов сдвигателя. Число (n-1-l) определяется вычитателем, входящим в состав блока k управления посредством вычитания из кода (п-1), хранящегося в регистре блока управления, кода i, поступающего со счетчика 1. Задающий генератор 13 блока управления формирует тактовые импульсы, поступающие на счетчик } в продолжение цикла вычислений и запрещаемые дешифратором 1 через элемент И 15 по его окончании. Значения А и В поступают в виде результата вычислений по формуле (1) на предыдущем цикле из арифметического блока 12 через коммутатор 8 в блоки 10 и 11 оперативной памяти. Операнды для данного цикла вычислени считываются в арифметический блок 12 из блоков 10 и 11 оперативной памяти (А и в) и из блока 7 памяти тригонометрических коэффициентов (W), Коммутаторы 8 и 9 осуществляют адресаци блоков 10 и 11 оперативной памяти с учетом признака четности р В предлагаемом устройстве проверк на четность подвергается код J, Так как его признак четности р равен соответствующему признаку для адреса одного из операндов и инверсии соответствующего признака для адреса дру то.го операнда, участвующего в эле-, «ентарной операции. Контроль четности кода j позволяет в предложенной структура непосредственно использовать выходные коды сдвигателей 2 и 3 для адресации блоков 10 и 11 оперативной памяти без дополнительного переключения этих кодов. Таким образом, отпадает необходимость в использовании коммутатора, что позволяет упростить устройство и повысить его быстродействие. Формула изобретения Устройство для выполнения быстрого преобразования Фурье, содержащее счетчик, три сдвигателя, блок анализа на четность, два коммутатора, арифметический блок, два блока оперативной памяти, блок памяти тригонометрических коэффициентов и блок управления, состоящий из задающего генератора, дешифратора, элемента И, вычитателя и регистра, причем выход задающего генератора и выход дешифратора через элемент И подключены к входу счетчика, выходы старших разрядов которого подключены к входу вычитаемого вычитателя, управляющим входам первого и второго сдвигателей, вход уменьшаемого вычитателя подключен к выходу регистра, выход вычитателя подключен к входу дешифратора и к управляющему входу третьегЪ сдвигателя, выходы младших разрядов счетчика подключены к информационным входам первого, второго и третьего сдвигателей , выход арифметического блока че- . рез первый коммутатор подключен к информационным входам первого и второго блоков оперативной памяти, выходы которых через второй коммутатор подк1Ж)чены к первому входу арифметического блока, управляющие входы первого и второго коммутаторов подклю- чены к прямому выходу блока анализа на четность, адресный вход блока памяти тригонометрических коэффициентов и его выход подключены соответственно к выходу третьего сдвигателя и к второму входу арифметического блока, отличающееся тем, что, с целью упрощения,в нем выходы младших разрядов счетчика подключены к входу блока анализа на четность, прямой и инверсный выходы которого подключены к дополнительному информационному входу первого и второго сдвигателей соответственно, выходы первого и второго сдвигателей подключены к адресным входам первого и второго блоков оперативной памяти соответст венно. Источники информации, принятые во внммзние при экспертизе Т. Авторское свидетельство СССР № 590750i кл. G Об f 15/332, J375. 2. ЗЕЕЕ Transactloris on Acoustics, Speech and Signal Processing,TASSP-76, December 1976, p. 577 (прототип).

5 Г

€Z