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

 

Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования Фурье по основанию 4 в устройствах цифровой обработки сигналов. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят процессорные модули l.n.m первого типа, входной блок 2, блоки 3.1-З.М постоянной памяти, блок 4 управления, генератор 5 тактовых импульсов и соответствующие связи между узлами устройства. 7 ил.

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (я)5 6 06 F 15/332

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4655490/24 (22) 17.01.89 (46) 07.12.91. Бюл, N. 45 (72) Д.В»Корчев, Ю.С.Каневский, B.B.ÃHèлицкий, С.В.Клименко, О.М.Поваренко и

Т.П.Ярцун (53) 681.32(088.8) (56) Рабинер Л., Гоулд Б. Теория и и рименение цифровой обработки сигналов. M.:

"Мир", 1978, с.674.

Авторское свидетельство СССР

¹ 1508233, кл. G 06 F t5/332, 1988. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования

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

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

В числовых позициях на фиг.1, 3 приняты следующие обозначения: первое число обозначает фун кционал ьную и ринадлежность, второе — номер группы, третье — но„„5U„„1697085 А (57) Изобретение относится к вычислительной технике и предназначено для выполнения алгоритма быстрого преобразования

Фурье по основанию 4 в устройствах цифровой обработки сигналов. Цель изобретения — повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят процессорные модули 1.n.m первого типа, входной блок 2, блоки 3.1 — 3.M постоянной памяти, блок 4 управления, генератор 5 тактовых импульсов и соответствующие связи между узлами устройства. 7 ил. мер процессорного модуля в данной группе, че1 вертое — номер функционального элемента в данном процессорном модуле.

Устройство (фиг.1) содержит процессорные модули 1.п.m первого типа, входной блок 2, блоки 3.1 — З,М постоянной памяти, блок 4 управления, генератор 5 тактовых импульсов, адресные входы б.i блоков ЗЛ.

Кроме того, устройство содержит (фиг,2) . процессорные модули второго типа 7.n.m u элементы 8.п задержки (и = 2,4).

Процессорный модуль первого типа (фиг.3) содержит арифметические блоки

9.п.гп, элементы 10.n.m задержки, узел

11.п,m постоянной памяти, элементы

12.п.m.р (р = 1,4) задержки, коммутаторы

13,плп.р, умножитель 14.n,m.

Процессорный модуль второго типа (фиг,4) содеожит регистры 15.п.m, арифметический блок 16.п.m и регистр 17.n.m. I697085

Арифметический блок (фиг.5) содержит коммутаторы 18,п.m,р, 19.пю.р, арифметические узлы 20.п m,р, 21,п.m,.р, элемент ИСКЛ 10ЧАЮ ЩЕ Е ИЛ И 22.n.m.p, Блок ввода (фиг.6) содержит аналогоцифровой преобразователь 23, элемент

ИЛИ-НЕ 24, 0-триггеры 25,п (n = 1,4), регистры 26,п.

Блок управления содержит (фиг.7) счетчик 27, дешифраторы 28.m (rn == 1, till), Регистры 26.п и три геры 25.п срабатывают по положительному фронту синхроимпульса, все остальные регистры — no отрицательному фронту,.

Рассмотрим работу устройства N =- 64, М = 3. В этом случае каждая линейка состоит из двух процессорных модулей первого типа, Элементы 12 и, 1.р, 10,п, 1.р задержки содержат четыре регистра, элементы 12.п, 2.р, 10,п, 2р задержки содержат по одному регистру. Счетчик 27 — двоичный шестиразрядный, соединен с двумя дешифраторами

28.1 и 28.2, В первую четверть первого такта в регистр 26.1 записывается отсчет X/0, во вторую четверть в регистр 26,2 записывается отсчет Х/1, в третью четверть такта в регистр 26.3 записывается отсчет Х/2, в последнюю четверть первого такта в регистр

26.4, записывается отсчет Х/3, В дальнейшем блок ввода работает аналогичным образом, и с целью упрощения его работа не

OllMcbl BBBTCA.

Рассмотрйм работу первого процессорного модуля 1.1.1 первой группы.

В следующие четыре такта(2 — 5) на входную шину этого процессорного модуля поступают первые входные отсчеты Х/О, Х/4, X/8, Х/.12. На управляющем входе коммутатора 13.1.1,1 — верхний логический уровень, На управляющих входах остальных коммутаторов процессорного модуля — нижний логический уровень, При верхнем логическом уровне коммутатор 13.1.1.1 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12.1.1.1 задержки.

