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

Ё

Изобретение относится к вычислительной технике и может быть использовано о аппаратуре спектрал ьнйгр анализа и синтеза сигналов. Цель изобретения - ловыше- ййе быстродействия, Для этого устройство содержит умножители 14, 15 комплексных чисел, коммутатор 16, сумматоры-вычита- тели 17-22. Сущность изобретения заключается в осуществлений базовой операции алгоритмов быстрого преобразования Хартли (БПХ) и быстрого преобразования Фурье (Б ПФ) по расщеплённому основанию, которые являются более эффективными, чем другие алгоритмы БПХ и БПФ. 2 ил.

9-Ю 1112 /J

Ч СЛ

о ю о

ю

Фиг.

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

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

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

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

Устройство содержит входы 1-8 one- рандов, входы 9-12 задания фазовых множителей, вход 13 задания тйпа о перации, умножители 14 и 15 комплексных чисел, коммутатор 16, сумматоры-вычитатели 17- 22, выходы 23-30 результата.

Базовая операция алгоритмов БПХ и БПФ по расщепленному основанию два - четыре описывается следующей системой уравнений:

qi eCNk + f SNk; РЗ g CN3k + h SN3k;

n eSNk - f Cwk: гз g SN3k - h CN3k;

a1 a + (qi - Yqs + Yn); e1

a-(qi-Yq3 + Yn);

b1 b + (qi-Yq3-Yri);f1

b-(qi-Yq3-Yn);

+ (r3-Yn-Yq3);

g1 с - (гз - Yn - Yq3);

+ fa + Yri-f Yq3);

h1 d - (r3 + Yn + Yq3),

50

устройства, выходы устройстгде a. b, с, d, e, f, g, h - входы a , b , c , d1 e1, f, g1, h1 - вы ва;

Y - значение сигнала на управляющем входе коммутатора 16 (Y ОЛ). 55

Cwr cos 2лг N I; Si/ sinl 2л: г IN I.

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

По входам 1-8 в устройство поступают входные числа. По входам 9-12 поступают фазовые множители. На множителях 14 и 15 комплексных чисел выполняются операции умножения входных чисел на фазовые множители в соответствии с выражениями:

,3k

feCNk + f Swk; fgCN3k + h SN:

|eSNk-fCNk; |gSN3k-hSN3k

На сумматорах-вычитателях 17-22 выполняются операции сложения и вычитания в соответствии с выражением:

I1 I + т;

т

1 - т,

0 5

0

5

5

0

0

5

где I, т - входы блока;

I, т1 - выходы блока.

Коммутатор 16 пропускает поступающие на его входы данные прямо или накрест в зависимости от значения сигнала Y на входе 13 устройства: если Y 1, то данные идут накрест; если Y 0 - прямо.

Порядок выполнения алгоритмов БПХ и БПФ на основе предлагаемой базовой операции определяется графом алгоритма (на фиг.2 показан граф алгоритма БПХ для N 32).

Базовая операция на графе изображена прямоугольником, внутри которого первая цифра указывает значение управляющего сигнала Y, вторая и третья в порядке сверху вниз определяют значения параметров k и N, используемых для ввода фазовых мнржи- телей CNk. SNk CN и SN . Для k 1.N/8-1 эти множители принимают значения CNk cosl27rk| N I; SNk sin 12 nk IN I; CN3k cos |6 k| N ;SN3k s n| N|, а для k 0 при N 8 (третья цифра равна размерности преобразования) они соответственно равны: 0.1 - /2/2 и(2/2.

Как видно из фиг.2, на первых двух этапах преобразования на некоторые входы подаются нули (обозначены О), а некоторые выходы не используются. На этих этапах с помощью базовой операции реализуются четырехточечные и пары двухточечных преобразований. Первые из них обозначены тройкой параметров 1, 0, 4, а вторые О, О, 2, которые реализуются с фазовыми множителями, равными Г для четырехточечного преобразования и 1/2 для двух двухточечных.

Порядок связей между входами и выходами базовых операций показан на фиг.2.

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

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

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

0

5 0 5 0 5

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

%