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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 09 6 Р 1533 ПИСАНИЕ ИЗОБРЕТЕНИ 110/24-24 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Институт технической кибернетики АН БССР(56) Патент Франции Ф 2092030, кл. С 06 Р 15/00, 1975.Авторское свидетельство СССР У 660057, кл. О 06 Р 15/332, 1979. (54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ДЕЙСТВИТЕЛЬНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники и предназначе но для использования в аппаратуре, осуществляющей спектральный анализ сигналов, представленных цифровыми последовательностями. Цель изобретения - повышение быстродействия, Поставленная цель достигается тем, что в состав устройства входят коммутатор 1, блок 2 синхронизации, К сумматоров 3 (И - размер преобразования), И регистров 4, (Х/2- 1) умножителей 5, блок 6 постоянной памяти коэффициентов и соответствующие связи между блоками устройства. Коды подключения поступают на коммутатор 1 иэ блока 2 синхронизации, который задает набор признаков суммирования или вычитания на сумматоры 3 и новые значения весовых коэффициентов, подаваемые на умножители 5 из блока 6 пою стоянной памяти. Результаты вычисле- Я ний фиксируются в регистрах 4, откуда передаются на выходы устройства и считываются с них для дальнейшейобработки. 2 ил.Изобретегггге относится к вичислительной технике и предггдзцачецо для использования в аппаратуре, осуществляющей спектральный анализ сигцдлов, представленных цифровыми последова тельностями.Цель изобретения - повышение быстродействия устройства за счет реализации в цем нового алгоритма быстрого действгп ельцого преобрдзоваггия1 О Фурье.На Фиг.1 представлена Функциональная схема устройства, цд фиг,2 - граф алгоритма быстрого действительного преобразования Фурье, реализованцый в устройстве (для размерности К=16).Устройство содержит коммутатор 1, блоксицхроцг,здции, Х сумматоров 3, И регистров 4, (Г - 2) /2 умггожите - лей 5 и блок 6 постоянной памяти коэффициеггтов.Устройство работает следующим образом.Исходный числовой массив, содер ж;ггцгцг 1 г членов, подается на входы 3 М/25 И/2-1 коммутатора 1, который представляет собой комбицдциоггцую схему, позволяющую производить подключение заданных вьгходных ьцш к ггход О ным. Нд вход управления коммутаторас первого выхода блока 2 сшгхроциздцшг поступает код, вызывдгощгш подачу цд входы сумматоров 3 соответствующих пдр операндов-членов входного35 массива, определяем в первым шагом алгоритма (для представленного примера Г=16 это отсчегьг с номерами О и 8, 1 и 9, 2 гг 10 7 гг 5). С выходов 3(И+2) блока 2 гицхроггцздциц нд входы синхронизации сумматоров 3 поступают сигналы, здддгощие вьгполцешге в ггих суммирования ггли выгитация в соответствии с данным шагом ачгоритма (нд первом шаге алгоритма ггервгге И/2 сумматоров 3 гзг,гполггггют суюгггровагггге, а следующие 1/2 - вычитание).С выходов сумматора 3 результаты передагвтся в регистры 4 для промежутогггого хранения, откуда информация поступает ца входы И/2(311/2- 1) коммутатора 1. Нд вход управления. коммутатора 1 с первого входа блока 2 синхронизации приходит код, вызывающий подачу на входы сумматоров 3 пар операндов, определяемых вторим шагом алгоритма (это пары с номерами 0 и 4, 1 и 5, 2 и 6, 3 и 7, 9 и 15, 1 О и 14, 11 и 13 для алгоритма при И=16). Для сумматоров 3, в которых на данном шаге це предусматривается суммирование или вьгчитдцие (это относится к обработке отсчетов 8 и 12 для примера при Е= 16) ца один из их входов поступает нулевое значение с 5 И/2-го входа коммутатора 1. С выходов сумматоров 3, выполняющих обработку в соответствии с сигналами с выходов 3 (И+2) блока 2 синхронизации, определяемыми вторым шагом алгоритма, результаты вновь поступают на регистры 4 и далее ца входы И/2(ЗИ/2-1) первого комутатора 1.Затем начинается выполнение 3-го шага алгоритма. Он включает два подшдгд. Первый содержит только операции суммирования-вычитания и выполцяется аналогично второму шагу алгоритма, цо с другими сигналами из блока 2 синхронизации, поступающими на входы управления коммутатора 1 и сумматоров 3. Причем операнды, подаваемые цд сумматоры 3 с выходов коммутатора 1, выбираются так, чтобы отсчеты, для которых на втором подшаге предусмотрено умножение, поступали на сумматоры 3, к выходам которых через соответствующие регистры 4 подключены умножители 5, т.е. имеющие номера (11/2+1)И. Наличие в устройстве (11/2-1) умножителей 5 объясняется особенностями алгоритма, в котором умножение ца шаге выполняется не более, чем для (К/2-1) операндов.С выходов сумматоров 3 результаты через регистры 4 подаются на входы И/2(ЗИ/2- 1) коммутатора 1, а также на входьг первого сомножителя умножителей 5. Синхронно на входы второго сомножителя умножителей 5 поступают соответствующие значения с выходов 1(М) блока 6 поСтоянной памяти коэффициентов по сигналу с второго входа блока 2 синхронизации, Значения произведений с выходов умножителей 5 подаются на входы 1(И/2-1) коммутдтора 1. На вход управления последнего с первого выхода блока 2 синхронизации поступает код, вызывающий подачу на входы сумматоров 3 информации с соответствуюших пар входов коммутагора 1. Для сумматоров 3, в которых на данном подшаге не предусматривается суммирование или вычитание, на один из входов подается нулевое значение с 511/2-го входа коммутатора 1.На входы сумматоров 3 с блока 2 сий- хронизации поступают сигналы, задающие выполнение в них суммирования или вычитания в соответствии с алгоритмом. Результаты суммирования посту 5 пают на регистры 4 и фиксируются в них,На этом заканчивается выполнение и з о б р е т е н и я35 формула 4Устройство для быстрого действите ного преобразования Фурье, содертретьего шага.Вычисления на четвертом и после дующих шагах проходят с другими операндами, но в целом подобны описанной процедуре выполнения третьего шага, Исключение составляет лишь последний шаг алгоритма, который не вклю 15 чает в себя подшагов. Он выполняется аналогично второму подшагу третьего шага алгоритма, но осуществляется по другим, соответствующим алгоритму, кодам подключения, поступающим из бло.20 ка 2 синхронизации на коммутатор 1, с другим набором признаков суммирования или вычитания, задаваемым из блока 2 синхронизации на сумматоры 3, и с новыми значениями весовых коэффициентов, подаваемыми на умножители 5 из блока 6 постоянной памяти коэффициентов по сигналу блока 2 синхронизации. Результаты вычислений фиксируются в регистры 4, откуда передаются 30 на входы устройства и считываются с них для дальнейшей обработки.1 жащее блок синхронизации, коммутатор,И сумматоров (Х - размер преобразования), И регистров, блок постояннойпамяти коэффициентов, (И/2-1) умножителей, первый вход блока синхронизации подключен к управляющему входукоммутатора, -й (1=1, М/2- 1) информационный вход которого подключен квыходу х-го умножителя, первый входкоторого подключен к 1-му выходу блока постоянной памяти коэффициентов,вход разрешения считывания которогоподключен к второму выходу блока синхронизации, третий выход которогоподключен к входу синхронизации 3-го(3=1, И) регистра, выход которогоявляется 3-м информационным выходомустройства, о т л и ч а ю щ е е с ятем, что с целью повышения быстродействия, (2 К)-й и 2 К-й (К=1, М) выходы коммутатора подключены соответственно к первому и второму входамК-го сумматора, выход которого подключен к информационному входу К-горегистра, выход которого подключен к( + 11/2- 1)-му информационному входукоммутатора, (3 + ЗИ/2+1)-й информационный вход которого является 3-минформационным входом устройства,5 Х/2-й информационный вход которогоявляется входом задания логическогонуля устройства, выход (+Я/2)-гоблока постоянной памяти подключен квторому входу -го умножителя, (3++3)-й выход блока синхронизации подключен к стробирующему входу К-госумматора.1322309 Х Хб Хд Хю г лишаь а- Вс арано оставитель ехред Л.О Редактор Н,Рогул орректор А,Зимокосов 867/ дписное 4/5 Проиэводственно-полиграфическое предприятие, г.ужгород, ул.Проектная,4Хфд х Хюц Х 1 ТирВНИИПИ Государспо делам изоб113035, Москва,аж 672 венного комитета СССР етений и открытий -35, Раушская наб д