阿達馬變換

阿達馬變換（Hadamard transform），或稱沃爾什-阿達瑪轉換，是一種廣義傅立葉變換（Fourier transforms），作為變換編碼的一種在影片編碼當中使用有很久的歷史。在近來的影片編碼標準中，阿達馬變換多被用來計算SATD(一種影片殘差信號大小的衡量)。

在數字信號處理大型積體電路演算法的領域中，阿達馬變換是一種簡單且重要的演算法之一，主要能針對頻譜做快速的分析。

變換矩陣

在H.264中使用了4階和8階的阿達馬變換來計算SATD，其變換矩陣為：

$H_{4}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}$

$H_{8}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{bmatrix}}$

SATD計算方法

當計算4x4塊${\begin{bmatrix}L_{4}\end{bmatrix}}$的SATD時，先使用下面的方法進行二維的阿達馬變換：

${\begin{bmatrix}L_{4}'\end{bmatrix}}={\begin{bmatrix}H_{4}\end{bmatrix}}\times {\begin{bmatrix}L_{4}\end{bmatrix}}\times {\begin{bmatrix}H_{4}\end{bmatrix}}$

然後計算${\begin{bmatrix}L_{4}'\end{bmatrix}}$所有係數絕對值之和並歸一化。

類似的，當計算8x8塊${\begin{bmatrix}L_{8}\end{bmatrix}}$的SATD時，先使用下面的方法進行二維的Hadamard變換：

${\begin{bmatrix}L_{8}'\end{bmatrix}}={\begin{bmatrix}H_{8}\end{bmatrix}}\times {\begin{bmatrix}L_{8}\end{bmatrix}}\times {\begin{bmatrix}H_{8}\end{bmatrix}}$

然後計算${\begin{bmatrix}L_{8}'\end{bmatrix}}$所有係數絕對值之和並歸一化。

建構阿達馬變換

阿達馬變換轉換主要型式為 ${\boldsymbol {2^{k}}}$ 點的轉換矩陣，其最小單位矩陣為 2x2 的阿達馬變換矩陣，以下分別為二點、四點與如何產生 ${\boldsymbol {2^{k}}}$ 點的阿達馬變換轉換步驟。

• 二點阿達馬變換轉換：

${\boldsymbol {W_{2}}}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}$

• 四點阿達馬變換轉換：

${\boldsymbol {W_{4}}}={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\end{bmatrix}}$

• 產生 ${\boldsymbol {2^{k}}}$ 點阿達馬變換的步驟：

步驟一： ${\boldsymbol {V_{2^{k+1}}}}={\begin{bmatrix}{\boldsymbol {W_{2^{k}}}}&{\boldsymbol {W_{2^{k}}}}\\{\boldsymbol {W_{2^{k}}}}&{\boldsymbol {-W_{2^{k}}}}\end{bmatrix}}$

步驟二： 根據正負號次序 (Sign change,正負號改變次數) 將矩陣 (Matrix) 內的列向量做順序上的重新排列。

${\boldsymbol {V_{2^{k+1}}}}\longrightarrow {\boldsymbol {W_{2^{k+1}}}}$

範例

${\boldsymbol {V_{4}}}={\begin{bmatrix}{\boldsymbol {W_{2}}}&{\boldsymbol {W_{2}}}\\{\boldsymbol {W_{2}}}&{\boldsymbol {-W_{2}}}\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}},\quad {\boldsymbol {W_{4}}}={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\end{bmatrix}}.$

${\boldsymbol {V_{8}}}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\end{bmatrix}},\quad {\boldsymbol {W_{8}}}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{bmatrix}}.$

特性

• 正交性

$\sum _{n=0}^{N-1}W\left[{h,n}\right]W\left[{m,n}\right]=0,\quad \mathrm {if} \,h\neq m.$

其表示 Walsh-Hadamard 轉換矩陣中，不同的列向量 (Row verctor) 做內積 (Inner product) 為零。

• 奇偶函數性質

可簡單從 Walsh-Hadamard 轉換矩陣中發現，其奇數列向量呈現左右兩邊偶對稱(Even symmetric)。反之，其偶數列向量呈現左右兩邊奇對稱(Odd symmetric)。

• 線性關係

若 $f\left[{n}\right]\Rightarrow F\left[{m}\right]\,and\,\,g\left[{n}\right]\Rightarrow G\left[{m}\right],$

則 $a\,f\left[{n}\right]+b\,g\left[{n}\right]\Rightarrow a\,F\left[{m}\right]+b\,G\left[{m}\right].$

• 邏輯相加性質

$W\left[{m,n}\right]\cdot W\left[{l,n}\right]=W\left[{m\oplus l,n}\right].$

範例：

$0\oplus 0=0,\quad 0\oplus 1=1,\quad 1\oplus 0=1,\quad 1\oplus 1=0,$

其運算方式為布林代數內的 XOR 邏輯閘。

• 特殊函數

$\delta \left[{n}\right]\Rightarrow 1,\quad 1\Rightarrow N\cdot \delta \left[{n}\right].$

