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

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

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

СП.

Недостатки этого устройства большое i количество оборудования и неоптимальное его использование при выполнении базовой операции БПФ.

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

Однако в данном, устройстве одна базовая операция БПФ выполняется за шесть тактов умножения, что приводит

к недостаточно высокому быстродейстВИЮ..

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

Поставленная цель достигается тем, что в устройстве для быстрого преобразования Фурье, содержащем шесть входных регистров, умножитель, ,регис тр произведений,два регистра сумм, два Коммутатора и блок микроnporpetMMHoro управления, причем выходы первого и второго входных регистров через первый коммутатор подключены к входам умножителя, выход которого подключен к входу регистра произведений, выходытретьего и четвертого входных регистров и выход регистра произведений через второй коммутатор подключены к входам сумматора, выход которого является выхо,зм устройства и подключен к входам регистров сумм, выходы блока микропрограммного управления подключены к управляющим входам коммутаторов, выходы пятого и шестого входных регистров подключены к дополнительным информационным входам первого кетимутатора, а выходы регистров сумм - к дополнительным информационньш входам второ- . го коммутатора. На чертеже представлена функциональная схема устройства для быстро го преобразования Фурье. Устройство содержит входные регистры 1 - б, коммутатор 7, умножитель 8, регистр 9 произведений, ком мутатор 10, сумматор 11, регистры 12 и 13 сумм и блок 14 микропрограм много управления. Блок 14 может состоять из генера тора тактовых импульсов, счетчика тактовых импульсов и блока памяти микрокоманд, адресный вход которого подключен к выходу счетчика, а выхо является выходом блока микропрограм много управления. Устройство выполняет за каждую базовую операцию следующие операции г ReA.,ReA.+ ReB.ReC,.., n,i--, ,,ReC. «еВ.,2(еЛ..-КеЛ,..1. где А - первое комплексное число .В,- - второе комплексное число С{ - комплексная весовая функция На выходные регистры 1-4 записыва ются исходные числовые данные ReA, ,-i, ReB|.-|n3m В, , Re С/ и On, С . KoMMiTarop 7 сомнохсителей направ ляет на умножитель 8 входные данные дл55 получения промежуточных произвед ний .(соогветственно по четырем тактам текусдей базовой операции, которые последовательно записывают в регистр & произведений в конце первого тактапроизведение ReB «ReC, в конце второго - От В JmCi-,B конце третье го - КеВ конце четвертог . i - ReC,. В первой половине второ го такта на сумматор 11 через коммутатор 10 поступают ReA из входного регист а 1 и первое произведение. Эта частная сумма записывается в кон де первой половины второго такта в регистр 12. В течение первой половин третьего такта коммутатор 10 подает на сумматор 11 новое произведение из регистра 9 и частную сумму из ре™ гистра 12 в результате сложения этих слагаемых, в сумматоре 11 а конце первой половины третьего такта на выход 15 выдается и одновременно записывается 3 регистр 13 первый результат ReAi . В течение половины третьего такта коммутатор 10 подает слагаемые из регистра 13 и входного регистра 1 для получения на сумматоре 11 BTOpouQ числа ReB5+. На протяжении первой половины чет вертого такта на сумматор 11 через коммутатор 10 подается третьеготроизйедение из регистра 9 и число из . входного регистра 2, частная.сумма записывается в регистр 12. В течение первой половины первого такта следующей базовой операции на выходе сумматора 11 после поступления на него через коммутатор 10 четвертого произведения из регистра 9 образуется следующее число ОщА ,которое записывается в регистр 13 и выдается на выход 15. Во второй половине первого такта следующей базовой операции получается последнее четвертое число путем сложения числа из входного регистра 2 и регистра 13, поступающих на сумматор 11 через коммутатор 10. Таким образом, в течение всех четырех тактов текущей базовой операции вычисляются четыре сомножителя, а частичные суммы и конечные результаты на выходе сумматора образуются IB течение первой половины второго и Четвертого тактов, а также в полутактах третьего такта текущей и первого такта последующей базовой операций. Таким образом, в предлагаемом устройстве цикл работы состоит из четырех тактов или восьми полутактов. Причем, в шести полутактах сумматор и блок умножения работают одновременно. Использование предлагаемого устройства позволяет получить выигрыш по быстродействию в сравнении с прототипом на 33%. Формула изобретения Устройство для быстрого преобразования Фурье, содержащее шесть входных регистров, умножитель, сумматор, регистр произведений, два регистра сумм, два коммутатора и блок микропрограммного управления, причем выходы первого и второго входных регистров через первый коммутатор подключены к входам умножителя, выход которого подключен к входу регистра произведений, выходы третьего и четвёртого входных регистров и выход регистра произведений через второй коммутатор подключены к входам сумматоpa.f выход которого является выходом «устройства и подключен к входам ре-. гистров сумм, выходы блока микропрограммного управления подключены к управляющим входам коммутаторов, отличающееся тем, что, с целью повышения быстродействия, выходы пятого и шестогр входных регистров подключены к дополнительным информационным входам первого коммутатора, а выходы регистров сумм - к дополнительным информационным входг1м второго коммутатора. Источники информации, принятые во внимание при экспертизе 1.Патент США 3800130, кл, 235-156, опублик, 1974, 2.Авторское свидетельство СССР 736113, кл. G 06 F.15/332, 1977 (прототип),

-i

S

uT

1

f2

ff

fff

fj

ff