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

 

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

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

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

РЕСПУБЛИК (19) (11) А1 (S1) 4 С 06 F 15/332

OllHCAHHE ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

gp,=

16

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

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

1084808, кл. G 06 F 15/332, 1984.

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

11 1233167, кл. G 06 Р 15/332, 07.02.85..Ф .) (54) УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ ПРОЦЕС-.

СОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к автомати ке и вычислительной технике и может о быть использовано в системах цифровой обработки сигналов при построении процессоров быстрого преобразования Фурье. Цель изобретения, — расширение области применения за счет формирования адреса произвольной разрядности.

Поставленная цель достигается за счет

1305711 того, что в состав устройства входит R коммутаторов (R — разрядность) 1» — 1, счетчик адреса 2, выходы разрядов счетчика адресов

3» — 3, выход переполнения 4 счетчика адресов, сдвиговый регистор 5 кода итерации, выхопы 6» — 6»», разряров сдвигового регистра кода итера1

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

Фурье.

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

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

Устройство содержит коммутаторы

1» — 1, счетчик 2 адресов, выходы

3, — 3„ разрядов счетчика адресов, выход 4 переполнения счетчика. адресов, сдвиговый регистр 5 кода итерации, выходы 6» — 6 разрядов сдвигового регистра кода итерации, элементы

2И-НЕ 7, — 7».» двухвходовой элемент

ИЛИ 8, двухвходовой элемент И 9, тактовый вход 10 устройства, вход 11 начальной установки устройства, вход 12 логической единицы устройства, вход

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

14 режима работы устройства, входы

15, — 15 - разрядов кода параметра устройства, выходы 16, — 16R разрядов адреса устройства.

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

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

s первом режиме устанавливается сле- 40 дующим образом.

На входы 15, — 15R » разрядов кода параметра устройства подается двоичции> элементы 2И-НБ 7< — 7„,, элемент

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

3 табл.

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

2И-НЕ 7» — 7R » . Тогда по импульсу на тактовом входе регистр 5 кода итерации установится в состояние "Все единицы". В результате к выходам 16»вЂ”

16 разрядов адреса устройства подключатся через соответствующие коммутаторы 1, — 1» выходы 3»- 3 разрядов счетчика адресов в порядке возрастания номера разряда. Так как на пермом входе параллельного занесения информации счетчика 2 адресов, подключенном к входу 12 логической единицы устройства, присутствует логическая единица, а на остальных входах параллельного занесения информации

3 13057 счетчика 2 адресов присутствует дво.ичный код, поступивший с входов 15,—

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

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

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

Как и в первом режиме, на Входы

15,— 15„ разрядов кода параметра устройства подается двоичный код чис- 30 ла (N/2-1). Вместе с тем на вход 13 разрешения работы устройства подается нулевой потенциал. После этого на вход 11 начальной установки устройства приходит импульс, который проходит через элемент ИЛИ 8 и поступает на тактовый вход регистра 5 кода итерации и на счетный вход счетчика 2 адресов. Так же, как и при начальной установке устройства в первом режиме 40 в счетчик 2 адресов запишется двоичный код числа (М-1). Нулевой потенциал, присутствующий на входе 13 устройства проходит через элемент И 9, поступает на управляющий вход регистра 5 кода итерации и определяет режим параллельного занесения информации в этот регистр. На первые входы элементов

2И-НЕ 7, — 7„, с входов соответственно 15, — 15я..q поступает код числа (N/2-1). Так как на вторых входах всех элементов 2И-НЕ 7, — 7„,, соединенных с входом 14 режима работы устройства присутствует единичный поэ

О тенциал, то на входы параллельного занесения информации регистра 5 итерации будет поступать инверсия двоичного кода числа (N/2-1) с выходов элементов 2И-HE 7, — 7 1 . В результате по импульсу на тактовом вхоце регистр

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

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

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

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

Если исходный массив из N последовательных адресов разбить íà P подtTl g массивов (Р = 2, m, c m) и в каждом из подмасснвов выполнить операцию идеального тасования, то такая операция может быть записана в виде P S(N).

В соответствии с алгоритмом быстрого преобразования Фурье обработка массива размером N требует m итераций. Тог. да формирование адресов на К-й итерации быстрого преобразования Фурье может быть описано выражением

2 S(N), (R = l,m).

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

М необходимо сформировать исходный массив последовательных адресов от нуля до (N — 1), разбить исходный масК-1 сив последовательных адресов на 2 подмассивов, а также в каждом из подмассивов выполнить операцию идеального тасования.

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

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

Очевидно, что если размер быстрого преобразования Фурье N, c N, то для формирования адресов достаточно взять часть результирующих адресов, полученных для N. Так, в приведенном в

Табл. 1 примере первая половина результирующей прследовательности адре1305711

6 сдвиговым регистром 5 кода итерации с частотой, равной частоте переполнения счетчика 2 адресов, Единичные потенциалы, присутствующие на входе 13 устройства и на входе

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

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

35 Таким образом, на последней итерации сдвиговый регистр 5 кода итерации будет находиться в состоянии "Все единицы".

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

1, — 1 представлен в табл. 2.

Закон коммутации для коммутаторов ! — 1g < представлен в табл. 3. сов представляет собой последователт ность адресов, необходимую для второ итерации 16-точечного быстрого преоб разования Фурье (т.е. для N< = 16; К

= 2).

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

И = 2 (m = 1-R) на первой итерации достаточно подключить выход 3 младш го разряда счетчика адресов к выходу

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

3 младшего разряда счетчика адресов к выходу 16» (m-2)-го младшего раэ ряда адреса устройства, выходы 3 3».z разрядов счетчика адресов соответственно к выходам 16„ — 16» разрядов адреса устройства, а выходы

3 — 3 остальных разрядов счетчика адресов — соотвественно к выходам

16,„, — 16 разрядов адреса устройФормула изобретения ства и т.д. 45

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

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

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

13057

Таблица 1

Номер подмассива

Исходный массив последовательных адресов

00100

00000

00001

00001

00010 в

00101

00011

00010

00100

00110

00101

00011

00 1 10

00111

00111

01100

01000

01001

01010

01001

01101

01011

01010

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

11

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

Ълемента 2И-НЕ подключен к i-му входу параллельного занесения информации сдвигового регистра кода итерации, выход элемента И подключен к входу управления сдвигом сдвигового регистра кода итерации.

Результирующая последовательность адресов

1305711

ПРодолжение табл. 01101

01110

01110

01011

01111

01111

10000

10000

10001

10100

10010

10001

10011

10101

10100

10010

10101.

10110

10110

10011

101 11

10111

11000

11000

11001

11100

11010

11001

11011

11101

11100

11010

11101

1i 110

11 110

11011

11111

11111

Таблица 2

Управляющий вход Номер информационного входа, коммутируемого на выход

1305711

Таблица 3

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

Управляющий вход (второй) Управляющий вход (первый) 0

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

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

Заказ 1454/48

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

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

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

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