阿达马变换

阿达马变换（Hadamard transform），或称沃尔什-阿达玛转换，是一种广义傅立叶变换（Fourier transforms），作为变换编码的一种在影片编码当中使用有很久的历史。在近来的影片编码标准中，阿达马变换多被用来计算SATD(一种影片残差信号大小的衡量)。

在数字信号处理大型集成电路算法的领域中，阿达马变换是一种简单且重要的算法之一，主要能针对频谱做快速的分析。

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

当计算4x4块${\displaystyle }$的SATD时，先使用下面的方法进行二维的阿达马变换：

然后计算${\displaystyle }$所有系数绝对值之和并归一化。

类似的，当计算8x8块${\displaystyle }$的SATD时，先使用下面的方法进行二维的Hadamard变换：

然后计算${\displaystyle }$所有系数绝对值之和并归一化。

阿达马变换转换主要型式为 ${\displaystyle {\mathbf{2}}^{\mathit{k}}}$ 点的转换矩阵，其最小单位矩阵为 2x2 的阿达马变换矩阵，以下分别为二点、四点与如何产生 ${\displaystyle {\mathbf{2}}^{\mathit{k}}}$ 点的阿达马变换转换步骤。

步骤一：

步骤二： 根据正负号次序 (Sign change,正负号改变次数) 将矩阵 (Matrix) 内的列向量做顺序上的重新排列。

${\displaystyle {\mathit{V}}_{{\mathbf{2}}^{\mathit{k}\mathbf{+}\mathbf{1}}}⟶<!--\; ⟶\; -->{\mathit{W}}_{{\mathbf{2}}^{\mathit{k}\mathbf{+}\mathbf{1}}}}$

${\displaystyle \underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}WW=0,\mathrm{i}\mathrm{f}h\ne <!--\; \ne \; -->m.}$

其表示 Walsh-Hadamard 转换矩阵中，不同的列向量 (Row verctor) 做内积 (Inner product) 为零。

可简单从 Walsh-Hadamard 转换矩阵中发现，其奇数列向量呈现左右两边偶对称(Even symmetric)。反之，其偶数列向量呈现左右两边奇对称(Odd symmetric)。

若 ${\displaystyle f\Rightarrow <!--\; \Rightarrow \; -->Fandg\Rightarrow <!--\; \Rightarrow \; -->G,}$

则 ${\displaystyle af+bg\Rightarrow <!--\; \Rightarrow \; -->aF+bG.}$

${\displaystyle W\cdot <!--\; \cdot \; -->W=W.}$

范例：

${\displaystyle 0\oplus <!--\; \oplus \; -->0=0,0\oplus <!--\; \oplus \; -->1=1,1\oplus <!--\; \oplus \; -->0=1,1\oplus <!--\; \oplus \; -->1=0,}$

其运算方式为布林代数内的 XOR 逻辑门。

${\displaystyle \mathrm{\delta <!--\; \delta \; -->}\Rightarrow <!--\; \Rightarrow \; -->1,1\Rightarrow <!--\; \Rightarrow \; -->N\cdot <!--\; \cdot \; -->\mathrm{\delta <!--\; \delta \; -->}.}$

其中， ${\displaystyle \mathrm{\delta <!--\; \delta \; -->}=\{\begin{array}{l}1,\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}n=0\\ 0,\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}n\ne <!--\; \ne \; -->0\end{array}.}$

若 ${\displaystyle f\Rightarrow <!--\; \Rightarrow \; -->F,}$

则 ${\displaystyle f\Rightarrow <!--\; \Rightarrow \; -->WF.}$

若 ${\displaystyle f\Rightarrow <!--\; \Rightarrow \; -->F,}$

则 ${\displaystyle Wf\Rightarrow <!--\; \Rightarrow \; -->F.}$

若 ${\displaystyle f\Rightarrow <!--\; \Rightarrow \; -->F,\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\left|f\right|}^2=\left(\frac{1}{N}\right)\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\left|F\right|}^2.}$

若 ${\displaystyle f\Rightarrow <!--\; \Rightarrow \; -->Fandg\Rightarrow <!--\; \Rightarrow \; -->G,}$

则 ${\displaystyle \underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}fg=\left(\frac{1}{N}\right)\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}FG.}$

若 ${\displaystyle f\Rightarrow <!--\; \Rightarrow \; -->Fandg\Rightarrow <!--\; \Rightarrow \; -->G,}$

则 ${\displaystyle h=f\star <!--\; \star \; -->g\Rightarrow <!--\; \Rightarrow \; -->H=FG,}$

其中 ${\displaystyle \star <!--\; \star \; -->}$ 代表逻辑折积 (Logical convolution)。

其中 ${\displaystyle F}$ 与 ${\displaystyle f}$ 分别都为行向量 (Column vector) 。

阿达马变换转换主要为一种非常适合应用于频域分析 (Spectrum analysis) ，去执行快速之分析。可惜的是对于折积性质是一种逻辑折积，与离散傅立叶变换上之折积性质截然不同。因此，较折积上无法取代离散傅立叶变换。

主要应用范围：

其主要是一种调变 (modulation) 与解调 (Demodultion) 之技术。

广义来说，其实阿达马变换转换是 Jacket 转换中的一项特例情况，其将 ${\displaystyle w=\pm <!--\; \pm \; -->2^0=1}$ 即可求得。

以下为四点的 Jacket 转换：