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

 

Союз Соввтсиик

Социапистичвсиик

Рвспубпии

ОП ИСАНИ Е

ИЗОВРЕТЕН ИЯ

К АВТОРСНО МУ СВИДЕТИЛЬСТВУ 886005 (61) Дополнительное к авт. свиа-ву— (22) Заявлено 26. 12. 79(2! ) 2860043/18-24 с присоелинеиием заявки М— (23) Приоритет— (51)М. Кл.

С 06 F 15/332

Гвсудврствапвб квинтет

СССР

h0 делан язабрвтеввй в вткрытвЯ

Опубликовано 30.11. 81. Бюллетень Рй 44

Дата опубликования описания 30,1 1.81 (53) УДК 681.323. (088.8) (72) Авторы изобретения

Ю .Н .Виноградов, Ю.С .Каневский, Н.E ..Иадянова, Б.А,Некрасов, А.М.Сергиенко и О.А.Федотав. г"

I

Киевский ордена Ленина политехнич 1еий" инСтитут им. 50-летия Великой Октябрь ской с алисУй11еской дев юции (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

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

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

2 устройства в последовательный поток

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

S специализированный процессор для

БПФ, который содержит запоминающее устройство (ЗУ/ операндов, ЗУ результатов, ЗУ весовых коэффициентов, которое выходом подключено ко входам (.2r-2) сдвиговых регистров весовых коэффициентов, которые выходами подключены к управляющим входам формирователей поразрядных произведений, к информационным входам которых под!

5 ключены выходы (2т -2) первых регистров и которые входами подключены к первому уровню сумматоров группы последовательно соединенных (,r /2+2) уровней комбинационных .сумматоров, ко второму уровню которой дополнительно подключены выходы последних двух регистров и последний уровень которой подключен ко входам 21 сдви- говых регистров результатов, выходы

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

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

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

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

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

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

С„, Cf, В4, Bg,, С1, С, В4,В, ° . e y

С, С, В, В(, ..., где j — номер цикла выполнения базовой операции

БПФ. В блоке 2 результатов результаты

Ф должны поступать и храниться в вида

0 0 очереди А 1, А10 А „, А, А,У е Афю A 41 А в ° °

Из блока 3 коэ ициентов весовые коэффициенты 41и выдаются одно55 временно и хранятся тоже в виде очереди Н„, % ...Ot,% . Так же, как

n o и известное, предлагаемое устройство выполняет операции вида

2S

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

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

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

886005

А„= В+ C „

А = В-С, A1q+) Aq

A +) А щ, В„+/Вй, C +)C !!/„+ ) Ф/ ; где А„=

А =

В

С ф» т.е. А1, с1%1 — се%2 + В1, А!1 Cq М/2 + С Я/! + В, <4

А 1= -(C<% — CgCg) + В1, A<<= -(C„e<+ gW,) +

Эти действия устройство выполняет за один цикл базовой операции БПФ.

Устройство работает по алгоритму с основанием ь»2. Все данные представлены в виде ф -разрядных двЬнчных чисел с фиксированной запятой в параллельном коде.

Элементы устройства соединены так, что умножитель 7 производит умножение С„ иэ регистра Il на очередную цифру М/„„ весового коэффициента

Щ,1, которая .поступает с выхода регистра 4 после (1-1) . сдвига содер- ру жимого этого регистра, умножитель 8 умножает из регистра 12 на очередную цифру 3(/щ весового коэффициента 4 иэ регистра 5, умножитель 9 умножает

С0 íà Nq) и умножитель 10 умножает З ,Сq на цифру %g1. Сумматор 15 производит действие. К =С.1%1„ -С 2Ж21, сумматор 16 производит действие К =

С1 II/gq+Cg%11. Сумматор 17 производит действие а!! K + B„, сумматор производит действие а1 „=К » В

)3 матор 19 производит действие а 21„=

-К +В.1, сумматор 20 производит действие а „=-К +В, т.е. эти действия производятся только в последнем и-ом такте цикла выполнения базовой опера° Э ции БПФ, а в первые (n-1) тактов а, Ил

К4! а !11 1 а 21! =-К11 а0о! 21

i t,2,...,n-1.Сумматоры 2! совместно с регистром 6, 22 совместно с 27, 23 совместно с 28 и 24 совместно с 29 произвбдят правый сдвиг и сложение

/ в1!1 а 1! а 21! а 12! (1=1 2, ° и) соответственно. Таким образом, через каждые и тактов в конце каждого цикла получения базовой операции 4

БПФ в регистрах результатов оказываются результаты базовой операции А.1,, А1, А 1и А2,.

Устройство работает следующим ооразом. И

Блок 1 выдает операнды через каждые ф тактов. В блоке 2 записываются результаты каждые — тактов. Пусть

И

4. 16 тактов. В нулевом такте С из блока

