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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

09) (11) 4(51) С 06 F 15/332

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3658228/24-24 (22) 09.08.83 (46) 07.01.85. Бюл. №- 1 (72) З.А. Вуколова и В.А. Шаньгин (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

N - 888130, кл. G 01 F 15/332, 1980 °

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

¹ 788114, кл. G 06 F 15/31, 1979.

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

N- 548863, кл, G 06 F 15/332, 1976 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

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

2 — входом первого 2-триггера и подключен к инверсному выходу первого

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

D-входу второгоD -триггера, счетному входу первого З-триггера, второму входу второго элемента И и второму входу третьего элемента И, третий вход которого является первым тактовым входом устройства, вторым и третьим тактовыми входами которого являются тактовые входы соответственно реверсивного счетчика и второго регистра адреса, второй вход элемента ИЛИ и второй вход первого злемен1133597 та И соединены и являются четвертым счетный вход второго Xf -триггера и тактовым входом устройства, пятым тактовых вход первого регистра адретактовым входом которого является са.

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

Известно индексное устройство процессора быстрого преобразования

Фурье, содержащее счетчики, сдвиговый регистр, регистры, адресный переключатель и устройство управления j1) .

Недостатком данного устройства является то, что при вычислении спект-. ров действительных сигналов произво- !5 дится повышенное число арифметических операций.

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

В данном процессоре блок сравнения при появлении адресов комплексносопряженных гармоник вырабатывает сигнал запрета выполнения арифметических операций, и происходит фор- 30 мирование следующего адреса. Таким образом, в процессоре за счет исключения избыточных операций, связанных с вычислением комплексно-сопряженных гармоник, увеличивается быстродейст- 35 вне в два раза (2) .

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

Кроме того, оперативная память данного процессора используется неэффективно.

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

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

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

Целью изобретения является повышение быстродействия (за счет формирования адресов операндов для согласованного режима работы ОЗУ и АУ процессора БПФ при выполнении специальной итерации безызбыточного. алгоритма БПФ) .

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

x(n)+x*(N-n) y(n) tÄÄ = 4t

<. а YC 1 Р11Й С ТВ 11 > а 11С J)13ble 13ХОД!з! ЭЛЕ ментов И Второй груп11ы 1 оединены и я 13ляются Входом ряэ реUIenия формиpо вания адреса устройства, группой информационных входов которого являются вторые входы соответствующих элементов И второй группы, второй реЗгистр адреса, введены первый, второй, третий и четвертый элементы И, элемент HE3 lelleH HJIH, первый и второй )З-триггеры, группа элементов HE реверсивный счетчик1информационные выходы разрядов второго регистра адреса подключены к входам соответствующих элементов HE группы, выходы которых подключены к информационным входам соответствующих разрядов реверсивного счетчика, информационные выходы разрядов которого подключены к вторым входам соответствую- 20 щих элементов И первой группы и информационным входам соответствующих разрядов второго регистра .адреса, суммирующий вход реверсивного счетчика подключен к выходу первого эле- 25 мента И, первый вход которого соединен с входом элемента НЕ и подключен к выходу .Второго элемента И, первый вход которого соединен с3 -входом первого D-триггера и подключен к инверсному выходу nepsol.oQ -триггера, прямой выход которого. подключен к первому входу третьего элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к первому входу четвертого элемента И; выход которого подключен к вычитающему входу реверсивного счетчика, второй вход четвертого элемента И подключен к выходу элемен-40 та НЕ, инверсный выход второго3-триггера подключен к 13-входу второго

Р-триггера, счетному входу первого

3)-триггера, второму входу второго элемента И и второму входу третьего элемента И, третий вход которого является первым тактовым входом устройства, вторым и третьим тактовыми входами которого являются тактовые входы соответственно реверсивного счетчика и второго регистра адреса, второй вход элемента ИЛИ и второй вход первого элемента И соединены и являются четвертым тактовым входом устройства, пятым тактовым входом ко- 5 торого является счетный вход второго3 -триггера и тактовый вход первого регистра адреса.

На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 — временная диаграмма работы предлагаемого устройств".; на фиг. 3 — блок-схема узла выдачи адресов.

Устройство для формирования адресов содержит регистр 1 адреса, узел

2 выдачи адресов, элементы И 3-6, элемент НЕ 7, реверсивный счетчик 8, группу 9 элементов НЕ, элемент ИЛИ 10, триггеры 11 и 12, регистр 13 адреса.

Узел 2 содержит группы 14 и 15 элементов И, группу 16 элементов ИЛИ.

При выполнении итерации БПФ на вход

1 узла 2 поступают адреса операндов.. !

На вход 1 подан разрешающий потенциал, а на вход 3 — запрещающий. Адреса операндов через узел 2 поступают на регистр 1 адреса, а далее к

ОЗУ. При выполнении специальной итерации БПФ на вход 3 поступает разрешающий потенциал, а на вход 1 — запрещающий. В этом случае адреса операндов поступают на регистр 1 адреса через вход 4 от счетчика 8.

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

Ф х (n) -х* (N-n) у (N-и)

N г"е п=1 до — — 1

