离散哈特利转换

在正式定义上，离散哈特利转换是一种线性可逆函数 H; Rⁿ -> Rⁿ (R表示实数的集合)。根据下列公式，N个实数输入 x₀,x₁,...,x_N-1经由转换产生N个实数输出

${\displaystyle H_{k}=\sum _{n=0}^{N-1}x_{n}\left[\cos \left({\frac {2\pi }{N}}nk\right)+\sin \left({\frac {2\pi }{N}}nk\right)\right]\quad \quad k=0,\dots ,N-1}$ 

其中${\displaystyle \cos(z)+\sin(z)\!}$  ${\displaystyle ={\sqrt {2}}\cos(z-{\frac {\pi }{4}})}$ 之组合有时候我们会以${\displaystyle \mathrm {cas} (z)\!}$ 表示，与在离散傅里叶变换之定义式中出现的${\displaystyle e^{-iz}=\cos(z)-i\sin(z)\!}$ 需有所区分(其中i为虚数单位)。

就像离散傅里叶变换一样，在一般的习惯或不同的应用上，离散哈特利转换定义式前之比例因子或正弦函数之正负号或有些许的差异，但并不会对离散哈特利转换的性质产生影响。

此转换可被诠释为N维之向量(x₀, ...., x_N-1) 乘上一个N-x-N 之矩阵的矩阵运算，于是离散哈特利转换为一种线性运算子。该矩阵是可逆矩阵，如欲由H_k 重建回x_n，此反转换只需对将H_k视为输入，进行离散哈特利转换，输出再乘上1/N即得。也就是说，离散哈特利反转换除了一个比例因子之外，与离散哈特利转换完全相同，此一特性尤其在哈特利转换之硬件架构设计有其优势。

离散哈特利转换可用于计算离散傅里叶变换，反之亦然，其关系如下。 对于实数输入x_n，经由离散傅里叶变换之输出X_k之实部为(H_k + H_N-k)/2，虚部为(H_N-k - H_k)/2。而离散哈特利转换的输出则等价于计算出x_n的离散傅里叶变换后乘上(1+i)，再取其实部。

如同离散傅里叶变换一样，当我们考虑使用离散哈特利转换计算两个向量x与y( x = (x_n)，y = (y_n) )之环形折积 z = x*y ( z = (z_n) )也变得简单许多。我们令向量X, Y与Z分别表示x,y与z之离散哈特利转换结果，于是Z可以由下式求得：

${\displaystyle {\begin{matrix}Z_{k}&=&\left[X_{k}\left(Y_{k}+Y_{N-k}\right)+X_{N-k}\left(Y_{k}-Y_{N-k}\right)\right]/2\\Z_{N-k}&=&\left[X_{N-k}\left(Y_{k}+Y_{N-k}\right)-X_{k}\left(Y_{k}-Y_{N-k}\right)\right]/2\end{matrix}}}$ 

我们可发现，类似离散傅里叶变换将折积运算转化为点对点复数乘法运算。离散哈特利转换将折积运算转化成简单的频率成分组成，其中的运算皆只包含实数运算。再经由离散哈特利反转换即得欲求之向量z。于是当我们需要计算折积时，除了利用离散傅里叶变换之外，亦可利用离散哈特利转换代为完成。而基于上述关系，一个针对使用离散哈特利转换进行折积运算之快速算法便可产生。

如同离散傅里叶变换的情况，如果我们直接依照定义计算离散哈特利转换，则需要${\displaystyle O(N^{2})}$ 的计算法杂度。但我们有类似于快速傅里叶变换之快速算法仅需${\displaystyle O(N\log N)}$ 的计算复杂度。几乎每种快速傅里叶变换算法，如Cooley-Tukey、质因数分解、Winograd等，皆有直接类比的快速离散哈特利转换算法。(然而，一些较为复杂之FFT算法如QFT则目前未有对应版本)。

