`Discrete Fourier TransformSpring 2012OutlinePeriodic Sequences Discrete Fourier Series Fourier Transform of Periodic Signals Sampling the Fourier Transform Discrete Fourier Transform Linear Convolution Using the Discrete Fourier Transform Discrete Cosine TransformsDiscrete Fourier TransformPeriodic SequencesDefinition (periodic sequence, periodic signal) A sequence x [n] is said to be periodic with period N if ~ x [n + N] = x [n], ~ ~ For example, a periodic impulse trainfor any integer n.p [n] = ~r =-[n - rN],n = . . . , -1, 0, 1, 2, . . .a complex exponential signal e ~k [n] = e j (2k N)n ,n = . . . , -1, 0, 1, 2, . . .Discrete Fourier TransformDiscrete Fourier SeriesTheorem (discrete Fourier series) Any periodic sequence can be represented as a sum of the complex exponentials. Such a representation is called a discrete Fourier series (DFS). Specifically, let x [n] be a periodic sequence with period ~ N. Then N-1 2 1 ~ X [k]e j ( N k )n . x [n] = ~ N k=0 Note that the frequencies of the complex exponentials are related to the period N via 2k k = . NDiscrete Fourier TransformOrthogonalityThe complex exponentials of a DFS are orthogonal. That is,N-1ej(n=02k N)n e -j2k Nn= Nkk .If k = k ,N-1en=0j ( 2k )n -j Ne2k NN-1 n=n=0ej2(k-k ) Nn=1-ej j2(k-k ) N 2(k-k ) NnN= 0.1-e2k NIf k = k ,N-1en=0j ( 2k )n -j NN-1 ne=n=01 = N.Discrete Fourier TransformDFS CoefficientsTheorem (DFS coefficients) ~ The coefficients X [k] of the DFS of x [n] can be obtained by ~N-1~ X [k] =n=0x [n]e -j ( ~2k N)n .Proof:N-1 N-1 N-12k Nx [n]e -j ( ~n=0)n =1~ j X [k ]e N n=0 k =0 ej2k N2k Nn -j ( 2k )n Ne1 = NN-1N-1~ X [k ]k =0 n=0n -j ( 2k )n Ne1 = NN-1~ X [k ]Nkkk =0~ = X [k].Discrete Fourier TransformPeriodicityTheorem ~ X [k] can be treated as a spectral sequence. Clearly, it is periodic with the same period as x [n]. ~N-1~ X [k + N] =n=0 N-1x [n]e -j ( N (k+N))n ~2=n=0x [n]e -j ( N k )n ~2~ = X [k].Discrete Fourier TransformThe Analysis EquationDefinition (analysis equation) Defining WNe -j( N ) ,2we can rewrite the equation for DFS coefficients asN-1~ X [k] =n=0kn x [n]WN . ~This is called the analysis equation. ~ It yields the weights of the complex exponentials X [k], which is an analysis of the spectral content of x [n]. ~Discrete Fourier TransformThe Synthesis EquationDefinition (synthesis equation) Complementary to the analysis equation, we have x [n] = ~ 1 NN-1 -kn ~ X [k]WN . k=0This is called the synthesis equation. Definition (DFS pair) ~ The following notation is used to denote a DFS pair (~ [n], X [k]): x x [n] ~ DFS~ X [k].Discrete Fourier TransformExample: Temporal Periodic Impulse TrainConsider a periodic impulse train in the temporal domainp [n] = ~r =-[n - rN].By the analysis equation, the DFS coefficients areN-1~ P[k] =n=00 kn p [n]WN = WN = 1. ~That is, the spectral sequence is flat.Discrete Fourier TransformExample: Spectral Periodic Impulse TrainConsider a periodic impulse train in the spectral domain~ Y [k] =r =-N [k - rN].By the synthesis equation, the signal is y [n] = ~ 1 NN-1 -kn 0 ~ Y [k]WN = WN = 1. k=0That is, the temporal sequence is flat.Discrete Fourier TransformPeriodic Rectangular SequenceSuppose x [n] is periodic with period N = 10. In one period, ~ x [n] = ~ 1, 0  n  4, 0, 5  n  9.By the analysis equation, the DFS coefficients are4~ X [k] =n=0kn 1 · W10 =5k 1 - W10 k 1 - W10=e-j 4 k 10sin k 2 sin k 10.Discrete Fourier TransformProperties of DFSlinearity a~[n] + b~ [n] x y shift x [n - m] ~ dualityDFS ~ x [n]  X [k] ~ DFS DFS~ ~ aX [k] + bY [k]km ~ WN X [k]DFS ~ X [n]  N x [-k] ~symmetry ~ x  [n]  X  [-k], ~DFS~ x  [-n]  X  [k] ~DFSDiscrete Fourier TransformProof: ShiftLet y [n] ~ x [n - m]. According to the analysis equation, we have ~N-1~ Y [k] =n=0 N-1kn y [n]WN ~=n=0 N-1kn x [n - m]WN ~=n=0x [n - m]WN ~N-1k(n-m)km WNkm = WNx [n - m]WN ~k(n-m)=n=0 km ~ WN X [k].Discrete Fourier TransformProof: DualityBegin with the synthesis equation. 1 x [n] = ~ Nn  -n N-1 -kn ~ X [k]WN k=0 N-1 kn ~ X [k]WN k=0 N-1- -  N x [-n] = -- ~ - -  N x [-k] = -- ~n=0 n  kkn ~ X [n]WN .~ The last one is the analysis equation of X [n]! Therefore,DFS ~ X [n]  N x [-k]. ~Discrete Fourier TransformPeriodic ConvolutionDefinition (periodic convolution) The periodic convolution of two periodic sequences of period N, ~ X [n] and y [n], is defined as ~N-1x [n] ~y [n] = ~m=0x [m]~ [n - m]. ~ yLet z [n] x [n] y [n]. ~ ~ ~ It is not difficult to see that z [n] a periodic sequence of period N. ~ What is the DFS for z [n]? ~Discrete Fourier TransformPeriodic Convolution TheoremTheorem (periodic convolution theorem) x [n] ~ y [n] ~ DFS~ ~ X [k]Y [k]. x [n] ~ y [n], we have ~k(n-m)Applying the analysis equation to z [n] ~N-1 N-1 kn z [n]WN = ~ n=0 N-1 n=0 N-1 km x [m]WN ~ m=0 n=0 m=0 N-1~ Z [k] = =km x [m]~ [n - m] WN WN ~ yy [n - m]WN ~k(n-m)~ ~ = X [k]Y [k].Discrete Fourier TransformSpectrum of a Discrete-Time SignalDefinition (spectrum of a DT signal) The spectrum of a discrete-time signal is the discrete-time Fourier transform (DTFT) of the signal. That is,X (e ) =n=-jx[n]e -jn .Note that X (e j ) is a function of a continuous variable  is a periodic function with period 2 completely determines x[n], with 1 x[n] = 2X (e j )e jn d ,-n = . . . , -1, 0, 1, . . .Discrete Fourier TransformSpectrum of a Complex ExponentialTheorem The spectrum of a complex exponential with frequency 0 , e [n] = e j0 n , ~ is ~ E (e j ) = 2l=- - &lt; 0 &lt; ,( - 0 - 2l ).Discrete Fourier TransformProof~ The inverse DTFT of E (e j ) must be e [n], ~ 1 2 -~ E (e j )e jn d  = e [n] = e j0 n . ~Therefore, within the integration interval [-, ], ~ E (e j ) = 2( - 0 ). ~ Furthermore, since E (e j ) must be periodic, we have~ E (e j ) = 2l=-( - 0 - 2l ).Discrete Fourier TransformPeriodic Signal as Sum of Complex ExponentialsBy the synthesis equation, a periodic signal x [n] can be expressed as ~ 1 x [n] = ~ NN-12 ~ X [k]e j N kn ,k=02which is a sum of complex exponentials e j ( N k )n .Discrete Fourier TransformSpectrum of a Periodic SingalUsing the DTFT of e j ( N k )n , we have the spectrum of x [n], ~21 ~ X (e j ) = N = =N-1~ X [k] 2k=0 N-1  l=- -2k + 2l N2 N 2 N2(k + lN) ~ X [k + lN]  - N .k=0 l=- k =-2k ~ X [k ]  - NClearly, the spectrum of a periodic sequence is completely contained in the DFS coefficients ~ X [k], k = 0, 1, . . . N - 1.Discrete Fourier TransformExample: Periodic Impulse TrainAs an example, consider the periodic impulse train with period Np [n] = ~r =-[n - rN].To find the spectrum, we only need to know ~ P[k], k = 0, 1, . . . N - 1. ~ By the analysis equation, P[k] = 1. Therefore, the spectrum is 2 2k ~  - P(e j ) = N k =- N.Discrete Fourier TransformPeriodic Signal as Convolution with Impulse TrainLet x [n] be a periodic sequence with period N. Let x[n] be one ~ period of x [n], i. e., ~ x[n] = (0  n  N - 1) ? x [n] : 0. ~ Then x [n] can be expressed via x[n] as ~x [n] = ~r =-x[n - rN]= x[n] r =-[n - rN]= x[n]  p [n] ~Discrete Fourier TransformPeriodic ExtensionDefinition (periodic extension) Given a signal s[n],~[n] sr =-s[n - rN],is called the periodic extension of s[n] with period N. This is also written as ~[n] s s[(n modulo N)] s[((n))N ].Normally, N is not smaller than the duration of s[n].Discrete Fourier TransformSpectrumIt follows from x [n] = x[n]  p [n] that the spectrum of x [n] is ~ ~ ~ ~ ~ X (e j ) = X (e j )P(e j ) = X (e ) j2k 2  - N k=- N .2k 2 X e j(2/N)k   - = N k=- NDiscrete Fourier TransformDFS Coefficients are Samples of DTFTEquating the spectrum of a periodic signal x [n] in two different ~ expressions, i.e. sum of complex exponentials and convolution with periodic impulse trains, 2k 2 ~ ~ X [k]  - X (e j ) = N k=- N . . . DFS . . . convolution,= we have2k 2 X e j(2/N)k   - N k=- N ~ X [k] = X (e j )|= 2k .N~ That is, X [k] are samples of X (e j ) at equally spaced frequencies.Discrete Fourier TransformExampleConsider the periodic rectangular sequence with period N = 10. In one period 1, 0  n  4, x [n] = ~ 0, 5  n  9. The spectrum of x[n] is4X (e ) =n=0je -jn = e -j2sin 5 2 . sin  2It is straightforward to verify that4 ~ X [k] = e -j 10 ksin k 2 sin k 10= X (e j )|= 2k .10Discrete Fourier TransformSampling the Fourier TransformConsider an aperiodic signal a[n] and do the following. Obtain the spectrum A(e j ) of a[n]. ~ Sample A[k] at frequencies k = 2k from A(e j ). N ~ [k], apply the synthesis equation of DFS and obtain a With X periodic sequence ~[n]. a In summary, we have a[n] -- -DTFTA(e j )-- --sampling~ A[k]- -DFSa ^[n].What is the relationship between a[n] and ^[n]? aDiscrete Fourier TransformTheoremTheorem a ^[n] is the periodic extension of a[n] with period N. 1 ^[n] = a N = =m N-11 -kn ~ A[k]WN = N k=0 a[m]e -jk=0 m2k m NN-1 -kn A(e jk )WN k=0 -kn WN1 NN-1a[m]1 NN-1WNk=0-k(n-m)=ma[m]~ [n - m] = pra[n - rN] = ~[n]. aDiscrete Fourier TransformAliasingConsider the case that a[n] is of finite duration M. If N &lt; M (undersamplng), the copies a[n - rN] would overlap in their span. This is called time-domain aliasing. If N = M, a[n] corresponds to one period of ~[n]. a If N &gt; M, a[n] can still be extracted, along with N - M zeros in one period of ~[n]. aDiscrete Fourier TransformFrequency-Domain Sampling TheoremTheorem (frequency-domain sampling theorem) For a finite-duration sequence a[n] of length M, it suffices to represent A(e j ) by N samples in [0, 2) with N  M. The following diagram shows how this is possible. A[k] - -DFSa ~[n]--- --one perioda[n]-- -DTFTA(e j ).Using a higher number of samples also works, and it leads to finer spectral resolution.Discrete Fourier TransformDiscrete Fourier TransformDefinition (discrete Fourier transform) The discrete Fourier transform (DFT) of a finite-duration sequence x[n] of length N is defined asN-1X [k] =n=0kn x[n]WN ,0  k  N - 1.Discrete Fourier TransformDiscrete Fourier TransformDefinition (inverse discrete Fourier transform) The inverse discrete Fourier transform (IDFT) is defined as 1 x[n] = NN-1 -kn X [k]WN , k=00  n  N - 1.We henceforth denote a DFT pair by x[n]  X [k].DFTDiscrete Fourier TransformCircular ShiftDefinition (circular shift) The circular shift by m of an N-point signal x[n] is defined as xm [n] = x[((n - m))N ], 0  n  N - 1, 0, otherwiseA circular shift can be visualized in two ways: construct periodic extension x [n], shift x [n] to the right by m, ~ ~ and truncate x [n] to the segment 0  n  N - 1; ~ place the points of x[n] clockwise on a circle, and rotate the points clockwise.Discrete Fourier TransformProperties of DFTlinearity ax[n] + by [n] circular shift xm [n] duality x[n]  X [k] symmetry x  [n]  X  [((-k))N ],DFT DFT DFT DFTaX [k] + bY [k] e -j N km X [k]2X [n]  Nx[((-k))N ]DFTx  [((-n))N ]  X  [k]DFTDiscrete Fourier TransformProof: Circular Shiftxm [n]DFTe -j N km X [k]2This can be argued as follows: x[n]  X [k]DFS ~  x [n]  X [k] ~ DFT~  x [n - m]  e -j N km X [k] ~  xm [n]  e -j N km X [k]DFT2DFS2Discrete Fourier TransformCircular ConvolutionDefinition (N-point circular convolution) The N-point circular convolution of two finite-duration sequences x[n] and y [n] is defined as follows:N-1x[n]Ny [n] =m=0 N-1x[((m))N ]y [((n - m))N ] x[m]y [((n - m))N ],m=0=0  n  N - 1.Let z[n] x[n] N y [n]. z[n] is of finite duration by definition. z[n] is one period of the periodic convolution z [n] ~x [n] ~y [n]. ~Discrete Fourier TransformCircular Convolution TheoremTheorem Let x[n] and y [n] be of finite duration N. Then x[n]Ny [n]-- - - - - -N-point DFTX [k]Y [k].~ ~ Let x [n], y [n] be the periodic extensions and X [k], Y [k] be the DFS ~ ~ coefficients. By the periodic convolution theorem, x [n] ~ y [n] ~ DFS~ ~ X [k]Y [k].Taking one period, we get x[n]Ny [n]DFTX [k]Y [k].Discrete Fourier TransformConvolution of Finite-Duration SequencesTheorem (finite-duration convolution) Let x[n] and y [n] be causal and finite-duration sequences with durations L and M respectively, andL-1z[n]x[n]  y [n] =m=0x[m]y [n - m].Then z[n] is sure to be causal and finite-duration of length no more than L + M - 1.Discrete Fourier TransformProofWe show that z[n] = 0 for n &lt; 0 and n &gt; L + M - 2. If n &lt; 0, we have n - m &lt; n &lt; 0, 0  m  L - 1.Therefore, the convolution sum is 0 as y [n - m] = 0. If n &gt; L + M - 2, we have n - m &gt; L + M - 2 - (L - 1) = M - 1, 0  m  L - 1.Therefore, the convolution sum is 0 as y [n - m] = 0. Since z[n] can be nonzero only for 0  n  L + M - 2, we conclude that the duration of z[n] is at most L + M - 1.Discrete Fourier TransformLinear ConvolutionTheorem Let x[n] and y [n] be causal and finite-duration sequences with durations L and M respectively. For any N  L + M - 1, we have x[n]  y [n] = x[n]L-1 Ny [n],0  n  N - 1.N-1x[n]  y [n] =m=0 N-1x[m]y [n - m] =m=0x[m]y [n - m]=m=0x[m]y [((n - m))N ]N= x[n]y [n].Discrete Fourier TransformImplementation of Convolution via DFTBy circular convolution theorem, the DFT of z[n] = x[n] Z [k] = X [k]Y [k]. Therefore, the convolution z[n] of two causal and finite-duration sequences x[n] and y [n] can be obtained as follows. pad x[n] and y [n] with zeros to length N  L + M - 1; compute DFT of X [k] and Y [k]; compute IDFT of Z [k] = X [k]Y [k]; extract from z[n] a finite-duration sequence of length L + M - 1. y [n] isNDiscrete Fourier Transform`

43 pages

#### Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

850363