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

t1

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

Цель изобретения - расширение функциональных возможностей устрой- ;СТва за счет обработки многомерных сигналов.

На фиг. 1 приведена структурная схема устройства для адресации процессора БПФ; на фиг. 2 - временная диаграмма работы при адресации поворачивающих множителей.

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

Известно четыре основных разновидности алгоритма БПФ с замещением

1. Алгоритм прореживания по времни с прямым упорядочением выходных данных.

2.Алгоритм прореживания по време-35 операндов базовой операции компонен- ни с двоично-инверсным упорядочением выходных данных.

3.Алгоритм прореживания по часто- мируются

те с прямым упорядочением выходных

40

данных.

4.®Алгоритм прореживания по частоте с двоично-инверсным упорядочением выходных данных.

Устройство для адресации процессо-., ра БПФ работает следующим образом.

По сигналу с выхода синхронизатора 5 происходит занесение в регистр 4 сдвига кода

ты XI вектора Х, затем компоненты Х2,...,Х, т.е. последовательно форадреса операндов базовых операций 1.1, 2.1, 3.1. Содержимое накапливающего сумматора 7 при этом не меняется, т.е. все одноименные базовые операции всех компонентов вектора X выполняются с неизменным поворачивающим множителем W°.

После формирования адресов операндов последнего вектора Х- по заднему фронту сигнала последовательности ТИ31 с третьего выхода, синхронизато- JQ ра 5 к содержимому га-разрядного счетчика 6 добавляется единица, счетчик 6 переполняется, так как в нем был коц ,11. . .Jj при m log n, и по сиг- го разрядов

для алгоритмов 2 и 4,

для алгоритмов

1 и 3,

В триггер 13 этим же сигналом заносится О для адресации поворачивающих множителей по алгоритмам 1 и 4, 1 - для адресации поворачивающих множителей по алгоритмам 2 и 3.

5

0

5

0

Этим же сигналом в исходное нулевое состояние приводятся накапливающий сумматор 7, счетчики 8 и 11. Пусть в регистр 4 сдвига занесен код 00...01. Устройство для адресации процессора БПФ формирует адреса операндов в памяти одинаково для алгоритмов 1 и 3. Различие в формировании адресов поворачивающих множителей обеспечивает в одном случае алгоритм прореживания по времени, а в другом - прореживание по частоте. Рассмотрим сначала алгоритм 1 - алгоритм прореживания по времени. Для этого алгоритма в триггер 13 заносится 0. Мультиплексор 12 подключает по второму выходу устройства.первую группу входов, т.е. выходы накапливающего сумматора 7, в котором в начальном состоянии нули (т.е. формируется адрес W°).

Формирование адресов операндов и поворачиваюпщх множителей ведется под управлением содержимого регистра 4 сдвига, которое по сигналу с управляющего выхода k-разрядного счетчика 3 сдвигается влево (в сторону с тарших разрядов) на один разряд после выполнения каждой итерации алгоритма БПФ.

Под управлением последовательностей сигналов ТИ1 и ТИЗ синхронизатора 5 согласно алгоритму БПФ на каждой итерации определяются адреса

операндов базовой операции компонен-

мируются

ты XI вектора Х, затем компоненты Х2,...,Х, т.е. последовательно форадреса операндов базовых операций 1.1, 2.1, 3.1. Содержимое накапливающего сумматора 7 при этом не меняется, т.е. все одноименные базовые операции всех компонентов вектора X выполняются с неизменным поворачивающим множителем W°.

После формирования адресов операндов последнего вектора Х- по заднему фронту сигнала последовательности ТИ31 с третьего выхода, синхронизато- ра 5 к содержимому га-разрядного счетчика 6 добавляется единица, счетчик 6 переполняется, так как в нем был коц ,11. . .Jj при m log n, и по сиг- го разрядов

налу переполнения га-разрядного счетчика 6 происходит добавление единицы к содержимому k-разрядного счетчика 3, а также занесение нового кода в накапливающий сумматор 7, т.е. к ну

левому coдepжимo fy накапливающего сумматора добавляется содержимое и-разрядиого регистра 4 сдвига. Причем, так как на первой итерации содержимое регистра 4 сдвига О0..,01, а накапливающий регистр (k-l)-разрядный, и выходы 1-го, 2-го,,.,, (k-l)-ro разрядов регистра сдвига соединены соответственна с (k-l)-M, (k-2)-M,...,1-м разрядами накапливающего сумматора, то на всей первой итерации содержимое накапливающего сумматора равно нулю, т.е. соответствует адресу W°. Сигнал переполнения k-разрядного счетчика 3 означает окончание, данной итерации. Он поступает на управляющий вход регистра 4 и сдвигает хранящуюся в нем единицу на один разряд влево (в сторону старших разрядов). На второй итерации регистр 4 сдвига содержит код 00.. .010 и накапливающий сумматор 7 .формирует адреса поворачивающих множителей W% , W%... и т.д.