В следующие четыре такта (6 — 9) на входную шину этого процессорного модуля поступают входные отсчеты Х/16, Х/20, Х/24, Х/28, На управляющем входе коммутатора

13.1.1.2 — верхний логический уровень. На управляющих входах остальных коммутаторов процессорного моцуля — нижний логический уровень. При верхнем логическом уровне коммутатор 13.1,1.2 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12.1.2 задержки и поступают на второй вход арифметического

55 блока 9.1.1.1, Коммутатор 13,1.1.1 принимает информацию с второго входа. Поэтому первые отсчеты циклически сдвигаются в элементе 12.1.1.1 задержки и поступают на первый вход арифметического блока 9,1,1.1.

На управляющие входы арифметического блока 9.1.1.1 поступают нижние логические уровни, что соответствует операции А + В, где А и  — операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.1 задержки заносятся четыре соответствующие суммы Х/О + X/16, Х/14+ Х/20, Х/8 + Х/24, Х/12 + Х/28.

В следующие четыре такта (10-13) на входную шину этого процессорного модуля поступают входные отсчеты X/32, Х/36, Х/40, X/44. На управляющем входе коммутатора 13.1.1.3 — верхний логический уровень. На управляющих входах остальных . коммутаторов процессорного модуля — нижний логический уровень. При верхнем логическом уровне коммутатор 13.1.1.3 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент 12.1.1.3 задержки и поступают на второй вход арифметического блока 9.1.1.2. Коммутаторы

13.1.1.1 и 13.1.1.2 принимают информацию с второго входа. Поэтому первые и вторые четыре отсчета циклически сдвигаются в элементах 12,1,1.1 и "12.1.1.2 задержки и поступают на первый и второй входы арифметического блока 9.1.1.1 соответственно. На управляющие входы арифметического блока 9.1.1,1 поступают верхний и нижний логические уровни соответственно, что соответствует операции А + В, где А и В— операнды на первом и втором входах соответственно. За эти четыре такта в элемент

10.1.1.1 задержки заносятся четыре соответствующие суммы Х/О + jX/16, Х/4+ jX/20, Х/8+ )Х/24, X/12 + jX/28. На управляющие входы арифметического блока 9.1.1.2 поступают нижние логические уровни, что соответствует операции (А + В) + С, где А + В и С вЂ” операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.2 задержки заносятся четыре соответствующие суммы Х/О+ Х/16+ Х/32, X/4+ X/20+ Х/36. Х/8

+ X/24+ Х/40, X/12 + Х/28 + Х/44.

В следующие четыре такта (14 — 17) на входную шину этого процессорного модуля поступают входные отсчеты Х/48, Х/52, X/56, Х/60, На управляющем входе коммутатора 13,1,1.4 — верхний логический уровень. На управляющих входах остальных коммутаторов процессорного модуля — нижний логический уровень, При верхнем логическом уровне коммутатор 13.1.1.4

1697085 принимает Информацию со своего первого, входа поэтому эти четыре отсчета последовательно записываются в элемент 12.1.1.4 задержки поступают на второй вход арифметического блока 9.1.1.3. Коммутаторы

13.1.1,1, 13.1,1.2 и 13.1,1.3 принимают информацию с второго входа. Поэтому первые, вторые, третьи четыре отсчета циклически сдвигаются в элементах 12.1.1.1, 12.1.1.2, 12.1.1.3 задержки. На управляющие входы арифметического блока 9.1.1.2 поступают верхние логические уровни, что соответствует операции (А + JB) - C, где А +

jB и С вЂ” операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.2 задержки заносятся четыре соответствующие суммы Х/О + JX/16X/32, Х/4 + jx/20 - Х/36, Х/8 + JX/24X/40, X/12+ JX/28- X/60. На управляющие входы арифметического блока 9.1.1.3 поступают нижние логические уровни; что соответствует операции (А+ В + С+ D), где А+ В

+ С и D — операнды на первом и втором входах соответственно, 3а эти четыре такта на первый вход умножителя 14,1.1 последовательно поступают суммы

Х/О + Х/16+ Х/32 + X/48, Х/4 + Х/20 + Х/36 + Х/52, Х/8+ Х/24+ Х/40+ Х/56, Х/12 + Х/28 + Х/44 + Х/60, На второй вход умножителя 14.1.1 поступает значение W640, где W и =

