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

 

Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования в устройствах цифровой обработки сигналов. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что в состав устройства входят M(M=LOG<SB POS="POST">N</SB>N

N - размер преобразования) процессорных модулей, M блоков постоянной памяти, M блоков умножения и блок управления, причем каждый процессорный модуль содержит три арифметических блока, четыре мультиплексора, два элемента задержки и группу из четырех элементов задержки с соответствующими связями между узлами устройства. 5 ил.

СОЮЗ СОВЕТСНИХ.

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

РЕСПУБЛИН (19) (И) (я) 4 G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Il0 ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4383318/24-24 (22) 23.02.88 (46) l5..09..89. .Бюл. .Ф 34 (72) Д.В. Корчев, В. В. Гнилицкий, Ю. С. Каневский, О.M. Поваренко и Т.Н. Черная (53) 631.32(088.8) (56) Авторское свидетельство СССР

1(1348815, кл. G 06 F 15/332, 1986 °

Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов.-M.: Мир, 1978, с. 674. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и предназначено

Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования Фурье (БПФ) по основанию

4 в устройствах цифровой обработки сигналов.

Цель изобретения — упрощение устройства.

На фиг. 1 и 2 приведена структурная схема устройства; на фиг. 3— структурная схема арифметического блока1 на фиг.4 — структурная схема блока умножения; на фиг, 5 — структурная схема блока управления с генератором тактовых импульсов.

Устройство содержит процессорные модули l.i (i =,M) информационные входы 2 ° i, выходы З.i, мультиплексоры 4.i, тактовые входы 5.i группу

2 для выполнения алгоритма быстрого преобразования в устройствах цифровой обработки сигналов. Цель изобретения — упрощение устройства. Поставленная цель достигается за счет того, что в состав устройства входят

M(M = log„N; N — размер преобразования) процессорных модулей, M блоков постоянной памяти, М блоков умножения и блок управления, причем каждый процессорный модуль содержит три арифметических блока, четыре мультиплексора, два элемента задержки и группу из четырех элементов задержки с соответствующими связязми между узлами устройства. 5 ил. элементов 6 ° i задержки, арифметические блоки 7.i элементы 8.i, задерж. ки, управляющие входы 9.i и 10,i, блоки Il.i постоянной памяти, блоки

12.i умножения и адресные входы 13.i.

Арифметический блок образуют мультиплексоры 14 и 15, сумматоры-вычитатели 16 17, элемент ИСКЛЮЧАЮЩЕЕ

ИЛИ 18.

Блок умножения содержит умножители 19-22, вычитатель 23 и сумматор 24.

Блок управленя состоит из генератора 25 тактовых импульсов, счетчика 26, дешифратора 27 и тактового выхода 28.

Рассмотрим работу устройства для

N = 16, М = 2. В этом случае устрой-, 1 ство состоит из двух модулей 1.1 и

26 последовательно изменяются от

1000 до 1011, Верхний логический уровень присутствует на третьем входе 5.1. Входные отсчеты поступают в третий элемент 6.1 задержки. Отсчеты в первом и втором элементах

6.1 задержки циклически сдвигаются через соответствующие мультиплексоры 4.!. Ha первый управляющий вход 9.1 поступает верхний логический уровень, а на первый управляющий вход 10.1 — нижний логический уровень . Это соответствует операции А +JB для первого арифметического блока 7.1. На вторые управляющие входы 9.1 и 10.1 . поступают нижние логические уровни. При этом второй арифметический блок 7.1 выполняет операцию (А+В)+С, где (А+В) — операнд, поступающий на первый вход, а С вЂ” операнд, поступающий на второй вход второго арифметического блока 7.1. В первый элемент 8.1, I задержки записываются соответствующие значения: X(0)+jX(4) Х (1)+

+jX(5); Х(2)+1Х(б); X(3)+jX(7). Во второй элемент 8.1 задержки записываются значения: X(0)+X(4)+X (8);

X(1)+X (5)+X(9), Х (2)+Х(6)+Х (10), Х {3)+X (7)+X(11) .

В следующие четыре такта на вход

2.1 поступают значения Х(12), Х (13), Х(14) и Х(15), состояния счетчика

26 последовательно изменяются от

1100 до 1111..Верхний логический уровень поступает на четвертый вход

5.1. На другие входы 5.1 поступают нижние логические уровни. Входные отсчеты записываются в четвертый элемент задержки 6.1 и на второй вход третьего арифметического блока 7.1 .

На йервые и вторые управляющие входы

9.1 и 10 ° 1 поступают верхние логические уровни. На треть и управляющие входы 9.1 и 10.1 поступают нижние логические уровни, первый арифметический блок 7.1 выполняет операцию А-В, второй арифметический блок 7.1 выполняет операцию (А+!В)-С. Третий арифметический блок 7.! выполняет операцию (А+В+С)+D; где (А+В+С) операнд, поступающий на первый вход третьего арифметического блока 7.1, а D - операнд, поступающий на второй вход третьего арифметического блока

7.1. В первый элемент 8.1 задержки записываются значения: Х(0)-X(4), Х (1)-Х (5), Х (2)-Х (6); Х(3)-Х (7) . Во

3 1508233

1.2. Допустим, изменения информации производятся положительным фронтом синхросигнала, вырабатываемым генератором 25 тактовых импульсов.

Дискретные элементы 6.1 и 8.1 задержки содержат по четыре регистра ° Дискретные элементы 6.2 и 8.2 задержки содержат по одному регистру. Счетчик 26 — двоичный, четырехразрядный, !О соединенный с двумя дешифраторами 27.

В первые четыре такта на вход 2.1 устройства поступают входные отсчеты Х (10), Х (1), Х (2), Х (3) . Состояния счетчика 26 последовательно из- 5 меняются от 0000 до 0011. На управ— ляющем входе 5.1 первого мультиплексора 4.1 находится верхний логический уровень, на остальных управляющих входах — нижний логический уро- 20 вень . При верхнем логическом уровне на управляющем входе 9,1 первый мультиплексор 4.1 производит прием информации со своего первого входа. Поэтому первые четыре отсчета последовательно записаны в первый элемент

6.1 задержки.

В следующие четыре такта на вход

2.1 устройства поступают отсчеты

Х(4), Х(5), Х(6) и Х(7) . Состояния 30 счетчика 26 изменятся последовательно от 0100 до 0111. При этом верхний логический уровень поступает на второй вход 5.1 с дешифратора 27, на остальных входах имеется нижний логический уровень. Первый мультиплексор 4.1 принимает информацию с второго входа. Поэтому первые четыре отсчета циклически сдвигаются в первом элементе 6.1 задержки. Вторая 40 четверка отсчетов заносится во второй элемент 6.1 задержки и поступает .на второй вход первого арифметического блока 7.1. На первый вход первого арифметического блока 7.1 поступают 45 последовательно первые четыре отсчета. На управляющие входы 9.1 и 10.1 первого арифметического блока 7,1 поступают нижние логические уровни, что соответствует операции А + В, где

А — операнд на первом входе, В— операнд на втором входе первого арифметического блока 7.1 . За четыре такта в первый элемент 8.1.задержки заносится четыре суммы: Х(0) + Х(4); 55

Х(1) + Х(5) > Х(2) + Х(6), Х(3) + Х(7).

За третью четверку тактов на вход

2.1 поступают отсчеты X(8), Х(9), X(10) и X (11), Состояния счетчика

5 1 50823 второй элемент 8.1 задержки записываются значения Х (0)+jX (4)-Х (8);

Х (1)+jX (5)-Х (9) ", Х (2) +jX (6) -Х (10), Х(3)+)Х(7)-Х (11). На выходе 3.1 последовательно появляются значения

Х(0)+Х (4)+Х (8)+X(12); Х(1)+Х (5)+

+Х (9)+X()3); Х(2)+Х (6)+Х(10)+Х (14);

