Устройство для адресации процессора быстрого преобразования фурье
Изобрет.ение относится к специализированным средствам вычислитель lf ..lной техники и может быть использовано в системах цифровой обработки сигналов, при построении устройств,, использующих в своей работе алгоритм быстрого преобразования Фурье. Цель изобретения - расширение области применения за счет обработки многомерных сигналов. Поставленная цель достигается за счет того, что устройство содержит регистр 1 адреса, формирователь 2 адреса, счетчик 3, регистр 4 сдвига, синхронизатор 5, счетчик 6, накапливающий сумматор 7, счетчик 8, блок 9 элементов И, элемент ИЛИ 10, счетчик 11, мультиплексор 12, триггер 13 и элемент ИПИ 14, 2 /ил. i СЛ Ю CO 00 I O5 СЛ f W IP
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (gg 4 G 06 F 15/332
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А ВТОРСКОМЪ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3968247/24-24 (22) 22,10,85 (46) 23.03.87. Бюл. Р 11 (7 1) Минский радиотехнический институт (72) А,А. Петровский и А,Н, Цыруль— ников (53) 681.32 (088.8) (56) Рабинер Л., Гоулд Б, Теория и применение цифровой обработки сигналов. — М,: Мир, 1978, Авторское свидетельство СССР
Ф 1040491, кл. С 06 F 15/332, 1983. (54) УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к специализированным средствам вычислитель„„SU„„1298765 А 1 ной техники и может быть использовано в системах цифровой обработки сигналов, при построении устройств,, использующих в своей работе алгоритм быстрого преобразования Фурье. Цель изобретения — расширение области применения за счет обработки многомерных сигналов. Поставленная цель достигается за счет того, что устройство содержит регистр 1 адреса, формирователь 2 адреса, счетчик 3, регистр 4 сдвига, синхронизатор 5, счетчик 6, накапливающий сумматор 7 счетчик 8, блок 9 элементов И, элемент ИЛИ 10, счетчик 11, мультиплексор 12, триггер 13 и элемент ИЛИ 14. а
2,ил, Я
1298765
Изобретение относится к специализированным средствам вычислительной техники и может быть испольэова но в системах цифровой обработки сигналов, при построении устройств, использующих в своей работе алгоритм быстрого преобразования Фурье
° (БПФ) .
Цель изобретения — расширение функциональных возможностей устрой- 10 ства за счет обработки многомерных сигналов.
На фиг. 1 приведена структурная схема устройства для адресации процессора БПФ; на фиг, 2 — временная диаграмма работы при адресации поворачивающих множителей, Устройство для адресации процессора быстрого преобразования Фурье содержит (m+k)-разрядный регистр 1 адерса, формирователь 2 адреса, разрядный счетчик 3, k-разрядный регистр 4 сдвига, синхронизатор 5, m-разрядный счетчик 6 (k-1)-разряд25 ный накапливающий сумматар 7, (k-2); разрядный счетчик 8, блок 9 элементов И, элемент ИЛИ 10, (k-1)-разрядный счетчик 11, мультиплексор 12, триггер 13, элемент ИЛИ 14.
Известно четыре основных разновидности алгоритма БПФ с замещением.
Алгоритм црореживания по времени с прямым упорядочением выходных данных.
2, Алгоритм прореживания по време- 35 ни с двоично-инверсным упорядочением выходных данных.
3. Алгоритм прореживания по частоте с прямым упорядочением выходных данных. 40
4.© Алгоритм прореживания по частоте с двоично-инверсным упорядочением выходных данных.
50 для алгоритмов 2 и 4, 1000...0
k-разрядов
000...0Т для алгоритмов 1 и 3.
В триггер 13 этим же сигналом заносится 0 для адресации поворачивающих множителей по алгоритмам 1 и 4, 1 — для адресации поворачивающих множителей по алгоритмам 2 и 3. устройство для адресации процессо-45 ра БПФ работает следующим образом, По сигналу с выхода синхронизатора 5 происходит занесение в регистр
4 сдвига кода
Этим же сигналом в исходное нулевое состояние приводятся накапливающий сумматор 7, счетчики 8 и 11.
Пусть в регистр 4 сдвига занесен код 00...01. Устройство для адресации процессора БПФ формирует адреса операндов в памяти одинаково для алгоритмов 1 и 3. Различие в формировании адресов поворачивающих множителей обеспечивает в одном случае алгоритм прореживания по времени, а в другом — прореживание по частоте.
Рассмотрим сначала алгоритм 1 — алгоритм прореживания по времени, Для этого алгоритма в триггер 13 заносится О. Мультиплексор 12 подключает по второму выходу устройства. первую группу входов, т.е. выходы накапливающего сумматора 7, в котором в начальном состоянии нули (т.е. фор" мируется адрес Ч ), Формирование адресов операндов и поворачивающих множителей ведется под управлением содержимого регистра 4 сдвига, которое по сигналу с
1 управляющего выхода k-разрядного счетчика 3 сдвигается влево (в сторону старших разрядов) на один разо ряд после выполнения каждой итера" ции алгоритма БПФ, Под управлением последовательностей сигналов ТИ1 и ТИЗ синхронизатора 5 согласно алгоритму БПФ на каждой итерации определяются адреса операндов базовой операции компоненты Х1 вектора Х, затем компоненты
Х2,...,Х„, т.е, последовательно формируются адреса операндов базовых операций 1.1, 2.1, 3.1. Содержимое накапливающего сумматора 7 при этом не меняется, т.е. все одноименные базовые операции всех компонентов r вектора Х выполняются с неизменным
0 поворачивающим множителем Ы
После формирования адресов операндов последнего вектора Х„ по заднему фронту сигнала последовательности
ТИ3, с третьего выхода. синхронизатора 5 к содержимому m-разрядного счетчика 6 добавляется единица, счетчик
6 переполняется, так как в нем был коп 11...1 при m = 1ор п, и по ouo:g р
m разрядов налу переполнения m-разрядного счетчика 6 происходит добавление единицы к содержимому k-разрядного счетчика
3, а также занесение нового кода в накапливающий сумматор 7, т,е. к ну129876 левому содержимому накапливающего сумматора добавляется содержимое
k-разрядного регистра 4 сдвига. Причем, так как на первой итерации содержимое регистра 4 сдвига 00...01, а накапливающий регистр (k-1)-pasрядный, и выходы 1-го, 2-ro» (k-1)-го разрядов регистра сдвига соединены соответственно с (k-1)-м, (k-2)-м,...,1-м разрядами накапли- 10 вающего сумматора, то на всей первой итерации содержимое накапливающего сумматора равно нулю, т.е. соответствует адресу W . Сигнал переполнения
k-разрядного счетчика 3 означает 15 окончание. данной итерации. Он поступает на управляющий вход регистра 4 и сдвигает хранящуюся в нем единицу на один разряд влево (в сторону старших разрядов). На второй итерации 20 регистр 4 сдвига содержит код 00...010, и накапливающий сумматор 7 формиру" ет адреса поворачивающих множителей о 2 2 о
W, W, W,... и т.д.
Рассмотрим работу устройства для
25 ацресации процессора БПФ, когда в регистр сдвига занесен тот же код
00...01 (при объеме выборки N =. 8 это код 001), а в триггер 13 занесена "1". При этом мультиплексор 12 подключает к выходу устройства вторуго группу входов, т.е. выходы (k-1)разрядного счетчика.11, выходы которого подключены инверсно, т.е. выход старшего разряда "1" подключен к 35 младшему (k-1)-му входу и т,д. (на выходе мультиплексора формируется код, который является двоично-инверс-: ным по отношению к коду самого счетчика). 40
Формирование адресов операндов идет полностью аналогично предыдущему случаю, когда в триггере 13 хранился 0, В исходном состоянии 45 счетчики 8 и 11 обнулены, т.е, первые базовые операции всех компонент г вектора Х проводятся с поворачивающим множителем W . После формирования адресов операндов последнего 50 вектора X m-разрядный счетчик переи полняется, происходит добавление единицы к содержимому k-разрядного счетчика 3 и (k-2)-разрядного счетчика
8. Этот же сигнал поступает на вто- 55 рой вход (k-1)-го элемента И, на первый вход которого заведен выход младI шего разряда регистра 4 сдвига, где на первой итерации находится " 1"
5 4 (фиг. 2), которая разрешает прохождение сигнала на выход элемента И и далее через элемент ИЛИ на вход суммирования счетчика 11, и его содержимое становится равным 01, а на выходе мультиплексора формируется адрес поворачивающего множителя W .
Остальные элементы И на первой итерации закрыты. Далее счетчик 11 формирует коды 10, 11, что соответствует поворачивающим множителям
W, W . После окончания итерации на управляющем выходе k-разрядного счетчика формируется сигнал, который сдвигает содержимое регистра сдвига на один разряд влево, и обнуляется (k-i)-разрядный счетчик 11, На второй итерации в регистре сдвига находится код 010, открывается (k-2)-й элемент И (фиг, 2), а на выход элемента ИЛИ проходит сигнал с выхода младшего разряда (k-2)разрядного счетчика 8. Переключение счетчика 11 происходит в два раза реже, т,е. формируются адреса поворачивающих множителей W W WР, W и т.д.
Формула изобретения
Устройство для адресации процессора быстрого преобразования Фурье, содержащее синхронизатор, регистр сдвига, первый и второй счетчики, формирователь адреса и регистр адреса, выходы разрядов которого являются первой группой выходов адреса устройства, первый выход синхро- . низатора подключен к тактовому входу регистра адреса, вход i-r o (i где k = lo8 N, N — количество элементов в комйоненте Х входного вектора Х = 1jX,...,Х„ll, 1 Э п — мерность векторного процесса, Т вЂ” знак транспортирования) разряда которого подключен к выходу i,-го разряда формирователя адреса, вход -го разряда которого подключен к выходу i-го разряда первого счетчика, вход i-ro разряда которого объединен с входом (i+k)-го разряда формирователя адреса и подключен к выходу 1-го разряда регистра сдвига, тактовый вход которого подключен к второму выходу синхронизатора, третий выход которого подключен к тактовому входу формирователя адре са, и счетному входу второго счетчика, выход j-га (j 1,m) разряда которого (где m Ent (logan)+1) 1298765
5 подключен к входу (j+k) -го разряда регистра адреса, выход переполнения первого счетчика подключен к входу управления сдвигом регистра сдвига, выход последнего разряда которого подключен к входу останова синхронизатора, выход переполнения второ,го счетчика подключен к счетному входу первого счетчика, о т л и— ч а ю щ е е с я тем, что, с целью 1О расширения области применения за счет формирования адреса при обработке многомерных сигналов, в него введены триггер, третий и четвертый счетчики, блок элементов И, накап- 15 пинающий сумматор, мультиплексор и два элемента ИЛИ, причем второй выход синхронизатора подключен к установочному входу накапливающего сумматора, первому входу первого эле-20 мента ИЛИ, установочному входу третьего счетчика и тактовому входу триггера, выход которого подключен к управляющему входу мультиплексора, информационные входы m-x (m = 1,k-1,) разрядов первой и второй групп информационных входов которого подключены к выходам соответственно m-x разрядов соответственно накапливающего сумматора и (k-m)-х разрядов четвертого счетчика, счетный вход которого подключен к выходу второго элемента ИЛИ, т-й вход которого подключен к m-му выходу блока элементов И, ш-й вход первой группы которого йодключен к выходу (m+1)- го разряда регистра сдвига, выход S-ro (S = 1,k-2)разряда третьего счетчика подключен к Б-му входу второй группы блока элементов И, выход -ro разряда регистра сдвига подключен к входу (Е-ш)-ro разряда накапливающего сумматора, тактовый вход которого подключен к выходу переполнения второго счетчика, выход переполнения первого счетчика подключен к второму входу первого элемента ИЛИ, выход которого подключен к установочному входу четвертого счетчика, выходы разрядов мультиплексора являются второй группой выходов адреса устройства, выход переполнения второго счетчика подключен к счетному входу третьего счетчика .и (k-1)-му входу второй группы блока элементов И, Г
1298765
ЮыаЬ
pez acme стига
Ааааа 1 с ет см 8 бьиад элемента @Jif 10
rSIJO0bl с ещж6м7
Редактор Е. Папп
Заказ 891/52 Тираж 673 Подписное
ВНИИНИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д, 4/5
Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4
9пра5яяюццц
Aavg z-ца р д юга юед юка,У
Вьиодлереноса
m pmpsAvzu юелжила 6
l9d 8 с етюх е 11
Афеы лФорх. %аюФаг ннажитевей на Вы оде иупьтиллекСОЯ7 13
Составитель А, Баранов
Техред Л.Сердюкова Корректор С. Шекмар
