阿达马变换
建议将沃尔什转换并入此条目或章节。(讨论) |
阿达马变换(Hadamard transform),或称沃尔什-阿达玛转换,是一种广义傅立叶变换(Fourier transforms),作为变换编码的一种在影片编码当中使用有很久的历史。在近来的影片编码标准中,阿达马变换多被用来计算SATD(一种影片残差信号大小的衡量)。
变换矩阵
在H.264中使用了4阶和8阶的阿达马变换来计算SATD,其变换矩阵为:
SATD计算方法
当计算4x4块 的SATD时,先使用下面的方法进行二维的阿达马变换:
然后计算 所有系数绝对值之和并归一化。
类似的,当计算8x8块 的SATD时,先使用下面的方法进行二维的Hadamard变换:
然后计算 所有系数绝对值之和并归一化。
建构阿达马变换
阿达马变换转换主要型式为 点的转换矩阵,其最小单位矩阵为 2x2 的阿达马变换矩阵,以下分别为二点、四点与如何产生 点的阿达马变换转换步骤。
- 二点阿达马变换转换:
- 四点阿达马变换转换:
- 产生 点阿达马变换的步骤:
步骤一:
步骤二: 根据正负号次序 (Sign change,正负号改变次数) 将矩阵 (Matrix) 内的列向量做顺序上的重新排列。
范例
特性
- 正交性
其表示 Walsh-Hadamard 转换矩阵中,不同的列向量 (Row verctor) 做内积 (Inner product) 为零。
- 奇偶函数性质
可简单从 Walsh-Hadamard 转换矩阵中发现,其奇数列向量呈现左右两边偶对称(Even symmetric)。反之,其偶数列向量呈现左右两边奇对称(Odd symmetric)。
若
则
- 逻辑相加性质
范例:
其运算方式为布林代数内的 XOR 逻辑门。
其中,
- 平移性质
若
则
- 调变性质
若
则
- 帕塞瓦尔定理 (Parseval's Theorem)
若
若
则
- 折积性质 (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.