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

 

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

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

РЕСПУБЛИК (19) ()3) (я)э G 06 F 15/332

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4724694/24 (22) 31.07.89 (46) 23.03.92. Бюл. М 11 (71) Житомирский филиал Киевского политехнического института им. 50-летия Великой Октябрьской социалистической революции (72) Д.В.Корчев, Ю.С,Каневский, И.А,Коноплицкий и В.И.Лозинский (53) 681.32(088.8) (56)авторское свидетельство СССР

N- 1196894, кл. G 06 F 15/332, 1983.

2.Linderman ВМ. е.а. A70 mter 1.2 micron

CMOS 16-paint 0FT processar. — Proc. 1ЕЕЕ

Cusfom integrat Clrcults Conf., Portland, 1987, р.219 — 222. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике, предназначено для вычисления быстрого преобразования Фурье, Изобретение может быть использовано в системах цифровой обработки сигналов.

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

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

Известно устройство для вычисления одномерного ДПФ и выполнения процедуры цифровой фильтрации, содержащее N умножителей, N сумматоров, блок регистров из N регистров, генератор тактовых имсчет того, что устройство содержит входную буферную память 2, генератор 3 тактовых импульсов, счетчик 5, блоки 6,7 постоянной памяти, группу вычислительных модулей 1го типа 8, регистр 9, триггер 10, буферные регистры 11, сумматоры 12,13, регистр 14 результата, вычислительный модуль 2-го типа 15, блок 16 постоянной памяти, буферный регистр 17, сумматор 18, умножитель

19, блок 20 постоянной памяти, вычислительные модули 3-го типа 21, сумматоры 22 и 23, триггер 24, коммутаторы 25 и 26, буферные регистры 27 и 28, регистры 29, буферные регистры 30, вычислительный модуль 4-го типа 31, сумматор 32, коммутатор 33, буферные регистры 34, триггер 35, группу вычислительных модулей 3-го типа

36, вычислительный модуль 1-го типа 37, выходную буферную память 38, триггеры 40 и 41, вычислительные модули 4-го типа 42. регистры 44, буферные регистры 45, сумматоры 46, сумматоры 4 результата, регистры

48 результата, триггеры 49, регистр 50, сумматор 51, регистры 52, сумматоры 57 и 58, сумматоры 59, регистры 60, коммутатор 61, ) сумматор 62, 10 ил.

° виаЪ пульсов, счетчик, дешифратор и линейку элементов И (1).

Однако реализация данного устройства требует больших аппаратурных затрат.

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

20

50 равляются при помощи генератора тактовых импульсов и счетчика (2).

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

