在計算數學中，一個與阿達馬變換有高度相關的快速沃爾什轉換（，FWHTh）是一個十分有效率的演算法，目的是計算阿達馬變換。一個直觀且基本的沃爾什轉換，他的計算複雜度 大約是 O(N^2)。而快速沃爾什轉換只需要N \log N 個加法或是減法即可。
而快速沃爾什轉換是一個分而治之的演算法，是一個常見的遞迴方法，將大小為 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/\sqrt2 的正規化項可以提出或省略掉。
沃爾什矩陣，又叫沃爾什序列，快速沃爾什轉換FWHTw，就是用上面的作法計算以後，把輸出結果排成序列。
相關條目
- 快速傅立葉轉換
- 沃爾什轉換
- 阿達馬變換
參考資料
*
评论 (0)