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

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

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

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

Устройство содержит процессорные модули 1.1 (i 1,М) информационные входы 2.1, выходы 3.1, мультиплексоры 4.1, тактовые входы 5.1, группу

элементов 6.1 задержки, арифметические блоки 7.1. элементы 8.1, задержки, управляющие входы 9.1 и 10.1, блоки 11.1 постоянной памяти, блоки 12.1 умножения и адресные входы 13.1.

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

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

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

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

1.2. Допустим, изменения информации производятся положительным фронтом синхросигнала, вырабатываемым генератором 25 тактовых импульсов. Дискретные элементы 6.1 и 8.1 задержки содержат по четыре регистра. Дискретные элементы 6.2 и 8.2 задержки содержат по одному регистру. Счетчик 26 - двоичный, четырехразрядныр, соединенный с двумя дешифраторами 27.

В первые четыре такта на вход 2.1 устройства поступают входные отсчеты Х(10), Х(1), Х(2), Х(3). Состояния счетчика 26 последовательно изменяются от 0000 до 0011. На управляющем входе 5.1 первого мультиплексора 4.1 находится верхний логи26 последовательно изменяются от 1000 ДС1 101 1 . Верхний логический уровень присутствует на третьем входе 5.1. Входные отсчеты поступают в третий элемент 6.1 задержки. Отсчеты в первом и втором элементах 6.1 задержки циклически сдвигаются через соответствующие мультиплексоры 4.1. На первьш управляющий вход 9.1 поступает верхний логический уровень, а на первый управляющий вход 10.1 - нижний логический уровень. Это соответствует операции А для первого арифметического блока 7.1. На вторые управляющие входы 9.1 и 10.1. поступают нижние логические уровни. При этом второй

Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования в устройствах цифровой обработки сигналов. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что в состав устройства входят M(M=LOG_NN

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

ческий уровень, на остальных управляю- арифметический блок 7.1 вьтолняет щих входах - нижний логический уро- 20 операцию (А+В)+С, где (А+В) - опе.-

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

В следующие четыре такта на вход 2.1 устройства поступают отсчеты Х(4), Х(5), Х(6) иХ(7). Состояния счетчика 26 изменятся последовательно от 0100 до 0111. При этом верхний логический уровень поступает на второй вход 5.1 с дешифратора 27, на остальных входах имеется нижний логический уровень. Первьш мультиплексор 4.1 принимает информацию, с вто- рог о входа. Поэтому первые четыре отсчета циклически сдвигаются в первом элементе 6.1 задержки. Вторая

четверка отсчетов заносится во второй элемент 6.1 задержки и поступает

.на второй вход первого арифметического блока 7.1. На первый вход первого арифметического блока 7.1 поступают последовательно первые четыре отсчета. На управляющие входы 9.1 и 10.1 первого арифметического блока 7.1 поступают нижние логические уровни, что соответствует операции А + В, где А - операнд на первом входе, В - операнд на втором входе первого арифметического блока 7.1, За четыре такта в первый элемент 8.1 задержки заносится четыре суммы: X(0) + Х(4); Х(1) + X(5)i Х(2) + Х(6); Х(3) + Х(7)

За третью четверку тактов на вход 2,1 поступают отсчеты Х(8), Х(9), Х(10) иХ(11). Состояния счетчика

25

45 50 55.

ранд, поступающий на первый вход, а С - операнд, поступающий на второй вход второго арифметического

блока 7.1. В первый элемент 8.1/

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

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

В следующие четыре такта на вход 2.1 поступают значения Х(12), Х(13), Х(14) иХ(15), состояния счетчика

25 26 последовательно изменяются от 1100 до 11II.-Верхний логический уровень поступает на четвертьш вход 5.1. На другие входы 5.1 поступают нижние логические уровни. Входные Отсчеты записываются в четвертый элемент задержки 6.1 и на второй вход третьего арифметического блока 7.1 . На первые и вторые управляющие входы | 9.1 и 10.1 поступают верхние логические уровни. На третьи управляющие входы 9.1 и 10.1 поступают нижние логические уровни, первьш арифметический блок 7.1 вьтолняет операцию А-В, второй арифметический блок 7.1 выполняет операцию (A+jB)-C. Третий арифметический блок 7.1 вьтолняет операцию (A+B+C)+Dj где (А+В+С) - операнд, поступающий на первый вход третьего арифметического блока 7.1, а D - операнд, поступающий на второй вход третьего арифметического блока 7.1. В первый элемент 8.1 задержки записываются значения: Х(0)-Х(4){ Х(1)Х(5), Х(2)-Х(6)-, Х(3)-Х(7). Во

40

второй элемент 8.1 задержки записываются значения X(0)+jX (4)-Х(8); X(l)+jX(5)-X(9), X(2)H-jX(6)-X(10)$ X(3)+jX(7)-X(ll), На выходе 3.1 последовательно появляются значения X(0)+X(4)+X(8)+X(12)J Х(1)-4-Х(5)-ь +Х(9)+Х(3)Г X(2)4.X(6)-tX(10)+X(J4); Х(3)+Х(7)Х(1 1)+Х(15). На второй вход блока 12.1 умножения поступает значение W , где W exp(-j 2 ii n/N) На вход 2.2 модуля 1.2 поступают четыре первых результата первой итерации алгоритма БПФ.

В следзтощую четверку тактов модуль 1.1 работает аналогично первой четверке тактов. На вход 2.1 поступают первые четыре отсчета следующего входного массива. Состояния счечика 26 последовательно изменяются от 0000 до 0011. Загрузка информации производится в первый элемент 6.1 задержки. На первый вход 9.1 поступает нижний логический уровень, на первьй вход 10.1 - верхний логический уровень. Первый арифметический блок 7.1 выполняет операцию A-JB. В первый элемент задержки 8 поступают значения: X(0)-jX(4); Х(1) -JX(5), X(2)-jX(6); X(3)-jX(7). На вторые управляющие входы 9.1 и 10.1 поступают нижние логические уровни. Второй арифме.тический блок 7.1 выполняет операцию (А-В)+С. Во второй элемент 8.1 задержки поступают значения: Х(0)-Х(4)+Х(8), Х(1)-Х(5)+Х(9 Х(2)-Х(6)+Х(10), Х(3)-Х(7)+Х(П).На третий управляющий вход 9.1 поступает нижний логический уровень, на третий управляющий вход 10.1 - верхний логический уровень. Третий арифметический блок выполняет операцию (A+jB-C)-jD. На выходе 3.1 модуля

вход блока умножения поступает последовательность весовых коэффициентов Wfg , W ,, Wf , .. На вход

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

логические уровни. При этом второй арифметический блок 7.1 выполняет операцию (A-jB)-C, а третий арифметический блок 7.1 - (A-B+C)-D. Во второй элемент 8.1 задержки поступают значения: X(0)jX(4)-X(8); X(l)-jX(5)-X(9), X(2)-jX(6)-X(10) X(3)-jX(7)-X(n). На выходе 3.1

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

W°g, Wfg, W,, W, на вход 2.2 вто- рого модуля 1.2 - третья четверка результатов первой итерации.

В седьмой четверке тактов элементы нового массива обрабатываются аналогично третьей четверке тактов. На третий управляющий вход 9.1 поступает нижний логический уровень, третий арифметический блок 7.1 выполняет операцию (A-jB-c)+jD. На выход 3.1 поступают значения: Х(0)- -JX(4)-X(8)+JX(12); X (I)-JX (5)-Х (9) + +JX(13), X(2)-jX(6)-X(10)+jX(14), X(3)-jX(7)-X(l )bjX(15), Ha второй

0 вход блока

5

0

5

0

чения W

5

.б

умножения

ТТ IT 6

16 б

поступают знаа

1 /g . На вход 2.2 второго модуля 1.2 поступают последние четыре результата.первой итерации.

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

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

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

Тринадцатый такт. Состояние счет- чика 26-1101. На входе 2,2 имеется значение Y(l) Х(1 )+Х (5)+Х(9)+Х (13). Верхний логический уровень находится на втором входе 5.2. Значение Y(l)

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

Четырнадцатый такт. На вход 2.2 поступает значение Y(2) Х(2)+Х(6) + +Х(10)+Х(14). Состояние счетчика 26-П10. Верхний логическрш уровень поступает на третий вход 5.2. На пер вый управляющий- вход 9.2 поступает верхний логи 1еский уровень. На первый управляющий вход 10.2 и вторые управляющие входы 9.2 и 10.2 поступают нижние логические уровни. Первый арифметический блок 7.2 выполняет операцию. A+jB. На его выходе присутствует значение Y(0)+jY(l). Второй арифметический блок 7.2 выполняет операцию (А+В)+С. На его выходе имеется значение Y(0)+Y(I)+У(2)

Пятнадцатый такт. На входе 2.2 находится значение Y(3) Х(3)+Х(7)+ +Х (11)+Х (15). Состояние счетчика 26- 1111. Верхний логический уровень поступает на четвертый вход 5.2.На первые и вторые уравляющие входы 9.2 и 10.2 поступают верхние логические уровни, на третьи- нижние логические уровни. Первый арифметический блок 7.2 выполняет операцию А-В. На его выходе имеется значение Y(0) -Y(l), второй арифметический блок 7.2 выполняет о.перацию (A+jB)-C. На его выходе находится значение Y(0)+jY(l) -Y(2). Третий арифметический блок 7,2 вьшолняет операцию (A+B+C)+D. На его выходе присутствует значение Y(0)+Y(l)+Y(2)+Y(3).Ha выходе блока зпяножения 12.2 имеется значение F(0),

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

t -

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

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

10

15

20

25

30

35

40

45

50

55

Устройство для вычисления быстрого преобразования Фурье, содержащее М (М N - размер преобразования) процессорных модулей, М :блоков постоянной памяти и блок управления, причем инормационный вход первого процессорного модуля является информационным входом устройства, актовые выходы i-й группы (i 1 ,М) блока управления подключены к тактовьт входам группы i-ro процессорного модуля, -й адресный выход блока управления подключен к адресному входу i-ro блока постоянной памяти, о тлич а ющ е е с я тем, .что, с целью упрощения устройства, оно содержит М блоков умножения, причем выход i-ro процессорного модуля подключен к первому входу i-го блока умножения, второй вход которого подключен к выходу i-ro б-лока постоянной памяти, выходы группы которого подключены к управляющим входам группы i-ro процессорного модуля, выход j-ro (j ; М-1) блока умножения подключен к информационному входу (j+l)-ro Процессорного модуля, а выход М-го вычислительного модуля являетс.я информационным выходом устройства, при этом i-й процессорный модуль содержит три арифметических блока, четыре мультиплексора, два элемента задержки и группу из четырех элементов задержки, выход первого мультиплексора подключен к входу первого элемента задержки группы, вьрсод которого подключен к первому информационному входу первого мультиплексора и первому информационному входу первого арифметического блока, выход которого подключен к вхсз- ду первого элемента задержки, выход которого подключен к первому информационному входу второго арифметического блока, выход которого подключен к входу .второго элемента задержки, выход которого подключен к первому информационному входу третьего арифметического блока, выход которого является выходом процессорного модуля, управляющими входами группы которого являются объединенные между собой первые и вторые управляющие входы

хИ

ш

з-ггтт

111

;.

Т

Т«

ЪПЩ

I ГА/Щ,

Г

тм А ;ш

г/

L-7.-

s.

дыход

0г/г. 2

ciJ

.78

26

5.f 5.1 S.1