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

сл

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

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

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

Устройство содержит счетчик I, мультиплексоры 2 и 3, регистр 4, счетчик 5, мультиплексор 6, регистр 7, преобразователь 8 кодов, мультиплексор 9, счетчик 10, счетчик итераций 11, дешифратор 12, счетчик 13 и блок управления 14.

Преобразователь кодов (фиг. 2) содержит блок элементов И-Ш1И 15, состоящий из п элементов, где п - число разрядов адресного устройства, и сдвиговый регистр 16.

Блок управления 14 (фиг. 3) содержит генератор 17 тактовых импульсов, элемент И 18, триггер 19, триггер 20, триггер 21, элемент И 22, регистр 23, элементы И 24-26, регистр 27, элемент И 28 счетчик 29, дешифраторы 30 и 31, мультиплексоры 32 и 33, элементы И 34 и 35, триггер 36 и элемент ИЛИ 37.

Устройство формирует адреса алгоритма БПФ для граф-схемы (фиг. 4). Отличительной особенностью его является то, что закон формирования адресов считывания не зависит от номера итерации, причем адрес первого операнда отличается от второго операнда для одной и той же базовой операции HaN/2, где N - размер обрабатываемого массива. Закон формирования адресов записи зависит от номера итерации, причем адрес первого операнда отличается от адреса второго операнда на 2 , где 1 - номер итерации. Как видно из граф-схемы алгоритма, входной и выходной г ассивы располагаются в памяти в естественном порядке. Счетчик 1 предназначен для формирования первого адреса считьгоания, а на счетчике 5 формируется второй адрес считывания.

Рассмотрим работу устройства при формировании адресов для операции БПФ.

в исходном состоянии все счетчики и регистры установлены в нулевое состояние, триггер 20 установлен в О.

Внешнее устройство выставляет на

0 входах устройства соответственно код операции БПФ (01) и код размера обрабатываемого массива N. С получением по входу сигнала Пуск триггер 20 устанавливается в состояние I

5 и разрешает прохождение синхросигналов ТЗ на вход счетчика 29.

На соответствующих выходах дешифратора 30 начинают появляться сигналы ДШ О - ДШ 14, стробированные

0 серией Т2. Сигналом ДШ7 происходит занесение в регистр 27 кода N, определяющего размер обрабатьшаемого массива. Примем, что коду 001 соответствует N 32.

5 Сигналом ДШ 8 через элемент И 35 устанавливаются в состояние О триггер 21, счетчики 5, 11 и 13 и регистр 16.

Сигналом ДШ 9 в регистре 23 фик0 сируется код 01, соответствующий выполнению операции БПФ.

По сигналу ДШ 1 О устанавливается в состояние 1 триггер 19 и начинает работать счетчик I. Этим же сигна5 лом в счетчике 5 устанавливается код 0...10000, соответствующий значению N/2 16.

Состояние счетчика 5, равное 16, через вход мультиплексора 2 (откры0 тый при значении синхросигнала Т1, равном 1), вход мультиплексора 3 (открытый при состоянии триггера 21 ,

равном О, что соответствует нечетной итерации) фиксируется в регистре с 4 по.синхросигналу ТЗ.

При значении синхросигнала Т1, равном О, на вход регистра 4 подключается выход счетчика 1 и полоп жительным фронтон синхросигнала ТЗ фиксируется в регистре 4. Далее состояние счетчиков I и 5 по положительному фронту синхросигнала Т1 уве- личивается на единицу и описанным вьпие

С способом передается в регистр 4 и далее на выход устройства. Работа счетчика 10, формирующетм адреса записи, в это время блокирована нулевым состоянием триггера 3fi,

При появлении сигнала через элемент И 34 триггер 36 устанавлива- ется в состояние 1 и разрешает ра- боту счетчика 10, одновременно через элемент И 26 в счетчике устанавливается код 0010 и работа его блокируется.

Адреса записи формируются следующим образом. Счетчик итераций 11 на первой итерации находится в состояни 00...1, что соответствует состоянию 1 на выходе дешифратора 12.При этом на выходе элемента И-ИЛИ 1 5 пе- редается синхросигнал Т1, который со ответствует значению первого разряда адресов записи.

