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

 

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

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

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

РЕСПУБЛИН

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

И A8TOPCHOMV СВИДЕТЕЛЬСТВУ (21) 4259459/24-24 (22) 30.04.87 (46),15.12.88. Бюл. № 46 (72) Т.П. Савенкова и В.А. Шаньгин (53) 681.32(088.8) (56) Авторское свидетельство СССР

¹ 999062, кл. G 06 F 15/332, 1979.

Авторское свидетельство СССР № 1056207, кл. G 06 F 15/332, 1981. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ОПЕРАНДОВ ПРОЦЕССОРА БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЪЕ (57) Изобретение относится к вычислительной технике, к устройствам для выполнения быстрого преобразования Фурье, которые могут быть применены в системах цифровой обработки сигналов.

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

1444814

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

UeJIb изобретения — повышение быстродействия.

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

Устройство содержит счетчик 1, мультиплексоры 2 и 3, регистр 4, счетчик 5, мультиплексор 6, регистр

7, преобразователь 8 кодов, мультиплексор 9, счетчик 10, счетчик ите- 20 раций 11, дешифратор 12, счетчик 13 и блок управления 14.

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

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

Устройство формирует адреса алгоритма БПФ для граф-схемы (фиг. 4).

Отличительной особенностью его является то, что закон формирования адресов считывания не зависит от номера итерации, причем адрес первого операнда отличается от второго опе — 45 ранда для одной и той же базовой операции на N/2, где N — размер обрабатываемого массива. Закон формирования адресов записи зависит от номера итерации, причем адрес первого операнда отличается от адреса второ(-1

ro операнда.на 2, где 1 " номер итерации. Как видно из граф-схемы алгоритма, входной и выходной массивы располагаются в памяти в естественном порядке. Счетчик 1 предназначен для формирования первого адреса считывания, а на счетчике 5 формируется второй адрес считывания.

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

БПФ.

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

»О»

Ф

Внешнее устройство выставляет на входах устройства соответственно код операции БПФ (О!) и код размера обрабатываемого массива N. С получением по входу сигнала "Пуск" триггер

20 устанавливается в состояние »1» и разрешает прохождение синхросигналов TÇ на вход счетчика 29.

На соответствующих выходах дешифратора ЗО начинают появляться сигналы ДШ 0 — ДШ 14, стробированные серией Т2. Сигналом ДШ 7 происходит занесение в регистр 27 кода N, определяющего размер обрабатываемого массива. Примем, что коду »001" соответствует N = 32 °

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

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

По сигналу ДШ I 0 устанавливается в состояние »1» триггер 19 и начинает работать счетчик l. Этим же сигналом в счетчике 5 устанавливается код

»0...10000", соответствующий значению N/2 = !6.

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

4 по синхросигналу ТЗ.

Прн значении синхросигнала Т), Равном »О", на вход регистра 4 подключается выход счетчика 1 и положительным фронтом синхросигнала ТЗ фиксируется в регистре 4. Далее состояние счетчиков и 5 по положительному фронту синхросигнала T) увеличивается на единицу и описанным выше способом передается в регистр 4 и далее на выход устройства. Работа счетчика 10, формирующег «лреса записи, в это время блокиров««а нулевым состоянием триггера 36.

1444814

При появлении сигнала ДШ )4 через элемент И 34 триггер 36 устанавливается в состояние "1" и разрешает раI боту счетчика 10, одновременно через: элемент И 26 в счетчике устанавлива— ется код "0010" и работа его блокируется.

Адреса записи формируются следующим образом. Счетчик итераций 11 на 1О первой итерации находится в состоянии и ll

00...1, чта соответствует состоянию "1" на выходе дешифратара 12.При этом на выходе элемента И-ИЛИ 15 передается синхросигнал T), который со- I5 ответствует значению первого разряда адресов записи.

Сдвиговый регистр 16 имеет и разрядов. Значения разрядов счетчика 10, подключенных к входу блока элементов

И-HJIH 15, на выход преобразователя кодов не проходят . На всех инверсных выходах сдвигового регистра 16 (кроме первого разряда) установлен еди25 ничный уровень. При этом значения разрядов счетчикà IО,. подключенных к входам блока элементов И-ИЛИ 15, проходят на выход преобразователя ко— дов. Таким образом, на первой итерации значения адресов записи опреде30 ляются фазой синхросигнала TI (первый разряд) и значением разрядов счетчика 10. С выхода преобразователя 8 кодов код адреса через вход мультиплексора 9 (на входе V мультиплексора 9 при операции БПФ постоянно высокий уровень)и вход мультиплексора 6 переписывается в регистр 7, а затем на выход устройства. При появлении на.выходе счетчика 1 кода "О...

010000", что соответствует значению

N/2 = 16, на выходе мультиплексора

32 устанавливается высокий уровень, что соответствует сигналу окончания итерации. Этим сигналом через элемент И 19 триггер 19 устанавливается в состояние "О" и блокирует работу счетчика 1, устанавливая его в состояние "О". Одновременно через элемент И 26 снимается блокировка счетчика 29 и он начинает счет, начиная с состояния "0010". На выходе дешифратора начинается снова формирование сигналов ДШ2 — ДШ14.

При появлении сигнала ДШ6 триггер

36 устанавливается в состояние "О" и блокирует работу счетчика 10. На этом заканчивается фа6миравание адресов записи операндов для первой итерации.

