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

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

Определение

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

${\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,}$

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

${\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.}$

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

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

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

${\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.}$

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

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

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

${\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).}$

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