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

 

Изобретение относится к автоматике и вычислительной технике. Цель, изобретения - упрощение устройства. Для достижения цели устройство дополнительно содержит (R-1)-разрядный сдвиговый регистр и элемент ИЛИ. Устройство работает в двух режимах: первый соответствует формированию адресов , по которым записываются отсчеты анализируемого входного сигнала; второй режим соответствует формированию адресов при выполнении быстрого преобразования Фурье. Изобретение может быть использойано в системах цифровой обработки сигналов при построении устройств, реализующих преобразование Фурье. 1 ил, 3 табл. (Я ГчЭ со 00 о

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (11) (51) 4 С 06 F 15/3g3

Г с

) 1 ж с

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3776984/24-24 (22) 06.08.84 (46) 23.05.86. Бюл. №- 19 (71) Таганрогский радиотехнический институт им. Б.Д.Калмыкова (72) И.И.Итенберг, С.И.Алферов и В.В.Леонов (53) 681.32(088.8) (56) Авторское свидетельство СССР

¹ 1062714,,кл. С 06 F 15/332, 1983.

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

¹ 1084808, кл . G 06 F 15/332, 1984 . (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

АДРЕСОВ АЛГОРИТМА БЫСТРОГО ПРЕОБРАЗОВАБ1Я ФУРЬЕ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — упрощение устройства.

Для достижения цели устройство дополнительно содержит (1(-1)-разрядный сдвиговый регистр и элемент ИЛИ. Устройство работает в двух режимах: первый соответствует формированию адресов, по которым записываются отсчеты анализируемого входного сигнала; второй режим соответствует формированию адресов при выполнении быстрого преобразования Фурье. Изобретение может быть использовано в системах цифровой обработки сигналов при построении устройств, реализующих преобразова- Ж ние Фурье. 1 ил, 3 табл.

1233167

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

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

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

Устройство содержит сдвигавый регистр 1 (кода итерации), ныходы

2„ - 2 разрядов регистра 1, коммутаторы 3, — 3, счетчик 4 адресов, выходы 5, — 5 разрядов счетчика ад— ресов, выход 6 переполнения счетчика адресов, элемент ИЛИ 7, вход 8 начального значения (логической единицы) устройства, вход 9 задания режима работы устройства, вход 10 сброса устройства, установочный вход 11 устройства, тактовый вход 12 устройства, выходы 13„ — 13 разрядов адреса устройства.

Устройство работает в двух режимах.

Первый режим определяется "нуле-вым" потенциалом на входе 9 задания режима работы устройства и соответствует формиРованию адресов, по которым записываются отсчеты анализируемого входного сигнала. Начальное состояние устройства в первом режиме устанавливается следующим образом.

IIo импульсу, приходящему на вход 10 с броса устройства, устанавливаются в нулевое состояние счетчик 4 адресов и сдвиговый регистр 1 (кода итерации) . Вслед за этим приходит импульс на вход 11 устройства, который появляется на выходе элемента ИЛИ 7 и поступает на тактовый вход регист— ра 1 (кода итерации) . "Нулевой" потенциал, присутствующий на входе 9 задания режима работы устройства, поступает на управляющий вход регистра 1 (кода итерации) и определяет режим параллельного занесения информации в этот регистр. Так как на

° всех информационных входах параллельного занесения регистра 1 (кода итерации), подключенных к входу 8 yc;;..— райс тва, присутствует па| ическая единица, та по импульсу на тактовом входе регистр 1 (кода итерации) устанав— ливается в состояние все единицы

5 8 результате к выходам 13 — 13

1 Р, разрядан адреса. устройства подключаются через соответствующие коммутаторы 3, — 3 выходы 5„ — 5 разрядов счетчика адресов н порядке возрастания номера разряда.

Записываемым отсчетам анализируемого входного сигнала соответствуют импульсы на тактовом входе 12 устройства, поступающие на второй вход счетчика 4 адресов. Таким образом, н первом режиме устройство формирует адреса, задаваемые счетчиком 4 адpecos и равные номерам отсчетов ана— лизируемога входного сигнала.

Второй режим работы устройства определяется единичным потенциалом на входе 9 задания режима работы устройства и соответствует формированию адрес.ов при выполнении быстрого

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

Принцип адресации, используемый в устройстве, заключается н следующем. Адреса операндов для каждой базавой операции "бабочки" быстрого преобразования Фурье определяются в полном соответствии с графом быстрого преобразования Фурье. Последовательность выполнения "бабочек в пределах каждой итерации определяется путем последовательного выделения в графе быстрого преобразования Фурье групп ч па - (— размерность быстрого пре2Р образования Фурье Р— номер выполняемой итерации) "бабочек и двоичной инверсии номеров "бабочек" в пределах группы. В табл, 1 представлен пример определения последовательности адресов операндов при выполнении второй итерации 16-точечного быстрого пресбразования Фурье (т.е. N =16, р 1

123 3167

Таблица 1

Номер "бабочки"

Номер "ба бочки" со

Новый номер

"бабочки"

Номер группы

Адрес операнда согласнэ

) графу

ПоследоваПоследовательность адресов тельность

"бабочек в группе в группе гласно графу

2 3

О

О

12

1О

13

14

В результате для формирования не- 4> обходимых адресов достаточно изменить положение младшего разряда счетчика 4 адресов относительно его остальных разрядов в зависимости от номера выполняемой итерации. На первой итера- 11 ции достаточно подключить выход 5, младшего разряда счетчика адресов к выходу 13 старшего разряда адреса устройства, а выходы 5 — 5 остальных разрядов счетчика адресов — сост" ветственно к выходам 13, — 13 разрядов адреса устройства. На второй итерации необходимо подключить выход 5, младшего разряда счетчика адресов к выходу 13 „ (R-1)-ro разряда устройства, выход 5 старшего разряда счетчика адресов — к выходу 13

R старшего разряда адреса устройства, а выходы 5 — 5„ остальных разрядов счетчика адресов — соответственно к выходам 13„ — 13„ разрядов адреса устройства. На третьей итерации необходимо подключить выход 5, младшего разряда счетчика адресов к выходу 13 (R-2)-го разряда адре/ са устройства, выходы 5, 5, двух старших разрядов счетчика адресов

123 31Ч

Т а 6 л и ц а 2

Первый управляющий

Номер информацив

Второй управ ляющий вход онного входа, коммутиt0 руемого на выход

О

О

Та блица 3

Управляющий вход соответственно к выходам 13, 13, двух старших разрядов адреса устройства, выходы 5> — 5 > остальных разрядов счетчика адресов — соответственно к выходам 13, — 13 „ разрядов адреса устройства и т.д.

Таким образом, на К -м этапе пре—

Ю образования порядок следования разрядов счетчика 4 адресов на выхо-дах 13 — 13 разрядов адреса устройства оказывается первоначальным (как при записи входной информации в первом режиме).

Указанная перегруппировка разрядов счетчика 4 адресов происходит с помощью коммутаторов 3 — 3 на выхо1 К> 20 де каждого из которых появляется один из трех (двух — для коммутатора 3, 3,. ) входных информационных сигналов .

Управление переключением коммутаторов осуществляется сдвиговым регист25 ром 1 (кода итерации) с частотой, равной частоте переполнения счетчика 4 адресов.

"Единичный" потенциал, присутст30 вующий на входе 9 задания режима работы устройства, поступает на управляющий вход регистра 1 (кода итерации) и определяет режим последовательного занесения информации в этот регистр. Сигналам считывания операндов для обработки соответствуют имt пульсы на тактовом входе 12 устройства, поступающие на второй вход счетчика 4 адресов Импульсы переполнения с выхода 6 переполнения счетчи40 ка 4 адресов проходят на выход элемента ИЛИ 7 и поступают на тактовый вход регистра 1 (кода итерации). Так как на информационном входе последо45 вательного занесения регистра 1 (кода итерации), подключенном к входу 8 устройства, присутствует логическая единица, то регистр 1 (кода итерации) последовательно заполняет 50 ся единицами со стороны младшего разряда. Таким образом, на последней итерации сдвиговый регистр 1 кода итерации находится в состоянии все единицы

Закон коммутации для коммутаторов 3, -- 3 представлены в табл.2, а для коммутаторов 3,, 3< — в табл.3.

Номер информационного входа, коммутируемого на выход

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

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

Фурье, содержащее P,(R — разрядность адреса) коммутаторов и счетчик адре— сов, счетный вход которого является тактовым входом устройства, а выход

j -го (1 =1,R) коммутатора является выходом,! -го разряда адреса устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит элемент ИЛИ и (R-1)-разрядный сдвиговый регистр, выход i — го (i =1, Я вЂ” 1) разряда которого подключен к первому управляющему входу (R+1-1) го коммутатора и к второму управляющему входу (R — l) -го коммутатора, первый и второй информационные входы К -ro коммутатора подключены к выходам соответственно первого и R -го разрядов счетчика адресов, выход (+1)-го разряда которого подключен к первому информационному входу i-го коммутаСоставитель А.Баранов

Редактор С.Саенко Техред О.Сопко Корректор C.Øåêìàð

Заказ 2772/51 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4 тора, второй информационный вход которого подключен к выходу первого разряда счетчика адресов, выход (-го разряда которого (f =2, а -1) подключен к третьему информационному входу -ro коммутатора, выход переполнения счетчика адресов подключен к первому входу элемента ИЛИ, выход которого подключен к тактовому входу 10 сдвигового регистра, вход разрешения записи которого является входом задания режима работы устройства, входом начального значения которого являются соединенные между собой входы Я вЂ” 1)— разрядного сдвигового регистра, вход обнуления которого соединен с входом обнуления счетчика адресов и является входом сброса устройства, установочным входом которого является второй вход элемента ИЛИ.