离散沃尔什-哈达玛变换的应用与分析

离散沃尔什-哈达玛变换（Discrete Walsh Hadamard Transform，DWHT）是将一个函数变换成取值为“+1”或“-1”的基本函数构成的级数。DWHT只需要进行实数运算，所需的存储量比FFT要少得多，运算速度也快得多。因此，DWHT在图像传输、通信技术和数据压缩中被广泛使用。DWHT具有能量集中的特性，而且原始数据中数字越是均匀分布，经变换后的数据越集中于矩阵的边角上。因此，可用来压缩图像信息。

（一）离散沃尔什变换

离散沃尔什（Walsh）变换的变换核由“+1”和“-1”所组成，本质上是将一个函数变换为取值为“+1”或“-1”的基向量构成的级数，以过零点数目替代频率的概念，称为序率。由于在变换过程中只有加法和减法运算，因而计算比较简单，易于硬件实现。

若N=2n，f（x）是时域的N点序列，x=0，1，2，…，N-1，则f（x）的沃尔什变换为

式中，u=0，1，2，…，N-1。式中变换核为

逆变换为

反变换核为h（x，u）=g（x，u）。上述变换式中bi（x）是x的二进制数的第i+1位的值（即0或1），如p=3，N=2p=8，x=6时，b0（6）=0，表示为b1（6）=1，b2（6）=1，变换核和反变换核用矩阵形式

二维离散沃尔什变换的正、反变换核相同，均为

则二维离散函数f（x，y）（x=0，1，…，M-1，y=0，1，…，N-1）的离散沃尔什正变换为

式中，u=0，1，…，M-1，ν=0，1，…，N-1。

逆变换为

（二）离散哈达玛变换

哈达玛变换本质上是一种特殊排序的沃尔什变换，它与沃尔什变换的区别是变换核矩阵行的次序不同。哈达玛变换的最大优点在于变换核矩阵具有简单的递推关系，即高阶的变换矩阵可以用低阶转换矩阵构成。

若N=2n，一维哈达玛正变换核与反变换核相同，为

因此一维离散哈达玛变换可表示为

式中，u=0，1，2，…，N-1。

逆变换为(www.xing528.com)

式中，x=0，1，2，…，N-1。

哈达玛变换核除了因子1/N 之外，由一系列的“+1”和“-1”组成。如N=8时的哈达玛变换核用矩阵表示为

由此矩阵可得出一个非常有用的结论，即2N阶的哈达玛变换矩阵可由N阶的变换矩阵按下述规律形成：

而最低阶（N=2）的哈达玛变换矩阵为

利用这个性质求N阶（N=2n）的哈达玛变换矩阵要比直接用式（2-170）来求此矩阵速度快得多，此结论提供了一种快速哈达玛变换（FHT）。

在哈达玛变换矩阵中，通常把沿某列符号改变的次数称为这个列的列率。则前面给出的N=8时的变换矩阵的8个列的列率分别为0、7、3、4、1、6、2和5。

二维离散哈达玛变换的正变换核和反变换核相同，为

式中M=2m，N=2n。则对应的二维哈达变换对可表示为

式中，u=0，1，2，…，M-1，ν=0，1，2，…，N-1。

式中，x=0，1，2，…，M-1，y=0，1，2，…，N-1。可以看出，二维离散哈达玛变换的正反变换核具有可分离性，因此可以通过两次一维变换来实现一个二维变换。

（三）快速沃尔什-哈达玛变换

类似于快速傅立叶变换，DWHT也有快速算法FWHT，也可将输入序列f（x）按奇偶进行分组，分别进行DWHT。FWHT的基本关系为

以8阶沃尔什-哈达玛变换为例，说明其快速算法

令

则