Устройство для формирования адресов алгоритма быстрого преобразования Фурье Советский патент 1986 года по МПК G06F17/14 G06F9/34 

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

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

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

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

2. - 2.

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

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

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

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

ройства, присутствует лог-ическая единица, то по импульсу на тактовом входе регистр (кода итерации) устанавливается в состояние все единицы,

В результате к выходам 13 - 13

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

Записываемым отсчетам анализируемого входного сигнала соответствуют импульсы на тактовом входе 12 устройства, поступающие на второй вход

счетчика 4 адресов. Таким образом, Б первом режиме устройство формирует адреса5 задавд.емые счетчиком 4 адресов и равные номерам отсчетов анализируемого входного сигнала.

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

0 (кода итерации) устанавливаются в состояние все нули,

Принцип адресации, используемый в устройстве, заключается в следуюs- щем. Мреса операндов для каждой ба- зовой операции бабочки быстрого преобразования Фурье определ;1ются в полном соответствии с графом быстрого преобразования Фурье. Последователь д кость вьшолнения бабочек в пределах каждой итерации определяется путем последовательного вьщеления в графе быстрого преобразования Фурье групп

N..

по (, - размерность быстрого пре- 45 2Р

образования Фурье, Р - номер выполняемой итера)р1и) бабочек и двоичной инверсии номеров бабочек в пределах группы, в табл. 1 представлен 52 пример определения последовательности адресов операндов при вьтолнении азторой итерации 16-точечного быстрого преобразования Фурье (т.е.Ы 16,

F

2)

В результате для формирования не- обходимых адресов достаточно изменить положение младшего разряда счетчика 4 адресов относительно его остальных разрядов в зависимости от номера выполняемой итерации. На первой Итера- ции достаточно подключить выход 5 младшего разряда счетчика адресов

к выходу 13,-, старшего разряда адреса

к

устройства, а выходы 5 - 5 остальных разрядов счетчика адресов - соот- ветственно к выходам 13 - 13 разрядов адреса устройства. На второй итерации необходимо подключить выТаблица 1

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

13,,

R

двух старших разрядов адреса устройства, выходы 5 - 5g.Q остальных разрядов счетчика адресов - соответственно к выходам 13, - разрядов адреса устройства и т.д.

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

Указанная перегруппировка разрядов счетчика 4 адресов происходит с помощью коммутаторов

1

на выхо Rде каждого из которых появляется оди

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

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

гистр дится Закон торов ны в торов

3,- в

табл.3.

Таблица 2

ТаблицаЗ

Управляющий вход

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

30

О 1

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

Устройство для формирования адресов алгоритма быстрого преобразования Фурье, содержащее R(R - разрядность адреса) коммутаторов и счетчик адресов, счетный вход которого является тактовым входом устройства, а выход J-го (,,R) коммутатора является выходом J-го разряда адреса устройства, отличающееся тем, что, с целью упрощения устройства, оно содержит элемент ИЛИ и (R-1)-разрядный :1виговый регистр, выход -го (, R-1) разряда которого подключен к первому управляющему входу (R.-;-1-i )-го коммутатора и к второму управляющему входу (R-i)-ro коммутатора, первый и вт-орой информационные входы R -го коммутатора подключены к выходам соответственно первого и R-ro разрядов счетчика адресов, выход (i+1)-ro разряда которого подключен к первому информадаонному входу 1-го коммутатора, второй ияформагу онньтй вход которого подключен к выходу первого разряда счетчика адрес В выход Р-го разряда которого (,) подключен к третьему информащюнному входу f-ro коммутатора, выход переполнения счетчика адресов подключен к первому входу элемента ИЛИ, выход которого подключен к тактовому входу сдвигового регистра, вход разрешения

Редактор С.Саенко

Составитель А.Баранов

Техред О.Сопко Корректор С.Шекмар

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

ВНШПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

.Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4

записи которого является входом задания режима работы устройства входом начального значения которого являются соединенные между собой входы (R-1)- разрядного сдвигового регистра, вход обнуления которого соединен с входом обнуления счетчика адресов и является входом сброса устройства, устано- вочным входом которого является второй вход элемента ИЖ.

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