Дискретное преобразование Хартли

Дискретное преобразование Хартли (сокращённо ДПХ) — разновидность дискретного ортогонального тригонометрического преобразования. Во многих случаях может служить заменой дискретного преобразования Фурье.

Определение

Последовательность [math]\displaystyle{ N }[/math] действительных чисел [math]\displaystyle{ h_0 }[/math], [math]\displaystyle{ h_1 }[/math], … , [math]\displaystyle{ h_{N-1} }[/math] преобразуется в последовательность [math]\displaystyle{ N }[/math] действительных чисел [math]\displaystyle{ H_0 }[/math], [math]\displaystyle{ H_1 }[/math], … , [math]\displaystyle{ H_{N-1} }[/math] с помощью дискретного преобразования Хартли по формуле:

[math]\displaystyle{ H_k = \dfrac{1}{N} \sum\limits_{n=0}^{N-1} h_n \operatorname{cas} \left( \dfrac{2 \pi}{N} nk \right), \ k = 0, \ldots, N-1, }[/math]

где [math]\displaystyle{ \operatorname{cas} x = \cos x + \sin x }[/math]. Обратное дискретное преобразование Хартли задаётся формулой:

[math]\displaystyle{ h_n = \sum\limits_{k=0}^{N-1} H_k \operatorname{cas} \left( \dfrac{2 \pi}{N} nk \right), \ n = 0, \ldots, N-1. }[/math]

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

Имеют место следующие формулы перехода от ДПФ (последовательность [math]\displaystyle{ F_0 }[/math], [math]\displaystyle{ F_1 }[/math], … , [math]\displaystyle{ F_{N-1} }[/math]) к ДПХ и наоборот:

[math]\displaystyle{ H_k = \operatorname{Re} F_k - \operatorname{Im} F_k, }[/math]

[math]\displaystyle{ F_k = \dfrac{1}{2} (H_k + H_{N-k}) - i \dfrac{1}{2} (H_k - H_{N-k}), \ k = 0, \ldots, N-1. }[/math]

Быстрое преобразование Хартли

Идея быстрого преобразования Хартли (сокращённо БПХ) такая же, как и у быстрого преобразования Фурье (сокращённо БПФ): за счет симметрии можно сократить количество вычислений.

Пусть из исходной последовательности [math]\displaystyle{ h_0 }[/math], [math]\displaystyle{ h_1 }[/math], … , [math]\displaystyle{ h_{N-1} }[/math] получены две новые последовательности длины [math]\displaystyle{ N }[/math], равные [math]\displaystyle{ \left( h_0, 0, h_2, 0, \ldots \right) }[/math] и [math]\displaystyle{ \left( 0, h_1, 0, h_3, \ldots \right) }[/math] и пусть их ДПХ равны соответственно [math]\displaystyle{ H_{1,k} }[/math] и [math]\displaystyle{ H_{2,k} }[/math], где [math]\displaystyle{ k = 0, \ldots, N-1 }[/math]. В этих обозначениях общая формула БПХ имеет следующий вид:

[math]\displaystyle{ H_k = H_{1,k} + H_{2,k} \cos \left( \dfrac{2\pi}{N} k \right) + H_{2,N-k} \sin \left( \dfrac{2\pi}{N} k \right). }[/math]

С помощью указанных выше формул перехода от ДПХ к ДПФ можно использовать БПХ для вычисления БПФ, что упрощает вычисления ввиду отсутствия комплексных умножений.

Литература

• Брейсуэлл, Р. Преобразование Хартли (рус.). — М.: Мир, 1990. — 175 с. — ISBN 5-03-001632-5.

См. также

• Дискретное комплексное преобразование