Поставленная цель достигается тем, что в устройство для вычисления БПФ, содержащее генератор тактовых импульсов, счетчик, умножитель, первый блок постоянной памяти, блоки входной и выходной буферной памяти, введены второй, третий и четвертый блоки постоянной памяти, первая группа из (А-1)/2 вычислительных модулей первого типа, каждый из которых состоит из двух сумматоров, двух буферных регистров, проходного регистра, регистра результата и триггера, первый вычислительный модуль второго типа, который состоит из сумматора и буферного регистра, вторая группа из ( — 1)/2 вычислительных модулей третьего типа, каждый из которых состоит из группы проходных регистров, содержащей А регистров, трех (за исключением 1-ro вычислительного модуля, который содержит две группы) групп буферных регистров, каждая иэ которых содержит по А регистров, двух коммутаторов, триггера, двух сумматоров, первый вычислительный модуль четвертого типа, который состоит из триггера, сумматора, коммутатора и группы буферных регистров, содержащей А регистров, вторая группа ( — 1)/2 вычислительных модулей третьего типа, полностью аналогичная первой, второй вычислительный модуль четвертого типа, аналогичный первому, вторая группа (А — 1)/2 вычислительных модулей первого типа, полностью аналогичная первой, второй вычислительный модуль второго типа, аналогичный первому, выход генератора тактовых импульсов соединен с шиной синхронизации и со счетным входом счетчика, выход которого соединен с адресными входами. первого — четвертого блоков постоянной памяти, входного и выходного блоков буферной памяти, 2(А+В) двухразрядных выходов второго блока постоянной памяти соединены соответственно с управляющими входами всех сумматоров, имеющихся в вычислительном устройстве, В+1 выходов третьего блока постоянной памяти соединены соответственно с синхровходами триггеров в первой и второй группах вычислительных модулей третьего типа и в первом и втором вычислительных модулях четвертого типа, в первой и второй группах вычислительных мод/лей первого типа вход и выход проходного регистра соединены с входами первого и второго буферных регистров соответственно, выходы которых соединены с входами сумматора, выход котороro соединен с первым входом сумматора результата, выход которого соединен с входом регистра результата, вход триггера соединен с синхровходами буферных регистрое, синхровходы триггера, проходного регистра, регистра результата соединены с шиной синхронизации, выход проходного регистра i-го (i = 1, (А — 1)/2 — 1) вычислительного модуля соединен с входом проходного регистра (i+1)-го вычислительного модуля, вход триггера 1-го (I = 11A112 — 1) вычислительного модуля соединен с выходом триггера (i+1)-го вычислительного модуля, вто ой вход сумматора результата i-го (i = 1, А — 1 2-1 - вычислительного модуля соединен с выходом регистра результата (1+1)-го вычислительного модуля, выход проходного регистра (А — 1)/2-ro вычислительного модуля соединен с входом регистра перрого (второго) модуля второго типа, выход которого соединен с первым входом сумматора этого вычислительного модуля, выход которого соединен с вторым входом сумматора результата (А — 1)/2-ro вычислительного модуля, синхровход регистра первого и второго вычислительных модулей второго типа соединен с шиной синхронизации, второй вход сумматора первого и второго вычислительных модулей второго типа соединен с нулевой шиной, вход проходного регистра первого вычислительного модуля является информационным входом группы вычислительных модулей первого типа, выход регистра результата первого вычислительного модуля является информационным выходом всей группы вычислительных модулей, в первой группе вычислительных модулей первого типа информационный вход соединен с выходом входного блока буферной памяти, вход которого является информационным входом всего устройства, информационный выход соединен с информационным входом первой группы вычислительных модулей третьего типа, вход триггера (А — 1)/2-го вычислительного модуля соединен с первым выходом первого блока постоянной памяти, во второй группе вычислительных модулей первого типа информационный вход соединен с информационным выходом второй группы вычислительных модулей третьего типа, вход триггера (А — 1)/2-ro вычислительного модуля соединен с четвертым выходом первого блока постоянной памяти, информационный выход соединен с входом выходного блока буферной памяти, выход которого я вля ется информац ионн ым выхо,о всего устройства, в. первой и второй

1721610

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

i-ro (! = 1,А — 1) регистра соединен с входом (!+1)-го регистра, вход и выход группы проходных регистров соединен соответственно с первыми входами первого и второго ком-. мутаторов, вторые входы которых соединены с выходами первой и второй групп буферных регистров соответственно, входы которых соединены с выходами первого и второго коммутаторов соответственно, выходы которых соединены с входами сумматора, выход которого соединен с первым входом сумматора результата, выход которого (за исключением первого вычислительного модуля) соединен с входом третьей группы буферных регистров, синхровходы которых, а также синхровходы всех остальных регистров соединены с шиной синхронизации, управляющие входы коммутаторов соединены с входом триггере, выход группы проходных регистРов I-го (i = 1,(В-1)/2-1) вычислительного модуля соединен с входом группы проходных регистров (!+1)-го вычислительного модуля, вторрй вход сумматора результата !-lo (i =

= Тл — 1)72 — 1) вычислител нного модуля соединен с выходом третьей группы буферных регистров (i+1)-го вычислительного модуля, вход триггере I-го (I = 1,(B — 1)72 — 1) вычислительного модуля соединен с выходом триггера (i+1)-го вычислительного модуля в первом и втором вычислительных модулях четвертого типа выход i-го (i = 1,А — 1) регистра группы буферных регистров соединен с входом (!+1)-го регистра, вход группы буферных регистров соединен с выходом коммутатора, второй вход которого соединен с выходом группы буферных регистров, выход которой соединен с первым входом сумматора, второй вход которого соединен с нулевой шиной, управляющий вход коммутатора соединен с входом триггера, выход которого соединен с входом триггера ( — 1)/2-ro вычислительного модуля, первый вход коммутатора соединен с выходом группы проходных регистров(8-1)/2-го вычислительного модуля, вь.ход сумматора соединен с вторым входом сумматора результата (В-1)/2-ro вычислительного модуля, в первой группе вычислительных модулей третьего типа информационный выход соединен с первым входом умножи5

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

