[信息与通信]多维信号处理第二章ppt课件

1、多维数字信号处置主讲：陈绵书第二章 多维信号的离散傅里叶分析 研讨内容 研讨多维离散傅里叶变换DFT，调查其与傅里叶变换之间的关系； 研讨计算有限区域序列的离散傅里叶变换的几个FFT算法。 多维DFT的两个要点 是有限区域序列的一种准确的傅里叶表示，也是多维周期序列的傅里叶级数展开； 变换存在潜在的周期性，可以开发有效算法。2.1 矩形周期序列的离散傅里叶级数表示 矩形周期序列 满足条件其中 和 是正整数。满足上式最小的 和 称为序列的程度周期和垂直周期。 根本周期12112122,x n nx nN nx n nN1N2N1N2N12,121122,:01,01N NRn nnNnN2.1

2、矩形表示续1 二维离散傅里叶级数展开 复正弦 是矩形周期的，程度周期为 垂直周期为 为傅里叶级数系数12121112121 122001212122,expNNkkx n nX k kjn kjn kN NNN 1 1221222expjn kjn kNN12121112121 122001222,expNNnnX k kx n njn kjn kNN 1N2N12,X k k2.1 矩形表示续2 周期序列的傅里叶级数与傅里叶变换的不同 周期序列没有傅里叶变换，不是绝对可和； 傅里叶级数系数公式上下限有限，且频率是整数； 离散傅里叶级数是可计算的变换。2.1 矩形表示续3例有周期序列， ， ，

3、 ， ， ，确定离散傅里叶级数的系数。解15N 24N 1212,x n nn n104n203n124312121 1220022,exp54nnX k kn njn kjn k121, ,k k对全部1243121 12200122,exp2054kkx n njn kjn k2.2 多维离散傅里叶变换 定义 有限区域序列生成周期序列 有限区域序列 ，支撑区为 ，那么可以生成周期序列 同时有 将周期序列 看成有限区域傅里叶级数系数序列 的周期延拓12,x n n12N NR12111222,x n nx nrN nr N12121212,0, N Nx n nn nRx n n其他12,X

4、 k k12,X k k1212111222,rrX k kX krN kr N2.2 多维离散傅里叶变换续1同时有 和 可以经过下式计算12112212,01,01,0, X k kkNkNX k k其他21,nnx21,kkX21212121,kkXkkXnnxnnx2.2 多维离散傅里叶变换续2 离散傅里叶正变换 离散傅里叶逆变换10102221112121112222exp,NnNnknNjknNjnnxkkX10 , 102211NkNk1010222111212121112222exp,1,NkNkknNjknNjkkXNNnnx10 , 102211NnNn2.2 多维离散傅里叶

5、变换续3 傅里叶变换和离散傅里叶变换的关系 抽样定理 空域抽样可以表示频域限带信号，假设频域非限带，那么空域抽样的频谱会呵斥混叠； 频域抽样可以表示空域限制信号，假设空域非限制，那么频域抽样的时域信号会呵斥混叠；1010221121211122exp,NnNnnjnjnnxX222111/2,/22121|,NkNkXkkX 1222211121,rrNrnNrnxnnx2.2 多维离散傅里叶变换续4 M维离散傅里叶变换 定义M维序列，其支撑区为 令对角矩阵 那么M维DFT为MiNnRii, 2 , 1, 10: nNMNNN0021N NnnNknkRjxX12exp NknNkkNnRjX

6、x12expdet12.2 多维离散傅里叶变换续5例计算以下 点阵的三维DFT解 可以表示为令那么321NNN其他, 01, 0, 10, 1,3211321nnNnnnnx321,nnnx NRnnnnnnnnx32132321,1,NjWN/2exp101010323211122333332221111,NnNnNnknNknNknNWWWnnkkkX2.2 多维离散傅里叶变换续6 10102321112222211133,NnNnknNknNkNWWnWkkkX101111133NnknNkNWW其他 , 0, 0,3211132133NkNRkkkkWNkkkX00, 01111011

7、111kNkWNnknN2.2 多维离散傅里叶变换续7例计算 点阵的二维离散傅里叶反变换其中，解21NN 其他, 010 , 10, 1,221121MkMkkkX2211,MNMN 1010212111222221111,MkMkknNknNWWNNnnx101021112222211111MkMkknNknNWNWN2.2 多维离散傅里叶变换续8222221111111111121nNMnNnNMnNWWNWWN22211121212expNMnNMnj221121222111/sin/sin/sin/sinNnNnNNNMnNMn2.2 多维离散傅里叶变换续9 离散傅里叶变换的性质 线性

