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

 

1. УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее (m+k)-разрядный; регистр адреса, выходы которого являются выxoдa и устройства, блок формирования адреса, первая группа входов которого соединена с информа ционными выходами k-разрядного счет чика,. а вторая группа входов блока формирования адреса подключена к выходу k-разрядного регистра сдвига, выходы которого соединены с информационными входами к-разрядного счетчика , управляющий вход регистра адреса, первый управляющий вход регист--ра сдвига и управляющий вход блока формирования адреса соединены соответственно с первым, вторым и третьим выходами блока синхронизации, отличающееся тем,-что, с целью расширения его функциональных возможностей за счет обработки п мерных процессов и упрощения схемы , в него введен т-разрядный счетчик , вход которого соединен с третьим выходом блока синхронизации, а информационные выходы т-разрядного . счетчика соединены с первой группой входов регистра адреса, вторая группа входов которого подключена к выходгш блока формирования -адреса, выход т-го разряда соединен с управляххцим входом k-разрядного счетчика управляющий выход которого подключен к управляющему входу k-pa8« рядного регистра сдвига, а выход ;k-ro разряда регистра сдвига соединен с входом блока синхронизации. 2.Устройство по п. 1, о т л ичающееся тем, что блок синхронизации содержит первый и второй триггеры, генератор одиночного импульса , элемент И, элемент задержки, генератор тактовых импульсов, выход которого соединен с первымвходом элемента И, выход которого соединен с первым входом элемента И, выход которого подключен к входу элемента задержки и является первым выходом блока синхронизации, вход установки в нуль первого триггера и вход установки в единицу второго триггера соединены с выходом генератора СО . одиночного импульса, выход которого является вторым выходом блока синхронизации , выход элемента задержки соединен со счетным входом первого триггера, выход которого является третьим выходом блока синхронизации, вход установки в нуль второго триггера подключен к входу блока синхронизации , а выход второго триггера соединен с вторым входом элемента И. 3.Устройство по п. 1, о т л ичающееся тем, что k-разряд4;:аь ный счётчик содержит k пар элеменсо тов И, k элементов ИЛИ и k триггеров , выход первого элемента И группы в i-ой паре

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

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

РЕСПУВЛИК

З(5П

Ъ !

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA

\ (21) 3408715/18-24 (22) 09.03.82 (46) 07.09.83. Бюл. М 33 .:(72.) A. A. Петровский и В. Б. Клюс

;(71) Минский радиотехнический инсти.тут (53) 681.32(088 ° 8) (56) 1. Авторское свидетельство СССР, В 548863, кл. G 06 F 15/332, 1977.

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

9 430381, кл. G 06 F 9/00, 1974 (прототип). (54)(57) 1 ° УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ

ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОЩ НИЯ

ФУРЬЕ, содержащее (m+k) -разрядный; регистр адреса, выходы которого являются выходами устройства, блок . формирования адреса, первая группа входов которого соединена с информа-. ционными выходами k-разрядного счет- чика, а вторая группа входов блока формирования адреса подключена к выходу k-разрядного регистра сдвига, выходы которого соединены с информа- ционными входами k-разрядного счетчика, управляющий вход регистра адреса, первый управляющий вход регист- ра сдвига и управляющий вход блока формирования адреса соединены соответственно с цервым, вторым и третьим выходами блока синхронизации, о т л и ч а ю щ е е с я тем,- что, с целью расширения его функциональ ных возможностей эа счет обработки и мерных процессов и упрощения схемы, в него введен m-разрядный счет-." чик, вход которого соединен с треть» им выходом блока синхронизации, а информационные выходы m-разрядного,-: счетчика соединены с первой группой входов регистра адреса, вторая rpyn па входов которого подключена к внходам блока формирования Адреса, йн» ход m»»ro разряда соединен с ynpasna ющим входом k-разрядного счетчика„ управлякиций выход которого подключеа к второму управляющему входу k-pas ..Su „„1040491 А рядного регистра сдвига, а выход ,k-го разряда регистра сдвига соединен с входом блока синхронизации.

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

3. Устройство по и. 1, о т л ич а ю щ е е с я тем, что k-разрядный счетчик содержит k nap элементов И, k элементов ИЛИ и k триггеров, выход первого элемента И группы в i-ой паре (i = 2, k) соединен с первым входом (i-1)-го элемента

ИЛИ.группы, второй вход которого соединен с выходом второго элемента И s (i-1)-ой паре группы, а выход (i-1)-го элемента ИЛИ группы соединен со счетным входом i-ro триггера группы, выход (i-1)-го триггера группы соединен с первыми входами элементов И в i-ой паре группы, выход первого элемента И в первой паре группы соединен со счетным входом первого триггера, а выход

k-ro триггера группы соединен с пер1040491

40 вым входом k-ro элемента ИЛИ группы, второй вход которого подключен к выходу второго,емента И k-ой "пары группы, а выход k-го элемента

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

4. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок фор1

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

Известно устройство адресации процессора быстрого преобразования

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

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

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

2 держащее блок выдачи адреса, вход которого соединен с выходом сумматора и через. блок ныдачи информации с выходом счетчика, представляющего собой двоичный счетчик с логической схемой, позволяющей делить его на две части, причем вход. сумматора соединен с.выходом блока ввода информации в сумматор, выход блока разl0 деления счетчика соединен с управляющими входами счетчика и блока ввода информации в сумматор, информационнйй вход которого соединен с выходом счетчика и выходом блока выдачи информации. Синхронизацию работы всего устройства осуществляет блок управляющих импульсов и потенциалов j2 ).

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

