Устройство для выполнения быстрого преобразования вещественных последовательностей

 

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

СОЮЗ С08ЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)5 - G 06 F 15/332

ГОСУДАРСТБЕЧНЫИ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ь .г.

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4417234/24 (22) 26.04,88 (46) 23.04,91. Бюл. N . 15 (72) А.А.Мельник и M.Н.Яцимирский (53) 681.3 (088,8) (56) Авторское свидетельство СССР

N- 886005, кл. 6 06 F 15/332, 1979.

Авторское свидетельство СССР

N. 1343424, кл. G 06 E 15 /332, 1985. (54)УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ВЕЩЕСТВЕННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ (57) Изобретение относится к вычислительной технике и предназначено для построения сг1ециализированных вычислительных

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

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

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

Устройство для выполнения быстрого преобразования (Хартли) вещественных последовательностей (фиг.1) содержит вычисли„„Я „„1644157 А1 средств спектрального анализа сигналов.

Цель изобретения — повышение быстродейсгвия. Для этого в устройство введены вычислительные блоки первого, второго и третьего аида и преобразователь. Вычислительный блок первого вида содержит сумматор и вычитатель, вычислительный блок второго вида — два вычислительных блока первого вида. вычислительный блок третьего вида — вычислительные блоки первого вида и блоки поворота вектора, включающие в себя умножители, сумматор и вычитатель, Преобразователь содержит вычислительные блоки первого вида. 1з. и. ф-лы, 7 ил. тельные блоки 11,..., 1и/ г первого вида, вычислительные блоки 21,..., 2д/.4 второго вида, вычислительные блоки 31,...,3мд" третьего вида, где k =- 1,2,..., log 2 N-3 — номер (Tс ступени, Вычислительный блок nepeoro вида ф„ (фиг,2) содержит вычитатель 4 и сумматор 5.

Вычислительный блок второго вида (фиг.3) у содержит вычислительные блоки 61 и 62 Ilepвого вида. Вычислительный блок третьего виде(фиг еГсодержитвычислигельиыеблоки71, ь

72, 72 первого вида(к = 1,2,..., log z N-2) и, д, блоки 81, Sz,..., 82 -1 поворота вектора. Блок

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

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

1644157

Si - sin

2 где k — номер ступени, j — номар блока пово- 30 рота вектора, Операция умножения данных А и В нэ константы выполняется на умножителях 9 — 12, операция сложения на сумматоре

14, а операция вычитания на вычитателе 13.

Гэким образом, за один проход инфор- 3 мации через устройство над N входными данными выполняется N-точечное быстрое преобразование Хартли. При выполнении алгоритма БПФ результаты с выхода устройства 15 для выполнения алгоритма БПХ 40 поступают на преобразователь 16, в котором в блоках 171, 17 „.., 17M/2-1 производится вычисление четной и нечетной . составляющих БПХ. На первых (N Q-1)-х выходах преобразователя 16 получаются мни- 45 мые части БПФ вещественной последовательности в обратном порядке, начиная с (N/2-1)-го выхода. На выходах с

N/2-го по N-й преобразователь 16 получаются действительные части БПФ веществен- 50 ной последовательности в обратном порядке, начиная с N-ro выхода.

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

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

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

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

БПХ, Нэ вычислительных блоках 1 выполняется первый этап алгоритма БПХ. Каждый блок 1 выполняет операции

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

A=AС +BSi; В=ASi-ВС, где константы Sj u Cj соответственно равны

2 к(й/4 — ) }