Х (3)+X(7)+X (! I )+Х (15) . На второй вход блока 12.1 умножения поступает значение W, где W> exp(-j 2 п/N).

На вход 2.2 модуля 1.2 поступают четыре первых результата первой итерации алгоритма БПФ, В следующую четверку тактов модуль 1.1 работает аналогично первой четверке тактов. На вход 2.1 поступают первые четыре отсчета следующего входного массива. Состояния счет. чика 26 последовательно изменяются от 0000 до 0011. Загрузка информации производится в первый элемент

6,1 задержки. На первый вход 9.1 поступает нижний логический уровень, на первый вход 10.1 — верхний логи в 25 ческий уровень. Первый арифметический блок 7.1 выполняет операцию

А-jB. В первый элемент задержки 8 поступают значения: Х (0)-jX(4), Х (1)-jX (5), Х (2)-jX (6), Х (3)-jX (7) . На вторые управляющие входы 9. 1 и 10. 1 поступают нижние логические уровни.

Второй арифметический блок 7.1 выполняет операцию (A-В)+С. Во второй элемент 8.1 задержки поступают значения: Х (О) -Х (4) +Х (8); Х (1 ) -Х (5) +Х (9), Х (2)-Х (6) +Х (1 0); Х (3) — Х (7) +Х (1 1 ) . На третий управляющий вход 9. 1 поступает нижний логический уровень, на третий управляющий вход 10.1 — верх40 ний логический уровень. Третий арифметический блок выполняет операцию (A+j В-С) - j D. На выходе 3. 1 модуля

