[科普中國]-快速沃爾什轉(zhuǎn)換

在計算數(shù)學(xué)中，一個與阿達馬變換有高度相關(guān)的快速沃爾什轉(zhuǎn)換（fast Walsh–Hadamard transform，F(xiàn)WHTh）是一個十分有效率的算法，目的是計算阿達馬變換?？焖傥譅柺厕D(zhuǎn)換是一個分而治之的算法，是一個常見的遞回方法，將大小N的沃爾什轉(zhuǎn)換拆成兩個大小為N/2 的沃爾什轉(zhuǎn)換。

簡介快速沃爾什轉(zhuǎn)換是一個用于計算阿達馬變換的方法。一個直觀且基本的沃爾什轉(zhuǎn)換，他的計算復(fù)雜度 大約是 O()。而快速沃爾什轉(zhuǎn)換只需要個加法或是減法即可。根據(jù) 阿達馬矩陣的遞回定義：

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

沃爾什矩陣，又叫沃爾什序列，快速沃爾什轉(zhuǎn)換FWHTw，就是用上面的作法計算以后，把輸出結(jié)果排成序列?？焖傥譅柺厕D(zhuǎn)換在諸如圖象處理等領(lǐng)域中有重要的應(yīng)用價值，而在這些應(yīng)用領(lǐng)域，待處理的數(shù)據(jù)量特別大，又常常有實時處理的要求1。

沃爾什轉(zhuǎn)換沃爾什轉(zhuǎn)換（Walsh Transform）是在頻譜分析上作為離散傅立葉變換的替代方案的一種方法。

在頻譜分析上最常用的一種方法是使用離散傅立葉變換，然而，即使已經(jīng)有許多快速的算法來實現(xiàn)離散傅立葉變換，仍然具有一些實現(xiàn)上的缺點，舉例來說，在離散傅立葉變換中，資料向量必須乘上復(fù)數(shù)系數(shù)的矩陣加以處理，而且每個復(fù)數(shù)系數(shù)的實部和虛部是一個正弦及余弦函數(shù)，因此大部分的系數(shù)都是浮點數(shù)，也就是說在做離散傅立葉變換處理的時候，我們必須做復(fù)數(shù)而且是浮點數(shù)的運算，因此計算量會比較大，而且浮點數(shù)運算產(chǎn)生的誤差會比較大。

而在沃爾什轉(zhuǎn)換中，資料向量需要乘上的矩陣是一個實數(shù)的矩陣，而且這些矩陣的系數(shù)是1或是–1，因此所有的系數(shù)都是絕對值大小相同的整數(shù)，這使得我們不需要作浮點數(shù)的乘法運算，更進一步，只需要使用加法來實現(xiàn)沃爾什轉(zhuǎn)換，這使的沃爾什轉(zhuǎn)換在運算復(fù)雜度上遠小于離散傅立葉變換。使用離散傅立葉變換相當(dāng)于把信號拆解成在不同頻率的正弦函數(shù)與余弦函數(shù)的分量，而使用沃爾什轉(zhuǎn)換相當(dāng)于把信號拆解成在許多不同震蕩頻率的方波上，因此，除非所要分析的信號擁有類似方波組合的特性，使用沃爾什轉(zhuǎn)換作頻譜分析的效果會比使用離散傅立葉變換分析的效果要差，這是降低運算復(fù)雜度所要付出的代價。沃爾什轉(zhuǎn)換的轉(zhuǎn)換式為

其中 是沃爾什轉(zhuǎn)換矩陣的第（m,n）個元素。 舉例來說，一個8點沃爾什轉(zhuǎn)換的轉(zhuǎn)換矩陣如下：

后面會解釋沃爾什轉(zhuǎn)換矩陣是如何產(chǎn)生，而沃爾什轉(zhuǎn)換的反轉(zhuǎn)換式為

注意到正轉(zhuǎn)換式與反轉(zhuǎn)換式只差了一個常數(shù)，這是由于沃爾什轉(zhuǎn)換矩陣的反矩陣就是自己的轉(zhuǎn)置矩陣乘上一個常數(shù)的緣故。

阿達馬變換阿達馬變換（Hadamard transform），或稱沃爾什-阿達瑪轉(zhuǎn)換，是一種廣義傅立葉變換（Fourier transforms），作為變換編碼的一種在影片編碼當(dāng)中使用有很久的歷史。在近來的影片編碼標(biāo)準(zhǔn)中，阿達馬變換多被用來計算SATD(一種影片殘差信號大小的衡量)。在數(shù)字信號處理大型集成電路算法的領(lǐng)域中，阿達馬變換是一種簡單且重要的算法之一，主要能針對頻譜做快速的分析。在H.264中使用了4階和8階的阿達馬變換來計算SATD，其變換矩陣為：

優(yōu)點

僅需實數(shù)運算 (Real operation) 。

不需乘法運算 (No multiplication) ，僅有加減法運算。

有部分性質(zhì)類似于離散傅立葉變換 (Discrete fourier transform) 。

順向轉(zhuǎn)換 (Forward transform) 與反向轉(zhuǎn)換 (Inverse transform ) 型式為相似式。

其中 與分別都為行向量 (Column vector) 。

缺點

其收斂速度較離散余弦變換慢，因此對于頻譜分析的效果較差。

其加減法量較離散傅立葉變換、離散余弦變換多。

本詞條內(nèi)容貢獻者為:

何星 - 副教授 - 上海交通大學(xué)