- ехр{-j 2кп /N}.

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

9.1.1.1 поступают верхние логические уровни, что соответствует операции А - В, где А и  — операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.1 задержки заносятся четыре соответствующие разности Х/О - Х/16, Х/4- Х/20, Х/8- Х/24, Х/12- Х/28.

В следующие четыре такта (18. 19, 20, 21) на входную шину этого процессорного модуля поступают первые четыре отсчета следующего входного массива. На управляющем входе коммутатора 13.1.1.1 — верхний логический уровень. На управляющих входах остальных коммутаторов процессорного модуля — нижний логический уровень.

При верхнем логическом уровне коммутатор .13.1.1.1 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент

12.1.1.1 задержки. Коммутаторы 13,1.1.2, 13.1.1.3 и 13.1.1.4 принимают информацию с второго входа. Поэтому вторые; третьи, 5 четвертые четыре отсчета циклически сдвигаются в элементах 12.1,1,2, 12.1.1,3, 12.1.1,4 задержки поступают на вторые входы арифметических блоков 9.1,1.1, 9.1.1.2, 9.1,1.3 соответственно, На управляющие

10 входы арифметического блока 9.1.1.2 поступают нижние логические уровни, что соответствует операции (А - В) + С, где А - В и С вЂ” операнды на первдм и втором входах соответственно. 3а эти четыре такта в элемент

15 10.1.1.2 задержки заносятся четыре соответствующие суммы Х/О- Х/16+ Х/32, Х/4 — /Х/20 + Х/36, Х/8 - Х/24 + Х/40

X/12 - jX/28 - X/60

На управляющие входы арифметического блока 9.1.1.3 поступают нижний и верхний логические уровни соответственно, что соответствует операции (A + JB - С) - )О, где

A+jB -С и)0 — операнды на первом и втором входах соответственно. За эти четыре такта на первый вход умножителя 14,1,1 последовательно поступают суммы;

Х/О+ jX/16- Х/32 - JX/48

Х/4 + jX/20 - X/36 0 JX/52, Х/8 + )Х/24 - Х/40 - ) Х/56, X/12 + jX/28 - X/44 — jX/60.

40 о

На второй вход умножителя 14,1.1 поступают значения О/чО, W44, Р/в48, Мч12.

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

9.1,1,1 поступают нижний и верхний логические уровни соответственно, что соответствует операции А - jB, где А и  — операнды на первом и втором входах соответственно.

3а эти четыре такта в элемент 10,1,1.1 задержки заносятся четыре соответствующих разности Х/О - jX/18, Х/4 - jX/20. Х/8JX/24, Х/12 — JX/28.

В следующие четыре такта (22 — 25) на входную шину этого процессорного модуля поступают вторые четыре отсчета следующего входного массива. На управляющем входе коммутатора 13.1.1.2 — верхний логический уровень. На управляющих входах ос1697085 тальных коммутаторов процессорного Мо дуля — нижний логический уровень. При верхнем логическом уровне коммутатор

13.1.1.2 принимает информацию с своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент

12.1,1.1 задержки. Коммутаторы 13.1.1.1., 13.1.1,3 и 13,1.1.4 принимают информацию с второго входа. Поэтому первые, третьи, четвертые отсчеты циклически сдвигаются в, элементах 12,1,1.1, 12.1.1.3, 12.1.1.4 задер, жки, На управляющие входы арифметиче, ского блока 9.1,1.2 поступают верхние, логические уровни, что соответствует onej раци (А- JB) - С, где А- jB и С вЂ” операнды на .первом и втором входах соответственно. За

: эти четыре такта в элемент 10.1.1.2 задержки заносятся четыре соответствующие суммы

Х/О - jX/16- X/32

X/4 - )Х/20 - Х/26

Х/8 -JX/24 - Х/40, X/12 -jX/28 - X/60. ь

На управляющие входы арифметического блока 9.1.1,3 поступают верхние логические уровни, что соответствует операции (А - В + С) - D, где А - В + С и 0 - операнды на первом и втором входах соответственно.

За эти четыре такта на первый входумножителя 14.1,1 последовательно поступают сумM х/О х/16 х/32-Х/48,X/4 Х/24+Х/36- Х/52, Х/8- Х/24+ Х/40 - Х/56 Х/12 - X/28+

+ Х/44 - Х/60, На второй вход умножителя 14.1.1 псступают значения М/в40, We<8, Рlу16, Wgq24.

