Question? Leave a message!




Discrete Time Fourier Transform

Discrete Time Fourier Transform
2. DSP Theorycont. Rahil Mahdian 04.05.2015Discrete Time Fourier Transform DTFT • Recall for continuous time Fourier transform, when the signal is sampled: Assuming DiscreteTime Fourier Transform (DTFT): Analysis: Synthesis: 2Properties of DTFT If xn is absolutely summable, it contains properties: • exists for each frequency, ω. Analysis Serie converges. is a continious function of frequency, ω. • Continuity of Stability of the frequency the system response Question. Is an ideal LPF implementable Gibbs Phenomenon 3DTFT theories 4DTFT examples 5Ideal Window 6Ideal Window 7Discrete Fourier Transform basics (DFT) DTFT is still a continuous function of frequency We need to save good samples of DTFT in memory, instead. theorem: Lossless representation Signal is limited of signal by its samples in frequency Analog sampling: is possible spectrum Lossless representation Signal is of signal in frequency DFT domain limited in Time domain by its samples sampling: domain is possible 8DFT intuition ௝ఠ 9DFT DFS relation 10DFT DFS relation Discrete Fourier series coefficients of are the Discrete Fourier Transform coefficients of We should take N samples from the DTFT of xn, , In a 2π period, to get the DFT coefficients of xn, named as By defining, DFS 11DFT 12DFT as a matrix operator 13Example • The DFT of a rectangular pulse • xn is of length 5 • We can consider xn of any length greater than 5 • Let’s pick N=5 • Calculate the DFS of the periodic form of xn 4 j2k /5n Xk e  n0 j2k 1 e  j2k /5 1 e 5 k 0,5,10,...    0 else  14Example Cont’d • If we consider xn of length 10 • We get a different set of DFT coefficients • Still samples of the DTFT but in different places 15Properties of DFT • Linearity DFT  x n X k 1 1 DFT xn Xk 2 2 DFT axn bxn aXk bXk 1 2 1 2 • Duality DFT xn Xk DFT Xn Nx k N • Circular Shift of a Sequence DFT xn Xk DFTj2k /Nm xn m0 n N1 Xke N 16ADC and DAC 17ADC and DAC y(t) x (t) D.S.P. c xn yn Input Output ADC DAC Signal Signal Analogue Digital to to Digital Analogue Converter Converter ஶ ஶஶ ஶ ௝ఠି௝ఠ௡ ି௝ఠ௡௝ஐ௡்ି௝ఠ௡ ିஶ ௡ୀିஶ ௡ୀିஶ௡ୀିஶ ஶ ஶ ஶ 1 Poisson's formula 1 ௝௡(ஐ்ିఠ ) =න݆ܺܿΩ (෍݁ )݀Ω =෍ ఠାଶగ௞ 2ߨ ܶ ିஶ Ω = ௡ୀିஶ ௞ୀିஶ ் Question. What is the requirement to be able to recover the signal completely “signal should be bandlimited“ 18Nyquist rate ݏܰܰ ݏܰ ݏ 19Reconstruction ConditionDAC T 2ߨ Ω = ݏ ܶ ݎ r D/C xn x (t) r (t) = x (n) = x(nT) ݎ sݎ ݎ ܿ ݎ ݎ ܿ ܿ ܰܿݏܰ 20Reconstructed signal sinc function is 1 at t=0 sinc function is 0 at nT ݎ r (t) = ݎݎݏ = Interpolation upon x(n) samples using sinc bases 21Oversampling and we can reconstruct from samples, due Assume: x (t)= c to band limited input signal Problem1. Infinite summation is impossible in practice Ideal LPF Truncate the h (tnT) after some n r AntiAliasing filter Problem 2. x (t) x(n) x (t) c 1 C/D D/C ܿ Compare x (t) x (t) c 2 H(jΩ) C/D D/C Q1.Which output is closer to x (t) c ଶ ߨߨ ܿ݅ − ܶ ܶ 2223Oversampled A/D Conversion • The idea is – to a have a simple analog antialiasing filter – Use higher than required sampling rate – implement sharp antialiasing filter in discretetime – Downsample to desired sampling rate 24Example 351M Digital Signal Processing 25Changing the Sampling Rate • A continuoustime signal can be represented by its samples as  x n x nT c • We can use bandlimited interpolation to go back to the continuoustime signal from its samples • Some applications require us to change the sampling rate – Or to obtain a new discretetime representation of the same continuoustime signal of the form x'n xnT' where T T' c • The problem is to get x’n given xn • One way of accomplishing this is to – Reconstruct the continuoustime signal from xn – Resample the continuoustime signal using new rate to get x’n – This requires analog processing which is often undersired 26Sampling Rate Reduction by an Integer Factor: Downsampling • We reduce the sampling rate of a sequence by “sampling” it xn xnM xnMT d c • This is accomplished with a sampling rate compressor • We obtain x n that is identical to what we would get by reconstructing the d signal and resampling it with T’=MT • There will be no aliasing if   N T' MT 27Frequency Domain Representation of Downsampling • Recall the DTFT of xn=x (nT) c   1 2k  j  Xe X j   c  T T T  k  • The DTFT of the downsampled signal can similarly written as   1 2r 1 2r j  X e X j X j   d c c  T' T' T' MT MT MT r r  • Let’s represent the summation index as r i kM where  k and 0 i M M1  1 1 2k 2i  j  X e X j  d c  M T MT T MT i0 r    2i M1  j  • And finally 1 j M M   Xe X e d  M i0  28Frequency Domain Representation of Downsampling: No Aliasing 29Frequency Domain Representation of Downsampling w/ Prefilter 351M Digital Signal Processing 30Increasing the Sampling Rate by an Integer Factor: Upsampling • We increase the sampling rate of a sequence interpolating it  x n x n /L x nT /L i c • This is accomplished with a sampling rate expander • We obtain x n that is identical to what we would get by i reconstructing the signal and resampling it with T’=T/L • Upsampling consists of two steps – Expanding  xn /L n 0,L,2L,...  xn xkn kL  e 0 else k  – Interpolating 31Frequency Domain Representation of Expander • The DTFT of x n can be written as e   jjnjLk jL Xe xkn kLe xke Xe e  nk k • The output of the expander is frequencyscaled 32Frequency Domain Representation of Interpolator • The DTFT of the desired interpolated signals is • The extrapolator output is given as • To get interpolated signal we apply the following LPF 33Interpolator in Time Domain • x n in a lowpass filtered version of xn i • The lowpass filter impulse response is sinn /L hn i n /L • Hence the interpolated signal is written as  sinn kL/L xn xk i n kL/L k • Note that h0 1 i hn 0 nL,2L,... i • Therefore the filter output can be written as xn xn /L xnT /L xnT' for n 0,L,2L,... i c c 34Changing the Sampling Rate by NonInteger Factor • Combine decimation and interpolation for noninteger factors • The two lowpass filters can be combined into a single one 35DFT Algorithm N1 xn = input nk Xk xnW  N Xk = frequency bins n0 W = twiddle factors 0 01 0(N1) X(0) = x0W + x1W +…+ xN1W N N N 0 11 1(N1) X(1) = x0W + x1W +…+ xN1W N N N : 0 k1 k(N1) X(k) = x0W + x1W +…+ xN1W N N N : 0 (N1)1 (N1)(N1) X(N1) = x0W + x1W +…+ xN1W N N N Note: For N samples of x we have N frequencies representing the signal. 36DFT FFT 2 • The DFT requires N (NxN) complex multiplications: • Each X(k) requires N complex multiplications. • Therefore to evaluate all the values of the DFT ( 2 X(0) to X(N1) ) N multiplications are required. • The DFT also requires (N1)N complex additions: • Each X(k) requires N1 additions. • Therefore to evaluate all the values of the DFT (N1)N additions are required. 37DFT FFT N1 nk Xk xnW ; 0 k N1 1  N n0 xn = x0, x1, …, xN1  Lets divide the sequence xn into even and odd sequences:  x2n = x0, x2, …, xN2  x2n+1 = x1, x3, …, xN1 38DFT FFT  Equation 1 can be rewritten as: N N 11 2 2 2nk2n1k 2 Xk x2nW x2n1W  N N n0 n0  Since: 2 2  j nk  j 2nk 2nk N 2 N W e e N 2n1k k nk W WW N N N nk  W 2 N 2 N N 11  Then: 2 2 nk k nk Xk x2nWW x2n1W N N N  n0 n0 2 2 k  YkW Zk N 39DFT FFT  The result is that an Npoint DFT can be divided into two N/2 point DFT’s: N1 nk Xk xnW ; 0 k N1 Npoint DFT  N n0  Where Y(k) and Z(k) are the two N/2 point DFTs operating on even and odd samples respectively: N N 11 2 2 nk k nk Xk xnWW xnW Two N/2  1 N N 2 N n0 n0 2 2 point DFTs k  YkW Zk N 40DFT FFT  Periodicity and symmetry of W can be exploited to simplify the DFT further: N N 11 2 2 nk k nk Xk xnWW xnW 1 N N 2 N  3 n0 n0 2 2  N N 11 N N  2 2 n k n k  N N  k 2 2  X k xnWW xnW  2 1 N 2  N N 2  n0 n0 2 2 N 2 2 N 2 2  j k j j k j k k : Symmetry  j k Or: 2 N N 2 N N W e e e eeW N N 2 2 N 2 N  j k j j k k N 2 N 2 2 N 2 k 2 : Periodicity W e e e W And: N N 2 2 41DFT FFT  Finally by exploiting the symmetry and periodicity, Equation 3 can be written as: N N 11 2 2 N  nk k nk X k xnWW xnW  4  1 N N 2 N 2  n0 n0 2 2 k  YkW Zk N N  k Xk YkW Zk; k 0,1  N 2  N N  k  X k Y kW Z k ; k 0,1  N 2 2  k  Y(k) and W Z(k) only need to be calculated once and used for both N equations.  Note: the calculation is reduced from 0 to N1 to 0 to (N/2 1). 42DFT FFT  Y(k) and Z(k) can also be divided into N/4 point DFTs using the same process shown above: k k Zk PkW Qk Yk UkW Vk N N 2 2 N  N  k k Z k PkW Qk  Y k UkW Vk  N N 4 4   2 2  The process continues until we reach 2 point DFTs. y0 X0 = y0+W z0 0 x0 y1 X1 = y1+W z1 x2 1 N/2 point y2 x4 DFT yN2 xN2 z0 XN/2 = y0W z0 0 x1 z1 W 1 XN/2+1 = y1W z1 x3 0 1 N/2 point z2 W 1 x5 1 DFT zN/21 xN1 43Summary • DFS Transform • DFT Transform • FFT algorithm • SamplingAliasing • Upsampling/Downsampling 44