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

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

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

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

Устройство для формирования адресов (фиг, 1) содержит счетчик , регистр 2, сумматор 3, сумматор 4 по модулю два, регистры 5 и 6, коммутатор 7 синхронизатор 8, вход 9 начальной установки, тактовый вход 10, вход II задания номера итерации, тактовый вход 12, вход 13 задания режима, выход 14 адреса,

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

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

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

5

с

0

0

5

О 5

Верхний А и нижний А адреса отличаются значением только одного разряда, причем положение этого разряда задается номером итерации, а значение его всегда О для верхнего адреса и 1 для нижнего адреса. Для получения нижнего адреса нужно логически сложить верхний адрес с номером текущей итерации,

При выполнении одной базовой операции БПФ необходимо четыре раза об-, ратиться к ОЗУ: два раза считать операнды из ОЗУ и два раза записать в ОЗУ результаты вычислений, причем во время считывания из ОЗУ и записи в ОЗУ АУ процессора должно производить вычисления. Такой режим работы процессора называется согласованным и определяется соотношением t 4tQ5, где tд, - время выполнения одной базовой операции БПФ в АУ процессора; 031 Р обращения к ОЗУ, Выполнение этого условия позволяет АУ и ОЗУ работать одновременно (параллельно), обеспечивая максимальную производительность (быстродействие) процессора.

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

мt

и А, нужно обратиться дважды: вна- Чсше произвести считывание операндов (г,3), а затем произвести запись результатов вычисления базовой операции (e,Jt), причем при считывании операндов i-й базовой операции из ОЗУ по А i и А ; АУ процессора производит вычисление (1-1)-й базовой операции БПФ, а при записи результатов вычисления i-й базовой операции в ОЗУ по А. и А АУ процессора производит вычисления (1+1)-й базовой операции (Ь),

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

313

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

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

Устройство работает следующим об разом.

Перед началом расчета первой итерации на вход 9 устройства поступает импульс начальной установки устройства, по которому счетчик 1, регистр 2 и триггеры 15 и 16 синхронизатора 8 устанавливаются в нулевое состояние. Триггеры 15 и 16 синхронизатора представляют собой делитель частоты входных тактовых импульсов на четы- ре. Расчет одной базовой операции занимает четыре такта. По команде с второго выхода синхронизатора 8 счетчик 1 изменяет свое состояние в каждом цизше работы (т.е. при формирова НИИ двух пар адресов и вычисления одной базовой операции, фиг. 2q ,Б), На выходе счётчика 1 формируется номер базовой операции в данной итерации. Запись текущего номера базовой операции в регистр 2 происходит в момент перехода по команде записи на В55оде 12 записи устройства, причем команда записи поступает непосредственно после изменения состояния счетчика. Такая команда может быть получена с выхода старшего разряда адреса тригонометрического коэффици-

37, 4 .

ента БПФ или представлять собой целую часть тригонометрического коэффициента БПФ и быть сформированной устройством формирования тригонометрического коэффициента процессора.

