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

(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств для быстрого преобразования Фурье в реальном масш табе времени. Известны устройства для выполнения быстрого преобразования Фурье (.БПФ), имеющие память операндов, память весовых коэффициентов, память результатов и комплексное арифметическое устройство. Данные во всех типах памяти - в виде очереди. Поток данных через арифметическое устройс во параллельный. В известных устройствах использованы громоздкие устройства для прео разования последовательного потока данных из памяти операндов в параллельный поток данных на вход арифмерического устройства и параплельног потока данных из арифметического устройства в последовательный поток данных на вход памяти результатов. Наиболее близким к Предлагаемому по технической сущности является специализированный процессор для БПФ, который содержит запоминающее устройство (ЗУ) операндов, ЗУ результатов, ЗУ весовых коэффициентов, которое выходом подключено ко входам (.) сдвиговых регистров весовых коэффициентов, которые выходами подключены к управляющим входам формирователей поразрядных произведений, к информационным входам которых подключены выходы ) первых регистров и которые входами подключены к первому уровню сумматоров группы последовательно соединенных (г/2+2} уровней комбинационных сумматоров, ко второму уровню которой дополнительно подключены выходы последних двух регистров и последний уровень которой подключен ко входам 2 сдвиговых регистров результатов, выходы

которых подключены ко входам последнего уровня сумматоров, где Г - основание алгоритма БПФ.

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

Цель изобретения - сокращение аппаратурных затрат.

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

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

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

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

5 регистров подключен ко вторым входам соответственно третьего и четвертого регистров, причем выходы четвертого и шестого сдвиговых регистров соединены соответственно со

вторыми входами соответственно первого и второго буферных регистров.

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

Устройство для БПФ состоит из блока 1 памяти операндов, блока 2 памяти результатов, блока 3 памяти коэффициентов, сдвиговых регистров 4, 5 и 6, умножителей 7-10, четырех регистров 11-14, десяти сумматоров 15-24, двух буферных регистров 25 и 26, сдвиговюс регистров 27, 28 и 29.

В блоке J памяти операндов операнды находятся в виде очереди типа

Г- г9 и Ил г Г «1 И

t/, Oi, Di, о а, о, 1.1, , oi,.., t с;, С, В, в| ... , где j - номер цикла выполнения базовой операции БПФ. В блоке 2 результатов результат должны поступать и храниться в виде очереди А,, А 1. Aj,, AJQ, ...

- 17

Из блока 3 коэффициентов весовые