На фиг.1-10 изображены структурные схемы блоков устройства для вычисления БПФ.

Устройство содержит информационный вход 1, информационный выход 39, генератор 3 тактовых импульсов, счетчик 5, умножитель 19, шину 4 синхронизации, первый блок 16 постоянной памяти, блоки входной

2 и выходной 38 буферной памяти, блоки

6,20 и 7 постоянной памяти, первую группу

8.i из (А — 1)/2 модулей первого типа, каждый из которых состоит из двух сумматоров 12,i и 13. i, двух буферных регистров 11 !,проходного регистра 9.i, регистра 14,i результата и триггера 10.!, кроме того, имеется первый модуль 15 второго типа, который состоит из сумматора 18 и буферного регистра 17, первую группу 21.i иэ (В-1)/2 модулей третьего типа, каждый иэ которых состоит из группы проходных регистров 29 !.k (k = 1,А), трех (за исключением первого модуля, который содержит две группы 27.! и 28.i) групп буферных регистров 27,i, 28 и 30.i, каждая иэ которых содержит по А регистров, двух коммутаторов 25 и 26,i, триггера 24.!, двух сумматоров 23.! и 22,i, кроме того. имеется первый модуль 31 четвертого типа, который состоит из триггера 35, сумматора 32, коммутатора ЗЗ и группы буферных регистров

34, содержащей А регистров, вторую группу

36.i ( — 1)/2 модулей третьего типа, полностью аналогичную первой, а также второй модуль четвертого типа, вторую группу 37.i (А-1)/2 модулей первого типа, полностью аналогичную первой, а также второй модуль второго типа, выход генератора 3 тактовых импульсов соединен с шиной 4 синхронизации и с входом. счетчика 5, выход которого соединен с адресными входами блоков 6,20,7 и 16 постоянной памяти и блоков 2 и 38 буферной памяти, 2(А+В) двухразрядных выходов 7.! второго блока 7 постоянной памяти соединены соответственно с управляющими входами всех сумматоров, имеющихся в вычислительном устройстве, В+1 выходов 20.k третьего блока

20 постоянной памяти соединены соответственно с синхровходами триггеров 24,i.

40.i, 35, 41 в модулях третьего типа первой

1721610

21.i и второй 36.i групп, включая и модули четвертого типа 31 и 42, в первой и второй группах 8.! (37.i) модулей первого типа вход и выход проходного регистра 9.l (44.I) соединены с входами первого 11,i.1 (45,I.1) и второго 11.i.2 (45Л.2) буферных регистров соответственно, выходы которых соединены с входами сумматора 12.! (46Л), выход которого соединен с первым входом сумматора 13.i (47.!) результата, выход которого соединен с входом регистра 14Л (48,l) результатаа, вход триггера 10.i (49.!) соединен с синхровходами буферных регистров 11.i (45.i), синхровходы триггера 10.l (49.I), проходного регистра 9.i (44.i), регистра 14Л (48.i) результата соединены с шиной 4 синхронизации, выход проходного регистра 9.! (44 Л)

8,i-ro (37.i-го) (i = 1,(A — 1)/2 — 1) модуля соединен с входом проходного регистра 9.i+1 (44.i+1) (8.!+1)-го (37,i+1-ro) модуля, вход триггера 10,i (49.i) 8.!-го (37.!-го) (i = 1,(А—

1)/2 — 1) модуля соединен с выходом триггера

10.i+1 (49.i+1) (8Л+1)-го (37.i+1-го) модуля, второй вход сумматора 13.! (47.i) результата

