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

 

Изобретение относится к области авд-оматики и вычислительной техники и предназначено для использования в составе специализированных процессоров быстрого преобразования Фурье. Цель изобретения - повышение быстродействия . Поставленная цель достигается за счет того, что в состав устройства для формирования адресов процессора быстрого преобразования Фурье входит счетчик 1, регистр 2, сумматор 3, сумматор по модулю два 4, регистры 5 и 6, комм. татор 7, синхронизатор 8, вход начальной установки 9, тактовый вход 10, вход задания номера итерации 11, тактовый вход 12, вход задания режима I 3 и выход адреса устройства 14. 4 ил. 7 со IN5 4: О СО -si (риг.1

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

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

РЕСПУБЛИН

ps 4 G 06 F 15/332

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНЯТИЙ (21). 4019094/24-24 (22) 31.01,86 (46) 15.07.87. Бюл. Ф 26 (72) К, Н. Водников и Л, П. Петрова (53) 681.32(088.8) (56) Авторское свидетельство СССР

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

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

11 548863) кл. С 06 Р 15/332, 1977. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АП;

РЕСОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЪЕ (5?) Изобретение относится к области автоматики и вычислительной техники и предназначено для использования

„„ЯО„„1324О37 А 1 в составе специализированных процес соров быстрого преобразования Фурье.

Цель изобретения — повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства для Формирования адресов процессора быстрого преобразования Фурье входит счетчик 1, регистр 2, сумматор 3, сумматор по модулю два 4, регистры 5 и 6, коммутатор 7, синхронизатор 8, вход начальной установки 9, тактовый вход 10, вход задания номера итерации 11, тактовый вход 12, вход задания режима 13 и выход ад реса устройства 14. 4 ил, 1 324037

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

Фурье (БПФ)..

Цель изобретения — повышение быстродействия.

На фиг, 1 представлена структурная схема устройства для формирования адресов (оперативной памяти) процессора быстрого преобразования Фурье; на фиг. 2 — временная диаграмма работы устройства в стандартной итерации; на фиг, 3 — то же, в специ!

5 альной итерации; на фиг. 4 — структурная схема синхронизатора °

Устройство для формирования адресов (фиг. 1) содержит счетчик 1, регистр 2, сумматор 3, сумматор 4 по

20 модулю два, регистры 5 и 6, коммутатор 7, синхронизатор 8, вход 9 начальной установки, тактовый вход 10, вход 11 задания номера итерации, тактовый вход 12, вход 13 задания режима, выход 14 адреса.

Синхронизатор 8 (фиг. 4) содержит триггеры 15 и 16, элементы И 17 и 18, сумматор 19 по модулю два, элемент

И 20„ элемент ИЛИ 21.

Принцип формирования верхнего А и нижнего А" адресов графа БПФ (адресов первого и второго операндов соответственно) в стандартных итераЗc циях БПФ заключается в следующем.

В верхнем адресе исключается иэ счета разряд, положение которого опредепяется номером выполняемой итерации. Этот разряд принимает значение "0" в данной итерации. При условии применения простых быстродействующих счетчиков с параллельной структурой такое исключение разряда может быть произведено суммированием текущего содержимого счетчика (номера текущей базовой операции) и хранимым содержимым счетчика в момент перехода (номером базовой операции в момент перехода), т.е, в момент измене-50 ния состояния исключаемого разряда на выходе счетчика, Если состояние счетчика в момент перехода фиксируется в регистре и на сумматоре суммируется содержимое этого регистра с содержимым счетчика, то на выходе сумматора можно получить верхний адрес, Верхний A и нижний A адреса отличаются значением только одного разряда, причем положение этого разряда задается номером итерации, а значение его всегда 0" для верхнего адреса и "1" для нижнего адреса. Для получения нижнего адреса нужно логически сложить верхний адрес с номером текущей итерации.

При выполнении одной базовой операции БПФ необходимо четыре раза об-. ратиться к ОЗУ: два раза считать опе-. ранды иэ ОЗУ и два раза записать в

ОЗУ результаты вычислений, причем во время считывания из ОЗУ и записи в

ОЗУ АУ процессора должно производить вычисления. Такой режим работы процессора называется согласованным и определяется соотношением с „=4с . где С вЂ” время выполнения одной базовой операции БПФ в АУ процессора; время обращения к ОЗУ, Выполнение этого условия позволяет АУ и

ОЗУ работать одновременно (параллельно), обеспечивая максимальную производительность (быстродействие) процессора.

Временная диаграмма работы АУ и

ОЗУ в согласованном режиме для стандартных итераций БПФ приведена на фиг, 2, Иэ диаграммы видно, что для выполнения t-й базовой операции БПФ к ОЗУ по одним и тем же адресам А . а

Н

f и А, нужно обратиться дважды: вначале произвести считывание операндов (g 8) а затем произвести запись рез-г.тьтатов вычисления базовой операции (е, ж), причем при считывании операндов i-й базовой операции иэ ОЗУ в н по А; и А; АУ процессора производит вычисление (i-1) -й базовой операции БПФ, а при записи результатов вычисления 1.-й базовой операции в