На вход второго процессорного модуля группы поступают четыре третьих результата первой итерации алгоритма БПФ, В следу",ощие четыре такта (26 — 29) на входную шину этого процессорного модуля поступают третьи четыре отсчета следующего входного массива, На управляющем входе коммутатора 13.1.1.3 верхний логический уровень. На управляющих входах остальных коммутаторов процессорногО модуля — нижний логический уровень. При верхнем логическом уровне коммутатор

13.1.1.3 принимает информацию со своего первого входа, поэтому эти четыре отсчета последовательно записываются в элемент

12.1,1.3 задержки. Коммутаторы 13.1.1.1, 13.1.1.2 и 13.1.1.4 принимают информаци1о с второго входа. Поэтому первые, вторые, четвертые четыре отсчета циклически сдвигаются в элементах 12,1.1.1, 12.1.1,2, 12,1,2,4 задержки, На управляющие входы арифметического блока 9.1,1,3 поступают верхний и нижний логические уровни, что соответствует операции (А - jB - С) + jD. где

А-jB — С и JO — операнды на первом и втором входах соответственно. За эти четыре такта

5 на первый вход умножителя 14.1.1 последовательно поступают суммы Х/О - jX/16X/32+)Х/48, Х/4-JX/20+ X/52, Х/8- JX/24- X/40+ )Х/56, Х/12 - jX/28 - Х/44 + JX/60.

На второй вход умножителя 14.1.1 поступа10 ют значения Э/б40, 6/е412, Wr<24, Хб446.

На вход второго процессорного модуля группы поступают четыре последних результата первой итерации алгоритма БПФ.

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

Рассмотрим работу второго процессорного модуля 1,1,2 первой линейки, начиная с четырнадцатого такта, Четырнадцатый такт. На входе процессорного модуля значение Y/p = (Х/0+ Х/16+

+ X/32+ X/48) М/640, которое через коммутатор 13.1.2.1 поступает на вход элемента задержки 12,1,2,1.

Пятнадцатый такт, На входе процессорного модуля значение Y/64 О = (Х/4 + X/20+

+ Х/36+ X/52) 6/рО, которое через коммутатор 13.1.2.2 поступает на вход элемента

12.1.2.2 задержки, Значение Y/О через коммутатор 13.1.2.1 поступает снова на вход элемента 12.1.2.1 задержки. На управляющие входы поступают нижние логические уровни. Арифметический блок 9.1.2.1 выполняет операцию А + B. На его выходе — зна35 чение Y/О+ Y/4.

Шестнадцатый такт. На входе процессорного модуля значение 3 - 8 = Х/8+ X/24+

+ Х/40+ Х/56, В/б40, которое через коммутатор 13.1,2.3 поступает на вход элемента

12.1.2.3 задержки. На управляющие входы поступают верхний и нижний логические уровни соответственно. Арифметический блок 9.1.2.1 выполняет операцию А+ jB. На его выходе — значение Y/О+ jY/4. Арифме45 тический блок 9.1.2.2 выполняет операцию (А+ В)+ С. На его выходе — значение Y/О+

+Y/4+ Y/8.

Семнадцатый такт. На входе процессорного модуля Y/12 - Х/12 + Х/28 + Х/44 +

5p + X/60) Р/640, которое через коммутатор

13.1.2.4 поступает на вход элемента 12. t.2,4 задержки. На одни управляющие входы поступают верхние логические уровни. на другие — нижние логические уровни. Арифметический блок 9.1.2,1 выполняет операцию А - В. На его выходе — значение Y/О—

-Y/4. Арифметический блок 9,1,2,2 выполняет операцию (А + JB/ - С). На его выходе— значение Y/Î + jY/4 - Y/8. Арифметический блок9,1.23выполняетоперацию(А+ jB+ С)+

1697085

+ D. На его выходе — значение Y/О + Y/4 +

+Y/8 + Y/12, которое поступает на первый вход умножителя 14.1.2, на второй вход которого поступает значение We<0. На выходе умножителя 14.1,2 — первый результат вто- 5 рой итерации алгоритма БПФ.

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

14.1.2 снимаются результаты второй итера- 15 ции алгоритма БПФ.

