Новый алгоритм быстрого преобразования Хартли

Удобным аппаратом цифровой обработки сигналов является дискретное преобразование Фурье (ДПФ). Широкое применение ДПФ объясняется наличием эффективных алгоритмов его вычисления.

Одним из наиболее быстрых алгоритмов вычисления ДПФ длиной 2(I > 2 - целое) был предложен И.Е. Капориным [)]. Этот алгоритм основывается на сведении преобразования Фурье L-точечной комплексной последовательности к вычислению четырех вещественных преобразований (двух косинусных и двух синусных) длиной порядка L/2. В обозначениях принятых в [1] преобразование по косинусам последо вательности

[aj) j_q имеет

вид:

5N> [а] = 2 a. cos г о < k < N, к           j=0 3 N а преобразование по синусам последовательности зом :

(aj}

N-1 j=1

(1 )

выглядит следующим обра-

В (1) показано, что преобразование по косинусам можно вычислить с помощью nN/2 - N + 1 умножений и 3nN/2 - 2N + п + 4 сложений, а преобразование по синусам - с помощью такого же числа умножений и 3nN/2 - 2N - п + 2 сложений, где n = log2 N.

Предложенный в [)] алгоритм вычисления ДПФ требует наименьшего количества вещественных операций сложения и умножения по сравнению с известными алгорит мами.

Указанный подход можно применить к вычислению дискретного преобразования Хартли, к которому в последнее время вновь появился интерес [2]. Использование этого преобразования вместо ДПФ в задачах обработки вещественных сигналов поз воляет ограничиться только вещественной арифметикой и примерно вдвое сократить объем вычислений.

Преобразование Хартли вещественной последовательности соотношением

(а?

L-1

)=0

определяется

• [a] = E a [cos ♦ sin ^k], 0 < к < L - 1.

  
  

к            j-Q J          L               L J

Покажем, как можно свести вычисления по формуле (3) к вычислению по формулам (1 ) и ( 2 ) .

Пусть N > 2 - целое, ьо = а0;

• ^bj = ^aj ^{+ a}2N-j' ^Cj = ^aj - ^a2N-j' 1 5 j 2 N - 1;                            (4)

bN ~ aN"

Разложив правую часть выражения (3) на две суммы по косинусам и синусам и учитывая, что

2п(М~j)k         2п j к cos ——jcos —;

sin 2п£рП = _s1n 2д£к , получим следующие соотношения:

H<2N)[a] - ФСЮ[Ь]; о u J о J

<2Ю[а] = «^’[Ь] * Ф^Ф 1 < к < N - 1;

«ZN-k^J = ФкЮ М' ^’[Ф 1 S к S N - 1;

у (2N ) г 1     ▲ (N ) г, i

*N [а] = Ф„ [Ь].

Согласно формулам (4) и (5) преобразование Хартли длиной L (L - четно) сводится к преобразованию по косинусам длиной L/2 + 1 и преобразованию по синусам длиной L/2 - 1 и дополнительно 4(1/2 - 1) вещественным сложениям. Учитывая приведенные выше вычислительные затраты на преобразования по косинусам и синусам, можно получить, что для реализации преобразования Хартли длиной L, равной целой степени двойки, требуется IL/2 - 3L/2 + 2 вещественных умножений и 31 L/2 - 3L/2 + 2 сложений, где I = log2 L.

• 8 [3] описан, по-видимому, наиболее быстрый из известных алгоритмов преобразования Хартли и даны оценки его вычислительной сложности для различных длин преобразуемых последовательностей. Сравнение предлагаемого в данной работе алгоритма с алгоритмом Прадо показывает, что для реализации первого требуется ровно столько вещественных сложений, сколько для второго, а умножений - в два раза меньше.

Представленный алгоритм (с использованием подхода, применяемого Капориным для вычисления ДПФ) является наилучшим с точки зрения вычислительных затрат, хорошо структуризуется и может быть рекомендован для практического использования .