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

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

Известно устройство быстрого действительного преобразования Хартли-Фурье, содержащее блок синхронизации, два счетчика адреса, блок постоянной памяти, четыре регистра/два умножителя, сумматор- вычитатель, блок постоянной памяти и три коммутатора. В данном устройстве базовая операция алгоритма быстрого преобразования Хартли (БПХ) по основанию два выполняется за три такта. Недостаток известного устройства - низкое быстродействие.

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

Устройство реализует алгоритм БПФ по основанию два с прореживанием по частоте. Для выполнения N-точечного БПФ необходимо выполнить N/2log2N итераций. Недостаток известного устройства - низкое быстродействие.

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

ел

с

ч ю

СП

Јь

NJ СО

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

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

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

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

Устройство содержит информационные входы 1-8, управляющий вход 9, входы 10-13 задания фазовых множителей, блоки 14-19 сложения-вычитания, коммутатор 20, умножители 21,22 комплексных чисел, информационные выходы 23-30.

Входы устройства 1, 3, 5, 7 соединены с первыми входами соответственно блоков 14, 15, 16, 17 сложения-вычитания, а входы 2, 4, 6, 8 - с вторыми входами соответственно блоков 14, 15, 16, 17, первые выходы которых соединены с выходами 23, 24, 25, 26 устройства соответственно, вторые выходы блоков 14, 15 сложения-вычитания соединены соответственно с первым и вторым входами блока 18, вторые выходы блоков 17, 16 соединены соответственно с .первым и .вторым входами блока 19, первый выход которого соединен с вторым входом умножителя 22, первый вход которого соединен с выходом коммутатора 20, входы которого

соединены с вторыми выходами.блоков 18, 19, а второй его выход соединен с вторым входом умножителя 21, первый вход которого соединен с первым выходом блока 18, первые и вторые выходы умножителей 21, 22 соединены соответственно с выходами 27,28, 29,30 устройства, входы 10,11,12, 13 которого соединены соответственно с третьими и четвертыми входами умнржите- лей 21, 22, управляющий вход коммутатора 20 соединен с входом 9 устройства.

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

а1 а + е; b1 b + f; d1 d + h; с1 с + g;

n (a - e) + (b - f); qi (a - e) - (b - f);

гз (d - h) - (c - g); qs (d - h) + (c - g);

. + CYqij-YKjJSN f1 nSNK-(Yqi + Yr3)CNK;

g1 (Yr3 + Yqi)CN3Rr+ q3SN3K; h1

(Yr3 + Yqi)SN-q3CN3 , где a, b, c, d, e, f, g, h - входы устройства;

a , b , с , d , e , f, g , h - выходы устрой- ства;.

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

Здесь Смг cos(2 тгг/N), SNT sin(2 лг/N),

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

По информационным входам 1-8 в устройство поступают входные числа. По входам 10-13 поступают фазовые множители. На блоках 14-19 сложения-вычитания, каж- дый из которых содержит сумматор и вычи- татель, выполняются операции сложения и вычитания в соответствии с выражением:

40

l + m; т

т,

il

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

Коммутатор 20 пропускает поступающие на его входы данные прямо или накрест в зависимости от значения сигнала Y на 5 входе 9 устройства. Если Y 0, то данные идут прямо, если Y 1 - накрест.

На умножителях 21,22 комплексных чисел выполняются операции умножения поступающих из блоков 18, 19 и коммутатора 0 20 чисел на фазовые множители в соответствии с выражениями:

I1 1См + т5мк: I ICw3K + тЗызк:

т1 15мк - тСм ; т ISN3K - тСмЗК где I. rri - входы умножителей; 5 | т - выходы умножителей;

Смг, Змг - фазовые множители, поступающие по входам 10-13.

Первое выражение реализуется на умножителе 21, второе - на умножителе 22.

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

Базовая операция на графе обозначена прямоугольником, внутри которого первая цифра указывает значение управляющего сигнала Y, вторая и третья в порядке сверху вниз определяют значения параметров К и N, используемых для ввода фазовых множителей Сг/, SNK, Сцзк. SN .

Для К 1,N/8-1 эти множители принимают значения CNK cos(2 лК/N), SNK sin(2jr K/N), СыЗК С05(2я ЗК/N). 5кж sl n(2 л:ЗК/N), а для К 0 при N 8 (третья цифра равна размерности преобразования N)OHH соответственно равны; 0, 1, - 2/2 и v2/2. На последнем этапе преобразования на некоторые входы подаются нули (обозначены 0), а некоторые выходы не используются. На этом этапе с помощью базовой

10

15

20

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

Быстродействие предложенного арифметического устройства для выполнения БПХФ определяется как сумма времени выполнения одного, умножения комплексных чисел и двух сложений, что только на одну операцию сложения больше, чем в устройстве-прототипе, что несущественно. В таблице приведено количество базовых операций при выполнении N - точечного (N 2m, n 5,12) алгоритма БПХ на предложенном устройстве и устройстве-прототипе, а также выигрыш по быстродействию. При выполнении алгоритма БПФ выигрыш по быстродействию аналогичен.

Изобретение относится к вычислительной технике и может быть использовано в аппаратуре спектрального анализа и синтеза сигналов. Цель изо.бретения - повышение быстродействия. Устройство содержит блоки сложения-вычитания, коммутатор и умножители комплексных чисел. 1 табл., 2 ил.

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

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

i 2

ft

3 4

tf

Й

Ј б

Л

S

/

tf .14

.25 .26

J7 .IB

го

-22

TZ9 JO

J

TT

fO // fl tf

Фиг f