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

(50 4 С 06 Г 15 Петров СССР1984.ССР1977.АНИЯ АП;ОБРАЗОтносится к областислительной техники УДАРСТНЕННЫЙ НОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЦТИЙ(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВРЕСОВ ПРОЦЕССОРА БЫСТРОГО ПРКВАНИЯ ФУРЪЕ(57) Изобретение оавтоматики и вычии предназначено для использования в составе специализированных процессоров быстрого преобразования Фурье.Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства для Формирования адресов процессора быстрого преобразования Фурьевходит счетчик 1, регистр 2, сумматор 3, сумматор по модулю два 4, регистры 5 и 6, коммутатор 7, синхронизатор 8, вход начальной установки 9,тактовый вход 10, вход задания номера итерации 11, тактовый вход 12,вход задания режима 13 и выход адреса устройства 14. 4 ил,ЯИзобретение относится к автоматике и вычислительной технике и, вчастности, предназначено для использования в составе специализированныхпроцессоров быстрого преобразования 5Фурье (БПФ)Цель изобретения - повышение быстродействия.На фиг, 1 представлена структурная схема устройства для формирования адресов (оперативной памяти) процессора быстрого преобразования Фурье; на фиг. 2 в .временная диаграммаработы устройства в стандартной итерации; на фиг, 3 - то же, в специ 5альной итерации; на фиг, 4 - структурная схема синхронизатораУстройство для формирования адресов (фиг. 1) содержит счетчик 1,регистр 2, сумматор 3, сумматор 4 по20модулю два, регистры 5 и б, коммутатор 7,синхронизатор 8, вход 9 начальнойустановки, тактовый вход 10, вход 11задания номера итерации, тактовыйвход 12, вход 13 задания режима, выход 14 адреса.Синхронизатор 8 (фиг. 4) содержиттриггеры 15 и 16, элементы И 17 и 18,сумматор 19 по модулю два, элементИ 20 элемент ИЛИ 21,30Принцип формирования верхнего Аи нижнего А" адресов графа БПФ (адресов первого и второго операндовсоответственно) в стандартных итерациях БПФ заключается в следующем. В верхнем адресе исключается иэ счета разряд, положение которого опредепяется номером выполняемойитерации. Этот разряд принимает значение "0" в данной итерации, При условии применения простых быстродействующих счетчиков с параллельной структурой такое исключение разряда может быть произведено суммированием текущего содержимого счетчика (номера текущей базовой операции) и хранимым содержимым счетчика в момент перехода (номером базовой операции в момент перехода), т.е, в момент изменения состояния исключаемого разряда на выходе счетчика, Если состояние счетчика в момент перехода фиксируется в регистре и на сумматоре суммируется содержимое этого регистра с содержимым счетчика, то на выходе сумматора можно получить верхний адрес,Верхний А и нижний А адреса отличаются значением только одного разряда, причем положение этого разряда задается номером итерации, а значение его всегда 0" для верхнего адреса и "1" для нижнего адреса. Для получения нижнего адреса нужно логически сложить верхний адрес с номером текущей итерации.При выполнении одной базовой операции БПФ необходимо четыре раза об-. ратиться к ОЗУ: два раза считать опе-, ранды иэ ОЗУ и два раза записать в ОЗУ результаты вычислений, причем во время считывания из ОЗУ и записи в ОЗУ АУ процессора должно производить вычисления, Такой режим работы процессора называется согласованным и определяется соотношением с =4 с где С - время выполнения одной базовой операции БПФ в АУ процессора;время обращения к ОЗУ, Выполнение этого условия позволяет АУ иОЗУ работать одновременно (параллельно), обеспечивая максимальную производительность (быстродействие) процессора.Временная диаграмма работы АУ и ОЗУ в согласованном режиме для стандартных итераций БПФ приведена на фиг, 2, Иэ диаграммы видно, что для выполнения -й базовой операции БПФ к ОЗУ по одним и тем же адресам А,аНи А, нужно обратиться дважды: вначале произвести считывание операндов(1,3), а затем произвести записьрезу.тьтатов вычисления базовой операции (Е, ж), причем при считывании операндов х-й базовой операции иэ ОЗУв нпо А, и А; АУ процессора производит вычисление (-1) -й базовой операции БПФ, а при записи результатов вычисления 1.-й базовой операции в ОЗУ по А,. и А н АУ процессора производит вычисления (1+1)-й базовой операции (Ь),Таким образом, для обеспечения согласованного режима в стандартныхитерациях БПФ устройство для формировалия адресов должно обеспечить формирование адресов операндов в порядке, указанном на фиг. 2, С этой целью вводятся два дополнительных регистра задержки, в которых записываются верхний и нижний адрес предыдущей пары операндов, т.е, осуществляется задержка адресов на один цикл вычисления базовой операции, 3 13240После выполнения всех стандартныхитераций согласно безызбыточному алгоритму БПФ образуется дополнительная итерация, в которой адреса пароперандов должны быть симметричнымиотносительно И/2; где Ч - число точек преобразования, Симметричные адреса образуют дополнением 1.-го адреса до И и для их получения достаточно образовать дополнительный код к Юизвестному х-му адресу, Дополнительный код может быть образован при инверсии предыдущего (-1)-го адреса,для чего нужно формировать (1.-1)-йадрес на время обработки 1.-й пары 15операндов,Временная диаграмма работы АУ иОЗУ в согласованном режиме для специальной итерации приведена нафиг, 3. Для обеспечения согласованно го режима используется дополнительный регистр задержки, а также управление входным переносом в сумматори группой сумматоров по модулю два,которые обеспечивают формирование 25адресов предыдущей и последующей пароперандов во время выполнения операций над текущей парой операндов(ь,т, д,е,ж),Устройство работает следующим об 30разом.Перед началом расчета первой итерации на вход 9 устройства поступаетимпульс начальной установки устройства, по которому счетчик 1, регистр 352 и триггеры 15 и 16 синхронизатора8 устанавливаются в нулевое состояние. Триггеры 15 и 16 синхронизаторапредставляют собой делитель частотывходных тактовых импульсов на четыре. Расчет одной базовой операциизанимает четыре такта. По команде свторого выхода синхронизатора 8 счетчик 1 изменяет свое состояние в каждом цикле работы (т.е. при формирова.45нии двух пар адресов и вычисления од.ной базовой операции, фиг, 2 а,6).На выходе счетчика 1 формируется номер базовой операции в данной итерации. Зались текущего номера базовой 50операции в регистр 2 происходит вмомент перехода по команде записи навходе 12 записи устройства, причемкоманда записи поступает непосредственно после изменения состояниясчетчика. Такая команда можетбытьполучена с выхода старшего разрядаадреса тригонометрического коэффици 37 4ента БПФ или представлять собой целую часть тригонометрического коэффициента БПФ и быть сформированной устройством формирования тригонометрического коэффициента процессора.В каждом цикле на выходе сумматора 3. формируется верхний адрес. Для формирования нижнего адреса используется группа сумматоров 4 по модулюдва, причем при расчете стандартных итераций БПФ каждый сумматор 4 по модулю два в группе работает в режиме ИЛИ. На второй вход группы сумматоров 4 по модулю два поступаетпрямой код номера итерации с входа 11 устройства, имеющий единицу в одном разряде, соответствующем номеру итерации, и нули в остальных разрядах. На выходе каждого сумматора по модулю два получается логическая суммаодноименных разрядов сумматора 3 и кода номера итерации с входа 11 устройства, В результате этого коды навыходах сумматора 3 и группы сумматоров 4 по модулю два отличаются на единицу в разряде, определяемом номером текущей итерации, и образуют адреса пар операндов согласно алгоритму БПФ. Для задержки адресов пар операндов на один цикл используются регистры 5 и 6, подключенные к выходам с;мматора 3 и группы сумматоров 4 по .модулю два соответственно. В . начале каждого цикла, в течение которого происходит расчет одной базовой операции БПФ, производится считывание первого и второго операндовиз ОЗУ по адресам А В и А Это происходит при наличии на третьем и четвертом выходах синхронизатора 8 команд "00" и 101" соответственно (фиг. 2 Ъ, н), При наличии команды 00 на управляющих входах коммутатора 7 адресов к выходу 14 устройства через коммутатор 7 адресов подклю чается выход сумматора 3 и формируется верхний адрес -го операнда, а при назтичии команды "О 1" к выходу 14 устройства подключается выход группы сумматоров 4 по модулю два и формируется нижний адрес х-го операнда, ОЗУ при этом находится в режиме считывания и выдает операнды по адресам А иЬ А", на вход АУ процессора БПФ. Пока происходит выполнение -й базовой операции, устройство формирует адреса А и А , по которым производитВ нся запись результатов выполнения(1.-1)-й базовой операпии с операндами, выбранными иэ ОУ н предыдущемцикле, Адреса А, и А, хранятся в8 Н1-1регистрах 5 и 6 и подключаются квходу 14 устройства через коммутатор7 адресов при подаче на управляющиевходы коммутатора команд ",10" и "11",сформированных на третьем и четвертом выходах синхронизатора 8, Адреса А А., А., А Формируются соб н 6 нответственно йри подаче на первыйвход синхронизатора 8 первого, второго, третьего и четвертого тактовыхимпульсов. С приходом четвертого тактового импульса на втором выходе синхронизатора 8 появляется импульс,переводящий счетчик 1 в новое состояние, а триггеры 15 и 16 синхронизатора 8 переходят при этом в нулевоесостояние, При этом к выходу 14 20устройства подключается выход сумматора 3, а с приходом пятого тактовогоимпульса (первого в последующем цикле) - выход группы сумматоров 4 поргмодулю два и так далее. Каждый четвертый тактовый импульс переписываетсодержимое сумматора 3 и группы сумматоров 4 по модулю два в регистры 5й 6 соответственно, т.е. происходит Фиксирование адресов операндовпредыдущего цикла, В начале следующего цикла производится считываниеиз ОЗУ операндов (+1)-й базовой операции по адресам Аи Аа затем6 Нзаканчивается выполнение -й базовой 35операции и производится запись результатов в ОЗУ по адресам А; и А;,находящимся в регистрах 5 и 6, Такаяпоследовательность формирования адресов операндов сохраняется до конца текущей итерации, после чего изменяется код номера итерации на входе 11 устройства и процесс Формнроваия адресов в новой итерации повторяется аналогичным образом,После выполнения всех стандартных итераций БПФ согласно беэыэбыточному алгоритму БПФ образуется специальная итерация, При формировании спе циальной итерации на вход 11 устройства поступает инверсный код номера итерации, т,е. "11111", а на вход 13 устройства - признак специальной итерации, При этом на выходах группы 55 сумматоров 4 по модулю два Формируется инверсное значение кодов, снимаемых с выхода сумматора 3, т,е. сумматоры 4 по модулю два в группе работают в режиме инвертора, Регистр 2 на время выполнения специапьной итерации установлен в нулевое со-. стояние командой с пятого выхода сигнализатора 8, При Формировании адреса первого операнда А, в х-м цикле спе 1циальной итерации на вход переноса сумматора 3 поступает единичная команда с первого выхода синхронизатора 8. Адрес Ац в 1.-м цикле формируется на выходах группы сумматоров 4 по модулю два при отсутствии команды переноса на. первом выходе синхронизатора 8. Адреса операндов предыдущей пары А,.и А .;. формируются на выходе сумматора 3 при отсутствии команды переноса и на выходе регистра 6, Адреса А ., А;, формируются на выходах сумматора 3 и подключаются к выходу 14 устройства через коммутатор 7 адресов при наличии команды "00" на третьем и четвертом выходах синхронизатора 8, адрес А чФормируется на выходах группы сумматоров 4 по модулю два и подключается к выходу 14 устройства при наличии коман ды "01" на третьем и четвертом выходах синхронизатора 8, а адрес Аформируется на выходе регистра 6 и подключается к выходу 14 устройства при наличии команды "11" на третьем и четвертом выходах синхронизатора 8.Каждый четвертый тактовый импульс вызывает изменение состояния счетчика 1 и запись информации с выходов группы сумматоров 4 по модулю два в регистр 6. Таким образом, в первой половине цикла производится считывание операндов иэ ОЗУ по адресам А; и А , а во второй половине - запись результатов арифметических операций над аналогичными операндами иэ предыдущего цикла по адресам А, и А ,;Формула изобретенияУстройство для Формирования адресов процессора быстрого преобразования Фурье, содержащее первый регистр, коммутатор и счетчик, информационный выход которого подключен к информационному входу первого регистра, вход разрешения записи которого является первым тактовым входом уст ройства, выходом адреса которого является выход коммутатора, о т л и -ч а ю щ е е с я тем, что, с цельюповышения быстродействия, в него введены второй и третий регистры, сумматор сумматор по модулю два и синхронизатор, первый выход которогоподключен к входу переноса сумматора,первый и второй входы которого подключены соответственно к информационному выходу счетчика и выходу регистра, выход которого подключен кпервому входу сумматора по модулюдва, первому информационному входукоммутатора и информационному входувторого регистра, выход которого 15подключен к второму информационномувходу коммутатора, третий информационный вход которого подключен к выходу третьего регистра, информационный вход которого соединен с четвертым информационным входом коммутатора и подключен к выходу сумматора по модулю два, вторым входом которого является вход задания номераитерации устройства, вход начальнойустановки, второй тактовый вход ивход задания режима которого являются соответственно входом запуска,тактовым входом и входом задания ре"жима синхронизатора, второй выходкоторого подключен к тактовым входам второго и третьего регистров исчетному входу счетчика, установочный вход которого соединен с входомначальной установки устройства,третий и четвертый выходы которогоподключены соответственно к первомуи второму управляющим входам коммутатора, а пятый выход синхро -низатора подключен к установочному входу первого регист-ра.%Д ЗА.р 1 г.Составитель А. Баранов едактор М, Дылын Техред И.Попович Корректор Л, Патай За ясно"; роизводственно-полиграфическое предприятие, г, Ужг ул, Проектна 29 б 753 Тираж 672 ВНИИПИ Государственного по делам изобретений 113 О 35, Москва, Ж, Рауш