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

ОПИСАНИЕИЗОЬЕЕтЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 01 548863 Союз Советских Социалистических Республик) Заявлено 07,02.75 (21) 2103463/2 с присоединением заявкиГосударственный комитет Совета Министров СССР по делам изобретенийи открытий 23) Приоритет(53) УДК 681.325(088.8) Бюллетеньписания 30.03.7 Опубликовано 28.02 ата опубликования Авторыизобретен И, Гречишников и А, К. Степанян(71) Заявител 4) БЛОК ФОРМИРОВАНИЯ АДРЕСОВУСТРОЙСТВА, РЕАЛ ИЗУЮЩЕГО БЫСТРПРЕОБРАЗОВАНИЕ ФУРЬЕ Д етение относится к облтехники и может бытьтроении устройства,преобразование Фурье. ен блок формирования й сдвиговый регистр,и группу элементов ИЛ Изобр тельной при пос быстроеИзвес деркащ рандов расширенстей.Поставленная цель достигается тем, чтоблок содержит регистр и группу элементовИЛИ, причем выход счетчика соединен с информационным входом регистра и первымвходом группы элементов ИЛИ, выход регистра и выход группы элементов ИЛИ соединены соответственно с вторым и третьим информационными входамп узла выдачи адресов, второй и третий управляющие входы которого, управляющий вход регистра и второйвход группы элементов ИЛИ соединены соответственно с пятым, шестым, седьмым и первым входами блока,Структурная схема блока приведена начертеже.Блок формирования адресов для устройства, реализующего быстрое преобразованиеФурье, содержит узел 1 реконфигурации счетчика, счетчик 2, регистр 3, группу 4 элементов ИЛИ, блок 5 выдачи адресов, первыйвход устройства 6, первый 7 и второй 8 счетные входы, управляющий вход регистра 9,первый 10, второй 11 и третий 12 управляющие входы блока выдачи адресов, выход 13устройства, управляющий вход 14 счетчика,информационные входы 15 - 17 блока выдачиадресов.Блок работает следующим образом,асти вычислииспользовано реализ ющеголяется его10 едостатком известного блока явначительное быстродействие.Наиболее близким к изобретению по технической сущности и достигаемому результату является блок (2 формирования адресов для устройства, реализующего быстрое преобразование Фурье, содержащий узел ре конфигурации счетчика, выход которого соединен с управляющим входом счетчика, узел выдачи адресов, первый информационный вход которого соединен с выходом счетчика, а выход - с выходом блока, причем вход уз ла реконфигурации счетчика, первый и второй счетные входы счетчика и первый управляющий вход узла выдачи адресов соединены соответственно с первым, вторым, третьим и четвертым входами блока. 25Недостатками известного блока являются сложность его построения и невозможность реализации безызбыточных алгоритмов быстрого преобразования Фурье.Цель изобретения - упрощение блока и 30 ие его функциональных возможно5488113 35 Адре с а верхние верхние верхние никиче нижние нижние верхние нижние оооо ООО 1 ОО 1 О 0011 1 ООО 1001 1010 1011 О 1 ОО О 1 О 1 О 11 О 0111 11 ОО 1101 111 О 1111 оооо ООО 1 О 1 ОО 0101 1000 1001 1100 1101 ОО 1 О ОО 11 О 11 О О 111 1010 1011 1110 1111 оооо 0001 0010 ОО 11 0100 0101 0110 0111 1 ООО 1 ОО 11010 1011 1100 1101 1110 1111 оооо ОО 1 О О 1 ОО О 11 О 1000 1010 11 ОО 1110 ООО 1 ОО 11 О 1 О 1 О 111 1001 1011 11 О 1 1111 0 О 65 Входной информацией для узла 1 являются признаки итерации (номер итерации), поступающие по входу 6. Узел 1 служит для разъединения (реконфигурации) счетчика 2 на две части, работающие самостоятельно. Вход 7 - счетный для первой части счетчика 2, вход 8 - для второй части. Выходной информацией счетчика 2 являются коды верхних адресов графа быстрого преобразования Фурье (БПФ), которые поступают на вход 15 блока 5, на информационный вход регистра 3 и на первый вход группы 4 элементов ИЛИ.С выхода группы 4 элементов ИЛИ на вход 17 блока 5 поступают коды нижних адресов графа БПФ, а с выхода регистра 7 снимаются коды вторых операндов специальной итерации, используемой при выполнении так называемых безызбыточных, алгопитмов БПФ.Коды нижних и верхних адресов графа БПФ в функции от номера итерации приведены в таблице.Очевидно, чго коды нижних и верхних адресов в -й итерации отличаются лишь в одном разряде, причем номер этого разряда в течение всей итерации постоянен и равен номеру итерации. Поэтому, если в кодах верхних адресов значение данного разряда заменить на противоположный, то получим последовательность нпкних адресов для данной итерации,Таким образом, в первой ятерацип для формирования кодов нижних адресов необходимо произвести логическое сложение старшего разряда верхнего адреса с признаком первой итерации, во второй итерации - второго разряда, начиная со стороны старшего, с признаком второй итерации и т, д. При реализации безызбыточного алгоритма БПФ или при одновременном выполнении БПФ над двумя вещественными процессами по окончании стандратных итераций БПФ организуется специальная итерация. При этом счетчик 2 формирует коды адресов операндов А . Для этой цели управление счетчика 2 осуществляется по входу 8, т. е, счетчик 2 в каждый элементарный цикл получает приращение на единицу. 5 10 15 20 25 30 Прп реализации безызбыточного алгоритма БПФ или при одновременном выполнении БПФ над двумя вещественными процессамп стандартных итераций БПФ дополняется специальной итерацией, для организации которой необходимо формировать коды адресов двух операндов А (А) и А (Л - й), 1=1, 2, Л/2 - 1; У - 1=У - 1, Л - 2 ЛЧ 2+1Легко заметить, что й-й и (И - И)-й коды являются дополнением друг к другу и для них справедливо соотношение М - Уг=lг - 1, где А - 1 - обратный код числа (Й - 1).Таким образом, для формирования кода адреса операнда А (У - Уг) необходимо запоминать код адреса (Уг - 1) из,предыдущего цикла и ооразовывать его обратный код.Устройство работает следующим образом.По сигналу на входе,б счетчик 2 разделяется на две части, причем разрядность первой М части (старшие разряды) составляет М, а второй - А - М, где М - порядковый номер итерации, Й=1 одв Л 7 - количество разрядов счетчика 2.Первая часть счетчика 2 изменяет свое состояние в каждый элементарный цикл работы (цикл работы - это формирование одной пары адресов). Вторая часть счетчика 2 изменяет свое состояние только в моменты переходов. 1-1 а каждом элементарном цикле на выходесчетчика 2 формируется код верхнего адреса графа БПФ, который по сигналу на входе 7 через блок 5 выдается на выход 13. Код нижнего адреса графа БПФ формируется на выходе группы 4 элементов ИЛИ, который поступает на выход 13 по сигналу на входе 11. Код дРеса опеРандов А (У - ь) ф, иется на инверсных выходах регистра 3, где хранится код адреса Ав предыдущем цикле, т. е. код Й - 1. Счетчик 2 получает приращение только после записи текущего кода й в регистр 3 по сигналу на входе 9, Выдача lг-го и (У - Й)-го кодов осуществляется по сигналам на входах 10, 12, 548863Таким образом, изобретение упрощает известное устройство за счет замены сумматора и блока ввода группой элементов ИЛИ. Введение регистра обеспечивает возможность реализации эффективных, так называемых безызбыточных алгоритмов БПФ, расширяет функциональные возможности известного устройства. Формула изобретенияБлок формирования адресов для устройства, реализующего быстрое преобразование Фурье, содержащий узел реконфигурации счетчика, выход которого соединен с управляющим входом счетчика, узел выдачи адресов, первый информационный вход которого соединен с выходом счетчика, а выход - с выходом блока, причем вход узла реконфигурации счетчика, первый и второй счетные входы счетчика и первый управляющий вход узла выдачи адресов соединены соответственно с первым, вторым третьим и четвертым входами блока, отличающийся тем, что, с целью упрощения блока и расширения его функциональных возможностей, он содержит регистр и группу элементов ИЛИ, причем выход счетчика соединен с информационным входом регистра и первым входом группы элементов ИЛИ, выход регистра и выход группы элементов ИЛИ соединены соответст венно с вторым и третьим информационнымивходами узла выдачи адресов, второй и третий управляющие входы которого, управляющий вход регистра и второй вход группы элементов ИЛИ соединены соответственно с 15 пятымшестым, седьмым и первым входамиблока,Источники информации, принятые во внимание при экспертизе изобретения1. Вьюхина Н. Н. Индексное устройство.20 Автоматрия, Мо 3, 1973, с. 34.2. Авт. св. Мо 430381, кл. С 06 9/00, 1971548863 Составитель ф, ШагиахметовТехред А, Камышиикова Корректор Е Хмелева Редактор С. Заика Типография, пр. Сапунова, 2 Заказ 436/18 Изд. ЛЪ 247 Тираж 899 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, Ж.35, Раушская наб., д. 4/5