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

 

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

СВОЗ COBETCHHX

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

РЕСПУБЛИК (19) SU (11) 3(51) G 06 F 15/332

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (9, ".))

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2 1) 3460243/18-24 (22) 02.07.82 (46} 23.11.83, Бюл. М 43 (72) С.N. Иатюшонок (71) Сибирский институт земного магнетизма, ионосферы и распрострачения радиоволн (53} 681.32(088.8)

) (56) 1. "Электроника", 1968, 11 13, с. 4-6.

2, "Автометрия", 1973, Р 3, с, 32-38, 3. Авторское свидетельство СССР

11 548863, кп. 5 06 F 15/332, 1975 (прототип), (54) (57) УСТРО)1СТВО ДЛЯ ФОР191ИРОВАНИЯ

АДРЕСОВ ОПЕРАНДОВ ПРОЦЕССОРА БИСТРОГО ПРЕОВРАЗОВАНИЯ ФУРЬЕ, содержащее, регистр итерации, выходы разрядов которого соединены с входами разрядов счетчика и соответственно с первьпж входами элементов ИЛИ группы, выходы разрядов счетчика соединены соответственно с вторыми входами элементов ИЛИ, первым информационным входом коммутатора адреса и соответственно с входамн разрядов первого регистра, выход которого соединен с вторым информационным входом коммутатора адреса, третий информационный вход которого подключен к выходам элементов И!П1 группы, а выход коммутатора адреса является выходом устройства, отличающее с я тем, что, с целью повышения быстродействия, в него введены второй регистр, мультиплексор, два триггера, шесть элементов И, два элемента ИЛИ и два элемента HF., причем выход старmего разряда регистра итераций подключен к первому входу первого элемента И и входу первого элемента НЕ, выход которого подключен к первому входу второго. элемента И, выход которого соединен с первым входом третьего элемента И, выход которого подключен к первому входу первого элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента

И, первый вход которого объединен с первым входом пятого элемента И и входом первого разряда адреса коммутатора адреса, выход второго элемента НГ соединен с вторыми входами третьего, четвертого и пятого элементов И и первым входом шестого элемента И, вь|ход которого соединен с первым входом второго элемента ИЛИ, второй вход которого подключен к выходу пятого элемента И, выход первого триггера подключен ко вторым входам первого и второго элементов И и тактовому входу второго триггера, выход которого соединен с вторым входом шестого элемента И и управляющими входаьи счетчика первого и второго регистров, выходы элементов

ИЛИ соединены с информационными входами мультиплексора и соответственно с входами разрядов второго регистра, выходы разрядов которого сое" динены с четвертым информационным входом коммутатора адреса, входы второго и третьего разрядов адреса которого соединены с выходами соответствеHHo второго и первого элементов

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

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

Известно индексное устройство про цессора БПФ дпя адресации операндов 10 и тригонометрических коэффициентов, содержащее два двоичных счетчи!са, итеративный сдвиговый регистр и ло— гическое устройство управления приращением счетчиков (1), Однако это устройство не способно выполнять безызбыточные алгоритмы

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

Известно также индексное устройство процессора БПФ, содержащее два

25 двоичных счетчика с входной логикой, итерационный сдвиговый регистр, два логический блока и формирователь номера модуля, предназначенный для одновременной адресации двух операн— дов „2) .

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

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

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

Цепью изобретения является повыC пение быстродействия, По тавленная цель достигается тем, что в устройство для формирования адресов операндов процессора быстрого преобразования Фурье, содержащее регистр итерации, выходы разрядов которого соединены с входами разрядов счетчика и соответственно с,первыми входами элементов ИЛИ группы, выходы разрядов счетчика соединены соответственно с вторыми входами элемента ИЛИ, первым информационным входом коммутатора адреса и соответственно с входами разрядов первого регистра, выход которого соединен с вторым информационным входом коммутатора адреса, третий .информационный вход — которого подключен к выходам элементов ИЛИ группы, а выход коммутатора адреса является выходом устройства, в него введены второй регистр, мультиплексор, два триггера, шесть элементов И, два элемента ИЛИ и два элемента НГ, причем выход старше.— го разряда регистра итераций подклю3 ° 1056 чеи к первому входу первого элемента

