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

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

Цель изобретения - повышение быстродействия.

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

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

Устройство (фиг.1) содержит процессорные модули l.n.m первого типа, входной блок 2, блоки 3.1-З.М постоянной памяти, блок 4 управления, генератор 5 тактовых импульсов, адресные входы 6.i блоков 3.i. Кроме того, устройство содержит (фиг.2) процессорные модули второгр типа 7.n.m и элементы 8.п задержки (п 2,4.

Процессорный модуль первого типа (фиг.З) содержит арифметические блоки 9.п.т, элементы 10.п.m задержки, узел 11.n.m посто я нной памяти, элементы 12.п.гл.р (р 1,4) задержки, коммутаторы 13.n.m.p, умножитель 14.п.m

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

О

ю XI о

00

ел

Арифметический блок (фиг.5) содержит коммутаторы 18.n.m.p, 19,n.m.p, арифметические узлы 20.n.m.p, 2,n.m р, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 22.n.m.p.

Блок ввода (фиг.6) содержит аналого- цифровой преобразователь 23, элемент ИЛИ-НЕ 24, D-триггеры 25,п (п 1,4), регистры 26,п.

Блок управления содержит (фиг.7) счетчик 27, дешифраторы 28.m (rn iTTvPl).

Регистры 26.п и триггеры 25.п срабатывают по положительному фронту синхроим- пульса, все остальные регистры - по отрицательному фронту.

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

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

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

В следующие четыре такта (2-5) на входную шину этого процессорного модуля поступают первые входные отсчеты Х/0, Х/4, Х/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 задержки и поступают на второй вход арифметического

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

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

0 входах соответственно. За эти четыре такта в элемент 10.1.1.1 задержки заносятся четыре соответствующие суммы Х/0 + Х/16, Х/14 + Х/20, Х/8 + Х/24, Х/12 + Х/28.

В следующие четыре такта (10-13) на

5 входную шину этого процессорного модуля поступают входные отсчеты Х/32, Х/36. Х/40, Х/44. На управляющем входе коммутатора 13.1.1.3 - верхний логический уровень. На управляющих входах остальных

0 коммутаторов процессорного модуля - нижний логический уровень. При верхнем логическом уровне коммутатор 13.1.1.3 принимает информацию со своего первого входа, поэтому эти четыре отсчета последо5 вательно записываются в элемент 12.1.1.3 задержки и поступают на второй вход арифметического блока 9.1.1.2. Коммутаторы 13.1.1.1 и 13.1.1.2 принимают информацию с второго входа. Поэтому первые и вторые

0 четыре отсчета циклически сдвигаются в элементах 12.1.1,1 и 12.1.1.2 задержки и поступают на первый и второй входы арифметического блока 9.1.1.1 соответственно. На управляющие входы арифметического бло5 кз 9.1.1.1 поступают верхний и нижний логические уровни соответственно, что соответствует операции А + В. где А и В - операнды на первом и втором-входах соответственно. За эти четыре такта в элемент

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

В следующие четыре такта (14-17) на входную шину этого процессорного модуля поступают входные отсчеты Х/48, .Х/52,

5 X/56, Х/бО. На управляющем входе коммутатора 13.1.1.4 - верхний логический уровень. На управляющих входах остальных коммутаторов процессорного модуля - нижний логический уровень. При верхнем логическом уровне коммутатор 13.1.1.4

принимает информацию со своего первого, входа поэтому эти четыре отсчета последовательно записываются в элемент 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) - С, где А + JB и С - операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.2 задержки заносятся четыре соответствующие суммы Х/0 + JX/16 - Х/32, Х/4 + JX/20 - Х/36, Х/8 + JX/24 - Х/40, Х/12 + JX/28 - Х/60. На управляющие входы арифметического блока 9.1.1.3 поступают нижние логические уровни, что соответствует операции (А + В + С + D), где А + В + С и D - операнды на первом и втором входах соответственно. За эти четыре такта на первый вход умножителя 14.1.1 последовательно поступают суммы

