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

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

Определение

Последовательность $N$ действительных чисел $h_{0}$, $h_{1}$, … , $h_{N-1}$ преобразуется в последовательность $N$ действительных чисел $H_{0}$, $H_{1}$, … , $H_{N-1}$ с помощью дискретного преобразования Хартли по формуле:

$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,$

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

$h_{n}=\sum \limits _{k=0}^{N-1}H_{k}\operatorname {cas} \left({\dfrac {2\pi }{N}}nk\right),\ n=0,\ldots ,N-1.$

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

Имеют место следующие формулы перехода от ДПФ (последовательность $F_{0}$, $F_{1}$, … , $F_{N-1}$) к ДПХ и наоборот:

$H_{k}=\operatorname {Re} F_{k}-\operatorname {Im} F_{k},$

$F_{k}={\dfrac {1}{2}}(H_{k}+H_{N-k})-i{\dfrac {1}{2}}(H_{k}-H_{N-k}),\ k=0,\ldots ,N-1.$

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

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

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

$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).$

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

Литература

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

См. также

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