查看“︁阿达马变换”︁的源代码

{{mergefrom|沃爾什轉換}}
'''阿达马变换'''（{{lang|en|Hadamard transform}}），或称'''沃爾什-阿達瑪轉換'''，是一种廣義[[傅立葉變換]]（Fourier transforms），作为[[变换编码]]的一种在影片编码当中使用有很久的历史。在近来的影片编码标准中，阿达马变换多被用来计算SATD(一种影片[[残差]]信号大小的衡量)。

在[[數字信號處理]]大型積體電路演算法的領域中，阿达马变换是一種簡單且重要的[[演算法]]之一，主要能針對[[頻譜]]做快速的分析。

== 变换矩阵 ==
在[[H.264]]中使用了4阶和8阶的阿达马变换来计算[[SATD]]，其变换矩阵为：

:<math> H_4 = \begin{bmatrix}
 1 &  1 &  1 &  1 \\
 1 & -1 &  1 & -1 \\
 1 &  1 & -1 & -1 \\
 1 & -1 & -1 &  1 
\end{bmatrix} </math>

:<math> 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} </math>

== SATD计算方法 ==

当计算4x4块<math>\begin{bmatrix}L_4\end{bmatrix}</math>的SATD时，先使用下面的方法进行二维的阿达马变换：

:<math>
  \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}
</math>

然后计算<math>\begin{bmatrix}L_4'\end{bmatrix}</math>所有系数[[绝对值]]之和并[[归一化]]。


类似的，当计算8x8块<math>\begin{bmatrix}L_8\end{bmatrix}</math>的SATD时，先使用下面的方法进行二维的Hadamard变换：

:<math>
  \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}
</math>

然后计算<math>\begin{bmatrix}L_8'\end{bmatrix}</math>所有系数[[绝对值]]之和并[[归一化]]。

== 建構阿达马变换 ==

阿达马变换轉換主要型式為 <math> \boldsymbol{2^k} </math> 點的轉換[[矩陣]]，其最小單位[[矩陣]]為 2x2 的阿达马变换矩陣，以下分別為二點、四點與如何產生 <math> \boldsymbol{2^k} </math>  點的阿达马变换轉換步驟。

*二點阿达马变换轉換：

<math> \boldsymbol{W_2} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} </math>    

*四點阿达马变换轉換：

<math> \boldsymbol{W_4} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -1 \end{bmatrix}</math>

*產生 <math> \boldsymbol{2^k} </math> 點阿达马变换的步驟： 

步驟一： <math> \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} </math>


步驟二： 根據正負號次序 (Sign change,正負號改變次數) 將[[矩陣]] (Matrix) 內的列向量做順序上的重新排列。

<math> \boldsymbol{V_{2^{k+1}}} \longrightarrow  \boldsymbol{W_{2^{k+1}}} </math>

== 範例 ==

<math> \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}. </math>


<math>   \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}. </math>

== 特性 ==
*'''正交性'''

<math> \sum_{n=0}^{N-1} W\left[ {h, n} \right]W\left[ {m, n} \right] = 0, \quad \mathrm{if} \, h \ne m. </math>

其表示 Walsh-Hadamard 轉換[[矩陣]]中，不同的[[列向量]] (Row verctor) 做[[內積]] (Inner product) 為零。

*'''[[奇偶函數]]性質'''

可簡單從 Walsh-Hadamard 轉換[[矩陣]]中發現，其奇數[[列向量]]呈現左右兩邊[[偶對稱]](Even symmetric)。反之，其偶數[[列向量]]呈現左右兩邊[[奇對稱]](Odd symmetric)。

*'''[[線性關係]]'''

若 <math>  f\left[{n}\right] \Rightarrow F\left[{m}\right] \, and \, \, g\left[{n}\right] \Rightarrow G\left[{m}\right], </math>

則 <math>  a\,f\left[{n}\right] + b\,g\left[{n}\right] \Rightarrow a\,F\left[{m}\right] + b\,G\left[{m}\right]. </math>

*'''[[邏輯相加]]性質'''

<math>  W\left[{m, n}\right] \cdot W\left[{l, n}\right] = W\left[{m \oplus l, n}\right]. </math>

範例：

<math> 0 \oplus 0 = 0, \quad 0 \oplus 1 = 1, \quad 1 \oplus 0 = 1, \quad 1 \oplus 1 = 0, </math>

其運算方式為[[布林代數]]內的 XOR 邏輯閘。

*'''[[特殊函數]]'''

<math> \delta\left[{n}\right] \Rightarrow 1, \quad 1 \Rightarrow N \cdot \delta\left[{n}\right].  </math>

其中， <math> \delta\left[{n}\right] = \begin{cases} \, 1, \quad \mathrm{when} \; n = 0 \\ \, 0, \quad \mathrm{when} \; n \ne 0 \end{cases}. </math>

*'''[[平移]]性質'''

若 <math>  f\left[{n}\right] \Rightarrow F\left[{m}\right], </math>

則 <math>  f\left[{n \oplus k}\right] \Rightarrow W\left[{k, m}\right] F\left[{m}\right]. </math>

*'''[[調變]]性質'''

若 <math>  f\left[{n}\right] \Rightarrow F\left[{m}\right], </math>

則 <math>  W\left[{k, n}\right] f\left[{n}\right] \Rightarrow F\left[{m \oplus k}\right]. </math>

*'''[[帕塞瓦尔定理]]''' (Parseval's Theorem)

若 <math>  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. </math>

若 <math>  f\left[{n}\right] \Rightarrow F\left[{m}\right] \, and \, \, g\left[{n}\right] \Rightarrow G\left[{m}\right],  </math> 

則 <math> \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]. </math>

*'''[[摺積]]性質''' (Convolution Property)

若 <math>  f\left[{n}\right] \Rightarrow F\left[{m}\right] \, and \, \, g\left[{n}\right] \Rightarrow G\left[{m}\right], </math>

則 <math> 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],  </math>

其中 <math> \star </math> 代表[[邏輯摺積]] (Logical convolution)。

== 優缺點比較 ==
===優點===
*僅需[[實數]]運算 (Real operation) 。
*不需[[乘法]]運算 (No multiplication) ，僅有加減法運算。
*有部分性質類似於[[離散傅立葉變換]] (Discrete fourier transform) 。
*順向轉換 (Forward transform) 與反向轉換 (Inverse transform ) 型式為相似式。

<math> \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}, </math>

其中 <math> F\left[ n \right] </math> 與 <math> f\left[ n \right] </math> 分別都為[[行向量]] (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 轉換中的一項特例情況，其將 <math> w = \pm 2^0 = 1 </math> 即可求得。

以下為四點的 Jacket 轉換：

<math> \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.</math>

*<math> \boldsymbol{2^{k+1}} </math> 點的 Jacket 轉換：

<math> \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}. </math>

==相关条目==
*[[阿达马矩阵]]

==參考文獻==
*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.

[[category:数字信号处理]]
[[Category:影片和電影技術]]
[[Category:变换编码]]
[[Category:量子算法]]