ОЗУ по А,. и А " АУ процессора производит вычисления (i+1)-й базовой операции (Ь).

Таким образом, для обеспечения согласованного режима в стандартных итерациях БПФ устройство для формировалия адресов должно обеспечить формирование адресов операндов в порядке, указанном на фиг. 2, С этой целью вводятся два дополнительных регистра задержки, в которых записываются верхний и нижний адрес предыдущей пары операндов, т.е. осуществляется задержка адресов на один цикл вычисления базовой операции, 3 13240

После выполнения всех стандартных итераций согласно безызбыточному алгоритму БПФ образуется дополнительная итерация, в которой адреса пар операндов должны быть симметричными относительно N/2; где N — число точек преобразования, Симметричные адреса образуют дополнением i-го адреса до N и для их получения достаточно образовать дополнительный код к 1О известному 1-му адресу, Дополнительный код может быть образован при инверсии предыдущего (i-I)-го адреса, для чего нужно формировать (i--.)-й адрес на время обработки i-й пары f5 операндов, Временная диаграмма работы АУ и

03У в согласованном режиме для специальной итерации приведена на фиг. 3. Для обеспечения согласованно-20 го режима используется дополнительный регистр задержки, а также управление входным переносом в сумматор и группой сумматоров по модулю два, которые обеспечивают формирование 25 адресов предыдущей и последующей пар операндов во время выполнения операций над текущей парой операндов (В,т, д,Е,ж), Устройство работает следующим об 30 разом.

Перед началом расчета первой итерации на вход 9 устройства поступает импульс начальной установки устройства, по которому счетчик 1, регистр 35

2 и триггеры 15 и 16 синхронизатора

8 устанавливаются в нулевое состояние. Триггеры 15 и 16 синхронизатора представляют собой делитель частоты входных тактовых импульсов на четы- 40 ре. Расчет одной базовой операции занимает четыре такта. По команде с второго выхода синхронизатора 8 счетчик 1 изменяет свое состояние в каждом цикле работы (т.е. при формирова-45 нии двух пар адресов и вычисления одной базовой операции, фиг. 2 а,5).

На выходе счетчика 1 формируется номер базовой операции в данной итерации. Зались текущего номера базовой операции в регистр 2 происходит в момент перехода по команде записи на входе 12 записи устройства, причем команда записи поступает непосредственно после изменения состояния счетчика. Такая команда может быть получена с выхода старшего разряда адреса тригонометрического коэффици"7 4 ента БПФ или представлять собой целую часть тригонометрического коэффициента БПФ и быть сформированной устройством формирования тригонометрического коэффициента процессора.

В каждом цикле на выходе сумматора 3. формируется верхний адрес. Для формирования нижнего адреса используется группа сумматоров 4 по модулю два, причем при расчете стандартных итераций БПФ каждый сумматор 4 по модулю два в группе работает в режиме ИЛИ. Н;- второй вход группы сумматоров 4 по модулю два поступает прямой код номера итерации с входа 11 устройства, имеющий единицу в одном разряде, соответствующем номеру итерации, и нули в остальных разрядах.

На выходе каждого сумматора по модулю два получается логическая сумма одноименных разрядов сумматора 3 и кода номера итерации с входа ll устройства, В результате этого коды на выходах сумматора 3 и группы сумматоров 4 по модулю два отличаются на единицу в разряде, определяемом номером текущей итерации, и образуют адреса пар операндов согласно алгоритму БПФ. Для задержки адресов пар операндов на один цикл используются регистры 5 и 6, подключенные к выходам сумматора 3 и группы сумматоров

4 по .модулю два соответственно. Вначале каждого цикла, в течение которого происходит расчет одной базовой операции БПФ, производится считывание первого и второго операндов из ОЗУ по адресам А В и А ., Это происходит при наличии на третьем и четвертом выходах синхронизатора 8 команд "00" и 1 01" соответственно (фиг. 2 >, н). При наличии команды

"00н на управляющих входах коммутатора 7 адресов к выходу 14 устройст-. ва через коммутатор 7 адресов подклю. чается выход сумматора 3 и формируется верхний адрес i-го операнда, а при наличии команды "О1" к выходу 14 устройства подключается выход группы сумматоров 4 по модулю два и формируется нижний адрес i-го операнда, ОЗУ при этом находится в режиме считывания и выдает операнды по адресам А и

Ь

А". на вход АУ процессора БПФ. Пока ! происходит выполнение i-й базовой операции, устройство формирует адреса А и А, по которым производитВ ся запись результатов выполнения

1 124037 (i-! )-й базовой аперапии с операндами, выбранными иэ О?У н предыдущем цикле, Адреса А. и А . храпятея в

В Н

1-1 1-1 регистрах 5 и 6 и подключаются к входу 14 устройства через коммутатор