8、 假设 与 是恣意有限区域序列，且 和 是恣意复常数，那么 支撑区确实定假设 的支撑区为 ， 的支撑区为 ，令 ，211,nnx212,nnxab212211212211,kkbXkkaXnnbxnnax1x21MMR2x21NNR111,maxNMP 222,maxNMP 2.2 多维离散傅里叶变换续10定义两个区域已增大的序列为序列 和 的支撑区为 ，且212121212121211211, , 0 ,MMPPMMRnnRnnRnnnnxnnx212121212121212212, , 0 ,NNPPNNRnnRnnRnnnnxnnx1x2x21PPR2121bxaxxbxa2.2 多维离

9、散傅里叶变换续11 循环移位假设一个有限区域序列循环移位，那么DFT要乘上一个复指数思索周期序列 ，程度周期 ，垂直周期 ，离散傅里叶级数系数 。令 是 的移位序列那么 和 的离散傅里叶级数系数的关系为21,nnx1N2N12,X k kyxxy221121,mnmnxnny2121,222111kkXWWkkYkmNkmN2.2 多维离散傅里叶变换续12那么定义 的循环移位序列为即其中 表示整变量 对 取模运算。循环移位：从支撑区左边或顶部移出的抽样值，又重新出如今右边或底部。21,nnx其他 , 0,21212121NNRnnnnynny212121221121,NNNNRnnmnmnxn

10、ny NnnN2.2 多维离散傅里叶变换续13DFT 定义为循环移位离散傅里叶变换对为2121,kkYkkY21,222111kkXWWkmNkmN21,222111kkXWWkmNkmN2121,NNRkk212211,22211121kkXWWmnmnxkmNkmNNN21,kkY2.2 多维离散傅里叶变换续14 实 的对称性假设 是实的，那么有其中 表示复共轭运算。由于所以 是Hermitian对称的21,nnx21,nnx1010*2121*1122222111,NnNnknNknNWWnnxkkX*kNnNnkNnkNWWW*10102121*112222221111,NnNnkNn

11、NkNnNWWnnxkkX212211,NNkNkNX2.2 多维离散傅里叶变换续15对于复有限区域序列，定义Hermitian对称分量和反对称分量由于那么可得21221121,Re,ReNNkNkNXkkX21221121,Im,ImNNkNkNXkkX212211*2121,21,NNsnNnNxnnxnnx212211*2121,21,NNanNnNxnnxnnx21*2211*,21kkXnNnNxNN2121*2121,Re,21,kkXkkXkkXnnxs2121*2121,Im,21,kkXjkkXkkXnnxa2.2 多维离散傅里叶变换续16 反射性假设那么 Parseval定

12、理2121,kkXnnx1212,kkXnnx211211,11kkNXnnNxNN22221221,NNkNkXnNnx212122112211,NNNNkNkNXnNnNx101021*2121101021*2111221122,1,NkNkNnNnkkYkkXNNnnynnx2.2 多维离散傅里叶变换续17 对偶性假设那么证明 调制性10102121211122222111,1,NnNnknNknNWWkkXNNnnx2121,kkXnnx21*2121*,kkxNNnnX21222111221121,NNlnNlnNlklkXnnxWW101021*21*211122222111,Nn

13、NnknNknNWWkkXnnxNN2.2 多维离散傅里叶变换续18 循环卷积 定义 有两个有限区域序列 和 ，支撑区是 序列满足 令 是 点DFT，表示为 问题是如何确定21,nnx21,nnh21NNR2121,kkXnnx2121,kkHnnh 212121,kkXkkHkkY21,nny21,kkY21NN 2.2 多维离散傅里叶变换续19讨论：思索一切序列的周期延拓由于离散傅里叶级数反变换得由于所以 1010212121211122222111,1,NkNkknNknNWWkkXkkHNNnny121 12 2121211121200,NNm km kNNmmX k kx m m W

14、W 10102121101021211122222211111122,1,NkNkkmnNkmnNNmNmWWkkHNNmmxnny 2211101021,1122mnmnhmmxNmNm 212121,kkXkkHkkY2.2 多维离散傅里叶变换续20由于所以称 是 与 的循环卷积另一种方式二维循环卷积运算符其他 , 0,21212121NNRnnnnynny 10102122112111222121,NmNmNNNNRnnmnmnhmmx 1010221121211122,NmNmmnmnhmmxnnyyhx 2121,*kkXkkHhxxhy101022112121112221,NmNm

15、NNmnmnxmmhnny*2.2 多维离散傅里叶变换续21 循环卷积推导线性卷积令 支撑区为 ， 支撑区为 ， 为二者卷积那么其支撑区为假设取那么循环卷积 为21,nnx21PPR21,nnh21QQR21,nnw 1222112121,mmmnmnxmmhnnw20111QPn20222QPn111,maxQPN 222,maxQPN xhy* 21112221101022112121,NNQmQmRnnmnmnxmmhnny2.2 多维离散傅里叶变换续22 的周期延拓为所以那么方括号中是线性卷积，可以用 表示，所以令那么21,nnx1222211121,rrNrnNrnxnnx12222