И и входу первого элемента HR выход которого подключен к первому входу второго элемента И, выход которо.го соединен с первым входам третьего элемента И, выход которого подключен к первому входу первого элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И, первый вход которого объединен 10 с первым входом пятого элемента ll u входом первого разряда адреса коммутатора адреса, выход второго.элемен« та ИЕ соединен с вторыми входами третьего, четвертого и пятого эле- 15 ментов И и первым входом шестого элемента И, выход которого соединен с первым входом второго элемента !1Д1, второй вход которого подключен к выходу пятого элемента И, выход первого 2!! триггера подключен к вторым входам первого и второго элементов И и тактовому входу второго триггера, выход которого соединен с вторым входом шестого элемента И и управляющими входами четчика, первого и второго регистров, выхсды .элементов ИЛИ соединень с информационными входами мультиплексора и соответственно с входами разрядов второго регистра, 30 выходы разрядов которого соединены с четвертым информационным входом коммутатора адреса, входы второго и третьего разрядов адерса которого соединены с выходами соотнетствен °

35 но, второго и первого элементов ИЛИ, выход первого элемента И подключен к управляющему входу коммутатора адреса, третий вход четвертого элемента И, третий вход пятого элемен40 та И и управляющий вход мультиплексора образуют вход задания объема преобразования устройства, третьи входы третьего и шестого элементов

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

Ha r, изображена блок-схема устройства для Аормирования адресов; на Лиг, 2 — временные диаграммы ра- 55 боты устройства; на фиг. 3 — подробная функциональная схема узла управления .выдачей адресов, 207 4

Устройство для Аормирования адресов операндов процессора БПФ состо- ит из двоичного счетчика 1 с входной логикой 2, группы элементов ИЛИ

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

Узел управления выдачей адресов (Лиг, 3) состоит из двухкаскадного делителя частоты синхроимпульсов на триггерах 14 и !5, первый нз которых 14 соединен с входной шиной синхроимпульсов первого элемента И 16, второго элемента И 17 (ныход старшего разряда 18 регистра 4 итераций), первый элемент НЕ 19, третьего элемента И 20, четвертого элемента И 21 ° входа БИ 12- 1 входа задания режима

12, второго элемента HF. 22, входа

"Считывание" 12-2 входа задания режима 1?, пятого. элемента И 23, шестого элемента И 24, тактового выхода 25, входа "Запись" 17-3, входа задания режима 12, выхода старшего разряда

26 выходного кода, первого элемента

ИЛИ 27, выход второго разряда 28 выходного кода, второго элемента ИЛИ

29, ныход младшего разряда 30 выходного кода управляющего выхода 31

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

Предварительно по входу 10 устанавливается размер преобразования, например 1024, 51? или 256 точек. 3атем ло входу 12 устанавливается режим работы блока адресации путем подачи единичного потенциала на одну из линий 12-1-!2-3. При влкючении режима БП ь подан потенциал на линию !

2-1. При этом входные синхроимпульсы поступают на входную шину 11 узла управления выдачей адресов 9, пройдя через делитель На триггерах 14 и15 с частотой в4 раза меньшей входной. Синхроимпульсы (фиг.2 а, б, фиг.3) поступают на входную логику 2 счетчика l,который изменяет свое состояние с каждым входным синхроимпульсом, причем один из разрядов счетчика 1 блокируется с помощью входной логики, управляемой регистром 4, который произ!

056207 водит сдвиг "!" с окончанием каждой итерации, Па первой итерации блокируется старший разряд счетчика l, на второй — предпоследний разряд и т.д, Блокируемый разряд счет- 5 чика остается в нулевом состоянии, а выход предыдущего разряда подается мимо блокируемого в последующие каскады. Параллельный код с выхода счетчика 1 поступает на группу элементов ИЛИ Зр Один из входов которых соединен с одним из разрядов счетчика 1, а другой вход с соответствующим разрядом регистра 4. На выходе каждого элемента ИЛИ получается логическая сумма одноименных разрядов счетчика l и регистра 4. В результа-, те этого коды на выходах счетчика 1 и группы элементов ИЛИ 3 отличаются на единицу в разряде, определяе- >О мом номером текущей итерации и образуют адреса пар операндов согласно алгоритму БПФ. Для задержки адресов операндов на один такт используются регистры задержки 5 и 7, подключенные к выходу группы элементов