Сдвиговый регистр 16 имеет п разрядов. Значения разрядов счетчика 10 подключенных к входу блока элементов И-ИЛИ 15, на выход преобразователя кодов не проходят . На всех инверсных выходах сдвигового регистра 16 (кроме первого разряда) установлен единичный уровень. При этом значения разрядов счетчика 1 О,.подключенных к входам блока элементов И-ИЛИ 15, проходят на выход преобразователя кодов. Таким образом, на первой итерации значения адресов записи определяются фазой синхросигнала Т1 (первый разряд) и значением разрядов счетчика 10. С выхода преобразователя 8 кодов код адреса через вход мультиплексора 9 (на входе V мульти- плексора 9 при операции БПФ постоянно высокий уровень)и вход мультиплексора 6 переписывается в регистр 7, а затем на выход устройства. При появлении на выходе счетчика 1 кода 0. . . 010000, что соответствует значению N/2 16, на выходе мультиплексора 32 устанавливается высокий уровень, что соответствует сигналу окончания итерации. Этим сигналом через эле- мент И 19 триггер 19 устанавливается в состояние О и блокирует работу счетчика 1, устанавливая его в состояние О. Одновременно через элемент И 26 снимается блокировка счет- чика 29 и он начинает счет, начиная с состояния 0010. На выходе дешифратора начинается снова формирование сигналов ДШ2 - ДШ14.

При появлении сигнала ДШ6 триггер 36 устанавливается в состояние О и блокирует работу счетчика 10. На это

0

5

0

;; ц

0 5

35

55

заканчивается формирование адресов записи операндов для первой итерации.

Далее начинается подгртовка устройства к формированию адресов для второй итерации. Сигналом ДШ 8 триггер 21 перебрасывается в противоположное состояние и производит перекоммутацию выходов мультиплексоров 2 и 9. Теперь, на второй итерации, адреса для считьшания операндов появляются на втором выходе устройства (на регистре 7), а адреса для записи - на первом выходе устройства (на регистре 4).

Сигналом ДШ 1 О в счетчик 11 добавляется единица, и в нем устанавливается код 0010, соответствующий второй итерации, одновременно этим же сигналом в счетчике устанавливается код, соответствующий значению N/2 16, а в регистре сдвига 16 устанавливается код 00...011. Кроме того, сигналом ДШ 10 триггер 19 устанавливается в состояние и разрешает работу счетчика I по входу +1. Начинается формирование адресов считывание, которое происходит так же, как и на первой итерации. С задержкой, определяемой сдвигом между .сигналами ДШ 10 и ДШ 14, сигналом ДШ 14 устанавливается в состояние 1 триггер 36 и начинает работать счетчик 10, формирующий вместе с преобразователем 8 кодов адреса записи. При этом на второй итерации на выходе дешифратора 12 состояние 1 устанавливается только на втором выходе. При этом на выход только второго элемента блока элементов И-ИЛИ 15 передается синхросигнал Т1, который определяет значение второго разряда адреса записи. Регистр 16 находится в состоянии 00...011, поэтому на входе шестого элемента блока элементов И-ИЛИ I5 устанавливается значение 1 и первый разряд счетчика 10 поступает на выход первого элемента 15 и определяет значение первого разряда адреса записи.

На входах остальных элементов блока элементов И-ИЛИ I5 устанавливается уровень О, и значения разрядов счетчика 10, подключенных к входу блока элементов И-ИЛИ 15, на выход не проходят. На инверсном выходе сдвигового регистра 16 устанавливается код 11...100, поэтому разряды счетчика 10, подключенные к входам

514

всех элементов блока элементов 15, начиная с третьего, проходят на выход преобразователя кодов. При этом второй разряд счетчика поступает на выход третьего элемента, третий разряд - на вькод четвертого элемента и т.д. Таким образом, на второй итерации первый разряд адреса записи определяется значением первого разряда счетчика 10. Второй разряд определяется значением синхросигнала Т1, Третий и последующие разряды адреса записи определ5ш тся значением разрядов счетчика 10, начиная с второго. На первом выходе формируется последовательность адресов для записи операндов. Далее процесс продолжается аналогично описанному вьше и формируются адреса считывания адресов по- следней итерации, что соответствует значению единицы на пятом вькоде дешифратора 12 (при N 32),- на выходе мультиплексора 33 устанавливается высокий уровень. При появлении сигнала ДШ7 через элемент 22 сбрасываются регистр 23 и триггер 20. Работа счетчика 29 по входу -Hi блокируется. Устройство находится в состоянии готовности к исполнению еле- дующей команды.