25 повышения быстродействия, в него дополнительно введены М/2 вычислительных блоков первого вида, N/4 вычислительных блоков второго вида и N/4 вычислительных блоков третьего вида, где N - размерность преобразования, причем первый и второй входы N/2 вычислительных блоков первого вида являются входами устройства, первый и второй выходы (2 i 1)-ro вычислительного блока (i = 1,2„„, N.4) первого вида соединены соответственно с первым и вторым входами i-ro вычислительного блока первого вида, первый и второй выходы 2i-ro вычислительного блока первого вида соединены соответственно с третьим и четвертым . входами 1-го вычислительного блока второго вида, первый второй, третий и четвертый выходы (2S - 1)-го вычислительного блока второго вида (Я = 1,..., N/8) соединены соответственно с первым, вторым, третьим и четвертым входами S-го вычислительного блока третьего вида первой ступени, пятый, шестой, седьмой и восьмой входы которого соединены соответственно с первым, вторым, третьим и четвертым выходами 2S-ro вычислительного блока второго вида, g-й выход (2а-1)-ro вычислительного блока третьего вида k-й ступени (k = i,2,3..., logzN

-3, а = 1,2„... N/2 + вычислительного блока третьего вида (k + 1)-й ступени, (g +2 + -й вход которого соединен с g-м выходом 2а-го вычислительного блока третьего вида k-й ступени, причем вычислительный блок первого вида содержит сумматор и вычитатель, первые входы сумматора и вычитателя соединены с вторым входом вычислительного блока первого вида, вторые входы сумматора и вычитателя соединены с первым входом вычислительного блока nepaoro вида, выходы сумматора и вычитателя соединены соответственно с вторым и первым выходами вычислительного блока первого вида, вычислительный блок второго вида содержит два вычислительных блока первого вида, причем первый и второй входы первого вычислительного блока первого вида соединены соответственно с первым и третьим входами вычислительного блока второго вида, первый и второй входы второго вычислительного блока первого вида соединены соответственно с вторым и четвертым входами вычислительного блока второго вида, первый и второй выходы первого вычислительного блока первого вида соединены соответственно с первым и вторым выходами вычислительного блока второго вида, третий и четвертый выходы которого соединены соответственно с первым и вторым выходами второго вычислительного блока первого вида, вычислительный блок третье1644157 в o ° и/ го вида содержит 2 вычислительных блоков первого вида, где а- номер ступени, а = 1,2,..., log N -2, и дополнительно 2 блоков поворота вектора, причем первый вход j-го блока поворота вектора (j

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

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

+1

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

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

m-го блока поворота вектора, второй вход

m-го вычислительного блока первого вида соединен с (2 +1 + m)-м входом вычислительного блока третьего вида, первый вход (m + 2 )-го вычислительного блока первого вида соединен с вторым BxoAOM m ão блока поворота вектора, первый выход r-го вычислительного блока (г = 1,2,.„, 2 ) соединен

a+i с r-и выходом вычислительного блока третьего вида, второй выход г-го вычислительноа+ го блока первого вида соединен с (г+2а 1-м выходом вычислительного блока третьего вида, в блок поворота вектора введен четвертый умножитель и вычитатель, причем первый вход блока поворота вектора соедиНрН с входами fl0pt.or 0 и третьего умножителей, выход второго умножителя соединен с первь,м входом вычитателя, второй вход блока поворота вектора соединен с входами второго и четвертого умножителей, выходы которых соединены с вторыми входами соответственно вычитателя и сумматора,выход вычитателя соединеH с первым выходом блока поворота вектсрэ, второй выход которого соединен с выходом сумматора, выходы вычислительного блока третьего вида (loggN -3)-й ступени являются группой выходов устройства.

2. Устройство по п.1, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, в него дополнительно в еден преобразователь, содержа ций М/2-1 вычислительных блоков первого вида, причем t-й выход вычислительного блока третьего вида (log г N-3)-й ступени (t = 1,2,..., Nj соединен с т-м входом преобразователя, N/2-й и N-й входы которого являются соответственно N/2-м и N-м его выходами, f-й и (N — f)-й входы преобразователя (f =- 1,2,..., N/2 -1) являются соответственно первым и вторым входами f-го вычислительного блока первого вида, первый и второй выходы которого являются соответственно (N

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

1б44157 иг5

NIZ i

Ф/2 1

Редактор Е,Папп

Заказ 1242 Тираж 414 Подписное

ЙНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35. Раушская наб., 4/5

Производственно-издательский комбинат "Патент". r. Ужгород, ул,Гагарина, 101

Ф!2 7

Ф/2

4 !2-1

У/211

1/2 !

Составитель ЮЛанцов

Техред М.Моргентал Корректор М,Самборская