Блок формирования адресов для устройства, реализующего быстрое преобразование фурье

 

ОПИСАНИЕ

ИЗОЬРЕтЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 0 548863

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

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

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 07.02.75 (21) 2103463/24 с присоединением заявки № (23) Приоритет

Опубликовано 28.02.77. Бюллетень № 8

Дата опубликования описания 30.03.77 (51) М. Кл. G 06F 15/34

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

Совета Министров СССР (53) УДК 681.325(088.8) an делам изобретений и открытий (72) Авторы изобретения

А. И, Гречишников и А. К. Степанян (71) Заявитель (54) БЛОК ФОРМИРОВАНИЯ АДРЕСОВ

ДЛЯ УСТРОЙСТВА, РЕАЛ ИЗУЮЩЕГО БЫСТРОЕ

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

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

Известен блок формирования адресов, содержащий сдвиговый регистр, счетчик операндов и группу элементов ИЛИ (1).

Недостатком известного блока является его незначительное быстродействие.

Наиболее близким к изобретению по технической сущности и достигаемому результату является блок (2) формирования адресов для устройства, реализующего быстрое преобразование Фурье, содержащий узел реконфигурации счетчика, выход которого соединен с управляющим входом счетчика, узел выдачи адресов, первый информационный вход которого соединен с выходом счетчика, а выход — с выходом блока, причем вход узла реконфигурации счетчика, первый и второй счетные входы счетчика и первый управляющий вход узла выдачи адресов соединены соответственно с первым, вторым, третьим и четвертым входами блока.

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

Цель изобретения — упрощение блока и расширение его функциональных возможностей.

Поставленная цель достигается тем, что блок содержит регистр и группу элементов

ИЛИ, причем выход счетчика соединен с информационным входом регистра и первым входом группы элементов ИЛИ, выход регистра и выход группы элементов ИЛИ соединены соответственно с вторым и третьим пн10 формационными входамп узла выдачи адресов, второй и третий управляющие входы которого, управляющий вход регистра и второй вход группы элементов ИЛИ соединены соответственно с пятым, шестым, седьмым и пер15 вым входами блока.

Структурная схема блока приведена на чертеже.

Блок формирования адресов для устройства, реализующего быстрое преобразование

20 Фурье, содержит узел 1 реконфигурации счетчика, счетчик 2, регистр 3, группу 4 элементов ИЛИ, блок 5 выдачи адресов, первый вход устройства 6, первый 7 и второй 8 счетные входы, управляющий вход регистра 9, 25 первый 10, второй 11 и третий 12 управляющие входы блока выдачи адресов, выход 13 устройства, управляющий вход 14 счетчика, информационные входы 15 — 17 блока выдачи адресов.

30 Блок работает следующим образом.

Адре с а верхние верхние верхние ни>киче нижние нижние верхние нижние оооо

ООО1

00»

1ООО

1001

1011

О1ОО

0101

0»о

0»1

»00

»01

»10

11»

ООО1

0101

1001

1101

ОО1О оо»

0»0

0»1

10»

»10

»11 оооо

OOOl

ОО»

0101

0111

1ООО

1ОО1

10»

»00

»01

»10

1111 оооо

ОО1О

О1ОО

»оо

»10

0001 оо»

0101

О»1

1001

10»

»01

»»

0О

Входной информацией для узла 1 являются признаки итерации (номер итерации), поступающие по входу 6. Узел 1 служит для разъединения (реконфигурации) счетчика 2 на две части, работающие самостоятельно.

Вход 7 — счетный для первой части счетчика 2, вход 8 — для второй части. Выходной информацией счетчика 2 являются коды верхних адресов графа быстрого преобразования

Фурье (БПФ), которые поступают на вход

15 блока 5, на информационный вход регистра 3 и на первый вход группы 4 элементов

ИЛИ.

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

БПФ.

Коды нижних и верхних адресов графа

БПФ в функции от номера итерации приведе1IbI в таблице.

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

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

При реализации безызбыточного алгоритма БПФ .или при одновременном выполнении

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

Прп реализации безызбыточного алгоритма БПФ или при одновременном выполнении

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

Легко заметить, что /г-й и (И вЂ” k)-й коды являются дополнением друг к другу и для них справедливо соотношение N — k=k — 1, где k — 1 — обратный код числа (k — 1).

Таким образом, для формирования кода адреса операнда А (N — /г) необходимо запоминать код адреса (k — 1) из,предыдущего цикла и ооразовывать его обратный код.

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

По сигналу на входе,б счетчик 2 разделяется на две части, причем разрядность первой

Ë4 части (старшие разряды) составляет М, а второй — k — М, где Л4 — порядковый номер итерации, k=log> N — количество разрядов счетчика 2.

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

На каждом элементарном цикле на выходе счетчика 2 формируется код верхнего адреса графа БПФ, который по сигналу на входе

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

Код адреса операндов А (N — k) формируется на инверсных выходах регистра 3, где хранится код адреса А ® в предыдущем цикле, т. е. код k — l.

Счетчик 2 получает приращение только после записи текущего кода и в регистр 3 по сигналу на входе 9. Выдача k-го и (У— г) -го кодов осуществляется по сигналам на входах 10, 12.

548863

Таким образом, изобретение упрощает известное устройство за счет замены сумматора и блока ввода группой элементов ИЛИ.

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

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

Блок формирования адресов для устройства, реализующего быстрое преобразование

Фурье, содержащий узел реконфигурации счетчика, выход которого соединен с управляющим входом счетчика, узел выдачи адресов, первый информационный вход которого соединен с выходом счетчика, а выход — с выходом блока, причем вход узла реконфигурации счетчика, первый и второй счетные входы счетчика и первый управляющий вход узла выдачи адресов соединены соответственно с первым, вторым третьим и четвертым входами блока, отличающийся тем, что, с целью упрощения блока и расширения его функциональных возможностей, он содержит регистр и группу элементов ИЛИ, причем выход счетчика соединен с информационным входом регистра и первым входом группы элементов ИЛИ, выход регистра и выход группы элементов ИЛИ соединены соответственно с вторым и третьим информационными входами узла выдачи адресов, второй и третий управляющие входы которого, управляющий вход регистра и второй вход группы элементов ИЛИ соединены соответственно с

15 пятым,,шестым, седьмым и первым входами блока.

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

1. Вьюхина Н. Н. Индексное устройство.

20 «Автоматрия», Ко 3, 1973, с. 34.

2. Авт. св. Ме 430381, кл. С 06 9/00, 1971 (прототип) .

548863

Составитель Ф. Шагиахметов

Техред А. Камышиикова Корректор Е. Хмелева

Редактор С. Заика

Типография, пр. Сапунова, 2

Заказ 436/18 Изд. Кв 247 Тираж 899 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, %-35, Раушская наб., д. 4/5