數(shù)字信號處理英文版課件：Chap 5 Finite-Length Discrete Transform

1、Chapter 5 Finite-Length Discrete Transform The Discrete Fourier Transform (DFT) Computation of the real sequences DFT Computation of Linear convolution Relation between DFT & DTFT Operations on Finite-Length Sequences DFT symmetry relations and DFT theorems Applications of DFT Circular shift of a se

2、quence Circular convolutionDSP group 2007 chap5-ed12 5.1 Orthogonal Transforms Definition: N-point orthogonal transform analysis equation synthesis equation Orthogonal basis sequence, Length-NDSP group 2007 chap5-ed13 Condition for orthogonal basis sequence Parsevals relation Orthogonal Basis sequen

3、ce satisfiesP189 (5.6) & energy compactionDSP group 2007 chap5-ed14 5.2 The Discrete Fourier Transform Review Time domain Frequency domain Continuous Periodic FS Aperiodic Discrete Continuous Aperiodic FT Aperiodic Continuous Discrete Aperiodic DTFT Periodic ContinuousDiscrete Periodic DFS Periodic

4、DiscreteDSP group 2007 chap5-ed15 5.2 The Discrete Fourier Transform 5.2.1 Definition xn : N-point sequence which is xn=0 when nN1 Xk : N-point sequence, called N-point DFT of sequence xn k,n = e j2kn/N complex basis sequenceOrthogonality, periodic 6 5.2.1The DefinitionIDFT Definition of IDFT Notati

5、on: WN = e j2 /N DFT Notation:Time domainFrequency domainDSP group 2007 chap5-ed17 5.2.1The Definition Examples of DFTExample 5.1-1Solution:Consider the length-N sequenceFind its N-point DFT.DSP group 2007 chap5-ed18Example 5.1-2Solution:Find its N-point DFT.Consider the length-N sequence 5.2.1The D

6、efinition Examples of DFTDSP group 2007 chap5-ed19Example 5-2Solution:Compute the N-point DFT of the length-N sequenceUsing a trigonometric identity 5.2.1The Definition Examples of DFTDSP group 2007 chap5-ed110 5.2.1The Definition Examples of DFTDSP group 2007 chap5-ed111 5.2.2 Matrix Relations DFT

7、definition Notation DFT represented in matrix formDSP group 2007 chap5-ed112 5.2.2 DFT matrixDN is the NN DFT matrix given byDSP group 2007 chap5-ed113 5.2.2 Matrix Relations IDFT in matrix formLikewise, the IDFT can be expressed in matrix forms:Or Where DSP group 2007 chap5-ed114 5.3 Relation betwe

8、en DTFT and DFT and their Inverses5.3.1 Relation with DTFT DTFT for a N-point sequence Sampling uniformly at N equally spaced frequencies DSP group 2007 chap5-ed115 5.3.1 Relation with DTFT DFT sequence Xk is precisely the set of frequency samples of the DTFT X(e j) of the length-N sequence xn at N

9、equally spaced frequencies: i.e.,DSP group 2007 chap5-ed116 5.3.2 Numerical Computation of DTFT The DFT provides a practical approach to the numerical computation of the DTFT of a finite -sequence. Define a new sequence xen Evaluate X(e j) at DSP group 2007 chap5-ed117Exampler = 2 5.3.2 Numerical Co

