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 Not that for discrete-time periodic signals since 2 e N mnn=e n /(2-m)=e Nhn ,k=0,1,2,…,N-1
6 ◆Fourier series representation of continuous-time periodic signals require infinitely many complex exponentials ◆Not that for discrete-time periodic signals, since 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 2 2 2 j k n j kn j kn N mN N N j mn e e e e + = = ◆The Fourier series representation can be written as , 0,1,2, , 1 k N = −
8.1 Representation of Periodic Sequence: the discrete Fourier series 2丌 2丌 2丌 k+mN)n 2mn Due to the periodicity of the complex exponential we only need n exponentials for discrete time Fourier series 刘=∑x[k]e j(2I/N)kn k=0 ◆ No need f[n]=i2Xkk]e
7 8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆Due to the periodicity of the complex exponential we only need N exponentials for discrete time Fourier series (2 ) 1 0 1 / [ ] N k j N kn x n X k e N − = = ◆No need 1 (2 / ) [ ] j N kn k x n X k e N = ( ) ( ) 2 2 2 2 j k n j kn j kn N mN N N j mn e e e e + = =
Discrete fourier series pair the Fourier series representation of a periodic sequence =∑[k]e 2丌/Nkn To obtain the Fourier series coefficients we multiply both sides by e-/(2 N)rn for0≤n≤N-1 and then sum both the sides we obtain 2丌 N-1 ∑(n)eN"=∑∑X(k)eN k-r)n 0 =0 2丌 2丌 ∑ xnen ∑X(k)∑eN (k-r)n n=0 k=0 n=0 8
8 Discrete Fourier Series Pair ( ) 1 0 1 2 / [ ] N k j N kn x n X k N e − = = ◆The Fourier series representation of a periodic sequence: 1 1 1 0 0 0 2 ( ) 2 1 ( ) ( ) N N N n n k j n k N N r j r n x n X k N e e − − − = = = − − = 1 1 0 0 1 0 2 ( ) 2 1 ( ) ( ) N N n k N n j r j k r n N n N x n X k N e 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 −
Discrete fourier series pair 2丌 N-1 2丌 ∑(n)eN"=∑X(k) 1 j(k-r)n n=0 k=0 n=0 N 2丌 ∑ (k-r)n k-r=m. m an integer 0. otherwise n Problem 8.51 HW r(ne n=0 2丌 X(k)=∑x(m) 0 对=∑平[ke k=0
9 Discrete Fourier Series Pair 1 0 2 ( ) 1, - , 0, 1 N n j k r n N k r mN m an integer N otherwi es e − = − = = 1 0 2 ( ) ( ) N n j N r n x n X e r − = − = 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 − = = Problem 8.51, HW 1 1 0 0 1 0 2 ( ) 2 1 ( ) ( ) N N n k N n j r j k r n N n N x n X k N e e − − = = − = − − =
8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆ a periodic sequence with period N n] =n+rN]for any integer A The Fourier series coefficients of xn is N-1 2n kn X(k) x(neN Analysis equation in]= Xkle Synthesis equation
11 8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆a periodic sequence xn with period N, ~ xn= xn+ rN for any integer r ~ ~ ◆The Fourier series coefficients of is xn ~ 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
8.1 Representation of Periodic Sequence: the Discrete Fourier Series [小=∑ (2 兀/Nkn xne n AThe sequence x[k] is periodic with period N []=M]]=XN+ [k+N=∑ 2I/Nk+nin n=0 ∑ 1(2xN)。2z xInle n=0
12 8.1 Representation of Periodic Sequence: the Discrete Fourier Series ◆The sequence is X k periodic with period N 1 ~ 1 ~ , ~ 0 ~ X = X N X = X N + ( )( ) 1 0 2 N n j N k N n X k N x n e − = − + + = ( ) 1 0 2 2 N n j N kn j n x n X k e e − = − − = = ( ) 1 0 2 N n j N kn X k x n e − = − =