Устройство для выполнения быстрого преобразования Фурье Советский патент 1982 года по МПК G06F17/14 G01R23/00 

Изобретение „относится к автомати ке и вычислительной технике и может .быть использовано в аппарате, осуществляющем спектральную обработку электрических сигналов в реальном масштабе времени. Известно устройстводля выполнения быстрого преобразования Фурье, содержащее четыре сумматора, три мн жительных блока, два сумматора-вычи тателя, четыре регистра L-4 Недостатком устройства является большое количество оборудования, так как для выполнения каждой арифметической операции оно содержит отдельный блок. Наиболее близким техническим решением к изобретению является устройство для выполнения быстрого пре образования Фурье,.содержащее шесть .входных регистров, блок управления, коммутатор, сумматор, два регистра суммы, коммутатор сомножителей, блок умножения, четыре регистра произве-г дений 12. Недостатком известного устройства является низкое быстродействие, поскольку в нем последовательно выполняются четыре операции умножения. Целью изобретения является повы- шение быстродействия устройства. , Поставленная .цель достигается тем, что устройство для выполнения быстрого преобразования Фурье, содержащеег шесть входных регистров, входы которых являются информационными входами устройства, блок управления, первый коммутатор, первый сумматор, первый и второй регистры суммы, причем выходы первого и второго входных регистров подключены соответственно к первому и второму информационным входам первого кокмутатора, управлякиций вход первого коммутатора слагаемых подключен к первому выходу блока управления, выход первого коммутатора слагаемых подключен к первому входу первого сумматора, выход которого подключен к входам первого и второго регистров суммы, содержит второй, третий, четвертый и пятый коммутаторы, второй сумматор, третий, четвертый, пятый и шестой регистры суммы, квадратор, причем выход второго входного регистра подключен к первому информационному .входу второго коммутатора и первому информационному входу пятого коммутатора, выход третьего входного регистрс-i подключен к первым информационным входам третьего и четвертого коммутаторов, выход четвертого входного регистра подключен к третьему информационному входу первого коммутатора и вторым информационным входам второго и пятого коммутаторов выход пятого входного регистра подключен к вторым информационным входам третьего и четвертого коммутаторов, выход шестого входного регист ра подключен к третьему информационному входу второго коммутатора, выход третьего коммутатора подключен к второму входу первого сумматора, выходы второго и четвертого коммутаторов подключены соответственно к первому и второму входам второго сум матора, выход первого cyjviMaTopa подключен к входу третьего регистра суммы, выход второго сумматора подключен к входам четвертого, пятого ишестого регистров суммы,.выход первого регистра суммы подключен к третьим информационным входам четвер того и пятого коммутаторов, выход второго регистра суммы подключен к третьему информационному входу треть его коммутатора, выход третьего регистра суммы подключен к четвертым информационным входам первого и пятого коммутаторов, выход четвертог регистра суммы подключен к пятому информационному входу первого комму татора и к четвертому информационному входу четвертого коммутатора, выход пятого регистра суммы подключе к пятым информационным входам четвер того и пятого коммутаторов, выход шестого регистра суммы подключен к шестым информационным входам первог и пятого коммутаторов, выход пятого коммутатора подключен к входу квадратора, выход которого подключен к четвертым информационным входам вто рого и третьего коммутаторов, второ третий, четвертый и пятый выходы бл ка управления подключены к управляю щим входам BToppio, третьего, четвертого и пятог9 коммутаторов соответственно, выходы первого, третьег четвертого и шестого регистров суммы являются информационньп ш выходам устройства. Кроме того, блок управления состоит из счетчика и дешифратора, причем счетный вход счетчика являет тактовымвходом устройства, выход счетчика подключен к входу дешифратора, выходы деши-фратора являются выходами блока управления. На фиг. 1 представлена функциональная схема устройства для выполнения быстрого преобразования Фурье на фиг. 2 - функциональная схема блока управления. Устройство содержит входные регистры 1-6, входы 7-12 которьрг явля ются информационными входами устройства, блок 13 управления, коммутатор 14, квадратор 15, коммутаторы 16-19, сумматоры 20 и 21, регистры суммы 22-27, выходы 28-31 которых являются информационными выходами устройства. Блок управления 13 состоит из счетчика 32, дешифратора 33, причем счетный вход 34 счетчика является тактовым входом устройства. В устройстве выполняются следующие операции ReA-H ReAj+R KA.UA:- + I f в е lmB.,-.-pVAy-l где А - первое комплексное число; BJ - второе комплексное число. Величины R и I определяются по известным формулам - r.,- + , где (-J -г-р) , N - объем выборки. Величины R и I с учетом того, что (ReW)2-+( )i 1 ,а также того, что произведение двух чисел А и В можно представить в виде АВ (A+B), находятся в соответствии с формулами .) ,)-М)-(-.)Ч, . 3- ( (vvibj Rew)- -(. , Квадратор 15 представляет собой табличную память. В каждой ячейке памяти хранится половина квадрата числа, являющегося адресом ячейки. Длительность такта .определяется cyMTviapHbiM временем обращения к квадратору, временем суммирования и временем задержки сигналов на коммутаторе 14 и одном из коммутаторов 16-19. В первом такте работы устройства в регистры 1-G записываются исходные данные , RgW, , ж tjj, A.Соответственно. Во втором такте по адресу Re В j из кв.адратора 15 извлекается число (RgB: ), которое через коммутатор 18 слагаемых подается на сумматор 21. Одновременно через коммутаторы 16, 17 и 19 на сумматор 20 подаются слагаемые и RgV/, а на сумматор 21 - постоянная величина 0,5. Результаты суммирования поступают в регистры суммы 23 и 27 соответственно.

В третьем такте.в квадраторе 15 по поступающему с регистра суммы 23 адресу определяется число ( Rg Bj +RpW) которое затем на сумматора 21 складывается с поступающим через коммутатор 19 с регистра суммы.27 значеtl i т (RgB;) +0,5j. Полученная

сумма записывается в регистр суммь1 26. Одновременно на сумматоре 20 определяется разность чисел и 1у„У, поступающих с входных регистров 4 и 5 через коммутаторы 16 и 17 и записывается в регистр .суммы 22.

В течение четвертого такта из содержимого регистра суммы 26 на сум маторе 21 вычитается определяемое в квадраторе 15 число (1,„В;). одновременно на сумматоре 20 это же число суммируется с содержимым регистра суммы 27, Полученные значеНИН записываются в регистры суммы 23 и 25.

В пятом такте работы устройства по содержимому регистра суммы 22 в квадраторе 15 определяется число ( wW), которое затем на сумматоре 20 складывается с содержимьам регистра суммы 23. Результат (величина R) записывается в регистр суммы 24. Одновременно через коммута.торы 18 и 19 на сумматор 21 посту- . пают значения RgB Hlyy,W, результат суммирования записывается в регистр суммы 27.

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

В седьмом такте формируется первый конечный результат вычислений этого на сумматоре 20 складываются содержимое входного регистра 1 и регистра суммы 24. Конечный результат записывается в регистр 23. Одновременно с этим по содержимому регистра 26 в квадраторе 15 находится значение (), поступающеё затем на суматор 21, где складывается с поступающим через коммутатор 19 содержимым регистра 22 Полученный результат (величина I), записывается в регистр 27. .

В течение следующего такта на сумматор 20 через коммутаторы 16 и 17 поступают соответственно содержимое входного регистра К величина RgA.,-) и содержимое регистра 24 (величина R

взятое с обратным знаком. На сумматор 21 через коммутаторы 18 и 19 поступают содержимое входного регистра 6 (величина и содержимое регистра 27 (величина I). Таким . o6pa3ONf, формируются конечные результаты Rg В.-. и ,A.,v , которые записываются в регистры сумгиы 22 и 25 соответственно.

В девятом такте работы устройства на сумматоре 21 складываются содержимое входного регистра 6 (1„А; ) и содержимое регистра 27 (1), взятое с обратным знаком. Полученное значение .., записывается в регистр 26

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

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

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

3- tyw

1.

Н

9 tc8

время выполнения операции .

SMдеумножения над действительными числами;

сввремя выполнения операции сложения (или вычитания) над действительными числами,

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

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

регистры суммы, квадратор, причем выход второго входного регистра подключен к первому информационному входу второго коммутатора и первому информационному входу пятого коммутатора, выход третьего входного регистра подключен к первым информационным входам третьего и четвертого коммутатора, выход четвертого входного регистра подключен к третьему информационному входу первого коммутатора и вторым информационным входам второго и пятого коммутаторов, выход пятого входного регистра подключен к вторым.информационным входам третьего и четвертого коммутаторов, выход luecToro входного регистра подключен к третьему информационному входу второго коммутатора, выход третьего коммутатора подключен к второму входу первого сумматора, выходы втсфого и четвертого коммутаторов подключены соответственно к первому и второму входам второго сумматора, выход первого сумматора подключен к входу третьего регистра суммы, второго сумматора подключен к входам четвертого, пятого и шестого регистров суммы, выход первого регистра суммы подключен к третьим информационным входам четвертого и пятого коммутаторов, выход второго регистра суммй подключен к третьему информационному вкоду -третьего коммутатора, выход третьего регистра суммы подключен к четвертым информационным входам первого и пятого коммутаторов, выход четвертого

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

и шё стого регистров суммы являются информационными выходами устройства.

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

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

1. Авторское свидетельство СССР № 656070, кл. G 06 F 15/332, 1979.

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

598085, кл. G 06 F 15/332, 1979 (прототип).

/2

8

28

Hdjijlf Ябл.Ю ИбйЛ Нб/I.W КВлЮ