第九章离散傅立叶变换及其快速算法

1、第九章 离散傅立叶变换及其他离散正交变换 在离散时间信号与系统研究的历史中，有一个终于的问题：“如何把数字计算机的应用和信号分析与处理紧密地结合起来”。离散傅里叶变换（DFT）就是在解决这个矛盾中形成的一种概念和计算方法。 本章最后还介绍了傅里叶变换以外的其他离散正交变换，包括离散沃尔什变换和离散余弦变换。9.1引言引言9.2傅立叶变换的离散性和周期性傅立叶变换的离散性和周期性对称关系对称关系时域周期性时域周期性频域离散性频域离散性（时域重复（时域重复频域抽样）频域抽样）时域离散性时域离散性频域周期性频域周期性（时域抽样（时域抽样频域重复）频域重复）时域非周期时域非周期频域连续性频域连续性 （

2、频域取包络（频域取包络 ） 时域连续性时域连续性频域非周期频域非周期（傅立叶变换的对偶性）（傅立叶变换的对偶性）nnFTF101)(4四种物理存在信号的傅立叶变换四种物理存在信号的傅立叶变换（1）连续周期信号）连续周期信号（2）连续非周期信号）连续非周期信号（3）离散非周期序列）离散非周期序列（4）离散周期序列）离散周期序列（1）连续周期信号的傅立叶变换 从从FS到到FT 从单脉冲的周期重复从单脉冲的周期重复)(2)(1nFtfFTnn221111).(1TTtjnndtetfTF例1：周期矩形脉冲的FS和FT01T1TE)(tf1TE1E)(FnFtFSFT周期重复)(2111nnSaEn)

