The Discrete Fourier Series Quote of the Day Whoever despises the high

The Discrete Fourier Series Quote of the Day Whoever despises the high wisdom of mathematics nourishes himself on delusion. Leonardo da Vinci Content and Figures are from Discrete-Time Signal Processing, 2e by Oppenheim, Shafer, and Buck, 1999-2000 Prentice Hall Inc.

Discrete Fourier Series Given a periodic sequence x[n] with period N so that x[n] x[n rN] The Fourier series representation can be written as 1 x[n] X k e j 2 / N kn N k The Fourier series representation of continuous-time periodic signals require infinite many complex exponentials Not that for discrete-time periodic signals we have e j 2 / N k mN n e j 2 / N kne j 2 mn e j 2 / N kn Due to the periodicity of the complex exponential we only need N exponentials for discrete time Fourier series 1 x[n] X k e j 2 / N kn N k 0 N 1 Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 2

Discrete Fourier Series Pair A periodic sequence in terms of Fourier series coefficients 1 N 1 x[n] X k e j 2 / N kn N k 0 The Fourier series coefficients can be obtained via N 1 X k x[n]e j 2 / N kn n 0 For convenience we sometimes use Analysis equation WN e j 2 / N N 1 X k x[n]WNkn n 0 Synthesis equation Copyright (C) 2005 Güner Arslan 1 x[n] X k WN kn N k 0 N 1 351M Digital Signal Processing 3

Example 1 DFS of a periodic impulse train 1 n rN x[n] n rN r 0 else Since the period of the signal is N N 1 N 1 j 2 / N kn X k x[n]e [n]e j 2 / N kn e j 2 / N k 0 1 n 0 n 0 We can represent the signal with the DFS coefficients as N 1 1 x[n] n rN e j 2 / N kn N k 0 r Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 4

Example 2 DFS of an periodic rectangular pulse train The DFS coefficients 4 1 e j 2 / 10 k5 j 2 / 10 kn j 4 k / 10 sin k / 2 X k e e j 2 / 10 k sin k / 10 1 e n 0 Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 5

Properties of DFS Linearity x1 n x n 2 DFS DFS a x1 n b x2 n DFS X1 k X2 k aX1 k bX2 k Shift of a Sequence x n DFS x n m DFS e j2 nm / N x n DFS X k e j2 km / NX k X k m Duality x n DFS X n DFS Copyright (C) 2005 Güner Arslan X k N x k 351M Digital Signal Processing 6

Symmetry Properties Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 7

Symmetry Properties Cont’d Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 8

Periodic Convolution Take two periodic sequences x n DFS 1 X1 k X2 k x2 n DFS Let’s form the product X3 k X1 k X2 k The periodic sequence with given DFS can be written as N 1 x3 n x1 m x2 n m m 0 Periodic convolution is commutative N 1 x3 n x2 m x1 n m m 0 Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 9

Periodic Convolution Cont’d N 1 x3 n x1 m x2 n m m 0 Substitute periodic convolution into the DFS equation N 1 N 1 X3 k x1[m] x2[n m] WNkn n 0 m 0 Interchange summations N 1 N 1 X3 k x1[m] x2[n m]WNkn m 0 n 0 The inner sum is the DFS of shifted sequence kn km x2[n m]WN WN X2 k N 1 n 0 Substituting N 1 N 1 N 1 kn X3 k x1[m] x2[n m]WN x1[m]WNkmX2 k X1 k X2 k m 0 n 0 m 0 Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 10

Graphical Periodic Convolution Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 11

The Fourier Transform of Periodic Signals Periodic sequences are not absolute or square summable – Hence they don’t have a Fourier Transform We can represent them as sums of complex exponentials: DFS We can combine DFS and Fourier transform Fourier transform of periodic sequences – Periodic impulse train with values proportional to DFS coefficients j Xe 2N X k k 2 k N – This is periodic with 2 since DFS is periodic The inverse transform can be written as 1 2 j j n 1 2 2 2 k j n X e e d X k e d 0 0 2 2 N k N j 1 2 2 k j n 1 N 1 X k 0 N e d N k 0 X k e N k Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 2 k n N 12

Example Consider the periodic impulse train p[n] n rN r The DFS was calculated previously to be P k 1 for all k Therefore the Fourier transform is j Pe 2N k Copyright (C) 2005 Güner Arslan 2 k N 351M Digital Signal Processing 13

Relation between Finite-length and Periodic Signals Consider finite length signal x[n] spanning from 0 to N-1 Convolve with periodic impulse train x[n] x[n] p[n] x[n] r r n rN x n rN The Fourier transform of the periodic sequence is j j j X e X e P e X ej 2N k j Xe 2 k N 2 k 2 j N 2 k X e N k N This implies that j 2N k X ej X k X e 2 k N DFS coefficients of a periodic signal can be thought as equally spaced samples of the Fourier transform of one period Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 14

Example Consider the following sequence 1 0 n 4 x[n] else 0 The Fourier transform X e j e j 2 sin 5 / 2 sin / 2 The DFS coefficients sin k / 2 X k e j 4 k / 10 sin k / 10 Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 15