Арифметическое устройство для процессора быстрого преобразования Фурье Советский патент 1991 года по МПК G06F15/332 

ОЭ

СД СД

ел

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

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

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

vi-г УН

F - ( П9к)(Пткск)х, (1)

F - вектор коэффициентов преобразования Фурье;

X - вектор вещественных входных данных;

n

N - размерность преобразования;

пn-k- „Tk+2

9k 12 ® И,

Т, - I ® vj k ;

ck 1г®и2®4 Ы,

;

I - единичная матрица; P - матрица идеальной перестановки;

IГ О

о s1,

Т - символ транспонирования;

1ч 4

h-k

и-М

D,

.H-k-«

- матрица дискретного преобразования Фурье порядка два; - символ кронекеровского произ- 45 ведения матриц;

- диагональная матрица, содержащая чисто вещественные коэффициенты;

- провоциркулянтная матрица ви- JQ да:

S

(5) 55

5

0

5

Й- - символ комплексного сопряжения.

Элемент q- матрицы S записывается в виде:

q 1 + jtf,

где j -л|-1;

Об - число равное основанию используемой системы счисления. Вычисление преобразования Фурье в соответствии с формулой (1) выпол г няется в два этапа. Первый этап заключается в умножении входного вектора X данных на произведение слабозаполненных матриц Ск и Тц. Поскольку матрицы С ц и Т k содержат чисто вещественные элементы, то на первом этапе все операнды являются чисто вещественным числом. Структура вычисления данного этапа вычисления аналогична структуре вычисления известного алгоритма вычисления быстрого преобразования Фурье по основанию два. Это позволяет выделить базовую операцию для первого этапа вычисления вида:

30

А; X; + Х-4(; А,ч, X;tl)d;,

(6)

где А-, А,1, - результаты выполнения

базовой операции; Х{, X - исходные операнды; d - элемент диагональной матрицы D.

На втором этапе вычисления дискретного преобразования Фурье в соответствии с (1) выполняется умножением блочно-диагональных матриц $к на промежуточных векторных данных Хк, при этом вычислительные затраты данного этапа состоят в выполнении базовых операций вида:

ReYj ReB + ReC-ctflmB-ImC); ImYj oi(ReB-ReC)+ImB + ImC,

(7)

