阿达马变换

阿达马变换(),或称沃爾什-阿達瑪轉換,是一种廣義傅立葉變換(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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.