第7章_沃尔什-哈达玛变换

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