3、(2)(1nFtfFTnn2).(111221111nSaTEdtetfTFTTtjnndtetfFtj)()(（2）连续非周期信号的傅立叶变换E)(0tf022tE)(0F220nFFT例2：2)(SaEF从傅立叶积分得到从傅立叶积分得到从周期信号取单脉冲得到从周期信号取单脉冲得到例例2：从周期信号取单脉冲得到：从周期信号取单脉冲得到1T1TE)(tftnFE)(0tf022t110)(nnTFF220FT2).(111221111nSaTEdtetfTFTTtjnn2)(SaEFnnjjenxeX)()(（3）离散非周期序列的傅立叶变换 从从Z变换的变量置换得到变换的变量置换得到 从非周期

4、信号的抽样得到从非周期信号的抽样得到 从离散周期信号取单周期得到从离散周期信号取单周期得到例3：从非周期信号抽样得到离散非周期序列)(tf0t)(F01)(tP) 1 (0t0)(tfs相乘相卷)(sssss00tsT)(sFsT1FTFTFT频域周期重复)()(nsTnTttnssnp)()(时域抽样)(1snsnFT2022-4-26例例4：从离散周期信号取单周期得到：从离散周期信号取单周期得到t0221T1T)(nfp022)(0nfsTE222sT2sT2t)(22snsnSaTE（4 4）离散周期序列的傅立叶变换）离散周期序列的傅立叶变换 从连续周期信号的抽样得到从连续周期信号的抽样

5、得到 从离散周期序列的从离散周期序列的DFS得到得到 从离散非周期信号的周期重复得到从离散非周期信号的周期重复得到10)()()(NkpLNkkXnTxFT从连续周期信号的抽样得到从连续周期信号的抽样得到1T1TE)(tft1E)(FFTsTE122sT2sT2t)(2111nnSaTEns例例4：离散周期矩形序列的傅立叶变换：离散周期矩形序列的傅立叶变换t0221T1T)(nfpE)(pFsTTE1222sT2sT2t220t后重复)(1tf先抽样022)(0nf离散非周期信号的周期重复离散非周期信号的周期重复9.3 从离散傅立叶级数从离散傅立叶级数(DFS)到离散到离散傅立叶变换傅立叶变换

6、(DFT) 效仿连续周期信号有傅立叶级数，记作：效仿连续周期信号有傅立叶级数，记作： 离散周期序列也有傅立叶级数，记作：离散周期序列也有傅立叶级数，记作：dtetxTFeFtxTTtjnpnntjnnp2211)(1)()(1)(1)(1010222kXNenxNaeaeanxpNnknjpkknjNkkknjkkpNNN周期性以N为周期1.2 , 1 , 0)(1)(1.2 , 1 , 0)()(221010NkekXNnxNnenxkXknjNkppNnknjppNN离散周期序列的傅立叶级数离散周期序列的傅立叶级数(DFS)的正负的正负运算对运算对周期序列的基频是周期序列的基频是 是是 K

7、次谐波分量，谐波系数是次谐波分量，谐波系数是 谐波成分中只有谐波成分中只有N个是独立的个是独立的 ， 是周期的是周期的njNe)(2)(kXp)()()(22NknjnkjNNeenkjNe)(2)(kXp)(nxpnN0N2N)(kXp0NN2kN有限长序列是周期序列的一个周期有限长序列是周期序列的一个周期 有限长序列 x(n)只有的N个值x(n)可看成是周期序列的主值序列，记作 周期序列 当 叫做 的主值周期，记作 有限长序列的以N 为周期的周期延拓)(0) 10()()(otherNnnxnx)(0) 10()()(otherNnnxnxp1.2 , 1 , 0Nn1.2 , 1 , 0

8、Nn)(nxpNpnxnx)()()()()(nGnxnxNp)()()(nGnxnxNp的主值序列的主值序列 也是周期性的，相当于有限长也是周期性的，相当于有限长序列周期延拓序列周期延拓 当当 时，其主值序列时，其主值序列相当于一个有限长序列相当于一个有限长序列)(kXp10Nk)(kXpNpkXkX)()()()()(kGkXkXNp 和和 都取主值周期，得到离都取主值周期，得到离散傅立叶变换散傅立叶变换(DFT)对对1.2 , 1 , 0)(1)(1)(1.2 , 1 , 0)()()(10101010222NkWkXNekXNnxeWhereNnWnxenxkXnkNknkjNkjNn

9、nkNnknjNNN)(kX)(nxNjNeW2NjNeW22210)()(NnnkNNWnxnxDFT120120222)()()(NnnNNnnkNNkWnxWnxnxDFT周期为周期为N和周期为和周期为2N的不同的不同 当主值周期为0N-1时， 点的DFT为 当主值周期为02N-1时， 2N DFT（接下页） 212101012)(2102120222) 1(1 )()()()()()()(22kNkkNNNnnNNnnNNNnNnkNNnnkNNnnkNNNXWWnxWnxWNnxWnxWnxnxDFTkXkk小结小结 是是 的主值序列的主值序列 是严格按傅立叶分析的概念得来的是严格按

10、傅立叶分析的概念得来的 只是一种借用形式，一种算法只是一种借用形式，一种算法 用用 计算信号的频谱时，计算信号的频谱时， 采样频率必须大于两倍的信号最高截止频率采样频率必须大于两倍的信号最高截止频率 对周期信号要取一个整周期对周期信号要取一个整周期DFTDFSDFSDFTDFT)(nxpnN0N2N)(kXp02NN2NkN0N0nk)(nx)(kXDFSDFT25 FS FT DFS FT)(2)(1nFtfFTnn102)(1)(1NnknjppkNenxNkXNa221111).(1TTtjnndtetfTF)()()()(12)(2)(10LNkkXnkXNTnaTtfFTNnnpsn

11、ksntjnnpeFtx1)(knjNkkpNeanx210)(所以知道DFT=X(k)就可以求得离散周期信号的FT,也就可以找到其他三种的FT例#：已知N 的x(n)序列的 DFT如图所示，求下图x1，x2，x3, , x4的FTN0N0nk)(nx)(kX)(1nxxpn0N)(2txxpTNTs02NN)(kX02N)(2kXNkkN22N2N1TNTs02N2Nk)(12)(kXNkXTs)(30txx N0n)(nx02N2NkN)(kXsT1. . 线性线性若若 f1(k) F1(n) f2(k) F2(n)则则 a1f1(k)+a2 f2(k) a1F1(n)+a2F2(n).

12、. 对称性对称性若若 f(k) F(n)则则 F(k) N f(n)f(n)应是应是f(n)周期拓展之后反转周期拓展之后反转称称圆周反转圆周反转。9.4离散傅立叶变换的性质离散傅立叶变换的性质3. 时移特性圆周位移（循环位移）圆周位移（循环位移）： 将有限长序列将有限长序列f(k)周期拓展成周期序列周期拓展成周期序列fN(k)，再右移再右移m位，得到时移序列位，得到时移序列fN(k m)，最后取其主，最后取其主值而得到的序列称为值而得到的序列称为f(k)的的圆周位移圆周位移序列，记为序列，记为 f (k m)NGN(k)时移特性时移特性若若 f(k) F(n)则则 f (k m)NGN(k)

13、WmnF(n) DFT时移特性证明时移特性证明DFT f (k m)NGN(k)=DFT fN (k m)GN(k) 102je)(NkknNNmkf令令i=k- -m，有，有DFT f (k m)NGN(k)=mnNmNmiinNNif2j12jee)(由于由于fN (k )和和 都是以都是以N为周期的函数，因此为周期的函数，因此inN2je)(e)(e)(102j12jnFififNiinNNmNmiinNN故故DFTf (k m)NGN(k)= WmnF(n) 4. 频移特性（调制）频移特性（调制）若若 f(k) F(n)则则 Wl kf (k) F(n l)NGN(n) 5. 时域循环

14、卷积（圆卷积）定理时域循环卷积（圆卷积）定理 线卷积：线卷积：有限长序列有限长序列f1(k)和和f2(k)的长度分别为的长度分别为N和和M，则两，则两序列的卷积和序列的卷积和f(k)(称为称为线卷积线卷积)仍为有限长序列序仍为有限长序列序列，长度为列，长度为N+M 1。 循环卷积：循环卷积：有限长序列有限长序列f1(k)和和f2(k)的长度相等，均为的长度相等，均为N，则，则f1(k)与与f2(k)的的循环卷积循环卷积定义为定义为1012102121)()()()()()(NmNNmNmkfmfmkfmfkfkf循环卷积结果的长度仍为循环卷积结果的长度仍为N。若两序列长度不等，采。若两序列长度

15、不等，采用用补零法补零法。循环卷积循环卷积例例 求图求图 (a)和和(b)所示所示f1(k)与与f2(k)的循环卷积的循环卷积f(k)。解解 将将f1(k)补一个零点，补一个零点，使使f1(k)与与f2(k)的长度均的长度均为为5。 )()()()(540521kGmkfmfkfm)0()()()0(540521Gmfmffmf(0)= f1(0) f2(0) + f1(1) f2(1) + f1(2) f2(2) + f1(3) f2(3) + f1(4) f2(4) =0+4+3+2+0=9) 1 ()1()() 1 (540521Gmfmffmf(1)= f1(0) f2(1) + f1

16、(1) f2(0) + f1(2) f2(1) + f1(3) f2(2) + f1(4) f2(3) =1+0+4+3+0=8借助循环卷积计算线卷积循环卷积便于利用数字计算机进行计算。循环卷积便于利用数字计算机进行计算。为借助循环卷积求线卷积，要使循环卷积的结果与线为借助循环卷积求线卷积，要使循环卷积的结果与线卷积结果相同，可以采用补零的方法，使卷积结果相同，可以采用补零的方法，使 f1(k)与与f2(k)的长度均为的长度均为LN+M1 则循环卷积与线卷积的结果相同。则循环卷积与线卷积的结果相同。时域循环卷积定理时域循环卷积定理若若 f1(k) F1(n) f2(k) F2(n)则则 f1(

17、k) * * f2(k) F1(n)F2(n)6. 频域循环卷积定理频域循环卷积定理若若 f1(k) F1(n) f2(k) F2(n)则则 f1(k) f2(k) F1(n) *F2(n)N17. 巴塞瓦尔定理巴塞瓦尔定理若若 f(k) F(n)则则210210| )(|1| )(|nFNkfNnNk表明，在一个频域带限之内，功率谱之和与信号的能表明，在一个频域带限之内，功率谱之和与信号的能量成比例。量成比例。 若x(n)是一个有限长序列，长度为N，对x(n)进行Z变换 10)()(NnnznxzX比较Z变换与DFT，我们看到，当z=W-kN时 )()()(10nxDFTWnxzXNnnkN

18、WzkN即 kNWzzXkX)()(（1） 9.5 离散傅里叶变换与离散傅里叶变换与z变换的关系变换的关系 表明 是Z平面单位圆上幅角为 的点，也即将Z平面单位圆N等分后的第k点，所以X(k)也就是对X(z)在Z平面单位圆上N点等间隔采样值，如图所示。kNjkNeWz2kNWkN2lDFT的运算量次）（复数加：，次复数乘：22101)1, 1 , 0()()()(NNNNNkWnxnxDFTkXNnnkNl减少DFT运算量的方法将长度N变短。例如若将长度变为N/2，则运算量变成：利用 的性质周期性：周期性： 共轭对称性：共轭对称性： 可约性：可约性：次复数加：，次复数乘：4/4/22NNnkN

19、W)(rNnNnNWW*)(nNnNWWnNrnrNWW9.6快速傅里叶变换（快速傅里叶变换（FFT）DFT的快速算法（FFT）综述lFFT的算法分类FFT算法首先由Cooly-Tuky提出了基2FFT算法，它对DFT的发展起到了极大推进作用。随后又出现了混合基算法。本节仅对基2FFT算法作介绍，内容包括：FFT的基本思想、时域与频域抽取的基2FFT算法及其程序实现。l基-2 FFT算法（DIT-FFT）指要求长度N满足 （M为整数），若不满足可将序列补零延长，使其满足长度要求。MN2l时域抽取与频域抽取），简称算法（按频域抽取），简称算法（按时域抽取FFT-DIFFreqency-In-De

20、cimationFFT-DITTime -In- DecimationFFTFFT时域抽取基2FFT算法（DIT-FFT） 算法的推导时域抽取算法是按 的奇偶把时间序列 分解为两个长为N/2点的序列，即：)(nxn)2()(1rxrx12/,.,1 ,0Nr) 12()(2rxrx10)()(NnknNWnxkX则12/02212/02112/0)12(12/02)()()12()2(NrkNkrNNrkrNNrrkNNrkrNWWrxWrxWrxWrxkrNkrNjKrNjkrNWeeW2/2/222212/,.,1 , 0)()()()()(2112/02/212/02/1NkkXWkXW

21、rxWWrxkXkNNrkrNkNNrkrN上式中 分别为 的N/2点DFT，即：X kXk12( )( )和x nx n12( )( )和12/02/11)()(NnknNWnxkX12,.,1 ,0Nk12/02/22)()(NnknNWnxkX12,.,1 ,0Nk这是 前N/2点DFT) 12/,.1 , 0)(NkkX时域抽取基2FFT算法（DIT-FFT）) 1, 2/)(NNkkXkNNkNWW2/)()()2(21kXWkXNkXkN12,.,1 , 0Nk显然，可采用蝶式运算图来表示上述前N/2和后N/2两式 ，如下图所示：时域抽取基2FFT算法（DIT-FFT）时域抽取基2

22、FFT算法（DIT-FFT）例如N=8时的DFT,可以分解为两个N/2=4点DFT, 如下图：时域抽取基2FFT算法（DIT-FFT）同理： , N/2仍可能是偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。MN2)12()()2()(1413lxlxlxlx)14/( , 1 ,0Nl14/0)12(2/114/022/11) 12()2()(NllkNNlklNWlxWlxkX14/04/42/14/04/3)()(NlklNkNNlklNWlxWWlx)()(42/3kXWkXkN14/, 1 , 0Nk)()()4(42/31kXWkXNkXkN故时域抽取基

23、2FFT算法（DIT-FFT）14/04/44414/04/333)()()()()()(NlklNNlklNWlxlxDFTkXWlxlxDFTkX其中对 也可进行同样的分解：X k2( )()()(62/52kXWkXkXkN)()()4/(62/52kXWkXNkXkN14/, 1 , 0Nk14/04/555)()()(NlklNWlxlxDFTkXklNNlWlxlxDFTkX4/614/066)()()()2()(25lxlx) 14/(,.,1 , 0) 12()(26Nllxlx时域抽取基2FFT算法（DIT-FFT）依次类推：经过M-1次分解后，可将N点DFT分解成N/2个两

24、点DFT。这样又一次的分解得到4个N/4点DFT，见下图。典 型 例 题例： 试画出N=8时的完整的基-2 DIT-FFT运算流图。 运算量时域抽取基时域抽取基2FFT算法（算法（DIT-FFT）由有关算法的讨论知：当 时，总共应有M级分解，每级有N/2个“蝶式运算”。每个“蝶式运算”需一次复数乘、两次复数加运算，这样M级总共需要的运算量为：MN2NNMN2log22复数乘运算次数NNMN2log复数加运算次数如：若N1024，直接计算DFT与采用FFT运算量之比约为205，“快速”得以充分体现。若N足够大，通过直接计算DFT与采用FFT计算其运算量之比为：NNNNNNNNNN22322222

25、log2loglog) 1(NNN22log)2/( FFT算法的特点时域抽取基时域抽取基2FFT算法（算法（DIT-FFT） 倒码倒码即码位倒置：是指将原二进制数的码位倒过来 按从低位到高位排列。 顺序顺序 二进制数二进制数 倒码倒码 倒码顺序倒码顺序 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 000 100 010 110 001 101 011 000 0 4 2 6 1 5 3 7如：N=8时，序号 “4” 用三位二进制表示正常码为“100”，而其倒码为 “001” ，变成了序号 “1” 。时域抽取基2FFT算法（DIT-FFT）由

26、完整的FFT流图可见：从左到右计算下一级蝶式运算时，仅需要用到本级的数据而不需要前一级的数据。例如在实施第二级蝶式运算时，仅需要第一级蝶式运算的结果，而不需要用到原来的输入数据 。据此就可在数据输入到存储器以后，每一级运算的结果存储在同一组存储单元中。直到最后输出，中间无需其他存储器。)(nx利用同一存储单元存放蝶式运算输入和输出数据的方法称为原位运算。原位运算可节省存储单元，降低FFT硬件实现的设备成本，从而使得FFT算法简单、快速、高效。 DIT-FFT算法其他形式的流图由信号流图理论知道：只要保证各节点所连接的支路及其传输系数不变，无论各节点相对位置如何排列，所得到的流图等效，DFT的结

27、果相同。时域抽取基2FFT算法（DIT-FFT）N=8 时输入是正序、输出是倒码的DIT-FFT运算流图例如将N=8时基2DIT-FFT信号流图中与 、 水平相连的所有节点分别同与 、 水平相连的所有节点对调，保持其余节点位置不变，得到新形式的信号流图。)4( x) 1 ( x)6( x) 3( x频域抽取基2FFT算法（DIF-FFT） 算法的推导频域抽取算法是把时间序列 前后对半分解为两个长为N/2点的序列，则：)(nx12/02/12/0)2/(12/012/12/010)2/()()2/()()()()()()(NnnkNNkNNnkNnNNnnkNNNnnkNNnnkNNnnkNWN

28、nxWnxWNnxWnxWnxWnxWnxnxDFTkX频域抽取基2FFT算法（DIF-FFT）12/02/212/0)2/()()2/()()2(NnrnNrnNNnWNnxnxWNnxnxrX当 k 取偶数时（ k = 2 r，r = 0 , 1 , . , N / 2 1）为奇数为偶数kkWkkNN11)1(2/)(kX)(nx当 k 取奇数时（ k = 2 r1，r = 0 , 1 , . , N / 2 1）nNNnrnNnrNNnWWNnxnxWNnxnxrX12/02/)12(12/0)2/()()2/()()12()2/()()(1Nnxnxnx令nNWNnxnxnx)2/()

29、()(212/02/1)()2(NnrnNWnxrX则12/02/2)() 12(NnrnNWnxrX这一结论表明：求 的N点DFT 再次分解成 求两个N/2 点DFT )(nx)(kX DIF-FFT的蝶式运算流图)(nx)2/(Nnx)2/()(NnxnxnNWNnxnx)2/()(1nNW DIF-FFT的一次分解运算流图频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）先蝶式运算，后 DFT。例如：N=8时频域抽取基频域抽取基2FFT算法（算法（DIF-FFT） DIF-FFT的二次分解运算流图通常 N/2 仍然为 2 的整数幂，继续将 N/2 点DFT分成偶数组和奇数组，这样每

30、个 N/2 点DFT又可分解成两个 N/4 点DFT，其输入序列分别是 和 按上下对半分开后通过蝶式运算构成的 4 个子序列，如下图所示：)(1nx)(2nx频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）按照以上方法继续分解下去，经过 M - 1 次分解，最后分解为 N/2 个两点DFT，这 N/2 个2点DFT的输出就是 N 点DFT的结果X(k) ，如下图所示： 有关说明频域抽取基频域抽取基2FFT算法（算法（DIF-FFT）以上给出了 N=8 时完整的 DIF - FFT 的运算流图。由于这种方法是 按 在频域进行奇偶分解，因此称之为频域抽取基2 运算。比较与相同点：运算次数与

31、存储量相同；不同点： 输入序列为自然序列而输出为码位倒置序列 蝶式运算过程不同 是序列先乘旋转因子后相加减 是序列先相加减后乘旋转因子)(kX1. 线性卷积实际应用中一般以线性卷积和相关运算处理为依据，如一个FIR数字滤波器的输出等于输入与滤波器的单位取样响应的线性卷积。DFT计算循环卷积DFT的快速算法FFT的出现， 使DFT在数字通信、 语言信号处理、 图像处理、 功率谱估计、 仿真、 系统分析、 雷达理论、 光学、 医学、 地震以及数值分析等各个领域都得到广泛应用。 3. 信号频谱分析2. 快速相关（功率谱计算）9.7离散傅里叶变换的应用离散傅里叶变换的应用线性卷积 线性卷积不受主值区间

32、限制循环卷积 在一定条件下与线性卷积相等。两个长度都为N的因果序列的循环卷积仍是一个长度为N的序列，而它们的线性卷积却是一个长度为2N-1的序列。1、利用循环卷积计算线性卷积 如果能将线性卷积转化成循环卷积，那么根据DFT的循环卷积性质，就能够用循环卷积来计算线性卷积，而循环卷积可以用FFT 进行快速计算。因此，首先需要讨论在什么条件下，循环卷积与线性 卷积相等的问题。 设h(n)和x(n)分别是长度为N和M的有限长序列，它们的线性卷积和循环卷积分别为 1010NlmLcLLmynh nx nh m x nmynh nx nh m xnmRn其中，L=maxN,M所以对照线性卷积的公式，可以看

33、出因 为 Lqxnx nqL 1010NcLmqNLqmynh mx nmqL Rnh m x nqLm Rn 10Nlmh m x nqLmynqL yc(n)是yl(n)以L为周期的周期延拓序列的主值序列。而yl(n)是个长度为N+M-1的序列，所以(1)如果L 2fc2) 谱分辨率F=Fs/N, 若N不变，要提高频谱分辨率，必须降低Fs 若Fs不变，为提高频谱分辨率，可增加采样点数N，即增加观察时间Tp。21cpfNFTF选取原则：（一）（一） 一维离散一维离散Walsh变换变换(WT)1. 定义正变换:1-N,0,1,u , ),()(1)(10,NxHWxuWxfNuF反变换:1-N

34、,0,1, , ),()()(10,xNuHWxuWuFxf)()(uFxfWT注意: Walsh正、反变换的变换核都一样！9.8沃尔什沃尔什(Walsh)变换及其应用实例变换及其应用实例2.一维离散Walsh变换的矩阵算法正变换:1-N,0,1,u , ),()(1)(10NxWxuWxfNuF)1, 1 ()1()1 , 1 ()1 ()0 , 1 ()0(1)1 (NWNfWfWfNF) 1, 1() 1() 1 , 1() 1 ()0 , 1()0(1) 1(NNWNfNWfNWfNNF)1,0()1()1 ,0()1 ()0 ,0()0(1)0(NWNfWfWfNF展开：令：) 1(

35、) 1 () 0 (NFFFF) 1() 1 () 0 (NffffNNNNWNWNWNWWWNWWWW) 1, 1() 1 , 1() 0 , 1() 1, 1 () 1 , 1 () 0 , 1 () 1, 0 () 1 , 0 () 0 , 0 (IWT：WFf WT：WfNF1(1/N可以忽略不写)注意: （1）正反变换的变换矩阵W都一样； （2）W代表Walsh序的Walsh矩阵。注意: 当变换矩阵为Hadamard矩阵HN时,称为Hadamard序的 Walsh变换。变换矩阵如下写法：IWHT：HFf WHT：HfNF1(1/N可忽略不写)其中H为Hadamaed序的Walsh矩阵

36、。IWT：WFf WT：WfNF1举例:Txf2813)(求Walsh序的一维离散Walsh变换F(u).反变换：2813215 . 15 . 31111111111111111)(4FWxf215 . 15 . 3281311111111111111114141)(4fWuF正变换：Walsh序的Walsh变换：举例:Txf2813)(求Walsh序的一维离散Walsh变换F(u)。用WHT。用WHT：15 . 125 . 3281311111111111111114141)(4fHuFH215 . 15 . 3281311111111111111114141)(4fWuF用WT：结果为Wa

37、lsh序结果为Hadamard序对应关系W序 H序0 01 22 33 1IWT：HFf WHT：HfNFH1Hadamard序的Walsh变换：3.Walsh序和Hadamard序的相互转换变换结果为Hadamard序的，要转换为Walsh序可以推导出以下转换方法（N=4）：二进制码格雷码倒序码 00 00 00 01 01 10 10 11 11 11 10 01（W序） （H序）对应关系W序 H序0 01 22 33 1N=8时的转换方法：二进制码 格雷码倒序码 000 000 000 001 001 100 010 011 110 011 010 010 100 110 011 101

38、 111 111 110 101 101 111 100 001（W序） （H序）对应关系W序 H序0 01 42 63 24 35 76 57 14.一维Walsh变换的物理意义正如一维傅立叶变换（连续）是将一个函数分解成无穷个正弦波的叠加，而傅立叶幅度谱是这些正弦波的幅度系数。一维Walsh变换（连续）是将一个函数分解成无穷个Walsh函数（方波）的叠加，而F(u)是这些Walsh函数的幅度系数.215 . 15 . 3)(2813)(uFxfWTT), 3(2), 2(), 1 (5 . 1), 0(5 . 3)(tWtWtWtWxfWWWW215 . 15 . 3)(2813)(uFx

39、fWTT), 3(2), 2(), 1 (5 . 1), 0(5 . 3)(tWtWtWtWxfWWWW), 0(tW), 1 ( tW), 2(tW), 3( tW0 12 3t), 0(5 . 3tW), 1 (5 . 1tW), 2(tW), 3(2tW0 12 3t)(xf3182（二（二) 二维离散二维离散Walsh变换变换1. 定义:正变换:1, 1 , 0,),(),(),(1),(1010NvuyvWxuWyxfNvuFNxNy反变换:1, 1 , 0,),(),(),(1),(1010NyxyvWxuWvuFNyxfNuNv注意：正变换和反变换的变换核都一样。2. 矩阵算法:

40、WT：WfWNF1WFWNf1其中：W为Walsh矩阵WHT：HfHNFH1HHFNfH1其中：H为Hadamard矩阵3. 矩阵算法举例: , 0000011001100000),(），（求vuWyxfWT：WfWNF1000001010000010111111111111111110000011001100000111111111111111141),(vuF正变换：反变换：000001100110000011111111111111110000010100000101111111111111111141),(yxf3. 矩阵算法举例:用WHT：HfHNFH1100100000000100

41、111111111111111110000011001100000111111111111111141),(vuFH正变换：0000010100000101),(vuF结果是Hadamard序，必须再转换为Walsh序。0000100100001001行序号变0000010100000101列序号变4. 实际图像变换举例:WT移中FTWT将能量集中于频率平面的左上角移中FT将能量集中于频率平面的中央3.2.7二维离散二维离散Walsh变换的应用变换的应用用于图像数据压缩用于图像数据压缩),(yxfWT),(vuF截取图像的左上角保存),(vuF),(vuF补0),(yxf经反变换，恢复原图像3.2.7二维离散二维离散Walsh变换的应