ИЛИ 3 и счетчика 1, Задержка адресов используется для совмещения операций обращения к оперативному запоминающему устройству (ОЗУ) и 30 ариАметических операций, что иллюстрируется на дыг. 2. В начале каждого цикла, в течение которого выполняется одна .базовая операция алгоритма БПФ, производится считывание первого и второго операнда по адре. сам А и А, Это производится при наличии "0" на выходах триггеров 14 и

15 делителя и при "0" на входе 18 элементов НЕ 19, "! на линии БПФ 4О

l2-l, при этом на линиях 26, 28 и 30 выходного кода узла управления выдачей адресов присутствует код 000, так как элемент И 21 закрыт нулевым потенциалом с выхода триггера 15, а 45 элемент И 24 — нулевым потенциалом линии "Запись" 12-3. При этом к выходу 13 устройства коммутатором 6 подключается выход двоичного счетчика 1, т.е. адрес первого операнда.

С поступлением первого синхроимпульса на вход 11 первый триггер !4 делителя устанавливается в "1", а второй — 15 .остается в "0", что приводит к появлению на выходе узла управления выдачей адресов кода 001, при этом к выходу 13 устройства подключается адрес второго операнда, образованный на выходе группы элементов

ИЛИ 3. ОЗУ при этом находится в режиме "Считывание" и выдает операнды по адресам А1, и А на вход ариАметического устройства процессора БПФ, и пока происходит выполнение арифметических операций блок адресации выбирает адреса А - и А, по которым производится запись результатов арифметических операций с операндами, выбранными из ОЗУ в предыдущем цикле. Адреса А1 и А; хранятся в регистрах 5 и 7 и подключаются к выходу коммутатора 6 при подаче на вход 11 второго и третьего сиихроимпульсов, выходной код блока

9 имеет при этом вид 0l0 и 011 соответственно, С приходом четвертого синхроимпульса на выходе 25 появляется выходной синхроимпульс, переводящий счетчик 1 в новое состояние, а триггеры 14 и 15 устанавливаются в нулевое состояние. При этом к выходу 13 подключен выход счетчика 1, с приходом пятого синхроимпуль" са на вход 11 на выход 13 подключается выход группы элементов ИЛИ 3 и т.д, Кроме этого, каждый четвертый входной синхроимпульс вызывает переписывание содержимого счетчика и группы элементов ИЛИ 3 в регистры 7 и 5 соответственно, т,е, при этом задерживаются адреса операндов предыдущего цикла, В начале следующего цикла производится считывание из ОЗУ операндов А +<и A < к этому моменту заканчиваются ариАметические операции и подключение к выходу 13 адресов А и Ащ, хранимых в регистрах

5 и 7 позволяет произвести результат вычислений над операндами по адресам их первоначального хранения.

