快速沃爾什轉換

在計算數學中，一個與阿達馬變換有高度相關的快速沃爾什轉換（英語：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.