1、Chap 5 Finite-Length Discrete Transforms 1 1 The Discrete Fourier Transform Relation Between DTFT and DFT Operation on Finite-Length Sequences Classification of Finite-Length Sequences DFT Symmetry Relation Discrete Fourier Transform Theorems Computation of the DFT of Real Sequence Linear Convolutio
2、n Using the DFT2 21.Definition10 ,01(5.1)NnX kx nk nkN-analysis equation10 ,01(5.2)Nkx nX kk nnN-synthesis equation,k n-basis sequence,Length-N5.1 Orthogonal Transforms3 3Condition:101,1,(5.3)0,Nnlkk nl nlkN2.Parsevals relation1122001 (5.6)NNnkx nX kN5.2 The Discrete Fourier Transform Time domain Fr
3、equency domainContinue aperiodic FT Aperiodic continueContinue periodic FS Aperiodic discreteDiscrete aperiodic DTFT Periodic continueDiscrete periodic DFS Periodic discrete 4 41.Review The engineering signals are often continuous and aperiodic.If we want to process the signals with DFT,we have to m
4、ake the signals discrete and periodic.5 52.Make a signal discrete and periodic1)Sampling to make the signal discrete2)Make the signal periodic:a)If xn is a limited length N-point sequence,see it as one period of a periodic signal that means extend it to a periodicb)If xn is an infinite length sequen
5、ce,cut-off its tail to make a N-point sequence,then do the periodic extending.The tail cutting-off will introduce distortion.We must develop truncation algorithm to reduce the error,which is windowing.6 62.Make a signal discrete and periodicx(t)xnTX(j)FTDFSX(j)DTFTP(t)Tsq(t)TP(j)0 0=2/TsQ(j)00=2/T5.
6、2.1 Definition7 71.Definition)7.5(10,10/2NkenxkXNnNknj-discrete Fourier transform2/,(5.8)jkn Nk nebasis sequence-complex exponential sequenceSuppose:xn,Xk-finite-length sequence,N-length;i.e.,xn=0 when nN-15.2.1 Definition8 8basis sequence has the orthogonality propertyNknje/2Proof:10/)(2/210/211NnN
7、nlkjNnljNnNknjeNeeN2()/2()(1)/1(1)jklNjklNNeeNL2()2()/1(111)11101NjkljklNklrNNeklNeL14444 42 4444 4 35.2.1 Definition1)Xk is also a length-N sequence in the frequency domain2)Xk is called the discrete Fourier transform (DFT)of the sequence xn3)Using the notation WN=e-j2 /N the DFT is usually express
8、ed as:9 9)13.5(10,10NkWnxkXNnnkN2.Note5.2.1 Definition1)The inverse discrete Fourier transform(IDFT)is given by10103.IDFT101 ,01(5.14)NknNkx nX k WnNN2)To verify the above expression,we multiply both sides of the above equation by WNln and sum the result from n=0 to n=N-15.2.1 Definition resulting i
9、n11111110001 NNNlnknlnNNNnnkx n WX k WWN11()001 NNk l nNnkX k WN11()001 NNk l nNknX kWN5.2.1 Definition 1212 Making use of the identity 1()0,integer0 Nk l nNnNklrNWr is anotherwise 111()0001 NNNlnk l nNNnknx n WX kWX lNHence5.2.1 Definition13131)Consider the length-N sequence11001Nnn,nx10010NNnknNWx
10、WnxkX10NkIts N-point DFT is given by4.Example5.2.1 Definition14142)Consider the length-N sequenceIts N-point DFT is given by4.Exampleny111001Nnmmnmn,kmNkmNNnknNWWmyWnykY1010Nk5.2.1 Definition15153)Consider the length-N sequence defined for 0 n N-14.Example cos(2/),01x nnr NrNUsing a trigonometric id
11、entity we can write2/2/1 2jnr Njnr Nx nee12nrnrNNWW5.2.1 DefinitionThe N-point DFT of xn is thus given by16164.Example10 NknNnX kx n W,2110)(10)(NnnkrNNnnkrNWWMaking use of the identity10NnnkNW)(,0N,rNkforotherwiser an integer5.2.1 Definition11()()001 2NNr k nr k nNNnnX kWW17174.Example/2/2-0Nfor kr
12、Nfor kN rotherwise10Nk5.2.2 Matrix Relations1818whereThe DFT samples defined by:)13.5(10,10NkWnxkXNnnkN can be expressed in matrix forms as:(5.25)NXD x011(5.26)TXXXXN011(5.27)Txxxx N5.2.2 Matrix Relations1919DN is the NN DFT matrix given by2121242(1)12(1)(1)11111111NNNNNNNNNNNNNNNWWWWWWDWWW5.2.2 Mat
13、rix Relations2020Likewise,the IDFT can be expressed in matrix forms as:10011(5.29)11NxXxXDx NX N5.2.2 Matrix Relations2121212(1)242(1)1(1)2(1)(1)111111111NNNNNNNNNNNNNNNWWWWWWDNWWW is the NN IDFT matrix given by1NDNote11(5.31)NNDDN5.3 Relation between DTFT and DFT and their Inverses22225.3.1 Relatio
14、n with DTFT The Fourier transform of the length-N sequence xn.()jX e10()(5.34)Njj nj nnnX ex n ex n eBy uniformly sampling at N equally spaced frequencies)(jeX2/,01,02kk NkN12/2/0()01Njjkn Nk NnX ex n ekN23235.3.2 Numerical Computation of DTFT1010MnNNnnxnxe2/,kk MMN112/2/00()(5.38)kMNjjkn Mjkn Meenn
15、X ex n ex n eDefine a new sequence xenEq.(5.38)used function freqz can evaluate the frequency response of xn 24245.3.3 The DTFT from DFT by interpolation1110001()NNNjj nknj nNnnkX ex n eX k weN1.show112/0011(2/)001 1 NNjkn Nj nknNNjk N nknX keeNX keN25255.3.3 The DTFT from DFT by interpolation(2)1(2
16、/)(2/)011jNkNjkN njkNneee(2)/2(2)/22sin()22sin()2jNkjNkNNkeNkeN(2/)(1)/22sin()22sin()2jk NNNkeNkN26265.3.3 The DTFT from DFT by interpolation2/)1)(/2(10)22sin()22sin(1)(NNkjNkjeNkNkNkXNeX)2(1)(10NkkXNeXNkjwhere2/)1()2sin()2sin(1)(NjeNN2727 from Xk by interpolation)(jeX5.3.3 The DTFT from DFT by inte
17、rpolationResult11,00,1)(/2NllNlThe interpolating polynomial satisfies:2/(),01jl NX eX llN28285.3.4 Sampling the DTFT1.Consider a sequence xn with a DTFT)(jeX2.We sample at N equally spaced points developing the NFrequency samples)(jeX10,/2NkNkk)(kjeX3.These N frequency samples can be considered as a
18、n N-point DFT Yk whose N-point IDFT is a length-N sequence yn.29295.3.4 Sampling the DTFTNow)12.3()(nnjjenxeX)16.3()(21deeXnxnjjFrom Eq.(3.12)46.5()()(/2lklNNkjjWlxeXeXkYklNklnkNNkknNWNlxWkYNny10)(101130305.3.4 Sampling the DTFTMaking use of the above identity in Eq.(5.48),thenotherwisemNnlWNNknkN01
19、110)()49.5(10NnmNnxnymyn is obtained by adding infinite number of shifted replicas of xn.Each replica shifted by an integer multiple of N sampling instants31315.3.4 Sampling the DTFTTo apply)49.5(10NnmNnxnyma)If xn is length-M sequence with MN,thus yn=xn for 0 n N-1.b)If MN,there is a time-domain al
20、iasing of samples of xn in generating yn,and xn can not be recovered from yn.32325.3.4 Sampling the DTFTExample 5.6 543210nxGive 8 equally spaced points7088nnxnxnxny 00543210ny-xn can be recovered from ynGive 4 equally spaced points7044nnxnxnxny 3264ny-xn cant be recovered from yn5.4 Operation on Fi
21、nite-Length Sequences33335.4.1 Circular shift of a sequence1.Consider length-N sequences defined for 0nN-12.Sample values of such sequences are equal to zero for values of n 0(right circular shift),the above equation implies5.4.1 Circular shift of a sequence3636nx16nx56nx46nx26nx0 1 2 3 4 5n0 1 2 3
22、4 5n0 1 2 3 4 5n7.Illustration of the concept of a circular shift5.4.1 Circular shift of a sequence37378.As can be seen from the previous figure,a right circular shift by n0 is equivalent to a left circular shift by N-n0 sample periods9.A circular shift by an integer number greater than N is equival
23、ent to a circular shift by n0 N5.4.1 Circular shift of a sequence3838xn-1xnxNn=4=05.4.1 Circular shift of a sequence393910.circular time-reversal1100NNxnxNnx NnnNxn 11.Frequency domain coNX kXkk 5.4.1 Circular shift of a sequence5.4.2 Circular convolution40401.This operation is analogous to linear c
24、onvolution,but with a subtle difference2.Consider two length-N sequences,gn and hn,respectively3.Their linear convolution results in a length-(2N-1)sequence yLn given by22010NnmnhmgnyNmL,41414.In computing yLn we have assumed that both length-N sequences have been zero-padded to extend their lengths
25、 to 2N-15.The longer form of yLn results from the time-reversal of the sequence hn and its linear shift to the right 6.The first nonzero value of yLn is yL0=g0h0,the last nonzero value is yL2N-2=gN-1hN-15.4.2 Circular convolution42427.To develop a convolution-like operation resulting in a length-N s
26、equence yCn,we need to define a circular time-reversal,and then apply a circular time-shift8.Resulting operation,called a circular convolution,is defined by10,10NnmnhmgnyNmNC5.4.2 Circular convolution4343Nyn=gn hn9.Since the operation defined involves two length-N sequences,it is often referred to a
27、s an N-point circular convolution,denoted as 10.The circular convolution is commutative,i.e.NN gn hn=hn gn5.4.2 Circular convolution4444001101102111201CCCyhh NhgyhhhgyNh Nh Nhg NLLMLLLML-circulant matrix5.4.2 Circular convolution4545Example 5.7-Determine the 4-point circular convolution of the two l
28、ength-4 sequences:1201,g n 221 1h n n321012ngn321012nhas sketched below5.4.2 Circular convolution4646The result is a length-4 sequence yCn given byFrom the above we observe,304mCmnhmgnhngny430 n3040mCmhmgy 1 3223 1 00hghghghg621101221)()()()(5.4.2 Circular convolution47473041 1 mCmhmgy23320110hghghg
29、hg711102221)()()()(30422mCmhmgy33021120hghghghg611202211)()()()(5.4.2 Circular convolution484830433mCmhmgy03122130hghghghg521201211)()()()(The circular convolution can also be computed using a DFT-based approach(example 5.10)5.4.2 Circular convolution4949Other method:1 2 0 12 2 1 14 4 2 22 2 1 12 2
30、1 12 6 5 5 4 1 14 1 16 7 6 5 265541 1Ly n 6765Cyn 5.4.2 Circular convolution5.5 Classifications of Finite-Length Sequences50505.5.1 Classification based on conjugate SymmetrySymmetry definition:,01(5.64)ccsccax nxnxnnN ccaxncircular conjugateantisymmetric part ccsxncircular conjugatesymmetric part 1
31、()012ccsNxnx nxnnN 1()012ccaNxnx nxnnN 5.5.1 Classification based on conjugate Symmetry5151If xn is real sequence-called circular even partor circular even sequence-called circular odd part or circular odd sequenceConjugate-symmetry part is a real sequenceConjugate-antisymmetry part is a real sequen
32、ceDenote xcevnDenote xcodn5252-circular conjugate-symmetric sequence NNIf x nxnxNn If xn is complex sequence NNIf x nxnxNn -circular conjugate-antisymmetric sequence5.5.1 Classification based on conjugate Symmetry5353Example-Consider the finite sequence of length-5 defined for 0n4 23,31,1323,42x njj
33、jjj Modulo 5 circularly time-reversed55555 0 023 1 413 2 342 3 231 4 123xxjxxjxxjxxjxxj *23,23,31,1342jjx njjj 5.5.1 Classification based on conjugate Symmetry 23,31,132342x njjjjj *523,13,4223,31,xnjjjjj 54543.50.50.5 3.50.0 3,5,.5ccajxnjj 01.531.51.5 0.2,51 5.53ccsxjjjnj55,ccsccsccaccaccsccaThus x
34、nxnxnxnx nxnxn 5.5.1 Classification based on conjugate Symmetry55555.5.1 Classification based on conjugate Symmetry5.5.2 Classification based on Geometric Symmetry5656-symmetric sequency 1(5.68)x nx Nn-antisymmetric sequency 1(5.69)x nx Nn Since the length N of a sequence can be either even or odd,f
35、our types of geometric symmetry are defined.5.6 DFT Symmetry Relations5757 (5.84)reimX kXkjXkReal partImaginary part reimx nxnjxn1()2reXkX kXk1()2imjXkX kXk5858Finite-length Complex Sequence12/0 Njkn NnXkx n eFrom the above12/0 NNjkn NNnXkx n e k=010 00 NNnXXx n 5.6 DFT Symmetry Relations 5959 1kN-1
36、12()/012/0 NjNk n NNnNjkn NnXkXNkxn exn e We thus get:Nx nXk In a similar NxnXk 5.6 DFT Symmetry Relations 112/2/001()2NNjkn Njkn NccsNnnxn ex nxne ccaimxnjXk6060112/2/001()2NNjkn Njkn NNnnx n exne 1()2reX kXkXkIn a similar reccsxnXk imccajxnXk5.6 DFT Symmetry Relations 6161Table 5.1:Symmetry proper
37、ties of the DFT of a complex sequence Length-N Sequence N-point DFT reimreimx nx njx nX kX kjXk NxnXk 1 2reccsNxnXkX kXk ccsrexnXk ccaimxnjXk1 2imccaNjxnXkX kXk Nx nXk 5.6 DFT Symmetry Relations6262Finite-length Real SequenceTable 5.2:Symmetry properties of the DFT of a real sequence Length-N Sequen
38、ce N-point DFT cevcodreimx nxnxnX kX kjXk codimxnjXk NX kXk cevrexnXk rereNXkXk imimNXkXk NX kXk arg argNX kXk symmetry relation5.7 DFT Theorems 6363DFT pairs:g nG kh nH k1.Linearity Theorems (5.98)DFTg nh nG kH k Note:if the length of each sequence is12,g nN h nN312 max,G kH kNNN 0,1n kN64642.Circu
39、lar Time-Shifting Theorems00(5.99)knDFTNNg n nWG k 5.7 DFT Theorems65653.Duality Theorems(5.101)DFTNG nNgk ReRe1nXnxImIm1nXnx)(RejeX)(ImjeXRe kXIm kXxn,N=10Re()jX eIm()jX eRe X kIm X k110 10 X kxk 5.7 DFT Theorems66665.Circular Convolution Theorems (5.102)DFTg nh nG k H k N4.Circular Frequency-Shift
40、ing Theorems00(5.100)k nDFTNNWg nG kk N-point DFTN-point DFTN-point IDFTyngnLength-NGkHkLength-NhnLength-N6767Example 5.10:gn=1 2 0 1,hn=2 2 1 1 0n 3,Compute ycn=gn hn Using DFT (example 5.7)23/23/240 124,1,2,1jknj kjknG kg n eeejj 23/23/240 226,1,0,1jknj kj kjknH kh n eeeejj 24,2,0,2cY kG k H kjj5.
41、7 DFT Theorems6868 24,2,0,2cY kG k H kjj32/40/23/21 41(2422)46,7,6,5jknckj njny nG k H k ej ej e5.7 DFT Theorems69696.Modulation Theorems101 (5.114)NDFTNlg n h nG l HklN 7.Parsevals Relation1122001 (5.115)NNnkg nG kN5.7 DFT Theorems7070Type of Property length-N sequence N-point DFT 10NmNmnhmg110NmNm
42、kHmGN1122001|NNnkg nG kNParsevals relationModulation gnhnGkHkCircular ConvolutionDuality Gn Ng-k NFrequency-shifting WN-k0ngn G k-k0 NCircular Time-shifting g n-n0 N WNkn0GkLinearity agn+bhn aGk+bHkhn Hkgn GkTable 5.35.7 DFT Theorems7171Consider the length-10 sequence,defined 0 n 9,xn=2,3,1,4,-3,-1,
43、1,1,0,6With a 10-point DFT given by Xk,0 k 9.Evaluate the following functions of Xk without computing the DFT:Example:(a)X0,(b)X5,(c),(d),(e)90 kX k9(4/10)0 jkkeX k920|kX k5.7 DFT Theorems89015 12nnn evenn oddXx nx n 7272Answer:(a)51011nnevenWnodd(b)1401900 nNnxXW5.7 DFT Theorems7373(c)990010 10 020
44、10kkxX kX kx(d)(2/)jk N mNx nmeX k 9(2/10)21001 02 10jkkxeX k 9(2/10)2100 10 0210 80jkkeX kxx 5.7 DFT Theorems7474(e)992200 10 780knX kx n1122001|NNnkx nX kNExample:gn and hn denotes a finite length real sequence of length-N.yn=gn+jhn.11 11NNkkNNabY kjaWbWComputing Gk,Hk,gnand hn.5.7 DFT Theorems757
45、5Answer:reccsimccaxnXkjxnjXk11 11NNkkNNabY kjaWbW*11 11NNkkNNabY kjaWbW*1111NNNNNkkNNabYkjaWbW 5.7 DFT Theorems767600()0000NkkNNNNN kkNNWkWkWWWkWk*11()21NNkNaG kY kYkaW*11()21NNkNbH kY kYkjbW*1111NNNkkNNabYkjaWbW 5.7 DFT Theorems11100011()00111()1101NNNNknmkmknNNNkkkmNNNmk m nNmkag nWa WWNaWNaWnNN W
46、e know 1()00 Nk m nNkNmnWmn,01ng nanNIn a similar,01nh nbnN5.8 Fourier-Domain Filtering)49.5(10NnmNnxnym7878The Fourier-domain filtering is usually implemented using the DFT.In the time domain,this approach is equivalent to the circuit convolution of signal xn and impulse response hn.In the frequenc
47、y domain,a simple approach to design the filter is to set the Fourier transform H(ej)to zero in the stopband,to set H(ej)equal to 1 in the passband.Since the ideal filtering has an inverse Fourier transform that is of infinite length,sampling the Fourier transform to create the DFT samples leads to
48、the time-domain aliasing.As a result,the DFT-based filtering will always lead to some small ripples in the filter response.Example 5.12:Consider the narrow-band lowpass signal0.03 0.10255nx nnenComputing the 256-point DFT,then X(k)=0,50k 206 Original signal the noise corrupted signalDFT of noise cor
49、rupted signalX(k)=0,50k 206the signal obtain after a Fourier-domain filtering small ripplesComputing the 256-point DFT,then X(k)=0,50k 206Example:Consider the noise corrupted piano audio.The original corrupted sequenceThe magnitude spectrum of original sequenceExample:Consider the noise corrupted pi
50、ano audio.The magnitude spectrum of Fourier-domain filteringThe uncorrupted sequence5.9 Computation of the DFT of real sequence83835.9.1 N-point DFT of two real sequence using a single N-point DFTLet gn and hn be two real sequence of length N (5.117)x ng njh nFrom table 5.1:*1 (5.118)2NG kX kXk*1 (5
