阿达马变换(Hadamard transform),或称沃尔什-阿达玛转换,是一种广义傅立叶变换(Fourier transforms),作为变换编码的一种在影片编码当中使用有很久的历史。在近来的影片编码标准中,阿达马变换多被用来计算SATD(一种影片残差信号大小的衡量)。
在数字信号处理大型积体电路演算法的领域中,阿达马变换是一种简单且重要的演算法之一,主要能针对频谱做快速的分析。
变换矩阵[编辑]
在H.264中使用了4阶和8阶的阿达马变换来计算SATD,其变换矩阵为:
![{\displaystyle H_{4}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6dff19c9707132eb9741ece1892c3a59d746df7)
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32911953fcf1ec51329b45637d26a6b52d7a75ae)
SATD计算方法[编辑]
当计算4x4块
的SATD时,先使用下面的方法进行二维的阿达马变换:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74aa660c46c9c9ef23708ec8ee4d8bd837270ee8)
然后计算
所有系数绝对值之和并归一化。
类似的,当计算8x8块
的SATD时,先使用下面的方法进行二维的Hadamard变换:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8177664f9761ec022b97f4992f5832398700c373)
然后计算
所有系数绝对值之和并归一化。
建构阿达马变换[编辑]
阿达马变换转换主要型式为
点的转换矩阵,其最小单位矩阵为 2x2 的阿达马变换矩阵,以下分别为二点、四点与如何产生
点的阿达马变换转换步骤。
- 产生
点阿达马变换的步骤:
步骤一:
步骤二: 根据正负号次序 (Sign change,正负号改变次数) 将矩阵 (Matrix) 内的列向量做顺序上的重新排列。
其表示 Walsh-Hadamard 转换矩阵中,不同的列向量 (Row verctor) 做内积 (Inner product) 为零。
可简单从 Walsh-Hadamard 转换矩阵中发现,其奇数列向量呈现左右两边偶对称(Even symmetric)。反之,其偶数列向量呈现左右两边奇对称(Odd symmetric)。
若
则
范例:
其运算方式为布林代数内的 XOR 逻辑闸。
其中,
若
则
若
则
若
若
则
- 折积性质 (Convolution Property)
若
则
其中
代表逻辑折积 (Logical convolution)。
优缺点比较[编辑]
- 仅需实数运算 (Real operation) 。
- 不需乘法运算 (No multiplication) ,仅有加减法运算。
- 有部分性质类似于离散傅立叶变换 (Discrete fourier transform) 。
- 顺向转换 (Forward transform) 与反向转换 (Inverse transform ) 型式为相似式。
其中
与
分别都为行向量 (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 转换中的一项特例情况,其将
即可求得。
以下为四点的 Jacket 转换:
点的 Jacket 转换:
相关条目[编辑]
参考文献[编辑]
- 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.