8.i-ro (37.i-го) (! = 1, (А — 1)/2 — 1) модуля соединен с выходом регистра 14Л+1 (48Л+1) результата (8,i+1)-го (37.i+1-го) модуля, выход проходного регистра 9.i (44.i) 8,(А — 1)/2-го (37.(А — 1)/2-го) модуля соединен с входом регистра 17 (50) модуля 15 (43), выход которого соединен с первым входом сумматора 18 (51) этого модуля, выход которого соединен с вторым входом сумматора 13Л (47.i) результата 8.(А — 1)/2-го (37.(А — 1)/2-ro) модуля, синхровход регистра 17 (50) модуля второго типа соединен с шиной 4 синхронизации, второй вход сумматора 18 (51) модуля 15 (43) соединен с нулевой шиной, вход проходного регистра 9.i (44.i) 8.1-го (37.1-ro) модуля является информационным входом всей группы модулей, выход регистра 14.i (48.!) результата 8.1-ro (37,1-го) модуля является информационным выходом всей группы модулей, в первой группе модулей 8.! информационный вход соединен с выходом входного блока 2 буферной памяти, вход которого является информационным входом 1 всего устройства, информационный выход соединен с информационным входом первой группы 21Л модулей, вход триггера

10,i 8.(А — 1)/2-го модуля соединен с первым выходом 6.1 первого блока 6 постоянной памяти, во второй группе модулей 37.i информационный вход соединен с информационным выходом второй группы модулей