Вторая, третья и четвертая группы устройства работают аналогично первой группе, последовательность смены управляющих сигналов на этих группах такая же, 20 как и на первой группе, Отличие для второй группы заключается в том, что на вход второй группы поступают отсчеты Х/1, Х/5, Х/9, Х/13, Х/18, Х/21, Х/25, Х/29, Х/33, Х/37, X/41, Х/45, Х/49, Х/53, Х/57, Х/61, с выхода блока 11.2.1 постоянной памяти последовательно поступают коэффициенты

We40, ЧЧ640, ЧЧ640, ЧЧ640, ЧЧ641, 1И645, \И649, ЧЧ6413, М/642, 6/6410; ЧЧ6418, М/6426, В/643, ЧЧ6415, W6427, ЧЧ6439, с выхода блока 11.2.2 30 постоянной памяти — коэффициенты W640, W644, Ю648, О/6412. Отличие для третьей группы заключается в том, что нэ вход этой группы поступают отсчеты Х/2, Х/6, Х/10, Х/14, Х/18, Х/22, Х26, Х/30, X/34, X/38, Х/42, Х/46, Х/50, Х/54, Х/58, Х/62, с выхода блока 11.3.1 постоянной памяти последовательно поступают коэффициенты We<0, W640, ЧЧ640, ЧЧ640, %642, М/646, Wg410, ЧЧ6414, ЧЧ644, М/6 12, ЧЧ6420, We<28, W646, W6418, 40

И/ы39, М/6442, с выхода блока 11.3.2 постоянной памяти — коэффициенты W640, М/648, Р/6416, 1И6424. Отличие для четвертой группы заключается в том, что на вход этой группы поступают отсчеты Х/3, Х/7, X/11, X/15, 45

Х/19, Х/23, Х/27, Х/31, Х/35, Х/39, Х/43, Х/47, Х/51, Х/55, Х/59, Х/63, с выхода блока 11.4.1 постоянной памяти последовательно поступают коэфициенты Wg40, ЧЧТО, ЧЧ640, W640, М/643, ЧЧб47, \/Ч641 " ЧЧ6415, W646 50

М/ы14, М/6422, М/6430, ЧЧ649, 1И6421 ЧЧ6433

И/е445, с выхода блока 11.4.2 постоянной памяти — коэффициенты ЧЧТО, О/6412, М/В424, М/6436, Рассмотрим работу вычислительной матрицы, начиная с семнадцатого такта..

Семнадцатый такт, На вход процессорного модуля 7;1,1 поступает результат второй итерации алгоритма БПФ 2(0) = (y(0)+

+ у(4) + у(8) + у(12)) We<0, который является операндом В для арифметического блока

16.1.1. Операндом А для этого арифметического блока является "О", На управляющих входах этого арифметического блока постоянно нижний логический уровень, что соответствует операции А + В. На выходе арифметического блока 16.1.1— значение 2(0).

Восемнадцатый такт. На вход процессорного модуля 1.1,1 поступает результат второй итерации алгоритма БПФ. 2(4) =

= (Y/О + JY/4 - Y/8 - JY/12) Wg40, который .является операндом В для арифметического блока 16.1,1. Операндом А для этого арифметического блока является "О". На выходе арифметического блока 16.1.1 — значение

Z(4). Ка вход процессорного модуля 7.1,2 поступает результат второй итерации алгоритма БПФ 2(0) = (Y/0 + Y/4 + Y/8 +

+ Y/12) Wg40, который является операндом

В для арифметического блока 16.1.2, Операндом А для этого арифметического блока является 2(0), На управляющих входах этого арифметического блока постоянно нижние логические уровни, что соответствует операции А+ В. На выходе арифметического блока 16.2.1 — значение Z(0) + 2(1).