特别地，由Cooley-Tukey算法所类比之离散哈特利转换算法一般被称为快速哈特利转换(FHT)算法，在1984年由 Bracewell 提出，此FHT快速算法对于2的幂次方点数之版本，由史丹佛大学于1987年提出为美国专利编号第4,646,256号，并于1995年公开专利权。

如同前文所述，离散哈特利算法之效率(基于浮点数的计算次数)可能较对应之特别针对实数输出之快速傅里叶变换算法差，此论点第一次是由Sorensen等人与Duhamel及Vetterli在1987年提出。现今电脑效能主要决定于快取与处理器管线化的考量，而非严格的运算数量所决定，所以在计算量上些微的差异已不如此显著。而在实务上，针对实数输入的高度最佳化快速傅里叶变换程式集已相当容易取得(由处理器厂商如英特尔)。然而，高度最佳化之离散哈特利转换程式集则并非如此普遍。

在离散傅里叶变换中，借由将相位${\displaystyle e^{-i{\frac {2\pi nk}{N}}}\!}$ 一般化，得到了所谓的一般化离散傅里叶变换，而离散哈特利转换也有类比的一般化离散哈特利转换，共有四种型态

型态一

${\displaystyle H_{k}=\sum _{n=0}^{N-1}x_{n}\left[\cos \left({\frac {2\pi }{N}}nk\right)+\sin \left({\frac {2\pi }{N}}nk\right)\right]\quad \quad k=0,\dots ,N-1}$ 

型态二

${\displaystyle H_{k}=\sum _{n=0}^{N-1}x_{n}\left[\cos \left({\frac {2\pi }{N}}(n+{\frac {1}{2}})k\right)+\sin \left({\frac {2\pi }{N}}(n+{\frac {1}{2}})k\right)\right]\quad \quad k=0,\dots ,N-1}$ 

型态三

${\displaystyle H_{k}=\sum _{n=0}^{N-1}x_{n}\left[\cos \left({\frac {2\pi }{N}}n(k+{\frac {1}{2}})\right)+\sin \left({\frac {2\pi }{N}}n(k+{\frac {1}{2}})\right)\right]\quad \quad k=0,\dots ,N-1}$ 

型态四

${\displaystyle H_{k}=\sum _{n=0}^{N-1}x_{n}\left[\cos \left({\frac {2\pi }{N}}(n+{\frac {1}{2}})(k+{\frac {1}{2}})\right)+\sin \left({\frac {2\pi }{N}}(n+{\frac {1}{2}})(k+{\frac {1}{2}})\right)\right]\quad \quad k=0,\dots ,N-1}$ 

一般化离散哈特利转换适用于很多应用，如滤波器设计、折积计算、信号表示法、任意点数组合之离散哈特利转换与快速算法。 对于一般化离散哈特利转换，亦有快速算法的设计(Guoan Bi et al. 2000)。

虽然离散哈特利转换相较于离散傅里叶变换有一个主要的优点，当实数输入时可以得到实数的输出，且计算过程中完全避免了复数的运算，降低了计算复杂度且可达到类似离散傅里叶变换的效果，于是在许多应用上为傅里叶变换之替代方案之一。然而，如同前文所述，在特别针对实数输入而设计之离散傅里叶变换算法往往可以得到较低的计算复杂度，于是如欲使离散哈特利转换之应用层面更广，进一步的分析与简化是必要的。

有相关文献(Soo-Chang Pei and Jian-Jiun Ding, 2000)探讨对于傅里叶变换相关之转换族，包括离散余弦转换、离散正弦转换、离散哈特利转换等之整数版本近似转换，其转换核系数并不牵涉到浮点数。整数转换主要有几个优点，首先对于一个运算的计算复杂度与需要的内存可以再加以缩减，尤其当输入亦为整数时特别显著，另一方面，由于不同的平台对于浮点数的精准度不一定相同，在跨平台的应用上，如果牵涉到浮点数的运算，则会有潜在错误的可能性。

