第7章 沃尔什 哈达玛变换ppt课件.ppt
7.5 离散沃尔什-哈达玛变换（Walsh Hadamard Transform）,7.5.1 格雷码（Gray Code）（1）二进制到格雷码的转换：,例：,（2）格雷码到二进制的转换：,7.5.2 拉德梅克函数（Rademacher） 1 . 拉德梅克函数定义 可见，R(n,t)为周期函数。,2 . 拉德梅克函数的规律和特性（1）周期函数 n=0时，T2； n=1时，T1； n=2时，T1/2； n=3时，T1/22； R(n,t)=R(n,t+1/2n-1),（2） 函数的取值 R(n,t)的取值只有1和1。（3） 函数的频率特性 R(n,t)是R(n1,t)的二倍频。（4） 函数离散化 如果已知n ，则R(n,t)在（0t1）范围内有2n-1个周期。（连续） 若在t=(k+1/2)/2n 处作取样，则可得到一个离散的数据序列 R(n,k)，其中，k=0,1,22n-1 。（离散）,7.5.3 沃尔什函数（Walsh） 沃尔什函数有三种不同的函数定义，但都可由拉德梅克函数构成。,（1）按沃尔什排列的沃尔什函数,其中，R(k+1,t)是任意拉德梅克函数，g(i)是i的格雷码， g(i)k是此格雷码的第k位数。P为正整数， 。,例：当p3时，对前8个Walw(i,t)取样，则：Walw(0,t)=1 1, 1, 1, 1, 1, 1, 1, 1Walw(1,t)=R(1,t) 1, 1, 1, 1,-1,-1,-1,-1Walw(2,t)=R(1,t) R(2,t) 1, 1, -1,-1,-1,-1, 1,1Walw(3,t)=R(2,t) 1, 1,-1,-1, 1, 1,-1,-1Walw(4,t)=R(2,t) R(3,t) 1,-1,-1, 1, 1,-1,-1, 1Walw(5,t)=R(1,t) R(2,t) R(3,t) 1,-1,-1, 1,-1, 1, 1,-1Walw(6,t)=R(1,t) R(3,t) 1,-1, 1,-1,-1, 1,-1, 1Walw(7,t)=R(3,t) 1,-1, 1,-1, 1,-1, 1,-1,取样后得到的按沃尔什排列的沃尔什函数矩阵,（2）按佩利（Paley）排列的沃尔什函数,其中，R(k+1,t)是任意拉德梅克函数，ik是自然二进制码的第k位数。P为正整数， 。,例：当p3时，对前8个Walp(i,t)取样，则：Walp(0,t)=1 1, 1, 1, 1, 1, 1, 1, 1Walp(1,t)=R(1,t) 1, 1, 1, 1,-1,-1,-1,-1Walp(2,t)=R(2,t) 1, 1,-1,-1, 1, 1,-1,-1Walp(3,t)= R(1,t) R(2,t) 1, 1, -1,-1,-1,-1, 1,1Walp(4,t)=R(3,t) 1,-1, 1,-1, 1,-1, 1,-1Walp(5,t)=R(1,t) R(3,t) 1,-1, 1,-1,-1, 1,-1, 1Walp(6,t)=R(2,t) R(3,t) 1,-1,-1, 1, 1,-1,-1, 1Walp(7,t)=R(1,t) R(2,t) R(3,t) 1,-1,-1, 1,-1, 1, 1,-1 ,取样后得到的按佩利排列的沃尔什函数矩阵,（3）按哈达玛（Hadamard）排列的沃尔什函数,其中，R(k+1,t)是任意拉德梅克函数，是倒序的二进制码的第k位数。P为正整数， 。,例：当p3时，对前8个WalH(i,t)取样，则：WalH(0,t)=1 1, 1, 1, 1, 1, 1, 1, 1WalH(1,t)=R(3,t) 1,-1, 1,-1, 1,-1, 1,-1WalH(2,t)=R(2,t) 1, 1,-1,-1, 1, 1,-1,-1WalH(3,t)=R(2,t) R(3,t) 1,-1,-1, 1, 1,-1,-1, 1WalH(4,t)=R(1,t) 1, 1, 1, 1,-1,-1,-1,-1WalH(5,t)=R(1,t) R(3,t) 1,-1, 1,-1,-1, 1,-1, 1WalH(6,t)=R(1,t) R(2,t) 1, 1, -1,-1,-1,-1, 1,1WalH(7,t)=R(1,t) R(2,t) R(3,t) 1,-1,-1, 1,-1, 1, 1,-1,取样后得到的按哈达玛排列的沃尔什函数矩阵,2n阶哈达玛矩阵有如下形式：,可见，哈达玛矩阵的最大优点在于它具有简单的递推关系， 即高阶矩阵可用两个低阶矩阵的克罗内克积(Kronecker Product)求得。因此常采用哈达玛排列定义的沃尔什变换。,7.5.4 离散沃尔什哈达玛变换（DWHT）,一维离散沃尔什变换定义为,一维离散沃尔什逆变换定义为,和,式中，HN为N阶哈达玛矩阵。,由哈达玛矩阵的特点可知，沃尔什-哈达玛变换的本质上是将离散序列f(x)的各项值的符号按一定规律改变后，进行加减运算， 因此，它比采用复数运算的DFT和采用余弦运算的DCT要简单得多。,例：将一维信号序列0，0，1，1，0，0，1，1作WHT变换及反变换。,二维离散沃尔什变换 很容易将一维WHT的定义推广到二维WHT。二维WHT的正变换核和逆变换核分别为,和,式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。,例：二维离散沃尔什变换的矩阵形式表达式为,和,求这两个信号的二维WHT。,M=N=4， 其二维WHT变换核为,所以,二维WHT结果（a）原图像 （b）WHT结果, 从以上例子可看出，二维WHT具有能量集中的特性，而且原始数据中数字越是均匀分布，经变换后的数据越集中于矩阵的边角上。因此，二维WHT可用于压缩图像信息。,7.5.5 快速沃尔什变换（FWHT） 类似于FFT，WHT也有快速算法FWHT， 也可将输入序列f(x)按奇偶进行分组，分别进行WHT。FWHT的基本关系为,以8阶沃尔什哈达玛变换为例，说明其快速算法。,令：,则：,算法一,沃尔什-哈达玛的蝶形运算示意图（算法一）,算法二,由于H8 G0 G1 G2均为对称矩阵，故H8 H8G0 G0 G1 G G2 G,令：,则：,沃尔什-哈达玛的蝶形运算示意图（算法二）,综上所述，WHT是将一个函数变换成取值为1或1的基本函数构成的级数，用它来逼近数字脉冲信号时要比FFT有利。同时， WHT只需要进行实数运算，存储量比FFT要少得多， 运算速度也快得多。因此，WHT在图像传输、 通信技术和数据压缩中被广泛使用。,
