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

О зз

yuuuj/с i егте umuCnlCH К ЬЫЧИСЛИТвЛЬной технике и предназначено для построения устройств обработки сигналов, работающих в реальном масштабе времени.

Цель изобретения - повышение быстродействия устройства при обработке комплексно-сопряженных входных данных.

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

п - 1 п -2 ( П CkTk П & ) X , k - оk - о

0)

15

где F (f0, fi, f2fN-i)T - вектор коэффициентов преобразования Фурье;

X - вектор входных данных, обладающих свойством комплексного сопряжения, которое можно выразить соотношением

Xi

I 1.М/9-1,

где

символ комплексного сопряжения;

Х0, Хм/2 являются чисто вещественными числами;

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

Оставшиеся члены выражения (1) описываются формулами:

, п -k - 1

W2 ® I 2k

V ч k + 1

(2)

Tk | 2 п - k - 1 v 2 k + 1 :(3)

|)| ® Mf k РТ2 п - k ,(4)

где 1Г - единичная матрица размерности;

А/2 - матрица преобразования Фурье размерности два;

& - символ кронекеровского произведения матриц;

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

V 9к+1

I 9k О

D ok

, n -k -1

0

n - k - 1

45

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

Р - матрица идеальной перестановки;

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

g t0 0 ... 0 g

0...0 0

000 gt 0

00 0 ... g g

(5)

55

0

5

0

5