Девятнадцатый такт, На вход процессорного модуля 7.1.1 поступает результат второй итерации алгоритма БПФ 2(8) = (Y(0) — Y(4) + Y(8) - Y(12) Н/640, который является операндом B для арифметического блока

16.1.1, Операндом А для этого арифметического блока является "О". На выходе. арифметического блока 16.1.1.— значение Z(8). На вход процессорного модуля 7,1.2 поступает результат второй итерации алгоритма БПФ

2(4) = (Y(0) = JY(8) = jY(11)) Wg40, который является операндом B для арифметического блвка 16.1.2. Операндом А для этого арифметического блока является "О", На выходе арифметического блока 16.1.2 — значение

2(4). На вход процессорного модуля 7.2.1 поступает результат второй итерации алгоритма БПФ 2(5) =(Y(1)+jY(5)- Y(9)+ jY/13) Wg<4, который является операндом В для арифметического блока 16,2,1, Операндом А для этого арифметического блока является значение Z(4). На управляющих входах этого арифметического блока постоянно верхний и нижние логические уровни, что соответствует операции А + В. На выходе арифметического блока 16.2.1 — значение Z(4) + 2(5).

На вход процессорного модуля 7.2.2 поступает результат второй итерации алгоритма

БПФ 2(1) = (Y/1 + Y/5 + Y/9 + Y/13)ЧЧТО, который, является операндам В для арифметического блока 16.2.2. Операндом А для этого арифметического блока является значение Z(0). На управляющих входах этого

1697085 арифметического блока постоянно верхний и нижний логические уровни соответственно, что соответствует операции А + jB, На выходе арифметического блока 16.2.2 — значение Z(0) + Z(1). На вход процессорного модуля 7.1,2 поступает результат второй итерации алгоритма БПФ Z(4) = (У/О +

+ jY/4 — Y/8- jY/12)Ив40, который является операндом В для арифметического блока

16.1.2. Операндом А для этого арифметиче,ского блока является "0". На вход процессорного модуля 7.1,3 поступает результат второй итерации алгоритма БПФ Z(0) ==

=- (Y/О + Y/4 + Y/8 + Y/12)W640, который является операндом В для арифметического блока 16,1.3. Операндом А для этого арифметического блока является "О". На управля-! ющих входах этого арифметического блока постоянно нижние логические уровни, что соответствует операции А + В. На выходе арифметическогдо блока 16,1.3 значение

2 .(О). На вход процессорного модуля 7.3.1 поступает результат второй итерации алгоритма БПФ Z(2) = (Y/2 + Y/6+ Y/10 -

+ Y/14)W640, который является операндом

В для арифметическогр блока 16.3.1. Операндом А для этого арифметического блока является Z(0) + Z(1). На управляющих входах этого арифметического блока постоянно нижние логические уровни, что, соответствует операции А+ В. На выходе, арифметического блока 16.3.1 значение

Z(G) + 7(1) + 2(2) + Z(3).

Двадцатый такт. На вход процессорного модуля 7.4.1 поступает значение 7(4) = (Y/4+ Y/8+ Y/12+ Y/16) Wg40.Ha выходе арифметического блока 16.4.1— значение 2(0) + 2(1) + Z(2) + Z(3).

С целью упрощения дальнейшая работа вычислительной матрицы не описывается.

Отметим, что на втором столбце матрицы вычисляется значение 2(!) + )7(!) - 1) - Z(l + 2)- jZ(i +3), на третьем столбце значение

Z(i) = Z(i+1) + Z(i+2) - Z(i+3), на четвертом столбце значение Z(i) - iZ(l+1) - Z(1+2) + j Z(i+3).

В соответствии с данными операциями на управляющих входах арифметических блоков процессорных модулей матрицы постоянно выставлены следующие логические уровни:

Π— О, Π— О, Π— О, О-О

0-0, 1-0, 1 — 1, 0--1, О-О, 1-1, 20

30 в

Π— О, 1-1, Π— 0, 0-1, 1 — 1, 1 — О, Начиная с двадцать первого такта на выходе процессорного модуля 7.4.1 последовательно получаются следующие коэффициенты БПФ: F(0), F(4), F(12)., F(1), F(5), F(9), F(13), F(2), F(6), F(10), F(14), F(3), F(7), F(11), F(15).

Начиная с двадцать второго такта на выходе процессорного модуля 7.4.2 последовательно получаются следующие коэффициенты БПФ: F(16), F(20), F(24), F(28), F(17), F(21), F(25). F(29), F(19), F(22), F(26), F(30), F(19), F(23), F(27), F(31), Начиная с двадцать третьего такта на выходе процессорного модуля 7.4.3 последовательно получаются следующие коэффиценты БПФ: F(32), F(36), F(40), F(44), F(33), F(27), F(41), F(45), F(34), F(38), F(42), F(46), F(35), F(39), F(43). F(47).

Начиная с двадцать четвертого такта на выходе процессорного модуля 7.4.4 последовательно получаются следующие коэффициенты БПФ: F(48), F(52), F(56), F(60), F(49), F(53), F(57), F(61), F(50), F(54), F(58), F(62), F(51), F(55), F(59), F(63).

Рассмотрим работу устройства в том случае, когда каждая группа процессорных второго типа содержит по одному элементу.

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

