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

 

Изобретение относится к области вычислительной техники и предназначено для использования в аппаратуре, осуществляющей спектральньпЧ анализ сигналов, представленных цифровыми последовательностями. Цель изобретения - повышение быстродействия Поставленная цель достигается тем, что в состав устройства входят коммутатор 1, блок 2 синхронизации, N сумматоров 3 (N - размер преобразования), N регистров 4, (N/2-1) умножителей 5, блок 6 постоянной памяти коэффициентов и соответствующие связи между блоками устройства. Коды подключения поступают на коммутатор 1 из блока 2 синхронизации, который задает набор признаков суммирования или вычитания на сумматоры 3 и новые значения весовых коэффициентов, подаваемые на умножители 5 из блока 6 постоянной памяти. Результаты вычислений фиксируются в регистрах 4, откуда передаются на выходы устройства и считываются с них для дальнейшей обработки. 2 ил. а С оо N3 to ОО о Х)

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) А1 (5D4 G 06 F 15 332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4031110/24-24 (22) 27.02.86 (46) 07.07.87. Бюл. )) 25 (71) Институт технической кибернетики АН БССР (72) В.Н.Дашук, С.Н.Демиденко, В.С.Кончак и Э.Б.Куновский (53) 68 1.32 (088.8) (56) Патент Франции Ф 2092030, кл. G 06 F 15/00, 1975.

Авторское свидетельство СССР

N 660057, кл. О 06 F 15/332, 1979. (54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ДЕЙСТВИТЕЛЬНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники и предназначено для использования в аппаратуре, осуществляющей спектральный анализ сигналов, представленных цифровыми последовательностями. Цель изобретения — повышение быстродействия, По\ ставленная цель достигается тем, что в состав устройства входят коммутатор

1, блок 2 синхронизации, N сумматоров 3 (N — размер преобразования), N регистров 4, (N/2- 1) умножителей

5, блок 6 постоянной памяти коэффициентов и соответствующие связи между блоками устройства. Коды подключения поступают на коммутатор 1 иэ блока 2 синхронизации, который задает набор признаков суммирования или вычитания на сумматоры 3 и новые значения весовых коэффициентов, подаваемые на умножители 5 из блока 6 постоянной памяти. Результаты вычислений фиксируются в регистрах 4, откуда передаются на выходы устройства и считываются с них для дальнейшей обработки. 2 ил.

1322309

Изобретение относится к вичислительной технике и предназначе«о для использования в аппаратуре, осуществляющей спектральный анализ сигналов, представленных цифровыми последова- 5 т t JI ь | I о с T я м и .

Цель изобретения — повышение быстродействия устройства за счет реализации в нем нового алгоритма быстрого действительного преобразования

1О

Фурье.

На фиг.1 представлена функциональIIa» схема устройства; на фиг.2 — граф алгоритма быстрого действите:и ного преобразования Фурье, реализованный в устройстве (для размерности К=16).

Устройство содержит коммутатор 1, блок 2 cltttxpot«пзации, Х сумматоров

3, N регистров 4, (! — 2)/2 умножите— лей 5 и блок 6 постоянной памяти коэффициентов.

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

Исходный числовой массив, содер- 25 жащий М членов, подается на входы

ЗМ/2...5N/2-1 коммутатора 1, который представляет собой комбинационную схему, позволяющую производить подключение заданных выходных иш к вход- 30 ным. На вход управления коммутатора

1 с первого выхода блока 2 синхронизации поступает код, вызывающий подачу на входы сумматоров 3 соответствующих пар операн 1ов- .ленов входного

35 массива, определяешьm первым шагом

;I III îpè III (для и! едставленного примера Г =16 это отсчеты с номерами 0 и 8, 1 и 9, 2 и 10... 7 lt !5). С выходов 3...(N+2) блока 2 синхронизации на вx0;III спнхр низации сумматоров

3 Ilocтупают с Itгначы, задающие выполнеш, е ll них суммирования II.IH вы штанин в соответствии с данным шагом ачгорптма (на первом шаге алгоритма первые N/2 сумматоров 3 ш,)полняют суммирование, а следующие Е/2 — вычитание).

С выходов сумматора 3 результаты передаются В регистры 4 для промежуто шзго хранения, откуда информация поступает на входы N/2...(ÇN/2- 1) коммутатора 1. На вход управления. коммутатора 1 с первого входа блока 2 синхронизации приходит код Вызываю щий подачу на входы сумматоров 3 пар операндов, определяемых вторим шагом алгоритма (это пары с номерами 0 и

4, 1 и 5, 2 и 6, 3 и 7, 9 и 15, 1О и 14, 11 и 13 для алгоритма при N=16) .

