Walsh-Hadamard轉換

**阿達馬變換**（**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.