第十一章 离散沃尔什变换及其快速算法

　　全体沃尔什函数以及它的子集都形成群，并且是可交换群。这说明它们满足封闭性的条件。它们还满足完备性条件。

　　因为沃尔什函数也是完备的正交函数系，那么满足条件的连续函数x(t)也能展开成沃尔什级数。为了方便，我们把x(t)定义在归一化的半开区间上，以表示，则

　　因此，对给定的任意小的，都能找到一个N，使kN时，。也就是N以后的各项可以忽略，即(11.4)和(11.5)式是足够准确的。

　　(DWT)W可直接由前N项沃尔什函数表示式(11.4)导出，其系数由(11.2)式的前N个决定。在这里，把，则由(11.2)式

　　上两式中的最高列率为N/2。根据列率域的取样定理，把的定义区间N等分，每一等份的时隙为，且令

　　说明：离散沃尔什变换DWT与离散傅里叶变换DFT非常相似，其区别在于用列率域代替了频域：(1)以权函数代替了；(2)以变换系数代替了X(k)；(3)因子1/N的位置不同，前者在逆变换中，后者在正变换中。

　　实质上是离散沃尔什级数前N项的系数。以表示阶矩阵，其中p为正整数，则(11.9)式可以写成矩阵形式

　　由于按阿达玛排列的沃尔什函数实际上是阿达玛矩阵从上而下按行编号(k)所得，而阿达玛矩阵有简单的递推关系，即从低阶阿达玛矩阵很容易得到高阶阿达玛，因此按阿达玛排列的沃尔什变换应用得更广泛一些。

　　按阿达玛排列的沃尔什变换与按沃尔什排列的沃尔什变换只是排列次序不同，本质上是一样的，所以只要以代替(DWT)W定义式中的就可以得到(DWT)H的定义式。

　　同样，以阿达玛矩阵，，p为正整数，代替(11.11)式中的，可以得到(DWT)H的矩阵形式定义式

　　所对应的沃尔什分量的列率简称的列率，以符号iB表示。下面从与的关系来说明iB。由(10.9)式

　　其中，是序号的p位二进制表示式的码位倒置后的表示式，是序号的p位格雷码，其中，p为正整数。

　　沃尔什排列的快速沃尔什变换是从阿达玛排列的快速沃尔什变换修改而来的，所以首先介绍阿达玛排列的快速沃尔什变换。

　　（1）(FWT)H与FFT一样，是由基本蝶式计算单元组成，基本蝶式计算单元的运算规则

　　（3）(FWT)H只有加减法运算(不计1/N因子)，完全消除了乘法运算，优于FFT。每级迭代，加减法次数为N，总共需要次加减法运算；

　　（4）FFT中原位计算的性能，对(FWT)H仍适用，因此只需要N个储存单元；

　　（5）(FWT)H的流图输入序列和输出序列都是正常顺序排列，不需要码位倒置程序；

　　（6）逆变换比正变换只少了1/N因子。因此图11.2所示流图去掉最后的乘1/N因子就可以用于(IFWT)H，这是流图输入序列为{Bx(k)}，输出序列为{x(n)}。

　　比较图11.2与图11.4可以发现，其中一个的逆转，即输入与输出两端互相调换，就是另外一个。去掉1/N因子，逆变换的流图也具有“逆转”特性。

　　由于只是排列的方法不同，它们之间有固定关系，因此对给定的时域序列，可以先由(FWT)H求出，然后再转化成。这种算法要求格雷码至二进码的转换，不是最有效的方法。

　　我们下面介绍的(FWT)W算法是由(FWT)H稍加修改而来，迭代运算的级数、运算次数以及原位运算等性能都与(FWT)H相同，并且逆变换与正变换的算法也相同。

　　“反号”的规律是：对图11.2一类流图，第r迭代级内的“块”自上而下按自然数编号，则偶数号“块”反号，奇数号“块”不反号。所谓“块”反号就是块内所有蝶式计算均按“反号”规则(11.24)式运算。如图11.6所示，第一级迭代只有1块，不反号；第二级迭代有2个块，第2块反号；第三级迭代有4个块，第2、4两个块反号。

　　对图11.4一类的流图，反号规律则不同，如图11.7所示，它不是按块反号，而是块内若包含两个以上的基本蝶式计算单元，则有一半(后一半)发生反号，另一半(前一半)不反号，若一块内只有一个基本蝶式计算单元，则不反号。

　　（3）输入序列或输出序列要进行码位倒置处理，方法与FFT中的完全相同。对图11.2一类的流图，要对输入序列进行码位倒置；对图11.4一类的流图，要对输出序列进行码位倒置。

