阿达马变换

维基百科,自由的百科全书
跳转至: 导航搜索

阿达马变换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 \ne 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 \ne 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].

  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) 之技術。

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.