阿達馬變換

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

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

## 變換矩陣

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

$$H_4 = \begin{bmatrix} <pre> 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 </pre> \end{bmatrix}$$

$$H_8 = \begin{bmatrix} <pre> 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 </pre> \end{bmatrix}$$

## SATD計算方法

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

$$<pre> \begin{bmatrix} L_4' \end{bmatrix} </pre> = <pre> \begin{bmatrix} H_4 \end{bmatrix} </pre> \times <pre> \begin{bmatrix} L_4 \end{bmatrix} </pre> \times <pre> \begin{bmatrix} H_4 \end{bmatrix} </pre>$$

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

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

$$<pre> \begin{bmatrix} L_8' \end{bmatrix} </pre> = <pre> \begin{bmatrix} H_8 \end{bmatrix} </pre> \times <pre> \begin{bmatrix} L_8 \end{bmatrix} </pre> \times <pre> \begin{bmatrix} H_8 \end{bmatrix} </pre>$$

然後計算$\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 \ne 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 \ne 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}.$$