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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Социалистмческик

Республик (n> 97251 7 (б1) Дополнительное к авт. свмд-ву (22) Заявлено 240381 (2 ) 3298729/18-24 с присоединением заявки ¹â€” (23) Приоритет

Опубликовано071182. Бюллетень №41

Дата опубликования описания 071182

)И) М.Кл.з

G 06 F 15/332

Государствеииый комитет

СССР ио делам изобретений и открытий

) Щ УДК 681. 3 (088.8) (72) Авторы изобретения

M.È. Дергачев, А.A. Балтрашевич и Т.Б. Сор .) (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО

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

Изобретение относится к автоматике:и вычислительной технике и может быть использовано в аппарате, осуществляющем спектральную обработку электрических сигналов в реальном масштабе времени.

Известно устройство для выполнения быстрого преобразования Фурье, содержащее четыре сумматора, три мно-жительных блока, два сумматора-вычитателя, четыре регистра (1).

Недостатком устройства является большое количество оборудования, так как для выполнения каждой арифметической операции оно содержит отдельный блок.

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

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

Целью изобретения является повышение быстродействия устройства.

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

25 регистры суммы, квадратор, причем выход второго входного регистра подключен к первому информационному . входу второго коммутатора и первому информационному входу пятого коммутатора, выход третьего входного ре972517 гистра подключен к первым информационным входам третьего и четвертого коммутаторов, выход четвертого входного регистра подключен к третьему информационному входу первого коммутатора и вторым информационным 5 входам второго и пятого коммутаторов, выход пятого входного регистра подключен к вторым информационным входам третьего и четвертого коммутаторов, выход шестого входного регист-10 ра подключен к третьему информационному входу второго коммутатора, выход третьего коммутатора подключен к второму входу первого сумматора, выходы втоРого и четвеРтого комму- 5 таторов подключены соответственно к первому и второму входам второго сумматора, выход первого сумматора подключен к входу третьего регистра суммы, выход второго сумматора подключен к входам четвертого, пятого и шестого регистров суммы,. выход первого регистра суммы подключен к третьим информационным входам четвертого и пятого коммутаторов, выход второго регистра суммы подключен к третьему информационному входу третьего коммутатора, выход третьего регистра суммы подключен к четвертым информационным входам первого и пятого коммутаторов, выхоц четвертого30 регистра суммы подключен к пятому ийформационному входу первого коммутатора и к четвертому информационному входу четвертого коммутатора, выход пятого регистра суммы подключен35 к пятым информационным входам четвертого и пятого коммутаторов, выход шестого регистра суммы подключен к шестым информационным входам первого и пятого коммутаторов, выход пятого 4() коммутатора подключен к входу квадратора, выход которого подключен к четвертым информационным входам второго и третьего коммутаторов, второй, третий, четвертый и пятый выходы бло-45 ка управления подключены к управляющим входам второго, третьего, четвертого и пятого коммутаторов соответственно, выходы первого, третьего, четвертого и шестого регистров суммы являются информационными выходами устройства.

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

На фиг. 1 представлена функциональная схема устройства для выпол- 6О нения быстрого преобразования Фурье; на фиг. 2 — функциональная схема блока управления.

Устройство содержит входные регистры 1-6, входы 7-12 которых являются информационными входами устройства, блок 13 управления, коммутатор 14, квадратор 15, коммутаторы

16-19, сумматоры 20 и 21, регистры суммы 22-27, выходы 28-31 которых являются информационными выходами устройства.

Блок управления 13 состоит иэ счетчика 32, дешифратора 33, причем счетный вход 34 счетчика является тактовым входом устройства.

В устройстве выполняются следующие операции

В,А-„=В A-+R

Ве В, =йе А -R

В =1„,А -1, где A< — первое комплексное число;  — второе комплексное число.

Величины R u I определяются re известным формулам

Веву ReW - 1 В.! И, )Ы )М

В в I W + I B)RåW1

2 It где =е р (-3 — ), М вЂ” объем выборки.

Величины R u I с уче ом того, что (Rg W) ++(IW)+ = I,а также того, что произведение двух чисел А и В можно представить в виде

AB = . ((A+B) -Я -В ), находятся в

1 2 д д. соответствии с формулами ю= ((а,в;.,в)+(„в,- ч)- — К В - 3 3 "<9»t. Ie "Е® — 1еЗ; - 3щь3 -4

Квадратор 15 представляет собой табличную память. В каждой ячейке памяти хранится половина квадрата числа, являющегося адресом ячейки.

Длительность такта определяется суммарным временем обращения к квадратору, временем суммирования и временем задержки сигналов на коммутаторе 14 и одном из коммутаторов

16-19 °

В первом такте работы устройства в регистры 1-6 записываются исходные ,цанные Re A> ВЕ Ве ° ю ) м"

1 А .соответственно. Во втором такте по адресу Ве В из квадратора 15 извлекается число (В В ), которое через коммутатор 18 слагаемых подается на сумматор 21. Одновременно через коммутаторы 16, 17 и 19 на сумматор 20 подаются слагаемые R и

RBW, а на сумматор 21 — постоянная величина 0,5. Результаты суммирования поступают в регистры суммы 23 и 27 соответственно.

972517

20

30 где t

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

55 вому входу первого сумматора, выход .которого подключен к входам первого

60 и второго регистров суммы, о т л и жит второй, третий, четвертый и пятый коммутаторы, второй сумматор, 65 третий, четвертый, пятый и шестой

