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

I

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

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

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

ВЫХОДОВ выходно1ч регистра соответственно через первый и второй промежуточные регистры соединены со входами сумматора-вычитателя, первая группа выходов которого через третий промежуточный регистр соединена с первой группой аходов первого блока умножения. Вторая группа выходов сумматор а-вычитаталя через четвертый промежуточный регистр соединена с первой группой аходов в.ход10ного регистра и с первой группой выходов устройства. Вторая группа аходов аходного регистра является группой аходов устройства. Выход регистра хранения комплексных чисел соединен со вто15рой группой входов первого блока умножения, первая группа выходов входного регистра соединена с информационными входами блока памяти.

Кроме того, известное устройство содер20жит блок хранения констант, к которому Тфедьявляются требования как по объему хранимой памяти, так и по времени выборки. Известное устройство имеет сложную схему. Целью изобретения является упрощение устройства. Цель изобретения достигается тем, что в предложенное устройство сдвиговый регистр и второй блок умножения, причем первая и вторая группы входов сдвигового регистра подключены соответственно к третьей группе выходо выходного регистра и второй группе вь ходов входного регистра. Управляющий вход сдвигового регйстр4 соединен с соответствующим выходои блока управления, выход сдвигового регистра саеди нен со входом регистра хранения компле ных чисел. Первая группа выходов перво го блока умножения через второй блок умножения подключена к третьей группе входов входного регистра, четвертая группа входов которого и вторая группа выходов первого блока умножения подкл . чены ко второй группе выходов устройства. На фиг. 1 показана структурная схем устройства; на фиг. 2 - приведен граф алгоритма БПФ, на фиг. 3 - Ъхема реализации графа алгоритма БПФ. Устройство (фиг. 1) содержит сдвиговый 1 и выходной 2 регистры, блок памяти 3, регистр 4 хранения комплекс ных чисел, промежуточные регистры 5-8, первый блок умножения 9 сумматор-вычитатель 1О, второй блок умноже ния 11, адресный блок 12, входной регистр 13, блок управления 14, первую и вторую группы выходов 15, 16, груп пу входов 17, управляющие выходы 1822 блок управления. Граф алгоритма БПФ (фиг. 2) прив-еден для исходного массива длиной в 16 значений. На фиг. 2, в частности, показаны индексы исходного массива 23, индексы выходного массива 24, операции умножения на 1 25, различные итерации 26 графа. Устройство реализует, например, алгоритм БПФ (см. фиг. 2) в поспедовательвости, изображенной на фиг. 3. Такая последовательность вычисле щя характеризуется тем, что в процесс вычисления втягиваются ячейки операндов намяти последовательно, причем до включения в вычисление новьк двух операндов все вычисления идут с операндами, которые уже участвовали в Быччслении на предьщущих этапах. Кроме того, номер константь всегда соответствует номеру первого операнда в двухточечном преобразовании Фурье первой итерации. Из сказанного можно сделать вывод: вместе с исходными данными в память нужно записывать и константы . Это всегда можно сделать, так как исходные операнды имеют меньщую разрядность, нежели разрядная сетка промежуточных вычислений. Так, например, реальным является-хранение вместе с операндами с номерами 1 i т одной константы с номером 1 в последних четырех .разрядах каждого числа (мнимого и действительного). При шестнадцатиразрядной сетке 12 разрядов занимает исходная информация, что вполне достаточно. Такое хранение констант позволяет формировать очередную константу по мере вовлечения новых исходных данных в вычислительный .процесс путем вьщвпе- ния четырех последних разрядов в каждом новом операнде. С очередной константой проводятся вычисления, которые не требуют участия ячеек с операндами, в которых содержатся последующее константы, поэтому промежуточные результаты вычислений не стирают последующие константы до того времени, когда они будут изъяты. Для обработки нового массива данньк требуется заново ввести константы. Устройство работает следующим образом. Ввод и вывод информации из устройства проводятся одновременно по аходам 17 вводится новый исходный массив, по выходам 15, 16 вьшодится результат. В процессе ввода новой информации из последних двух операндов константы вьщеляются сразу, кактсяькоэти операнды записьшаются во входной регистр 13, последние разряды подаются в сдвиговый регистр. После окончания записи исходного массива в сдвиговом регистре хранится половина разрядов KOHCTaHiibi. Процесс вычисления начинается с выработки в адресном блоке 12 данных адресов двух первых операвдов, которые последовательно выбираются в выходной регистр 2. Управляющие сигналы по выходам 21 и 18 организуют соответственно запись последнах разрядов в сдвиговый регистр и непропускание последни-Х разрядов в промежугочные регистры 5 и 6. После принятия последних разрядов первого операнда по выходу 21 передается сигнал сдвига на требуемое число разрядов, последние разряды второго операнда Заканчивают формирование константы в сдвиговом регистра, и ока передается в регистр 4 хранения комплексны чисел, откуда она поступает в блок умно жения 9 {комплексньрс чисел). К моменту принятия два операнда (комплексные числа), записанные в промежуточных регистрах 5 и 6, попадают в сумматор-вы татель 10, где осуществляется сложение комплексных чисбл, результат операции передается через регистр 7 в блок 9, гд умножается на сформированную константу. Во время умножения комплексные числа, записанные в регистрах 5 и 6, в сумматоре-вычитателе 10 вычитаются, результат записывается в промежуточный регистр 8, далее передается во входной регистр 13 и по адресу адресного блока (данных) 12 записьшается в блок памяти 3. Далее результат умножения записьшается во входной регистр 13, а зате в блок памяти устройства. На этом первый шаг алгоритма БПФ заканчивается. Последовательность опера ции, описанная здесь, относится к шагу с константой 1 . После всех операций с этой константой проводятся операции с константами, номера которых д- В этом случае используются те же константы, что и на предьщущи-х шагах, однако результат дополнительно умножается на мнимое число / j -трГ / (в блоке 11 умножения. Функции этого блока сводятся к перекоммутации вьсхода блока умножения и смене знака; допустим, выход блока 9 умножения/а- Ь|, выход блока 11 умножения на мнимое число /-Ь JCI /, что делается перекоммутацией информационных шин и сменой знака у мнимой части в комплексного числа. Введение блока 1J. позволяет хранить вдвое меньшее число констант и использовать свойство констант; /.2K(i-5). р(-з .e..p((-if).pe|) Необходимость дополнительного умножения на j в данном выражении учитывается блокомумножения на мнимое число. Управляющие сигналы, передаваемые по выходам 19 и 20, соот- ветственно слуксгг: первый - для передачи последних разрядов при вводе двух последних операндов в сдвиговом регистре и для подключения в различные моменты временной диаграммы необходимых входов к аходному рогист- ру (выборки) J второй - для передачи сигналов записи в регистр хранения комплексных чисел из сдвигового регистра подготовленной новой константы. Описанная последовательность работы различных частей устройства выполняется во всах режимах, причем в процессе выполнения шагов второй и следующих итераций, когда выделения констант не происходит, сигналы по выходу 21 блокируют запись в сдвиговый регистр информации, а сигналы по выходу 18 открывают последние разряды промежуточных регистров для приема информации их выходного регистра (выборки). Предложенное устройство при принятой организации вычислительного процесса работает без блоков долговременной памяти, наличие которых требует соответственно собственного адресного блока констант. В результате сокращается оборудование устройства и увеличивает ся его надежность. Преимущества предложенного устройства проявляются при многоканальной обработке информации, когда используется много устройства для реализации БПФ. В этом случае достаточно на все устройства иметь один источник констант, из которого эти константы передаются в каждое из устройств для реализации БПФ. Формула изобретения Устройство для реализации быстрого преобразования Фурье, содернсашее блок управления, выходы которого подключены сосугветственно к управляющим входам входного регистра, первого и второго промежуточных регистров, регистра хранения комплексных чисел, адресного блока, выход которого через блок памяти .подключен ко аходу выходного регистра, первая и вторая группы вькодов которого соответственно через парный и второй промежуточные регистры соединены со входами сумматора-вычитателя, первая группа выходов которого через третий промежуточный регистр соединена с первой группой аходов первого блока умножения, вторая группа выходов сумгматора-вычитатвпя через четвертый промежуточный регистр соединена с первой группой входов входно1о регистра не первой группой выходов устройства, вторая группа входов входного регистра является группой входов устройства, выход регистра хранения комплексных чисел соединен со второй группой входов первого блока умножения, первая группа выходов входного регистра соединена с информационными в.-,одами блока -памяти, отличающееся тем, что, с целью упрощения устройства, оно содержит сдвиговый регистр и второй блок умножения, причем первая и вторая группы входов сдвигового регистра1 подкл чены соответственно k третьей группе , вькодов выходного регистра и второй 7 7 группе выходов входного регистра, управляющий вход сдвигового регистра соединен с соответствующим вьрсодом блока управления, выход сдвигового регистра соединен со входом регистра хранения Комплексных чисел, первая группа выходов первого блока умножения через второй блок умножения подключена к третьей группе входов входного регистра, четвертая группа входов которого и вторая rspynna выходов первого блока умножения подключены ко второй группе выходов устройства. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство CCXiP № 421994, кл. Q06 F; 15/34, 1974. 2,Зарубежная электроника, 1973, № 2, с. 45 (прототип). 1 -н Z r-/fi 7 1Г1--ГГ .--2i 1111 j-jll 1Г/ХХЧг : 2.2 m ХУ v .хул - W // Ч