快速沃爾什轉換
外观
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/58/1010_0110_Walsh_spectrum_%28fast_WHT%29.svg/400px-1010_0110_Walsh_spectrum_%28fast_WHT%29.svg.png)
在計算數學中,一個與阿達馬變換有高度相關的快速沃爾什轉換(英語:fast Walsh–Hadamard transform,FWHTh)是一個十分有效率的演算法,目的是計算阿達馬變換。一個直觀且基本的沃爾什轉換,他的計算複雜度 大約是 O()。而快速沃爾什轉換只需要 個加法或是減法即可。
而快速沃爾什轉換是一個分而治之的演算法,是一個常見的遞迴方法,將大小為 的沃爾什轉換拆成兩個大小為 的沃爾什轉換。這樣的寫法是根據阿達馬矩陣 的遞迴定義:
其中 的正規化項可以提出或省略掉。
沃爾什矩陣,又叫沃爾什序列,快速沃爾什轉換FWHTw,就是用上面的作法計算以後,把輸出結果排成序列。
相關條目
[编辑]參考資料
[编辑]- 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.
![]() | 这是一篇電腦科學小作品。您可以通过编辑或修订扩充其内容。 |