В третьем такте в квадраторе 15 по поступающему с регистра суммы 23 адресу определяется число (Q B +R

В течение четвертого такта из содержимого регистра суммы 26 на сумматоре 21 вычитается определяемое в квадраторе 15 число (1„„В ) . Одф Ъ ° новременно на сумматоре 20 это же число суммируется с содержимым регистра суммы 27. Полученные значения записываются в регистры суммы

23 и 25.

В пятом такте работы устройства по содержимому регистра суммы 22 в квадраторе 15 определяется число (II„S - 1„,Ч), которое затем на сумматоре 20 складывается с содержимым регистра суммы 23. Результат (величина R) записывается в регистр суммы 24. Одновременно через коммутаторы 18 и 19 на сумматор 21 посту- . ают значения Re B и!„„У, результат суммирования записывается в регистр суммы 27.

В шестом такте по содержимому регистра 27 в квадраторе 15 определяется число (В8 В +I W), которое затем на сумматоре 20 складывается с поступающим через коммутатор 16 содержимым регистра 25, взятым с обратным знаком. Результат записывается в регистр 22. Одновременно с этим через коммутаторы 18 и 19 на сумматор 21 поступают значения

I>B> и R

Результат суммирования записывается в регистр 26.

В седьмом такте формируется первый конечный результат вычислений8 Ал,л. Для этого на сумматоре 20 складываются содержимое входного регистра 1 и регистра суммы 24. Конечный результат записывается в регистр

23. Одновременно с этим по содержимому регистра 26 в квадраторе 15 находится значение (I В +R W), поступающее затем на суматор 21, где складывается с поступающим через коммутатор 19 содержимым регистра 22.

Полученный результат (величина I), записывается в регистр 27.

В течение следующего такта на сумматор 20 через коммутаторы 16 и 17 поступают соответственно содержимое входного регистра 1(величина R ) и содержимое регистра 27 (величина !). Таким образом, формируются конечные результаты йб В. л и А л, которые записываются в регистры суммы 22 и

25 соответственно.

В девятом такте работы устройства на сумматоре 21 складываются содержимое входного регистра б (I Aj ) и содержимое регистра 27 (I), взятое с обратным знаком. Полученное значение 8> q записывается в регистр 26.

Технический эффект от использования устройства заключается в повышении быстродействия.

Базовая операция быстрого преобразования Фурье в известном устройстве выполняется эа 8 тактов, причем длительность такта равна длительности операции умножения двух действительных чисел. Базовая операция быстрого преобразования Фурье в данном устройстве выполняется за 9 тактов, причем длительность такта равна длительности операции сложения (или вычитания).

Выигрыш в быстродействии Н определяется иэ выражения

З- ум

= .— — >) 1, сЕ время выполнения операции . умножения над действительными числами; время выполнения операции сложения (или вычитания) над действительными числами.

1. Устройство для выполнения быстрого преобразования:Фурье, содержащее шесть входных регистров, входы которых являются информационными входами устройства, блок управления, первый коммутатор, первый сумматор, первый и второй регистры суллы, причем выходы первого и второго входных регистров подключены соответст венно к первому и второму информационным входам первого коммутатора, управляющий вход первого коммутатора слагаемых подключен к первому выходу блока управления, выход первого коммутатора слагаемых подключен к перч а ю щ,е е с.я тем, что, с целью йовыаения быстродействия, оно содер972517 регистры суммы, квадратор, причем выход второго входного регистра подключен к первому информационному входу второго коммутатора и первому информационному входу пятого коммутатора, выход третьего входного регистра подключен к первым информационным входам третьего и четвертого коммутатора, выход четвертого входного регистра подключен к третьему информационному входу первого коммутатора и вторым информационным вхо дам второго и пятого коммутаторов, выход пятого входного регистра подключен к вторым информационным входам третьего и четвертого комму- 15 татаров, выход шестого входного регистра подключен к третьему информационному входу второго коммутатора, выход третьего коммутатора подключен к второму входу первого сумматора, 29 выходы второго и четвертого коммутаторов подключены соответственно к первому и второму входам второго сумматора, выход первого сумматора подключен к входу третьего регистра 25 суммы, выМод второго сумматора подключен к входам четвертого, пятого и шестого регистров суммы, выход первого регистра суммы подключен к третьим информационным входам четвертого и пятого коммутаторов, выход второго регистра суммИ подключен к третьему информационному входу третьего коммутатора, выход третьего регистра суммы подключен к четвертым информационным входам первого и пятого коммутаторов, выход четвертого регистра суммы подключен к пятому информационному входу первого коммутатора и к четвертому информационному входу четвертого коммутатора, выход пятого регистра суммы подключен к пятым информационным входам четвертого и пятого коммутаторов, выход шестого регистра суммы подключен к шестым информационным входам первого и пятого коммутаторов, выход пятого коммутатора подключен к входу квадратора, выход которого подключен к четвертым информационным входам второго и третьего коммутаторов, второй, третий, четвертый и пятый выходы блока управления подключены к управляющим входам второго, третьего, четвертого и пятого коммутаторов соответственно, выходы первого, третьего, четвертого и шестого регистров суммы являются информационными выходами устройства.

2. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок управления состоит из счетчика и дешифратора, причем счетный вход счетчика является тактовым входом устройства, выход счетчика подключен к. входу дешифратора, выходы дешнфратора являются выходами блока управления.

Источники информации, принятые во внимание при экспертиэе

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

Р 656070, кл. 6 06 Г 15/332, 1979;

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

9 598085, кл. 6 Об Г 15/332, 1979 (прототип).

972517

Нбл.!Ф l(й 16 Кбд, ВНИИПИ Заказ 8518/41

Тираж 731 Подписное

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