快速沃爾什轉換

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

在計算數學中，一個與阿達馬變換有高度相關的快速沃爾什轉換（Template:Lang-en，FWHT_h）是一個十分有效率的演算法，目的是計算阿達馬變換。一個直觀且基本的沃爾什轉換，他的計算複雜度 大約是 O($N^2$)。而快速沃爾什轉換只需要$N\log N$ 個加法或是減法即可。

而快速沃爾什轉換是一個分而治之的演算法，是一個常見的遞迴方法，將大小為 $N$的沃爾什轉換拆成兩個大小為$N/2$ 的沃爾什轉換。這樣的寫法是根據$2N\times 2N$阿達馬矩陣 $H_N$的遞迴定義:

$H_N=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}{H}_{N-1}& H_{N-1}\\ H_{N-1}& -H_{N-1}\end{array}\right).$

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

沃爾什矩陣，又叫沃爾什序列，快速沃爾什轉換FWHT_w，就是用上面的作法計算以後，把輸出結果排成序列。

相關條目

• 快速傅立葉轉換
• 沃爾什轉換
• 阿達馬變換

參考資料

• Template:Cite journal