阿达马变换

阿达马变换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 逻辑门。

 

其中,  

 

 

  • 调变性质

 

 

 

 

 

  • 折积性质 (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.