Для сумматоров 3, в которых на данном шаге не предусматривается суммирование или вычитание (это относится к обработке отсчетов 8 и 12 для примера при Е=16) на один из их входов поступает нулевое значение с 5И/2-го входа коммутатора 1. С выходов сумматоров 3, выполняющих обработку в соответствии с сигналами с выходов 3... (N+2) блока 2 синхронизации, определяемыми вторым шагом алгоритма, результаты вновь поступают на регистры

4 и далее на входы И/2...(ÇN/2-1) первого ког мутатора 1.

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

Ю соответствующие регистры 4 подключены умножители 5, т.е. имеющие номера (N/2+1)...N. Наличие в устройстве (N/2-1) умножителей 5 объясняется особенностями алгоритма, в котором умножение на шаге выполняется не более, чем для (N/2-1) операндов.

С выходов сумматоров 3 результаты через регистры 4 подаются на входы

N/2...(3N/2- 1) коммутатора 1, а также на входы первого сомножителя умножителей 5 . Синхронно на входы второго сомножителя умножителей 5 поступают соответствующие значения с выходов

1...(N-2) блока 6 постоянной памяти коэффициентов по сигналу с второго входа блока 2 синхронизации ° Значения произведений с выходов умножителей 5 подаются на входы 1...(N/2-1) коммутатора 1. На вход управления последнего с первого выхода блока 2 синхронизации поступает код, вызывающий подачу на входы сумматоров 3 информации с соответствуюших пар входов коммутаtopa 1. Для сумматоров 3, в которых на данном подшаге не предусматривается суммирование или вычитание> на один из входов подается нулевое значение с 5N/2-ro входа коммутатора 1.

1322309

На входы сумматоров 3 с блока 2 сий- хронизации поступают сигналы, задающие выполнение в них суммирования или вычитания в соответствии с алгоритмом. Результаты суммирования посту 5 лают на регистры 4 и фиксируются в них.

На этом заканчивается выполнение и з о б р е т е н и я)

Формула

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

Вычисления на четвертом и после- 10 дующих шагах проходят с другими операндами, но в целом подобны описанной процедуре выполнения третьего шага. Исключение составляет лишь последний шаг алгоритма, который не вклю-15 чает в себя подшагов. Он выполняется аналогично второму подшагу третьего шага алгоритма, но осуществляется по другим, соответствующим алгоритму, кодам подключения, поступающим из бло-20 ка 2 синхронизации на коммутатор 1, с другим набором признаков суммирования или вычитания, задаваемым из блока 2 синхронизации на сумматоры 3, и с новыми значениями весовых коэффициентов, подаваемыми на умножители 5 из блока 6 постоянной памяти коэффициентов по сигналу блока 2 синхронизации. Результаты вычислений фиксируются в регистры 4, откуда передаются 30 на входы устройства и считываются с них для дальнейшей обработки.

1 жащее блок синхронизации, коммутатор, N сумматоров (N — размер преобразования), N регистров, блок постоянной памяти коэффициентов, (N/2-1) умножителей, первый вход блока синхрони. зации подключен к управлявшему входу коммутатора, i-й (i=i, N/2-1) информационный вход которого подключен к выходу i-го умножителя, первый вход которого подключен к i-му выходу блока постоянной памяти коэффициентов, вход разрешения считывания которого подключен к второму выходу блока синхронизации, третий выход которого подключен к входу синхронизации J ãо (3=1, N) регистра, выход которого является 1-м информационным выходом устройства, о т л и ч а ю щ е е с я тем, что с целью повышения быстродействия, (2К-1)-й и 2К-й (К=1, N) выходы коммутатора подключены соответственно к первому и второму входам

К-го сумматора, выход которого подключен к информационному входу К-го регистра, выход которого подключен к (i + N/2- 1)-му информационному входу коммутатора, (j + 3N/2+1)-й информационный вход которого является 3-м информационным входом устройства, 5N/2-й информационный вход которого является входом задания логического нуля устройства, выход (i+N/2)-ro блока постоянной памяти подключен к второму входу i-го умножителя, (j+

+3)-й выход блока синхронизации подключен к стробирующему входу К-го сумматора.

1322309

К1 х а

6„

Хд

Х7

Хв

Хд 4о

Хя

X>z х»

Х1Ч

Х1 б а-д а —; — о

Составитель А.Баранов

Техред Л.Олийнык, Редактор Н,Рогулич

Корректор А.Зимокосов

Подписное

Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная,4 б

1 I

1ш08 Йшаа ) Й аа ашот

I»

Заказ 2867/47 Тираж 672

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

T а °

1, вк

4,