　　在本节中，用符号DWT表示任一种排列的离散沃尔什变换，{W(k)}表示任何一种排列的离散沃尔什变换的列率域序列，对应的时域序列以{x(n)}表示。即与

　　我们在第二章第四节说明了循环位移序列以及循环位移序列的DFT。即若x2(n)是x1(n)顺向循环（圆位移）s步后的序列，并令各自的DFT分别为X1(k)和X2(k)，则有

　　则称z(n)L为x(n)并元位移l步的并元位移序列。当n, l取不同的值，并元位移的结果示于表11.2。

　　式中Wal(k,l)是[Wal(p)]第k行第l列的元素。在上式推导中使用了乘法定理(10.16)式以及模二加法的性质，即若n⊕l=r，则n=r⊕l

　　上式表明，Wz2(k)与l无关，即序列{x(n)}并元位移l步后，取其DWT后的第k个系数的平方Wz2(k)与l无关，仍等于W2(k)。W2(k)实质是按列率表达的功率，因此就得到

　　两时域序列并元卷积的DWT等于两序列DWT的乘积。或者说，两时域序列的并元卷积/相关{k12(n)}与两序列的DWT之乘积{W1(k)W2(k)}构成一个DWT的变换对。

　　即两列率域序列并元卷积的IDWT等于两列率域序列各自IDWT之乘积。或者说，两列率域的并元相关/卷积{k12(k)}与这两列率域的各自IDWT之乘积构成一个DWT的变换对。这就是列率域中的并元卷积定理。

　　上式成为自相关定理。它说明自相关序列与功率谱是一对DWT。这与DFT中的维纳定理相似。

　　这就是DWT中的Paserval定理，与由(11.10a)式导出的熟知的DFT中的Paserval定理也非常相似。这一定理证实了沃尔什函数的完备性。

　　本节和下一节要介绍如何定义和计算沃尔什谱。(DWT)W谱是按沃尔什排列的离散沃尔什变换的谱。即沃尔什谱是列率谱。

　　令时域序列为{x(n)}，DFT得结果为{X(k)}，由于DFT的权指数为WNkn复数，所以一般说来，X(k)应是复数，故可令

　　(DFT)谱有明确的物理意义。X(k)是信号x(n)的正弦分量系数，其中GX(k)可以看成1欧姆电阻上的电流或电压的增幅，是相应的幅角，而PX(k)则是单位时间（1秒）内消耗的功率。

　　我们已经指出，(DWT)w的结果是Wx(k)相应的沃尔什分量的系数，其列率i是自然顺序增长的，i与k的对应关系是

　　由于不能像正余弦函数那样合并成一项，所以不能得到类似于DFT中的振幅谱和相位谱。但是可以定义Cal和Sal系数的平方和为功率谱。据上式

　　严格地说，沃尔什变换是没有振幅谱和相位谱的。但是有些作者仍然仿照DFT中的相位谱的定义，来定义(DWT)w的相位谱

　　(DWT)H指按阿达玛排列的离散沃尔什变换的谱。下面首先说明(DWT)H对时域序列{x(n)}循环位移一些不变的量。以N=8为例，令{z(n)}L表示{x(n)}循环左移l位后的序列，即

　　由上式可以看出，[A8]由沿对角线排列的一些方阵组成，它们的阶愈来愈大。利用(11.47)式以及分块矩阵乘法，可以得到

　　可见，上式右端不是改变的量，即中不遂序列的循环移位而改变的量。我们把这些量定义为的功率普，这个谱可表示为

　　可见，不想的功率谱那样，每个谱点都是单一列率的功率，对，每个谱点含有一族列率的功率，每组列率都是由最低列率及其全部奇数倍的列率组成。当然，所有谱点的列率的和正好等于个。

　　为了获得时域信号序列的功率谱，不必算出全部系数，只要对的流图稍加简化就可得到全部谱点。以及图的流图为例，可有

　　显然，的相位谱的每个谱点包含的列率与相应的功率谱的所有列率相同。因为这样的列率族使数据压缩，所以只给定对应的功率谱和相位谱，是不能恢复原数据序列的。这是与的谱所不同的。

　　对略加修改，就可以得到修改的沃尔什—阿达玛变换，以符号表示，这一正交变换的定义如下

　　由于，与不同，是非对称的，所以计算与计算的流图的结构也不一样。以为例，与的算法流图分别示于图和图中。

　　上式就是对维序列的每一行做点一维变换，共做次，结果仍是维序列，然后代入式：

　　上式就是对维序列的每一行做点一维变换，共做次，结果就是要求的维列率域序列

　　计算维离散沃尔什变换的另一种方法是转化作一维变换，即将数据矩阵，按列一次排下去，就形成个数据的列阵，然后做点一维变换，最后再按列巴数据依次排成维序列。现在举一例说明。