沃尔什哈达玛变换ppt课件.ppt

7.5离散沃尔什-哈达玛变换（WalshHadamardTransform）,7.5.1格雷码（GrayCode）（1）二进制到格雷码的转换：,1,例：,2,（2）格雷码到二进制的转换：,3,7.5.2拉德梅克函数（Rademacher）1.拉德梅克函数定义可见，R(n,t)为周期函数。,4,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),5,（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。（离散）,6,7.5.3沃尔什函数（Walsh）沃尔什函数有三种不同的函数定义，但都可由拉德梅克函数构成。,（1）按沃尔什排列的沃尔什函数,其中，R(k+1,t)是任意拉德梅克函数，g(i)是i的格雷码，g(i)k是此格雷码的第k位数。P为正整数，。,7,例：当p3时，对前8个Walw(i,t)取样，则：Walw(0,t)=11,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,8,取样后得到的按沃尔什排列的沃尔什函数矩阵,9,（2）按佩利（Paley）排列的沃尔什函数,其中，R(k+1,t)是任意拉德梅克函数，ik是自然二进制码的第k位数。P为正整数，。,10,例：当p3时，对前8个Walp(i,t)取样，则：Walp(0,t)=11,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,11,取样后得到的按佩利排列的沃尔什函数矩阵,12,（3）按哈达玛（Hadamard）排列的沃尔什函数,其中，R(k+1,t)是任意拉德梅克函数，是倒序的二进制码的第k位数。P为正整数，。,13,例：当p3时，对前8个WalH(i,t)取样，则：WalH(0,t)=11,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,14,取样后得到的按哈达玛排列的沃尔什函数矩阵,15,2n阶哈达玛矩阵有如下形式：,16,可见，哈达玛矩阵的最大优点在于它具有简单的递推关系，即高阶矩阵可用两个低阶矩阵的克罗内克积(KroneckerProduct)求得。因此常采用哈达玛排列定义的沃尔什变换。,17,7.5.4离散沃尔什哈达玛变换（DWHT）,一维离散沃尔什变换定义为,一维离散沃尔什逆变换定义为,18,和,式中，HN为N阶哈达玛矩阵。,19,由哈达玛矩阵的特点可知，沃尔什-哈达玛变换的本质上是将离散序列f(x)的各项值的符号按一定规律改变后，进行加减运算，因此，它比采用复数运算的DFT和采用余弦运算的DCT要简单得多。,20,例：将一维信号序列0，0，1，1，0，0，1，1作WHT变换及反变换。,21,二维离散沃尔什变换很容易将一维WHT的定义推广到二维WHT。二维WHT的正变换核和逆变换核分别为,和,式中：x,u=0,1,2,M1；y,v=0,1,2,N1。,22,例：二维离散沃尔什变换的矩阵形式表达式为,和,求这两个信号的二维WHT。,23,M=N=4，其二维WHT变换核为,24,所以,25,26,二维WHT结果（a）原图像（b）WHT结果,27,从以上例子可看出，二维WHT具有能量集中的特性，而且原始数据中数字越是均匀分布，经变换后的数据越集中于矩阵的边角上。因此，二维WHT可用于压缩图像信息。,28,7.5.5快速沃尔什变换（FWHT）类似于FFT，WHT也有快速算法FWHT，也可将输入序列f(x)按奇偶进行分组，分别进行WHT。FWHT的基本关系为,29,以8阶沃尔什哈达玛变换为例，说明其快速算法。,30,令：,则：,算法一,31,32,33,34,沃尔什-哈达玛的蝶形运算示意图（算法一）,35,算法二,由于H8G0G1G2均为对称矩阵，故H8H8G0G0G1GG2G,36,令：,则：,37,沃尔什-哈达玛的蝶形运算示意图（算法二）,38,综上所述，WHT是将一个函数变换成取值为1或1的基本函