Фурье, например, прореживания по

З0 времени с инверсным или прямком упорядочением выходных данных, т.е. малая степень унификации устройства.

Таким образом, основными недостатками известных устройств адресации процессора быстрого преобразования

Фурье являются малые функциональные воэможности (невозможно использовать устройство в процессоре обработки и. -мерных векторных процессов), сложность структурной реализацйи, малая степень унификации. 1040491

Цель изобретения — ра гшнрение функциональных возможностей за счет обработки tl-мерных процессов-и упрощение структуры устройства.

Поставленная цель достигается тем, что в устройство для адресации процессора быстрого преобразования

ФУРье, содеРжащее (m+k)-РазРЯДный регистр адреса„ выходы которого as-, ляются выходами устройства, блок: формирования адреса, первая группа входов которого соединена с инфор- мационными выходами х-разрядного.: счетчика, а вторая группа входов бпока формирования адреса Подключена к выходу k =ðàçðÿäíîãî регистра ,сдвига, выходы которого соединены с информационными входами -разрядного счетчика, управляющий вход регистра, первый управляющий вход регистра сдвига и управляющий вход блока формирования адреса соедине- . ны соответственно с первым, вторим и третьим выходами блока синхронизации, введен m-разрядный счетчик, вход которого соединен с третьим выходом блока синхронизации, а информационные выходы m-разрядного счетчика соединены с первой группой входов регистра адреса, вторая.

rpynna входов которого подключена к выходам блока формирования адреса, Samoa m-го разряда соединен с управляющим входом k-разрядного счетчика, управляющий выход которого подключен к второму управляющему входу Ы-разрядного регистра сдвига, а выход k-ro разряда регистра сдьига соединен с входом блока синхро низации.

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

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

nepsoro триггера, выход которого .яв-,. ляется третьим выходом блока cssxpoнизации, вход установки в нуль второго триггера подключен к входу блока синхронизации, а выход второго триггера соединен с вторым входом элемента И.

При этом Х«разрядный счетчик со держит k пар элементов И, k элемеНтов ИЛИ и к триггеров, выход первого элемента И группы в i-й паре (i

2, k) соединен с первым входоМ

65 довательностей управляющих сигналов, обеспечивающих функционирование все-, го устройства адресации процессора быстрого преобразования Фурье. Блок, синхронизации (фиг. 2) содержит re-, (i-1)-го элемента ИЛИ группы, второй вход которого соединен с выходом второго элемента И в (i-1)-ой паре группы, а выход (i-1)-го элемента

ИЛИ группы соединен со счетным вхо дом i-го триггера группы, выход (i -1)-го триггера группы соединен с первыми входами элементов И в i-A паре группы, выход первого элемента

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

15 k-ой йары группы, а выход k-ro элемента ИЛИ группы является управляющим выходом k-разрядного счетчика, вторые входы элементов И группы являются информационными входами k2О .разрядного счетчика, причем второй вход первого элемента И во всех парах группы является инверсным входом

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

35 группой входов блока формирования адреса, первые входы элементов И группы образуют вторую группу входов блока формирования. адреса, а вторые входы элементов И группы со

Щ единены с управляющим входом блока формирования адреса.

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

ФУрье, на фиг. 2 - структурная схема блока синхронизации; на фиг. 3 временные диаграммы, поясняющие принци работы блока синхронизации, на фиг. 4 ю функциональная схема

k-разрядного первого счетчика, на

Фиг. 5 - функциональная схема блока .формирования адреса.

Устройство адресации процессора быстрого преобразования Фурье содержит (m+k)-разрядный регистр 1 адзз реса, блок 2 формирования адреса, k-разрядный счетчик 3, k-разрядный регистр 4 сдвига, блок 5 синхронизации, ж-разрядный счетчик б.

