快速沃爾什轉換

計算數學中,一個與阿達馬變換有高度相關的快速沃爾什轉換(英語:fast Walsh–Hadamard transformFWHTh)是一個十分有效率的演算法,目的是計算阿達馬變換。一個直觀且基本的沃爾什轉換,他的計算複雜度 大約是 O()。而快速沃爾什轉換只需要 個加法或是減法即可。

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

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

其中 的正規化項可以提出或省略掉。

沃爾什矩陣,又叫沃爾什序列,快速沃爾什轉換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.