查看“︁快速沃爾什轉換”︁的源代码

[[File:1010 0110 Walsh spectrum (fast WHT).svg|thumb|400px|输入向量(1,0,1,0,0,1,1,0)的例子]]

在[[計算數學]]中，一個與[[沃爾什轉換|阿達馬變換]]有高度相關的'''快速沃爾什轉換'''（{{lang-en|'''fast Walsh–Hadamard transform'''}}，'''FWHT<sub>h</sub>'''）是一個十分有效率的[[演算法]]，目的是計算[[沃爾什轉換|阿達馬變換]]。一個直觀且基本的沃爾什轉換，他的[[計算複雜度]] 大約是 [[Big O notation|O(<math>N^2</math>)]]。而快速沃爾什轉換只需要<math>N \log N</math> 個加法或是減法即可。

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

:<math>H_N = \frac{1}{\sqrt 2} \begin{pmatrix} H_{N-1} & H_{N-1} \\ H_{N-1} & -H_{N-1} \end{pmatrix}. </math>

其中 <math>1/\sqrt2</math> 的正規化項可以提出或省略掉。

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

== 相關條目 ==
* [[快速傅立葉轉換]]
* [[沃爾什轉換]]
* [[阿達馬變換]]

== 參考資料 ==
*{{cite journal |last=Fino |first=B. J. |last2=Algazi |first2=V. R. |year=1976 |title=Unified Matrix Treatment of the Fast Walsh–Hadamard Transform |journal=IEEE Transactions on Computers |volume=25 |issue=11 |pages=1142–1146 |doi=10.1109/TC.1976.1674569 }}

{{電腦科學小作品}}
[[Category:数字信号处理]]