10、mputation of DTFTFind gk.18 5.3.2 Numerical Computation of DTFTn=0:20;x=cos(2*pi*n*30/200) + cos(2*pi*n*35/200);y = fft(x,256); figure(1)subplot(2,1,1);xbin = (0:255)*200/256;plot(xbin,abs(y)n=0:100;x=cos(2*pi*n*30/200) + cos(2*pi*n*35/200);y = fft(x,256);xbin = (0:255)*200/256;subplot(2,1,2);plot(x

11、bin,abs(y)19 5.3.3 The DTFT from DFT by interpolation The DTFT of N-point sequence xn:DSP group 2007 chap5-ed120Because 5.3.3 The DTFT from DFT by interpolationDSP group 2007 chap5-ed121 Notation 5.3.3 The DTFT from DFT by interpolationDSP group 2007 chap5-ed122 Sampling X(e j ) at N equally spaced

12、points k=2k/N, 0 k N1, developing the N frequency samples: 5.3.4 Sampling the DTFT Consider an arbitrary sequence xn Let Question: DSP group 2007 chap5-ed123 5.3.4 Sampling the DTFTDSP group 2007 chap5-ed124Because Two casesSuppose xn : length M, i.e. xn =0 for nN, time-domain aliasing, xn can not b

13、e recovered from yn .Case a MN yn=xn, for 0 n N 1 .Example 5.6 5.3.4 Sampling the DTFTxn can be recovered from ynSolution:Solution:xn cannot be recovered from ynExample 5.6DSP group 2007 chap5-ed127DTFTReal lineSamplingNo time aliasingPeriodizeMN0 n M10 k N1 5.3.4 Sampling the DTFT Length of sequenc

14、e M is less than sampling point NynxnDSP group 2007 chap5-ed128DTFTReal lineSamplingtime aliasingPeriodizeM N0 n M10 k N1 5.3.4 Sampling the DTFT Length of sequence M is greater than sampling point NynxnDSP group 2007 chap5-ed1295.4.1 Circular shift of a sequence1. Consider length-N sequences define

15、d for 0nN1 2. i.e. xn=0, for n 0 (right circular shift), the above equation implies 5. 4.1 Circular shift of a sequenceWhere: if r = m +l N, and 0m N1, then moduloDSP group 2007 chap5-ed1317. Illustration of the concept of a circular shift 5. 4.1 Circular shift of a sequence exampleDSP group 2007 ch

16、ap5-ed1328. 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 periods;9. A circular shift by an integer number greater than N is equivalent to a circular shift by n0 N. 5. 4.1 Circular shift of a sequence comments on the examp

17、le10. Circular shift can be realized by extend the sequence periodically as xn+mN first, and then shift, or vice versa, and at last get the sample for 0nN1. P183 Fig 5.5DSP group 2007 chap5-ed133xn-1xnx4 5. 4.1 Circular shift of a sequence example1 xn+4m,DSP group 2007 chap5-ed134 5. 4.1 Circular sh

18、ift of a sequence stepsStep1: time-shifting;Step2: N-point period extension; Step3: get the principle; DSP group 2007 chap5-ed13511. circular time-reversal12. Frequency domain 5.4.1 Circular shift of a sequencespeciallyDSP group 2007 chap5-ed1361. This operation is analogous to linear convolution, b

19、ut with a subtle difference;2. Consider two length-N sequences, gn and hn;3. Their linear convolution results in a length (2N-1) sequence yLn given by 5.4.2 Circular convolutionDSP group 2007 chap5-ed1374. Resulting operation, called a circular convolution, is defined by 5.4.2 Circular convolution d

20、efinition5. Since the operation defined involves two length-N sequences, it is often referred to as an N-point circular convolution, denoted as DSP group 2007 chap5-ed1386. The circular convolution is commutative, i.e. 5.4.2 Circular convolutiongn hn = hn gn (5.56)NN7. The matrix form of circular co

21、nvolution isP201 (5.54)circulant matrixDSP group 2007 chap5-ed139nn 5.4.2 Circular convolution Example Determine the 4-point circular convolution of the two length-4 sequences:Example 5.7Solution:DSP group 2007 chap5-ed140 The result is a length-4 sequence yCn given by4 5.4.2 Circular convolution Ex

22、ampleDSP group 2007 chap5-ed141 5.4.2 Circular convolution ExampleDSP group 2007 chap5-ed142The circular convolution can also be computed using a DFT-based approach 5.4.2 Circular convolution Example P203 Fig 5.6DSP group 2007 chap5-ed143 5.4.2 Circular convolution Example0gn = hn151234Assume gn = h

23、n =un un 6 ; Example A2Compute: (1) gn hn; (2) gn hn (3) gn hn12010yn= gn hn6DSP group 2007 chap5-ed144 5.4.2 Circular convolution Example0gn hn651234010yn= gn hn6010 gn hn612DSP group 2007 chap5-ed145 5.4.2 Circular convolution relation with linear convolutionAssume: sn=gn hn, sCn=gn hn, N0n N14601

24、0yn= gn hn0-N = 6yn+NN=66N=6ynNN=60 5.4.2 Circular convolution Example A2DSP group 2007 chap5-ed147Another method based on linear convolution 5.4.2 Circular convolution Example 5.7)0n 3 DSP group 2007 chap5-ed1485.5.1 Classification based on conjugate Symmetry 5.5 Classifications of Finite-Length Se

25、quencesWhere DSP group 2007 chap5-ed149 5.5.1 Classification based on conjugate SymmetryFor N-point sequence, the symmetry is using modulo operationWhere circular conjugate-symmetric part circular conjugate-antisymmetric part circular conjugate-symmetric circular conjugate-antisymmetric 5.5.1 Classi

26、fication based on conjugate Symmetry For N-point DFT:DSP group 2007 chap5-ed151circular even part or circular even sequence circular odd part or circular odd sequence Conjugate-symmetry part is a real sequence Conjugate-antisymmetry part is a real sequence Denote xevnDenote xodn 5.5.1 Classification

27、 based on conjugate Symmetry If xn is a real sequence:DSP group 2007 chap5-ed152Consider the finite sequence of length-4 defined for 0n3 Modulo 4 circularly time-reversed 5.5.1 Classification based on conjugate Symmetry ExampleExample 5.9Solution:DSP group 2007 chap5-ed153 5.5.1 Classification based

28、 on conjugate Symmetry ExampleDSP group 2007 chap5-ed154Real partImaginary part 5.6 DFT symmetry relations55Length-N Sequence N-point DFT 5.6 DFT symmetry relations Table 5.1P194 Tab 5.1 DSP group 2007 chap5-ed156 5.6 DFT symmetry relations-Table 5.2Length-N real Sequence N-pointDFT Symmetryrelation

29、s 5.7 DFT Theorems Table 5.3 Theorem Length-N Sequence N-point DFT LinearityCircular time-shiftingCircular frequency-shiftingN-point circularConvolutionDualityParsevals RelationModulation DSP group 2007 chap5-ed158N-point DFTN-point DFTN-point IDFTyngnLength-NGkHkLength-NhnLength-N 5.7 DFT Theorems

30、Circular convolution diagram DSP group 2007 chap5-ed159Solution: 5.7 DFT Theorems Circular convolution exampleExample 5.11 Find the 4-point circular convolution of the two sequences using DFT approach:DSP group 2007 chap5-ed160 5.7 DFT Theorems Circular convolution example DSP group 2007 chap5-ed161

31、Let Xk (0k9) is 10-point DFT of the sequence xn, defined for 0n9, xn=2, 3, 1, 4, -3, -1, 1, 1, 0, 6Evaluate the following functions of Xk :(a) X0, (b) X5, 5.7 DFT Theorems example Example A1DSP group 2007 chap5-ed162Solution: 5.7 DFT Theorems example DSP group 2007 chap5-ed163(e) According to Parsev

32、als relation 5.7 DFT Theorems example DSP group 2007 chap5-ed1645.9.1 N-point DFTs of two real sequence using a single N-point DFTLet gn and hn be two real sequence of length N According to symmetry relations of DFT (table 5.1): 5.9 Computation of the DFT of real sequenceDSP group 2007 chap5-ed165 L

33、et vn be a real sequence of length 2N. 5.9.2 2N-point DFT of a real sequence using a single N-point DFT66 5.9.2 2N-point DFT of a real sequence using a single N-point DFTStep1: decimation; Step2: DFT; Step3: construction; DSP group 2007 chap5-ed167Linear convolution is a key operation in most signal

34、 processing applications. 5.10 Linear Convolution Using the DFTRelation between linear convolution and circular convolution:sn=gn hn, sCn=gn hn, Ncircular convolution theorem:DSP group 2007 chap5-ed168 5.10.1 Linear convolution of two finite -length sequence Consider two sequences: gnlength N; hnlen

35、gth M; Linear convolution of the two sequence: y n= gnhn length N+M1; L-point Circular convolution of the two sequence:yCn=gn hn L When L N+M1,yCn= y n DSP group 2007 chap5-ed169 5.10.1 Linear convolution of two finite -length sequence Let L N+M1, the linear convolution can be computed using circular convolution, or using the DFT circular convolution theorem. To realize the above process, we need to define two length-L seque