DSP-第8章.ppt

1、Digital Signal Processing,Chapter 8 The Discrete Fourier Transform,2,8.0 Introduction four kinds of Fourier tranforms,3,Fourier transform for the continuous and nonperiodic time sign,Continuous and nonperiodic,Nonperiodic and continuous,4,Fourier transform for the continuous and periodic time sign,C

2、ontinuous and periodic,Nonperiodic and discrete,5,Fourier transform for the discrete and nonperiodic time sign,|X(ej)|,Discrete and nonperiodic,Periodic and continuous,6,Fourier transform for the discrete and periodic time sign,Discrete and periodic,Periodic and Discrete,7,8.0 Introduction,Up to now

3、, we have converted analog signals into discrete-time sequences. So now we can process these sequences by computers. But we cannot process the spectra, i.e., Fourier transforms, in digital way, because they are continuous. In order for that the signals can be processed by computers in the discrete-f

4、requency domain, we should sample the continuous-frequency Fourier transforms, to obtain the discrete-frequency Fourier transforms.,8,8.4 Sampling The Fourier Transform,Sampling X(z) at |z| =1, the discrete Fourier transform can be obtained.,9,8.4 Sampling The Fourier Transform,The continuous-freque

5、ncy Fourier transform X(ej) is sampled by an impulse train as follows This sampling process can be described as The Fourier transform X(ej), after sampled, is defined as the discrete Fourier transform.,10,8.4 Sampling The Fourier Transform,Since According to the convolution theorem, we get that Ther

6、efore, after sampling the continuous-frequency Fourier transform, the sequence becomes periodic. x(n) is a precise periodic shifted repetition of x(n).,11,8.4 Sampling The Fourier Transform,Therefore, from equally spaced samples of the Fourier transform, we are able to recover a signal x(n) consisti

7、ng of a sum of periodic repetitions of the original discrete signal x(n). In this case, the period of the repetition is equal to the number, N, of samples of the Fourier transform in one period. Only if N is larger than or equal to the length, L, of x(n), can x(n) be obtained by isolating one period

8、 of x(n):,12,8.4 Sampling The Fourier Transform,13,8.4 Sampling The Fourier Transform,14,8.4 Sampling The Fourier Transform,The expression shows that a finite-length sequence can be obtained from the samples of its Fourier transform. This expression is referred to as the inverse discrete Fourier tra

9、nsform, IDFT for short.,15,8.5 The Discrete Fourier Transform,So the direct and inverse Fourier transforms of a discrete and period sign x(n) are,16,8.5 The Discrete Fourier Transform,In equation If x(n) has length L N, it has to be padded with zeros up to length N, to adapt the sequence length when

10、 calculating its DFT, and The larger the number of zeros padded on x(n) for the calculation of the DFT, the more it resembles its Fourier transform. The amount of zero-padding used depends on the arithmetic complexity allowed by a particular application.,17,8.5 The Discrete Fourier Transform,18,8.5

11、The Discrete Fourier Transform,For the direct and inverse discrete Fourier transform in order to simplify the notation, it is common practice to use X(k) instead of , and to define then we get the canonical form of discrete Fourier transforms, that is,19,8.5 The Discrete Fourier Transform,The discre

12、te Fourier transform can be interpreted in two related ways: As a discrete-frequency representation of finite-length signals. As the Fourier transform of a periodic signal having period N. This periodic signal may correspond to the finite-length signal x(n) repeated periodically, not restricting the

13、 index n in to the interval 0 n N-1.,20,Example 1,Compute the DFT of the following sequence Solution,21,Example 1 (cont.),22,Example 2,Compute the DFT of the following sequence Solution,23,Example 3,Compute the DFT of the following sequence Solution,24,8.6 Properties of the DFT,1 Linearity If x(n) =

14、 k1x1(n) + k2x2(n), then X(k) = k1X1(k) + k2X2(k) Note that the two sequences and two DFTs must have the same length, and the two sequences, if necessary, should be zero-padded accordingly in order to reach the same length.,25,序列的圆周移位,一个有限长序列 x(n) 的圆周移位 (circular shift) 是指以它的长度N为周期，将其延拓成周期序列 ，将 加以移位

15、，取主值区间 0 n N-1，记为 其中 x(n+m)N 表示 x(n) 的周期延拓序列 的移位，即 RN(n)为矩形序列。,26,序列的圆周移位,Step 1,Step 2,Step 3,Step 4,27,2 Circular Time-Reversal,Time-reversal If x(n) X(k), then x( n)N RN(n) X (k)N RN(k),28,3 Circular Shift of a Sequence,Circular shift in the time domain（时域圆周移位） If x(n) X(k), then Note that the se

16、quence x(n+l)N RN(n) is the circular shift of x(n).,29,3 Circular Shift of a Sequence,Proof,30,3 Circular Shift of a Sequence,Circular shift in the frequency domain（频域圆周移位） If x(n) X(k), then Note that the sequence X(k-l)N RN(k) is the circular shift of X(k).,31,4 Complex Conjugation,If x(n) X(k), t

17、hen,32,5 Parsevals theorem,Parsevals theorem,33,6 Conjugate Symmetry Properties,Symmetric and antisymmetric sequences If x(n) = x*(n)N RN(n), it is a periodically circular conjugate symmetric sequence; If x(n) = x*(n)N RN(n), it is a periodically circular conjugate antisymmetric sequence. Periodical

18、ly circular conjugate symmetric and antisymmetric sequences have the following properties: If x(n) is circular conjugate symmetric, X(k) is real; If x(n) is circular conjugate antisymmetric, X(k) is imaginary;,34,7 Symmetry Properties of Real Sequences,Real and imaginary sequences If x(n) is a real

19、sequence, then ReX(k) = ReX(k)NRN(k) ImX(k) = ImX(k)NRN(k) If x(n) is an imaginary sequence, then ReX(k) = ReX(k)NRN(k) ImX(k) = ImX(k)NRN(k),35,8.6.5 Circular convolution Theorems,Circular convolution in time If x(n) and h(n) are N-length finite sequences,and Then which can be rewritten in a compac

20、t form as,36,8.6.5 Circular convolution Theorems,The circular convolution can be rewritten as the matrix form,37,If Compute the 4-DFT of x(n). If y(n) is the 4-point circular convolution of x(n) and h(n), compute y(n) and the 4-DFT of y(n). Solution,Example 1,38,Example 1 (cont.),2.,39,Example 1 (co

21、nt.),40,Example 2,Compute the 6 point circular convolution. Solution,41,Example 2 (cont.),The 6 point circular convolution is Now, lets see the linear convolution.,42,Example 2 (cont.),The 6 point circular convolution is and the linear convolution is Comparison between the circular and the linear. U

22、sually, two convolutions are different from each other; In a certain condition, two convolutions could be the same, that is, the period N is greater than or equal to the length of the linear convolution.,43,Linear Convolutions Evaluated by the Circular Convolution,The circular convolution can be exp

23、ressed as If we want the circular convolution to be equal to the linear convolution between x(n) and h(n), we need Assuming that x(n) has duration L and h(n) has duration K, then we have that c(n) is not zero if,44,Linear Convolutions Evaluated by the Circular Convolution,Then if c(n) is null. Since

24、 the most strict case in the equation is for n=0, we have that the condition for c(n)=0 is Thus, in order to perform a linear convolution using the inverse DFT of the product of the DFT of two sequence, we must choose a DFT size N satisfying,45,Example 3.2,n,1 2 3,46,Example 3.2,yc4(n) is different from yl(n).,yc6(n) is equal to yl(n).,47,Linear Time-Invariant