Такая последовательность выполнения*" базовых операций сохраняется до конца текущей итерации, определяемой выбранным размером преобразования с по" ! мощью мультиплексора 8, на ин(юрмационные входы которого .поданы стар шие разряды с выхода группы элементов ИЛИ 3. В зависимости от кода размера, подаваемого на другой вход блока 8, признаком сдвига регистра

8, т,е. моментом окончания итерации служит появление "!" на одном из старших разрядов группы элементов

ИЛИ 3. С началом следующей итерации порядок проведения адресации операн дов происходит аналогично описанному, только изменяются значения адресов, так как происходит сдвиг "1"

1056207 в регистре 4 и соответствующее перемещение "0" в блокируемом разряде счетчика I. После выполнения всех обычных Итераций согласно безыэбыточному алгоритму ВПФ образуется дополнительная итерация, в которой адреса пар операндов должны быть симметричны относительно М/2, где 11 - число точек преобразования. Известно, что симметричные адреса образуют дополнением одного адреса до И, и для их получения достаточно образовать дополнительный код к известному адресу С этой целью в устройстве выход старшего разряда регистра 4, принимаюший значение,"1" во время действия дополнительной итерации, подключен к одному из входов узла управления выдачей адресов, а именно к входу I8 элемента И 17 и элемента 11Е 19, при этом выходом элемента HF. 19 запирается элемент И 16, запрещаю- щий прохождение на выходную шину кода блока 9 выхода первого триггера

14, однако "1" на выходе этого триг- 25 гера проходит открытый элемент И 17 и потенциал на управляющей линии 31 вызывает появление дополнительного кода на выходе 13 от кода, поданного на вход. Последовательность кодов на выходной шине блока 9 будет следующей за цикл: 000, 000, 010, 010, а вид выходной ИНАормации на выходе

l3 таким: сОстОянию счетчика 1; ДОполни- 35 тельный код счетчика 1; состояние регистра задержки 7; дополнительный ,код регистра 7.

Таким образом, в первой половине цикла производится считывание Операн- 4О дов с адресами А1 и Ак, а во второй половине цикла запись результатов ариАметических операций над аналогичными операндами из предыдущего цикла.

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

"1" на выходе старшего разряда 26 ..выходного кода узла управления вьщачей адресов 9. В зависимости от кода размера на входах 10-1 и 10-2 выходы 28 и 30 принимают состояния "0"

II II или 1, а выходной код узла 9 принимает следующие состояния . l 0 0 1 0 1, 1 1 0 и 1 1, Так как входные отсчеты при записи должны поступать в двоично-инверсном порядке, к инАормационному входу коммутатора 6 адре со в . выходы счетчика 1 подключены в двоично-инверсном порядке, т . е . к входу мп адще го разряда коммутатора 6 под" ключен старший разряд счетчика 1, к входу второго разряда — предпоследний разряд счетчика и т . д . К другому инАормациоиному входу коммутатора 6 подключены выходы счетчика 1 в двоично-инверсном порядке, но сдвинутые íà I разряд влево, т . е . вход младше го разряда коммутатора 6 соединен с предпоследним старшим разрядом счетчика 1, а вход предпоследнего старше го раз ряда коммутатора 6 соединен с младшим разрядом счетчика 1 ° К информационным входам коммутатора 6 также подсоединены в двоично-инвер сном порядке сдвинутые на 2 и на 3 разряда выходы счетчика 1, Этим дости гается уменьшение размера прео бр азо вания при переходе от пятого до восьмого значения выходного управляюще го кода узла 9 .

Каждый четвертый иэ синхроимпульсов на входе 11 вызывает увеличение на "!" содержимого счетчика 1, при этом элементы И 20 и 21 узла управления выдачей адресов 9 закрыты нулевым потенциалом с линии БПФ 12-1 и выходной код узла 9 на линиях ?6, 28 и 30 определяется .только кодом размера, подаваемым в порядке предварительной установки. Режим "Запись" заканчивается в момент переполнения счетчика I и устройство переходит в режим ожидания.

В режиме "Считывание" на вход 12-2 подается единичный потенциал, который после инвертирования элементом НЕ 22 запирает элементы И ?О, 21, 23, 24 и выходной код узла 9 в режиме "Считы" ванне" постоянно составляет 000, т.е. к выходу 13 устройства постояннО подключен счетчик 1, который увеличивает свое содержимое с каждым синхроимпульсом, поступающим на его вход, при этом на выходе 13 устройства о6разуется последовательность возрастающиХ от 0 ДО М-! адресов, что соl0S620?

10 ответствует выбранному алгоритму БПФ с двоично-инверсным порядком данных на входе и прямым — на выходе, Регистр 4 итераций в режиме "Запись" и Считывание не изменяет своего состояния, поэтому входная логика 2 не производит блокировку разрядов счетчика I сохраняя естественный порядок его счета, Таким образом, данное устройство для Аормирования операндов процессора ВПФ способно производить адресацию записи входных выборок в ОЗУ, адресацию считывания коэффициентов фурье иэ ОЗУ, а также адресацию операндов в процессе вычисления козАфициентов Фурье. В последнем режиме данное устройство позволяет вычислять безызбыточные алгоритмы БПФ и производить вычисления с высокой скоростью, так как выбор операндов из ОЗУ или запись s ОЗУ производится одновременно с выполнением ариА метических операций с другими операндами, 1056207

Фвч

ЮтрамУм Ал ийт! 056207

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

Редактор А. Г1андор Техред Л.Пилипенко Корректор А.Зимокосов

Заказ 9308/43 Тираж 706 Подписное

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

И 3035 Москва )К-35 Раушская наб. д. 4/5

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