Блок 5 синхронизации предназначен для формирования необходимых после1040491 нератор 7 тактовых импульсов, элемент И 8, элемент 9 задержки, первый триггер 10 "торой триггер -11, генератор 12 одиночного импульса.

: K-разрядный первый счетчик 3 с управляемыми цепями переноса предназначен для подготовки базы адреса. Его разрядность определяется следующим образом:

Я2 где N-2 — количество элементов в компоненте Х; входного вектора Х = Х „, ..., X„g и — мерность векторного процесса,"

Т - знак транспортирования вектора, матрицы.

К-разрядный первый счетчик 3 содержит (фиг. 4) группу элементов

И 13 из k пар элементов И, группу элементов ИЛИ 14 из k элементов ИЛИ и-группу триггеров 15 из k триггеров

Второй m-разрядный счетчик 6 необходим для формирования базы адреса при обработке и-мерных векторных процессов, разрядность ш которого определяется согласно выражению ш = Еи1(1оц.и) + 1.

Второй m-разрядный счетчик 6 представляет собой двоичный суммирующий счетчик с коэффициентом пересчета, равным мерности и обрабатываемого векторного процесса.

Блок формирования адреса 2 предназначен для формирования адресов элементов обрабатываемого массива в соответствующих базовых операциях алгоритма быстрого преобразования

Фурье с учетом полученных баэ в

k-разрядном первом счетчике 3 и в регистре 4 сдвига. Блок 2 формиро» вания адреса (фиг. 5) содержит группу элементов И 16 и группу элементов ИЛИ 17, состоящих из k элементов.

Регистр адреса 1 предназначен для фиксирования адреса элементов обрабатываемого векторного процесса в соответствующих базовых операциях алгоритма быстрого преобразования Фурье. Он представляет собой (m+k)-разрядный регистр хранения информации. k-разрядный регистр 4 сдвига служит для управления цепями переноса k-разрядного первого счетчика 3. Он представляет собой

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

Устройство адресации процессора быстрого преобразования Фурье padoтает следующим образом.

По сигналу с выхода 2 блока синхронизации в регистр 4 сдвига заносится код ос о

Данная единица по сигналу с управляющего выхода k-разрядного первого счетчика 3 сдвигается вправо (в сто .рону младших разрядов) на один разряд после выполнения каждой итерации в алгоритме быстрого преобразования

Фурье. Следовательно, на одном из выходов к-разрядного регистра 4 сдвига будет потенциал единицы, что будет разрешать перенос из:(М-1)-ro разряда в (2+1)-ый и запрещать пе15,Ренос в 1-ый разряд k-разрядного первого счетчика 3, т.е. единица на

М-ом выходе k-разрядного регистра

>Q 4 сдвига поступает на Я-ую пару элементов И группы 13 k-разрядного пер«

1 вого счетчика 3 и запрещает прохож-дение единицы переноса с (М-1)-го разряда через (2-1)-ый элемент ИЛИ

25 группы 14 в 3-ый разряд данного счетчика, с другой стороны потенциал единицы на .й-ом выходе Х-разрядного регистра 4 сдвига разрешает прохождение данной единицы переноса через Х-ый элемент ИЛИ группы 14 в (2+1)-ый разряд Е-разрядного первого счетчика 3. Следует, отметить, что Х-ый разряд данного счетчика будет в нуле и в течение выполнения

Я-ой итерации не изменится его состояние. Здесь номер 2-ro разряда соответствует fk — (6-1)) номеру итерации в алгоритме быстрого преоби ТИ3 (фиг. 2 и 3) на первом и третьем выходах соответственно. Сигналы

ТИЗ образуются путем деления в два, раза частоты задержанных сигналов

ТИ1. Это осуществляется с помощью элемента 9 задержки и второго триг» гера 11. Время с и частота сюгна65 лов ТИ1 определяется, исходя иэ разования Фурье.

Данный. код в регистре 4 сдвига

40. íà k - (Я-1)-ой итерации выполнения алгоритма быстрого преобразования Фурье участвует в формировании адресов операндов базовых операций, вычисляемых на этой итерации, .соот45 ветствующих компонент векторного процесса.

Согласно алгоритму быстрого пре« образования Фурье на каждой итерации происходит обработка базовых ° операций всех компонент вектора

