apter 8 The discrete Fourier Transform K8:0 Introduction K8.1 Representation of Periodic Sequence: the Discrete fourier series 98.2 Properties of the Discrete Fourier Series 8.3 The Fourier transform of Periodic signal 8.4 Sampling the Fourier Transform 98.5 Fourier Representation of Finite-Duration Sequence: the discrete Fourier Transform < 8.6 Properties of the Discrete Fourier Transform 18.7 Linear Convolution using the Discrete Fourier transform 8.8 the discrete cosine transform(DCT)
2 Chapter 8 The Discrete Fourier Transform ◆8.0 Introduction ◆8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆8.2 Properties of the Discrete Fourier Series ◆8.3 The Fourier Transform of Periodic Signal ◆8.4 Sampling the Fourier Transform ◆8.5 Fourier Representation of Finite-Duration Sequence: the Discrete Fourier Transform ◆8.6 Properties of the Discrete Fourier Transform ◆8.7 Linear Convolution using the Discrete Fourier Transform ◆8.8 the discrete cosine transform (DCT)
Filter Design Techniques 8.0 Introduction
3 Filter Design Techniques 8.0 Introduction
8.0 Introduction Discrete Fourier Transform(DFT)for finite duration sequence DFT is a sequence rather than a function of a continuous variable DFT corresponds to samples equally spaced in frequency of the Discrete-time Fourier transform(dTFT) of the signal
4 8.0 Introduction ◆Discrete Fourier Transform (DFT) for finite duration sequence ◆DFT is a sequence rather than a function of a continuous variable ◆DFT corresponds to samples, equally spaced in frequency, of the Discrete-time Fourier transform (DTFT) of the signal
8.0 Introduction Derivation and interpretation of DFT is based on relationship between periodic sequence and finite-length sequences The Fourier series representation of the periodic sequence corresponds to the DFT of the finite-length sequence
5 8.0 Introduction ◆Derivation and interpretation of DFT is based on relationship between periodic sequence and finite-length sequences： ◆The Fourier series representation of the periodic sequence corresponds to the DFT of the finite-length sequence
8.1 Representation of Periodic Sequence: the discrete fourier series Given a periodic sequence x[n] with period n so that 义]=Xn+rN The fourier series representation can be written as 2丌/Nk 小=∑[k]e Q Fourier series representation of continuous-time periodic signals require infinitely many complex exponentials, for discrete-time periodic signals 2丌 2丌 k+mN)n j (2rmn k=0.1.2.….N-1
6 ◆Fourier series representation of continuous-time periodic signals require infinitely many complex exponentials, ◆for discrete-time periodic signals: 8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆Given a periodic sequence with period N so that x[n] ~ x[n rN] ~ x[n] ~ = + 1 (2 / ) [ ] k j N kn x n X k N e = ( ) 2 j k N N m n e + ◆The Fourier series representation can be written as , 0,1,2, , 1 k N = − 2 j kn N e = ( ) 2 2 j kn N j mn e e =
8.1 Representation of Periodic Sequence: the discrete Fourier series 丌 2丌 +mIn tMn e k=0,1,2,…,N-1 Due to the periodicity we only need N complex exponentials for discrete time Fourier series =∑]2x0 ∑[k]e k=0 The Fourier series representation of a periodic sequence
7 8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆Due to the periodicity ,we only need N complex exponentials (2 ) 1 0 1 / [ ] N k j N kn x n X k e N − = = 1 (2 / ) [ ] N k j kn x n X k e N = ( ) 2 j k N N m n e + ( ) 2 2 j kn N j mn e e = 2 j kn N e = , 0,1,2, , 1 k N = − for discrete time Fourier series: The Fourier series representation of a periodic sequence
Discrete Fourier series pair ◆ The fourier series:=∑x[kle j(2T/N)kn k=0 To obtain the Fourier series coefficients we multiply both sides by e (2/ N)rn for osn<N-1 and then sum both the sides we obtain n 2T(k-r)n ∑ x(ne ∑∑X(k)eN n=0 N k=0 ∑X(k)∑e (k-r)n k=0 n=0 8
8 Discrete Fourier Series Pair ◆The Fourier series: 1 0 2 ( ) N n j n N r x n e − = − 0 1 1 0 2 ( ) ( ) 1 N n N k j k r n N N X k e − − = = − = ◆To obtain the Fourier series coefficients we multiply both sides by for 0nN-1 and then sum both the sides , we obtain j n (2 / ) N r e − 1 1 0 0 2 ( ) ( ) 1 n N k N j n N k r N X k e − − = = − = (2 ) 1 / 0 1 [ ] j N N k kn x n e X N k − = =
Discrete fourier series pair 1 N1 2T(k-r)n 1,k-r=N, m an integer ∑ 0 n=0 otherwise orthogonality of the complex exponentials Problem 8.51 丌 rn 27(k-r)n x(ne =∑(k)∑ =0 X(r+mN) k=0 0 X(k)=∑ 2兀kn X(r r(new Periodic n=0 DFS coefficients=1∑[k]e2m k=0 The discrete Fourier series
9 Discrete Fourier Series Pair 1 0 2 1 ( ) N n j k r n N N e − = − = X ( )r Problem 8.51 1 0 2 ( ) N n j n N r x n e − = − 0 1 1 0 2 ( ) ( ) 1 N n N k j k r n N N X k e − − = = − = 1, - , 0, k r mN m an integer otherwise = = (2 ) 1 / 0 1 [ ] j N N k kn x n e X N k − = = 1 0 2 ( ) N n j n N k x n e − = − X ( ) k = = X ( ) r + mN The Discrete Fourier Series coefficients Periodic orthogonality of the complex exponentials. DFS
8.1 Representation of Periodic Sequence: the Discrete Fourier Series +a periodic sequence x[n] with period N, [n=x[n+rN for any integer The discrete Fourier series: 2丌 Synthesis equation k=0 ◆ Coefficients: N-1 2丌 j<-kn Analysis X(k)=∑(n)e equation 1 0
11 8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆a periodic sequence x n with period N, x n x n rN for any integer r = + ◆The Discrete Fourier Series: 1 0 2 ( ) ( ) , N n j kn X k x n N e − = − = 1 0 2 1 [ ] , N k j kn N x n X k N e − = = Synthesis equation Analysis equation ◆Coefficients:
8.1 Representation of Periodic Sequence: the Discrete Fourier Series 区]=∑对e 2/N)k 7=0 OThe sequence x[k] is periodic with period N x[]=X[M,x[=x[N+ X[+M=∑F[]e 兀(k+Nn n=0 kn ∑ xInle e/zn=Xkk n=0
12 8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆The sequence is X k periodic with period N X X X X 0 , 1 1 = = + N N ( ) 1 0 N 2 n j k n N N X k x n N e − = − + + = 1 0 2 N 2 n j kn N j n x n X k e e − = − − = = ( ) 1 0 2 N n j N kn X k x n e − = − =