Блок формирования адресов для устройства, реализующего быстрое преобразование фурье Советский патент 1977 года по МПК G06F17/14 

Входной информацией для узла 1 являются признаки итерации (номер итерации), поступающие по входу 6. Узел 1 служит для разъединения (реконфигурации) счетчика 2 на две части, работающие самостоятельно. Вход 7 - счетный для первой часта счетчика 2, вход 8 - для второй части. Выходной информацией счетчика 2 являются коды верхних адресов графа быстрого преобразования Фурье (БПФ), которые поступают па вход IS блока 5, на ипформационный вход регистра 3 и на первый вход группы 4 элементов ИЛИ.

С выхода группы 4 элементов ИЛИ на вход 17 блока 5 поступают коды адресов графа БПФ, а с выхода регистра 7 снимаются коды вторых операндов специальной итерации, используемой при выполнении так называемых безызбыточных, алгопитмов БПФ.

Коды нижних и верхних адресов графа БПФ в функции от номера итерации ириведены в таблице.

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

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

При реализации безызбыточного алгоритма БПФ или при одновременном выполнении БПФ над дву.мя вещественными процессами стандартных итераций БПФ дополняется специальной итерацией, для организации которой необходимо формировать коды адресов двух операндов A(k) и Л (), , 2, ..., /V/2-1; , N-2, ..., Nf2+l.

Легко заметить, что k-й и (/V-А)-и коды являются дополнением друг к Другу и для

ни.х справедливо соотношение k-1,

где k-1 - обратный код числа (k-1).

Таким образо.м, для фор.мирования кода адреса операнда А (N-k необходимо запоминать код адреса (-1) из предыдущего цикла и образовывать его обратный код. Устройство работает следующим образом. По сигналу на входе .6 счетчик 2 разделяется на две части, причем разрядность первой уМ части (старшие разряды) составляет М, а второй - k-М, где М - иорядковый номер итерации, - количество разрядов счетчика 2.

Первая часть счетчика 2 изменяет свое состояние в каждый элементарный цикл работы (цикл работы - это фор.мирование одной пары адресов). Вторая часть счетчика 2 изменяет свое состояние только в моменты переходов.

Па каждом эле.ментарном цикле на выходе счетчика 2 формируется код верхнего адреса графа БПФ, который по сигиалу на входе 7 через блок 5 выдается на выход 13. Код нижнего адреса графа БПФ формируется на выходе группы 4 элементов ИЛИ, который поступает па выход 13 по сигналу на входе 11.

Адреса

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

Код адреса операндов Л (Л-k) формируется на инверсных выходах регистра 3, где хранится код адреса Л (k) в иредыдуще.м цикле, т. е. код k-I.

Счетчик 2 получает приращение только после записи текущего кода k в регистр 3 по сигналу на входе 9. Выдача -го и {N- /г)-го кодов осуществляется по сигналам па входах 10, 12. Таким образом, изобретение упрощает известное устройство за счет замены сумматора и .блока ввода группой элементов ИЛИ. Введение регистра обеспечивает возможность реализации эффективных, так называемых безызбыточмых алгоритмов БПФ, расширяет функциональные возможности известного устройства. Формула изобретения Блок формирования адресов для устройства, реализующего быстрое преобразование Фурье, содержащий узел реконфигурации счетчика, выход которого соединен с управляющ«м входом счетчика, узел выдачи адресов, первый информационный вход которого соединен с выходом счетчика, а выход - с выходом блока, причем вход узла реконфигурации счетчика, первый и второй счетные входы счетчика и первый управляющий вход узла выдачи адресов соединены соответственно с -первым, вторым третьим и четвертым входами блока, отличающийся тем, что, с целью упрощения блока и расширения его функциональных возможностей, он содержит регистр и группу элементов ИЛИ, причем выход счетчика соединен с информационным входом регистра и первым входом группы элементов ИЛИ, выход регистра и выход группы элементов ИЛИ соединены соответственно с вторым и третьим информационными входами узла выдачи адресов, второй и третий управляющие входы которого, управляющий вход регистра и второй вход группы элементов ИЛИ соединены соответственно с пятым, шестым, седьмым и первым входами блока. Источники информации, принятые во внимание при экспертизе изобретения 1.Вьюхина Н. Н. Индексное устройство. «Автоматрия, № 3, 1973, с. 34. 2.Авт. св. № 430381, кл. С 06 9/00, 1971 (прототип).

//