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

СОЮЗ СОВЕТСНИХ,СОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН П 9 15/33 ЕТЕНИ ля выполнен я алгоритмая в устройссигналов.ение устройль достигае быстроговах цифроель изобретва. Пося за счет преобразован вой обработк тения - упрставленная того ства входят реобразовай, М блоков оков умноженияем каждый проит три арифе мультипл ржки и г держки с ежду узл ычислиначено длярого преобоснованиюобработки иг ение устретения ль роиства.На фиг. 1 иная схема устроструктурная схеблока 1 на фиг.4блока умножения ения сод щитател умножии сумматурная схема бл нераторомУстройс модули 1. входы 21, соры 4.д,акт во со(1выход ство состои акто ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР ОПИСАНИ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР У 1348815, кл, С 06 Р 15/332, 1986,Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов.-М.: Мир, 1978, с. 674. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и предназначено Изобретение относится тельной технике и предна выполнения алгоритма быс разования Фурье (БПФ) по 4 в устройствах цифровой приведена структур ства; на фиг. 3 - а арифметическогоструктурная схема на фиг, 5 - струкка управления с геых импульсов.держит процессорные Г,М) информационные ы 3.1, мультиплекые входы 5,1, групп что в состав уст М(М = 1 одИ; И - разме ния) процессорных мод постоянной памяти, М б и блок управления, при цессорный модуль содер ме тич еских блока, ч еты сора, два элемента зад из четырех элементов з ветствующими связязми устройства. 5 ил. элементов 6.1 задержки, арифметические блоки 7,1. элементы 8.1, задержки, управляющие входы 9.1 и 10,1, блоки 11,1 постоянной памяти, блоки 12.1 умножения и адресные входы 13Арифметический блок образуют мультиплексоры 14 и 15, сумматоры-вычитатели 16 и 17, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 18. Блок умножтели 19-22,тор 24,Блок упратора 25 тактка 26, дешифрвыхода 28.РассмотримЯ =16 М леня состоит из гене вых импульсов, счетч атора 27 и тактового работу устроиства дляВ этом случае устрой из двух модулей 1 1 ил3 1508233 1,2. Допустим, изменения информации производятся положительным фронтом синхросигнала, вырабатываемым генератором 25 тактовых импульсов. Дискретные элементы 6.1 и 8,1 задержки содержат по четыре регистра. Дискретные элементы 6.2 и 8.2 задержки содержат по одному регистру. Счетчик 26 - двоичный, четырехразрядный, 1 О соединенный с двумя дешифраторами 27.В первые четыре такта на вход 2.1 устройства поступают входные отсчеты Х(10), Х(1), Х(2), Х(3). Состояния счетчика 26 последовательно из меняются от 0000 до 0011, На управ - ляющем входе 5.1 первого мультиплексора 4.1 находится верхний логический уровень, на остальных управляющих входах - нижний логический уро вень . При верхнем логическом уровне на управляющем входе 9,1 первый мультиплексор 4,1 производит прием информации со своего первого входа. Поэтому первые четыре отсчета последовательно записаны в первый элемент6.1 задержки.В следующие четыре такта на вход 2,1 устройства поступают отсчеты Х(4), Х(5), Х(6) и Х(7) . Состояния 30 счетчика 26 изменятся последовательно от 0100 до 0111. При этом верхний логический уРовень поступает на второй вход 5.1 с дешифратора 27, на остальных входах имеется нижний логический уровень. Первый мультиплексор 4.1 принимает информацию с второго входа. Поэтому первые четыре отсчета циклически сдвигаются в первом элементе 6.1 задержки. Вторая 40 четверка отсчетов заносится во второй элемент 6.1 задержки и поступает .на второй вход первого арифметического блока 7,1. На первый вход первого арифметического блока 7.1 поступают последовательно первые четыре отсчета. На управляющие входы 91 и 10.1 первого арифметического блока 7,1 поступают нижние логические уровни, что соответствует операции А + В, где А - операнд на первом входе, В - операнд на втором входе первого арифметического блока 7.1 . За четыре такта в первый элемент 8.1.задержки заносится четыре суммы: Х(0) + Х(4); Х(1) + Х(5), Х(2) + Х(6); Х(3) + Х(7).За третью четверку тактов на вход 2.1 поступают отсчеты Х(8), Х(9), Х(10) и Х (11). Состоянии счетчика 26 последовательно изменяются от 1000 до 1011, Верхний логический уровень присутствует на третьем входе 5.1. Входные отсчеты поступают в третий элемент 6.1 задержки. Отсчеты в первом и втором элементах 6,1 задержки циклически сдвигаются через соответствующие мультиплексоры 4.1. На первый управляющий вход 9.1 поступает верхний логический уровень, а на первый управляющий вход 10.1 - нижний логический уровень . Это соответствует операции А +В для первого арифметического блока 7.1. На вторые управляющие входы 9.1 и 10.1 . поступают нижние логические уровни. При этом второй арифметический блок 7.1 выполняет операцию (А+В)+С, где (А+В) - операнд, поступающий на первый вход, а С - операнд, поступающий на второй вход второго арифметического блока 7.1, В первый элемент 8.1, 1задержки записываются соответствующие значения: Х (О)+1 Х (4) 1 Х (1)+ +1 Х(5); Х(2)+1 Х(6); Х(3)+1 Х(7). Во второй элемент 8.1 задержки записываются значения: Х(0)+Х(4)+Х (8); Х(1)+Х (5)+Х(9), Х (2)+Х(6)+Х (10), Х (3)+Х (7)+Х(1 ) .В следующие четыре такта на вход 2.1 поступают значения Х(12), Х (13), Х(14) и Х(15), состояния счетчика 26 последовательно изменяются от 1100 до 1111. Верхний логический уровень поступает на четвертый вход 5.1, На другие входы 5.1 поступают нижние логические уровни. Входные отсчеты записываются в четвертый элемент задержки 6.1 и на второй вход третьего арифметического блока 7.1 . На йервые и вторые управляющие входы9.1 и 101 поступают верхние логические уровни. На третьи управляющие входы 9.1 и 10,1 поступают нижние логические уровни, первый арифметический блок 7.1 выполняет операцию А-В, второй арифметический блок 7.1 выполняет операцию (А+В)-С. Третий арифметический блок 7. выполняет операцию (А+В+С)+П; где (А+В+С) операнд, поступающий на первый вход третьего арифметического блока 7.1, а 0 - операнд, поступающий на второй вход третьего арифметического блока 7,1. В первый элемент 8,1 задержки записываются значения: Х(0)-Х(4), Х (1)-Х (5) , Х (2)-Х (6); Х(3)-Х (7) . Во5 150823второй элемент 8.1 задержки записываются значения Х(0)+1 Х(4)-Х(8)",Х (1)+Х (5)-Х (9) ", Х (2)+1 Х (6)-Х (10) ,Х(3)+1 Х(7)-Х (11). На выходе 3.1 последовательно появляются значенияХ(0)+Х (4)+Х (8) +Х (12) ф Х (1)+Х (5)++Х (9)+Х (13); Х (2)+Х (б)+Х (10)+Х (14);Х (3)+Х(7)+Х (11)+Х (15) . На второйвход блока 12.1 умножения поступаетзначение 11, , где М, = ехр(-12 ип/Б).На вход 2.2 модуля 1.2 поступают четыре первых результата первой итерации алгоритма БПФ,В следующую четверку тактов модуль 1.1 работает аналогично первойчетверке тактов. На вход 2.1 поступают первые четыре отсчета следующего входного массива. Состояния счетчика 26 последовательно изменяютсяот 0000 до 0011. Загрузка информации производится в первый элемент6,1 задержки. На первый вход 9,1 поступает нижний логический уровень,на первый вход 10,1 - верхний логический уровень. Первый арифметический блок 7.1 выполняет операциюАВ. В первый элемент задержки 8поступают значения: Х (0)-1 Х(4), Х (1)-Х(5)ф, Х(2)-1 Х(6), Х(3)-Х(7). Навторые управляющие входы 9,1 и 10.1поступают нижние логические уровни.Второй арифметический блок 7,1 выполняет операцию (А-В)+С. Во второйэлемент 8.1 задержки поступают значения: Х (О)-Х(4)+Х(8); Х (1)-Х(5)+Х (9) 35Х(2)-Х (6)+Х(10); Х(3) - Х(7)+Х (11). Натретий управляющий вход 9,1 поступает нижний логический уровень, натретий управляющий вход 10.1 - верх 40ний логический уровень. Третий арифметический блок выполняет операцию-Х (10)-1 К(14), Х (3)+1 Х (4)-Х (11)-,1 Х(15) которые поступают на первыйвход блока 12.1 умножения. На второйвход блока умножения поступает последовательность весовых коэффициенотов И,ь, Ч , И 1 ь, Иь . На вход2,2 второго модуля 1.2 поступаетвторая четверка результатов первойитерации алгоритма БНФ.В шестую четверку тактов первыймодуль 1.1 работает аналогично второму. На вторые и третьи управляющиевходы 9.1 и 10.1 поступают верхние 3 6логические уровни. При этом второй арифметический блок 7,1 выполняет операцию (АВ)-С, а третий арифметический блок 7.1 - (А-В+С)-0, Во второй элемент 8.1 задержки поступают значения: Х(0)-1 Х(4)-Х(8); Х(1)-Х (5)"Х(9), Х(2)-1 Х(6)-Х(10); Х(3)-1 Х(7)-Х (11). На выходе 3,1 присутствует последовательность значений: Х (О)-Х (4)+Х (8) -Х (12) , Х (1)- -Х (5)+Х(9)-Х (13); Х (2)-Х(6)+Х (10)- -Х (14); Х (3)-Х(7)+Х(11)-Х (15) . На второй вход блока умножения поступает последовательность значенийИ , на вход 2,2 второго модуля 1.2 - третья четверка результатов первой итерации.В седьмой четверке тактов элементы нового массива обрабатываются аналогично третьей четверке тактов, На третий управляющий вход 9,1 поступает нижний логический уровень, третий арифметический блок 7.1 выполняет операцию (АВ-с)+1 Р. На выход 3.1 поступают значения: Х(0)- -1 Х(4)-Х(8)+1 Х(12); Х (1)-1 Х (5)-Х (9)+ +1 Х (13) ф, Х (2)-1 Х(6)-Х (10)+1 Х(14); Х (3)-1 Х (7)-Х (11) -1 Х ,15) . На второй вход блока умножения поступают значения 11,ь, Ы 1 ь, 1 ьь, 1 ъ,ь . На вход 2,2 второго модуля ),2 поступают последние четыре результата первой итерации.Дальнейшая работа модуля 1,1 продолжается по описанному алгоритму.Рассмотрим работу второго модуля 1.2. Элементы 6.2 и 8.2 задержки содержат по одному регистру. На второй вход блока 12.2 умножения поступаетопостоянное значение Ы . Начнем расьсматривать работу модуля 1.2 с четвертой четверки тактов работы устройства.Двенадцатый такт. Состояние счетчика 26-1100. На входе 2.2 модуля присутствует значение У(0) = Х(0)+ +Х. (4)+Х (8) +Х (12), Верхний логический .уровень снимается с первого выхода дешифратора 27, соединенного с первым входом 5,2. Значение 1(О) через первый мультиплексор 4.2 поступает на вход первого элемента 6.2 задержки.Тринадцатый такт. Состояние счетчика 26-1101. На входе 2,2 имеется значение У(1) = Х(1)+Х (5)+Х(9)+Х (13) . Верхний логический уровень находится на втором входе 5.2. Значение У(1)55 поступает на вход второго элементазадержки 6.2. Значение У(0) черезпервый мультиплексор 4.2 поступаетснова на вход .первого элемента 6.2задержки. На первые управляющие входы 9,2 и 10.2 поступают нижние логические уровни. Первый арифметическийблок 7.2 выполняет операцию А+В. Наего выходе значение У(0) + 7(1),Четырнадцатый такт. На вход 2.2поступает значение У(2) = Х (2)+Х (6)++Х (10)+Х (14) . Состояние счетчика26-1110. Верхний логический уровеньпоступает на третий вход 5,2. На первый управляющий вход 9,2 поступаетверхний логический уровень. На первый управляющий вход 1 0,2 и вторыеуправляющие входы 9.2 и 10.2 поступают нижние логические уровни. Первый арифметический блок 7,2 выполняет операцию. А+1 В. На. его выходеприсутствует значение У(0)+17(1).Второй арифметический блок 7.2 выполняет операцию (А+В)+С. На его выходе имеется значение 7(0)+У(1)+7(2),Пятнадцатый такт, На входе 2.2находится значение У(3) = Х(3)+Х (7)++Х (11)+Х (15), Состояние счетчика 261111. Верхний логический уровеньпоступает на четвертый вход 5.2.Напервые и вторые уравляющие входы 9.2и 10.2 поступают верхние логическиеуровни, на третьи - нижние логическиеуровни. Первый арифметический блок7.2 выполняет операцию А-В. На еговыходе имеется значение У(0) -У(1),второй арифметический блок .2 выполняет операцию (А+1 В)-С. На еговыходе находится значение У(0)+17(1)-У(2), Третий арифметический блок7.2 выполняет операцию (А+В+С)+О. Наего выходе присутствует значениеУ(0)+У(1)+У(2)+7(3). На выходе блокаумножения 12.2 имеется значение Р(0),Последовательность смены управляющих сигналов на втором модуле 1.2происходит аналогично первому модулю1.1, но в четыре раза быстрее. По 1этому ее дальнейшая работа соответствует описанному алгоритму. С выхода блока 12.2 умножения снимаютсярезультаты БПФ Р(К) в четвертичноинверсном порядке,1 При описании работы устройства предполагалось, что блоки 12.х умножения не тактируются и не вносят задержку при работе, поскольку внут 10 15 20 25 30 35 40 45 ренние регистры в их схемах не меняют сущности работы устройства. Ф о р м у,л а и з о б р е т е н и я Устройство для вычисления быстрого преобразования Фурье, содержащее М (М = 1 ояИ, Н - размер преобразования) процессорных модулей, М блоков постоянной памяти и блок управления, причем инормационный вход первого процессорного модуля является информационным входом устройства, тактовые выходы -й группы (1. = 1,М) блока управления подключены к тактовым входам группы -го процессорного модуля,- й адресный выход блока управления подключен к адресному входу 1-го блока постоянной памяти, о т л и ч аю щ е е с я темчто, с целью упрощения устройства, оно содержит М блоков умножения, причем выход -го процессорного модуля подключен к первому входу -го блока умножения, второй вход которого подключен к выходу -го блока постоянной памяти, выходы группы которого подключены к управляющим входам группы 1.-го процессорного модуля, выход 1-го (1 = 1; М) блока умножения подключен к информационному входу Я+1)-го процессорного модуля, а выход М-го вычислительного модуЛя является информационным выходом устройства, при этом х-й процессорный модуль содержит три арифметических блока, четыре мультиплексора, два элемента задержки и группу из четырех элементов задержки, выход первого мультиплексора подключен к входу первого элемента задержки группы, выход которого подключен к первому информационному входу первого мультиплексора и первому информационному входу первого арифметического блока, выход которого подключен к входу первого элемента задержки, выходкоторого подключен к первому информационному входу второго арифметического блока, выход которого подключен к входу, второго элемента задержки,выход которого подключен к первомуинформационному входу третьего арифметического блока, выход которогоявляется выходом процессорного модуля,управляющими входами группы которогоявляются объединенные между собойпервые и вторые управляющие входыпервого, второго и третьего арифМтических блоков, выход 1-го (1 = 2,С)мультиплексора подключен к второмуинформационному входу (1-1)-го арифметического блока и входу 1-го элемента задержки группы, выход которого подключен к первому информационному входу 1-го мультиплексора,вторые информационные входы всехмультиплексоров соединены между собой и являются информационным входом процессорного модуля, тактовымвходом группы которого являются объединенные между собой управляющиевходы всех мультиплексоров, причемК-й (К = 1,3) арифметический блоксодержит два мультиплексора, два сумматора-вычитателя и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к управляющим входам первого ивторого мультиплексоров, выходы которых подключены к первым информационным входам соответственно первого и второго сумматоров-вычитателей,выходыкоторых объединены между собой и являются выходом арифметического блока, первым управляющим входом которого являются соединенные междусобой управляющий вход первого сумматора-вычитателя и первый вход элемента ИСКЛЮЧАЮШЗЕ ИЛИ, второй входкоторого соединен с управляющимвходом второго сумматора-вычитателяи является вторым управляющим входомарифметического блока, первым информационным входом которого являютсяобъединенные между собой вторые информационные входы первого и второгосумматоров -вычитателей, соединенныемежду собой первые информацчонныевходы первого и второго мультиплексоров объединены соединенными междусобой вторыми информационными входами первого и второго мультиплексорови образуют второй информационныйвход арифметического блока.1