7 адресов при подаче на управляющие входы коммутатора команд ".10" и "11", сформированных на третьем и четвертом выходах синхронизатора 8, Адреса А, А ., А., А формируются еоб н В н ответственно йри подаче на первый вход синхронизатора 8 первого, второго, третьего и четвертого тактовых импульсов. С приходом четвертого тактового импульса на втором выходе син- 15 хранизатора 8 появляется импульс, переводягций счетчик 1 в новое состояние, а триггеры 15 и 16 синхронизатора 8 переходят при этом в нулевое состояние ° При этом к выходу 14 20 устройства подключается выход сумматора 3, а с приходом пятого тактового импульса (первого в последующем цикле) — выход группы сумматоров 4 по рг модулю два и так далее. Каждый четвертый тактовый импульс переписывает содержимое сумматора 3 и группы сумматоров 4 по модулю два в регистры 5 и 6 соответственно, т.е. происходит фиксирование адресов операндов предыдущего цикла. В начале следующего цикла производится считывание из ОЗУ операндов (i+1)-й базовой операции по адресам А,, и А;... а затем

В Н заканчивается выполнение 1 и базовой 35 операции и производится запись результатов в ОЗУ по адресам А; и А;, В н находящимся в регистрах 5 и 6. Такая последовательность формирования адресов операндов сохраняется да конца текущей итерации, после чего изменяется код номера итерации на входе 11 устройства и процесс формирования адресов в новой итерации повторяется аналогичным образом, d$

После выполнения всех стандартных итераций БПФ согласно беэыэбыточнаму алгоритму БПФ образуется специальная итерация, При формировании спе- - 0 циальнай итерации на вход 11 устройства поступает инверсный код номера итерации, т ° е. "111...11" а на вход

13 устройства - признак специальной итерации. При этом на выходах группы 55 сумматоров 4 по модулю два формируется инверсное значение кодов, снимаемых с выхода сумматора 3, т ° е. сумматары 4 по модулю два в группе работают в режиме инвертора, Регистр 2 на время выполнения специальной итерации установлен в нулевое со-. стояние командой с пятого выхода сигнализатора 8, При формировании адреса первого операнда А, в i-м цикле спе1 циальнай итерации на вход переноса сумматора 3 поступает единичная команда с первого выхода синхронизатора 8. Адрес Ад, в i-м цикле формируется на выходах группы сумматоров

4 по модулю два при отсутствии команды переноса на. первом выходе синхронизатора 8. Адреса операндов предыдущей пары А,. „ и А !, „ формируются на выходе сумматора 3 при отсутствии команды переноса и на выходе регистра 6, Адреса А -, А;, формируются на выходах сумматор а 3 и подключ ают ся к выходу 14 устройства через коммутатор 7 адресов при наличии команды

"00" на третьем и четвертом выходах синхронизатора 8, адрес А гг„ формируется на выходах группы сумматоров

4 по модулю два и подключается к выходу 14 устройства при наличии команды "01" на третьем и четвертом выходах синхронизатора 8, а адрес

А „ „ формируется на выходе регистра 6 и подключается к выходу 14 устройства при наличии команды "11" на третьем и четвертом выходах синхронизатора 8.

Каждый четвертый тактовый импульс вызывает изменение состояния счетчика 1 и запись информации с выходов группы сумматоров 4 по модулю два в регистр 6. Таким образом, в первой половине цикла производится считывание операндов иэ ОЗУ по ад-. ресам А; и А, а ва второй половине — запись результатов арифметических операций над аналогичными операндами иэ предыдущего цикла по адресам А, и А„„.;

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

Устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее первый регистр, коммутатор и счетчик, информационный выход которого подключен к информационному входу первого регистра, вход разрешения записи которого является первым тактовым входом уст райства, выходом адреса которого яв1324037 ляется выход коммутатора, о т л и— ч а ю щ e e с я тем, что, с целью повышения быстродействия, в него введены второй и третий регистры, сумматор„ сумматор по модулю два и синхронизатор, первый выход которого подключен к входу переноса сумматора, первый и второй входы которого подключены соответственно к информационному выходу счетчика и выходу .ре- Ю гистра, выход которого подключен к первому входу сумматора по модулю два, первому информационному входу коммутатора и информационному входу второго регистра, выход которого подключен к второму информационному входу коммутатора, третий информационный вход которого подключен к выходу третьего регистра, информационный вход которого соединен с чет- 20 вертым информационным входом коммутатора и подключен к выходу сумматора по модулю два, вторым входом которого является вход задания номера итерации устройства, вход начальной установки, второй тактовый вход и вход задания режима которого являются соответственно входом запуска, тактовым входом и входом задания режима синхронизатора, второй выход которого подключен к тактовым входам второго и третьего регистров и счетному входу счетчика, установочный вход которого соединен с входом начальной установки устройства, третий и четвертый выходы которого подключены соответственно к первому и второму управляющим входам коммутатора, а пятый выход синхро— низатора подключен к установочному входу первого регист- ра.

1324037

Редактор М, Дылын

Заказ 2967/53 Тираж 67? Подписно"-.

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

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

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

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

Техред И.Попович Корректор Л. Патай