Х = (!Х.„ ..., Х, (т, т.е. устройство адресации процессора быстрого преобразования Фурье должно определять адреса операндов базовых операций компоненты Хп(1)э 1 = Х, Я вектора

Х., затем X (>), ..., Х (С). Для этого. блок, 5 синхронизации выдает все последовательности сигналов ТИ1

1040491 длительности вычисления базовой операции операционным автоматом процес. сора быстрого преобразования. Фурье. Согласно алгоритму БПФ на каждой итерации первыми определяются адреса операндов базовой операции компоненты Х вектора Хт, затем компоненты

Х< Поэтому по первому сиг» налу последовательности ТИ1 с перво-го выхода блока 5 синхронизации содержимое m-разрядного счетчика 6 10 записывается в первые m старших разрядов регистра 1 адреса, а содержимое -разрядного счетчика 3 через группу элементов ИЛИ Т7 блока 2 формирования адреса передается в после» 35 дующие Х разрядов (m+k)-разрядного регистра адреса. При этом определяется адрес первого элемента Х ком- . поненты Х вектора Х в базовой опеТ

1 рации. Затем формируется первый сигнал последовательности ТИЗ с третьего выхода блока 5 синхронизации на управляющий вход блока 2 формирования адреса и разрешает передачу че-. рез группу элементов И 16 и группу элементов ИЛИ 17 на k младших инфор« мационных входа регистра 1 адреса содержимое k-разрядного счетчика 3 и регистфа 4 сдвига. Далее согласно алгоритму. работы блока 5 синхронизации (фиг. 3) поступает второй сигнал последовательности ТИ1 с первого выхода блока 5 синхронизации на управляющий вход регистра 1 адреса, по которому, содержимое т-разрядного счетчика 6, k-разрядного счетчика

3 и регистра 4 сдвига записывается ,в (m+k)-разрядный регистр адреса. .. При этом, как отмечалось выше, в

Я-ый разряд регистра 1 адреса на

fk - (Ф-1)) -ой.итерации запишется - 40 единица„ так как в этом разряде

Е-paэpяднbго счетчика 3 на дайной итерации всегда ноль. Полученный адрес в регистре 1 адреса определя ет втоРой элемент Х компоненты

Х вектора Х в базовой операции. По эадйему фронту данного сигна ла последовательности ТИЗ в m-разрядный счетчик добавится единица.

Далее по следующей паре сигналов последовательности ТИ1 сигналу цо-,. следовательности ТИЗ аналогично описанному выше формируются адреса эле-, ментов Х21и Х компоненты Х2 векто- ра Х . Снова к содержимому m-разряд т ного счетчика 6 прибавляется единица по заднему фронту сигнала последовательности ТИЗ. Затем аналогично определяются адреса элементов Х к;:

Х компоненты Х вектора Х в базовой операции и r.ä. И, наконец, фор- 60 мируются адреса элементов Х „ и Х „2 компоненты Х вектора Х в базовой и операции. По заднему фронту сигнала последовательности ТИЗ с третьего выхода блока 5 синхронизации к содержимому m-разрядного счетчика б добавляется единица, счетчик переполняется, так как в нем было код

11 ...1 ппи п = lop>2» и пп сигналу

П переполнения m-разрядного счетчика .происходит добавление единицы к содержимому k-разрядного счетчика. ,Далее процесс продолжается аналогич. но описанному выше и определяются адреса элементов компонент Х.„,, X

Х„ вектора Х следующих "ба очек" Hà (k — (2-1))-ой итерации °

Сигнал переполнения k-paapag uiо счетчика 3 означает окончание данной итерации. Он поступает на управляющий вход регистра 4 и.сдвигает хранящуюся-в нем единицу на один разряд вправо (в сторону младших. разрядов). Далее начинается формирование адресов на следующей итера.ции (k-k) аналогично описанному вы» ше. После .формирования адресов последней k-ой итерации по сигналу переполнения с управляющего выхода

k-разрядного счетчика 3 производится сдвиг содержимого регистра 4, по сигналу с которого выдвигаемая за пределы регистра единица поступает на вход блока 5 синхронизации и устанавливает в ноль первый триггер 11, что обеспечит нулевой потенциал на входе элемента И 8, а это запре тит формирование последовательностей сигналов ТИ1 и ТИЗ. Иа этом кончается один цикл работы устройства адресации процессора быстрого преобразования Фурье, и устройство готово к работе с новыми исходными данными, с новым вектором фТ.

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

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

1040491

1040491

7/Р

Фуд l (i9eeyj

ГТМ (/brrp$

1040491

1040491

6Ъ Дачи Ф

Ае У/УЖф

um Ювчи Х

Заказ 6930/53 Тираж 706

BHHHIIH Государственного комитета СССР по делам изобретений.и открытий

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

Ю ЮЮЮ

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Подписное

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

Редактор И. Ковальчук Техред М. Кузьма Корректор iO. Макаренко