Первая четверть семнадцатого такта.

На вход процессорного модуля 7.1,1 поступает результат второй итерации алгоритма

БПФ Z(0) = (у(0) + у(4) + у(8) + y(12)) Wg40, который является операндом В для арифметического блока 16,1.1. Операндом А для этого арифметического блока является "О".

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

На выходе арифметического блока 16.1,1— значение Z(0).

Вторая четверть семнадцатого такта. На вход процессорного модуля 7.1,1 поступает результат второй итерации алгоритма БПФ

Z(0), который является операндом В для арифметического блока 16.1,1, Операндом А для этого арифметического блока является

"0". На выходе арифметического блока

16.1.1 — значение Z(0). На вход процессорного модуля 7,2.1 поступает результат второй итерации алгоритма БПФ 2(1) = (у(1) + у(5) +

1697085

+ у(9) + у(13))У/вд0, который является операндом В для арифметического блока 16.2.1.

Операндом А для этого арифметического блока является значение 2(0). На уравляющие входы этого арифметического блока поступают нижниЕ логические уровни, что соответствует операции А + В. На выходе арифметического блока 16.2.1 — значение

2(0) + Z(1).

Третья четверть семнадцатого такта. На вход процессорного модуля 7.1.1 поступает результат второй итерации алгоритма БПФ

Z(0), который является операндом В для арифметического блока 6.1;1. Операндом А для этого арифметического блока является

"0". На выходе арифметического блока

16.1.1 — значение Z(0). На вход процессорного модуля 7,2.1 поступает результат второй итерации алгоритма БПФ Z(1), который является операндом В для арифметического блока 16,2,1. Операндом А для этого арифметического блока является значение 7(0).

На управляющих входах этого арифметического блока — верхний и нижний логические уровни соответственно, что соответствует операции А+ JB. На выходе арифметического блока 16.2.1 — значение Z(0) + JZ(1). На вход процессорного модуля 7.3,1 поступает результат второй итерации алгоритма БПФ

Z(2) = (Y(2) + т /6+ Y/10+ Y/14)%640, который является операндом В для арифметического блока 16.3.1. Операндом А для этого арифметического блока является

Z(0) + Z(1). На управляющих входах этого арифметического блока нижние логические уровни, что соответствует операции А + В.

На выходе арифметического блока 16.3.1— значение Z(0) + 2(1) + Z(2).

Последняя четверть семнадцатого такта. На вход процессорного модуля 7.4.1 поступает значение Z(3) = (у(3) + у(11) =

= у(15))Ив40. На выходе арифметического блока 16.4.1 — значение Z(0)+ Z(1)+ Z(2)+ Z(3).

С целью упрощения дальнейшая работа вычислительной матрицы не описывается.

Отметим, что на выходе линейки появляются значения Z(i) + Z(i+1)+ Z(i+2) +Z(i+3), Z(i)+

+jZ(i+1) - Z(i+2) - JZ(i+3), Z(i) - Z(i+1) + Z(i+2)-Z(i+3), Z(i) - JZ(i+1) - Z(i+2) + JZ(i+3), В соответствии с данными операциями на входах арифметических блоков 16.п.1 (n = 1,4) появляются следующие логические уровни:

Начиная с последней четверти семнадцатого такта на выходе процессорного модуля 7.4.1 последовательно получаются следующие коэффициенты БПФ: F(0), F(16), F(32), F(48), F(4), F(20), F(36), F(52), F(8), F(24), F(40), F(56), F(12), F(28), F(44), F(6), F(1), F(17), F(33), F(49), F(5), F(21), F(27), F(53), F(9), F(25), F(41), F(57), F(13), F(29), F(45), F(61), F(2). F(18), F(34), F(50), F(6), F(22), F(38), F(54), F(10), F(26), (F42) F(58) Е(14), F(30) F(46) F(62) F(3). F(19)

F(35). F(56), F(7), F(23), F(39), F(55), F(11), F(27), F(43), F(59), F(15), F(31), F(47), F(63).

В этом случае синхронизация элементов 8.2-8,4 и 7.п.1 осуществляется непосредственно с выхода генератора 5 тактовых импульсов.

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

Устройство для вычисления быстрого преобразования Фурье, содержащее первую группу из M-1) (М = 1о94Й, N — размер преобразования) процессорных модулей

