阿达马变换

阿达马变换（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.