Х/0+ Х/16 +Х/32+ Х/48, Х/4+ Х/20 +Х/36+ Х/52, Х/8 + Х/24 + Х/40+ Х/56, Х/12+ Х/28 + Х/44 +Х/60.

На второй вход умножителя 14.1.1 поступает значение Л/640, где WN n - exp{-j 2яп /N}.

На вход второго процессорного модуля группы поступают четыре первых результата первой итерации алгоритма БПФ. На управляющие входы арифметического блока 9.1.1.1 поступают верхние логические уровни, что соответствует операции А - В. где А и В - операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.1 задержки заносятся четыре соответствующие разности Х/0 - Х/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 принимают информацию с второго входа. Поэтому вторые, третьи,

четвертые четыре отсчета циклически сдвигаются в элементах 12.1.1,2, 12.1.1.3,

12.1.1.4задержки поступают на вторые входы арифметических блоков 9.1.1.1, 9.1.1.2, 9.1.1.3 соответственно. На управляющие

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

10.1.1.2 задержки заносятся четыре соответствующие суммы Х/0 - Х/16 + Х/32,

Х/4-JX/20 +Х/36,

Х/8-Х/24 + Х/40

Х/12-JX/28-Х/60

На управляющие входы арифметическо- го блока 9.1.1.3 поступают нижний и верхний логические уровни соответственно, что соответствует операции (А + JB - С) - JD, где A + jB-CnJD-операнды на первом и втором входах соответственно. За эти четыре такта на первый вход умножителя 14.1.1 последовательно поступают суммы:

X./0 + JX/16-X/32-JX/48 X/4 + JX/20-X/360JX/52, Х/8+ JX/24-Х/40-JX/56,

X/12 + JX/28-X/44-JX/60.

На второй вход умножителя 14.1.1 поступают значения WeiO, , , W6412. На вход второго процессорного модуля группы поступают четыре вторых результата первой итерации алгоритма БПФ. На управляющие входы арифметического блока 9.1.1.1 поступают нижний и верхний логические уровни соответственно, что соответствует операции А -jB, где А и В - операнды

на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.1 задержки заносятся четыре соответствующих разности Х/0 - jX/18, Х/4 - jX/20, Х/8 - JX/24, X/12-JX/28.

В следующие четыре такта (22-25) на

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

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 поступают верхние логические уровни, что соответствует one- раци(А-JB)- С, где A-JB и С-операнды на первом и втором входах соответственно. За эти четыре такта в элемент 10.1.1.2 задержки заносятся четыре соответствующие суммы

X/0-JX/16-X/32

X/4-JX/20-X/26