Рассмотрим работу устройства для адресации процесс ора БПФ, когда в регистр сдвига занесен тот же код 00...01 (при объеме выборки N 8 это код 001), а в триггер 13 занесена 1. При этом мультиплексор 12 подключает к выходу устройства вторую группу входов, т.е. выходы (k-1) разрядного счетчика-11, выходы которого подключены инверсно, т.е. выход старшего разряда 1 подключен к младшему (k-l)-My входу и т.д. (на вькоде мультиплексора формируется код, который является двоично-инверсным по отношению к коду самого счетчика) .

Формирование адресов операндов идет полностью аналогично предыдущему случаю, когда в триггере 13 хранился О. В исходном состоянии

счетчики 8 и 11 обнулены, т.е. первые базовые операции всех компонент вектора Х проводятся с поворачивающим множителем W. После формирования адресов операндов последнего 50 вектора Х т-разрядный счетчик переполняется, происходит добавление единицы к содержимому k-разрядного счетчика 3 и (k-2)-разрядного счетчика 8. Этот же сигнал поступает на вто- 55 рой вход (k-l)-ro элемента И, на первый вход которого заведен выход младшего разряда регистра 4 сдвига, где на первой итерации находится 1

40

45

0

5

0

5

5

(фиг. 2), которая разрешает прохождение сигнала на выход элемента И и далее через элемент ИЛИ на вход суммирования счетчика 11, и его содержимое становится равным 01 , а на выходе мультиплексора формируется адрес поворачивающего множителя W , Остальные элементы И на первой итерации закрыты. Далее счетчик 11 формирует коды 10 2, 11, что соответствует поворачивающим множителям W , VP . После окончания итерации на управляющем выходе k-разрядного счетчика формируется сигнал, который сдвигает содержимое регистра сдвига на один разряд влево, и обнуляется (k-1)-разрядный счетчик 11. На второй итерации в регистре сдвига находится код 010, открывается (k-2)-й элемент И (фиг, 2), а на выход элемента ИЛИ проходит сигнал с выхода младшего разряда (k-2)- разрядного счетчика 8. Переключение счетчика 11 происходит в два раза реже, т.е. формируются адреса поворачивающих множителей W°, W°, W , W ит.д.

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

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

Ijk, где k lop; N, N - количество элементов в компоненте X/ входного вектрра Х //Х,... ,, п - мерность векторного процесса, Т - знак транспортирования) разряда которого подключен к выходу i-ro разряда формирователя адреса, вход i-ro разряда которого подключен к выходу i-ro разряда первого счетчика, вход i-ro разряда которого объединен с входом (i-(-k)-ro разряда формирователя адреса и подключен к выходу i-ro разряда регистра сдвига, тактовый вход которого подключен к второму выходу синхронизатора, третий выход которого подключен к тактовому входу формирователя адре- ca, и счетному входу второго счетчика, выход j-ro (j 1,m) разряда которого (где m - Ent (Iog5n)+1)

51

подключен к входу (j+k)-ro разряда регистра адреса, выход переполнения первого счетчика подключен к входу управления сдвигом регистра сдвига, выход последнего разряда которого подключен к входу останова синхронизатора, выход переполнения второ- ,го счетчика подключен к счетному входу первого счетчика, отличающееся тем, что, с целью расширения области применения за счет формирования адреса при обработке многомерных си гналов, в него введены триггер, третий и четвертый счетчики, блок элементов И, накапливающий сумматор, мультиплексор и два элемента ИЖ, причем второй выход синхронизатора подключен к установочному входу накапливающего

Сумматора, первому входу первого эле-20 выход которого подключен к устано- мента ИЛИ, установочному входу третьего счетчика и тактовому входу триггера, выход Которого подключен к управляющему входу мультиплексора, информационные входы т-х (т - 1,k-f) разрядов первой и второй групп ин- формационньпс входов которого подключены к .выходам соответственно га-х

25

вочному входу четвертого счетчика, выходы разрядов мультиплексора являются второй группой выходов адреса устройства, выход переполнения второго счетчика подключен к ному входу третьего счетчика и (k-1)-My входу второй группы блока элементов И,

разрядов соответственно накапливающего сумматора и (k-m)-x разрядов четвертого счетчика счетньй вход которого подключен к выходу второго элемента ИЛИ, ш-й вход которого подключен к т-му выходу блока элементов И, ш-й вход первой группы кото

рого подключен к выходу vm+O-ro разряда регистр сдвига, выход S-ro (S 1,и-2)разряда третьего счетчика подключен к S-му входу второй группы блока элементов И, выход т-го разряда регистра сдвига подключен к входу (k-m)-ro разряда накапливающего сумматора, згактовый вход которого подключен к выходу переполнения второго счетчика, выход переполнения Первого счетчика подключен к второму входу первого элемента lUIH,

выход которого подключен к устано-

вочному входу четвертого счетчика, выходы разрядов мультиплексора являются второй группой выходов адреса устройства, выход переполнения второго счетчика подключен к ному входу третьего счетчика и (k-1)-My входу второй группы блока элементов И,

Изобрет.ение относится к специализированным средствам вычислитель 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