1. 1 последовательно появляются значения: Х(0)+jX (4)-Х(8)-jX(12), Х(1)+

+jX(5)-Х(9)-jX(13); Х(2)+jХ(6)45

-X(10)-jX(14), X(3)+jX(4)-Õ (11)-jX(15)> которые поступают на первый вход блока 12.1 умножения. На второй вход блока умножения поступает последовательность весовых коэффициено тов И Ч,ь .И,ь И„6 . На вход

2.2 второго модуля 1.2 поступает вторая четверка результатов первой итерации алrоритма БНФ.

В шестую четверку тактов первый модуль 1.1 работает аналогично второму. На вторые и третьи управляющие входы 9.1 и 10.1 поступают верхние

3 6 логические уровни. При этом второй арифметический блок 7. 1 выполняет операцию (А-j B)-С, а третий арифметический блок 7.1 — (А-В+С)-D. Bo второй элемент 8.1 задержки поступают значения. Х(0)-jX(4)-Х(8);

Х(1)-jX(5)-X(9); Х(2)-jX(6)-Х(!О)»

Х(3)-1Х(7)-Х (11) . На выходе 3,1 присутствует последовательность значений: Х (О)-Х (4)+Х(8)-Х (12); Х(1)-Х (5)+X(9)-Х (13); Х (2)-Х(6)+Х (10)-Х (14); Х (3)-Х(7)+Х(11)-Х (15) . На второй вход блока умножения поступает последовательность значений

И, И,6, И 6, И, на вход 2.2 второго модуля 1.2 — третья четверка результатов первой итерации.

В седьмой четверке тактов элементы нового массива обрабатываются аналогично третьей четверке тактов.

На третий управляющий вход 9.1 поступает нижний логический уровень, третий арифметический блок 7.1 выполняет операцию (А-jB-c)+jD. На выход 3.1 поступают значения: Х(0)-jX(4)-Х(8)+1Х(12)1 Х (1)-jX (5)-Х (9)+

+jX (13), Х (2)-jX(6)-X (10)+jX(14);

Х (3)-jX (7)-Х (11) - .jX,15) . На второй вход блока умножения поступают знаxoд

2.2 второго модуля ).2 поступают последние четыре результата первой итерации.

Дальнейшая работа модуля 1.1 продолжается по описанному алгоритму.

Рассмотрим работу второго модуля

1.2. Элементы 6.2и 8.2 задержки содержат по одному регистру. На второй вход блока 12.2 умножения поступает о постоянное значение W . Начнем рас ь сматривать работу модуля 1.2 с четвертой четверки тактов работы устройства.

Двенадцатый такт. Состояние счетчика 26-1100. На входе 2.2 модуля присутствует значение 7(0) = X(0)+

+Х. (4)+Х (8)+Х (12) . Верхний логический .уровень снимается с первого выхода дешифратора 27, соединенного с первым входом 5.2. Значение Y(0) через первый мультиплексор 4.2 поступает на вход первого элемента 6.2 задержки.

Тринадцатый такт. Состояние счетчика 26-1101. На входе 2,2 имеется значение Y(1) = X(1)+X(5)+X(9)+X (13) .

Верхний логический уровень находится на втором входе 5.2. Значение Y(l) 1508233

55 поступает на вход второго элемента задержки 6.2. Значение Y(0) через первый мультиплексор 4.2 поступает снова на вход .первого элемента 6.2 задержки. На первые управляющие входы 9.2 и 10.2 поступают нижние логические уровни. Первый арифметический блок 7.2 выполняет операцию А+В. На его выходе значение Y(0) + Y(1)..

Четырнадцатый такт. На вход 2.2 поступает значение Y(2) = Х (2)+Х(6)+

+Х (10)+Х (14) . Состояние счетчика

26-lll0. Верхний логический уровень поступает на третий вход 5.2. На первый управляющий вход 9.2 поступает верхний логический уровень. На .первый управляющий вход 1 0.2 и вторые управляющие входы 9.2 и 10.2 посту— пают нижние логические уровни. Пер— вый арифметический блок 7.2 выполняет операцию. A+jB. На. его выходе присутствует значение Y(0)+jY(1).

