快速沃尔什转换

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

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

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

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