阿达马变换

Template:Mergefrom 阿达马变换（Template:Lang），或称沃爾什-阿達瑪轉換，是一种廣義傅立葉變換（Fourier transforms），作为变换编码的一种在影片编码当中使用有很久的历史。在近来的影片编码标准中，阿达马变换多被用来计算SATD(一种影片残差信号大小的衡量)。

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

变换矩阵

在H.264中使用了4阶和8阶的阿达马变换来计算SATD，其变换矩阵为：

$H_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\end{array}\right]$

$H_8=\left[\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ 1& -1& 1& -1& 1& -1& 1& -1\\ 1& 1& -1& -1& 1& 1& -1& -1\\ 1& -1& -1& 1& 1& -1& -1& 1\\ 1& 1& 1& 1& -1& -1& -1& -1\\ 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{array}\right]$

SATD计算方法

当计算4x4块$\left[\begin{array}{c}{L}_4\end{array}\right]$的SATD时，先使用下面的方法进行二维的阿达马变换：

$\left[\begin{array}{c}{L_4}^{\prime }\end{array}\right]=\left[\begin{array}{c}{H}_4\end{array}\right]\times \left[\begin{array}{c}{L}_4\end{array}\right]\times \left[\begin{array}{c}{H}_4\end{array}\right]$

然后计算$\left[\begin{array}{c}{L_4}^{\prime }\end{array}\right]$所有系数绝对值之和并归一化。

类似的，当计算8x8块$\left[\begin{array}{c}{L}_8\end{array}\right]$的SATD时，先使用下面的方法进行二维的Hadamard变换：

$\left[\begin{array}{c}{L_8}^{\prime }\end{array}\right]=\left[\begin{array}{c}{H}_8\end{array}\right]\times \left[\begin{array}{c}{L}_8\end{array}\right]\times \left[\begin{array}{c}{H}_8\end{array}\right]$

然后计算$\left[\begin{array}{c}{L_8}^{\prime }\end{array}\right]$所有系数绝对值之和并归一化。

建構阿达马变换

阿达马变换轉換主要型式為 $2^{𝒌}$ 點的轉換矩陣，其最小單位矩陣為 2x2 的阿达马变换矩陣，以下分別為二點、四點與如何產生 $2^{𝒌}$ 點的阿达马变换轉換步驟。

• 二點阿达马变换轉換：

${𝑾}_2=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$

• 四點阿达马变换轉換：

${𝑾}_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\\ 1& -1& 1& -1\end{array}\right]$

• 產生 $2^{𝒌}$ 點阿达马变换的步驟：

步驟一： ${𝑽}_{2^{𝒌\mathit{+}1}}=\left[\begin{array}{cc}{𝑾}_{2^{𝒌}}& {𝑾}_{2^{𝒌}}\\ {𝑾}_{2^{𝒌}}& \mathit{-}{𝑾}_{2^{𝒌}}\end{array}\right]$

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

${𝑽}_{2^{𝒌\mathit{+}1}}⟶{𝑾}_{2^{𝒌\mathit{+}1}}$

範例

${𝑽}_4=\left[\begin{array}{cc}{𝑾}_2& {𝑾}_2\\ {𝑾}_2& \mathit{-}{𝑾}_2\end{array}\right]=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\end{array}\right],{𝑾}_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ 1& -1& -1& 1\\ 1& -1& 1& -1\end{array}\right].$

${𝑽}_8=\left[\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ 1& 1& -1& -1& 1& 1& -1& -1\\ 1& -1& -1& 1& 1& -1& -1& 1\\ 1& -1& 1& -1& 1& -1& 1& -1\\ 1& 1& 1& 1& -1& -1& -1& -1\\ 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{array}\right],{𝑾}_8=\left[\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ 1& 1& 1& 1& -1& -1& -1& -1\\ 1& 1& -1& -1& -1& -1& 1& 1\\ 1& 1& -1& -1& 1& 1& -1& -1\\ 1& -1& -1& 1& 1& -1& -1& 1\\ 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{array}\right].$

特性

• 正交性

$\sum _{n=0}^{N-1}W\left[h,n\right]W\left[m,n\right]=0,\mathrm{i}\mathrm{f}h\ne m.$

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

• 奇偶函數性質

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

• 線性關係

若 $f\left[n\right]\Rightarrow F\left[m\right]andg\left[n\right]\Rightarrow G\left[m\right],$

則 $af\left[n\right]+bg\left[n\right]\Rightarrow aF\left[m\right]+bG\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,0\oplus 1=1,1\oplus 0=1,1\oplus 1=0,$

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

• 特殊函數

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

其中， $\delta \left[n\right]=\{\begin{array}{c}1,\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}n=0\\ 0,\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}n\ne 0\end{array}.$

• 平移性質

若 $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],\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]andg\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]andg\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{array}{c}\begin{array}{ccccc}F\left[m\right]& =& \sum _{n=0}^{N-1}W\left[m,n\right]f\left[n\right]& & (\text{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]& & (\text{Inverse Type})\end{array}\end{array},$

其中 $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 轉換：

${𝑱}_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -w& w& -1\\ 1& w& -w& 1\\ 1& -1& -1& 1\end{array}\right],wherew=\pm 2^k.$

• $2^{𝒌\mathit{+}1}$ 點的 Jacket 轉換：

${𝑱}_{2^{𝒌\mathit{+}1}}=\left[\begin{array}{cc}{𝑱}_{2^{𝒌}}& {𝑱}_{2^{𝒌}}\\ {𝑱}_{2^{𝒌}}& -{𝑱}_{2^{𝒌}}\end{array}\right].$

相关条目

• 阿达马矩阵

參考文獻

• 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.