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

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

Определение

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

$H_k=\frac{1}{N}\sum _{n=0}^{N-1}{h}_n\mathrm{cas}\left(\frac{2\pi }{N}nk\right),k=0,\dots ,N-1,$

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

$h_n=\sum _{k=0}^{N-1}{H}_k\mathrm{cas}\left(\frac{2\pi }{N}nk\right),n=0,\dots ,N-1.$

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

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

$H_k=\mathrm{Re}{F}_k-\mathrm{Im}{F}_k,$

$F_k=\frac{1}{2}(H_k+H_{N-k})-i\frac{1}{2}(H_k-H_{N-k}),k=0,\dots ,N-1.$

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

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

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

$H_k=H_{1,k}+H_{2,k}\cos \left(\frac{2\pi }{N}k\right)+H_{2,N-k}\sin \left(\frac{2\pi }{N}k\right).$

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

Литература

• Шаблон:Книга

См. также

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