Устройство для выполнения быстрого преобразования вещественных последовательностей Советский патент 1991 года по МПК G06F15/332 

СЛ

С

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

Изог оетение относится к области вы- числител чой техники и предназначено для построения специализированных вычислительных ( редств спектрального анализа сигналов.

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

На фиг.1 представлена схема устройства для выполнения быстрого преобразования (Хартли) вещественных последовательностей; на фиг.2 - схема вычислительного блока первого вида; на фиг.С - схема вычислительного блока второго вида; на фиг.4 - схема вычислительного блока третьего вида; на фиг.5 - схема блока поворота вектора; на фиг.6 - схема устройства для выполнения быстрого преобразования (Фурье) вещественных последовательностей; на фиг.7 - схема преобразователя,

Устройство для выполнения быстрого преобразования (Хартли) вещественных последовательностей (фиг. 1) содержит вычислительные блоки 1i,..., IN/ 2 первого вида, вычислительные блоки 2i2м/ А второго вида, вычислительные блоки 3iЗм/2

третьего вида, где k 1,2log 2 N-3 - номер

ступени.

Вычислительный блок первого вида (фиг,2) содержит вычитатель 4 и сумматор 5. Вычислительный блок второго вида (фиг.З) содержит вычислительные блоки 6i и 62 первого вида. Вычислительный блок третьего вида (фиг.4)содержит вычисли, ельные блоки 7i,

72, 72 первого вида (k 1,2log 2 N-2 ) и

блоки 8i, 8282 k повороте вектора. Блок

6 поворота вектора (фиг.5) содержит умножители 9-12, вычитатель 13 и сумматор 14.

Устройство при выполнении быстрого преобразования Фурье (БПФ) содержит устройство 15 для выполнения быстрого преобразователя Хартли (БПХ), представленное на фиг.1, и преобразователь 16. Преобразователь 16содержит вычислительные блоки 17i,

172 17N/2-1.

О

4

сл

4

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

На входы устройства в двоично инверсном порядке одновременно поступают N чи- сеп, подлежащих обработке. Устройство 15 аппаратно реализует граф-схему алгоритма БПХ. На вычислительных блоках 1 выполняется первый этап алгоритма БПХ. Каждый блок 1 выполняет операции А А + В; В А-В,

где А и В - входные данные. Сложение выполняется на сумматоре 5, а вычитание на вычитателе 4. В блоках 2 выполняется второй этап алгоритма БПХ. Каждый блок 2 выполняет операции, аналогичные операциям блока 1. Каждый блок 3, в котором выполняется k-й этап алгоритма Хартли, состоит из блоков 7 первого вида и блоков 8 поворота вектора. В блоках 7 выполняются операции, аналогичные операциям, выполняемыми блоками 1. Блоки 8j поворота вектора выполняют операции

А - A Cj + В Sj: В A S - В Q. где константы Sj и Cj соответственно равны

S| sinMi zU; Sl slnMfiW

где k - номер ступени, j - номар блока поворота вектора, Операция умножения данных А и В на константы выполняется на умножителях 9 -12, операция сложения на сумматоре 14, а операция вычитания на вычитателе 13. Таким образом, за один проход информации через устройство над N входными данными выполняется N-точечное быстрое преобразование Хартли. При выполнении алгоритма БПФ результаты с в ыхода устройства 15 для выполнения алгоритма БПХ поступают на преобразователь 16, в котором в блоках 17i, 17217м/2-1 производится вычисление четной и нечетной . составляющих БПХ. На первых (N/2-i)-x выходах преобразователя 16 получаются мнимые части БПФ вещественной последовательности в обратном порядке, начиная с (М/2-1)-го выхода. На выходах с N/2-гопоМ-й преобразователь 16 получаются действительные части БПФ вещественной последовательности в обратном порядке, начиная с N-ro выхода. Формула изобретения 1. Устройство для выполнения быстрого преобразования вещественных последовательностей, содержащее блок поворота вектора, содержащий три умножителя и сумматор, причем выход первого умножителя соединен с первым входом сумматора, отличающееся тем, что, с целью

повышения быстродействия, в него дополнительно введены N/2 вычислительных блоков первого вида, N/4 вычислительных блоков второго вида и N/4 вычислительных

блоков третьего вида, где N - размерность преобразования, причем первый и второй входы N/2 вычислительных блоков первого вида являются входами устройства, первый и второй выходы (2 i -1)-ro вычислительного

0 блока (I 1,2,..., N.4) первого вида соединены соответственно с первым и вторым входами 1-го вычислительного блока первого вида, первый и второй выходы 21-го вычислительного блока первого вида соединены

5 соответственно с третьим и четвертым входами 1-го вычислительно. блока второго вида, первый второй, третий и четвертый выходы (2S - 1)-го вычислительного блока второго вида (S 1N/8) соединены соот0 ветственно с первым, вторым, третьим и четвертым входами S-ro вычислительного блока третьего вида первой ступени, пятый, шестой, седьмой и восьмой входы которого соединены соответственно с первым, вто5 рым, третьим и четвертым выходами 2S-ro вычислительного блока второго вида, д-й выход (2а-1)-го вычислительного блока третьего вида k-й ступени (k 1,2,3..., Iog2N -3, а 1,2N/2k+2 вычислительного блока

0 третьего вида (k + 1)-й ступени, (д +2 вход которого соединен с g-м выходом 2а-го вычислительного блока третьего вида k-й ступени, причем вычислительный блок первого вида содержит сумматор и вычитатель,

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

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

5 причем первый и второй входы первого вычислительного блока первого вида соединены соответственно с первым и третьим входами вычислительного блока второго вида, первый и второй входы второго вычисли0 тельного блока первого вида соединены соответственно с вторым и четвертым входами вычислительного блока второго вида, первый и второй выходы первого вычислительного блока первого вида соединены со5 ответственно с первым и вторым выходами вычислительного блока второго вида, третий и четвертый выходы которого соединены соответственно с первым и вторым выходами второго вычислительного блока первого вида, вычислительный блок третье

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

а 1,2log N -2, и дополнительно 2 2

блоков поворота вектора, причем первый вход j-ro блока поворота вектора (j 1,2,...,2 )соединен с j-м входом вычислительного блока третьего вида,второй вход 1-го блока поворота вектора соединен с (2-j)-M входом вычислительного блока третьего вида, первый вход 2 -го блока первого вида соединен с 2 и -м входом вычислительного блока третьего вида, 3 2 а-Л вход которого соединен с вторым входом 2 а -го вычислительного блока первого вида, первый вход 2 вычислительного блока первого вида, .соединен с 2а +1-м входом вычислительного блока третьего вида, 2 а+2-й вход которого соединен с вторым входом 2 а +1-го вычислительного блока первого вида, первый вход т-го вычислительного блока первого вида (т

1,22 ) соединен с первым выходом

т-ro блока поворота вектора, второй вход m-ro вычислительного блока первого вида соединен с (2 а +1 + т)-м входом вычисли- тельного блока третьего вида, первый вход (т + 2 )-го вычислительного блока первого вида соединен с вторым входом m-ro блока поворота вектора, первый выход r-го вычислительного блока (г 1,22 а+1) соединен

с r-м выходом вычислительного блока третьего вида, второй выход r-го вычислительного блока первого вида соединен с (r+2a + /выходом вычислительного блока третьего

Че w ЧТУ у

IliiIlliiiiliiil

#

j, 4, Ф Ф 4 4 IT 4 jr j, X1X J/ -1Ф - 4 4/

шшшшшотшш

0

5

5

0

0

вида, в блок поворота вектора введен четвертый умножитель и вычитатепь, причем первый вход блока поворота вектора соединен с входами первого и третьего умножителей, выход второго умножителя соединен с первым входом вычитателя, второй вход блока поворота вектора соединен с входами второго и четвертого умножителей, выходы которых соединены с вторыми входами соответственно вычитателя и сумматора,выход вычитателя соединен с первым выходом блока поворота вектора, второй выход которого соединен с выходом сумматора, выходы вычислительного блока третьего вида (logjjN -3)-й ступени являются группой выходов устройства.

соединен с t-м входом преобразователя, N/2-й и N-й входы которого являются соответственно N/2-м и N-м его выходами, f-й и

(N - т)-й входы преобразователя (f 1,2

N/2 -1) являются соответственно первым и вторым входами f-ro вычислительного блока первого вида, первый и второй выходы которого являются соответственно (N - f)-M и ( N/2 - т)-м выходами преобразователя, выходы преобразователя являются дополнительной группой выходов устройства.

V V jf W JLSL.

П-2

Фиг.1

rЮ

ч- т to

v

i

i

«VI

i.

Фиг. 7