Chapter 12SamplingSampling Periodic FunctionsDiscrete Time Fourier TransformSlide 5Example DExample of ConvolutionFinding DTFT For periodic signalsExample A & BDT Fourier TransformsProperties of DTFTFourier Transform of Periodic SequencesDiscrete Fourier TransformSlide 14A short hand notationInverse of DFTUsing MATLAB to Calculate DFTExample of DFTExample of DFTSlide 20Slide 21Slide 22Example of IDFTSlide 24Fast Fourier Transform AlgorithmsRadix-2 FFT Algorithms - Two point FFTGeneral FFT AlgorithmExampleFFT Algorithms - Four point FFTFFT Algorithms - 8 point FFTA Simple Application for FFTSlide 32ReferencesChapter 12Fourier Transforms of Discrete SignalsSampling•Continuous signals are digitized using digital computers •When we sample, we calculate the value of the continuous signal at discrete points –How fast do we sample –What is the value of each point •Quantization determines the value of each samples valueSampling Periodic Functions- Note that wb = Bandwidth, thus if then aliasing occurs (signal overlaps)-To avoid aliasing -According sampling theory: To hear music up to 20KHz a CD should sample at the rate of 44.1 KHzDiscrete Time Fourier Transform•In likely we only have access to finite amount of data sequences (after sampling) •Recall for continuous time Fourier transform, when the signal is sampled: •Assuming•Discrete-Time Fourier Transform (DTFT):Discrete Time Fourier Transform•Discrete-Time Fourier Transform (DTFT): •A few points–DTFT is periodic in frequency with period of 2–X[n] is a discrete signal –DTFT allows us to find the spectrum of the discrete signal as viewed from a windowExample DSee map!Example of Convolution•Convolution–We can write x[n] (a periodic function) as an infinite sum of the function xo[n] (a non-periodic function) shifted N units at a time –This will result–ThusSee map!Finding DTFT For periodic signals•Starting with xo[n]•DTFT of xo[n]ExampleExample A & BnotesnotesX[n]=a|n|, 0 < a < 1.DT Fourier Transforms.1  is in radian and it is between 0 and 2 in each discrete time interval2. This is different from where it was between – INF and + INF3. Note that X() is periodicProperties of DTFT•Remember:•For time scaling note that m>1  Signal spreadingFourier Transform of Periodic Sequences•Check the map~~~~~See map!Discrete Fourier Transform•We often do not have an infinite amount of data which is required by DTFT–For example in a computer we cannot calculate uncountable infinite (continuum) of frequencies as required by DTFT•Thus, we use DTF to look at finite segment of data –We only observe the data through a window–In this case the xo[n] is just a sampled data between n=0, n=N-1 (N points)Discrete Fourier Transform•It turns out that DFT can be defined as •Note that in this case the points are spaced 2pi/N; thus the resolution of the samples of the frequency spectrum is 2pi/N. •We can think of DFT as one period of discrete Fourier seriesA short hand notationremember:Inverse of DFT•We can obtain the inverse of DFT•Note thatUsing MATLAB to Calculate DFT•Example: –Assume N=4–x[n]=[1,2,3,4]–n=0,…,3–Find X[k]; k=0,…,3orExample of DFT •Find X[k] –We know k=1,.., 7; N=8Example of DFTExample of DFTTime shift Property of DFTOther DFT properties: http://cnx.org/content/m12019/latest/Polar plot forExample of DFTExample of DFTSummation for X[k]Using the shift property!Example of IDFTRemember:Example of IDFTRemember:Fast Fourier Transform Algorithms•Consider DTFT•Basic idea is to split the sum into 2 subsequences of length N/2 and continue all the way down until you have N/2 subsequences of length 2Log2(8)NRadix-2 FFT Algorithms - Two point FFT•We assume N=2^m –This is called Radix-2 FFT Algorithms •Let’s take a simple example where only two points are given n=0, n=1; N=2http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.htmly0y1y0Butterfly FFTAdvantage: Less computationally intensive: N/2.log(N)Advantage: Less computationally intensive: N/2.log(N)General FFT Algorithm •First break x[n] into even and odd•Let n=2m for even and n=2m+1 for odd •Even and odd parts are both DFT of a N/2 point sequence•Break up the size N/2 subsequent in half by letting 2mm•The first subsequence here is the term x[0], x[4], …•The second subsequent is x[2], x[6], … 11)2sin()2cos()]12[(]2[2/22/2/2/2/2/2/2/212/02/12/02/NNjNNmNNNmNNmNmkNmkNNmmkNkNNmmkNWjeWWWWWWWmxWWmxWExample11)2sin()2cos()]12[(]2[][2/22/2/2/2/2/2/2/212/02/12/02/NNjNNmNNNmNNmNmkNmkNNmmkNkNNmmkNWjeWWWWWWWmxWWmxWkXLet’s take a simple example where only two points are given n=0, n=1; N=2]1[]0[]1[]0[)]1[(]0[]1[]1[]0[)]1[(]0[]0[11001.0111001.01000.0101000.01xxxWxxWWxWkXxxxWWxWkXmmmmSame resultFFT Algorithms - Four point FFTFirst find even and odd parts and then combine them:The general form:FFT Algorithms - 8 point FFThttp://www.engineeringproductivitytools.com/stuff/T0001/PT07.HTMApplet: http://www.falstad.com/fourier/directions.htmlA Simple Application for FFTt = 0:0.001:0.6; % 600 pointsx = sin(2*pi*50*t)+sin(2*pi*120*t);y = x + 2*randn(size(t));plot(1000*t(1:50),y(1:50))title('Signal Corrupted with Zero-Mean Random Noise')xlabel('time (milliseconds)')Taking the 512-point fast Fourier transform (FFT): Y = fft(y,512)The power spectrum, a measurement of the power at various frequencies, is Pyy = Y.* conj(Y) / 512;Graph the first 257 points (the other 255 points are redundant) on a meaningful frequency axis: f = 1000*(0:256)/512;plot(f,Pyy(1:257))title('Frequency content of y')xlabel('frequency (Hz)')This helps us to design an effective filter!ML Help!Example•Express the DFT of the 9-point {x[0], …,x[9]} in terms of the DFTs of 3-point sequences {x[0],x[3],x[6]}, {x[1],x[4],x[7]}, and {x[2],x[5],x[8]}. LaterReferences •Read Schaum’s Outlines: Chapter 6•Do Chapter 12 problems: 19, 20, 26, 5,