Рассмотрим работу устройства при формировании адресов для операции безызбыточного алгоритма БПФ.

Как известно, для выполнения one- рации безызбыточного алгоритма необходимо сформировать следующую последовательность адресов О и N, 1, и N- l, 2 и N-2 и т.д. Порядок адресов считьшания и записи одинаков.

Для вьтолнения этой операции внеш .нееустройство выставляет на втором и третьем входе устройства код операции 10 и код размера обрабатьгоае- мого массива N (пусть N 32 и ему соответствует код 001). При получении по первому входу сигнала Пуск триггер 20 устанавливается в состояние 1 и разрешает прохождение синхросигналов 13 на вход счетчика 29. Дешифратор начинает вырабатьшать сигналы, начиная с ДШ 7 с

Этим сигналом в регистре 27 фиксируется код размера массива. Сигналом ДШ8 через элемент И 35 устанав- ливаются в состояние О триггер 21, счетчики 5, 11 и 13 и регистр 16. По сигналу ДШ9 в регистр 23 записыва46

ется код команды 10, соответствующий операции безызбыточного алгоритма БПФ. Сигналом ДШ 10 устанавливается в состояние 1,триггер 19 и начинает работать счетчик 17.Этим же сигналом в счетчиках 5 и 13 устанавливается код 0...100000, соответствующий значению N 32, что обеспечивается дешифратором 31 при коде команд 10. Начинается .формирование адресов считывания, причем первый адрес формируется на счетчике 1 в последовательности О, 1, 2 и т.д. до N/2. Второй адрес считывания образуется на счетчике 5, который при этой операции работает по входу 1,,что определяется элементом 28, причем адреса формируются в последовательности N, N-1, N-2 и т.д. до N-N/2-1.

Коммутация адресов на выходе устройства осуществляется аналогично операции БПФ.

Адреса записи образуются на счетчиках 10 и 13, причем преобразователь 8 кодов работает как на первой итерации алгоритма БПФ, т.е. первый разряд совпадает со значением синхросигнала Т1 5 а остальные разряды определяются значением разрядов счетчиков 10.

Адреса записи начинают формироваться по сигналу ДШ16, т.е. с такой же задеряской, как и при операции БПФ. Второй адрес записи формируется на счетчике 13, который работает аналогично счетчику 5, с учетом задержки. Сформированные адреса записи через мультиплексоры 9 и 6 поступают на вход регистра 7, а затем на второй выход устройства. При появлении на выходе счетчика 1 кода 0...10000, что соответствует значению N/2, на выходе мультиплексора 32 вырабатывается сигнал Конец итерации, который через элемент 18 устанавливает триггер 19 в состояние О, и работа счетчика 1 блокируется. Одновременно начинает работать счетчик 29, и с появлением сигнала ДШ6 устанавливается в состояние О триггер 36 и блокируется работа счетчика 10. Далее сигналом да17 через элемент 22 устанавливается в состояние О регистр 23 и сбрасывается триггер 20. Вьшолнение операции заканчивается, и устройство будет находиться в состоянии ожидания следующей коматгды.

144А8

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

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

0

5

8

0

5

0

5

0

5

148

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

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

с 0

5

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

J/t фиг Ч 7/J

м

Изобретение относится к вычислительной технике, к устройствам для выполнения быстрого преобразования Фурье, которые могут быть применены в системах цифровой обработки сигналов. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входит счетчик 1 , мульпшлек- соры 2,3, регистр 4, счетчик 5, мультиплексор 6, регистр 7, преобразователь кодов 8, состоящий из сдвигового регистра и блока элементов И-ИЛИ, мультиплексор 9, счетчик 10, счетчик итераций 11, дешифратор 12, счетчик 13 и блок управления 14. 5 ил.

«о

JUb

l2Z

Гч11

;

13

к tV5 -Ч

b

cr

Ч -о ««

ь

Составитель A. Баранов Редактор М. Циткина Техред А.Кравчук

Заказ 6508/50

Тираж 704

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

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

:э

e

N

2

:з Co §

c:t §

r-.tNj

t§

Корректор Г. Решетник

Подписное