15 первого типа, М-1 блоков постоянной памяти, блок управления и генератор тактовых импульсов, выход которого подключен к тактовому входу блока управления, 1-ый (! = 1, M-1) управляющий выход которого подключен к первому управляющему входу l-ro процессорного модуля первого типа первой группы, второй управляющий вход которого подключен к выходу i-ro блока постоянной памяти, адресный вход которого подключен к -му адресному выходу блока управления, выход j-го (j = 1, М-2) процессорного модуля первого типа первой группы подключен к информационному входу i+1-го процессорного модуля первого типа первой группы, 30 причем процессорный модуль первого типа содержит шесть элементов задержки. три арифметических блока, умножитель и четыре коммутатора, выход первого-коммутатора подключен к входу первого элемента задержки, выход которого подключен к первому информационному входу первого арифметического блока, выход которого подключен к входу второго элемента задержки, выход которого подключен к первому

40 информационному входу второго арифметического блока, выход которого подключен к входу третьего элемента задержки, выход которого подключен к первому информационному входу третьего арифметического

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

1697085

3/4

1/4 2/4

ОО

00 управляющие входы всех арифметических блоков, отличающееся тем,что,с целью повышения быстродействия, в него введены вторая, третья и четвертая группы из M-1 процессорных модулей первого типа в каждой группе, блок ввода, три блока задержки и четыре группы из 1=х (1 — целое число) процессорных модулей второго типа в каждой группе, при этом первый и второй управляющие входы 1-го процессорного мо:дуля первого типа К-ой группы подключены соответственно к l-му управляющему выхо ду блока управления и выходу i-ro блока постоянной памяти, выход j-ro процессорного модуля первого типа K-ой группы подключен к информационному входу j+ 1 го процессорного модуля первого типа К-ой группы, первый информационный вход Кго процессорного модуля второго типа I-ой

; (i = 1,L) группы подключен к первому выходу, (К-1)-процессорного модуля второго типа 11-ой группы, второй информационный вход

К-го процессорного модуля второго типа Кой группы подключен к второму выходу I-гс процессорного модуля второго типа К-1-ой группы, выход M-1-ro процессорного модуля первого типа первой группы подключен к первому информационному входу первого процессорного модуля второго типа первой групы, выход M-1-го процессорного модуля первого типа К-ой (К = 2,4) группы подключен к входу К-1-ro блока задержки, выход которого подключен к первому информационному входу первого процессорного модуля второго типа К-ой группы, второй выход

I-го процессорного модуля второго типа четвертой группы является ii-ым информационным выходом устройства, информационным входом которого является информационный вход блока ввода, 1-ый выход. которого подключен к информационному входу первого процессорного модуля первого типа

К-ой группы, выход генератора тактовых импульсов подключен к тактовому входу входного блока, при этом в каждый процессорный модуль первого типа введен блок постоянной памяти, выход которого под5 ключен к второму входу умножителя, адресный вход блока постоянной памяти i-го процессорного модуля первого .типа I-ой группы подключен к 1-му адресному выходу блока управления, при этом процессорный

10 модуль второго типа содержит два регистра и арифметический блок, первый информационный вход которого соединен с информационным входом первого регистра и является первым информационным входом

15 процессорного модуля второго типа, вторым информационным входом, первым и вторым выходами которого являются соответственно второй информационный вход арифметического блока, выход первого ре20 гистра и выход второго регистра, информационный вход которого подключен к выходу арифметического блока, тактовые входы первого и второго регистров всех процессорных модулей второго типа подключены к

25 тактовому выходу блока управления, причем входной блок содержит четыре регистра, элемент ИЛИ-НЕ, четыре D-триггера и аналого-цифровой преобразователь, выход которого подключен к информационному входу I-го регистра, выход которого является 1-ым выходом входного блока, тактовым входом которого являются соединенные между собой тактовые входы всех D-триггеров и аналого-цифрового преобразователя, информационный вход которого является информационным входом входного блока, выход 1-го D-триггера подключен к тактовому входу I-го регистра, выход S-ro (S. 1,3)

D-триггера подключен к S-му входу элемента ИЛИ-НЕ, выход которого подключен к информационному входу первого 0-tphrãåpa, выход К-1-го D-триггера подключен к информационному входу К-ro D-триггера, 1697085

1697085.

1697085

Составитель A.Áàðàíoâà

Редактор Т.Федотов Техред M.Ìîðãåíòàë Корректор Т.Малец

Заказ 430 7 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101