36.i, вход триггера 49Л 37,(А-1)/2-го модуля соединен с четвертым выходом 6.4 первого блока 6 постоянной памяти, информационный выход соединен с входом выходного блока 38 буферной памяти, выход которого является информационным выходом 39 всего устройства, в первой 21.l и во второй 36.! группах модулей вход первого регистра группы проходных регистров 29.i (52.i) 21.1го (36.1-го) модуля является информационным входом всей группы модулей, выход сумматора результата 22.i (53.i) 21.1-го (36,1го) модуля является информационным выходом всей группы модулей, во всех группах регистров 29.!Лс (52.!Лс), 28.!Лс (54Л.k), 27.!Лс (55.М), ЗО.И (56.Щ выход k-ro (k = 1,А-1) регистра соединен.с входом (k+1)-го регистра, вход и выход группы проходных регистров 29.! (52.!) соединены соответственно с первыми входами первого 25.! (57,!) и второго 26.i (58.l) коммутаторов, вторые входы которых соединены с выходами первой 27.i (55.i) и второй 28.i (54.i) групп буферных регистров соответственно, входы которых соединены с выходами первого 25,i (57.!) и второго 26.i (58.i) коммутаторов соответственно, .зыходы которых соединены с входами сумматора 23,i (59.i), выход которого соединен с первым входом сумматора 22,i (53.i) результата, выход которого (за исключением 21 1-ro (36.1-го) модуля) соединен с входом третьей группы буферных регистров

30.i (56.i), синхровходы которых, а также синхровходы всех остальных регистров соединены с шиной 4 синхронизации, управляющие входы коммутаторов 25.i (57Л) и

26,i (58,i) соединены с входом триггера 24.i (40.i), выход группы проходных регистров

29.i (52Л) 21.i-ro (36.i-го) (i = 1,( — 1)/2 — 1) модуля соединен с входом группы проходных регистров 29,i+1 (52.i+1)(21Л+1)-го(36.i+1-го) модуля, второй вход сумматора 22Л (53,i) результата 21.!-ro (36.i-ro) (i = 1,(B — 1)/2 — 1) модуля соединен с выходом группы буферных регистров 30,i+1 (56.i+1). (21,i+1)-ro (36,i+1-ro) модуля, вход триггера 24.! (40Л)

21Л-ro (36.i-ro) (i = 1,(B — 1)/2 — 1) модуля соединен с выходом триггера 24,i+1 (40.i+1) (21.i+1)-го (36. !+1-го) модуля, в модуле 31 (42) выход 34Л-го (60,i-го) (i = 1,А — 1) регистра группы буферных регистров соединен с входом (34.!+1)-го (60.i+1-ro) регистра, вход группы буферных регистров 34.i (60, !) соединено с выходом коммутатора 33 (61), второй вход которого соединен с выходом группы буферных регистров 34.i (60Л), выход которой соединен с первым входом сумматора

32 (62), второй вход которого соединен с нулевой шиной, управляющий вход коммутатора соединен с входом триггера 35 (41), выход которого соединен с входом триггера

24Л (40,i) 21.( — 1)/2-го (36.(B — 1)/2-го) модуля, первый вход коммутатора 33 (61) соединен с выходом группы проходных регистров

29.! (52Л) 21.(В-1)/2-го (36,(В-1)/2-ro) моду1721610

10 ля, выход сумматора 32 (62) соединен с вторым входом сумматора результата 22Л (53Л)

21.(В-1)/2-ro (36.(В-1)/2-го) модуля, в группе модулей 21.i информационный выход соединен с первым входом умножителя 19, вход триггера 35 модуля 31 — с третьим выходом 6.3 первого блока 6 постоянной памяти, в группе модулей 36.i информационный вход соединен с выходом умножителя 19, вход триггера 41 модуля 42 соединен с четвертым выходом 6.4 первого блока 6 постоянной памяти, второй вход умножителя 19 соединен с выходом четвертого блока 16 постоянной памяти, все группы модулей работают с комплексными операндами.

Рассмотрим работу устройства потактно. Устройство вычисляет БПФ по алгоритму Винограда с периодом в N отсчетов, где

N = А х В, где А и  — простые числа. Для определенности полагают, что А = 3; В = 5.

С генератора 3 тактовых импульсов идут синхросигналы типа меандр, Применяются следующие сокращения: Рà — регистр; TP— триггер; MX —; СТ вЂ” счетчик;

БПП вЂ”; ББП вЂ” блок буферной памяти; ВХ вЂ”; ВЫХ вЂ” выход;

АЛУ вЂ” сумматор; УМН вЂ” умножитель; ШС— шина синхронизации.

Рассмотрим работу первой группы модулей 8.i. Допустим, что триггеры 10.i (49.!), проходные регистры 9.i (44Л), регистры 17 и

50, регистры 14.1(48Л) результата срабатывают по переднему фронту синхросигнала (положительный перепад), а буферные регистры 11.i (45.i) — по заднему фронту синхросигнала (отрицательный перепад).

В течение первых 15 тактов входные отсчеты поступают на ВХ 1 и записываются в ББП 2, после чего следует три холостых такта. В 19-м такте на выходе ББП 2 появляется первый отсчет (но уже в нужной последовательности). Этот такт считают первым, поскольку он первый для работы первой группы модулей первого типа, 1-й такт — ББП 2 = Х(О);

2-й такт — ББП 2 = Х(5); РГ9,1 =Х(0);

3-й такт — ББП 2 =-Х(10); РГ9.1 =Х(5); РГ

17 = Х(0); PI 11.1.1 = Х(10); РГ 11,1.2 = X(5);

АЛУ 18 = Х(0); АЛУ 12,1 = Х(5) + Х(10); АЛУ

13.1 = Х(0) + Х(5) + Х(10); БПП 6(6,1) = "1".

В 4-м такте на выходе первой группы появляется операнд Y(1) = Х(0)+ Х(5)+ Х(10).

Дальше работа первой группы продолжается по описанному алгоритму, Управляющие сигналы с БПП 7 поступают на АЛУ 12Л, 13.i, 18 таким образом, что на выходе первой группы появляются результаты, равносильные умножению двух матриц

14-йтакт- БПП 6(6.2)="0"; БПП20="1";

TP 24,2 = "1"; РГ 34.3 = Y(1); РГ 34.2 = Y(2);

20 РГ 34.1 = Y(3); РГ 29.2.3 = Y(4); РГ 29,2.2 = Y(5);

РГ 29.2.1 = Y(6); РГ 29,1.3 = Y(7); РГ29.1.2 =

= Y(8); РГ 29.1.1 = Y(9); МХ 25.2 = Y(7); МХ 26.2"= Y(4); АЛУ 32 = Y{1); АЛУ 23.2 = Y(4) + Y(7);

АЛУ22.2 = У(1) +Y(4)+Y(7);: РГ 14.1 = Y(10).

25 15-й такт — БПП 20 = "0"; TP 24.2 = "1";

РГ 34.3 = V(2); РГ 34.2 = У(3); РГ 34.1 = Y(1);

P Г 29,2,3 = Y(5); Р Г 29.2.2 = Y(6); Р Г 29,1,3 =

=Y(8); РГ 29.1,2 = Y(9); РГ 14.1 = Y(11); РГ

29.1.1 = Y(10); МХ 25.2 = Y(8); MX 26.2 = Y(5);

30 АЛУ32 = Y(2); АЛУ23.2= Y(5)+ Y(8);AJIY22.2=

= У(2)+ Y(5)+ Y(8); РГ 27.2.1 = Y(7); РГ 28.2.1=

= Y(4); РГ 30.2,1 = Y(1)+ Y(4)+ Y(7).

16-й такт — БПП 20 = "0"; TP 24,2 = "1";

РГ 34.3 = Y(3); РГ34.2 = Y(1); РГ34.1 = Y(2);

35 РГ 29,2,3 = Y(6); РГ 29. I.Ç = Y(9); РГ 29,1,2 =.

25.2= Y(9); MX26.2= Y(6); АЛУ32 = Y(3); АЛУ

23.2 = Y(6) + Y(9); АЛ У 22.2 =. Y(3) + Y(6) + Y(9);

РГ 27,2,1 = У(8); РГ 28.2.1 = Y(5); РГ 30,2,1 =

40 = Y(2)+ Y(5) + Y(8); P Г 30,2,2 = Y(1) + Y(4) + Y(7);

РГ 27.2.2 = Y(7); РГ 28.2.2 = Y(4).

17-й такт — БПП 20 = "1"; TP 24.1 = "1";

РГ34.3 = V(1); РГ 34,2 = Y(2); РГ 34.1 = Y(3);

РГ 29.1.3 = Y(10); РГ 29,1,2 = Y(11); РГ 14.1 =

45 =V(13}, PI-29.1.1 = Y(12); MX 25.1 = Y(13); MX

26.1 = Y(10); АЛУ32 = 0; АЛУ23.2 = Y(4)+ Y(7);

АЛУ 22.2 = Y(4) + Y(7); РГ 27.2.1 = Y(9); РГ

28.2.1 = Y(6}; РГ 30.2.1 = Y(3) + Y(6) + Y(9); P Г

30,2,2 = Y(2}+ Y{5)+ Y(8); РГ 27,2.2 = Y(8); РГ

50 28.2,2 = Y(5); P Г 30.2.3 = Y(1) + Y(4) + Y(7); P Г

27.2.3 = Y(4); РГ 28,2.3 = V(7); MX 25.2 = Y(7);

МХ 26.2 = Y(4); АЛУ 23.1 = Y(10) + Y(13); АЛУ

22.1 = Y(1) + Y(4) + Y(7} + Y(10) + Y(13), 55

1 1 1 X(k)

0 1 1 х X(k+5)

0 1 -1 X(k+10) где X(k) — входные отсчеты сигнала;

k = 0,3,6,9,12, а суммирование в скобках происходит по модулю 15.

Работу первой группы модулей 21.i рассмотрим начиная с 5-го такта, 5-й такт — РГ 14.1 = Y(1).

Далее в течение 9 тактов происходит передача по проходным регистрам 29.i. В

12-м такте на выходе Bllll 6(6.2) "1", на выходах БПП 20 "1", в результате чего TP 35

"1", а операнды через МХ 33 проходят в цепочку регистров 34Л.

=Y(10); РГ 14.1 = Y{12); РГ 29.1.1 = Y(11); МХ

Далее работа группы модулей 21.i продолжается по описанному алгоритму, Управляющие сигналы с БПП 7 на АЛУ 32, 23.i, 22.i поступают таким образом, что на выходе имеется результат, равносильный умножению матриц

1721610

Y(k)

Y(k+ 1)

Y(k+ 2) х Y(k+ 3)

Y(k+ 4) ! 0

1 1 1 1 1 0

0 1 1 1 1 0

0 1-1 0 0 0

0 1 1 -1 -1 0

0 0 0 1-1 0

0 1 -1 1 -1 0

Y(k)

Y(k+ 1)

Y(k+ 2)

x Y(k+ 3)

Y(k+ 4)

Y(k+ 5) 1 0 0 0 0 0

1 1 1 1 0 1

1 1 -1 1 0-1, 1 1 0-1 1 1!

1 1 0 1 -1 -1

X(k) х X(k+1)

X(k+ 2) 1 0 0

1 1 1

1 1-1

55 где Y(k) — значения, поступающие на вход группы модулей 21.1(k = 1,6,11).

С информационного входа модуля 21,1 значения поступают на первый вход УМН

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

Вторая группа модулей Зб.l работает аналогично первой группе 21,!. Управляющие сигналы с БПП 7 на АЛУ 62, 53.i, 59.! поступают таким образом, что на выходе имеется результат, аналогичный умножению двух матриц где Y(k) — значения, поступающие на вход группы модулей 36.i (k = 1,7,13).

С информационного входа модуля 36.1 значения поступают на информационный вход группы модулей 37.i, Группа модулей

37,l работает аналогично первой группе модулей 8.i. Управляющие сигналы с БПП 7 поступают на АЛУ 46.i, 47,i, 51 таким образом, что на выходе группы модулей появляются результаты, равносильные умножению двух матриц где X(k) — значения, поступающие на информационный вход группы модулей 37.l, k1,4,7,10,13.

С выхода группы модулей 37,i значения поступают на вход выходного блока 38 буферной памяти и с его выхода поступают на выход устройства в той последовательности, в которой они входили.

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

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

40 снижения аппаратурных затрат, устройство содержит второй, третий и четвертый блоки постоянной памяти, первую и вторую группы из (А — 1)/2 вычислительных модулей первого типа, первый и второй вычислительные модули второго типа, первую и вторую группу из ( — 1)/2 (А  — размер преобразователя) вычислительных модулей третьего типа, первый и второй вычислительный модули четвертого типа, причем вычислительный модуль первого типа содержит два сумматора, два буферных регистра, проходной регистр, регистр результата и триггер, вычислительный модуль второго типа содержит сумматор и буферный регистр, вычислительный модуль третьего типа содержит группу из А проходных регистров, в первом модуле две, в остальных — три группы по А буферных регистров в каждой группе, два коммутатора, триггер, два сумматора, вычислительный модуль четвертого типа содержит триггер, сумматор, коммутатор и группу из А буферных регистров, при этом выход генератора тактовых импульсов подключен к тактовым входам триггеров, первых и вторых буферных резисторов, и роходных регистров и регистров результата всех вычислительных модулей первого типа, тактовым входам регистров всех вычислительных модулей второго типа, тактовым входам проходных регистров группы и буферных регистров первой, второй и третьей групп всех вычислительных модулей третьего типа, к тактовым входам буферных регистров группы всех вычислительных модулей четвертой группы и к счетному входу счетчика, информационный выход которого подключен к адресным входам первого, второго, третьего и четвертого блоков постоянной памяти и адресным входам блоков входной и выходной буферной памяти 2"

«(А+В) выходов второго блока постоянной памяти подключены к управляющим входам соответствующих сумматоров вычислительных модулей первого типа и второй групп, первого и второго вычислительных модулей второго типа, вычислительных модулей третьего типа первой и второй групп, первого и второго вычислительных модулей четвертого типа, (В+1) выходов третьего блока постоянной памяти подключены к тактовым входам соответствующих триггеров вычислительных модулей третьего типа первой и второй групп и тактовым входам триггеров первого и второго вычислительных модулей четвертого, типа, в вычислительных модулях первого типа первой и второй групп информационный вход и выход проходного регистра соединены соответственно с входами соответственно первого и второго буфер13

1721610

55 ных регистров, выходы которых подключены соответственно к первому и второму входам первого сумматора, выход которого подключен к первому входу второго сумматора, выход которого подключен к информационному входу регистра результата, в первой и второй г ппах выход проходного регистра !-го(! =1, А — 1 2-1 вычислительного модуля первого типа подключен к информационному входу проходного регистра (i+1)-го вычислительного модуля первого типа, информационный вход i-ro триггера i-го вычислительного модуля первого типа подключен к выходу триггера (!+1)-ro вычислительного модуля первого типа, выход регистра результата которого подключен к второму входу второго сумматора !-го вычислительного модуля первого типа, выход проходного регистра (А-1)/2-го вычислительного модуля первого типа соединен с информационным входом регистра вычислительного модуля второго типа, выход которого подключен к первому входу сумматора данного вычислительного модуля, выход которого подключен к второму входу второго сумматора (А — 1)/2-го вычислительного модуля первого типа, второй вход сумматора вычислительного модуля второго типа подключен к входу логического нуля устройства, информационный вход проходного регистра первого вычислительного модуля первого типа первой группы подключен к выходу блока входной буферной памяти, информационный вход которого является информационным входом устройства, информационный выход регистра результата первого вычислительного модуля первого типа первой группы подключен к информационному входу первого проходного регистра группы первого вычислительного модуля третьего типа первой группы, информационный вход триггера (А—

-1)/2-го вычислительного модуля первого типа первой группы подключен к первому выходу первого блока постоянной памяти, выход регистра второго сумматора первого вычислительного модуля третьего типа второй группы подключен к информационному входу проходного регистра вычислительного модуля первого типа второй группы, информационный вход триггера (А — 1)/2-го вычислительного модуля первого типа которой подключен к второму выходу nepeoro блока постоянной памяти, а выход регистра результата первого вычислительного модуля первого типа второй группы подключен к информационному входу блока выходной буферной памяти, выход которого является информационным выходом устройства, во всех группах регистров вычислительных модулей третьего типа выход i-ro (i = 1,А — 1) регистра группы подключен к информационному входу (!+1)го регистра группы, информационный вход первого проходного регистра группы объединен с первым информационным входом первого коммутатора, а выход А-го проходного регистра группы подключен к первому информационному входу второго коммутатора, вторые информационные входы первого и второго коммутаторов подключены к выходам А-х буферных регистров соответственно первой и второй групп, информационные входы первых регистров которых подключены к выходам соответственно первого и второго коммутаторов, кроме того, выходы первого и второго коммутаторов подключены соответственно к первому и второму входам первого сумматора, выход которого подключен к первому выходу второго сумматора, выход которого подключен к информационному входу первого буферного регистра третьей группы, а управляющие входы первого и второго коммутаторов подключены к выходу триггера, выход А-го и оходного регистра группы!-ro(i=1,  — 1 2 — 1 вычислительного модуля третьего типа подключен к информационному входу первого проходного регистра группы (!+1)-го вычислительного модуля третьего типа, второй вход второго сумматора !-го вычислительного модуля третьего типа подключен к выходу А-го буферного регистра третьей группы (i+1)-го вычислительного модуля третьего типа, выход триггера которого подключен к информационному входу триггера i-ro вычислительного модуля третьего типа, выход !-го (i = 1,А-1) буферного регистра группы вычислительного четвертого типа подключен к информационному входу (!+1)-ro буфеаного регистра группы этого же модуля, а информационный вход первого буферного регистра группы подключен к выходу коммутатора, первый информационный вход которого подключен к выходу А-ro буферного регистра группы и соединен с первым входом первого сумматора, второй вход которого подключен к входу логического нуля устройства, выходы триггеров первого и второго вычислительных модулей четвертого типа подключены к управляющим входам коммутаторов этих же модулей и к информационным входам триггеров ( — 1)/2-го вычислительного модуля третьего типа соответственно первой и второй групп, а вторые информационные входы коммутаторов и выходы сумматоров первого и второго вычислительных модулей четвертого типа подключены соответственно к выходам А-проходных регистров групп и вторым входам вторых суммато15

1721610

16 ров (В-1)/2-х вычислительных модулей соответственно первой и второй группы, выход второго сумматора первого вычислительного модуля третьего типа первой группы подключен к первому входу умножителя, а информационный вход триггера первого вычислительного модуля четвертого типа подключен к третьему выходу первого блока постоянной памяти, информационный вход первого проходного регистра группы первого вычислительного модуля третьего типа второй группы подключен к выходу умножителя, второй вход которого подключен к вы5 ходу четвертого блока постоянной памяти, информационный вход триггера второго вычислительного модуля четвертого типа подключен к четвертому выходу первого блока постоянной памяти.

1721610

1721610

1721610

1721610

1721610 е> ю

Составитель Д. Корчев

Редактор И. Шмакова Техред М.Моргентал Корректор М. Шароши

3 аз 954 Тираж аказ Подписное

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

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

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