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

 

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

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

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

РЕСПУБЛИК (51) 4 G 06 F 15/332

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

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

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

ll0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 397 1328/24-24 (22) 28.10.85 (46) 23.03.87, Бюл. Р 11 (72) В.И. Папушой и А.А. Мороз (53) 681. 32 (088. 8) (56) Авторское свидетельство СССР

В 548364, кл. G 06 F 15/332, 1976.

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

Ф 922763, кл. G 06 F 15/332 1982.

„„SU„„1298766 А 1 (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

АДРЕСОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных процессоров, реализующих алгоритм быстрого преобразования

1298766

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

Цель изобретения — повьппение быстродействия устройства.

На фиг. 1 представлена функцио- 10 нальная схема устройства; на фиг. 2 функциональная схема синхронизато< ра; на фиг, 3 — временные диаграмм работы синхронизатора; на фиг, 4— функциональная схема узла блокировки, Устройство для формирования адресов процессора быстрого преобразования Фурье состоит из синхронизатора 1, счетчика 2, регистра 3 сднига, R узлов блокировки (разряда) 4.1-4,R и регистров 5 — 9.

Синхронизатор 1 (фиг. 2) содержит g(-триггер 10, регистр 11 сдвига, элементы И 12-14, элемент ИЛИ 15, элементы И 16 ; 26,,элемент ИЛИ 27, 25 элемент И 28, элемент ИЛИ 29, элемент ИЛИ 30.

Увел 4 блокировки содержит элемент И-НЕ 31, элемент HJIH-НЕ 32 и два сумматора 33 и 34 по модулю два °

Устройство для формирования адресов процессора быстрого преобразования Фурье функционирует следующим образом. . В первоначальном состоянии счет- 35 чик 2 установлен в нулевое состояние, в регистре 3 сдвига младший первый разряд установлен в единичное состояние, а остальные R разрядов установлены в нулевое состояние, ре- 40 гистр 11 сдвига блока 1 управления установлен в состояние, при котором на его вцходе А1 — логическая единица, а на выходах А2 — A4 — логический нуль, IK-триггер 10 сброшен, т,е. на инверсном выходе его логирования адресов процессора быстрОГО преобразования Фурье состоит из синхронизатора 1, счетчика 2, регистра

3 сдвига, узлов 4,1-4,R блокировки и регистров 5 — 9. 4 ил, ческая единица, а на прямом выходе логический нуль. На упранляющий вход регистра 11, который включен как кольцевой регистр, поступают тактовые импульсы и логическая единица. появляется последовательно на выходах А1, А2, АЗ, А4, снова на А1 и т,д, Управляющие сигналы вырабатываются схемой, состоящей из элементов 10, 12-30 (фиг. 2), приведены на временной диаграмме (фиг ° 3), где ТИ вЂ” тактовые импульсы, А1 — А4 выходы регистра 11, вход 2 — сигнал на входе синхронизатора 1, ных. 1, вых. 2...,, вых. 14 — сигналы соответственно на первом, втором,..., четырнадцатом выходах синхронизатора 1, ТГ.10 — сигнал на прямом выходе ТК-триггера 10.

Рассмотрим функционирование устройства при работе в i-м цикле i-ro этапа алгоритма быстрого преобразования Фурье, Во время n-ro цикла должна быть адресована и-я пара операндов для считывания их из Оперативного запоминающего устройства и (и-1)-я пара операндов для записи результата обработки операндов предыдущего цикла в оперативное запоми. нающее устройство. Для выдачи адресов операндов предыдущего цикла используются первый, второй, третий и четвертый регистры хранения адреса операнда. Разрядные выходы этих. регистров соединены между собой,а также с разрядными выходами первого регистра 5 и являются выходами устройства, с которьж считывается адрес операнда. Выходы этих регистров имеют три устойчивых состояния. В любой момент времени активНЫМ ЯВЛЯЕТСЯ ТОЛЬКО ОДИН Н3 ЭТИХ регистров> а именно тот, на который подан сигнал чтения из синхронизатора 1, а выходы остальных регистров счетчика 2 поступает ня входы узлов блокировки 4 и проходит на вы- ход узлов 4 блокировки без изменения (для данных выходов счетчика 2 соответствующие узлы блокировки включены по схеме повторителя), а информация с 2 . †.го выхода счетчика 2 блокируется и подменяется информацией, поступающей с выхода синхронизатора 1 на вход соответствующего узла блокировки (узел блокировки

2 -го разряда счетчика включен по схеме инвертора по третьему входу).

В первой половине первого такта сигналом с соответствующего выходя синхронизатора f производится запись адреса первого операнда и-й пары операндов в регистр 5 (третий выход синхронизатора 1 установлен в

3 состояние логической единицы), а также сигналом с седьмого выхода синхронизатора 1 — запись адреса первого операнда и-й пары операндов в регистр 6. Во второй половине первого такта сигналом с пятого выхода. синхронизатора 1 производится чтение адреса первого операнда и-й пары операндов из регистра 5. В первой половине второго такта производится запись второго операнда и-й пары операндов сигналом с шестого выхода синхронизатора 1 — в регистр 5 и сигналом с восьмого выхода синхронизатора 1 — в регистр 7 (при сигнале на третьем выходе синхронизатора 1, установленном в состояние логического нуля). Во второй половине -второго такта производится чтение адреса второго операнда и-й пары операндов из регистра 5 сигналом с пятого выхода синхронизатора 1, а также сигналом с первого выхода синхронизатора 1 перезапись в счетчик 2 адреса второго операнда и-й пары операндов алгоритма быстрого преобразования

Фурье, В конце второго такта IK-триггер 10 синхронизатора 1 изменяет свое состояние на противоположное, чем производится переключение на цикл работы второй группы регистров, если работала первая группа регистров или переключение на цикл работы первой группы регистров, если работала вторая группа. В первой половине третьего такта продолжается чтение адреса второго операнда и-й пары операндов из регистра 5. Во второй половине третьего такта, а также

3 1298766

4 находятся в этот момент времени в высокоимпедансном состоянии. Зались и чтение информации в регистры 6-9,, а также в регистр 5 производятся в соответствии с временной диаграммой, приведенной на фиг, 3. Четыре регист5 ра хранения адреса операнда разбиты на две группы. К первой группе относятся регистры 6 и 7, к второй— регистры 8 и 9. В первом и втором fp тактах п-ro цикла алгоритма быстрого преобразования Фурье производится запись адресов пары операндов и-го цикла в регистры, относящиеся к одной группе, затем происходит переключение IK-триггера 10 синхронизатора 1, чем выбирается другая группа регистров и в третьем и четвертом тактах и-го цикла производится чтение адресов пары операндов (n-1)-ro цикла из этой группы регистров для записи результата обработки этой пары операндов в оперативное запоминающее устройство. В следующем (n+1)-м цикле алгоритма быстрого 25 преобразования Фурье в первых двух тактах производится запись адресов операндов в те же регистры второй группы, с которых в и-м цикле считывались адреса и только в конце второго такта IK-триггер 10 синхронизатора 1 переключается на работу первой группы регистров, Адреса пары операндов. алгоритма быстрого преобразования Фурье на каждом этапе отличаются информацией в одном разряде, номер которого соответствует номеру этапа алгоритма. быстрого преобразования Фурье, причем адрес первого операнда и-й пары операндов О содержит логический нуль в данном разряде, а адрес второго операнда— логическую единицу. Поэтому данный. разряд счетчика 2 блокируется и подменяется или логическим нулем или 4 логической единицей в соответствии с управляющими сигналами, поступающими на узлы 4 блокировки с синхрони затора 1 и с регистра 3 сдвига, Номеру этапа алгоритма быстрого преобэО разования Фурье соответствует состояние регистра 3 сдвига,.В соответствии с этим состоянием на его выходах 1, 2, З...,,i-1, 1+1...,,К+1 присутствует уровень логического нуля, а на выходе 1 — уровень логической единицы. Данные уровни поступают на четвертые входы узлов 4 блокировки, при этом информация с выхонавливается в логическую единицу и производится чтение адреса первого операнда и-й пары операндов из регистрч 5. В первой половине второго такта производится запись адреса второго операнда и-й пары операндов сигналом с шестого выхода синхронизатора 1 в регистр 5 и сИгналом с восьмого выхода синхронизатора 1 в регистр 7 (при сигнале на четвертом выходе синхронизатора 1, установленном в логическую единицу). Во второй половине второго такта и в первой половине третьего такта сигналом с пятого выхода синхронизатора 1 производится чтение адреса второго операнда и-й пары операндов иэ регистра

5„В конце второго такта триггер 10 со счетным входом синхронизатора 1 изменяет свое состояние на противоположное, чем производится переключение на цикл раооты второй группы регистров, если работала первая. группа регистров, или переключение на цикл работы первой группы регистров, если работала вторая группа, Во второй половине третьего такта и в первой половине четвертого такта сигналом с тринадцатого выхода синхронизатора производится чтение адреса первого операнда (n-1.)-й пары операндов из регистра 8. Во второй половине четвертого такта и в первой половине первого такта последующего (и+1)-го цикла сигналом с четырнадцатого выхода синхронизатора 1 производится чтение адреса второго операнда (и-1)-й пары операндов из регистра 9. Затем цикл повторяется до тех пор, пока не будут обработаны все пары операндов беэыэбыточного этапа алгоритма быстрого преобразования Фурье, после чего устройство заканчивает работу.

Формула и э обретения

Устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее синхронизатор, первый регистр, R узлов блокировки (R — разрядность адреса) и счетчик, выход i-ro (i = 1,R) разряда которого подключен к первому входу i-ro узла блокировки,- выход которого подключен к информационному входу х-го разряда первого регистра, выход i†- ro разряда которого является выходом

1-го разряда адреса устройства и под5 1298766 6 в первой половине четвертого, сигналом с тринадцатого выхода синхронизатора 1 производится чтение регистра 8, хранящего адрес первого операнда (n-1)-й пары операндов. В первой половине четвертого такта сигналом с второго выхода синхронизатора производится добавление единицы в счетчик 2. . Во второй половине четвертого так- 10 та, а также в первой половине последующего первого такта производится чтение адреса второго операнда (n-1)-й пары операндов из регистра 9 сигналом с четырнадцатого выхода f5 синхронизатора 1, Цикл повторяется до тех пор, пока не будут обработаны все пары операндов по всем этапам алгоритма быстрого преобразования Фурье, после че- 70

ro устройство начинает вырабатывать адреса пар операндов специального этапа безызбыточного алгоритма быстрого преобразования Фурье. При этом на выходах регистра сдвига 3-1,2,..., 25

R устанавливается уровень логического нуля, а на выходе R+1 — уровень логической единицы. Ни один иэ разрядов счетчика 2 не блокируется узлами 4 блокировки. Информация с раз- З0 рядных выходов счетчика 2 проходит на выход узлов 4 блокировки или с инверсией (сигнал на четвертом выходе синхронизатора 1 установлен в состояние логической единицы), или без инверсии (сигнал на четвертом выходе синхронизатора 1 установлен в состояние логического нуля) и поступает на информационные входы регистров 5-9. 40

Рассмотрим работу устройства при работе в п-м цикле специального этапа алгоритма быстрого преобразования Фурье, В первом такте сигналом на чет- 45 вертом выходе синхронизатора 1 производится инверсия разрядных выходов счетчика 2 узлами 4 блокировки.

В первой половине первого такта производится запись адреса первого операнда и-й пары операндов сигналом с шестого выхода синхронизатора i в регистр 5 и сигналом,с седьмого выхода синхронизатора 1 в регистр 6, Во второй половине первого такта сигналом с второго выхода синхронизатора производится добавление единицы в счетчик 2, а также сигнал на пятом выходе синхронизатора 1 уста12Ч87Ч. ключен к входу 1-го разряда счетчика, счетный суммирующий входы которого подключены соответственно к первому и второму выходам синхронизатора, третий и четвертый выходы которого подключены соответственно к второму и третьему входам i-ro узла блокировки, вход разрешения чтения и вход разрешения записи первого регистра подключены соответствен- 10 но к пятому и шестому выходам синхронизатора, тактовый вход которого является тактовым входом устройства, причем i-й узел блокировки содержит первый и второй сумматоры по модулю 15 два, элемент И-HE и элемент ИЛИ-НЕ, выход которого подключен к первому входу первого сумматора по модулю два, выход которого подключен к первому входу второго сумматора по мо- 20 дулю два, выход которого является выходом узла блокировки, первым входом которого является первый вход элемента ИЛИ-НЕ, вторым и третьим входами узла блокировки являются соответственно второй вход второго сумматора по модулю два и первый вход элемента И-НЕ, выход которого подключен к второму входу первого сумматора по модулю два, вторые входы элемента ИЛИ-НЕ и элемента И-НЕ соединены между собой и являются четвертым входом узла блокировки, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены регистр сдвига и второй, третий, четвертый и пятый регистры, информапионные входы -x разрядов которых подключены к выходу i-ãî узла блокировки, четвертый вход которого подключен к выходу

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

1298766

Г-, .Г-1 Г-1

Г-ГГ- — Г 1 — Г

А3

à — 1 Г 1.=1 Г—

8я.Z

Веа.!

ТГ-5

Вм.2 Lfl йа.6

ГГ== Г1-Г Г1 = — —

ы9

Ва.® Гà — — ГГ

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

Редактор, Е, Папп ТехредЛ.Сердюкова Корректор О.Луговая

Заказ 891/52 Тираж 673 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул, Проектная,