數(shù)字信號處理課件ch5noVIP

1、2022-3-21Autumn 200815 Finite-Length Discrete TransformsAutumn 200822022-3-21Finite-Length Discrete TransformsnIt is convenient to map a finite-length sequence from the time domain into a finite-length sequence of the same length in a different domain, and vice-versa. nSuch transformations are usual

2、ly collectively called finite-length transforms. Autumn 200832022-3-21Finite-Length Discrete Transforms5.1 Orthogonal Transforms 5.2 The Discrete Fourier Transform 5.3 Relation Between the Fourier Transform and the DFT and Their Inverses 5.4 Operations on Finite-Length Sequences 5.5 Classifications

3、of Finite-Length Sequences 5.6 DFT Symmetry Relations Autumn 200842022-3-21Finite-Length Discrete Transforms5.7 Discrete Fourier Transform Theorems 5.8 Fourier-Domain Filtering 5.9 Computation of the DFT of Real Sequences 5.10 Linear Convolution Using the DFT 5.11 Discrete Cosine Transform 2022-3-21

4、Autumn 200855.1 Orthogonal TransformsAutumn 200862022-3-21Orthogonal TransformsnLet xn denote a length-N time-domain sequence with Xk denoting the coefficients of its N-point orthogonal transform. nThe general orthonormal transform pair is given 1Nn0nkkXN1nx1Nk0nknxkX1N0k1N0n,*Autumn 200872022-3-21O

5、rthogonal TransformsIn the class of finite-dimensional transforms, the basis sequences satisfy the condition kl,0kl, 1n , ln ,kN11N0n*Autumn 200882022-3-21Orthogonal TransformsnTo verify the inverse transform expressionnAn interchange of the order of summation on the right-hand side of the above equ

6、ation yields n , ln ,kkXN1nl,nx*1N0n1N0k1N0n* ln, ln, k1kn, ln10k10*10*XNXxNNnNnAutumn 200892022-3-21Orthogonal TransformsnAn important consequence of the orthogonality of the basis sequencenParsevals relation 1N0k21N0n2kXN1nxAutumn 2008102022-3-21Orthogonal TransformsnIn transforms with good energy

7、 compaction properties, most of the signal energy is concentrated in a subset of the transform coefficients, allowing the remaining coefficients with very low energy to be set to zero values. nThis process leads to an efficient approximation of the time-domain signal in the transform domain and is t

8、he basis of many signal compression methods. 2022-3-21Autumn 2008115.2 The Discrete Fourier Transform Autumn 2008122022-3-21The Discrete Fourier Transform1 Definition 2 Matrix Relations 3 DFT Computation Using MATLAB 2022-3-21Autumn 2008131 DefinitionAutumn 2008142022-3-21Definition Using the notati

9、on the DFT is usually expressed as: The inverse discrete Fourier transform (IDFT) is given byNjNeW/21010NkWnxkXNnknN10110NkWkXNnxNkknNAutumn 2008152022-3-21DefinitionTo verify the inverse discrete Fourier transform (IDFT)Autumn 2008162022-3-21Definition Making use of the identity HenceAutumn 2008172

10、022-3-21Example Consider the length-N sequence Its N-point DFT is given byAutumn 2008182022-3-21Example Consider the length-N sequence Its N-point DFT is given byAutumn 2008192022-3-21ExampleConsider the length-N sequence defined for where r is an integer in the range Using a trigonometric identity

