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

Союз СоввтсиикСоцианнстнчвсинаРвспубини ОП ИСАНИЕИЗОВРЕТЕН ИЯК АВТОРСНО МУ СВИДЕТВЛЬСТВУ оо 886005(5)М. Кл. 3/18-2 С 06 Г 15/ Гоеударстеапвй квинтет СССР ао делан ааебретеавЯ в аткрыткЯ(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГ ПРЕОБРАЗОВАНИЯ ФУРЬЕустройства в последовательный поток данных на вход памяти результатов,Наиболее близким к предлагаемому но технической сущности является специализированный процессор для БПФ, который содержит запоминающее устройство 1 ЗУ) операндов, ЗУ результатов, ЗУ весовых коэффициентов, которое выходом подключено ко входам 2-2) сдвиговых регистров весовых коэффициентов, которые выходами подключены к управляющим входам формирователей поразрядных произведений, к информационным входам которых подключены выходы 2 т -2) первых регистров и которые входами подключены к первому уровню сумматоров группы последовательно соединенных 1, /2+2) уровней комбинационных .сумматоров, ко второму уровню которой дополнительно подключены выходы последних двух регистров и последний уровень которой подключен ко входам 21 сдви- говых регистров результатов, выходы вычис ыть ис- пециабыстрогоьном масштвах использоства для преобьного потока ндов в парала вход арифме,параллельногоетического Изобретение относится клительной технике и может бпользовано при построениилизированных устройств дляпреобразования Фурье в реалтабе времени. Известны устройства для выполнения быстрого преобразования Фурье БПФ), имеющие память операндов, память весовых коэффициентов, памят результатов и комплексное арифметическое устройство. Данные во всех типах памяти - в виде очереди, Пото данных через арифметическое устройс во параллельный. В известных устрой ваны громоздкие устро разования последовател данных из памяти опер лельный поток данных рического устройства потока данных иэ ариф Е,Мадянова,А,Федотав .г Яий"инСтитут лисУМескойрев юкоторых подключены ко входам последнего уровня сумматоров, где г - основание алгоритма БПФ.Недостаток .указанного устройствазаключается в том, что во избежание использования преобразования последовательного потока операндов в параллельный и параллельного потока результатов н последовательный онсодержит 2 г ЗУ операндов и 2 ЗУ результатов, данные в которых находятся в виде очередей, те. характеризуется большими аппаратурными затратами.Цель изобретения - сокращение аппаратурных затрат.Поставленная цель достигается тем, что устройство, содержащее блок памяти операндов, блок памяти результатов, блок памяти коэффициентов, сдвигоные регистры, сумматоры, умно- жители и регистры, причем выход блока памяти коэффициентов соединен со входами первого и второго сдвиговых регистров, выход первого регистра подключен к первым входам первого и второго умножителей, выход второго регистра соединен с первыми входами третьего и четвертого умножителей, выход первого сднигоного регистра подключен ко вторым входам первого и4четвертого умножителей, а выход второго сднигового регистра соединен со вторыми входами третьего и второго умножителей, выходы первого и третье, го умножителей подключены соответственно к первому и второму входу первого сумматора, выход которого соединен с первыми входами второго и третьего сумматоров, выходы которых соединены с первыми входами соответственно четвертого и пятого сумматоров, выходы которых подключены ко входам соответственно третьего и четвертого сдвиговых регистров, выходы четвертого и второго умножителей соединены соответственно с первым и вторым входами шестого сумматора, выход которого соединен с первыми нходами соответственно седьмого и восьмого сумматоров, выходы которых подключены к первым выходам соответственно девятого и десятого сумматоров, выходы которых соединены со входами соответственно пятого и шестого сдвиговых регистров, выходы которых соединены со вторыми нходами соответственно девятого и десятого сумматоров, а выходы третьего и четвертогоЭ 5 40 В блоке 1 памяти операндон операнды находятся в виде очереди типаС, С, В, ВР, С 1, С, В 4,ВС, С, В, В, , где- номерцикла выполнения базовой операцииБПФ, В блоке 2 результатов результатыФдолжны потупатоь и храниться в вида0 0очеред А 1, А А А+ф Афф А 1 АИз блока 3 коэ ициентов весовыекоэффициенты М и щ выдаются одно временно.и хранятся тоже в виде очереди Н, % %,% . Так же, како ои известное, предлагаемое устройствовыполняет операции вида 5 1 О 15 20 25 ЭО сдвиговых регистров соединечы со вторыми входами соответственно четвертого и пятого сумматоров, первый выход третьего регистра подключен ко вторым входам седьмого и восьмого сумматоров, а первый вьгход четвертого регистра соединен со вторыми входами второго и третьего сумматоров, содержит два буферных регистра, причем выход блока памяти операндон подключен к первому входу первого буферного регистра, первый выход которого соединен с первым входом второго буферного регистра, первый выход которого соединен с первым входом третьего регистра, второй выход которого подключен к первому входу четвертого регистра, второй выход которого соединен со входом блока памяти результатов, вторые выходы первого и второго буферных регистров подключены ко входам соответственно первого и второго регистров, а выходы третьего и четвертого сдвиговых регистров подключены ко вторым нхо" дам соответственно третьего и четвертого регистров, причем выходы четвертого и шестого сдвиговых регистров соединены соответственно со вторыми входами соответственно первого и второго буферных регистров,На чертеже представлена блок-схема устройства для быстрого преобразования фурье при г 2. Устройство для БПФ состоит из блока 1 памяти операндов, блока 2 памяти результатов, блока 3 памяти коэффициентов, сдвиговых регистров 4, 5 и б, умножителей 7-10, четырех регистров 11-14, десяти сумматоров 5-24, двух буферных регистров 25 и 26, сдвиговых регистров 27, 28 и 29.886005 А= В+ С, А= В - С), АА 121 А 2.1 +1 А Щ;В 1+в, С,+ С 2, Ф+ Ю 2; где А=А) =ВСфа т.е. А)1 С 1%1 - С 2%2 + В 1,А= С,Ю 2+ СЯ/, + В); 1 ЕА 1= -(св 1 - сна) + в 1,А = -(сю+ Ср,) + в.Эти действия устройство выполняет за один цикл базовой операции БПФ.Устройство работает по алгоритмус основанием ьв 2. Все данные представлены в виде ю -разрядных двЬнчных чисел с фиксированной запятой впараллельном коде.Элементы устройства соединенытак, что умножитель 7 производит умножение С иэ регистра 11 на очередную цифру М/1 весового коэффициентаЩ 1, которая .поступает с выхода регистра 4 после (1-1) . сдвига содер- ужимого этого регистра, умножитель 8умножает из регистра 12 на очереднуюцифру %21 весового коэффициента Ф 2иэ регистра 5, умножитель 9 умножаетС 2 на Ю.) и умножитель 10 умножает-К,)+В 1, сумматор 20 производит действие а=-К+В, т,е. эти действияпроизводятся только в последнем и-омтакте цикла выполнения базовой опера Эции БПФ, а в первые (и) тактов а ,ИК 41 а 1 о 1 11 а 21) =-К 11 ац. 211 1,2п,Сумматоры 2 совместнос регистром 6, 22 совместно с 27, 23совместно 1 с 28 и 24 совместно с 29произвбдят правый сдвиг и сложениеРа 1. а )о), а 211, а 12; 1=1,2,,и) соответственно. Таким образом,через каждые и тактов в конце каждого цикла получения базовой операции З 4БПФ в регистрах результатов оказываются результаты базовой операции А.)1,А 1, А 1 и А 2,.Устройство работает следующим образом. ИБлок 1 выдает операнды через каждые ф тактов. В блоке 2 записываются результаты каждые - тактов. ПустьИ416 тактов. В нулевом такте С из блока/и иэ блока 1 заносится в регистр 25, С пересылается в регистр 26, в этом а1 отакте С 2 передается из регистра 25 в регистр )2, а С передается из регистора 26 в регистр 11, из блока коэффициентов Фи Ю заносятся в регистры 4 ио о5 соответственно, т.е. подготовлены исходные данные для нулевого цикла базовой операции БПФ, и с этого момента эти данные начинают участвовать в вычислениях, результатов А, А)2, А 2ои А еВ такте - =8) Во из блока 1 эанооснтся в регистр 25. В такте- и=Щ4 Во заносится из блока 1 в регистр 25,оа В пересылается в регистр 26, В такте(и=16) В.) пересылается иэ ре-0гистра 26 в регистр 13, а В пересыО лается из регистра 25 в регйстр 26, в регистр 25 заносится новое С для следующего цикла базовой операции БПФ. В такте( - И =20) В 1 пересылает 7ося иэ регистра )3 в регистр 14, а оВ 2 пересылается иэ регистра 26 в регистр 13, новое С пересылается из регистра 25 в регистр 26, в регистр 2 записывается новое С. В такте ( и=20), В и В участвуют в образоо1вании результатов на сумматорах 17- 20, т.ена сумматоры регистры ) 3 и 4 выдают свое содержимое только в этом такте - последнем такте вычисления результатов А 11, А 2, А 2)А 22оО В следующем такте (Л. и+121) резульо о о д отаты А. А, А 1 и А пересылаются в регистры 14, 13, 26 и 25 соответственно.В такте (п 24) А 1 иэ регистра3 о14 записывается в блок 2 результатов, А 2 из регистра 25 пересылается в орегистр 26, А 2,) из регистра 26 переОсылается в регистр 13, А 1 из регистра 13 пересылается в регистр )4, в,1 регистр 25 заносится новое.в 1, В такте ( и=28) аналогично в регистр 254записывается новое В, иэ 25 в 26 пе 1 ореходит В 1, из 26 в 13 переходит А,о о из 13 в 14 переходит А 21, а А 2 пересылается в блок 2 результатов из регистра 14 операндов. В такте (2.П=32) новое В переходит иэ 25 в 26, В 1 переходит из 26 в 13, А 2 перехоо дит из 13 в 14, а А 2 из 14 пересыла 0ется в блок 2. Аналогично в такте)1 =36) последний результат А 2 пересылается из 14 в блок 2, В" переходит из 26 в 13, В переходит из 139 в 14 и т,д.)1 ричем все результаты последующих циклон базовой операции БПФ886005 7записываются в блок результатов 2 при непрерывной выдаче операндов блоком 1 и весовых коэффициентов блоком 3.5Таким образом, в-ом такте в регистре 6 умножителях 7, 8 и 9о о образуются результаты А+ рА,А, рА 1-го цикла базовой операции БПФ"4,В следующем такте они Енпересылаются в регистры 14, 13,26 и 25 со ответственно. В такте ( +3) Аиз 14 пеФредается в блок 2, А из регистра ,25 пересылается в 26, Аиэ 26 пересылается в 13, А из 13 пересыла Ф ется в 1 г 4. В 25 из блока 1 заносится новое В ф" . В такте (Ф) новое В заносится в 25, В пересылается из 25 в 26, А пересылается из 26 в 13, А 2 пересйлается иэ 13 в 3 ф 14, А передается в блок 2. В такте 1 аи 1 а м) новое Са поступает из блока 1. в регистр 25, Впересылается из 25 и 26,В 1 " пересылается из 26 в 13, А 1 пересылается вв из 13 в 14, А, передается в блок 2. В такте (1 фл- =1 т 5) новое Сй поступает в регистр 25, С передается из 25 в 26, Вф" пересылается из 26 в 13, Вф" пересылается из 13 у 4 в 14, последний результат,-го цикла базовой операции БПФ Апередается в блок 2. В такте (1й: 1Ь) В 1 и В 1 выдается иэ регистров 3 и 14 для (ф,) цикла базовой операции БПФ, в регистре 6 и умножителях 7, 8 и 9 оказываются результаты дующем (11+ =1 4 Ц такте с фф1 2.1 и Ста передаются нз буферных ре 4 Ф гистров 25 и 26, в регистры 1 и 12, весовые коэффициенты иэ блока 3 Ф 1 и Й а заносятся в регистры 4 и 5 и начинается (Ф 1) цикл базовой операции БПФ, В этом же такте результаты А , , А 12 , А б иб 13+1 43 АЯ заносятся в регистры 14, 13, 26 ,и 25,соответственно. В сравнении с аналогичными устрой-, ствами,у которых для преобразования пос- уф ледовательного потока операндов в парал- лельный и параллельного потока в последовательный необходимо 4 буферных регистра на входе и выходе арифметического устройства и коммутатор 2 г направлений, в предлагаемое устройство для этих же целей дополнительно вводится только (21-2) буферных регистра. 8Формула изобретенияУстройство для выполнения быстрого преобразования Фурье, содержащее .блок памяти операндов, блок памяти результатов, блок памяти коэффициентов, сдвиговые региотрыв сумматоры,Фумножители и регистры, причем выход блока памяти коэффициентов соединен со входами первого и второго сдвиговых регистров, выход первого регистра подключен к первым входам первого и второго умножителей, выход второго регистра соединен с первыми входами третьего и четвертого умножителей, выход первого сдвигового регистра подключен ко вторым входам первого и четвертого умножителей, а выход второго сдвигового регистра соединен со вторыми входами третьего и второго умножителей, выходы первого и третьего умножителей подключены соответственно к первому и второму входу первого сумматора, выход которого соединен с первыми входами второго и третьего сумматоров, выходы которых соединены с первыми входами соответственно четвертого и пятого сумматоров, выходы которых подключены ко входам соответственно третьего и четвертого сдвиговых регистров, выходы четвертого и второго умножителей соединены соответственно с первым и вторым входами шестого сумматора, выход которого соединен с первыми входами соответственно седьмого и восьмого сумматоров, выходы которых подключены к первым выходам соответственно девятого и десятого сумматоров, выходы которых соединены со входами соответственно пятого и шестого сдвиговых регистров, выходы которых соединены со вторыми входами соответственно девятого и десятого сумматоров, а выходы третьего и четвертого сдвиговых регистров соединены со вторыми входами соответственно четвертого и пятого сумматоров, первый выход третьего регистра подключен ко вторым входам седьмого и восьмого сумматоровра первый выход четвертого регистра соединен со вторыми входами второго и третьего сумматоров, отличающееся тем, что, с целью сокращения аппаратурных затрат, оно содержит два буферных регистра, причем выход блока памятиоперандов подключен к первому входупервого буферного регистра, первыйвыход которого соединен с первым886005 Заказ 10560/78 . Тираж 748 сно И лиал ППП "Патент", г, Ужг ул Проектная входом второго буферного регистра,первый выход которого соединен спервым входом третьего регистра,второй выход которого подключен кпервому входу четвертого регистра,второй выход которого соединен совходом блока памяти результатов, вто.рые выходы первого и второго буферных регистров подключены ко входам 0соответственно первого и второго ре гистров, а выходы третьего и четвертого сдвиговых регистров подключены ко вторым входам соответственно тре- Э тьего и четвертого регистров, причемвыходы четвертого и шестого сдвиговых регистров соединены соответствен-.но со вторыми входами соответственно первого и второго буферных регистров.