где Re и Im обозначают соответственно вещественную и мнимую части числа; В, С - исходные операции, являются элементами вектора х,(.

Для выполнения базовой операции (7) потребуется выполнить шесть операций :типа сложения и две операции

тривиального умножения на константу фЈ, которая выполняется путем сдвига кода на К разрядов ,

На фиг.1 изображена функциональная схема устройства; на фиг.2 - граф вычисления по алгоритму (1) для N 16; на фиг.З и 4 - структуры базовых операций по формулам (6) и (7) соответственно.

Устройство содержит сумматоры 1-4, вычитатели 5-8, умножители 9-12, коммутаторы 13-17, регистры 18-21, триггер 22, входы 23-29 устройства, вход задания режима 30 устройства, тактовый вход 31 устройства, информационные выходы 32-35 устройства.

Устройство работает следующим образом.

Выполнение алгоритма (1) быстрого преобразования Фурье рассматривается на примере для (см.фиг.2).

На первом этапе вычисления в соответствии с фиг.2 выполняется последовательность базовых операций по фиг.З. Для этого на вход 30 устройства подается сигнал уровня 1, который поступает на управляющие входы коммутаторов 13 и 14 и переводит их в режим передачи данных с их входов на выходы.

Одновременно с приходом первого тактового импульса на вход 31 устройства на входы 23.24,25 и 27 устройства подаются операнды базовой операции по фиг.З, а на входы 26 и 28 устройства - коэффициенты данной базовой операции.

Поступление на входы сумматора 1 и вычитателя 5 первого и третьего one рандов с входов 23 и 25 устройства соответственно позволяет получить на выходах сумматора 1 и вычитателя 5 сумму и разность первого и третьего операндов базовой операции по фиг.З. При этом результатом с выхода вычитателя 5 поступает на вход умножителя 9, на другой вход которого подается первый коэффициент базовой опера ции по фиг.З, что позволяет осуществить умножение разности первого и третьего операндов на первый коэффициент dj, результат которого поступает через вход коммутатора 13 на вход регистра 20. В то же время результат сложения первого и третьего операндов с выхода сумматора 1 подается на вход регистра 18. Аналогично описанному на вход регистра 19 поступает

сумма второго и четвертого операндов базовой операции по фиг.З с выхода сумматора 2, а на вход регистра 21 подается разность второго и четвертого операндов, полученная на выходе вычитателя 6 и умноженная на второй коэффициент dn в умножителе 10.

Через время

10

t

ч+

V

5

0

.-

0

5

5

0

5

где tc - время выполнения операции сложения;

t(. - время выполнения операций умножения;

t.. - время распространения сигнала через коммутатор, на вход 31 устройства поступает второй тактовый импульс, по которому осуществляется запись результатов вычисления в регистры 18-21, а сигнал уровня 1, поступающий с входа 30 на вход триггера 22, поступает на выход 5 последнего. Сигнал высокого уровня с выхода триггера 22 поступает на управляющие входы коммутаторов 15-17 и переводит их в режим передачи данных с входов на выходы. По приходу второго тактового импульса на входы 23 - 27 устройства поступают также очередные исходные операции для базовой операции по фиг.З, а на выход умножителя 7 - второй выходной операнд данной базовой операции, являющийся результатом умножения кода, полученного на выходе вычитагеля 7, на третий коэффициент сЦ базовой опера- ции по фиг.3.

Операнды с выходов регистров 20 и 21 поступают на входы сумматора 4 и вычитателя 8 соответственно, а также через входы коммутаторов 16 и 15 на входы вычитателя 8 и сумматора 4. В результате этого на выходе сумматора 4 формируется третий выходной операнд базовой операции по фиг.З, а операнд, сформированный на выходе вычитателя 8, поступает на вход умножителя 12, где осуществляется его умножение

на коэффициент Ц в соответствии со структурой базовой операции по фиг.З.

К концу второго такта работы устройства ка выходы 32-35 устройства поступают выходные операнды с выходов соответственно сумматора 30 умножителя 11, сумматора 4 и умножителя 12 через вход коммутатора 17.

Кроме того на входах регистров 18-21 по аналогии с описанным формируются промежуточные операнды для данных, поступивших на входы 23-28 устройства на втором такте.

По приходу третьего тактового импульса на вход 31 устройства на выходы 32-35 устройства передаются результаты выполнения базовой операции по фиг.З, в первый - четвертый регистры 18-21 записываются промежуточные результаты, а на входы 23-29 подаются очередные значения входных операндов для базовой операции по j фиг.3.

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

На последнем такте выполнения базовой операции до фиг.З на входах регистров 18-21 формируются промежуточные операнды, которые по приходу очередного импульса записываются в указанные регистры. При этом на вход 30 устройства поступает сигнал уровня О, который переводит коммутаторы 13 и 14 в режим передачи данных с соответствующих входов на выходы. Кроме того, по тактовому импул су на входы 23 и 24 устройства подаются вещественная и мнимая части первого операнда базовой операции по фиг.4, на входы 25 и 27 устройства поступают вещественная и мнимая части второго операнда базовой операции по фиг.4, на вход 29 устройства поступает третий коэффициент базовой операции по фиг.З. Это позволяет к концу данного такта работы устройства на выходах сумматора 1 и 2 получить суммы вещественных и мнимых частей входных операндов в соответствии со структурой вычисления базовой операции по фиг.4, коды которых подаются на входы регистров 18 и 19 соответственно, а на выходах вычитателей 5 и б формируются разности вещественных и мнимых входных операндов, которые поступают через входы коммутаторов 13 и 14 на входы регистров 20 и 2Т.

Соединение. 1-х разрядов выходов . вычитателей 5 и 6 с (1+к)-ми разрядами входов коммутаторов 13 и 14 позволяет осуществтить умножение операндов поступающих на входы ука

0

5

0

5

0

5

0

5

0

5

занных коммутаторов на тривиальный множитель об .

По приходу очередного тактового импульса на вход 31 устройства на входы 32-33 устройства подаются результаты выполнения базовой операции по фиг.З, в регистры 18-21 заносятся промежуточные результаты вычис- ления базовой операции по фиг.4, а на входы 23-27 устройства поступают исходные операнды базовой операции по фиг.4. Кроме того, сигнал уровня О с входа триггера 22 по тактовому импульсу поступает на его выход, что переводит коммутаторы 15 - 17 в режим передачи данных с соответствующих входов на выходы. Это разрешает прохождение кода с выхода регистра 19 через вход коммутатора 15 на вход сумматора 4, на другой вход которого подается код промежуточного результата с выхода регистра 20, что позволяет на выходе сумматора 4 сформировать код мнимой части результата выполнения базовой операции по фиг.4. На выходе вычитателя 8 образуется вещественная часть результата базовой операции по фиг.4 как результат вычитания данных, поступающих на вход вычитателя 8 с выхода регистра 18 через вход коммутатора 16.

Код вещественной части результата выполнения базовой операции по фиг.4 поступает через вход коммутатора 17 на выход 35 устройства.

На данном такте работы устройства на входах регистров 18-21 формируются промежуточные результаты выполнения базовой операции по фиг.4. Таким образом максимальная задержка сигналов на данном такте вычисления

Ч + 2tk

по истечении которого на вход 31 устройства поступает очередной тактовый импульс, по которому на выходы 34 и 36 устройства подаются коды мнимой и вещественной части результата базовой , операции по фиг.4, в регистры 18-21 заносятся промежуточные результаты выполнения базовой операции по фиг.4, а на входы 23,24, 25 и 27 устройства подаются очередные исход- ные операнды базовой операции по фиг.4.

Дальнейшие вычисления по данной базовой операции выполняются в устройстве по описанной схеме.

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

Арифметическое устройство для процессора быстрого преобразования Фурье, содержащее первый, второй и г третий сумматоры, первый, второй третий вычитателя, первый, второй, третий и четвертый регистры, первый, второй, третий и четвертый умножители, первый и второй коммутаторы, 10 причем выход первого регистра подключен к первым входам третьих сумматора и вычитателя, а выход третьего сумматора является первым информационным выходом устройства, о т л и ч а- 15 ю щ е е с я тем, что, с целью шения быстродействия при обработке вещественных данных, в него введены четвертые сумматор и вычитатель, триггер, третий, четвертый и пятый 20 коммутаторы, причем выход первого сумматора подключен к информационному входу первого регистра, тактовый вход которого соединен с тактовыми входами триггера, второго, третьего и четвертого регистров и является тактовым входом устройства, первым информационным входом которого являются соединенные между собой первые входы первого сумматора и перво- 3 го вычитателя, выход которого подключен к первому входу первого умножителя и первому информационному входу первого коммутатора, выход которого подключен к информационному входу 3 третьего регистра, выход которого подключен к первому входу четвертого сумматора и первому информационному входу четвертого коммутатора, выход которого подключен к первому входу 4 четвертого вычитателя, выход которого подключен к первому информационному входу пятого коммутатора и первому информационному входу четвертого умножителя, выход которого подключен 4 к второму информационному входу пятого коммутатора, выход которого является вторым информационным выходом устройства, вторым информационным

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

чен к первому входу третьего умно-

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

ЧЛ

Изобретение относится к вычислительной технике и предназначено для построения устройств обработки сигналов, работающих в реальном масштабе времени. Цель изобретения - повышение быстродействия устройства при обработке вещественных входных данных. Поставленная цель достигается за счет того, что устройство содержит сумматоры 1-4. вычитатели 5-8, умно- жители 9-12, коммутаторы 13-17, регистры 18-21, триггер 22. 4 ил.

Фиг,

ImY