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

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

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

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

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

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

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

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

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

В первоначальном состоянии счет- чик 2 установлен в нулевое состояние в регистре 3 сдвига младший первый разряд установлен в единичное состояние, а остальные R разрядов установлены в нулевое состояние, ре- гистр 11 сдвига блока 1 управления установлен в состояние, при котором на его выходе А1 - логическая единица, а на выходах А2 - А4 - логический нуль, 1К-триггер 10 сброшен, т.е. на инверсном выходе его логи

рования адресов процессора быстрого преобразования Фурье состоит из синхронизатора 1, счетчика 2, регистра 3 сдвига, узлов A.1-A.R блокировки и регистров 5-9. А ил.

О 5

0

5 0 s

5

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

Рассмотрим функционирование устройства при работе в i-м цикле i-ro этапа алгоритма быстрого преобразования Фурье, Во время п-го цикла должна быть адресована п-я пара операндов для считывания их из оперативного запоминающего устройства и (п-1)-я пара операндов для записи результата обработки операндов пре- дьщущего цикла в оперативное запоминающее устройство. Для выдачи адресов операндов предыдущего цикла используются первый, второй, третий и четвертый регистры хранения адреса операнда. Разрядные выходы этих- регистров соединены между собой, а также с разрядными выходами первого регистра 5 и являются выходами устройства, с которых считывается адрес операнда. Выходы этих регистров имеют три устойчивых состояния. В любой момент времени активным является только один из этих регистров, а именно тот, на который подан сигнал чтения из синхронизатора 1, а выходы остальных регистров

находятся в этот момент времени в высокоимпедансном состоянии. Запись и чтение информации в регистры 6-9, а Takme в регистр 5 производятся в соответствии с временной диаграммой, приведенной на фиг, 3. Четыре регистра хранения адреса операнда разбиты на две группы. К первой группе относятся регистры 6 и 7, к второй - регистры 8 и 9. В первом и втором тактах п-го цикла алгоритма быстрого преобразования Фурье Производится запись адресов пары операндов п-го цикла в регистры, относящиеся к одной группе, затем происходит пере- ключение IK-tpHrrepa 40 синхронизатора 1, чем выбирается другая группа регистров и в третьем и четвертом тактах п-го цикла производится чтение адресов пары операндов . (n-l)-ro цикла из этой группы регист ров для записи результата обработки этой пары операндов в оперативное запоминающее устройство. В следую

30

35

40

щем (п+1)-м цикле алгоритма быстрого 25 регистр 6. Во второй половине пер- преобразования Фурье в первых двух тактах производится запись адресов операндов в те же регистры второй группы, с которых в п-м цикле считывались адреса и только в конце второго такта Ж-триггер 10 синхронизатора 1 переключается на работу первой группы регистров. Адреса пары операндов.алгоритма быстрого преобразования Фурье на каждом этапе отличаются информацией в одном разряде, номер которого соответствует номеру этапа алгоритма быстрого преобразования Фурье, причем адрес первого операнда п-й пары операндов содержит логический нуль в данном разряде, а адрес второго операнда - логическую единицу. Поэтому данный разряд счетчика 2 блокируется и подменяется или логическим нулем, или логической единицей в соответствии с управляющими сигналами, поступающими на узлы 4 блокировки с синхронизатора 1 и с регистра 3 сдвига. Номеру этапа алгоритма быстрого преоб- м разования Фурье соответствует состояние регистра 3 сдвига, В соответствии с этим состоянием на его выходах 1, 2, 3,,..,i-1, i+1R+1

присутствует уровень логического нуля, а на выходе 1 - уровень логической единицы. Данные уровни поступают на четвертые входы узлов А блокировки, при этом информация с выхо45

55

вого такта сигналом с пятого выхода. синхронизатора 1 производится чтение адреса первого операнда п-й пары операндов из регистра 5, В первой половине второго такта производится запись второго операнда п-й пары операндов сигналом с шестого выхода синхронизатора 1 - в регистр 5 и сигналом с восьмого выхода синхронизатора 1 - в регистр 7 (при сигнале на третьем выходе синхронизатора 1, установленном в состояние логического нуля). Во второй половине -второго такта производится чтение адреса второго операнда п-й пары операндов из регистра 5 сигналом с пятого выхода синхронизатора 1, а также сигналом с первого выхода синхронизатора 1 перезапись в счетчик 2 адреса второго операнда п-й пары операндов алгоритма быстрого преобразования Фурье, В конце второго такта 1К-триг- гер 10 синхронизатора 1 изменяет свое состояние на противоположное, чем производится переключение на ЦИКЛ работы второй группы регистров, если работала первая группа регистров или переключение на цикл работы первой группы регистров, если работала вторая группа. В первой половине третьего такта продолжается чтение адреса Второго операнда п-й пары операндов из регистр а 5. Во второй половине третьего такта, а также

