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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 9) (1) в) 4 С 06 Р 15 35 Гс ОПИСАНИЕ ИЗОБРЕТЕН ЛЬСТВ ТОРСНОМУ СВИД(21) 3776984/ (22) 06,08.84 (46) 23.05,86 (71) Таганрог институт им. (72) И.И.Итен и В.В.Леонов (53) 681.32(0 В 19 кии радиот .Д. Калмыко ерг, С.И.Ал чески ер свидетельство СССРС 06 Г 15/332, 1983идетельство СССРС 06 Р 15/332, 1984(54) УСТРОЙСТВ АДРЕСОВ АЛГОРИ ЗОВАВ 1 Я ФУРЬЕ СУДАРСТВЕННЫИ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(57) Изобретение относится к автоматике и вычислительной технике, Цель изобретения - упрощение устройства. Для достижения цели устройство дополнительно содержит Я)-разрядный сдвиговый регистр и элемент ИЛИ, Устройство работает в двух режимах: первый соответствует формированию адресов, по которым записываются отсчеты анализируемого входного сигнала; вто. рой режим соответствует формированию адресов при выполнении быстрого преобразования Фурье. Изобретение может быть использовано в системах цифровой обработки сигналов при построении устройств, реализующих преобразование фурье. 1 ил, 3 табл.Изобретение относится к автоматике и вычислительной технике и может быть.использовано в системах цифровой обработки сигналов при построении устройств, реализующих быстрое преобразование Фурье.Цель изобретения - упрощение устройства.На чертеже представлена функциональная схема устройства для формирования адресов алгоритма быстрого преобразования Фурье.Устройство содержит сдвиговый регистр 1 (кода итерации), выходы 2 - 2 разрядов регистра 1, коммутаторы 3, - 3 , счетчик 4 адресов, выходы 5, - 5 в разрядов счетчика адресов, выход б переполнения счетчика адресов, элемент ИЛИ 7, вход 8 начального значения (логической единицы) устройства, вход 9 задания режима работы устройства., вход 10 сброса устройства, установочный вход 11 устройства, тактовый вход 12 устройства, выходы 13 - 13 разрядов адреса устройства.Устройство работает в двух режимах.Первый режим определяется "нуле-. вым" потенциалом на входе 9 задания режима работы устройства и соответствует формированию адресов, по которым записываются отсчеты анализируемого входного сигнала. Начальное состояние устройства в первом режиме устанавливается следующим образом,По импульсу, приходящему на вход 10 сброса устройства, устанавливаются в нулевое состояние счетчик 4 адресов и сдвиговый регистр 1 (кода итерации). Вслед за этим приходит импульс на вход 11 устройства, который появляется на выходе элемента ИЛИ 7 и поступает на тактовый вход регистра 1 (кода итерации). "Нулевой" потенциал, присутствующий на входе 9 задания режима работы устройства, поступает на управляющий вход регистра 1 (кода итерации) и определяет режим параллельного занесения информации в этот регистр. Так как навсех информационных входах параллельного занесения регистра 1 (кода итерации), подключенных к входу 8 устройстна, присутствует логическая единица, то по импульсу на тактовом входе регистр 1 (кода итерации) устанав -ливается в состояние "все единицы5 В результате к выходам 13 - 13разрядов адреса. устройства подключаются через соответствующие коммутаторы 3, - Зк выходы 5 - 5 разрядовсчетчика адресов в порядке возрастания номера разряда,Записываемым отсчетам анализируемого входного сигнала соответствуютимпульсы на тактовом входе 12 устройства, поступающие на второй входсчетчика 4 адресов. Таким образом,н первом режиме устройство формируетадреса, задаваемые счетчиком 4 адресов и равные номерам отсчетов ана -лизируемога входного сигнала,Второй режим работы устройстваопределяется единичным потенциаломна входе 9 задания режима работыустройства и соответствует формированию адрес.ов при выполнении быстрого25епреобразования Фурье. Начальное состояние устройства в этом режиме устанавливается по импульсу на входе 10сброса устройства, при этом и счетчик 4 адресов, и сдвиговый регистр 1ЗО (кода итерации) устанавливаются в состояние все нули. Принцип адресации, используемый в устройстве, заключается в следующем. Адреса операндов для каждой базовой операции "бабочки" быстрого преобразования Фурье определяются в полном соответствии с графом быстрого преобразования Фурье. Последовательность выполнения "бабочекв пределах каждой итерации определяется путем последовательного выделения в графе быстрого преобразования Фурье групп по - ( - размерность быстрого пре 2 Робразования Фурье, Р - номер выполняемой итерации) "бабочеки двоичной инверсии номеров "бабочек" в пределах группы. В табл, 1 представлен пример определения последовательности адресов операндов при выполнении второй итерации 1 б-точечного быстрого преобразования Фурье (т,е. М =1 б, р - "э12331 б 7 Таблица 1 Номер "бабочки" Номер "ба бочки" со Новый номер"бабочки" Номергруппы Адрес операнда согласнэграфу тельность "бабочектельностьадресов в группе в группе гласнографу 5 2 3 О О О О О О 12 12 1 О 13 10 14 В результате для формирования не обходимых адресов достаточно изменить положение младшего разряда счетчика 4 адресов относительно его остальных разрядов в зависимости от номера выполняемой итерации. На первой итера О ции достаточно подключить выход 5, младшего разряда счетчика адресов к выходу 13 старшего разряда адреса устройства, а выходы 5 - 5 остальных разрядов счетчика адресов - сост"б ветственно к .выходам 13, - 13 разрядов адреса устройства. На второй итерации необходимо подключить выПоследова- Последоваход 5, младшего разряда счетчика ад- ресов к выходу 13(й)-го разряда устройства, выход 5 старшего разряда счетчика адресов - к выходу 13 старшего разряда адреса устройства, а выходы 5 - 5остальных разрядов счетчика адресов - соответственно к выходам 13 - 13 разрядов адреса устройства. На третьей итерации необходимо подключить выход 5, младшего разряда счетчика адресов к выходу 13(Р)-го разряда адре/ са устройства, выходы 5, 5 к, двух старших разрядов счетчика адресов1233167 Таблица 2 Первый управляюций вход Номер информаци -Второй управ ляющий вход онного входа,коммути 10 руемогона выход О15 О Та бли ца 3 Уп р а вля ющийвход соответственно к выходам 13, 13,двух старших разрядов адреса устройства, выходы 5 - 5остальных разрядов счетчика адресов - соответственно к выходам 13, - 13разрядовадреса устройства и т.д. Таким образом, на 1 -м этапе пре - образования порядок следования разрядов счетчика 4 адресов на выхо.- дах 13 - 13 разрядов адреса устройства оказывается первоначальным (как при записи входной информации в первом режиме). Указанная перегруппировка разрядов счетчика 4 адресов происходит с помощью коммутаторов 3 - 3 на выхо 20 де каждого из которых появляется один из трех (двух - для коммутатора 3 , 3) входных информационных сигналов. Управление переключением коммутаторов осуществляется сдвиговым регист 25 ром 1 (кода итерации) с частотой, равной частоте переполнения счетчика 4 адресов."Единичный" потенциал, присутст 30вующий на входе 9 задания режима работы устройства, поступает на управляющий вход регистра 1 (кода итерации) и определяет режим последовательного занесения информации в этот регистр. Сигналам считывания операндов для обработки соответствуют импульсы на тактовом входе 12 устройства, поступающие на второй вход счетчика 4 адресов. Импульсы переполнения с выхода 6 переполнения счетчи 40 ка 4 адресов проходят на выход элемента ИЛИ 7 и поступают на тактовый вход регистра 1 (кода итерации). Так как на информационном входе последо 45 вательного занесения регистра 1 (кода итерации), подключенном к входу 8 устройства, присутствует логическая единица, то регистр 1 (кода итерации) последовательно заполняет 50 ся единицами со стороны младшегоразряда. Таким образом, на последней итерации сдвиговый регистр 1 кода итерации находится в состоянии все единицыЗакон коммутации для коммутаторов 3; - 3 япредставлены в табл.2, а для коммутаторов 3 3 - в табл.3. Номер информационноговхода, коммутируемогона выход Формула изобретения Устройство для формирования адресов алгоритма быстрого преобразования Фурье, содержащее ( К - разрядность адреса) коммутаторов и счетчик адресов, счетный вход которого является тактовым входом устройства, а выход ,1-го (,1 =1,Р) коммутатора является выходом, -го разряда адреса устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит элемент ИЛИ и -1)-разрядный сдвиговый регистр, выход -го ( =1, к -1) разряда которого подключен к первому управляющему входу (1+1-)-го коммутатора и к второму управляющему входу Я - ) -го коммутатора, первый и второй информационные входы К -го коммутатора подключены к выходам соответственно первого и К -го разрядов счетчика адресов, выход ( +1)-го разряда которого подключен к первому информационному входу -го коммутаСоставитель А.БарановРедактор С.Саенко Техред О.Сопко Корректор С.Шекмар Заказ 2772/51 тираж 671 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Производственно-полиграфическое предприятие, г,ужгород, ул,Проектная, 4 тора, второй информационный вход которого подключен к выходу первогоразряда счетчика адресов, выход 1 -горазряда которого ( =2, к - 1) подключен к третьему информационному входу-го коммутатора, выход переполнения счетчика адресов подключен к первому входу элемента ИЛИ, выход которого подключен к тактовому входу 1 Осдвигового регистра, вход разрешения записи которого является входом задания режима работы устройства, входомначального значения которого являютсясоединенные между собой входы Я - 1)разрядного сдвигового регистра, входобнуления которого соединен с входомобнуления счетчика адресов и является входом сброса устройства, установочным входом которого являетсявторой вход элемента ИЛИ.