коэффициенты W и W выдаиотся одновременно и хранятся тоже в виде очереди , V ...«/j,«vj. Так же, как и известное,предлагаемое устройство выполняет операции вида Л В + CW i AI В - GW; где А А(A +jAji, В ,-, С С.+ j , A - G2(/i+ А.я; С,1-ь + HI, AnS -(C-,Wi - ) BV, A,, .,) + BI. Эти действия устройство выполняет за один цикл базовой операции БПФ. Устройство работает по алгоритму с основанием «2. Все данные представлены в виде fl -разрядных двЬичных чисел с фиксированной запятой в параллельном коде. Элементы устройства соединены так, что умножитель 7 производит умножение С из регистра I1 на очередную цифру весового коэффициента MJ , которая поступает с выхода регистра 4 после (-1j сдвига содержимого этого регистра, умножитель 8 умножает из регистра 12 на очередную цифру Wn весового коэффициента Vi из регистра 5, умножитель 9 умножает С 2. на W-J4 и умножитель 10 умножает С/, на цифру Wii . Сумматор 15 производит действие. К Gv, , сумматор 16 производит действие Кл (/j,. Сумматор 17 производит действие , В, сумматор 18 производит действие В, сум матор 19 производит действие з , сумматор 20 производит действие a(2 ij -Kft-«-Bf., т.е. эти действия производятся только в последнем такте цикла вьтолнения базовой опера ции БПФ, а в первые (п-1) тактов а ,; .; ,2,...,n-1.Сумматоры 21 совместно с регистром 6, 22 совместно с 27, 23 ,совместно с 28 и 24 совместно с 29 произвбдят правый сдвиг и сложение ii-i 3 , а 2 , (,2 п) соответственно. Таким образом, через каждые п тактов в конце каждого цикла получения базовой операции БПФ в регистрах результатов оказываются результаты базовой операции А. 1(L А 2,1 и А . Устройство работает следующим образом. Блок 1 вьодает операнды через каждые - тактов. В блоке 2 записываются результаты каждые - тактов . Пуст тактов. В нулевом такте С из блок 8 4 1 заносится в регистр 25. В такте ( из блока 1 заносится в регистр 25, с пересылается в регистр 26, в этом такте G передается из регистра 25 в регистр 12, а G передается из регистра 26 в регистр II, из блока коэффициентов W и W заносятся в регистры 4 и 5 соответственно, т.е. подготовлены исходные данные для нулевого цикла базовой операции БПФ, и с этого момента эти данные начинают участвовать в вычислениях .результатов А, А , А. и А22. В такте (47) блока 1 заносится в регистр 25. В такте (-j-n- l) Bij заносится из блока 1 в регистр 25, а В пересылается в регистр 26. В такте()В пересылается из регистра 26 в регистр 13, а Б-пересылается из регистра 25 в регистр 26, в регистр 25 заносится новое с, для следующего ц)икла базовой операции БПФ. В такте/i-n 20) В пересыпается из регистра 13 в регистр 14, а Вл пересылается из регистра 26 в регистр 13, новое пересыпается из регистра 25 в регистр 26, в регистр 25 записывается новое С. В такте (т ). В и В„ участвуют в образовании результатов на сумматорах I720, т.е. на сумматоры регистры 13 и I4 выдают свое содержимое только в этом такте - последнем такте вычисления результатов А , . А .. В следующем такте {in+1 2l) резуль«О д0. таты Ajf , , А и пересылаются в регистры 14, 13, 26 и 25 соответственно. В такте () А из регистра 14 записывается в блок 2 результатов, А, из регистра 25 пересылается в регистр 26, ) из регистра 26 пересьшается в регистр 13, из регистра 13 пересылается в регистр 14, в . регистр 25 заносится новое.В. В такте ( ) аналогично в регистр 25 записывается новое Bj, из 25 в 26 переходит д| , из 26 в 13 переходит А(л, из .13 в 14 переходит Ал,), а пересылается в блок 2 результатов из регистра 14 операндов. В такте (In 32) новое BIJ переходит из 25 в 26, в1| переходит из 26 в 13, Aj переходит из 13 в 14, а Aft. из 14 пересылается в блок 2. Аналогично в такте i VI 3б) последний результат пересылается из 14 в блок 2, В переходит из 26 в 13, Bj переходит из 13 в 14 и т.д.Причем все результаты последующих циклов базовой операции БПФ записываются в блок результатов 2 при непрерывной выдаче операндов блоком 1 и весовых коэффициентов блоком 3, Таким образом, в i-ом такте в регистре 6 умножителях 7, 8 и 9 образуются результаты А. . j-ro цикла базовой операции БПФ у 5 ЛгЛ14г1 .в следующем такте они пересылаются в регистры 14,1 3,26 и 25 со ответственно. В такте (i+З) 14 пе.рёдается в блок 2, A.J. из регистра ,25 пересылается в 26, Ад из 26 пересылается в 13, . 3 пересылается в 1:-4, В 25 из блока 1 заносится новое . В такте ( f 4 j новое в| заносится в 25, Е пересылается из 25.в 26, Ai. пересылается из 26 в 13, А, пересьшается из 13 в 14, А, передается в блок 2. В такте 4 } H-f 1 ) новое поступает из блока I. в регистр 25, пересылается из 25 и 2,В-, пересылается из 26 в 13, А1 пересылается из 13 в 14, А- передается в блок 2 В такте (i n-f -t 5) новое С поступает в регистр 25, С-, передается из 25 в 26, пересылается из 26 в 13, Ъ пересьшается из 13 в 14, последний результат , j -го цикла базовой операции БПФ передается в блок 2. В такте {i + Пг --ffe) J 14. V, (+1 В , и В ; выдается из регистров 13 и 14 для (J+.) цикла базовой операции БПФ, в регистре 6 я умножителях 7, 8 и 9 оказываются результаты , Afi , и АИ . В следующем (i 4 пМ si4i) такте CY и передаются из буферных регистров 25 и 26, в регистры II и 12, весовые коэффициенты из блока 3 Wy и W i заносятся в регистры 4 и 5 и начинается (J + U.) цикл базовой операции БПФ. же такте результаты А А - , A,J и li заносятся в регистры 14, 13, 26 |й 7,5 /соответственно. В сравнении с аналогичными устройствами,у которых для преобразования пос ледовательного потока операндов в парал лельный и параллельного потока в последовательный необходимо 4) буферных регистра на входе и выходе арифметического устройства и коммутатор 2 г направлений, в предлагаемое устройств для зтих же целей дополнительно вводится только (2(-2) буферных регистра. Формула изобретения Устройство дпя вьтолнения быстрого преобразования Фурье, содержащее блок памяти операндов, блок памяти результатов, блок памяти коэффициентов, сдвиговые регистры, сумматоры, умножители и регистры причем выход блока памяти коэффициентов соединен со входами первого и второго сдвиговых регистров, выход первого регистра подключен к первым входам первого и второго умножителей, выход второго регистра соединен с первыми входами третьего и четвертого умножителей, выход первого сдвигового регистра подключен ко вторым входам первого и четвертого умножителей, а выход второго сдвигового регистра соединен со вторыми входами третьего и второго умножителей, выходы первого и третьего умножителей подключены соответственно к первому и второму входу первого сумматора, выход которого соединен с первыми входами второго и третьего сумматоров, выходы которых соединены с первыми входами соответственно четвертого и пятого сумматоров;. . выходы которых подключены ко входам соответственно третьего и четвертого сдвиговых регистров, выходы четвертого и второго умножителей соединены соответственно с первым и вторым входами шестого сумматора, вьГход которого соединен с первыми входами соответственно седьмого и восьмого сумматоров, выходы которых подключены к первым выходам соответственно девятого и десятого сумматоров, выходы которых соединены со входами соответственно пятого и шестого сдвиговых регистров, выходы которых соединены со вторыми входами соответственно девятого и десятого сумматоров, а выходы третьего и четвертого сдвиговых регистров соединены со вторыми входами соответственно четвертого и пятого сумматоров, первый выход третьего регистра подключен ко вторым входам седьмого и восьмого сумматоров, а первый выход четвертого регистра соединен со вторыми входами второго и третьего сумматоров, отличающееся тем, что, с целью сокращения аппаратурных затрат, оно содержит два буферных регистра, причем выход блока памяти операндов подключен к первому входу первого буферного регистра, первый выход которого соединен с первым

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

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