fO

jr -

2

4

21-2

20

гтои / 7-2 7 дов , Z ,,.., / , ,...,/.

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

0

5

0

5 регистр 6. Во второй половине пер-

5

5

вого такта сигналом с пятого выхода. синхронизатора 1 производится чтение адреса первого операнда п-й пары операндов из регистра 5, В первой половине второго такта производится запись второго операнда п-й пары операндов сигналом с шестого выхода синхронизатора 1 - в регистр 5 и сигналом с восьмого выхода синхронизатора 1 - в регистр 7 (при сигнале на третьем выходе синхронизатора 1, установленном в состояние логического нуля). Во второй половине -второго такта производится чтение адреса второго операнда п-й пары операндов из регистра 5 сигналом с пятого выхода синхронизатора 1, а также сигналом с первого выхода синхронизатора 1 перезапись в счетчик 2 адреса второго операнда п-й пары операндов алгоритма быстрого преобразования Фурье, В конце второго такта 1К-триг- гер 10 синхронизатора 1 изменяет свое состояние на противоположное, чем производится переключение на ЦИКЛ работы второй группы регистров, если работала первая группа регистров или переключение на цикл работы первой группы регистров, если работала вторая группа. В первой половине третьего такта продолжается чтение адреса Второго операнда п-й пары операндов из регистр а 5. Во второй половине третьего такта, а также

;В первой половине четвертого, сигналом с тринадцатого выхода синхронизатора 1 производится чтение регистра 8, хранящего адрес первого операнда (п-1)-й пары операндов, В первой половине четвертого такта сигналом с второго выхода синхронизатора производится добавление единицы в счетчик 2,

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

Во второй половине четвертого так-10 регистр 7 (при сигнале на четвертом

та, а также в первой половине последующего первого такта производится чтение адреса второго операнда (п-1)-й пары операндов из регистра 9 сигналом с четырнадцатого выхода синхронизатора 1,

Цикл повторяется до тех пор, пока не будут обработаны все пары операндов по всем этапам алгоритма быстрого преобразования Фурье, после чего устройство начинает вырабатывать адреса пар операндов специального этапа без.ызбыточного алгоритма быстрого преобразования Фурье, При этом

на выходах регистра сдвига 3-1,2,,,,, 25 цикл работы первой группы регистров.

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

Рассмотрим работу устройства при работе в п-м цикле специального этапа алгоритма быстрого преобразования Фурье.

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

выходе синхронизатора 1, установленном в логическую единицу), Во второй половине второго такта и в первой половине третьего такта сигналом с

пятого выхода синхронизатора 1 производится чтение адреса второго операнда п-й пары операндов из регистра 5« В конце второго такта триггер 10 со счетным входом синхронизатора 1

изменяет свое состояние на противоположное, чем производится переключение на цикл раЗоты второй группы регистров, если работала первая группа регистров, или переключение на

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

40 ДО тех пор, пока не будут обработа- ны все пары операндов безызбыточного этапа алгоритма быстрого преобразования Фурье, после чего устройство заканчивает работу,

45

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

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

55 узла блокировки, выход которого подключен к информационному входу i-ro разряда первого регистра, выходi ro разряда которого является выходом i-ro разряда адреса устройства и под7

ключей к входу i-ro разряда счетчика, счетный суммирующий входы которого подключены соответственно к первому и второму выходам синхронизатора, третий и четвертый выходы которого подключены соответственно к второму и третьему входам i-ro узла блокировки, вход разрешения чтения и вход разрешения записи первого регистра подключены соответственно к пятому и шестому выходам синхронизатора, тактовый вход которого является тактовым входом устройства, причем 1-й,узел блокировки содержит первый и второй сумматоры по модулю два, элемент И-НЕ и элемент ИЛИ-НЕ, выход которого подключен к первому входу первого сумматора, по модулю два, выход которого подключен к первому входу второго сумматора по модулю два, выход Которого является выходом узла блокировки, первым входом которого является первый вход элемента ИЛИ-НЕ, вторым и третьим входами узла блокировки являются соответственно второй вход второго сумматора по модулю два и первь|.й вход элемента И-НЕ, выход которого подключен к второму входу первого суммато12

1298766

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

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

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

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

TH

.ААААААААААААААЛА

32

Редактор, E. Папп

Фес. 4

Составитель А. Баранов Техред Л. Сердюкова

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д, 4/5

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

Фиг.З

J4

Корректор О.Луговая

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