在此提供八点离散哈特利转换之整数近似转换核如下:

${\displaystyle HI_{P}={\begin{bmatrix}1&1&1&1&1&1&1&1\\8&10&8&0&-8&-10&-8&0\\1&1&-1&-1&1&1&-1&-1\\5&0&-5&8&-5&0&5&-8\\1&-1&1&-1&1&-1&1&-1\\5&-8&5&0&-5&8&-5&0\\1&-1&-1&1&1&-1&-1&1\\8&0&-8&-10&-8&0&8&10\\\end{bmatrix}}}$ 

离散哈特利转换为离散傅里叶变换之替代方案之一（其他包括离散余弦转换，离散正弦转换，瓦西转换，哈尔转换等），可视为离散傅里叶变换之简化版本，对于实数输入可以产生实数的输出，去除离散傅里叶变换需要复数计算之缺点，而且如此一来，因为不需要储存虚部的资讯，内存的需求亦有所减少。此外因为正转换与逆转换有相当的一致性，架构设计简单亦有许多相关算法提出。在输入为实数时，可替代离散傅里叶变换进行频谱分析与折积的计算，。 在不同的应用需求上，一般化离散哈特利转换与其快速算法被提出，如欲进一步降低复杂度，亦有相关文献讨论如何产生近似离散哈特利转换之整数离散哈特利转换，使离散哈特利转换对浮点数乘法的需求可以进一步去除。

傅里叶变换 快速傅里叶变换

• R. N. Bracewell, "Discrete Hartley transform," J. Opt. Soc. Am. 73 (12), 1832–1835 (1983).
• R. N. Bracewell, "The fast Hartley transform," Proc. IEEE 72 (8), 1010–1018 (1984).
• R. N. Bracewell, The Hartley Transform (Oxford Univ. Press, New York, 1986).
• R. N. Bracewell, "Computing with the Hartley Transform," Computers in Physics 9 (4), 373–379 (1995).
• R. V. L. Hartley, "A more symmetrical Fourier analysis applied to transmission problems," Proc. IRE 30, 144–150 (1942).
• H. V. Sorensen, D. L. Jones, C. S. Burrus, and M. T. Heideman, "On computing the discrete Hartley transform," IEEE Trans. Acoust. Speech Sig. Processing ASSP-33 (5), 1231–1238 (1985).
• H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, "Real-valued fast Fourier transform algorithms," IEEE Trans. Acoust. Speech Sig. Processing ASSP-35, 849–863 (1987).
• Pierre Duhamel and Martin Vetterli, "Improved Fourier and Hartley transform algorithms: application to cyclic convolution of real data," IEEE Trans. Acoust. Speech Sig. Processing ASSP-35, 818–824 (1987).
• Mark A. O'Neill, "Faster than Fast Fourier", Byte 13(4):293-300, (1988).
• J. Hong and M. Vetterli and P. Duhamel, "Basefield transforms with the convolution property," Proc. IEEE 82 (3), 400-412 (1994).
• D. A. Bini and E. Bozzo, "Fast discrete transform by means of eigenpolynomials," Computers & Mathematics (with Applications) 26 (9), 35–52 (1993).
• Miodrag Popovi? and Dragutin ?evi?, "A new look at the comparison of the fast Hartley and Fourier transforms," IEEE Trans. Signal Processing 42 (8), 2178-2182 (1994).
• Neng-Chung Hu et al., "Generalized Discrete Hartley Transforms," IEEE Trans. Signal Processing, vol. 42, No. 12, Dec. 1992
• Guoan Bi et al., "Fast Algorithms for Generalized Discrete Hartley Transform of Composite Sequence Lengths," IEEE Trans. Circuits and System-II vol. 49, No. 9, Sept. 2000
• Soo-Chang Pei and Jian-Jiun Ding, "The Integer Transforms Analogous to Discrete Trigonometric Transforms," IEEE Trans. on Signal Processing vol.48, No. 12, Dec. 2000