Ф ! заносится в регистр 25. В такте I =-4) С2 Yl иэ блока 1 заносится в регистр 25, С пересылается в регистр 26, в этом а

1 о такте С передается иэ регистра 25 в регистр !2, а С„ передается из регисто ра 26 в регистр 11, из блока коэффициентов Ф и Ф заносятся в регистры 4 и о о

5 соответственно, т. е. подготовлены исходные данные для нулевого цикла базовой операции БПФ, и с этого момента эти данные начинают участвовать в вычислениях, результатов А „, А/2, А2 о

И Афф е

В такте -=8) Во из блока 1 заносится в регистр 25. В такте (— и»Щ

Во заносится из блока l в регистр 25, 0 а В1 пересылается в регистр 26. В такте (n=l6) В пересылается иэ ре-

0 гистра 26 в регистр 13, à B пересыО лается из регистра 25 в регйстр 26, в регистр 25 заносится новое С„ для следующего цикла базовой операции

БПФ. В такте(— И =.20) В! пересылает/е 5 ъ 0 (4 ся иэ регистра 13 в регистр 14, а

В2 пересылается иэ регистра 26 в регистр 13, новое С пересылается из

1 регистра 25 в регистр 26, в регистр

2j. Записывается новое C). В такте (и=20), В и Б участвуют в образо0

2 вании результатов на сумматорах 1720, т.е..на сумматоры регистры 3 и !

4 выдают свое содержимое только в этом такте — последнем такте вычисления результатов A«, A«, АО„,А .

0 0

В следующем такте (Л п+1 21) реэуль0 0 о 4. 0 таты А,, А1, А и А пересылаются в регистры 14 13, 26 и 25 соответственно.

В такте (+n24) А„ иэ регистра

3 0

14 записывается в блок 2 результатов, А из регистра 25 пересылается в о регистр 26, А0 из регистра 26 переО сылается в регистр 13, А1 из регистра 13 пересылается в регистр 14, в, 1 регистр 25 заносится новое. В . В такте (и=28) аналогично в регистр 25

4 записывается новое В, иэ 25 в 26 пе1 ореходит В, из 26 в 13 переходит А, 0 о из .13 в 14 переходит А21, à А о пересылается в блок 2 результатов из регистра 14 Операндов. В такте 1,2.!!

=32) новое В0 переходит иэ 25 в 26, В переходит из 26 в 13, А0 перехо1 0 дит из 13 в 14, à А> из 14 пересыла0 ется в блок 2. Аналогично в такте Л =36) последний результат А пересылается из 14 в блок 2, В" переходит из 26 в 13, В„ переходит из 13

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

886005

7 записываются в блок результатов 2 при непрерывной выдаче операндов блоком 1 и весовых коэффициентов блоком 3.

° 5

Таким образом, в 1 -ом такте в регистре 6 умножителях 7, 8 и 9 о о образуются результаты A11,A„,А(„рА

j-го цикла базовой операции БПФ (1 - / 4-1 ) B следующем такте они уО н пересылаются в регистры 14, 13,26 и 25 со. ответственно. В такте (1+3) А„„из 14 пе4 редается в блок 2, А из регистра ,25 пересылается в 26, А < иэ 26 пересылается в 13, А из 13 пересыла- М ется в 1г4. В 25 из блока l заносится новое B »" . В такте ((4) новое

I 1

В заносится в 25, В пересылается из 25 в 26, А пересылается из

26 в-.13, А 2„ пересйлается иэ 13 в 50

14, А передается в блок 2. В такте (а 1 z-Ô= 1 а м) новое б а поступает из блока 1. в регистр 25, Во пересылается из 25 и 26у В1" пересы (,. лается из 26 в 13, А j пересылается ВВ из 13 в 14, А .1 передается в блок 2.

В такте {1+n-<= + 15) новое С

Э+2 поступает в регистр 25, С„ передается из 25 в 26, В " пересылается из 26 в 13, B) " пересылается из 13 в 14, последний результат, ) -го цикла базовой операции БПФ А передается в блок 2. В такте {1 + й= 1 1Ь)

В 1 и В 1 выдается иэ регистров

13 и 14 для (jt<) цикла базовой операции БПФ, в регистре 6 и умножителях 7, 8 и 9 оказываются результаты дующем (1 4 11+1 =1 4 1Ц такте С

1 2.

-1 и СЗ Н передаются нз буферных ре 40 гистров 25 и 26, в регистры 1! и 12, )4 весовые коэффициенты иэ блока 3 Ф 1 и N $ заносятся в регистры 4 и 5 и начинается () Ф1) цикл базовой операции БПФ. В этом же такте результаты А „,, А „, А . и

A<1 45

АЯ заносятся в регистры 114, 13, 26 ,и 25 соответственно.

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

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

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

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

ВНИИПИ Заказ 10560/78 Тираж 748 Подписное

Филиал ППП "Патент", г, Ужгород, ул. Проектная, 4