Х/8 - JX/24 - Х/40, Х/12 - (Х/28 - Х/60.

На управляющие входы арифметического блока 9.1.1,3 поступают верхние логические уровни, что соответствует операции (А - В + С) - D, где А - В + С и D - операнды на первом и втором входах соответственно. За эти четыре такта на первый вход умножителя 14.1.1 последовательно поступают суммы Х/О-Х/16 ;Х/32 - Х/48, Х/4 - Х/24 + Х/Зб- -Х/52, Х/8-Х/24 +Х/40-Х/56, Х/12-Х/28+ + Х/44-Х/60,

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

В следующие четыре такта (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 принимают информацию с второго входа. Поэтому первые, вторые, четвертые четыре отсчета циклически сдвигаются в элементах 12,1.1.1, 12.1.1.2.

12.1.2.4задержки. На управляющие входы арифметического блока 9.1.1.3 поступают

верхний и нижний логические уровни, что соответствует операции (А - JB - С) + JD, где А-jB-СиJD-операнды на первом и втором входах соответственно. За эти четыре такта

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

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

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

0 Четырнадцатый такт. На входе процессорного модуля значение Y/0 (Х/0 + Х/16+ + Х/32 + Х/48) W640, которое через коммутатор 13.1.2.1 поступает на вход элемента задержки 12.1.2.1.

5Пятнадцатый такт. На входе процессорного модуля значение Y/64 0 (Х/4 + Х/20+ + Х/36 + Х/52) WwO, которое через коммутатор 13.1.2.2 поступает на вход элемента 12.1.2.2 задержки. Значение Y/0 через ком0 мутатор 13.1.2.1 поступает снова на вход элемента 12.1.2.1 задержки. На управляющие входы поступают нижние логические уровни. Арифметический блокЭ. 1.2.1 выполняет операцию А + В. На его выходе - зна5 чение Y/0 +Y/4.

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

0 12.1.2.3 задержки. На управляющие входы поступают верхний и нижний логические уровни соответственно. Арифметический блок 9.1.2.1 выполняет операцию А + JB. На его выходе - значение Y/0 + JY/4. Арифме5 тический блок 9.1.2.2 выполняет операцию (А + В) + С. На его выходе - значение Y/0 + +Y/4 + Y/8.

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

Q + Х/60) W640, которое через коммутатор 13.1.2.4 поступает на вход элемента 12.1.2.4 задержки. На одни управляющие входы поступают верхние логические уровни, на другие - нижние логические уровни. Арифс метический блок 9.1.2.1 выполняет операцию А - В. На его выходе - значение Y/0 - -Y/4. Арифметический блок 9.1.2.2 выполняет операцию (А + jB/ - С). На его выходе - значение Y/0 + JY/4 - Y/8. Арифметический блок 9,1.2.3 выполняет операцию (А + JB+ С) +

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

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

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

W640, W640, W640, W640, W641, W645, W649,

W6413, W642, W6410, W6418, W6426, W643, W6415, W6427. W6439, с выхода блока 11.2.2 постоянной памяти - коэффициенты Л/640, W644, W648, Л/б412. Отличие для третьей группы заключается в том, что на вход этой группы поступают отсчеты Х/2, Х/б, Х/10, Х/14, Х/18, Х/22, Х26, Х/30, Х/34, Х/38, Х/42, Х/46, Х/50, Х/54, Х/58, Х/62, с выхода блока 11.3.Т постоянной памяти последовательно поступают коэффициенты Л/640,

W640, W640, W640, W642, W646, W6410, W6414, W644, W6412, W6420, W6428, Л/б4б, W6418, W6439, W6442, с выхода блока 11.3.2 постоянной памяти - коэффициенты W640, Л/б48, W6416, We424. Отличие для четвертой группы заключается в том, что на вход этой группы поступают отсчеты Х/З.Х/7, Х/11, Х/15, Х/19, Х/23, Х/27, Х/31, Х/35, Х/39, Х/43, Х/47, Х/51, Х/55, Х/59, Х/63, с выхода блока 11.4.1 постоянной памяти последовательно поступают коэфициенты Л/640, We40,

W640, W640, W643, W647, W6411, W6415, W646,

W6414, W6422, W6430, W649, W6421, W6433, W6445, с выхода блока 11.4.2 постоянной памяти - коэффициенты , W6412, W6424, W6436.

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

Семнадцатый такт. На вход процессорного модуля 7.1.1 поступает результат второй итерации алгоритма БПФ 2(0) (у(0) + + у(4) + у(8) + у(12)) W640, который является

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

Восемнадцатый такт. На вход процес- 0 сорного модуля 1.1.1 поступает результат второй итерации алгоритма БПФ. Z(4) (Y/0 + jY/4 - Y/8 - JY/12) We40, который является операндом В для арифметического блока 16.1.1. Операндом А для этого ариф5 метического блока является О. На выходе арифметического блока 16.1.1 - значение Z(4). На вход процессорногд модуля 7.1,2 поступает результат второй итерации алгоритма БПФ Z(0) (Y/0 + Y/4 + Y/8 +

0 + Y/12) W640, который является операндом В для арифметического блока 16.1.2. Операндом А для этого арифметического блока является Z(0). На управляющих входах этого арифметического блока постоянно нижние

5 логические уровни, что соответствует операции А + В. На выходе арифметического блока 16.2.1 -значение Z(0) + Z(1).

Девятнадцатый такт, На вход процессорного модуля 7.1.1 поступает результат

0 второй итерации алгоритма БПФ Z(8) (Y(0) - Y(4) + Y(8) - Y(12) W640, который является операндом В для арифметического блока 16.1.1, Операндом А для этого арифметического блока является О. На выходе .эриф5 метического блока 16.1.1 - значение Z(8). На вход процессорного модуля 7,1.2 поступает результат второй итерации алгоритма БПФ Z(4) (Y(0) JY(8) JY(11)) W640, который является операндом В для арифметического

0 блока 16.1.2. Операндом А для этого арифметического блока является О. На выходе арифметического блока 16.1.2 - значение Z(4). На вход процессорного модуля 7.2.1 поступает результат второй итерации алгорит5 (5) (Y(1) + JY(5)-Y(9) + jY/13)W644. который является операндом В для арифметического блока 16.2.1. Операндом А для этого арифметического блока является значение Z(4). На управляющих входах этого

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

арифметического блока постоянно верхний и нижний логические уровни соответственно, что соответствует операции А + JB. На Ешходе арифметического блока 16.2.2 -значение Z(0) + Z(1). На вход процессорного модуля 7.1,2 поступает результат второй итерации алгоритма БПФ Z(4) (Y/0 + + JY/4 - Y/8 - )Y/12)W640, который является операндом В для арифметического блока 16.1.2. Операндом А для этого арифметического блока является О. На вход процес1 сорного модуля 7.1,3 поступает результат второй итерации алгоритма БПФ 2(0)

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

1 блока 16.1.3. Операндом А для этого арифметического блока является О. На управляющих входах этого арифметического блока постоянно нижние логические уровни, что соответствует операции А + В, На выходе арифметическогдо блока 16,1.3 значение Z(0). На вход процессорного модуля 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(0) + Z(1) + Z(2) + Z(3).

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

С целью упрощения дальнейшая работа вычислительной матрицы не описывается. Отметим, что на втором столбце матрицы вычисляется значение Z(i) + jZ(i) -1) - Z(i f 2)- - jZ(i +3), на третьем столбце значение Z(i) Z(i+1) + Z(i+2) - Z(i+3), на четвертом столбце значение Z(i)-IZ(l+1)-Z(i-f-2) + jZ(l-K3. В соответствии с данными операциями на управляющих входах арифметических блоков процессорных модулей матрицы постоянно выставлены следующие логические уровни: 0-0, 0-0, 0-0, 0-0,

о-о,

1-0,

1-1.

0-1.

о-о, 1-1.

о-о, 1-1,

0-0, 0-1,

1-1,

1-0.

Начиная с двадцать первого такта на выходе процессорного модуля 7.4.1 последовательно получаются следующие коэффи0 циенты БПФ: 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 после5 довательно получаются следующие коэффициенты БПФ: 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).

