阿达马变换

阿达马变换（Hadamard transform），或称沃尔什-阿达玛转换，是一种广义傅立叶变换（Fourier transforms），作为变换编码的一种在影片编码当中使用有很久的历史。在近来的影片编码标准中，阿达马变换多被用来计算SATD(一种影片残差信号大小的衡量)。

在数字信号处理大型集成电路算法的领域中，阿达马变换是一种简单且重要的算法之一，主要能针对频谱做快速的分析。

变换矩阵

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

<math> H_4 = \begin{bmatrix}

1 &  1 &  1 &  1 \\
1 & -1 &  1 & -1 \\
1 &  1 & -1 & -1 \\
1 & -1 & -1 &  1 

\end{bmatrix} </math>

<math> 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} </math>

SATD计算方法

当计算4x4块<math>\begin{bmatrix}L_4\end{bmatrix}</math>的SATD时，先使用下面的方法进行二维的阿达马变换：

<math>

 \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}

</math>

然后计算<math>\begin{bmatrix}L_4'\end{bmatrix}</math>所有系数绝对值之和并归一化。

类似的，当计算8x8块<math>\begin{bmatrix}L_8\end{bmatrix}</math>的SATD时，先使用下面的方法进行二维的Hadamard变换：

<math>

 \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}

</math>

然后计算<math>\begin{bmatrix}L_8'\end{bmatrix}</math>所有系数绝对值之和并归一化。

建构阿达马变换

阿达马变换转换主要型式为 <math> \boldsymbol{2^k} </math> 点的转换矩阵，其最小单位矩阵为 2x2 的阿达马变换矩阵，以下分别为二点、四点与如何产生 <math> \boldsymbol{2^k} </math> 点的阿达马变换转换步骤。

• 二点阿达马变换转换：

<math> \boldsymbol{W_2} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} </math>

• 四点阿达马变换转换：

<math> \boldsymbol{W_4} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -1 \end{bmatrix}</math>

• 产生 <math> \boldsymbol{2^k} </math> 点阿达马变换的步骤：

步骤一： <math> \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} </math>

步骤二： 根据正负号次序 (Sign change,正负号改变次数) 将矩阵 (Matrix) 内的列向量做顺序上的重新排列。

<math> \boldsymbol{V_{2^{k+1}}} \longrightarrow \boldsymbol{W_{2^{k+1}}} </math>

范例

<math> \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}. </math>

<math> \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}. </math>

特性

• 正交性

<math> \sum_{n=0}^{N-1} W\left[ {h, n} \right]W\left[ {m, n} \right] = 0, \quad \mathrm{if} \, h \ne m. </math>

其表示 Walsh-Hadamard 转换矩阵中，不同的列向量 (Row verctor) 做内积 (Inner product) 为零。

• 奇偶函数性质

可简单从 Walsh-Hadamard 转换矩阵中发现，其奇数列向量呈现左右两边偶对称(Even symmetric)。反之，其偶数列向量呈现左右两边奇对称(Odd symmetric)。

• 线性关系

若 <math> f\left[{n}\right] \Rightarrow F\left[{m}\right] \, and \, \, g\left[{n}\right] \Rightarrow G\left[{m}\right], </math>

则 <math> a\,f\left[{n}\right] + b\,g\left[{n}\right] \Rightarrow a\,F\left[{m}\right] + b\,G\left[{m}\right]. </math>

• 逻辑相加性质

<math> W\left[{m, n}\right] \cdot W\left[{l, n}\right] = W\left[{m \oplus l, n}\right]. </math>

范例：

<math> 0 \oplus 0 = 0, \quad 0 \oplus 1 = 1, \quad 1 \oplus 0 = 1, \quad 1 \oplus 1 = 0, </math>

其运算方式为布林代数内的 XOR 逻辑门。

• 特殊函数

<math> \delta\left[{n}\right] \Rightarrow 1, \quad 1 \Rightarrow N \cdot \delta\left[{n}\right]. </math>

其中， <math> \delta\left[{n}\right] = \begin{cases} \, 1, \quad \mathrm{when} \; n = 0 \\ \, 0, \quad \mathrm{when} \; n \ne 0 \end{cases}. </math>

• 平移性质

若 <math> f\left[{n}\right] \Rightarrow F\left[{m}\right], </math>

则 <math> f\left[{n \oplus k}\right] \Rightarrow W\left[{k, m}\right] F\left[{m}\right]. </math>

• 调变性质

若 <math> f\left[{n}\right] \Rightarrow F\left[{m}\right], </math>

则 <math> W\left[{k, n}\right] f\left[{n}\right] \Rightarrow F\left[{m \oplus k}\right]. </math>

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

若 <math> 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. </math>

若 <math> f\left[{n}\right] \Rightarrow F\left[{m}\right] \, and \, \, g\left[{n}\right] \Rightarrow G\left[{m}\right], </math>

则 <math> \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]. </math>

• 折积性质 (Convolution Property)

若 <math> f\left[{n}\right] \Rightarrow F\left[{m}\right] \, and \, \, g\left[{n}\right] \Rightarrow G\left[{m}\right], </math>

则 <math> 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], </math>

其中 <math> \star </math> 代表逻辑折积 (Logical convolution)。

优缺点比较

优点

• 仅需实数运算 (Real operation) 。
• 不需乘法运算 (No multiplication) ，仅有加减法运算。
• 有部分性质类似于离散傅立叶变换 (Discrete fourier transform) 。
• 顺向转换 (Forward transform) 与反向转换 (Inverse transform ) 型式为相似式。

<math> \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}, </math>

其中 <math> F\left[ n \right] </math> 与 <math> f\left[ n \right] </math> 分别都为行向量 (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 转换中的一项特例情况，其将 <math> w = \pm 2^0 = 1 </math> 即可求得。

以下为四点的 Jacket 转换：

<math> \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.</math>

• <math> \boldsymbol{2^{k+1}} </math> 点的 Jacket 转换：

<math> \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}. </math>

相关条目

• 阿达马矩阵

参考文献

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