其中， $\delta \left[{n}\right]={\begin{cases}\,1,\quad \mathrm {when} \;n=0\\\,0,\quad \mathrm {when} \;n\neq 0\end{cases}}.$

• 平移性質

若 $f\left[{n}\right]\Rightarrow F\left[{m}\right],$

則 $f\left[{n\oplus k}\right]\Rightarrow W\left[{k,m}\right]F\left[{m}\right].$

• 調變性質

若 $f\left[{n}\right]\Rightarrow F\left[{m}\right],$

則 $W\left[{k,n}\right]f\left[{n}\right]\Rightarrow F\left[{m\oplus k}\right].$

• 帕塞瓦爾定理 (Parseval's Theorem)

若 $f\left[{n}\right]\Rightarrow F\left[{m}\right],\quad \sum _{n=0}^{N-1}\left|f\left[n\right]\right|^{2}=\left({\frac {1}{N}}\right)\sum _{n=0}^{N-1}\left|F\left[m\right]\right|^{2}.$

若 $f\left[{n}\right]\Rightarrow F\left[{m}\right]\,and\,\,g\left[{n}\right]\Rightarrow G\left[{m}\right],$

則 $\sum _{n=0}^{N-1}f\left[n\right]g\left[n\right]=\left({\frac {1}{N}}\right)\sum _{n=0}^{N-1}F\left[m\right]G\left[m\right].$

• 摺積性質 (Convolution Property)

若 $f\left[{n}\right]\Rightarrow F\left[{m}\right]\,and\,\,g\left[{n}\right]\Rightarrow G\left[{m}\right],$

則 $h\left[{n}\right]=f\left[{n}\right]\star g\left[{n}\right]\Rightarrow H\left[{m}\right]=F\left[{m}\right]G\left[{m}\right],$

其中 $\star$ 代表邏輯摺積 (Logical convolution)。

優缺點比較

優點

• 僅需實數運算 (Real operation) 。
• 不需乘法運算 (No multiplication) ，僅有加減法運算。
• 有部分性質類似於離散傅立葉變換 (Discrete fourier transform) 。
• 順向轉換 (Forward transform) 與反向轉換 (Inverse transform ) 型式為相似式。

${\begin{cases}{\begin{matrix}F\left[m\right]&=&\sum _{n=0}^{N-1}W\left[{m,n}\right]f\left[n\right]&&({\mbox{Forward Type}})\\f\left[n\right]&=&\left({\frac {1}{N}}\right)\sum _{n=0}^{N-1}W\left[{m,n}\right]F\left[m\right]&&({\mbox{Inverse Type}})\end{matrix}}\end{cases}},$

其中 $F\left[n\right]$ 與 $f\left[n\right]$ 分別都為行向量 (Column vector) 。

缺點

• 其收斂速度較離散餘弦變換慢，因此對於頻譜分析的效果較差。
• 其加減法量較離散傅立葉變換、離散餘弦變換多。

應用範圍

阿達馬變換轉換主要為一種非常適合應用於頻域分析 (Spectrum analysis) ，去執行快速之分析。可惜的是對於摺積性質是一種邏輯摺積，與離散傅立葉變換上之摺積性質截然不同。因此，較摺積上無法取代離散傅立葉變換。

主要應用範圍：

• 帶寬降低 (Bandwidth reduction) 。
• CDMA (Code division multiple access)。

其主要是一種調變 (modulation) 與解調 (Demodultion) 之技術。

• 資訊編碼 (Information coding)。
• 特徵識別 (Feature extraction)。
• 心電圖分析 (ECG signal analysis in medical signal processing)。
• Hadamard 頻譜量測 (Hadamard spectrometer)。
• 避免量化誤差 (Avoiding quantization error)。由於阿達馬變換轉換輸入輸出皆為整數，因此不會有量化誤差的問題。

Jacket 轉換

廣義來說，其實阿達馬變換轉換是 Jacket 轉換中的一項特例情況，其將 $w=\pm 2^{0}=1$ 即可求得。

以下為四點的 Jacket 轉換：

${\boldsymbol {J_{4}}}={\begin{bmatrix}1&1&1&1\\1&-w&w&-1\\1&w&-w&1\\1&-1&-1&1\end{bmatrix}},\quad where\ w=\pm 2^{k}.$

• ${\boldsymbol {2^{k+1}}}$ 點的 Jacket 轉換：

${\boldsymbol {J_{2^{k+1}}}}={\begin{bmatrix}{\boldsymbol {J_{2^{k}}}}&{\boldsymbol {J_{2^{k}}}}\\{\boldsymbol {J_{2^{k}}}}&-{\boldsymbol {J_{2^{k}}}}\end{bmatrix}}.$

相關條目

• 阿達馬矩陣

參考文獻

• Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.
• H. F. Harmuth,「Transmission of information by orthogonal functions,」1970.
• Moon-Hu. Lee,「A new reverse Jacket transform and its fast algorithm,」IEEE Trans. Circuits Syst.-II, vol. 47, pp.39-46, 2000.
• K.G.Beauchamp, "Walsh Functions and Their Applications," Academic Press,1975.
• H. F. Harmuth, "Transmission of Information by Orthogonal Functions," Springer, 1969.