Далее начинается подготовка устройства к формированию адресов для второй итерации. Сигналом ДШ 8 триггер 21 перебрасывается в противоположное состояние и производит перекоммутацию выходов мультиплексоров

2 и 9. Теперь, на второй итерации, адреса для считывания операндов появляются на втором выходе устройства (на регистре 7), а адреса для записи — на первом выходе устройства (на регистре 4).

Сигналом ДШ 10 в счетчик 11 добачляется единица, и в нем устанавливается код "00)0", соответствующий второй итерации, одновременно этим же сигналом в счетчике устанавливается код, соответствующий значению N/2 = 16, а в регистре сдвига

16 устанавливается код "00...011

Кроме того, сигналом ДШ IO триггер !

9 устанавливается в состояние "1", и разрешает работу счетчика 1 по входу

"+1". Начинается формирование адресов считывание, которое происходит так же, как и на первой итерации. С задержкой, определяемой сдвигом между сигналами ДШ 10 и ДШ 14, сигналом

ДШ 14 устанавливается в состояние триггер 36 и начинает работать счетчик 10, формирующий вместе с преобразователем 8 кодов адреса записи. При этом на второй итерации на выходе дешифратора 12 состояние

"1" устанавливается только на втором выходе. При этом на выход толька второго элемента блока элементов

И-ИЛИ 15 передается синхросигнал T) который определяет значение второго разряда адреса записи. Регистр 16 находится в состоянии "00...011", поэтому на входе шестого элемента блока элементов И-ИЛИ )5 устанавливается значение "1" и первый разряд счетчика 10 поступает на выход первого элемента 15 и определяет значение первого разряда адреса записи.

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

1444814 всех элементов блока элементов И-ИЛИ

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

Работа счетчика 29 по входу "+l" блокируется. Устройство находится в состоянии готовности к исполнению сле- 30 дующей команды.

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

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

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

Дешифратор начинает вырабатывать сигналы, начиная с ДШ 7.

Этим сигналом в регистре 27 фик— сируется код размера массива. Сигналом ДШ8 через элемент И 35 устанавливаются в состояние "0" триггер 21, счетчики 5, 11 и 13 и регистр 16. По сигналу ДШ9 в регистр 23 записывается код команды "10", соответствующий операции безызбыточного алгоритма БПФ. Сигналом ДШ !О устанав— ливается в состояние "1",:триггер )9 и начинает работать счетчик 17.Этим же сигналом в счетчиках 5 и 13 устанавливается код "0...100000", соответствующий значению N = 32, что обеспечивается дешифратором 31 при коде команд "10". Начинается.формирование адресов считывания, причем первый адрес формируется на счетчике 1 в последовательности "0", "!", "2" и т.д, до N/2. Второй адрес считывания образуется на счетчике 5, который при этой операции работает по входу "l",.что определяется элементом ?8, причем адреса формируются в последовательности N, N — 1, N-2 и т.д. до N-N/2-1.

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

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

Адреса записи начинают формиро— ваться по сигналу ДШ!6, т.е. с такой же задержкой, как и при операции БПФ.

Второй адрес записи формируется на счетчике 13, который работает аналогично счетчику 5, с учетом задержки.

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

Выполнение операции заканчивается, и устройство будет находиться в состоянии ожидания следующей команды.!

4448t4

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

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

5 управления, первый счетчик, счетчик итераций, информационный выход которого подключен к входу дешифратора, первый и второй регистры, выходы которых являются выходами соответственно адреса считывания и адреса записи устройства, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в него введен реверсивный счетчик, второй и третий счетчики, первый, второй, третий и четвертый мультиплексоры, сдвиговый регистр, блок элементов И-ИЛИ, первый выход блока управления подключен к управляющим входам первого и второго мультиплексоров, выходы которых подключены к информационным входам соответственно первого и второго регистров, второй выход блока управле— ния подключен к входу обнуления первого счетчика, информационный выход которого подключен к первому информационному входу третьего мультиплексора и входу номера последнего эле- 30 мента блока управления, третий выход которого подключен к счетным входам первого и второго счетчиков, первому входу блока элементов И-ИЛИ и управляющему входу третьго мультиплексора, выход которого подключен к первым ин35 формационным входам первого и второго мультиплексоров, вторые информационные входы которых подключены к выходу четвертого мультиплексора, первый 40 информационный вход которого подключен к выходу блока элементов И вЂ И, второй и третий входы которого подключены соответственно к прямому и инверсному выходам сдвигового регистра, четвертый выход блока управления подключен к суммирующему входу реверсивного счетчика, вычитающий вход которого соединен со счетным входом третьего счетчика, управляющим входом четвертого мультиплексора и под50 ключен к пятому выходу блока управления, шестой выход которого подключен к тактовому входу сдвигового регистра, счетному входу второго счетчика, входам синхронизации приема первого и третьего счетчиков, информационные входы которых подключены к седьмому выходу блока управления, восьмой выход которого подкл»ачен к входам обнуления третьего счетчика, счетчика итераций, сдвигового регистра и реверсивного счетчика, информационный выход которого подключен к второму информационному входу третьего мультиплексора, девятый выход блока управления подключен к входу обнуления второго счетчика, информационный выход которого подключен к четвертому входу блока элементов

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

1устройства, причем блок управления содержит два регистра, два дешифратора, счетчик, два мультиплексора, четыре триггера-, восемь элементов

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

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

l4448l4

1444814

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

Редактор М. Циткина Текред А.Кравчук Корректор Г. Реп|етник

Заказ 6508/50

Тираж 704

Подписное

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

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

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