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

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

1133597 i

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

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

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

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

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в устройство для формирования адресов операндов процессора быстрого преобразования Фурье, содержащее первую и вторую группы элементов И, выходы которых подключены соответственно к первому и второму входам соответствующих элементов ИЛИ группы, выводы которых подключены к информационным входам соответствующих разрядов первого регистра адреса, информационный выход которого является информационным: выходом устройства, первые входы элементов И первой группы объединены и являются входом запрещения формирования адреса устройстпа, а jiepnbie входы элементов И Итерой группы соединены и являются входом разрешения формирования адреса устройства, группой информационных входов которого являются вторые входы соответствующих элементов И второй группы, второй ре|Гистр адреса, введены , второй третий и четвертый элементы И, элемент НЕ, элемент ИЛИ, первый и второйD-триггеры, группа элементов НЕ, реверсивный счетчик информационные выходы разрядов второго регистра адреса подключены к входам соответствующих элементов НЕ группы, выходы которьк подключены к информационным входам соответствующих разрядов реверсивного счетчика, информационные выходы разрядов которого подключены к вторым входам соответствую щих элементов И первой группы и информационным входам соответствующих разрядов второго регистра .адреса, суммирующий вход реверсивного счетчика подключен к выходу первого элемента И, первый вход которого соединей с входом элемента НЕ и подключен к выходу -второго элемента И, первый вход которого соединен сD-входом первогоD-триггера и подключен к инверсному выходу первого D-триггера, прямой выход которого подключен к первому входу третьего элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к первому входу четвертого элемента И, выход которого подключен к вычитающему входу реверсивного счетчика, второй вход четвертого элемента И подключен к выходу элемен та НЕ, инверсньй выход второго D-тригера подключен кD-входу второго D-триггера, счетному входу первого Б-триггера, второму входу второго элемента И и второму входу третьего элемента И, третий вход которого является первым тактовым входом устройства, вторым и третьим тактовыми входами которого являются тактовые входы соответственно реверсивного счетчика и второго регистра адреса, второй вход элемента ИЛИ и второй вход первого элемента И соединены и являются четвертым тактовым входом устройства, пятым тактовым входом ко торого является счетный вход второго) -триггера и тактовый вход первого регистра адреса.

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

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

Узел 2 содержит группы 14 и 15 элементов И, группу 16 элементов ИЛИ При выполнении итерации БПФ на вход 1 узла 2 поступают адреса операндов. На вход i подан разрешающий потенциал, а на вход 3 - запрещающий. Адреса операндов через узел 2 поступают на регистр 1 адреса, а далее к ОЗУ. При выполнении специальной итерации БПФ на вход 3 поступает разрешающий потенциал, а на вход 1 - запрещающий. В этом случае адреса операндов поступают на регистр 1 адреса через вход 4 от счетчика 8.

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

x(n)+x(N-n)

уЫ

,., ч x(n)-x(N-n) y(N-n) ,

1 где п 1 до -j - 1;

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

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

Для обеспечения согласованного режима работы ОЗУ и АУ должно выполняться соотношение

Sr 0.4

где t - время выполнения вычислений в АУ;

- время обращения к ОЗУ. - При выполнении этого соотношения АУ и ОЗУ будут работать одновременно, обеспечивая максимальную производительность процессора. Для обеспечения такого режима необходимо. , 51 чтобы устройство формирования адресов операндов вырабатьшало адреса в порядке, указанном в таблице (для 16-точечного массива). Устройство работает следующим образом. В исхолцрм состоянии все регистры, счетчики и триггеры установлены в положение О сигналом Начальная установка (фиг.2). Сигнал Начальная установка длится во вре мя СИ1 , СИ2, СИЗ, и поэтому эти синхроимпульсы в это время блокированы. Сигналом СИ4 в счетчик 8 пере писывается инверсное состояние регистра 13 и си гналом СИ5 через узел 2 выдачи адресов содержимое счетчика записывается в регистр 1, где адрес хранится на время обращения к ОЗУ. СИЗ устанавливает триггер 11 в состояние 1, и на выходе элемен та И 6 устанавливается низкий уровень. На выходе элемента И 5 низкий уровень и прохождение СИ1 через эле мент И 3 блокировано. На выходе эле мента НЕ 7 высокий уровень и СИ1 через элемент ИЛИ 10 и элемент И 4 проходит навход вычитание счетчи ка 8. В счетчике устанавливается код 1 110.- Сигналом СИЗ содержимое счетчика 8 переписывается в регистр 13, а сигналом СИ4 инверсное значение переписывается в счетчик 8. По сигналу СИЗ содержимое счетчика 8 переписывается в регистр 1 и на выходе устройства формируется второй адрес считывания 0001. Одновременно СИЗ устанавливает триггер 11 в О, а триггер 12 в 1.

0000

13 1 1111 0001

О 0000

О . 0000 14 2 1110

0000

1111

1 -1

0001 1110 0000

1111

-2 0000 1111

-1 1110

0001

1 0010 1101

-1 Состояние выхода элемента И 3 не меняется и СИ1 через элемент 10 и 4 проходит на вход Вычитание счетчика 8. В связи с тем, что на входе элемента И 6 устанавливаются высокие уровни, СИ2 через элементы 6, 10и 4 проходит на вход вычитания счетчика 8. Таким образом, содержимое счетчика уменьшается на две единицы. После прохождения СИЗ, СИ4, СИЗ на регистре 1 формируется первый адрес записи для ОЗУ. Формирование второго адреса записи происходит так же, как и формирование второго адреса считывания. По сигналу СИЗ триггеры 11и 12 устанавливаются в 1, на выходе элемента 3 устанавливается высокий уровень. Теперь СИ1 проходит через элемент И 3 на вход Сложение счетчика 8. Прохождение сигналов через элемент 4 блокируется низким уровнем элемента 7. На счетчике устанавливается код 0001, После прохождения СИЗ, СИ4 и СИЗ на основном регистре устанавливается код 1110, соответствующий очередному адресу считывания. Далее процесс формирования С11гналов периодически повторяется. Состояние регистров, счетчика и. схем элементов И приведено в таблице при формировании адресов для 16-точечного массива чисел. Таким образом, предлагаемое устройство обеспечивает выработку адресов операндов в последовательности, необходимой дпя согласованного режима работы АУ и ОЗУ при выполнении специальной итерации, т.е. по отношению к известному техническому решег ио повьшается производительность процессора БПФ.

1001

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

1000

0111

-1

Cul Cu2

Cu3.

Cu4.

Ca5-.

Ha, ка

W)ITM

.yrs)-i

.U(5)

Bx..Cv-J,

ФУ9.2