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

1305711

того, что в состав устройства входит R коммутаторов (R - разрядность) выходы 3„

Ц, счетчик адреса 2,

разрядов счетчика адресов 3 t выход переполнения А счетчика адресов, сдвиговый регистор 5 кода итерации, выходы б, - 6,, разрядов сдвигового регистра кода итера1

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

Целью изобретения является расшире ние области применения за счет формирования адреса произвольной разрядности.

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

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

13разрешения работы устройства, вход

14режима работы устройства, входы 15,- разрядов кода параметра устройства, выходы 16,- 16 разрядов адреса устройства.

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

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

На входы 15,- 15к., разрядов кода параметра устройства подается двоичции, элементы 2И-НЕ 7р., , элемент

ИЛИ 8, элемент И 9, тактовый вход 10, вход начальной установки 11, вход логической единицы 12, вход разрешения работы 13, вход режима работы 14, входы кода константы 15,- 15,, , выходы разрядов адреса 16,- 16. 1 ил. 3 табл.

5.

0

5

0

5

0

Hbifi код, зависящий от размера массива записываемых отсчетов. Этот код определяется по следующему правилу: если размер массива N 2 (га 1,R), то на входы 15(- 15д должен подаваться двоичный код числа (N/2-1), причем 15,- вход йля младшего разряда двоичного кода. Вслед за этим приходит импульс на вход 11 начальной установки устройства, который появляется на выходе элемента ИЛИ 8 и поступает на тактовый вход сдвигового ре- гистра 5 кода итерации и на счетный вход счетчика 2 адресов. Нулевой потенциал, присутствзтощий на входе 14 режима работы устройства, приходит через элемент И 9, прступает на вход управления сдвигом регистра 5 кода итерации и определяет режим параллельного занесения информации в этот регистр. Так как на вторых входах всех элементов 2И-НЕ 7 - 7|., , соединенных с входом 14 режима работы устройства, присутствует нулевой потенциал, то на входы параллельного занесения информации регистра 5 кода итерации- будет поступать единичный потенциал с выходов соотвествующих элементов 2И-НЕ 7,- 7о., . Тогда по импульсу на тактовом входе регистр 5 кода итерации установится в состояние Все единицы. Б результате к выходам 16j разрядов адреса устройства подключатся через соответствующие коммутаторы 1,- IR выходы 3 разрядов счетчика адресов в порядке возрастания номера разряда. Так как на пер- мом входе параллельного занесения информации счетчика 2 адресов, подключенном к входу 12 логической единицы устройства, присутствует логическая единица, а на остальных входах параллельного занесения информации.

313

счетчика 2 адресов присутствует дво- .ичный код, поступивший с входов 15,- 15q. разрядов кода параметра, то по импульсу на счетном входе счетчика 2 адресов последний установится в сое- тояние, соответствующее двоичному коду, числа (N-1).

Записываемым отсчетам анализируемого входного сигнала соответствуют импульсы на тактовом входе 10 устрой- ства, поступающие на тактовьш вход счетчика 2 адресов. Счетчик 2 адресов работает в вычитающем режиме. Таким образом, в первом режиме работы устройство формирует адреса, задаваемые счетчиком 2 адресов и равные дополнению номеров отсчетов анализируемого входного сигнала до (N-1).

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

-

Как и в первом режиме, на ходы 15,- 15р( разрядов кода параметра устройства подается двоичный код чис- зо ла (N/2-1). Вместе с тем на вход 13 разрешения работы устройства подается нулевой потенциал. После этого на вход 11 начальной установки устройства приходит импульс, который прохо- дит через элемент РШИ 8 и поступает на тактовый вход регистра 5 кода итерации и на счетный вход счетчика 2 адресов. Так же, как и при начальной установке устройства в первом режиме Q в счетчик 2 адресов запишется двоичный код числа (N-1). Нулевой потенциал, присутствующий на входе 13 устройства проходит через элемент И 9, поступает на управляющий вход регистра 5 кода итерации и определяет режим параллельного занесения информации в этот регистр. На первые входы элементов 2И-НЕ 7, - 7я-| с входов соответственно 15, - 15к..д поступает код числа 50 (N/2-1). Так как на вторых входах всех элементов 2И-НЕ 7, - 7, , соединенных с входом 14 режима работы устройства, присутствует единичный потенциал, то на входы параллельного 55 занесения информации регистра 5 итерации будет поступать инверсия двоичного кода числа (N/2-1) с выходов элементов 2И-НЕ 7,- 7к-1 . В результате

57

fOf520

25

зо Q й 5055114

по импульсу на тактовом входе регистр 5 кода итерации установится в состояние, соответсвующее инверсии двоичного кода числа (N/2-1).

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

Принцип адресации, используемый в устройстве, заключается в следующем.

Адреса, необходимые для любой К-й итерации быстрого преобразования Фурье, могут быть получены с помощью опера- ции идеального тасования, предполагающей разделение исходного массива из п 2 последовательных адресов пополам и чередование адресов из двух половин. Обозначим операцию идеального тасования S(N).

Если исходньш массив из N последовательных адресов разбить на Р под- массивов (Р 2 , т, т) и в каждом из подмассивов выполнить операцию идеального тасования, то такая операция может быть записана в виде P S(N). В соответствии с алгоритмом быстрого преобразования Фурье обработка массива размером N требует m итераций. Тогда формирование адресов на К-й итерации быстрого преобразования Фурье может быть описано выражением

s(N), (R т;).

Это выражение означает, что для формирования адресов К-й итерации быстрого преобразования Фурье размером N необходимо сформировать исходный массив последовательных адресов от

нуля до (N-1), разбить исходный масп -1сив последовательных адресов на 2

подмассивов, а та-кже в каждом из под- массивов выполнить операцию идеального тасования. I. -

В результате получится последовательность адресов, необходимая для адресации операндов.

В табл.1 представлен пример формирования последовательности адресов при выполнении третьей итерации 32-тЬ- чечного быстрого преобразования Фурье (т.е. N 32; К 3).

Очевидно, что если размер быстрого преобразования Фурье N, N, то для формирования адресов достаточно взять часть результирующих адресов, полученных для N. Так, в приведенном в Табл. 1 примере первая половина результирующей прследовательности адресов представляет собой последоватеятз- ность адресов, необходимую для второй итерации 16-точечного быстрого преобразования Фурье (т.е. для N 16; К 2).

В результате для формирования необходимых адресов достаточно изменять положение-младшего разряда счетчика 2 адресов относительно его остальных

сдвиговым регистром 5 кода итерации с частотой, равной частоте переполнения счетчика 2 адресов.

Единичные потенциалы, присутствующие на входе 13 устройства и на входе 14 режима работы устройства, поступаю соотззетственно на первьй и второй входы элемента И 9, на выходе которого появляется логическая единица, коразрядов в зависимости от размера быс- Ю торая поступает на управляющий вход трого преобразования Фурье и номера регистра 5 кода итерации и определяет выполняемой итерации. При выполнении режим последовательного занесения ин- быстрого преобразования Фурье размером формации в этот регистр. N 2 (т 1-R) на первой итерации Сигналом считывания операндов дл я достаточно подключить выход 3 младше- 5 обработки соответствзтот импульсы на го разряда счетчика адресов к выходу, 16 ш-го разряда адреса устройства, выходы 3ij,- 3, разрядов счетчика адресов подключить соответственно к выхотактовом входе 10 устройства, посту- пающие на тактовый вход счетчика 2 адресов. Счетчик считает в вычитающем режиме. Импульсы переполнения с выхода

ства,

а выходы 3,- 3 разрядов

дам 16,- 16m-i разрядов адреса устрой-20 4 переполнения счетчика адресов проходят на вход элемента ИЛИ 8 и поступают на тактовьш вход регистра 5 кода итерации и на счетный вход счетчика 2 адресов. По импульсу на счетном входе счетчика 2 адресов в него запишется двоичньш код числа (N-1), присутству- ющ11й на его входах. Так как на входе последовательного занесения информации регистра 5 кода итерации присутствует логическая единица, поступающая с входа 12 логической единицы устройства, то регистр 5 кода итерации будет последовательно заполняться единицами со стороны старшего разряди.

счетчика адресов подключить соответственно к выходам 1б,„,- 16ц разрядов адреса устройства. На второй итерации необходимо подключить выход 3, млад шего разряда счетчика адресов к выходу 16ff,-, (m-l)-ro разряда адреса устройства, выходы 3. разрядов счетч1|ка адресов подключить соответственно к выходам 16,- 16 разрядов

30

. о

будет находиться в состоянии Все единицы.

Закон коммутации для коммутаторов

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

адреса устройства, а выходы 3fj ос тальных разрядов счетчика адресов - соответственно к выходам 16{ разрядов адреса устройства. На третьей итерации необходимо подключить выход 35 Таким образом, на последней итерации 3, младшего разряда счетчика адресов сдвиговый регистр 5 кода итерации к выходу 16.т-г (т-2)-го младшего разряда адреса устройства, выходы 3,- 3,п-г разрядов счетчика адресов соответственно к выходам 16,- раз- Г, 1 рядов адреса устройства, а выходы Зд остальных разрядов счетчика адресов - соотвественно к выходам 16, - 16, разрядов адреса устройства и т.д.

Таким образом, на этапе преоб- Устройство для адресации процессо- разования порядок следования разрядов ра быстрого преобразования Фурье, со- счетчика 2 адресов на выходах 16,- -держащее R коммутаторов, (R - разряд- 16 разрядов адреса устройства оказы- ность формируемого адреса), сдвиговьй « „„регистр кода итерации, элемент ИЛИ

и счетчик адресов, тактовьш вход кото- .рого является тактовым входом устройства, выход переполнения счетчика ад- ресов подключен к первому входу элемента. ИЛИ, второй вход которого является входом начальной установки устройства, а выход элемента ИЛИ подключен к тактовому входу сдвигового

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

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

Описанная перегруппировка разрядов счетчика 2 адресов происходит с помощью коммутаторов IR, на выходе каждого из которых появляется один из трех (двух - для коммутаторов 1 j- Ij,) входньк информационных сигналов. Управление переключением осуществляется

сдвиговым регистром 5 кода итерации с частотой, равной частоте переполнения счетчика 2 адресов.

Единичные потенциалы, присутствующие на входе 13 устройства и на входе 14 режима работы устройства, поступаю соотззетственно на первьй и второй входы элемента И 9, на выходе которого появляется логическая единица, которая поступает на управляющий вход регистра 5 кода итерации и определяет режим последовательного занесения ин- формации в этот регистр. Сигналом считывания операндов дл я обработки соответствзтот импульсы на

торая поступает на управляющий вход регистра 5 кода итерации и определяет режим последовательного занесения ин- формации в этот регистр. Сигналом считывания операндов дл я обработки соответствзтот импульсы на

тактовом входе 10 устройства, посту- пающие на тактовый вход счетчика 2 адресов. Счетчик считает в вычитающем режиме. Импульсы переполнения с выход

-20

. о

355

будет находиться в состоянии Все единицы.

Закон коммутации для коммутаторов

Таким образом, на последней итерации сдвиговый регистр 5 кода итерации Г, 1

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

им образом, на последней итерации иговый регистр 5 кода итерации 1

Таким образом, на последней итерации сдвиговый регистр 5 кода итерации Г, 1

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

регистра кода итерации, вход последовательного занесения информации которого является входом задания логической единицы устройства, первый информационный вход R-ro крммутатора под- ключен к выходу первого разряда счетчика адресов, первый информационный вход i-ro (i 1,R - 1.) коммутатора подключен к выходу (i + 1)-го разряда счетчика адресов, второй информацион- ный вход R-ro коммутатора подключен к выходу R-ro разряда счетчика адресов, второй информационный вход i-ro коммутатора подключен к выходу первого разряда счетчика адресов, третий информационный вход 1-го (1 2,R-1) коммутатора подключен к выходу 1-го разряда счетчика адресов, выход j-ro (j 1,R) коммутатора является выходом j-ro разряда адреса устройства, отличающееся тем, что, с целью расширения области применения за счет формирования адреса произвольной разряр ности, в него введены (R-1) элемент 2И-НЕ и элемент И, первый

00001 00010 00011 00100 00101 00110 00111 01000 01001 0°1010 01011 01100

вход которого является входом разрешения работы устройства, выход i-ro разряда сдвигового регистра кода итерации подключен к первому управляющем входу (i+1)-ro коммутатора и второму управляющему входу i-ro коммутатора, первый вход i-ro элемента 2И-НЕ объединен с (i+1)-M входом параллельного занесения информации счетчика адресов и является входом i-ro разряда кода параметра устройства, вторые входы всех элементов 2И-НЕ объединены с вторым входом элемента И и являются входом режима работы устройства, первый вход параллельного занесения информации счетчика адресов подключен к входу логической единицы устройства, счетный вход счетчика адресов подключен к выходу злементр, ИЛИ, выход i-ro элемента 2И-НЕ подключен к i-му входу параллельного занесения информации сдвигового регистра кода итерации, выход элемента И подключен к входу управления сдвигом сдвигового регистр кода итерации.

Таблица 1

00100

00001

00101

00010

00110

00011

00111

01000

01100

01001

01101

01010

1305711

10 Продолжение табл. 1

О О 1

О 1 1

Редактор С.Пекарь

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

Техред В.Кадар Корректор А.Обручар

Заказ 1454/48

Тираж 673Подписное

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

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

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

Изобретение относится к автомати ке и вычислительной технике и может быть использовано в системах цифровой обработки сигналов при построении процессоров быстрого преобразования Фурье. Цель изобретения, - расширение области применения за счет формирова- ния адреса произвольной разрядности. Поставленная цель достигается за счет 5г fS, со о ел