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

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

УСТРО СТВО ДЛЯ ФОРШРОВАЮШ АДРЕСОВ ОЛКРАИДОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОВРАЗОВАНИЯ ФУРЬЕ, содержащее , регистр итерации, выходы разрядов которого соединены с входами разрядов счетчика и соответственно с первыми входами элементов ИШ группы, выходы разрядов счетчика соединены соответственно с вторыми входами элементов НЛП, первым информационным входом KONB jTaTopa адреса и соответственно с входа1 & разрядов первого регистра, выход которого соединен с вторым инflюpмaциoнным входом коммутатора адреса, третий инЛормадаониый вход которого подключен к выходам элементов 1UM группы, а выход коммутатора адреса является выходом устройства, отличаю тем, что, с целью повышения быстродействия , в него введены второй регистр, мультиплексор, два триггера, шесть элементов Н, два элемента ЯПИ и два элемента НЕ, причем выход старшего разряда регистра итераций подключен к первому входу первого элемента И и входу первого элемента НЕ, выход которого подключен к первому входу второго элемента И, выход которого соединен с первым входом третьего элемента И, выход которого подключен к первому входу первого элемента 1ШН, второй вход которого подключен к выходу четвертого элемента И, первый вход которого объединен с первым входом пятого элемента И и входом первого разряда адреса коммутатора адреса, выход второго элемента I1R соединен с вторыми входами i третьего, четвертого и пятого элементов 11 и первым входом шестого эле(Л мента И, выход которого соединен с первым входом второго элемента 11ПИ, второй вход которого подключен к выходу пятого элемента И, выход первого триггера подключен ко вторым входам первого и второго.элементов И и тактовому входу второго триггера, сд выход которого соединен с вторым :| входом шестого элемента И и управляющими входами счетчика первого и второго регистров, выходы элементов НЛИ соединены с информационными входами мультиплексора и соответственно с входами разрядов второго регистра, выхолзы разрядов которого соединены с четвертым информа1щонным входом коммутатора адреса, входы второго и третьего разрядов адреса которого соединены с выходами соответственно второго и первого элe eнтoв ШШ, выход первого элемента И подключен к управляющему входу коммутатора адреса, третий вход четвертого элемента 1, третий вход пятого

I

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

Известно индексное устройство прцессора для адресации операыдЪв и тригонометрических коэс ЬАициентоВ; содержащее два двоичных счетчика, итеративный сдвиговый регистр и логическое устройство управления приращением счетчиков Q.

Однако это уч;тройство не способно выполнять безызбытбчные алгоритм ШФ, кроме того, в нем применяется лишь частичное совмещение операгщй обращения к оперативной памяти и арифметических операций,, что снижает быстродействие процессора БПО,

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

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

Известен также блок формирования адресов для устройства, реализующего быстрое преобразование Фурье содержащий счетчик, узел реконфигурации счетчика, управляемый признаками итерации, .регистр задержки адреса, подключенньй к выходу счетчика, группу элементовHJMj соединенную с выходами счетчика и признакам-я итерации, регистр задержки адреса,подключенный к выходу счетчика, группу элементов ИЛИ, соединенную с выходами счетчика и признаками итерации, выход группы элементов ИЛИ соединен с одним из входов блока выдачи информации, другие входы которого соединены с выходом счетчика и с выходом регистра. Устройство позволяет реализовать безызбыточный алгоритм БПФ 3j.

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

Целью изобретения является повыt

цение быстродействия.

Поставленная цель достигается теы что в устройство дпя формирования адресов операндов процессора быстрого преобразования Фурье, содержащее регистр итерации, выходы разрядов которого соединены с входами разрядов счетчика и соответственно с .первыми входами элементов ИЛИ группы, ВЫХОД) разрядов счетчика соединены соответственно с вторыми входами элемента гШИ, первым информационным входом коммутатора адреса и соответственно с входами разрядов первого регистра, выход которого: еоединен с вторым информационным входом ко1мутатора адреса, третий .информационный вход - которого подключен к выходам элементов IUM группы, а выход коммутатора ;адреса является выходом устройства, в него введены второй регистр, мультиплексор, два триггера,шесть элементов И, два элемента ШШ и два элемента НЕ, причем выход старшего разряда регистра итераций подключей к первому входу цервого элемента И и входу первого элемента НЕ, выход которого под1шючен к первому вхо ду второго элемента И, выход которо.го соединен с первым входом третьего элемента И, выход которого подключен к первому входу первого элемента ИЛИ, второй вход которого подключен к выходу четвертого элемен та И, первый вход которого объединен с первым входом пятого элемента И и входом первого разряда адреса коммутатора ;вдреса, выход второго.элемента ПЕ соединен с вторыми входами третьего, четвертого и пятого элементов П и первым входом шестого эле мента И, выход которого соединен с первым входом второго элемента ILTIi, второй вход которого подключен к выходу пятого элемента И, выход первог триггера подключен к вторым входам первого и второго элементов И и тактовому входу второго триггера, выход которого соединен с вторым входом шестого элемента И и управляюищми входами (четчнка, первого и второго регистров, выхс.ты-элементов 1ШН соеданень с информационными входами мультиплексора и соответственно с входами разрядов второго регистра, выходы разрядов которого соединены с четвертым информационным входом коммутатора адреса, входы второго и третьего раарйдов адерса которого соединены с выходами, соответственно, второго и первого элементов ИГО выход первого элемента И подключен . к управплк1 1ему входу коммутатора адреса, третий вход четвертого элемента И, третий вход пятого элемента И и упранляю1ций вход мультиплексора образуют вход задания объема преобразования устройства, третьи входы третьего и шестого элементов И объединены и вместе с входом второго элемента НЕ и первым входом пятого элемента И образуют вход задания режима устройства, тактовый вход первого триггера является тактовым входом устройства, а информационный выход мультиплексора соединен с управляющим входом регистра итераций На Лиг, 1 изображена блок-схема устройства для Формирования адресов на фиг. 2 - временные диаграммы работы устройства; на Лиг. 3 - подробная функциональная схема узла управления .выдачей адресов. Устройство для (Нормирования адресов операндов процессора БПФ состо-. ит из двоичного счетчика 1 с вход- ной логикой 2, группы элементов ИПИ 3, регистра А итера1Ц1й, первого регистра (задержки адреса) 5, коммутатора 6 адресов, второго регистра (задержки адреса) 7, мультиплексора (узла выбора размера) 8, уала управления выдачей адресов 9,, входа задания размера преобразования 10, тактового входа 11, входа задания режима 12, информационного выхода I3 устройства. Узел управления выдачей адресов (фиг. З) состоит из двухкаскадного делителя частоты синхроимпульсов на триггерах 14 и 15, первый из которых 14 соединен с входной шиной синхроимпульсов первого элемента И 16, второго элемента И 17 (выход старшего разряда 18 регистра 4 итераций), первый элемент НЕ 19, третьего элемента И 20, четвертого элемента И 21, входа Б1№ 12-1 входа задания режима 12, второго элемента НЕ 22, входа Считывание 12-2 входа задания режима 12, пятого, элемента И 23, шестого элемента И 24, тактового выхода 25, входа Запись 12-3, входа задания режима 12, выхода старшего разряда 26 вьрсодного кЪда, первого элемента HTDI 27, выход второго разряда 28 выходного кода, второго элемента ИШ1 29, выход младшего разряда 30 выходного кода управляющего выхода 31. Устройство работает следуюп1им образом. Предварительно по входу 10 устанавливается размер преобразования, например 1024, 512 или 256 точек. Затем по входу 2 устанавливается режим работы блока адресации путем подачи единичного потенциала на одну из линий 12-1-12-3. При влкючении режима подан потенциал на линию 12-1. При этом входные синхроимпульсы поступают на входную шину 11 узла управления выдачей адресов 9, пройдя через делитель на триггерах 14 и 15 с частотой в4 раза меньшей входной. Синхроимпульсы (фиг. 2 а, б, фиг.З) поступают на входную логику 2 счетчика 1,который изменяет свое состояние с каждым входным синхроимпульсом, причем один из разрядов счетчика 1 блокируется с помопью входной логики, управляемой регистром 4, который производит сдвиг 1 с окончанием каждой итеращ-1и. На первой итерации блокируется старший разряд счетчика р на второй - предпоследний раэряд и т.д. Блокируемый разряд счетчика остается в нулевом состоянии, а выход .предь дущего разряда подается .мимо блокируемого в последуюи1ие каскады. Параллельный код с выхода счет чика 1 поступает на группу элементов И.ПИ 3, один из входов которых соединен с одним из разрядов счетЗд1ка 1, а другой вход с соответствующим разрядом регистра 4, На выходе каждого элемента -ИЛИ получается логическая .сумма одноименных разрядов счетчикг 1 и регистра 4. В результате этого коды на выходах счетчика 1 и группы элементов {{ЛИ 3 отличаются на единицу в разряде, определяе мом номером текущей итерации и образуют адреса пар операндов согласно алгоритму БПФ, Для задержки адресов операндов на один такт используются регистры задержки 5 и 7, подключенные к выходу группы элементов ИЛИ 3 и счетчика 1, Задержка адресов используется для совмещения опера1р1й обращения к оперативному запоминающеь-гу устройству (ОЗУ) и арифметических операций, что .иллюст рируется на ter, 2, В начале каждого цикла, в течение которого выполняется одна.базовая операция алгоритма БПФ, производится считывание первого и второго операнда по адре. сам АИ и Af. Это производится при на личии О на выходах триггеров 14 и 15 делителя и при О на входе 18 элементов НЕ 19, 1 на линии БПФ 12-1, при этом на линиях 26, 28 и 30 выходного кода узла управления выдачей адресов присутствует код 000, так как элемент И 21 закрыт нулевым потенциалом с выхода триггера 15, а элемент.И 24 - нулевым потенциалом линии Запись 12-3. При этом к выходу 13 устройствакоммутатором 6 подключается выход двоичного счетчика 1, т.е. адрес первого операнда. С поступлением первого синхроимпульса на вход 11 первый триггер 14 делителя устанавливается в 1, а второй - 15 остаетсяв О,, что приводит к появлению на выходе узла управ ления выдачей адресов кода 001, при этом к выходу 13 устройства подключается адрес второго операнда, обра зованньй на выходе группы элементов ЙШ1 3. ОЗУ при этом находится в режиме Счк тывание и вЫдает операнды по адресам А | и вход арифметического устройства процессора БПФ, и пока происходит выполнение арифметических операхшй блок адресации выбирает адреса А .. и по которым производится запись результатов арифметических операций с операндами; выбранными из ОЗУ в предыдущем дакле. Адреса A.- и А хранятся Е регистрах 5 и 7 и подключаются к выходу коммутатора 6 при подаче на вход 1 второго и третьего синхроимпульсов, выходной код блока 9 имеет при этом вид 010 и ОП соответственно. С приходом четвертого синхроимпульса на выходе 25 появляется выходной синхроимпульс, переВОДЯ1ЦИЙ счетчик I в новое состояШ1е, а триггеры 14 и 15 устанавливаются в нулевое состояние. При этом к выходу I3 подключен выход счетчика 1 , с приходом пятого синхроимпульса на вход 11 на выход 13 подключает ся выход группы элементов ИЛИ 3 и т.д. Кроме этого, четвертый входной синхроимпульс вызывает переписывание содержимого счетчика 1 и группы элементов ИЛИ 3 в регистры 7 и 5 соответственно, т.е. при этом задерживаются адреса операндов предыдуйего цикла. В начале следующего цикла производится считывание из ОЗУ операндов А} и Ац+|, к этому моменту заканчиваются арифметические операции и подключение к выходу 3 адресов А и Af, хранимых в регистрах 5 и 7 позволяет произвести результат вычислений над операндами по адресам их первоначального хр анения. Такая последовательность выполнения базовых операций сохраняется до конца текущей итерации, определяемой выбранным размером преобразования с помощью м /льтиплексора 8, на информационные входы которого -поданы староше разряды с выхода группы элементов lUIIl 3. В зависимости, от кода размера, подаваемого на другой вход , блока 8, признаком сдвига регастра 8, т.е. моментом окончания итерации служит появление 1 на одном из старших разрядов группы элементов ИЛ11 3, С началом следующей итерации порядок проведения адресации операндов происходит аналогично описанному, только изменяются значения адр.есов, так как происходит сдвиг, в регистре 4 и соответствующее перемещение О в блокируемом разряде счетчика 1. После выполнения всех обычных итераций согласно безызбыточ ному алгоритму ВПФ образуется дополнительная итерация, в которой адреса пар операндов должны быть симметричны относительно N/Z, где N - число точек преобразования. Известно, ;что симметричные адреса образуют дополнением одного адреса до Н, и для их получения достаточно образовать дополнительный код к известномуадре су, С этой целью в устройстве выход старшего разряда регистра 4, принйма1огд(Ий значение. во время действия дополнительной итерации, подключен к одному из входов узла управ ления выдачей адресов, а именно к входу 18 элемента Н 17 и элемента FIE 19, при этом выходом элемента НЕ 19 запирается элемент И 16, запрещаю 1вий прохождение на выходную шину кода блока 9 выхода первого триггера 14, однако 1 на выходе этого триггера проходит открытый элемент И 17 и потенциал на управляющей линии 31 вызывает появлетше дополнительного кода на выходе 13 от кода, поданного на вход. Последовательность кодов на выходной пине блока 9 будет следующей за цикл: 000, 000, 010, 010, а вид выходной инЛормагши на выходе 13 таким: состояние счетчика 1; дополнительный код счетчика 1; состояние регистра задержки 7; дополнительный .код регистра 7, Таким образом, в первой половине цикла производится считывание операн дов с адресами А к и Ац.,, а во второй половине цикла запись результатов арифметических операций над аналогичными операндами из предыдур1его цикда. В течение цикла проводится чередо вание адресов считывания одних операндов .с адресами записи операндов из преда1дущего цикла, что позволяет проводить арифметические действия над операндами одновременно с обращением к ОЗУ. Перевод блока адресации в режим записи входных счетчиков производится подачей единичного потенциала на линию Запись 12-3 входа задания режима 12, что приводит к появлению 1 на выходе старшего разряда 26 ..выходного кода узла управления вьщачей адресов 9. В зависимости от кода размера на входах 10-1 и 10-2 выходы 2Я и 30 принимают состояния О или 1, а выходной ко/ узла 9 принимает следующие состоянияJOO, 101, 110 и 11. Так как входные отсчеты при записи должны поступать в двоично-инверсном порядке, к информационному входу коммутатора 6 адресов.выходы счетчика I подключены в двоично-инверсном порядке, т.е. к входу мпадщего разряда коммутатора 6 подключен старший разряд счетчика 1, к входу второго разряда - предпоследний разряд счетчика и т.д. К другому информационному входу коммутатора 6 подключены выходы счетчика 1 в двоично-инверсном порядке, но сдвинутые на 1 разряд влево, т.е. вход младшего разряда коммутатора 6 соединен с предпоследним старшим разрядом счетчика 1, а вход предпоследнего старшего разряда коммутатора 6 соединен с мпадгдгм разрядом счетчика 1, К информационным входам коммутатора 6 также подсоединены в двоично-инверсном порядке сдвинутые на 2 и на 3 разряда выходы счетчика I. Этим достигается уменьшение размера преобразования при переходе от пятого до восьмого значения выходного управляющего кода узла 9. Каждый четвертый из синхроимпульсов на входе 1 вызывает увеличение на I содержимого счетчика I, при этом элементы И 20 и 2I узла управления выдачей адресов 9 закрыты нулевым потенциалом с лишш ВПФ 12-1 и выходной код узла 9 на линиях 26, 28 и 30 определяется .только кодом размера, подаваемым в порядке предварительной установки. Режим Запись заканчивается в момент переполнения счетчика I и устройство переходит в режим ожидания. R режиме Считывание на вход 12-2 подается единичный потенциал, который после инвертирования элементом НЕ 22 запирает элементы И 20, 21, 23, 24 и выходной код узла 9 в режиме Считывание постоянно составляет 000, т.е. к выходу 13 устройства постоянно подключен счетчик 1, который увеличивает свое содержимое с каждым синхроимпульсом, поступающим на его вход, при этом на выходе 13 устройства образуется последовательность возрастаю1цих от О до N- адресов, что соответствует выбранному алгоритму НПО с двоично-инверсным порядком данных на входе и прямым - на выходе. Регистр 4 итераций в режиме Запись и Считывание не изменяет своего состояния, поэтому входная логика 2 не производит блокировку разрядов счетчика 1, сохраняя естественный порядок его счета,

Тажим образом, данное устройство для формирования операндов процессора БПФ способно производить адресаjj

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

i/7

I I II I I I I II

,РП.

лт L

Дя. иЛт-t вперанЗы Ая иАт|

лл

Дли

J Л. L

Лт-1