* — знак комплексно-сопряженных чисел.

Таким образом, для выполнения специальной итерации необходимо считать два.числа x(n) и х(N-п), произвести вычисления в АУ и записать результаты y(n) и y(N-и) по тем же адресам в ОЗУ.

Для обеспечения согласованного режима работы ОЗУ и АУ. должно выполняться соотношение где t — время выполнения вычисле1у ний в АУ; — время обращения к ОЗУ.

- При выполнении этого соотношения

АУ и ОЗУ будут работать одновременно, обеспечивая максимальную производительность процессора. Для обеспечения такого режима необходимо, 1133597

Код основного ре-.

Код дополнительного

Значение входов

СЧ

Код счетчика

Номер операнда

Режим ОЗУ гистра регистра

0000

0000

Считывание

0001

1110

0000

0001

Запись

0000

0000

0000

0001

1110

Считывание

0010

1101

i 110 чтобы устройство формирования адресов операндов вырабатывало адреса в порядке, указанном в таблице (для

16-точечного массива).

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

В исходном состоянии все регистры, счетчики и триггеры установлены в положение "О" сигналом "Начальная установка" (фиг. 2). Сигнал 10

"Начальная установка" длится во время СИ1, СИ2, СИЗ, и поэтому эти синхронмпульсы в это время блокированы. Сигналом СИ4 в счетчик 8 переписывается инверсное состояние ре- 15 гистра 13 и сигналом СИ5 через узел

2 выдачи адресов содержимое счетчика записывается в регистр 1, где адрес хранится на время обращения к ОЗУ. СИ5 устанавливает триггер 11 20 в состояние "1", и на выходе элемента И 6 устанавливается низкий уровень.

На выходе элемента И 5 низкий уровень и прохождение СИ1 через элемент И 3 блокировано. На выходе элемента НЕ 7 высокий уровень и СИ1 через элемент ИЛИ 10 и элемент И 4 проходит на вход "вычитание" счетчика 8. В счетчике устанавливается код 1 110. — Сигналом СИЗ содержимое счетчика 8 переписывается в регистр

13, а сигналом СИ4 инверсное значение переписывается в счетчик 8. По сигналу СИ5 содержимое счетчика 8 переписывается в регистр 1 и на выходе устройства формируется второй адрес считывания 0001. Одновременно

СИ5 устанавливает триггер 11 в "О", а триггер 12 в "1".

Состояние выхода элемента И 5 не меняется и СИ1 через элемент 10 и 4 проходит на вход "Вычитание" счетчика 8. В связи с тем, что на входе элемента И 6 устанавливаются высокие уровни, СИ2 через элементы 6, 1 О и 4 проходит на вход вычитания счетчика 8. Таким образом, содержимое счетчика уменьшается на две единицы. После прохождения СИЗ, СИ4, СИ5 на регистре 1 формируется первый адрес записи для ОЗУ. Формирование второго адреса записи происходит так же, как и формирование второго адреса считывания. По сигналу СИ5 триггеры

11 и 12 устанавливаются в "1", на выходе элемента 5 устанавливается высокий уровень. Теперь СИ1 проходит через элемент И 3 на вход "Сложение" счетчика 8. Прохождение сигналов через элемент 4 блокируется низким уровнем элемента 7. На счетчике устанавливается код 0001, После прохождения СИЗ, СИ4 и СИ5 на основном регистре устанавливается код 1110, соответствующий очередному адресу считывания. Далее процесс формирования сигналов периодически повторяется. Состояние регистров, счетчика и схем элементов И приведено s таблице при формировании адресов для 16-точечного массива чисел.

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

1133597

Продолжение таблицы т.

Значение

Режим ОЗУ

0010

Запись

0000

1110

0001

1101

0010!

Считывание

0001

1101

1100 .

0011

Запись

0001

0011

1110

1101

0010

1110

1100

Считывание

00f 1

0010 0100

1100

1011

0100

1101

0010

Запись

1100

1101

0011

1011

Считывание

0100

0011

1011

1010

0101

Запись

0101

0011

1100

1100

1011

0100

0100

Считывание

0101

1010

1010

1001

0110

Запись

0110

0100

1011

1011

1010

Offal

0101

1001

Считывание

0110

1001

1000

0111

Запись

0111

0101

1010

1010

1001

0110

Считывание

0110

0111

1000

1000

Запись

1001

0111

1001

1000

Номера операнда

Код счетчика

1000 входов сч

Код. дополнительного регистра

0111

0110

КОД ОснОВного регистра

113359?9

Продолж,ение габлиць!

Реаим ОЗУ

0111

1000

0111

Считывание

1001

0110

0111

1000

0111

1001

Запись

1000

0111

1000

Номера Код счетчи операнда ка

Значение входов

СЧ

Код дополнительного регистра

Код основного регистра

Си1

Си?

СиЮ

Си4

СиХ

Нач. уг-ма

r,(è

t т,(.иФ) .u(s) дхйрl"

gaff-1

ФАР

1133597

Составитель А. Баранов редактор Т. Кугрышева ТехредM.Гергель Корректор M. немчик

Заказ 9948/40 Тираж 710 Подписное

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

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

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