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

(72) Авторы иэобретеии я

А.С. Альховик и И.Г Дорофеев

1., °

Ленинградский ордена Ленина электротех ческий. институт им. В.И. Ульянова (Ленина) (7l ) Заявитель (4) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

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

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

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

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

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

3 95508 входу третьего сдвигателя, выходы младших разрядов счетчика подключены к информационным входам первого, второго и третьего сдвигателей, выход арифметического блока через первый коммутатор подключен к информационным входам первого и второго блоков оперативной памяти, выходы которых через второй коммутатор подключены к первому входу арифметического бло- tO ка, управляющие входы первого и второго коммутаторов подключены к прямому выходу блока анализа на четность адресный вход блока памяти тригонометрических коэффициентов и его вы- (3 ход подключены соответственно к выходу третьего сдвигателя и к второму входу арифметического блока, вь1ходы младших разрядов счетчика подключены к входу блока анализа на четность, 2в прямой и инверсный выходы которого подключены к дополнительному информационному входу .первого и второго сдвигателей соответственно, выходы первого и второго сдвигателей подклю- 2S чены к адресным входам первого и второго блоков оперативной памяти соответственно.

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - зв функциональная схема блока управления.

Устройство содержит счетчик 1, сдвигатели 2-4, блок 5 управления, блок 6 анализа на четность, блок 7 па- мяти тригонометрических коэффициентов, коммутаторы 8 и 9, блоки 10 и 11. оперативной памяти, арифметический блок 12.

Блок 5 управления состоит иэ задающего генератора 13, дешифратора 14, элемента И 15, вычитателя 16 и регистра 17.

Арифметический блок производит вычисления в соответствии с выражениями

V., 4S (1)

В=А-W ° В, 1 где W = ехр(-32n/N);

3= - .

N — число дискрет входного сигнала;

К - показатель степени поворачивающего множителя;

А и  — комплексные числа, определен" ные на предыдущем шаге вычислений.

Для выполнения БПФ над N входными дискретами требуется n = Bogs N шагов.

На каждом из шагов производится N/2

5 4 элементарных операций. Обозначим через i номер шага, а через j - номер элементарной операции.

0,1,2,...,(n-1};

= 0,1,2,...,(N/2-1).

Адреса операндов А и В, участвующих в одной элементарной операции, различаются по признаку четности р.

Значение р определяется следующим образом: р = О, если число единиц в двоичном коде адреса операнда четное; р = 1 в противном случае.

Устройство работает следующим образом.

В младших разрядах счетчика 1 записывается текущее значение j, а в старших - текущее значение 1. Число j поступает на информационные входы сдвигателей 2-4, а число 1 — на управляющие входы сдвигателей 2 и

В сдвигателях 2 и 3 из кода 3 в соответствии с текущим номером шага

БПФ i и с учетом четности кода формируются адреса операндов А и В, которые считываются из блоков 10 и 11 оперативной памяти.

Пусть 3„ 5 „ „ ...Jtjo - двоичный код 3 . На информационные входы сдви" гателя 2 поступает код р3„3,! „ ...Jt5o на информационные входы сдвйгателя 3р3 J „„...j, jo. Сигналы р и р вырабатываются блоком 6 анализа на четность в зависимости от четности кода

J. Сдвигатели 2 и 3 осуществляют циклический сдвиг кода, поступающего на их информационные входы, на разрядов вправо. Старший разряд на выходе сдвигателей не используется, остальные разряды подаются на адресные входы блоков 10 и 11 оперативной памяти.

B сдвигателе 4 определяется адрес величины W", считываемой иэ блока 7 памя ти три гономе три ческих коэффи ци ентов в арифметический блок 12. Этот адрес получается и з числа j посредством записи нулей в (n-1 i) младших разрядов последнего. На и нформационные входы сдвигателя 5 поступает код, состоящий из 2 разрядов, где Г разрядность кода 5 . В 3 старших разрядов этого кода записаны нули, в младших - код j . Входной код сдвигателя подвергается циклическому сдвигу на (n-1-i) разрядов влево, при этом на выходе используются младших разрядов сдвигателя.

Число {и-1-i) определяется вычитателем, входящим в состав блока 4

Формула изобретения

5 9550 управления посредством вычитания из, кода (n-1), хранящегося в регистре блока управления, кода i, поступающего со счетчика 1. Задающий генератор 13 блока управления формирует тактовые импульсы, поступающие на счетчик 1 в продолжение цикла вычислений и запрещаемые дешифратором 14 через элемент И 15 по его окончании.

Значения А и В поступают в виде 1о результата вычислений по формуле (1) на предыдущем цикле из арифметического блока 12 через коммутатор 8 в блоки 10 и 11 оперативной памяти.

Операнды для данного цикла вычислений 1 считываются:в арифметический блок 12 из блоков 10 и 11 оперативной памяти (А и В) и из блока 7 памяти тригонометрических коэффициентов (Ч ), Коммутаторы 8 и 9 осуществляют адресацию m блоков 10 и 11 оперативной памяти с учетом признака четности с

В предлагаемом устройстве проверке на четность подвергается код J так как его признак четности р равен со- И ответствующему признаку для адреса одного из операндов и инверсии соответствующего признака для адреса дру-ого операнда, участвующего в эле-. ментарной операции. 39

Контроль четности кода J позволяет в предложенной структуре непосредственно использовать выходные коды сдвигателей 2 и 3 дпя адресации блоков 10 и 11 оперативной памяти без дополнительного переключения этих кодов. Таким образом, отпадает необходимость в использовании коммутатора что позволяет упростить устройство и повысить его быстродействие. 4в

Устройство для выполнения быстрого4 преобразования Фурье, содержащее счетчик, три сдвигателя, блок анализа на четность, два коммутатора, арифметический блок, два блока оперативной памяти, блок памяти тригонометри85 6 ческих коэффициентов и блок управления, состоящий из задающего генератора, дешифратора, элемента И, вычитателя и регистра, причем выход задающего генератора и выход дешифратора через элемент И подключены к вхо" ду счетчика, выходы старших разрядов которого подключены к входу вычитаемого вычитателя, управляющим входам первого и второго сдвигателей, вход уменьшаемого вычитателя подключен к выходу регистра, выход вычитателя подключен к входу дешифратора и к управляющему входу третьегь сдвигателя, выходы младших разрядов счетчика подключены к информационным входам первого, второго и третьего сдвигателей, выход арифметического блока через первый коммутатор подключен к информационным входам первого и второго блоков оперативной памяти, выходы которых через второй коммутатор подключены к первому входу арифметического блока, управляющие входы первого и второго коммутаторов подклю чены к прямому выходу блока анализа на четность, адресный вход блока памяти тригонометрических коэффициентов и его выход подключены соответственно к выходу третьего сдвигателя и к второму входу арифметического блока, о т л и ч а ю щ е е с я тем, что, с целью упрощения,в нем выходы младших разрядов счетчика подключе" ны к входу блока анализа на четность, прямой и инверсный выходы которого подключены к дополнительному информационному входу первого и второго сдвигателей соответственно, выходы перового и второго сдвигателей подключены

1 к адресным входам первого и второго блоков оперативной памяти соответст" венно.. . Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР и 590750; кл. G 06 f 15/332, 1975. 2. 3 ЕЕЕ Transactions on Acoustics, Speech and Signal Ргосезз 1ng,TASSP-76, December 1976, р. 577 (прототип).

955085

Раа 2

Заказ 6439/55

Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35,, Раушская наб., д. 4/5

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

Составитель И. Дорофеев

Редактор С. Тараненко Техред M.Tenep Корректор А. Гриценко