Начиная с двадцать третьего такта на

0 выходе процессорного модуля 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).

5Начиная с двадцать четвертого такта на

выходе процессорного модуля 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).

0 F{55). F(59), F(63).

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

случае, когда каждая группа процессорных

второго типа содержит по одному элементу.

В этом случае матрица этих процессорных

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

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

0 На вход процессорного модуля 7.1.1 поступает результат второй итерации алгоритма БПФ Z(0) (у(0) + у(4) + у(8) + у(12)) W640, который является операндом В для арифметического блока 16.1.1. Операндом А для

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

Вторая четверть семнадцатого такта. На вход процессорного модуля 7.1.1 поступает результат второй итерации алгоритма БПФ Z(0), который является операндом В для

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

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

Третья четверть семнадцатого такта. На вход процессорного модуля 7.1.1 поступает результат второй итерации алгоритма БПФ Z(0), который является операндом В для арифметического блока 6.1.1. Операндом А для этого арифметического блока является О. На выходе арифметического блока 16.1.1 - значение Z(0). На вход процессорного модуля 7.2.1 поступает результат второй итерации алгоритма БПФ Z(1), который является операндом В для арифметического блока 16,2.1. Операндом А для этого арифметического блока является значение Z(0). На управляющих входах этого арифметического блока - верхний и нижний логические уровни соответственно, что соответствует операции A + JB. На выходе арифметического блока 16.2.1 - значение Z(0) + JZ(1). На вход процессорного модуля 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(0) + Z(1) + Z(2).