В каждом цикле на выходе сумматора 3.формируется верхний адрес. Дпя формирования нижнего адреса используется группа сумматоров 4 по модулю два, причем при расчете стандартных итераций БПФ каждый сумматор 4 по модулю два в группе работает в режиме ИЛИ. На второй вход группы сумматоров 4 по модулю два поступает прямой код номера итерации с входа 1 устройства, имеющий единицу в одном разряде, соответствующем номеру итерации, и нули в остальных разрядах. На выходе каждого сумматора по модулю два получается логическая сумма одноименных разрядов сумматора 3 и кода номера итерации с входа 1I устройства, В результате этого коды на выходах сумматора 3 и группы сумматоров 4 по модулю два отличаются на единицу в разряде-, определяемом номером текущей итерации, и образуют адреса пар операндов согласно алго- риткгу БПФ. Для задержки адресов пар операндов на один цикл используются регистры 5 и 6, подключенные к выходам сумматора 3 и группы сумматоров 4 по .модули два соответственно, В - начале каждого цикла, в течение которого происходит расчет одной базовой операции БПФ, производится считывание первого и второго операндов из ОЗУ по адресам А - и А. Это происходит при наличии на третьем и четвертом выходах синхронизатора 8 команд 00 и 01 соответственно (фиг. 2 ,и). При наличии команды 00 на управляющих входах коммутатора 7 адресов к выходу 14 устройства через коммутатор 7 адресов подклю чается выход сумматора 3 и формируется верхний адрес i-ro операнда, апринаяи чии команды 01 к выходу 14 устройства подключается выход группы суммато- ров 4 по модулю два и формируется нижний адрес i-ro операнда, ОЗУ при этом находится в режиме считывания и выдает операнды по адресам А ; и А на вход АУ процессора БПФ. Пока происходит выполнение i-й базовой операции, устройство формирует адреса А и А, по которым производится запись результатов выполнения

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

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

После выполнения всех стандартных итераций БПФ согласно безызбыточному алгоритму БПФ образуется специальная итерация. При формировании спе циальной итерации на вход 11 устройства поступает инверсный код номера итерации, т,е. 1 11 . ., 1 , а на вход 13 устройства - признак специальной итерации. При этом на выходах группы сумматоров 4 по модулю два формируется инверсное значение кодов, снимаемых с выхода сумматора 3, т,е, сумматоры 4 по модулю два в группе работают в режиме инвертора. Регистр 2 на время выполнения специальной итерации установлен в нулевое со стояние командой с пятого выхода сигнализатора 8. При формировании адрес первого операнда А, в i-м цикле специальной итерации на вход переноса сумматора 3 поступает единичная команда с первого выхода синхронизатора 8. Адрес в i-M цикле формируется на выходах группы сумматоро 4 по модулю два при отсутствии команды переноса на первом выходе синхронизатора 8, Адреса операндов предыдущей пары А . и А. f.-. формируютс я на вькоде сумматора 3 при отсутствии команды переноса и на выходе регистра 6. Адреса А-, А . формируются на выходах сумматора 3 и подключаются к выходу 14 устройства через коммутатор 7 адресов при наличии команды 00 на третьем и четвертом выходах синхронизатора 8, адрес А , формируется на выходах группы сумматоров 4 по модулю два и подключается к выходу 14 устройства при наличии коман ды 01 на третьем и четвертом выходах синхронизатора 8, а адрес АМ., форкиру€1тся на выходе регистра 6 и подключается к выходу 14 устройства при Нсшичии команды 11 на третьем и четвертом выходах синхронизатора 8,

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

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

Устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее первый регистр, коммутатор и счетчик, информационный которого подключен к информационному входу первого регистра, вход разрешения записи которого является первым тактовым входом ройства, выходом адреса которого яв7

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

г 1

JxO

(/

е /к

3

и

м Н-

240378

татора и подключён к выходу сумматора по модулю два, вторым входом которого является вход задания номера итерации устройства, вход начальной 5 установки, второй тактовый вход и

вход задания режима которого явля- ются соответственно входом запуска, тактовым входом и входом задания режима синхронизатора, второй выход fO которого подключен к тактовым входам второго и третьего регистров и счетному входу счетчика, установочный вход которого соединен с входом начальной установки устройства, J5 третий и четвертый выходы которого подключены соответственно к первому, и второму управляющим входам коммутатора, а пятый выход синхронизатора подключен к устано- 0 вочному входу первого регистра.

мДг

Hvr

м;

Ф//г7

i f I I I iLJ

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

г

j j t

- «flK-i 3

j; --T-I

к. lit 1

VHjriI-L

i/

A

Wz.i

Составитель A. Редактор М, Дылын Техред И.ПопоБИЧ

Заказ 2967/53 Тираж 672Подписное

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

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

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

J.

.

Корректор Л, Патай