快速沃尔什转换

在计算数学中，一个与阿达马变换有高度相关的快速沃尔什转换（英语：fast Walsh–Hadamard transform，FWHT_h）是一个十分有效率的算法，目的是计算阿达马变换。一个直观且基本的沃尔什转换，他的计算复杂度 大约是 O($N^{2}$)。而快速沃尔什转换只需要$N\log N$ 个加法或是减法即可。

输入向量(1,0,1,0,0,1,1,0)的例子

而快速沃尔什转换是一个分而治之的算法，是一个常见的递回方法，将大小为 $N$的沃尔什转换拆成两个大小为$N/2$ 的沃尔什转换。这样的写法是根据$2N\times 2N$阿达马矩阵 $H_{N}$的递回定义:

$H_{N}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{N-1}&H_{N-1}\\H_{N-1}&-H_{N-1}\end{pmatrix}}.$

其中 $1/{\sqrt {2}}$ 的正规化项可以提出或省略掉。

沃尔什矩阵，又叫沃尔什序列，快速沃尔什转换FWHT_w，就是用上面的作法计算以后，把输出结果排成序列。

相关条目

• 快速傅立叶转换
• 沃尔什转换
• 阿达马变换

参考资料

• Fino, B. J.; Algazi, V. R. Unified Matrix Treatment of the Fast Walsh–Hadamard Transform. IEEE Transactions on Computers. 1976, 25 (11): 1142–1146. doi:10.1109/TC.1976.1674569.