Последняя четверть семнадцатого такта. На вход процессорного модуля 7.4.1 поступает значение Z(3) (у(3) + у(11) y(15)). На выходе арифметического блока 16.4.1 - значение Z(0) + Z(1) + Z(2) + Z(3).

С целью упрощения дальнейшая работа вычислительной матрицы не описывается. Отметим, что на выходе линейки появляются значения Z(i) + Z(i+1) + Z0+2) +Z0+3), Z(i) + +JZ(I+1) - Z{l+2) - jZ(i+3). Z(i) - Z(i+1) + Z(l+2) - -Z(i+3), Z(i) - JZ0+1) - Z(l+2) + JZ0+3). В соответствии с данными операциями на входах арифметических блоков 16.П.1 (п 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). F(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). 5В этом случае синхронизация элементов 8.2-8,4 и 7.П.1 осуществляется непосредственно с выхода генератора 5 тактовых импульсов.

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

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

5 первого типа, М-1 блоков постоянной памяти, блок управления и генератор тактовых импульсов, выход которого подключен к тактовому входу блока управления, i-ый 0 1. М-1) управляющий выход которого подклю0 чен к первому управляющему входу 1-го процессорного модуля первого типа первой группы, второй управляющий вход которого подключен к выходу 1-го блока постоянной памяти, адресный вход которого подключен

5 к 1-му адресномулыходу блока управления, выход j-ro 0 1Г, М-2) процессорного модуля первого типа первой группы подключен к информационному входу i+1-го процессорного модуля первого типа первой группы.

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

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

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

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

управляющие входы всех арифметических блоков, отличающееся тем, что, с целью повышения быстродействия, в него введены вторая, третья и четвертая группы из М-1 процессорных модулей первого типа в каждой группе, блок ввода, три блока задержки и четыре группы из L-x (L - целое число) процессорных модулей второго типа в каждой группе, при этом первый и второй управляющие входы i-ro процессорного модуля первого типа К-ой группы подключены соответственно к l-му управляющему выходу блока управления и выходу 1-го блокз постоянной памяти, выход j-ro процессорного модуля первого типа К-ой группы подключен к информационному входу.J+ процессорного модуля первого типа К-ой группы, первый информационный вход К- го процессорного модуля второго типа 1-ой ,( 1,1) группы подключен к первому выходу (К-1)-процессорного модуля второго типа I- 1-ой группы, второй информационный вход К-гр процессорного модуля второго типа К- ой группы подключен к второму выходу 1-го процессорного модуля второго типа К-1-ой группы, выход М-1-го процессорного модуля первого типа первой группы подключен к первому информационному входу первого процессорного модуля второго типа первой трупы, выход М-1-го процессорного модуля первого типа К-ой (К 57) группы подключен к входу К-1-го блока задержки, выход которого подключен к первому информационному входу первого процессорного модуля второго типа К-ой группы, второй выход 1-го процессорного модуля второго типа четвертой группы является 1-ым информационным выходом устройства, информационным входом которого является информационный вход блока ввода, 1-ый -которого подключен к информационному входу первого процессорного модуля первого типа К-ой группы, выход генератора тактовых ммпульсов подключен к тактовому входу входного блока, при этом в каждый процессорный модуль первого типа введен блок постоянной памяти, выход которого подключей к второму входу умножителя, адресный вход блока постоянной памяти 1-го процессорного модуля первого типа 1-ой группы подключен к i-му адресному выходу блока управления, при этом процессорный

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

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

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

входу 1-го регистра, выход которого является -ым выходом входного блока, тактовым входом которого являются соединенные между собой тактовые входы всех D-тригге- ров и аналого-цифрового преобразователя,

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

ы и

6.М

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

Г

Т

Т5Л

U1

и

I

Т I

а -

S

-

8

Фм.1

Т

Т

Ш

W

из

I

I

757

I

Фт.2

Фиг.

Фиг.З

I

Пп.т

ЈLI

Фиг. 5

i

Физ.6

ФмЛ