16、211112211,rrNrmnNrmnxmnmnx 1211221010222211112121,rrQmQmNrmnNrmnxmmhnny2121,NNRnn21,nnw 21122122211121,NNrrRnnNrnNrnwnny1111QPN1222QPN 21212121,NNRnnnnwnny2.2 多维离散傅里叶变换续23利用DFT计算线性卷积步骤：1选择 和 ，满足2把 添加足够的零值抽样，以便填满 区域3用类似的方法添加 的零值抽样点4计算 及 的 点DFT5计算乘积6计算 的 点反DFT1N2N21,nnh21NNR21,nnx21NN 2121,kkXkkH 2121

17、,kkXkkH21NN 21,nnx21,nnh1111QPN1222QPN2.2 多维离散傅里叶变换续24例令 ， ， 表示列的标号， 表示行的标号， 在左下角。解循环卷积1201,21nnx1101,21nnh0 , 01n2n 1 , 11 , 00 , 10 , 01 , 1xxxxX 1 , 11 , 00 , 10 , 01 , 0 xxxxX 1 , 11 , 00 , 10 , 00 , 1xxxxX 1 , 11 , 00 , 10 , 00 , 0 xxxxX2.2 多维离散傅里叶变换续25代入 和 ，得线性卷积21,nnx21,nnh2402,21kkX1311,21kk

18、H 21202,2121kkXkkH3423,21nny0012000100000000,21nnx0011000100000000,21nnh2.2 多维离散傅里叶变换续26jjjjjjjjjjkkX323421223101222123,21jjjjjjjjjjjkkH2123121212112,21 jjjjjjjjjjkkXkkH55255122162551012621255,21210132002300010000,21nnw3423,21nny2.3 离散傅里叶变换的计算 直接计算 算式其中 复杂度每个抽样需求 次复乘数和几乎一样的复加数总的需求 次复乘数和复加数M维情况下，需求 次

19、复乘数和复加数101021211122222111,NnNnknNknNWWnnxkkX1011Nk1022NkNjWN2exp21NN2221NN22221MNNN2.3 离散傅里叶变换的计算续1 行-列分解法 算式 复杂度每个抽样需求 的复乘数和复加数总的需求 的复乘数和复加数111112222210102121,knNNnNnknNWWnnxkkX 10212122222,NnknNWnnxknG11111102121,knNNnWknGkkX21NN 2121NNNN2.3 离散傅里叶变换的计算续2 M情况 算式分解出其中最后一维 复杂度每个抽样需求 的复乘数和复加数，总的需求 的复乘

20、数和复加数11111111111010102121,knNNnknNNnNnknNMMWWWnnnxkkkXMMMMMMMMMM MMNNNN121MMMNNNNNNN121212.3 离散傅里叶变换的计算续3 算式分解出最后二维 复杂度每个抽样需求 的复乘数和复加数，总的需求 的复乘数和复加数111112222211111101010102121,knNNnknNNnknNNnNnknNMMWWWWnnnxkkkXMMMMMMMMMMMMMMM MMMNNNNN1221MMMMNNNNNNNN1221212.3 离散傅里叶变换的计算续4 算式分解M维 复杂度每个抽样需求 的复乘数和复加数，总

21、的需求 的复乘数和复加数111112222211111101010102121,knNNnknNNnknNNnNnknNMMWWWWnnnxkkkXMMMMMMMMMM MNNN21MMNNNNNN21212.3 离散傅里叶变换的计算续5 算法复杂度对比 实际复乘数 点的二维DFT的复乘数22221MdirectNNNCMMdirectcrNNNNNNC2121 /2log21221 /MMFFTcrNNNNNNC复乘1240102directC复乘931 /1022directcrC复乘720 /10210FFTcrC102410242.3 离散傅里叶变换的计算续6 矢量快速傅里叶变换 原理

22、：将一个二维DFT延续地分成更小的二维DFT，直到分为只需计算无足轻重的二维DFT时为止。 方法：分解成四个和式，一个是 为偶数 为偶数，一个是 为偶数 为奇数，一个是 为奇数 为偶数，一个是 为奇数 为奇数。1n2n1n1n1n2n2n2n2.3 离散傅里叶变换的计算续7 例如： 其中 12/012/0222121001222112 ,2,NmNmkmkmNWmmxkkS 12/012/02221211112221112 , 12,NmNmkmkmNWmmxkkS 12/012/02221210112221112 ,2,NmNmkmkmNWmmxkkS 12/012/0222121101222112 , 12,NmNmkmkmNWmmxkkS10102121122211,NnNnknNknNWWnnxkkX21122111211021012100,kkNkNkNWkkSWkkSWkkSkkS2.3 离散傅里叶变换的计算续8 的周期性程度周期为 ，垂直周期为11100100,SSSS 12/012/0222121001222112 ,2,NmNmkmkmNWmmxkkS 12/012/022