11、we can write10)/2cos(NnNrnnx1Nr0)(21)(21/2/2rnNrnNNrnjNrnjWWeenxAutumn 2008202022-3-21Example The N-point DFT of gn is thus given by10)(10)(21NnnkrNNnnkrNWWkXotherwiserNkforNrkforNkX, 0, 2/, 2/Autumn 2008212022-3-21DefinitionnThe computation of the DFT and the IDFT requires, respectively, approximat

12、ely N2 complex multiplications and N(N-1) complex additions.nHowever, elegant methods have been developed to reduce the computational complexity to about N(log2N) operations. nThese techniques are usually called fast Fourier transform (FFT) algorithms .2022-3-21Autumn 2008222 Matrix RelationsAutumn

13、2008232022-3-21Matrix Relations The DFT samples defined bycan be expressed in matrix form aswhereAutumn 2008242022-3-21Matrix RelationsAnd is the DFT matrix given by)1)(1()1(21)1(2421211111111NNNNNNNNNNNNNNNNWWWWWWWWWDAutumn 2008252022-3-21Matrix Relations Likewise, the IDFT relation given bycan be

14、expressed in matrix form asWhere is theIDFT matrixAutumn 2008262022-3-21Matrix Relationswhere Note:)1)(1()1(2)1()1(242)1(21111111111NNNNNNNNNNNNNNNNWWWWWWWWWND*11NNDND2022-3-21Autumn 2008273 DFT Computation Using MATLABAutumn 2008282022-3-21DFT Computation Using MATLABThere are four built-in functio

15、ns in Matlab for the computation of the DFT and the IDFT: fft(x), fft(x,M), ifft(X), ifft(X,M) These functions make use of FFT algorithms which are computationally highly efficient compared to the direct computation.Autumn 2008292022-3-21ExamplenDetermine the M-point DFT Uk of the following N-point

16、sequence: otherwiseNnnu, 010, 10246800.81Original time-domain sequenceTime index nAmplitudeAutumn 2008302022-3-21ExamplenThe magnitude and phase of the DFT sequence for N =8 and M =16. 05101502468Magnitude of the DFT samplesFrequency index kMagnitude051015-1.5-1-0.500.511.5Phase of the DFT

17、samplesFrequency index kPhaseAutumn 2008312022-3-21ExamplenComputation of the IDFT using Matlab.otherwiseKkKkkV, 010,/0246800.81Frequency index kAmplitudeOriginal DFT samplesAutumn 2008322022-3-21Example051015-0.2-0.3Real part of the time-domain samplesTime index nAmplitude051015-

18、0.2-Imaginary part of the time-domain samplesTime index nAmplitude2022-3-21Autumn 2008335.3 Relation Between the DTFT and the DFT and Their InversesAutumn 2008342022-3-21Relation1 Relation with Discrete-Time Fourier Transform 2 Numerical Computation of the Fourier Transform Using the DFT 3

19、 Fourier Transform from DFT by Interpolation 4 Sampling the Fourier Transform 2022-3-21Autumn 2008351 Relation with Discrete-Time Fourier TransformAutumn 2008362022-3-21Relation with Discrete-Time Fourier TransformThe Fourier transform of the length-N sequence , defined for ,is given by jeX nx1-Nn01

20、0)(NnnjnnjjenxenxeXAutumn 2008372022-3-21Relation with Discrete-Time Fourier Transform The simplest relation between a length-N sequence xn, defined for and its DTFT ， is obtained by uniformly sampling on the -axis between From the definition of the DTFT we thus have X k1Nk0enxeX1N0nNkn2jNk2j,)(/Aut

21、umn 2008382022-3-21Relation with Discrete-Time Fourier TransformThe N-point DFT sequence Xk is precisely the set of frequency samples of the Fourier transform of the length-N sequence xn at N equally spaced frequencies . jeX1Nk0,Nk2k2022-3-21Autumn 2008392 Numerical Computation of the Fourier Transf

22、orm Using the DFT Autumn 2008402022-3-21Numerical Computation of theDTFT Using the DFT A practical approach to the numerical computation of the DTFT of a finite-length sequence Let be the DTFT of a length-N sequence xn We wish to evaluate at a dense grid of frequencies , where M N:1Mk0,Mk2kAutumn 20

23、08412022-3-21Numerical Computation of theDTFT Using the DFT Define a new sequence Then 120kMjknjMeenXex n e1, 010,MnNNnnxnXe 1N0nM/kn2j1N0nnjjenxenxeXkkAutumn 2008422022-3-21Numerical Computation of theDTFT Using the DFT Thus is essentially an M-point DFT of the length-M sequence The DFT can be comp

24、uted very efficiently using the FFT algorithm if M is an integer power of 2.()kjeXeAutumn 2008432022-3-21Example Compute the DFT and the DTFT of the Sequence, as shown below00.810246810/MagnitudeIndicates DFT samples2022-3-21Autumn 2008443 Fourier Transform from DFT by InterpolationAutumn 2

25、008452022-3-21Fourier Transform from DFT by Interpolation The N-point DFT Xk of a length-N sequence xn is simply the frequency samples of its DTFT evaluated at N uniformly spaced frequency points Given the N-point DFT Xk of a length-N sequence xn, its DTFT can be uniquely determined from Xk.Autumn 2

26、008462022-3-21Fourier Transform from DFT by Interpolation ThusAutumn 2008472022-3-21Fourier Transform from DFT by Interpolation2/ )1()/2(2/ )2(2/ )2()/2()2(10)/2(22sin22sin22sin22sin11NNkjNkNjkNjNkjkNjNnnNkjeNkNkNNkNkNeeeeeAutumn 2008482022-3-21Fourier Transform from DFT by Interpolation Therefore2/

27、 )1()/2(1022sin22sin1)(NNkjNkjeNkNkNkXNeX】Autumn 2008492022-3-21Fourier Transform from DFT by InterpolationnThe above equation can be rewritten asThe samples of the Fourier transform can be obtained by interpolation of the DFT samples at the discrete frequency points.10)2()(NnjNkkXeX 2/ )1(2sin2sinN

28、jeNNjeXlX2022-3-21Autumn 2008504 Sampling the Fourier TransformAutumn 2008512022-3-21Sampling the DTFT Consider a sequence xn with a DTFT We sample at N equally spaced points developing the N frequency samples These N frequency samples can be considered as an N-point DFT Yk whose N-point IDFT is a l

29、ength-N sequence yn.Autumn 2008522022-3-21Sampling the DTFT Now Thus An IDFT of Yk yields10,)/2(NkWlxeXeXkYlklNNkjjk10,110NnWkYNnyNkknNAutumn 2008532022-3-21Sampling the DTFT i.e. Making use of the identity1()0110Nk n lNknlmNWotherwiseN 10,1110)(10NnWNlxWWlxNnyNklnkNlNklknNklNAutumn 2008542022-3-21S

30、ampling the DTFTwe arrive at the desired relation Thus yn is obtained from xn by adding an infinite number of shifted replicas of xn, with each replica shifted by an integer multiple of N sampling instants, and observing the sum only for the intervalmNnmNnxny10,1Nn0Autumn 2008552022-3-21Sampling the

31、 DTFT To applyto finite-length sequences, we assume that the samples outside the specified range are zeros Thus if xn is a length-M sequence with then yn = xn formNnmNnxny10,1Nn0Autumn 2008562022-3-21Sampling the DTFT If M N, there is a time-domain aliasing of samples of xn in generating yn, and xn

32、cannot be recovered from yn Example Let Autumn 2008572022-3-21Sampling the DTFTBy sampling its DTFTat and then applying a 4-point IDFT tothese samples, we arrive at the sequence yngiven by i.e. xn cannot be recovered from yn2022-3-21Autumn 2008585.4 Operations on Finite-Length Sequences Autumn 20085

33、92022-3-21Operations on Finite-Length SequencesDFT also satisfies a number of properties that are useful in signal processing applications. Some of these properties are essentially identical to those of the Fourier transform, while some others are somewhat different. Autumn 2008602022-3-21Operations

34、 on Finite-Length Sequences1 Circular Shift of a Sequence 2 Circular Convolution 2022-3-21Autumn 2008611 Circular Shift of a SequenceAutumn 2008622022-3-21Circular Shift of a Sequence Consider length-N sequences defined for Sample values of such sequences are equal to zero for values of n 0 and1Nn0N

35、n Autumn 2008632022-3-21Circular Shift of a Sequence If xn is such a sequence, then for any arbitrary integer , the shifted sequence is no longer defined for the range We thus need to define another type of a shift that will always keep the shifted sequence in the range1Nn01Nn0 01nnxnxAutumn 2008642

36、022-3-21Circular Shift of a Sequence The desired shift, called the circular shift, is defined using a modulo operation: For (right circular shift), the above equation impliesNcnnxnx000000,1,nnfornnNxNnnfornnxnxcAutumn 2008652022-3-21Circular Shift of a SequencenGiven a length-6 sequence xn, its circ

37、ularly shifted versions are shown nx665nx1nx662nx4nxAutumn 2008662022-3-21Circular Shift of a SequencenAs can be seen, a right circular shift by is equivalent to a left circular shift by sample periods. nIt should be noted that a circular shift by an integer number greater than N is equivalent to a

38、circular shift by .0n0nN 0nN0nAutumn 2008672022-3-21Circular Shift of a SequenceIn the frequency domain, the circular shifting operation by samples on the length-N DFT sequence is defined by where is also a length-N DFT. 0kNckkXkX0 kXc kXAutumn 2008682022-3-21Steps to get a circular shift of a seque

39、nceGiven a sequence , M-point sequencenPeriodizenTime-shiftingnPrincipal value x n, Ny nxn 100Ny ny nnxnn 1 CNxny nRn2022-3-21Autumn 2008692 Circular ConvolutionAutumn 2008702022-3-21Circular ConvolutionThis operation is analogous to the linear convolution but with a subtle difference. Consider two

40、length-N sequences, gn and hn, respectively. Their linear convolution results in a length-(2N-1) sequence given by nyL10220,NmLNnmnhmgnyAutumn 2008712022-3-21Circular Convolution To develop a convolution-like operation resulting in a length-N sequence , we need to define a circular time-reversal, an

41、d then apply a circular time-shift Resulting operation, called a circular convolution, is defined by nyc 1Nn0mnhmgny1N0mNCAutumn 2008722022-3-21Circular Convolution Since the operation defined involves two length-N sequences, it is often referred to as an N-point circular convolution, denoted as The

42、 circular convolution is commutative, i.e. nhngnyC# ngnhnhng#Autumn 2008732022-3-21ExampleDetermine the 4-point circular convolution of the two length-4 sequences:as sketched below3n0,1122nh,1021ngAutumn 2008742022-3-21Example The result is a length-4 sequence given by From the above we observe 30m4

43、C3n0,mnhmgnhngny#6)21 () 10() 12()21 ( 1 3223 1 000hghghghgyCAutumn 2008752022-3-21Example Likewise7) 11 () 10() 12()21 (23320 1 1 0 1 hghghghgyC6) 11 ()20() 12() 11 (3302 1 1 202hghghghgyC5)21 ()20() 12() 11 (03 1 22 1 303hghghghgyC2022-3-21Autumn 2008765.5 Classifications of Finite-LengthAutumn 20

44、08772022-3-21Classifications of Finite-Length1 Classification Based on Conjugate Symmetry 2 Classification Based on Geometric Symmetry 2022-3-21Autumn 2008781 Classification Based on Conjugate Symmetry Autumn 2008792022-3-21Classification Based on Conjugate Symmetry A length-N sequence xn can be exp

45、ressed as whereis the periodic conjugate-symmetric partis the periodic conjugate-antisymmetric part 1Nn0nxnxnxcapcsp 1Nn0,nxnx21nxN*csp 1Nn0,nxnx21nxN*capAutumn 2008802022-3-21Classification Based on Conjugate Symmetry A length-N sequence xn is called a circular conjugate-symmetric sequence ifand is

46、 called a circular conjugate-antisymmetric sequence ifAutumn 2008812022-3-21ExampleConsider the length-4 sequence defined for : Its conjugate sequence is given by To determine the modulo-4 time-reversed version observe the following:Autumn 2008822022-3-21Example Hence, 32 1 3, 2422, 65 31, 4100*4*4*

47、4*4*juujuujuujuu3j2, 2j4,6 j5,4j1nu4*Autumn 2008832022-3-21Example Therefore Likewise 5 . 4j5 . 3,4, 5 . 4j5 . 3, 1nunu21nu4*CSP 5 . 1 j5 . 1, 2j, 5 . 1 j5 . 1,4jnunu21nu4*capAutumn 2008842022-3-21ExampleA complex DFT Xk can also be expressed as a sum of a circular conjugate-symmetric part and a cir

48、cular conjugate-antisymmetric part as kXcs kXca10,NkkXkXkXcacs10,21*NkkXkXkXNcs10,21*NkkXkXkXNcaAutumn 2008852022-3-21Classification Based on Conjugate Symmetry A sequence satisfyingis called a periodic sequence with a period Nwhere N is a positive integer and k is anyinteger Smallest value of N sat

49、isfyingis called the fundamental periodAutumn 2008862022-3-21Classification of SequencesBased on Symmetry Example - A sequence not satisfying the periodicitycondition is called an aperiodic sequenceAutumn 2008872022-3-21Other Types of Classifications A sequence xn is said to be absolutelysummable if

50、 Example - The sequenceis an absolutely summable sequence as2022-3-21Autumn 2008882 Classification Based on Geometric SymmetryAutumn 2008892022-3-21Classification Based on Geometric SymmetryFinite-length sequences exhibiting geometric symmetry play an important role in digital signal processing. Two types of geometric symmetries are usually defined: (1) symmetric (2) antisymmetricAutumn 2008902022-3-21Classification Based on Geometric SymmetrynA length-N symmetric sequence xn satisfies the condition nA length-N antisymmetric sequence xn sat