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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскимиСоциалистическикРеспублик иц 972517(23) ПриоритетОпубликовано 071182, Бюллетень Йо 41Дата опубликования описания 071182 Р 1 М Кл, 6 06 Г 15/332 Государствеииый комитет СССР ио делам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к автоматике:и вычислительной технике и может быть использовано в аппарате, осуществляющем спектральную обработку электрических сигналов в реальном масштабе времени.Известно устройстводля выполнения быстрого преобразования Фурье, содержащее четыре сумматора, три множительных блока, два сумматора-вычитателя, четыре регистра 1.Недостатком устройства является большое количество оборудования, так как для выполнения каждой арифметической операции оно содержит отдельный блок. Наиболее близким техническим решением к изобретению является устройство для выполнения быстрого преобразования Фурьесодержащее шесть , входных регистров, блок управления, коммутатор, сумматор, два регистра суммы, коммутатор сомножителей, блок умножения, четыре регистра произве-. дений2 .Недостатком известного устройства является низкое быстродействие, поскольку в нем последовательно выполняются четыре операции умножения. Целью изобретения является повышение быстродействия устройства.Поставленная .цель достигаетсятем, что устройство для выполнения быстрого преобразования Фурье, содержащее шесть входных регистров, входы которых являются информационныьк входами устройства, блок управления, первый коммутатор, первый сумматор, первый и второй регистры суммы, причем выходы первого и второго входных регистров подключены соответственно к первому и второму информационным входам первого коммутатора, управляющий вход первого коммутатора слагаемых подключен к первому выходу блока управления, выход первого коммутатора слагаемых подключен к первому входу первого сумматора, выход которого подключен к входам первого и второго регистров суммы, содержит второй, третий, четвертый и пятый коммутаторы, второй сумматор, третий, четвертый, пятый и шестой 25 регистры суммы, квадратор, причемвыход второго входного регистраподключен к первому информационному .входу второго коммутатора и первому информационному входу пятого комму- ЗО татора, выход третьего входного ре 972517Гистра подключен к первым информационным входам третьего и четвертого коммутаторов, выход четвертоговходного регистра подключен к третьему информационному входу первогокоммутатора и вторым информационным 5входам второго и пятого коммутаторов,выход пятого входного регистра подключен к вторым информационным входам третьего и четвертого коммутаторов, выход шестого входного регист ра подключен к третьему информационному входу второго коммутатора,выход третьего коммутатора подключенк второму входу первого сумматора,выходы второго и четвертого коммутаторов подключены соответственно кпервому и второму входам второго сумматора, выход первого сумматора подключен к входу третьего регистрасуммы, выход второго сумматора подключен к входам четвертого, пятогоишестого регистров суммы,.выходпервого регистра суммы подключен ктретьим информационным входам четвертого и пятого коммутаторов, выходвторого регистра суммы подключен ктретьему информационному входу третьего коммутатора, выход третьегорегистра суммы подключен к четвертым информационным входам первого ипятого коммутаторов, выхоц четвертого 30регистра суммы подключен к пятомуийформационному входу первого коммутагора и к четвертому информационному входу четвертого коммутатора,выход пятого регистра суммы подключен 35к пятым информационным входам четвертого и пятого коммутаторов, выходшестого регистра суммы подключен кшестым информационным входам первогоИ ПЯТОВО КОММУтаТОРОВв ВЫХОД ПЯТОГО 40коммутатора подключен к входу квадратора, выход которого подключен кчетвертым информационным входам второго и третьего коммутаторов, второй,третий, четвертый и пятый выходы бло ка управления подключены к управляющим входам второго, третьего, четвертого и пятого коммутаторов соответственно, выходы первого, третьего,четвертого и шестого регистров суммыявляются информационными выходамиустройства,Кроке того, блок управления состоит из счетчика и дешифратора,причем счетный вход счетчика являетсятактовым входом устройства, выход 55счетчика подключен к входу дешифратора, выходы дешифратора являютсявыходами блока управления.На фиг. 1 представлена функциональная схема устройства для выпол Онения быстрого преобразования Фурье;на фиг. 2 - функциональная схемаблока управления.устройство содержит входные регистры 1-6, входы 7-12 которых явля ются информационными входами устройства, блок 13 управления, коммутатор 14, квадратор 15, коммутаторы16-19, сумматоры 20 и 21, регистрысуммы 22-27, выходы 28-31 которыхявляются информационными выходамиустройства.Блок управления 13 состоит иэсчетчика 32, дешифратора 33, причемсчетный вход 34 счетчика являетсятактовым входом устройства.В устройстве выполняются следующиеоперацииВ,А =В Р +й1 д =1 А+1Ве В=йе ДВ=1 в,д -1,где А - первое комплексное число;В - второе комплексное число.1Величины Й и 1 определяются поизвестным формулам=В В 1 + 1 В Ве 1,27 Ггде И=ехр(-1 - ), М - объем выборки.Величины В и 1 с учетом того,что (ВЕИ)+1 У)д =1,а также того,что произведение двух чисел А и Вможно представить в видеРВ = . (А+В) -А -В , находятся в1 Я. д 2.соответствии с формуламив- ввв;+вр)(3 в,-в и)-- ,КеВ, Э В="еф фяеЦ -- 1 е 35 - Этьен -1Квадратор 15 представляет собойтабличную памяТь, В каждой ячейкепамяти хранится половина квадратачисла, являющегося адресом ячейки.Длительность такта .определяетсясуммарным временем обращения к квадратору, временем суммирования и временем задержки сигналов на коммутаторе 14 и одном из коммутаторов16-19В первом такте работы устройствав регистры 1-6 записываются исходныеДанные ВеД в ВЕЧ, ВЕЬ1 юВ) в 1 м"1 А.соответственно. Во втором тактепо адресу Ве В из квадратора 15извлекается число(В В ), котороечерез коммутатор 18 слагаемых подается на сумматор 21. Одновременночерез коммутаторы 16, 17 и 19 на сумматор 20 подаются слагаемые йеВ иВВИ, а на сумматор 21 - постояннаявеличина 0,5. Результаты суммирования поступают в регистры суммы 23и 27 соответственно.51015 20 25 30 где с,35 40 формула изобретения 45 50 55 вому входу первого сумматора, выход которого подключен к входам первого 60 и второго регистров суммы, о т л и жит второй, третий, четвертый и пятый коммутаторы, второй сумматор,65 .третий, четвертый, пятый и шестой В третьем такте в квадраторе 15по поступающему с регистра суммы 23адресу определяется число (ВЕ В +В 1)которое затем насумматоре 21 складывается с поступающим через коммутатор 19 с регистра суммы.27 эначеГ 1 .нием -(КЕВ ) +0,5. Полученнаясумма записывается в регистр суммы 26, Одновременно на сумматоре 20определяется разность чисел 1,В) и111, поступающих с входных регист ров 4 и 5 через коммутаторы 16 и 17,и записывается в регистр .суммы 22.В течение четвертого такта изсодержимого регистра суммы 26 на сумматоре 21 вычитается определяемоев квадраторе 15 число (1 В ) . ОдЯновременно на сумматоре 20 это жечисло суммируется с содержимым регистра суммы 27. Полученные значения записываются в регистры суммы23 и 25.В пятом такте работы устройствапо содержимому регистра суммы 22в квадраторе 15 определяется число(11 В - 1,Ч), которое затем на сумматоре 20 складывается с содержимымрегистра суммы 23, Результат (величина К) записывается в регистр суммы 24. Одновременно через коммутаторы 18 и 19 на сумматор 21 посту- .пают значения ЙЕ Вл и 1 У, результатсуммирования записывается в регистрсуммы 27.В шестом такте по содержимомурегистра 27 в квадраторе 15 определяется число (ВЕ В +1,И) , котороезатем на сумматоре 20 складываетсяс поступающим через коммутатор 16содержимым регистра 25, взятым собратным знаком. Результат записывается в регистр 22, Одновременнос этим через коммутаторы 18 и 19на сумматор 21 поступают значения1 щВ и ВВЧ с входных регистров 4 и 2.Результат суммирования записываетсяв регистр 26.В седьмом такте формируется первый конечный результат вычисленийВА+л. Для этого на сумматоре 20складываются содержимое входного регистра 1 и регистра суммы 24, Конечный результат записывается в регистр23. Одновременно с этим по содержимому регистра 26 в квадраторе 15находится значение (1 В +Вей), поступающее затем на суматор 21, гдескладывается споступающим черезкоммутатор 19 содержимым регистра 22.Полученный результат (величина 1),записывается в регистр 27,В течение следующего такта на сумматор 20 через коммутаторы 16 и 17поступают соответственно содержимоевходного регистра 1(величина ЙЕА )и содержимое регистра 24 (величина К),взятое с обратным знаком. На сумматор 21 через коммутаторы 18 и 19 поступают содержимое входного регистра б (величинаА ) и содержимое регистра 27 (величина ). Таким образом, формируются конечные результаты йбВ л и 1,пА, которые записываются в регистры суммы 22 и 25 соответственно.В девятом такте работы устройства на сумматоре 21 складываются содержимое входного регистра б (1 щА ) и содержимое регистра 27 (1), взятое с обратным знаком. Полученное значениеВ л записывается в регистр 26.Технический эффект от использования устройства заключается в повышении быстродействия.Базовая операция быстрого преобразования фурье в известном устройстве выполняется эа 8 тактов, причем длительность такта равна длительностиоперации умножения двух действительных чисел. Базовая операция быстрого преобразования Фурье в данномустройстве выполняется за 9 тактов,причем длительность такта равна длительности операции сложения (иливычитания). Выигрыш в быстродействии Н определяется иэ выражения 8. йум= -, - 1,севремя выполнения операции .умножения над действительными числами;время выполнения операциисложения (или вычитания)над действительными числами,1. Устройство для выполнения быстрого преобразования:Фурье, содержащее шесть входных регистров, входы которых являются информационными входами устройства, блок управления, первый коммутатор, первый сумматор, первый и второй регистры суюлы, причем выходы первого и второго входных регистров подключены соответст венно к первому и второму информационным входам первого коммутатора, управляющий вход первого коммутатора слагаемых подключен к первому выходу блока управления, выход первого коммутатора слагаемых подключен к перчающ,ееся тем, что, с цельюйовыаения быстродействия, оно содер 972517регистры суммы, квадратор, причем выход второго входного регистра подключен к первому информационному входу второго коммутатора и первому информационному входу пятого коммутатора, выход третьего входного регистра подключен к первым информационным входам третьего и четвертого коммутатора, выход четвертого входного регистра подключен к третьему информационному входу первого коммутатора и вторым информационным вхо дам второго и пятого коммутаторов, выход пятого входного регистра подключен к вторым информационным входам третьего и четвертого комму татаров, выход шестого входного регистра подключен к третьему информационному входу второго коммутатора, выход третьего коммутатора подключен к второму входу первого сумматора, 29 выходы второго и четвертого коммутаторов подключены соответственно к первому и второму входам второго сумматора, выход первого сумматора подключен к входу третьего регистра 25 суммы, выМод второго сумматора подключен к входам четвертого, пятого и шестого регистров суммы, выход первого регистра суммы подключен к третьим информационным входам четвертого и пятого коммутаторов, выход второго регистра суммИ подключен к третьему информационному входу третьего коммутатора, выход третьего регистра суммы подключен к четвертым информационным входам первого и пятого коммутаторов, выход четвертого регистра суммы подключен к пятомуинформационному входу первого коммутатора и к четвертому информационному входу четвертого коммутатора,выход пятого регистра суммы подключен к пятым информационным входамчетвертого и пятого коммутаторов,выход шестого регистра суммы подключен к шестым информационным входам первого и пятого коммутаторов,выход пятого коммутатора подключенк входу квадратора, выход которогоподключен к четвертым информационным входам второго и третьего коммутаторов, второй, третий, четвертый и пятый выходы блока управленияподключены к управляющим входамвторого, третьего, четвертого и пятого коммутаторов соответственно,выходы первого, третьего, четвертогои шестого регистров суммы являютсяинформационными выходами устройства.2, Устройство по п.1, о т л и -ч а ю щ е е с я тем, что блок управления состоит из счетчика и дешифратора, причем счетный вход счетчикафявляется тактовым входом устройства, выход счетчика подключен к.входу дешифратора, выходы дешнфратора являются выходами блока управления.Источники информации,принятые во внимание при экснертиэе1. Авторакое свидетельство СССРУ б 56070, кл, 6 Об Г 15/332, 1979;2. Авторское свидетельство СССРУ 598085, кл. О Об Г 15/332, 1979972517 НИИПИ Заказ 8518/41 ираж 731 Подписное илиал ППП "Патент", .Ужгород, ул.Проектная,4