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

 

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

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

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 734707 (6I ) Донолннтельное к авт. свнд-ву (22) Заявлено 06. 10.77(21) 2530578/18-24 с присоединением заявки РЙ— (23) Приоритет

Опубликовано 15.0 480е Бюллетень Ле 18

Дата опубликования описания 20. 05е80 (51) М. Кл.

GO6 Г 15/34

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

СССР ао делам иэооретеиий к открытий (53) УДК 681, 325 (088. 8) (72) Автор изобретения

И, Г, Грибков (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО

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

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

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

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

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

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

5 734707

Известное устройство имеет сложную схему.

14елью изобретения является упрощение устройства.

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

На фиг. 1 показана структурная схема устройства; на фиг. 2 — приведен граф алгоритма БПФ на фиг. 3 — схема реализации графа алгоритма БПФ.

Устройство (фиг. 1) содержит сдвиговый 1 и выходной 2 регистры, блок памяти 3, регистр 4 хранения комплекснь1х чисел, промежуточные регистры

5-8, первый блок умножения 9,, сумматор-вычитатель 10, второй блок умнож ния 11, адресный блок 12, входной регистр 13, блок управления 14, первую и вторую группы выходов 15, 16, группу входов 17, управляющие. выходы 1822 блок управления. граф алгоритма БПФ (фиг. 2) приведен для исходного массива длиной в

16 значений. На фиг. 2, в частности, показаны индексы исходного массива

23, индексы выходного массива 24, операции умножения на 2 25, различные итерации 26 графа.

Устройство реализует, например, алгоритм БПФ (см. фиг. 2) в последовательности, изображенной на фиг. 3.

Такая последовательность вычисления характеризуется тем, что в процесс вычисления втягиваются ячейки операндов памяти последовательно, причем до включения в вычисление новых двух операндов все вычисления идут c оггерандами, которые уже участвовали в выччслении на предыдуших этапах.

6

Кроме того, номер константы всегда соответствует номеру первого операнда в двухточечном преобразовании Фурье первой итерации.

Из сказанного можно сделать вывод: вместе с исходными данными в память с нужно записывать и константы. Это всегда можно сделать, так как исходные операнды имеют меньшую разрядность, нежели разрядная сетка промежуточных вычислений. Так, например, реальным является -.хранение вместе с опе° . N рандами с номерами 1, 1 — — одной конф станты с номером i в последних четырех разрядах каждого числа (мнимого и действительного). При шестнадцатиразрядной сетке 12 разрядов занимает исходная информация, что вполне достаточно.

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

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

Ввод и вывод информации из устройства проводятся одновременно, по входам

17 вводится новый исходный массив, по выходам 15, 16 выводится результат. В процессе ввода новой информации из последних двух операндов константы выделяются сразу, как только эти операнды записываются во входной регистр 13, последние разряды подаются в сдвиговый регистр. После окончания записи исходного массива в сдвиговом регистре хранится половина разрядов константы.

Процесс вычисления начинается с выработки в адресном блоке 12 данных адресов двух первых операндов, которые последовательно выбираются в выходной регистр 2. Управляющие сигналы по выходам 21 и 18 организуют соответственно запись последних разрядов в сдвиговый регистр и непропускание последних разрядов в промежуточные регистры 5

734707 и 6. После принятия последних разрядов первого операнда по выходу 21 передается сигнал сдвига на требуемое число разрядов, последние разряды второго опранда заканчивают формирование констан-. ты в сдвиговом регистре, и она передается в регистр 4 хранения комплексньцс чисел, откуда она поступает в блок умножения 9 (комплексных чисел). К моменту принятия два операнда (комплексные числа), записанные в промежуточных регистрах 5 и 6, попадают в сумматор-вычитатель 10, где осуществляется сложение комплексных чисбл, результат операции передается через регистр 7 в 6пок 9, где

-умножается на сформированную константу. Во время умножения комплексные числа, записанные в регистрах 5 и 6, в сумматоре-вычитателе 10 вычитаются, результат записывается в промежуточный

20 регистр 8, далее передается во входной регистр 13 и по адресу адресного блока (данных) 12 записывается в блок памяти 3. Далее результат умножения запи25 сывается во входной регистр 13, а затемв 6пок памяти устройства.

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

Я с константами, номера которых 1 — — .

В этом случае используются те же константы, что и на предыдуших шагах, 35 однако результат дополнительно умножается на мнимое число jg = (в блоке 11 умножения. Функции этого блока сводятся к перекоммутации выхода блока умножения и смене знака: допустим, выход блока 9 умножения tС+.) Ь, выход блока ll умножения на мнимое число—

IP — О + d /, что делается перекоммутацией информационных шин и сменой знака у мнимой части в" комплексного числа.

Введение блока 11 позволяет хранить вдвое меньшее число констант и использовать свойство констант:

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

55, - (4)

Ехр (-j yð(- 1е р(-j — )=уекр(— ) Необходимость дополнительного умножения на ) в данном выражении учитывается блоком-умножения на мнимое число. Управляюши сигналы, передаваемые по выходам 19 и 20, соответственно служат: первый — для певедачи последних разрядов при вводе двух последних операндов в сдвиговом регистре и для подключения в различные моменты временной диаграммы необходимых входов к входному р "гистру (выборки) второй — для передачи сигналов запйси в регистр хранения комплексных чисел из сдвигового регистра подготовленной новой константы.

Описанная последовательность работы различных частей устройства выполняется во всех режимах, причем в процессе выполнения шагов второй и следуюших итераций, когда выделения констант не происходит, сигналы по выходу 21 блокируют запись в сдвиговый регистр информации, а сигналы по выходу 18 открывают последние разряды промежуточных регистров для прйема информации ихвыходного регистра (выборки).

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

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

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

-памяти, о т л и ч а ю пт е е с я тем, что, с келью упрощения устройства, оно >s содержит сдвиговый регистр и второй блок умноженйя, причем первая и вторая группы входов сдвигового регистра подхлю чены соответственно к третьей группе, выходов выходного регистра и второй 20

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

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

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

hh 421994, кл. 606 > 15/34, 1874.

2, Зарубежная электроника«, 1973 № 2, с. 45 (прототип).

6 16