Второй арифметический блок 7.2 выполняет операцию (А+В)+С. На его выходе имеется значение Y (0) +Y (I ) +Y (2), Пятнадцатый такт. На входе 2.2 находится значение Y(3) = Х(3)+Х (7)+

+Х (11)+Х (15) . Состояние счетчика 261111. Верхний логический уровень поступает на четвертый вход 5.2.На первые и вторые упавляющие входы 9.2 и 10.2 поступают верхние логические уровни, на третьи — нижние логические уровни. Первый арифметический блок

7.2 выполняет операцию А-В. На его выходе имеется значение 7(0) -Y(1), второй арифметический блок 7.2 выполняет операцию (A+j3)-С. На его выходе находится значение Y(0)+jY(1)-7(2), Третий арифметический блок

7.2 выполняет операцию (А+В+С)+О. На его выходе присутствует значение

Y(0)+Y(1)+Y(2)+Y(3) . На выходе блока умножения 12.2 имеется значение F(0), Последовательность смены управляющих сигналов на втором модуле 1.2 происходит аналогично первому модулю

1.1, но в четыре раза быстрее. По1 этому ее дальнейшая работа соответствует описанному алгоритму. С выхода блока 12.2 умножения снимаются результаты БПФ F(K) в четвертичноинверсном порядке.

При описании работы устройства предполагалось, что блоки 12.i умножения не тактируются и не вносят задержку при работе, поскольку внут10 l5

45 ренние регистры в их схемах не меняют сущности работы устройства.

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

Устройство для вычисления быстрого преобразования Фурье, содержащее М (И = 1оя„И; Н вЂ” размер преобразования) процессорных модулей, М .блоков постоянной памяти и блок управления, причем инормационный вход первого процессорного модуля является информационным входом устройства, тактовые выходы i-й группы (i = 1,Ì) блока управления подключены к тактовым входам группы i-ro процессорного модуля, — и адресный выход блока управления подключен к адресному входу i-го блока постоянной памяти, о т л и ч а ю щ е е с я тем,,ч=о, с целью упрощения устройства, оно содержит М блоков умножения, причем выход i-го процессорного модуля подключен к первому входу i-ro блока умножения, второй вход которого подключен к выходу i-го блока постоянной памяти, выходы группы которого подключены к управляющим входам группы i-ro процессорного модуля, выход j-ro (j = l; М-1) блока умножения подключен к информационному входу (j+1)-го процессорного модуля, а выход M-го вычислительного модуЛя является информационным выходом устройства, при этом х-й процессорный модуль содержит три арифметических блока, четыре мультиплексора, два элемента задержки и группу из четырех элементов задержки, выход первого мультиплексора подключен к входу первого элемента задержки группы, выход которого подключен к первому информационному входу первого мультиплексора и первому информационному входу первого арифметического блока, выход которого подключен к входу первого элемента задержки, выход которого подключен к первому информационному входу второго арифмети— ческого блока, выход которого подключен к входу, второго элемента задержки, выход которого подключен к первому информационному входу третьего арифметического блока, выход которого является выходом процессорного модуля, управляющими входами группы которого являются объединенные между собой первые и вторые управляющие входы

1508233 первого, второго и третьего арифй6тических блоков, выход 1-го (1 = 2,7) мультиплексора подключен к второму информационному входу (1-1)-го арифметического блока и входу 1-го элемента задержки группы, выход которого подключен к первому информационному входу 1-ro мультиплексора, вторые информационные входы всех мультиплексоров соединены между собой и являются информационным входом процессорного модуля, тактовым входом группы которого являются объединенные между собой управляющие входы всех мультиплексоров, причем

К-й (К = 1,3) арифметический блок содержит два мультиплексора, два сумматора-вычитателя и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к управляющим входам первого и второго мультиплексоров, выходы которых подключены к первым информационным входам соответственно первого и второго сумматоров-вычитателей, выходы которых объединены между собой и являются выходом арифметического блока, первым управляющим входом которого являются соединенные между собой управляющий вход первого сумматора-вычитателя и первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого соединен с управляющим входом второго сумматора-вычитателя и является вторым управляющим входом арифметического блока, первым информационным входом которого являются объединенные между собой вторые информационные входы первого и второго сумматоров -вычитателей, соединенные между собой первые информацчонные входы первого и второго мультиплексоров объединены соединенными между собой вторыми информационными входами первого и второго мультиплексоров и образуют второй информационный вход арифметического блока.

1 508233

1508233