Элемент q матрицы S описывается выражением g 1 + j (Л., где а - число, равное основанию срользуемой системы счисления; j 1 .

Вычисление преобразования Фурье по формуле (1) выполняется в два этапа. На первом этапе производится умножение входного вектора X на блочно-диагональ- ные матрицы вь . Результатом данного этапа является вектор промежуточных данных X. элементы которого являются вещественными числами.

На втором этапе алгоритма (1) осуществляется выполнение итераций вычисления, аналогичных классическому алгоритму быстрого преобразования Фурье, с той лишь разницей, что все операнды и коэффициенты являются чисто вещественными числами.

Основой вычислительных затрат на пер-, вом этапе вычисления является процедура умножения промежуточного вектора данных X или части его на матрицу S вида (5), при этом результат данного умножения обозначается вектором Y, а элементы его представляются в виде

Yi gXi + g X м

(6)

где

m означает приведение числа по

0

5

0

5

0

5

модулю т;

т - размерность матрицы S; Xi и X - элементы вектора X. Обозначим Xi через В, а X через С

в результате выражение (6) примет вид

ReYi ReB + ReC-a(lmB - ImC);

lmY, ImB + lmC + «(ReB - ReC), (7) где Im и Re - обозначают мнимую и вещественную части числа.

Соотношение.(7) следует трактовать как аналитическое выражение базовой операции первого этапа алгоритма (1) вычисления преобразования Фурье.

На втором этапе вычисления по формуле (1) выполняется последовательность операций типа бабочка :

AJ X, + Хи-1 di:

Am XI - Хн- rdi,(8)

где Ai, Am - результаты выполнения операции типа бабочка ;

di - элемент вещественной диагональной матрицы D;

Xi, Xj+i - элементы некоторого промежуточного вектора данных.

Объединение четырех операций (8) (по две операции с двух соседних итераций вычисления) при N 49 позволяет получить укрупненную базовую операцию, для выполнения которой потребуется четыре выходных операнда ХьХ2,Хз и ХА и три коэффициента di,d2 и da.

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

Устройство (фиг.1) содержит умножители 1-4, коммутаторы 5-9, триггер 10, сумматоры 11-13,вычитатели , сумма- торы-вычитатели 17 и 18, регистры 19-22, элемент НЕ 23, входы 24-30, тактовый вход 31, вход 32 задания режима и информационные входы 33-36.

Устройство работает следующим образом (фиг.2-4),

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

Для этого на вход 32 устройства подается сигнал уровня О, который поступает на адресные входы коммутаторов 5 и 6 и переводит их в режим передачи данных с первых входов на выходы. Кроме того, сигнал уровня О поступает на вход управления первого сумматора-вычитателя 17 и переводит его в режим вычитания данных. Приход указанного сигнала на вход элемента НЕ 23 инвертирует его, в результате сигнал высокого уровня с выхода элемента НЕ 23 поступает на вход управления второго сумматора-вычитателя 18 и переводит его в режим сложения операндов.

На первом такте работы устройства на входы 24 и 25 подаются вещественные части первого и второго операндов базовой операции фиг.З, а на входы 27 и 28 поступают мнимые части первого и второго операндов соответственно. Через время, равное времени выполнения операции сложения и времени распространения сигнала через коммутатор, на выходах сумматора 11 и вы- читателя 14 формируются результаты сложения и вычитания вещественных частей первого и второго операндов фиг.З, что обеспечивается подачей на сумматор 11 и вычитатель 14 вещественной части первого операнда с входа 24, а на другие входы первого сумматора 11 и первого вычитателя 14с входа 25 устройства через вход первого коммутаторов 5 - вещественной части второго операнда.

Аналогично на выходах сумматоров-вы- читателей 17 и 18 формируются разность и сумма мнимых частей первого и второго операндов фиг.З соответственно. Это позволяет к концу первого такта работы устройства на входы регистров 19 и 20 подать сумму и разность вещественных частей первого и второго операндов, а на входы регистров 21 и 22 - разность и сумму мнимых частей первого и второго операндов базовой операции фиг.З.

По приходу тактового импульса на тактовые входы указанных регистров происходит запись в них операндов, находящихся на входах, а на входы 24,25.27 и 28 поступают входные операнды базовой операции фиг.З аналогично описанному.

Кроме того, по приходу тактового импульса на тактовый вход триггера 10 на его выходе устанавливается сигнал уровня О, поступивший на его вход в первом такте работы устройства Сигнал уровня О с выхода триггера 10 поступает на управляющие входы коммутаторов 7,8 и 9 и переводит их в режим передачи данных с их входов на выходы.

Это позволяет на втором такте работы

устройства на выходе сумматора 13 получить результат сложения суммы мнимых частей, поступающей на вход сумматора 13 с выхода регистра 22 через вход коммутатора 9, и разности вещественных

частей, поступающей на вход сумматора 13 с выхода регистра 20 через вход коммутатора 7.

Код разности вещественных частей

входных операндов поступает на вход коммутатора 7 со сдвигом на К разрядов, определяемых величину тривиального множителя а . На выходе вычитате 15 формируется разность суммы вещественны частей первого и второго операндов базовой операции фиг.З, поступающей на вход вычитателя 15 с выхода регистра 19, и разности мнимых частей первого и второго операндов, поступающей на вход вычитателя 15 с выхода регистра 21 через вход коммутатора 8 При этом на входе коммутатора 8 осуществляется умножение операнда чз множитель а в соответствии со структурой базовой операции фиг.З. Таким образом, к

концу второго такта работы устройства на выходах сумматора 13 и вычитателя 15 формируются соответственно мнимая и еещест- венная части результата выполнения базовой операции фиг.З, которые поступают на выходы 34 и 35 устройства, а на входы регистров 19-22 подаются промежуточные результаты выполнения базовой операции. По положительному перепаду очередного тактового импульса на входы 24.25,27

и 28 устройства поступают новые значения исходных операндов базовой операции фиг.З, в регистры 19-22 заносятся промежуточные результаты базовой операции, а с выходов 34 и 35 устройства считываются результаты вычислений.

По приходу последующих тактовых импульсов описанные выше действия повторяются по аналогии вплоть до окончания выполнения первого этапа вычислений по алгоритму (1).

На последнем такте выполнения базовой операции фиг.З на входах регистров 19- 22 находятся промежуточные результаты выполнения данной базовой операции. С приходом очередного тактового импульса указанные промежуточные данные записываются в регистры 19-22, на выходы 34 и 35 устройства подаются мнимая и вещественная части выходного операнда базовой операции фиг.З, а на входы 24 и 25 поступают первый и второй операнды базовой операции фиг.4, на входы 26-29 устройства - соответственно первый коэффициент, третий и четвертый операнды, второй коэффициент базовой операции фиг.4.

Кроме того,на вход 32 устройства подается сигнал уровня 1, который поступает на управляющие входы коммутаторов 5 и 6, вход элемента НЕ 23, вход управления сум- матора-вычитателя 17 и вход триггера 10.

Это приводит к установлению коммутаторов 5 и 6 в режим передачи данных с входа на выход, сумматора-вычитателя 17 - в режим сложения операндов, а сумматора-вычитателя 18 - в режим вычитания.

В умножителях 1 и 2 осуществляется умножение второго и пятого операндов базовой операции фиг.4 на первый и второй коэффициенты соответственно. Результаты названных умножений с выходов умножителей 1 и 2 через входы коммутаторов 5 и 6 поступают на входы сумматора 11, вычита- теля 14 и сумматоров-вычитателей 17 и 18.

При этом на входы сумматора 11 и вы- читателя 14 поступает первый операнд базовой операции фиг.5 входа 24 устройства, а на входы сумматоров-вычитателей 17 и 18 приходит третий операнд базовой операции фиг.4 с входа 27 устройства, что позволяет на выходах сумматора 11 и вычитателя 14, а также сумматоров-вычитателей 17 и 18 получить промежуточные результаты выполнения базовой операции фиг.4.

В то же время на выходах 34 и 35 устройства формируются результаты выполнения базовой операции фиг.З.

Длительность рассматриваемого такта работы устройства отличается от длительности предыдущих тактов работы устройства на первом этапе алгоритма (1) и равна:

1и - ten + tyM + Тк,

где ten, tyM, Тк - время выполнения операции сложения, умножения и распространения сигнала через коммутатор.

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

происходит запись промежуточных результатов вычисления базовой операции фиг.4 в регистры 19-22, выдача результатов выполнения базовой операции фиг.З на выходы 34 и 35 устройства, подача на входы 24-29 устройства входных операндов (по аналогии с описанным выше), а на вход 30 устройства - третьего коэффициента базовой операции фиг.4. Кроме того, сигнал уровня 1 с входа 31 устройства записывается в триггер 10 и

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

операции фиг.4, что позволяет через время, равное на выходах сумматоров 12 и 13, а также на выходах вычитателей 16 и 15, получить результаты выполнения базовой операции фиг.4. При этом в умножителях 3

и 4 получаются результаты умножения третьего и четвертого промежуточных результатов базовой операции фиг.4 на третий коэффициент. Указанные результаты умножения через входы коммутаторов 8 и 9 поступают на входы сумматора 12, вычитателя 15 и сумматора 13, вычитателя 16 соответственно. На другие входы сумматора 12 и вычитателя 15 поступает промежуточный результат с выхода регистра 19, а на входы

сумматора 13 и вычитателя 16 подается промежуточный результат вычисления с выхода регистра 20 через вход коммутатора 7.

По приходу очередного тактового импульса на вход 31 устройства на входы 33-36

устройства поступают результаты выполнения базовой операции согласно фиг.4, в регистры 19-22 заносятся промежуточные результаты выполнения базовой операции фиг.4, а на входы 24-30 устройства поступают исходные операнды названной базовой операции.

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

выполнения базовой операции фиг.З.

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

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

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

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

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

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

режима устройства.

сэ сч| 2 о

-.-.- I. - . ь . - г

I |ь 14 (41 1 14 1 IX Ix if (4 .ЧьЧкЧ vw k,, t . i сэ сч| 2 о

-.-.- I. - . ь . - г

14 1 IX Ix if (4 t . i

Изобретение относится к вычислительной технике и предназначено для построения устройств обработки сигналов, работающих в реальном масштабе времени. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят умножители 1-4, коммутаторы 5-9, триггер 10, сумматоры 11,12,13, вычитатели 14,15,16, сумматоры-вычитатели 17,18, регистры 19-22 и элемент НЕ 23. 4 ил.

N

I

5 S3 1Q «

г г г

Re В

Фиг. 3

X

ImA