### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Signals and Systems ECE 3640

Utah State University

GPA 3.86

### View Full Document

## 10

## 0

## Popular in Course

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

This 108 page Class Notes was uploaded by Seth Gibson on Wednesday October 28, 2015. The Class Notes belongs to ECE 3640 at Utah State University taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/230401/ece-3640-utah-state-university in ELECTRICAL AND COMPUTER ENGINEERING at Utah State University.

## Reviews for Signals and Systems

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/28/15

ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT Objective To investigate the discrete Fourier transform which is a numerical way of computing Fourier transforms The DFT We have seen that the Fourier transform can be used in a variety of applications While an important theoretical tool there is a problem with it in practice we must have an analytical expression for the functions we are transforming and have to be able to compute its transform In practice the transforms are often computed from discrete samples of a signal and the transform is computed for only a discrete set of frequencies This computational approach is known as the DFT There are fast algorithms for computing the DFT which are called the Fast Fourier Transform FFT The FFT is nothing more than a way of organizing the computations in the DFT to compute exactly the same thing but with less processing for the computer It is safe to say that the revolution in signal processing has its genesis in the discovery of the FFT algorithm We will begin my making the connection between continuoustime signals with the spectrum and the DFT signals in their discrete time and frequency domains Let be timelimited to 739 seconds having spectrum Fwi Then since is timelimited it cannot be bandlimited why Let denote the sampled signal with samples taken ever T seconds and let F60 denote the spectrum of the sampled signal the periodic extension of Fw repeating ever 75 lT Hz Because f is not bandlimited there must be some amount of aliasing ow let us imagine sampling in the frequency domain of Fw this corresponds to creating a periodic repetition of the sampled signal in the time domain We let To be the period of repetition in the time domain corresponding to samples every lTo of the spectrum ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 2 Let us determine how many samples are involved here The number of samples in the time domain of each period is To N i 0 T The number of samples in the frequency domain of each period is F lT 7is 0 F0 1T0 NO The aliasing can be reduced by increasing the sampling frequency but can never be entirely eliminated for a timelimited signal If we had started out with a ban dlimited signal then it would not have been timelimited and we would have had overlapping in the time domain If in addition the signal that we are dealing with is not in fact timelimited but we must for reasons of practicality deal with a timelimited version we must perform some truncation This truncation leads to spectral leakage This also causes aliasing creating higher spectral components than might have been in the original signal The spectral leakage can be reduced by increasing the window width longer data set This increases To which in turn reduces for Note that 70 determines the frequency resolution Also observe that by this sampling property we are getting only a partial view of the spectrum A true spectral peak might not lie right on one of the sample values This can be mitigated by sampling more nely decrease f0 meaning increase T0 meaning increase N0 Let be a discretetime sequence possibly obtained from a continuoustime signal by sampling say fkTi Note that we are using k as the discrete time index Suppose t at we have No samples of the signal where N0 is some number that we choose As a point for future reference the number No is commonly chosen to be a power of 2 since this works most efficiently for most FFT routines Following the book s notation let ft Tm TfkT 16m That is it is simply a scaled version of the time sample Often this scaling is overlooked or it is assumed that the sampling interval is normalized to one Also let FT F Two That is it is a sample of the spectrum The DFT of the set of points 1 f1 i i fNO1 is given by N071 N071 FT Z fkeijr ok Z fkeijwrrkNo 1 k0 k0 where 90 27rN0 oni In the transform formula the number 7 must be an integer It is an index to a frequency as we will see later The inverse DFT is 1 N071 1 N071 i F jr ok 7 F jQerNo 2 ft Nogre Negre ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 3 The transform pair is sometimes represented as fkltZgtFr Fr flflcl Note the interesting parallels between these transforms and the FiTis we have already seen 1 In going from the time domain k to the frequency domain r the exponen tial term in the summation has a negative sign 2 In going from the frequency domain to the time domain the exponential term has a positive sign and the summation is multiplied by a normalizing factor lNo in this case It should be pointed out that while the sampling processing introduces possible aliasing and spectral leakage problems the actual transform pair given above is exact Let us connect the de nition given above with the conventional Fourier transform noting where approximations are made The sampled signal can be written as 7 N071 fa Z fkT6t 7 m lC0 time limited The Fourier transform of this signal is N071 V E Z fkT57 WT lC0 If we neglect the aliasing over the interval lwl lt us2 by the sampling theorem we ave 1 FQU TF Hence N071 FM TFw T Z fkTe j WT M lt psi2 lC0 Sampling this now we obtain N071 F FWD T Z fkTe j W T Let wOT 00 then 90 wOT 27rF0T 27rN0 By our de nition TfkT fk Putting these de nitions together we nd N071 Fr Z fkwmok lC0 We conclude that except for aliasing the DFT represents a sampled version of the FT Taking the last expression for FT multiply by e 1mg and sum N071 N071 N071 E Frejm or 2 2 fkeijk okejm or r0 7 0 k0 ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 4 We nd how that N071 Z 51m7k907 7 0 N0 k m mod N0 0 otherwise Hence the sum collapses and we get the desired result The value FT is said to provide information about the rth frequency bin lt corresponds to a Hertz frequency of 5 fT9027VTf0 TTo Take some examples r 0 A f 0 rlgtfFsN0Tii 0 This is the frequency resolution 7 N02 A f FsZ This is the maximum representable frequency The number of points in the DFT can be written as T N0 7 0 T a where T0 relates to the sampling rate in the frequency domain and T relates to the sampling rate in the time domain Observe that to increase the frequency resolution the number of points of data No must be increased We can increase N0 and improve the frequency resolution by increasing T0 taking more data which amounts to taking samples closer together in frequency f0 lTo or by taking samples faster in time increasing the sampling rate Note The book de ned the transform in terms of fk TfkTi In practice the FFT routines simply deal with the data fk they don t worry about whether it is scaled or not Since the effect of the scaling by T is to simply scale the transform in applications it is not common to worry about the scaling either Example 1 A signal has a duration of 2 ms and an essential bandwidth of 10 kHz What is its absolute bandwidth We want to have a spectral resolution of 100 Hz in the DFT Determine N0 the number of points in the DFT By the sampling theorem we must sample at least double the highest frequency which is B 10000 Let F5 2B 20000 samplessec The resolution is F0 100 Hz The signal duration is To lFo 10 ms Here is an interesting thing to get the spectral resolution we need we need 10 ms of data when in fact the signal only lasts for 2 ms The solution is to take the 2 ms of data then pad the rest with zeros This is called zero padding Then E f0 In practice we would probably want No to be a power of 2 so No 256 is a better choice This could be obtained by decreasing T which would reduce aliasing or increasing To which would increase the resolution 1 N0 200 Note that zero padding cannot replace any information that is not already present in the signal It simply re nes the sampling of the spectrum that is al ready present ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 5 Aliasing and Leakage There are two effects that are introduced into the computation of the DFT Aliasing Since when we compute we are necessarily dealing with a timelimited set of data the signal cannot be bandlimited The sampling process with its incumbent spectral duplication therefore introduces aliasing This aliasing effect can be reduced by sampling faster Leakage If the function xt is not really time limited then we truncate it in order to obtain a nite set of samples As viewed above the mathematics sees the sampled signal as if it were periodic in time There are two ways of viewing what is going on First if we have a function 950 we can obtain a timetruncated version of it by W 0100 where yt is the truncated version and wt is a windowing function In the frequency domain the effect is to smear the spectrum out Yw 5X60 WW This smearing is spectral leakage Another way of viewing the leakage is this if we truncate a function then make it periodic the resulting function is going to have additional frequency components in it that were not in the original function due to the change from end to end The only way this does not happen is if the the signal is periodic with respect to the number of samples already Leakage can be reduced either by taking more samples wider windows of data ice increasing No It can also be reduced by choosing a different window function However it can never be completely eliminated for most functions Some examples In this section some examples of FFT usage are presented by means of MATLAB f 100 Z frequency of the signal fs 400 Z sampling rate N0 128 Z choose the number of points in the FFT f0 fsNO 39Z compute the frequency resolution f0 3125 Hz k OzNO l 392 range of index values fin cos2piffsk 39Z input function plotkfin Z plot the function ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 7 Note that the function ends at the end of a cycle its periodic 7 extension is the same as the function 7 fout fftfinN0 7 compute the FFT plot kabsfout 7 we have to plot absfout since fout is a complex vector 2D 4D EEI ED mu 12D MEI note that there are exactly two peaks This is because the frequency was a multiple of the resolution The bin with the frequency peaks is bin 32 and bin 96 128 3296 since ffO 32 Note the indexing in Matlab starts from index1 This means that index 1 corresponds to bin 0 Hence bin 32 is in fout33 fout33 64 0i 7 fout97 64 0i 7 7 Now let s change the frequency and do it again f f0 7 set the frequency to the lowest resolvable frequency fin cos2piffsk 7 function plotkfin 7 plot the function fout fftfinN0 7 compute the FFT plot kabsfout ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 2D 4D EEI ED mu 12D 1 El 7 7 Now let s try a frequency that is not a multiple of the 7 frequency resolution f 51 7 Note that ffO 1632 which is not an integer bin number fin cos2piffsk 7 function plotkfin 7 plot the function fout fftfinN0 7 compute the FFT plot kabsfout ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 8 5m 4m an in m z u 4n an 7 Note that the time function does not end at the end of a period 7 The transform does not occupy just one bin there is spectral 7 leakage The peak occurs at bin 16 the nearest integer to the 7 true real frequency bin ED mu 12D MEI 7 Now let s examine the effect of zero padding on this problem 7 increasing N0 Using the same frequency add on 128 zeros to the 7 set of samples fin1 fin zeros1128 foutl fftfin1256 plot O255absfout1 an 5m 4m an in m an mu 15D 2mm 25m 3 Note that the zero padding did nothing to improve the spectral leakage Now let s examine the effect of the number of samples on the spectral resolution Suppose that we have a signal that consists of two sinusoids f1 51 Hz and f2 53 Hz We will keep the same 7 sampling rate To begin with we will take 128 points of data fin cos2pikf1fs cos2pikf2fs plotkfin ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 9 fout fftfin128 plot kabsfout 7 The frequency resolution is f03125 Hz The frequencies we wish to 7 distinguish are too close to both show up 7 Now let s increase the number of sample points up to 512 This gives 7 a frequency resolution of f0 07813 k2 0511 fin2 cos2pik2f1fs cos2pik2f2fs plot k2fin2 ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 10 fout2 fftfin2512 plot k2absfout2 7 In this case we are able to distinguish between the two 7 frequencies 7 Now suppose that instead of taking more data we had simply decided 7 to zeropad out to 512 points 397 finl fin zeros1384 7 512 points plotk1fin1 foutl fftfin1512 plot k1fout1 ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 11 7 Note that we have not increased the spectral resolution We have 7 only provided a more finely sampled version of the spectrum we saw 7 with 128 points The FFT The FFT is a way of organizing the computations necessary to compute the DFT in such a way that the same work is done but with less effort I like to think of this as a bicycle analogy lfl ride my bike from home to work I use the same engine me as ifl walk in But by organizing my e orts better by means of wheels and gears the engine is able to work more efficiently and I get here faster To gauge the improvement let s rst approximate how many computations are necessary to compute the DFT lfl have No data points I can compute one of the DFT outputs by the formula N071 FT Z fkeijwrkrNo kio There are NO terms in the summation each of which requires a multiply naturally in the name of efficiency we would precompute and store all the complex exponential factors So each points requires N0 multiplyaccumulate operations There are No points in the transform so the overall DFT takes about N3 multiply accumulates If No 1024 this turns out to be a whopping 1048576 multiplyaccumulates We ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 12 would say the complexity is 0N02 where the 0 means order of which is to say in the ballpark of77 The FFT is able to reduce the computational requirements to about 0N0 log2 N0 For the case of N0 1024 this turns is 10240 operations which is more than 100 times faster And it provides exactly the same result This speedup has enabled some algorithms to be developed and successfully deployed that never could have happened Note that this speedup is entirely independent of the technology It was 100 times faster 20 years ago and will be 100 times faster 20 years from now The discovery of the FFT laid the foundation for modern DSP as well as a variety of computational disciplines One of the morals of this story is that it pays to pay attention to how the computations are done We will not go into two many details of how the FFT works 7 we need to leave something to ECE 5630 We can however give a brief summary The basic technique is divide and conquer we take a problem with No points and divide it into two problems of N02 points Since the complexity goes up as the square of the number of points each of these N02 problems is four times as easy as the No problem If we can put these two problems together to give the overall answer then we have saved computations We then take each of these N02 problems and split them into N04 problems each of which is easier and so on At every level we split the number of points that go into the computation until we get down to a DFT in just two points This is easy to compute This subdivision shows why the number of points must be a power of two we split by two at every stage in the process This also shows why the complexity has the factor of log2 N0 in it we can split No by two that many times All good routines to numerically compute the DFT are based upon some form of FFT Convolution using the DFT We have seen the convolution theorem over and over convolution in time is the transform of multiplication in the frequency domain By numerically computing the transform using the DFT we can compute convolutions of sequences There are some issues to be very careful of however since the DFT imposes certain require ments on the signals We will worry later about this For the moment consider the computational complexity Suppose I have a sequence x of N points and another sequence y also of N points We know that the convolution will have 2N7 1 points Computation of each of the outputs requires approximately N2 computations The overall complexity for computing convolution is therefore 0 2 But here is the neat thing We compute the DFT of x and the DFT of y multiply the points in the frequency domain then transform back X DFTxk Yr DFTQk Zr XrYr 2k IDFTZT This sure seems like the long way around the barn But consider the number of computations if we do the DFTs using FFTs Each transform requires ON log N operations the multiplication is 0N and the inverse transform is ONlog2 N The overall computation is ONlog2 N That s how orders are computed So it requires fewer computations by far than straightforward convolution at least of N is large enough This is in fact the way MATLAB computes its convolutions ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 13 This is also the way that symbolic packages such as Mathematica compute their multiplications of large integers Now the issues regarding use of the DFT for convolution Recall that the DFT always assumes that the signal is periodic This is the key to understanding the convolution The convolution is done on periodic signals where the period is the number of points in the DFT and the result of the convolution is periodic also Suppose that we are dealing with Npoint DFTs We can de ne a convolution which is periodic with period N by N71 yk fie 91c Z fnglc7n 710 The notation k 7 is used to indicate that the di erence is taken modulo N Suppose N 10 and fk is a sequence 6 points long and gk is a sequence 10 points long Draw sequences and their lOperiodic extensions Show graphically what the periodic convolution is The periodic convolution is the convolution computed when DFTs are used Suppose we don t want the effects of the circular convolution we just want regular linear convolution What we need to do is zero pad lf fk is a sequence of length N and gk is a sequence of length M then their convolution will have N M 7 1 points If we take a DFT with at least that many points there will be no wrap around Show pictures ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT Objective To investigate the discrete Fourier transform which is a numerical way of computing Fourier transforms The DFT We have seen that the Fourier transform can be used in a variety of applications While an important theoretical tool there is a problem with it in practice we must have an analytical expression for the functions we are transforming and have to be able to compute its transform In practice the transforms are often computed from discrete samples of a signal and the transform is computed for only a discrete set of frequencies This computational approach is known as the DFT There are fast algorithms for computing the DFT which are called the Fast Fourier Transform FFT The FFT is nothing more than a way of organizing the computations in the DFT to compute exactly the same thing but with less processing for the computer It is safe to say that the revolution in signal processing has its genesis in the discovery of the FFT algorithm We will begin my making the connection between continuoustime signals with the spectrum and the DFT signals in their discrete time and frequency domains Let be timelimited to 739 seconds having spectrum Fwi Then since is timelimited it cannot be bandlimited why Let denote the sampled signal with samples taken ever T seconds and let F60 denote the spectrum of the sampled signal the periodic extension of Fw repeating ever 75 lT Hz Because f is not bandlimited there must be some amount of aliasing ow let us imagine sampling in the frequency domain of Fw this corresponds to creating a periodic repetition of the sampled signal in the time domain We let To be the period of repetition in the time domain corresponding to samples every lTo of the spectrum ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 2 Let us determine how many samples are involved here The number of samples in the time domain of each period is To N i 0 T The number of samples in the frequency domain of each period is F lT 7is 0 F0 1T0 NO The aliasing can be reduced by increasing the sampling frequency but can never be entirely eliminated for a timelimited signal If we had started out with a ban dlimited signal then it would not have been timelimited and we would have had overlapping in the time domain If in addition the signal that we are dealing with is not in fact timelimited but we must for reasons of practicality deal with a timelimited version we must perform some truncation This truncation leads to spectral leakage This also causes aliasing creating higher spectral components than might have been in the original signal The spectral leakage can be reduced by increasing the window width longer data set This increases To which in turn reduces for Note that 70 determines the frequency resolution Also observe that by this sampling property we are getting only a partial view of the spectrum A true spectral peak might not lie right on one of the sample values This can be mitigated by sampling more nely decrease f0 meaning increase T0 meaning increase N0 Let be a discretetime sequence possibly obtained from a continuoustime signal by sampling say fkTi Note that we are using k as the discrete time index Suppose t at we have No samples of the signal where N0 is some number that we choose As a point for future reference the number No is commonly chosen to be a power of 2 since this works most efficiently for most FFT routines Following the book s notation let ft Tm TfkT 16m That is it is simply a scaled version of the time sample Often this scaling is overlooked or it is assumed that the sampling interval is normalized to one Also let FT F Two That is it is a sample of the spectrum The DFT of the set of points 1 f1 i i fNO1 is given by N071 N071 FT Z fkeijr ok Z fkeijwrrkNo 1 k0 k0 where 90 27rN0 oni In the transform formula the number 7 must be an integer It is an index to a frequency as we will see later The inverse DFT is 1 N071 1 N071 i F jr ok 7 F jQerNo 2 ft Nogre Negre ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 3 The transform pair is sometimes represented as fkltZgtFr Fr flflcl Note the interesting parallels between these transforms and the FiTis we have already seen 1 In going from the time domain k to the frequency domain r the exponen tial term in the summation has a negative sign 2 In going from the frequency domain to the time domain the exponential term has a positive sign and the summation is multiplied by a normalizing factor lNo in this case It should be pointed out that while the sampling processing introduces possible aliasing and spectral leakage problems the actual transform pair given above is exact Let us connect the de nition given above with the conventional Fourier transform noting where approximations are made The sampled signal can be written as 7 N071 fa Z fkT6t 7 m lC0 time limited The Fourier transform of this signal is N071 V E Z fkT57 WT lC0 If we neglect the aliasing over the interval lwl lt us2 by the sampling theorem we ave 1 FQU TF Hence N071 FM TFw T Z fkTe j WT M lt psi2 lC0 Sampling this now we obtain N071 F FWD T Z fkTe j W T Let wOT 00 then 90 wOT 27rF0T 27rN0 By our de nition TfkT fk Putting these de nitions together we nd N071 Fr Z fkwmok lC0 We conclude that except for aliasing the DFT represents a sampled version of the FT Taking the last expression for FT multiply by e 1mg and sum N071 N071 N071 E Frejm or 2 2 fkeijk okejm or r0 7 0 k0 ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 4 We nd how that N071 Z 51m7k907 7 0 N0 k m mod N0 0 otherwise Hence the sum collapses and we get the desired result The value FT is said to provide information about the rth frequency bin lt corresponds to a Hertz frequency of 5 fT9027VTf0 TTo Take some examples r 0 A f 0 rlgtfFsN0Tii 0 This is the frequency resolution 7 N02 A f FsZ This is the maximum representable frequency The number of points in the DFT can be written as T N0 7 0 T a where T0 relates to the sampling rate in the frequency domain and T relates to the sampling rate in the time domain Observe that to increase the frequency resolution the number of points of data No must be increased We can increase N0 and improve the frequency resolution by increasing T0 taking more data which amounts to taking samples closer together in frequency f0 lTo or by taking samples faster in time increasing the sampling rate Note The book de ned the transform in terms of fk TfkTi In practice the FFT routines simply deal with the data fk they don t worry about whether it is scaled or not Since the effect of the scaling by T is to simply scale the transform in applications it is not common to worry about the scaling either Example 1 A signal has a duration of 2 ms and an essential bandwidth of 10 kHz What is its absolute bandwidth We want to have a spectral resolution of 100 Hz in the DFT Determine N0 the number of points in the DFT By the sampling theorem we must sample at least double the highest frequency which is B 10000 Let F5 2B 20000 samplessec The resolution is F0 100 Hz The signal duration is To lFo 10 ms Here is an interesting thing to get the spectral resolution we need we need 10 ms of data when in fact the signal only lasts for 2 ms The solution is to take the 2 ms of data then pad the rest with zeros This is called zero padding Then E f0 In practice we would probably want No to be a power of 2 so No 256 is a better choice This could be obtained by decreasing T which would reduce aliasing or increasing To which would increase the resolution 1 N0 200 Note that zero padding cannot replace any information that is not already present in the signal It simply re nes the sampling of the spectrum that is al ready present ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 5 Aliasing and Leakage There are two effects that are introduced into the computation of the DFT Aliasing Since when we compute we are necessarily dealing with a timelimited set of data the signal cannot be bandlimited The sampling process with its incumbent spectral duplication therefore introduces aliasing This aliasing effect can be reduced by sampling faster Leakage If the function xt is not really time limited then we truncate it in order to obtain a nite set of samples As viewed above the mathematics sees the sampled signal as if it were periodic in time There are two ways of viewing what is going on First if we have a function 950 we can obtain a timetruncated version of it by W 0100 where yt is the truncated version and wt is a windowing function In the frequency domain the effect is to smear the spectrum out Yw 5X60 WW This smearing is spectral leakage Another way of viewing the leakage is this if we truncate a function then make it periodic the resulting function is going to have additional frequency components in it that were not in the original function due to the change from end to end The only way this does not happen is if the the signal is periodic with respect to the number of samples already Leakage can be reduced either by taking more samples wider windows of data ice increasing No It can also be reduced by choosing a different window function However it can never be completely eliminated for most functions Some examples In this section some examples of FFT usage are presented by means of MATLAB f 100 Z frequency of the signal fs 400 Z sampling rate N0 128 Z choose the number of points in the FFT f0 fsNO 39Z compute the frequency resolution f0 3125 Hz k OzNO l 392 range of index values fin cos2piffsk 39Z input function plotkfin Z plot the function ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 7 Note that the function ends at the end of a cycle its periodic 7 extension is the same as the function 7 fout fftfinN0 7 compute the FFT plot kabsfout 7 we have to plot absfout since fout is a complex vector 2D 4D EEI ED mu 12D MEI note that there are exactly two peaks This is because the frequency was a multiple of the resolution The bin with the frequency peaks is bin 32 and bin 96 128 3296 since ffO 32 Note the indexing in Matlab starts from index1 This means that index 1 corresponds to bin 0 Hence bin 32 is in fout33 fout33 64 0i 7 fout97 64 0i 7 7 Now let s change the frequency and do it again f f0 7 set the frequency to the lowest resolvable frequency fin cos2piffsk 7 function plotkfin 7 plot the function fout fftfinN0 7 compute the FFT plot kabsfout ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 2D 4D EEI ED mu 12D 1 El 7 7 Now let s try a frequency that is not a multiple of the 7 frequency resolution f 51 7 Note that ffO 1632 which is not an integer bin number fin cos2piffsk 7 function plotkfin 7 plot the function fout fftfinN0 7 compute the FFT plot kabsfout ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 8 5m 4m an in m z u 4n an 7 Note that the time function does not end at the end of a period 7 The transform does not occupy just one bin there is spectral 7 leakage The peak occurs at bin 16 the nearest integer to the 7 true real frequency bin ED mu 12D MEI 7 Now let s examine the effect of zero padding on this problem 7 increasing N0 Using the same frequency add on 128 zeros to the 7 set of samples fin1 fin zeros1128 foutl fftfin1256 plot O255absfout1 an 5m 4m an in m an mu 15D 2mm 25m 3 Note that the zero padding did nothing to improve the spectral leakage Now let s examine the effect of the number of samples on the spectral resolution Suppose that we have a signal that consists of two sinusoids f1 51 Hz and f2 53 Hz We will keep the same 7 sampling rate To begin with we will take 128 points of data fin cos2pikf1fs cos2pikf2fs plotkfin ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 9 fout fftfin128 plot kabsfout 7 The frequency resolution is f03125 Hz The frequencies we wish to 7 distinguish are too close to both show up 7 Now let s increase the number of sample points up to 512 This gives 7 a frequency resolution of f0 07813 k2 0511 fin2 cos2pik2f1fs cos2pik2f2fs plot k2fin2 ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 10 fout2 fftfin2512 plot k2absfout2 7 In this case we are able to distinguish between the two 7 frequencies 7 Now suppose that instead of taking more data we had simply decided 7 to zeropad out to 512 points 397 finl fin zeros1384 7 512 points plotk1fin1 foutl fftfin1512 plot k1fout1 ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 11 7 Note that we have not increased the spectral resolution We have 7 only provided a more finely sampled version of the spectrum we saw 7 with 128 points The FFT The FFT is a way of organizing the computations necessary to compute the DFT in such a way that the same work is done but with less effort I like to think of this as a bicycle analogy lfl ride my bike from home to work I use the same engine me as ifl walk in But by organizing my e orts better by means of wheels and gears the engine is able to work more efficiently and I get here faster To gauge the improvement let s rst approximate how many computations are necessary to compute the DFT lfl have No data points I can compute one of the DFT outputs by the formula N071 FT Z fkeijwrkrNo kio There are NO terms in the summation each of which requires a multiply naturally in the name of efficiency we would precompute and store all the complex exponential factors So each points requires N0 multiplyaccumulate operations There are No points in the transform so the overall DFT takes about N3 multiply accumulates If No 1024 this turns out to be a whopping 1048576 multiplyaccumulates We ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 12 would say the complexity is 0N02 where the 0 means order of which is to say in the ballpark of77 The FFT is able to reduce the computational requirements to about 0N0 log2 N0 For the case of N0 1024 this turns is 10240 operations which is more than 100 times faster And it provides exactly the same result This speedup has enabled some algorithms to be developed and successfully deployed that never could have happened Note that this speedup is entirely independent of the technology It was 100 times faster 20 years ago and will be 100 times faster 20 years from now The discovery of the FFT laid the foundation for modern DSP as well as a variety of computational disciplines One of the morals of this story is that it pays to pay attention to how the computations are done We will not go into two many details of how the FFT works 7 we need to leave something to ECE 5630 We can however give a brief summary The basic technique is divide and conquer we take a problem with No points and divide it into two problems of N02 points Since the complexity goes up as the square of the number of points each of these N02 problems is four times as easy as the No problem If we can put these two problems together to give the overall answer then we have saved computations We then take each of these N02 problems and split them into N04 problems each of which is easier and so on At every level we split the number of points that go into the computation until we get down to a DFT in just two points This is easy to compute This subdivision shows why the number of points must be a power of two we split by two at every stage in the process This also shows why the complexity has the factor of log2 N0 in it we can split No by two that many times All good routines to numerically compute the DFT are based upon some form of FFT Convolution using the DFT We have seen the convolution theorem over and over convolution in time is the transform of multiplication in the frequency domain By numerically computing the transform using the DFT we can compute convolutions of sequences There are some issues to be very careful of however since the DFT imposes certain require ments on the signals We will worry later about this For the moment consider the computational complexity Suppose I have a sequence x of N points and another sequence y also of N points We know that the convolution will have 2N7 1 points Computation of each of the outputs requires approximately N2 computations The overall complexity for computing convolution is therefore 0 2 But here is the neat thing We compute the DFT of x and the DFT of y multiply the points in the frequency domain then transform back X DFTxk Yr DFTQk Zr XrYr 2k IDFTZT This sure seems like the long way around the barn But consider the number of computations if we do the DFTs using FFTs Each transform requires ON log N operations the multiplication is 0N and the inverse transform is ONlog2 N The overall computation is ONlog2 N That s how orders are computed So it requires fewer computations by far than straightforward convolution at least of N is large enough This is in fact the way MATLAB computes its convolutions ECE 3640 Lecture 9 7 Numerical Computation of the FT the DFT 13 This is also the way that symbolic packages such as Mathematica compute their multiplications of large integers Now the issues regarding use of the DFT for convolution Recall that the DFT always assumes that the signal is periodic This is the key to understanding the convolution The convolution is done on periodic signals where the period is the number of points in the DFT and the result of the convolution is periodic also Suppose that we are dealing with Npoint DFTs We can de ne a convolution which is periodic with period N by N71 yk fie 91c Z fnglc7n 710 The notation k 7 is used to indicate that the di erence is taken modulo N Suppose N 10 and fk is a sequence 6 points long and gk is a sequence 10 points long Draw sequences and their lOperiodic extensions Show graphically what the periodic convolution is The periodic convolution is the convolution computed when DFTs are used Suppose we don t want the effects of the circular convolution we just want regular linear convolution What we need to do is zero pad lf fk is a sequence of length N and gk is a sequence of length M then their convolution will have N M 7 1 points If we take a DFT with at least that many points there will be no wrap around Show pictures ECE 3640 Lecture 9 i The Discretetime Fourier Transform Objective To learn about the discretetime Fourier transform DTFT which provides a spectral representation for discretetime signa s Transforms we have met and loved We have studied this year a variety of transforms Laplace transforms which are useful for system analysis including transient and stability analysis By evaluating at s jw we explored also the concept of frequency response Ztransforms which are the transform appropriate for discretetime systems Like the Laplace transform it can be used for transient analysis stability analysis and by evaluating at 2 eJWT we get the concept of frequency response Fourier series which are used to provide a representation of periodic signals This has some application to circuit analysis for periodic signals and leads by taking a limit to signals of increasingly longer period to the Fourier transform We also saw that we can take the idea of series representations of functions and use a variety of other basis functions for other useful representations Fourier transforms which can be used to examine frequency response of signals y means of their properties we are also lead to consider concepts such as modulation Fourier transforms do not really address the stability issues that Laplace transforms do nor can they be used as conveniently for transient analysis However by not starting at t 0 they simplify some other issues Two more transforms are introduced The Discretetime Fourier Transform is to the Ztransform What the Fourier transform is to the Laplace transform That is we have an exact frequency component representation of signals that are not periodic by evaluating a possibly twosided Ztransform at 2 em The DTFT is the study of this set of lecture notes The Discrete Fourier Transform DFT can be used to compute a transform of a nitelength discretelysampled set of data The DFT can be used for computational signal analysis and its implementation in the form of the FFT is very common However because the signal is truncated in time and in frequency it does not provide an exact frequency analysis although there are techniques to get close enough in practice The Discretetime Fourier Transform DTFT Recall that the Ztransform is Fe Empire 710 The DTFT is de ned as 00 FM Z flnleimn ECE 3640 Lecture 9 7 The Discrete time Fourier Transform 2 Clearly if is causal the DTFT is the Ztransform evaluated on the unit circle Just like the FT is the Laplace transform evaluated on the jw axis Observe that FQ is 27rperiodic FQ FQ 2 Again we see this idea of the periodic repetition of the spectrum in the frequency domain and the source of aliasing Note that FQ is a function of continuous frequency 9 7 we are not looking at samples of the spectrum as for the DFT and hence the function does not have to be periodic But FQ is periodic and hence FQ has a Fourier series representation its RS coef cient are just the samples But this representation allows us to write down an inverse DTFT to go from FQ to k simply stick things in the formula for the RS coef cients where the period of the function is 27r fk mek da Need we point out that yet again in going from time domain to frequency domain the exponent has negative sign and in going from frequency domain to time domain the exponent has a positive sign Notationally we will write k 42gt F And as for other transforms we can talk about the amplitude and phase spectra Example 1 Find the DTFT of k akuUs FQ Zake jnk 717 15710 k20 No surprise there Magnitude response 1 mm 1 7 acosQ as1nQ Phase response AFQ itan 1 liacosQ Show plot Interpret the frequency axis The frequency 9 7r represents half the ECE 3640 Lecture 9 7 The Discrete time Fourier Transform 3 sampling rate Any higher frequencies get Wrapped back around 1 Example 2 An example that leads to some important insight When dealing With the DFT is the discretetime rect functioni k 1 lkl SN 0 otherwise Then eemwm emN N FQ 2 wk em 71 k7N See summation formula on p 64 Then doing the old trick of pulling out enough exponent to produce real trigonometric functions we get 57102 eijn2N12 7 ejn2N12 sin2N 129 e jQ2e jQ2 7 5102 sinpm FQ Plot this When does it cross the axis This is kind of like a sinc function except ECE 3640 Lecture 9 7 The Discrete time Fourier Transform 4 that it is periodic 1 Comment on spectral leakage Example 3 We can also compute an inverse transform Let FQ rectQ7r2 and its periodic repetition Then mew 991 k 4 7 27quot 7W45 74SIDC 7r i System analysis using the DTFT For a discretetime system with input signal and impulse response Mk the output is ylkl 1Wquot hlkl The discretetime convolution theorem says that we can transform this to get YQ Same sort of stu we have seen all year long We will nish the story by an example Example 4 Let Mk 05kuk and k 08kuki Find the output We know that we could convolve this but we will instead to illustrate the point use the convolution theorem We can nd from our previous example if nothing else that l em FM 178519 em 7 8 l em 17 55 19 em 7 5 We nd 9 n J J Yam 5 e em 78 51975 ECE 3640 Lecture 9 H The Discrete time Fourier Transform 5 Taking the inverse transform by mean of PFE just like we would have done for the Ztransform we get MQP 5V 8WMH Properties of the DTFT 1 va H FHD MW e Win 1 H k0 H FWB j n fkejk95 H Fm 7 as f1kf2k H 171M F261 Parseval HP7quot 939 mw wmwm ECE 3640 Lecture 1 Discretetime systems Objective To learn about discretetime systems To learn about numeric solution of difference equations To learn about analytical solution of difference equations including the zeroinput response and the zerostate response To investigates sta bility issues for discretetime systems Reading pp 5407616 Now we are ready to make a change of direction Up till now we have focused on continuous time systems Now we will look at discretetime systems This I hope will reinforce some of the stuff we have seen Where do these things come from CD discretetime system DC There is a sample interval T Many systems have an intrinsically de ned period days weeks months etc It is common to write ykT I may get sloppy on the parentheses and the brackets Example 1 A sampled signal suppose Acosw0t90 and we sample every T seconds k fkT Acosw0Tk 90 Let 90 wOT k Acos00k 90 We get a new frequency 00 whose units are in radians per sample The amplitude does not change the phase does not change Now consider a speci c example Suppose we 27r1000 A lOOOHz signal Let We get f k so 90 7r2 Plot this Now let T 1 What happened 1 1 Now let T m 7 W What happens 1 T 7 1 7 4000 Acos27r1000l4000k Acos7r2k Example 2 An example of a discretetime Bank deposit Bank balance Bank pays some interest every period 7 Then the money goes as ylkl ylk 1l Tylk 1l flkl The money at the end of the k period is the money that was there plus the money due to interest plus any new deposits Draw the block diagram realization 121 Example 3 If yt then M lm ylkl m m iflk e 1 1 Instead of using RLC the elements in discretetime systems are delays adders and multipliers Comment on advantages precision stability exibility variety size storage reliability sophistication sharing cost ECE 3640 Lecture 1 7 Discrete time systems 2 Some useful signal models for discretetime Discretetime unit impulse 6W 6w 23 Discretetime unit step uk gt MW 1k70 0 klt0 Discretetime exponential 4 yk grows When l yl gt 1 and decays When l yl lt 1 Plot on unit circle What about When M 1 We can Write this as Pij for some 9 This is a rotating phasori Discretetime sinusoid cosQk 6 Note Not all discretetime sinusoids are periodic unlike in the continuous time case flkl flk Nol This is only possible if 9N0 is an integral multiple of 27r cosQk cosQk N0 iii 9N0 27rm or Q 27r 7 N0 Must therefore have Q27r be a rational number Note There is nonuniqueness of discretetime sinusoidsi For example cos9i67rkt9 cos87rkli67rkt9 cosli67rk9 cos7li47rkt9 cos0i47rk79 All these frequencies look the same Exponentially damped sinusoid VIC cosQk 9 Some useful signal operations Essentially the same as for continuous time Time shifting k ml Shift left by m etc Time reversal ik Time compression Decimation glkl fl take every other point Time expansion glkl flit2 When kZ is an integer ECE 3640 Lecture 1 7 Discrete time systems 3 Difference equations The equations that arise in discretetime systems are not di erential equations but di e rence equations We could write yknan1ykn71 a1yk1aoyk 7 bmfkmbm1fkm71 b1fk1bofk advance operator form It could also be written as by k A k 7 n ylklan71yk 139 a1yk7n1laoylk7nl bnflklbn71fk 139 biflk n1lboflk nl delay operator form Numerically it is straightforward to nd solutions of the system equation given some initial conditions 31 an71ylk 1l an72ylk 2liquot39iaoylk nbnfkbn71flk 139quot l boflk n Just propagate forward Example 4 Fibonacci series y1 1 y2 1 yn 7 1 yn 7 2 1 Example 5 yk 7 05yk 7 1 Suppose we know y71 16 and k2 yk 05yk 71fk y0 0506 0 8 y1 0581 5 y2 055 4 65 etc 1 We will use E to indicate the advance operator E k k 1 etc Example 6 yk 2 iyUs 1 1176yk k 2 1n operator notation E2 1E i k 7 E2fk 4 16 y 7 A lot like what we did for di erential equations 1 We can write the general nth order di erence equation as Equot aHEW1 a1E aoyk WEquot bn71En 1 b1E bomk or QlElylkl PlElflkl Now we do the same kinds of things we did before the zeroinput response then the zerostate response Zeroinput response When there is no input we can write QlElyolkl 0 En aann l a1E aoyok 0 ECE 3640 Lecture 1 7 Discrete time systems 4 What happened for continuous time Similar Let s try a simply case to get starte E Wyolkl 0 Try a solution y0k C yk Comment on the di erence from earlier casei Substi tute in and show that it works EC39ylC cvk1 This works in the general case subs and show that it works Substituting gives n an717n 1 39 39 39 11W a0y0lkl 0 or QlVlyolkl 0 For an interesting nontrivial solution we will look for roots of QM 7 0 Write as V7V1V7V2v7vn 7 0 QM is thus the characteristic polynomial and we look at its roots The roots are V1 VQVHWW As before we take all possible solutions in a linear combination yon C1vl cw cw Repeated roots lf QM 7 v 7 WW 7 WNW 7 Vr239 v 7 m then yolk 7 c1 cak erkHM wwa cw So how do things behave as a function of root location 08 08 75 12 M08 1 etc Same old same 0 Example 7 Solve ylk 2 7 076m 17 016 7 51 2 with y7l 0 and y72 254 and 4 kuk E2 7 06E 7 016mm 7 5E2fk Characteristic polynomial 42 7 06y 7 016 7 39y 02m 7 08 7 0 y0k 7 c1702 cQ08 C At k 71 0 i 5 5 7 Ci 162 At k 72 25 254 25c1 E62 So c1 15 and CQ 45 We will get the zerostate solution lateri ls this asymptotically stable 1 ECE 3640 Lecture 1 7 Discrete time systems 5 Complex roots With roots y l yleji then ylkl ClVl C gtka 9 with c and 9 arbitrary constants same steps as before Example 8 E2 7156E 81mm 7 E 3fk y l 2 and yli2 1 Characteristic polynomial 42 7156y 81 0 Factor 39y 7 78 7145M 7 78 3145 7 0 Roots 78 i j45 Convert to polar 41 erW6 42 Qe jWG Zeroinput solution yolk c9lC cos7r6k 9 Need to nd c and 9 using the initial conditions At k fl 2 igcos77r6 9 At k 72 C l cos77r3 9 Using cosa b cosa cosb 7 sina sinb p 65 1 2 7 ccos9 cs1n9 l ccos9 sin9 Solve for unknowns c cos9 and csin 9 ccos9 2308 csin9 7397 9 717 rad c 234 Zerostate response The steps are similar to what we did before introduce delta function then the impulse response then the convolution sum Discrete time impulse function 1 k 0 lkl 7 0 otherwise Plot We have the discretetime impulse response Mk ECE 3640 Lecture 1 7 Discrete time systems 6 Then Mk is the solution when initial conditions are all zero H71 H72 h7n 0 We can nd a numerical solution by substitution Example 9 yk 7 0 6yk 7 l 7 16yk 7 2 5fk Mk 7 6hk 7 il6hk 7 2 56W with H71 H72 0 5 hl 3 etc How long does this go on Comment on HR vsi FlRi A closed form solution may be obtained from W 7 we yolklulkl where A boaoi 1 Example 10 yk 7 0 6yk 7 17 0 16yk 7 2 5fk E2 7 06E 7 0 16yk 7 5E2fk y0k 7 c170i2k cQ0e8 C Mk 7 0 c170i2k CQ0i8kus Need to nd constantsi At k 0 Mo 7 0 6h717 0 16h72 7 5 h1 7 06m 7 0 16h71 0 h05hl37gtc1lcQ4i 11 Zerostate response Observe that we can write flkl fl0l5lkl fl1l5lk 71l Zflml k 7 ml Now we add up the response of the system to each of these outputs fl0l5lkl A flolhlkl fl1l5lk 1l A fillh k 7 1 Adding these up ylkl Zflmlhlk ml Same sorts of properties as we ha before Commutative f k f2k f2k f k DistributiVe fllkl lekl fslkl fllkl lekl f1lkl fslk Associative frlkl f2lkl r fslkl 7 wk r f2lkl r fslkl Shifting f1k 7 m f2k 7 n ck 7 m 7 n Convolution with impulse k 6k k ECE 3640 Lecture 1 7 Discrete time systems 7 Width If f1 has length m points and f2 has length n points then f1 f2 has ength m n 7 1 points Note length given in points For causal systems with causal inputs My ylkl flmlhlk 7 ml 0 3 H Example 11 Find ck gk when 018kuk and gk 013kuk 1c 4k Zmlswmlg w m 0 8 m 7 k ck 7 013 Z lt03 m0 Important fact emblazon this in your heads Also be aware that symbolic packages know this The sum of a geometric series is We get OS013 7 1 Clkl BMW 2l 8k1 3k lulkl 1 Example 12 The problem we have seen before yk 2 7 16yk 1 7 116yk 5fk 2 with k 44mm hkl i QVC 4 8klulkl ylkl hkl flkl Use tables and a lot of simpli cation 1c 1 7 7 1c 1 1c 1 7 1c 1 75105125 C1 7 2122712 1 712718 C1uk 71126125 C 1444712 C 518118 Cuk 1 Total response zeroinput component zerostate components Example 13 Take the same system as before with y71 0 y72 2541 Then yk12712k 1818 C 71126125 C 1444712 C 518118 C ECE 3640 Lecture 1 7 Discrete time systems 8 Natural and forced response The total solution may be divided into a natural and forced response just like we did before The natural response is those components of the total response Which have the natural modes of the system The forced response is everything else Which must necessarily come from the forcing function For the last example yk i64472k 6618 C 712625 C System stability Plots as a function of pole location Asymptotically stable unstable marginally stable BlBO stability System response to bounded inputs ylkl hlkl flkl lylkll Zhimmk 7m S Zlhlmlllflmikll For bounded input 7 m lt K1 lt 0 lylkll S K1Zlhlmll Bounded if Em lhml lt 0 or all roots inside unit circle ECE 3640 Lecture 4 Fourier series expansions of periodic functions Objective To build upon the ideas from the previous lecture to learn about Fourier series which are series representations of periodic functions Periodic signals and representations From the last lecture we learned how functions can be represented as a series of other functions flttgt ickik k l We discussed how certain classes of things can be built using certain kinds of basis functions In this lecture we will consider speci cally functions that are periodic and basic functions which are trigonometric Then the series is said to be a Fourier series A signal is said to be periodic with period To if ftftTo for all t Diagram on board Note that this must be an everlasting signal Also note that if we know one period of the signal we can nd the rest of it by periodic extension The integral over a single period of the function is denoted by TO mm When integrating over one period of a periodic function it does not matter when we start Usually it is convenient to start at the beginning of a period The building block functions that can be used to build up periodic functions are themselves periodic we will use the set of sinusoids If the period of is To let we 27rT0 The frequency we is said to be the fundamental frequency the fundamental frequency is related to the period of the function Furthermore let F0 lTo We will represent the function using the set of sinusoids 2390t cos0tl 210 cosw0t91 2t cos2w0t92 Then ft C0 Z 0 cosnu0t 97 n71 The frequency nwo is said to be the nth harmonic of we Note that for each basis function associated with f t there are actually two parameters the amplitude C7 and the phase 97 It will often turn out to be more useful to represent the function using both sines and cosines Note that we can write C7 cosnw0t 97 C7 cost9n cosnw0t 7 C7 sin9n sinnw0t ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 2 Now let 1 C7 cos 9 b7 7C7 sin 97 Then C7 cosnu0t 97 a7 cosnw0t I sinnu0t Then the series representation can be t CoiCncosnw0t6n n1 00 a0 2 an cosnltu0t I sinnw0t n1 The rst of these is the compact trigonometric Fourier series The second is the trigonometric Fourier series To go from one to the other use C0 10 C7 wag b3 97 tan 17bna i To complete the representation we must be able to compute the coefficients But this is the same sort of thing we did before If we can show that the set of functions cosnw0t sinmu0t is in fact an orthogonal set then we can use the same formulas we did before Check 7 0 n y m TO cosnw0t cosmu0t dt 7 n m 7 0 So pairs of cosine functions are orthogonal Similarly n7 m 0 TO s1nnw0t s1nmwot dt 7 n m 0 So pairs of sin functions are orthogonal Also sinnw0t cosmu0t dt 0 for all n and m To So the sines and cosines are orthogonal to each other This means that we can use our formulas t COSW0tgt 2 an ltcosnw0t cosnw0tgt To TO COSltW0Q dt 7 t sinnwotgt 7 3 bn 7 ltsinnw0t sinnw0tgt 7 To To Emmet dt The only exception is the coefficient 10 ltft1gt 1 WW rozgmdt Example 1 Let us start with a square wave ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 1 7W2 t 7r2 ft 0 teizj lmmlwl and its periodic extensions The period is To 2 so we 27rT0 1 The series is t 10 Zancosnt bnsinnt The coefficients can be found as follows 1 quot2 1 7 dt 10 27r 42 2 1 7r2 2 0 71 even an cosntdt isinmr2 73 n 15913Hi 7 42 quot7 1 n371115w 1 M2 bn sinnt dt 0i 7quot 77r2 We can Write 1 2 l 1 l ft costigc083tgcos5ticos7tgti Here is an interesting tidbit Evaluate this at t 0 1131 1 1 2 7r 3 5 7 Solving we get In the compact form 1 C0 i 0 71 even C7 737 71 odd 11 It is interesting to see how the function gets built up at the pieces are added ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 4 together The Fourier Spectrum For a function having a compact trigonometric Fourier series the set of am plitudes C7 and the set of phases 97 provide all the information necessary to represent the function This is interesting if you think about it a function which is de ned at every point in a continuum can be represented with only a countable number of points A plot of the amplitudes C7 vs the w is the amplitude spectrum of the signal A plot of the phase 97 vs 1 is the phase spectrum of the signal Example 2 Show the magnitude and phase spectrum of the square wave from the previous example Actually if we allow the amplitude to show a shift of 7r by allowing a signed ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 5 quantity then the task is somewhat easier In this case the spectrum is said to be an amplitude spectrum rather than a magnitude spectrum The amplitude spectrum is convenient to work with whenever all the sine terms are zero so all the information is conveyed in the an Example 3 Find the Fourier series of the following signal and plot its magnitude and phase spectrum The signal is periodic with T0 2 The fundamental frequency is 27r we 2 7r The function can be written analytically for the purposes of integration as 2At 1 t 2 f 22104 gtg This gives is only one period of the function but that is suf cient for our purposes The Fourier series coefficients can be written as 2 32 17 7 ftgtcosmrtdt To 712 12 32 2At cos mrtdt 2Al 7 t cos n7rtdt 712 12 0 We will take this at face value for now Soon we will learn some tricks that will help evaluate this sort of thing sometimes But notice the utility of being able to use a symbolic integration package You may want to go back and review ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions What we did early last quarter With MATLAB the symbolic integration exercises were Written With this sort of integration mind 2 32 bn 7 sinnwtdt To 712 12 32 2At sinn7rtdt 21417 t sin mrtdt 712 12 sinn7r2 7127392 Actually I checked this using my current favorite symbolic tool Mathematical This is the resu t In6 bu Integrate 2 A t Sinn Pi t t1212 Integrate 2 A 1 t Sinn Pi t t1232 1 Pi 1 Pi A 11 Pi COS 2 Sin 2 2 Dut6 lt 2 2 nPi 1 Pi 1 Pi A 1 Pi Cos 2 Sin 2 2 gt 2 2 1 Pi 1 Pi A 1 Pi Cos 2 1 Pi 2 A Sin 2 2 gt 2 2 1 Pi 3 1 Pi 3 1 Pi A 1 Pi Cos 2 Sin 2 2 gt 2 2 1 Pi In7 Simplifyb11 n Pi 1 Pi 1 Pi 2 4 A 1 Pi Cos 2 Sin Sin 2 2 2 Out 7 ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 7 In problems of this sort it is considered bad form to leave it in terms of all the sins and cosines go thy way and sin no morel since they can occlude the underlying values of the coefficients So we will work through the detail to get the answer shown in the book In doing this however do not lose sight of the forest for the trees We already have the coefficients we are simply manipulating them a bit In practice these types of manipulations could be skipped or be done by a computer say if we were plotting the magnitude spectrum In the simpli cation note that the term sin2n7r2 is zero when n is even So we only need to consider odd n For odd n sin2n7r2 1 so we can focus on the other part First consider odd n of the form n 4k 1 Then cosn7r2 cos4k l7r2 cos7r2 0 sinn7r2 sin4k 17r2 sin7r2 1 sin3n7r2 sin34k 17r2 sin37r2 71 When n 4k 3 cosn7r2 cos4k 37r2 cos37r2 0 sinn7r2 sin4k 37r2 sin37r2 71 sin3n7r2 sin34k 37r2 sin97r2 1 Combining all this together gives the desired answer sing the symbolic toolbox in MATLAB I obtained syms A n t int 2Atsinnpit t 1212 3115 2A 2sin12npinpicos 12npi n 2pi 2 The Fourier series is ft ansin mt 8A 71 WW2 72 sinn7rt 7r n135 n 8A 39 2 2 w Sinn7rt 7r n135m n 8A 1 1 1 sm r 7 g sm37rt g sm57rt 7 E sm77rt To plot the Fourier spectrum the compact trigonometric Fourier series is needed Recall that this expresses the function in terms of cosines We only have it in terms of Sines We we have to do a little phaseshift trick sinkt coskt 7 90 7 sinkt coskt 90 t 0 To2 ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 9 Let us use these facts in relation to Fourier series Suppose we want to compute the FS of an even function such as the square wave signal example Then 1 ToQ 2 ToQ 7 t dt i t dt a0 To mm To f 2 ToQ 4 ToQ a 7 cosnw0tdt 7 cosnw0tdti To iToQ To 0 2 ToQ bn 7 sinmu0tdt 0 To fro2 To compute the FS of an odd signal 1 ToQ a ftdt0 0 To 7To2 2 To2 a 7 cosnw0tdt 0 To iToQ 2 ToQ 4 ToQ bn i Sinmotdt 7 sinnw0tdti T0 TOQ T0 0 Review the signals transformed so far in light of these symmetries Determining the fundamental frequency The trigonometric Fourier series can be used to represent any periodic functions In periodic functions every frequency in the Fourier series representation is an integral multiple of some fundamental frequency Such frequencies are said to be harmonically related The ratio of any two harmonically related frequencies is a rational number ie a number which can be represented as the ratio of two integers Interesting mathematical fact there are more irrational numbers than there are rational numbers Any number which involves a transcendental number such as 7r or e or which involves square roots which cannot be simpli ed down to ratios of integers such as is an irrational numbers For functions which are harmonically related the fundamental frequency is the greatest common divisor of the frequencies Example 4 ls the function f1t 2 7 cost 91 cos t 92 5 cost a periodic function If it is what is the fundamental frequency We need to determine if the frequencies are harmonically related We neglect the DC terms Taking ratios 1 2 2 g 4 which is rational l 3 2 7 7 g 7 which is rational 2 4 3 7 7 7 7 g 7 which is rationals So is a periodic functions The fundamental frequency is the greatest common divisor GCD12 23 76 161 ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 10 The GCDnumLCMdeni 1 Example 5 Is the function 3 sin3 t 9 7cos6t periodic The ratio of frequencies is m 7 7273 which is irrational 1 Example 6 ls ft 3sin3 t 19 7cos6 t periodic The ratio of frequencies is 3V E which is rational The fundamental frequency is GCD3 6 3V1 Interpretation of the smoothness of the function Functions which are smooth eig continuous have most of their variations at lower frequencies Functions which are not smooth have variations at higher frequencies We can look at the rate of decay of the amplitude spectrum to determine something about the smoothness of the function For example the square wave function has abrupt jumps and is not even contin uous The coef cients of the Fist decay as ln By contrast the sawtooth function we examined is smoother since it is continuous lts coefficients decay more quickly decaying down as ln The Gibbs phenomenon According to our theory with a complete set of basis functions we can represent any function exactly We furthermore know how to obtain the best approximation if we use only a nite set of functions Interestingly even the best approximation can still have some substantial errors Consider the error in the squarewave series Observe that there is a jump just before the point of discontinuity As it turns out no matter how large n is this error remains and it has an amplitude of about 9 of the discontinuity As 71 gets larger and larger this wiggle becomes narrower and moves closer to the point of the discontinuity but it never goes away This overshoot phenomenon is known as the Gibbs phenomenon One of the important rami cations of this is in how we de ne functions to be equal It is true that T 7 i0 C7 cosnu0t 972dt 0 that is there is zero error between the function and the Fourier series as de ned by this squared integral criterion But it does not mean that the functions are pointforpoint equal In this case the error region simply becomes so small that the integral is zero But this does not mean that ftgt 2 C7 cosmu0t 97 n0 ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 11 at every point The mathematicians who like to leave no such stones unturned have made this an object of tremendous study and consider such quali cations as equal almost everywhere as or equal with probability one These are both in distinction to equal everywhere or equal always We have to be careful what we mean when we say two things are equal Ayn Rand would probably have trouble with this perhaps it is not the case that A A is always true Using Fourier Series for Signal Analysis Suppose we have a system with transfer function Hs and a periodic input signal What is the output signal One way to do this of course is to convolve the input signal with the impulse response But we all know how much we love convolution and there is not a lot of insight to be gained from such a brute force computation Another approach is to represent in terms of sinusoids then use the properties ofLTl systems Speci cally if ft C0 2 C7 cosnw0t 9n n1 then the output will be the sum of the responses due to each input yt C0H0 chlHOnwo cosnw0t 9n AHjnw0 n1 Discuss what happens in terms of ltering In the homework you will work an example of this Exponential Fourier Series We have seen how sin and cosine functions can be represented in terms of complex exponentials It turns out that we can use complex exponentials to represent Fourier series In many respects this makes for a simpler representation et s go back to the compact Fourier series representation function and express it in terms of complex exponentials C7 cosnw0t 97 Dnejnwot Dne j7wot where 1 D7 gems D e jenC We can write the Fourier series 00 ft C0 2 C7 cosmu0t 97 n1 00 D0 ZDnejnwotJrDineijnuot n1 D0 ZDnejWot n0 00 Z Dnejnwot n7ocgt ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 12 Now how do we nd the coefficients First note that if we de ne the inner product correctly the exponentials are orthogonal Up to now inner products have been de ned for real functions We will extend this now to inner products over complex functions If and gt are a periodic complex functions with period To de ne the inner product as ltftgtgt T famdt where the overline means complex conjugate The rules for this inner product are the same as before except that ltf 9 9 f With this inner product note that ltejnwot ejmwgt ejnwote7jmwotdt 1 ej nim w 7 1 a To n 7 mw0 which is 0 if n 7 m y 0 and To is n m So under this inner product we have a whole set of orthogonal functions The geometry of orthogonal functions we talked about before applies including the orthogonality theorem We can therefore write D 7 jnwot 7 U BMW 7 1 7jnwotd n7PIOJft5 7W7 170 Tofwe t Derive this another way also Note that this is true for all values of 71 there are no special cases when n 0 and there is only one formula not two as for sins and cosines This is my preferred form In fact due to its similarity with the Fourier transform to be discussed soon it is the most common form of the Fourier series It is of course possible to convert from one form to another For example Dn gm 71b Suppose as is most often the case that is a real function Then 7 l 1 v t D7 7 fte JquotW0 dt 7 fteJquotW dt D77 T0 T0 To To Example 7 Find the exponential F s of the square wave function with period 27r o p 428 7r2 r Dn 167jmdtlsmn7r2 27r 7W2 2 TNT2 This is a good time to introduce a function that is near and dear to the heart of engineers sinx smc x 7 95 So we can write D7 sincn7r2 Note sinc0 1 How do we know 1 Important observation To compute the FIS coefficients multiply the function by an exponential with negative exponent There are many transforms that electrical engineers use 7 Laplace transforms Ztransforms Fourier series Fourier trans forms eth In all of these the exponent is negative Don t forget it ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 13 Exponential Fourier Spectra As for the trigonometric FS we can make a plot of the RS by plotting the mag nitude and phase of the complex numbers For the example above D0 12 Dol 12 4D0 0 D1 17r lDll 17r LDl 0 D71 17r lD1l17r AD1 0 D2 0 D2 0 When plotting the spectrum both positive and negative values of 71 need in general to be plotted Bandwidth of a signal The bandwidth of a signal is the amount of frequency required to sustain the signal unmodi ed Actually there are about a bajillion di erent de nitions for bandwidth depending on the application of the problem Example 8 Spectra on p 445 The bandwidth is the highest nonzero frequency 7 the lowest nonzero frequency 9 7 0 7 9 1 Example 9 The bandwidth of the square wave function is in nite What is often done from a practical power of view is to go out far enough 7 till the terms not included are small enough to worry about Just what is far enough depends on l the particular application Exalnple 10 In this example we will nd the RS of an important function the periodic set of pulses This is used as we will see in chapter 8 as a representation of the sampling process 6T0 t 60 7 71 ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 14 Plot and explains This is clearly periodic and hence has a F3 in some sense We can write 6 Z Dnejnwot n7ocgt where we can compute the coefficients from 1 7 39nw t Bu 7 6Tote J 0 dt T0 T0 Taking the integral from 71102 to T02 we get 1 To2 V t 1 D i 6t JquotW dti To To2 5 To This gives the important formula 1 v MOP Z 61 n7ocgt The spectrum does not decay anl TLC and 4D 0 1 Energy of signals and Parseval s relationships It is possible and often theoretically useful to examine the energy of signals in both the time domain and the frequency Fourier series domain We will develop an important relationships Suppose is a periodic function with FiSi representation t ZDMW n and gt is a periodic function with the same period and a FiSi representation gm ZEnejnuot 71 Now consider an average energy kind of term 1 gt ft9 Wt To To Substituting in for each of the RS gives taking advantage of the orthogonality of the exponential function 1 gt 7 gt T TO my welt i DnEn We can write this in a convenient inner product notations We can de ne the inner product between two series Dn and as Dm E Z D E n Then we can write using our complex inner product for functions Tiom glttgtgt ltDn Engt ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 15 A relationship such as this is known as a Parseval s relationship named after some guy As a special case take gt Then is the average energy of By the Parseval s relationship 1 TWO ltDn D7 0 Example 11 Find the sum of the series 7r 2 Zn s1ncn7r2gt By recognizing the terms from the Fist for a square wave with period 27r we can use Parseval s relationship 7r 2 1 quot2 2 1 Zn s1ncn7r2gt 7 g iwQ dt 7 i This would have been hard to do any other way 1 A return to the geometric viewpoint We have seen that functions can be represented as series of orthogonal functions and have seen examples of orthogonal functions the trigonometric and the complex exponentials Historically these were rst examined by Jean Baptiste Fourier who used these to solve the partial differential equations related to heat ow At rst his methods were considered unconventional by mathematicians Now the gener alization of Fourier s methods form one of the largest and most fruitful areas of mathematics Are there any other useful orthogonal functions Given a set of functions that are not orthogonal is it possible to make it orthogonal somehow Both answers are yes We begin looking at a set of orthogonal polynomials de ned over the inter val 711 It is easy to check that the set of polynomials 1 tt2t3 i is not orthogonal For example ltm3gt 11lttgtltt3gtdt Consider however the polynomials In general 1 d PFTWCzTn t2 7 1 ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 16 These polynomials are known as the Legendre polynomials It can be shown that 0 my n 77 1 PmtPntdt 2 71 2m1 For functions that are de ned over any nite interval Legendre polynomials can be used as a functional representation Another way that orthogonal functions arise is by means of another inner prod uct While we have not mentioned it in the past it is possible to introduce a positive weighting factor into the inner product Every one of these produces a new inner product each with properties that may be useful for particular applications If wt is a nonnegative function then we can de ne an inner product ltf ggtw I wtftgtdt where the subscript u indicates the weighting and I is some interval of integration I For example for w t an 71 1 we might de ne an inner product as 1 1 t t 7 t t dt ltf gtglt gtgtw 1 Mn M A set of polynomials that is orthogonal with respect to this norm is the set of Chebyshev polynomials T0t 1 ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 17 T t cosn cosilt For example T1t t T2t cos2 cosilt 2 cos2cos 1t7 1 2t2 71 T3t cos3 cosilt 4cos3cos 1t 7 3 coscos 1t 4t3 7 31 Notice that these have the equal ripple77 property This makes them useful in function approximation and in fact Chebyshev functions are used at the heart of the Remez algorithm Another set of interesting orthogonal functions that have been the topic of an incredible amount of research lately are wavelet functions Unlike the familiar and common trigonometric functions there are actually several families of wavelets this is part of what makes it confusing One type of wavelets is described by two sets of functions known as a scaling function and known as a wavelet function In dealing with these functions instead of looking at different frequencies we scale and shift these functions We de ne 45W 21724421137 k 1mm 217213 7 k Make plots and explain Then somewhat miraculously the following orthogonality properties exist 4 jmtgt 51cm Mica WWW 5115km lt jkta Wm 13 6jl6km These are pretty remarkable This gives us a whole bunch of functions that we can use to signal representations f0 ZaJk Jkt Z bjk jlct 1c M ECE 3640 Lecture 4 7 Fourier series expansions ofperiodic functions 18 This is useful for a variety of things which will become more clear after we talk about Fourier transforms next chapter But notice that we can represent any function not just periodic functions localizing both frequency information and time information There are also very ef cient algorithms that are faster than the Fast Fourier Transform FFT to compute a discrete wavelet transforms ECE 3640 Lecture 2 i Z Transforms Objective Ztransforms are to difference equations what Laplace transforms are to differential equations In this lecture we are introduced to Ztransforms their inverses and their properties We will also solve difference equations using transform techniques Introduction to the Ztransform As you recall we talked rst about differential equations then difference equations The methods of solving difference equations was in very many respects parallel to the methods used to solve differential equations We then learned about the Laplace transform which is a useful tool for solving differential equations and for doing system analysis on continuoustime systems Our development now continues to the Ztransform This is a transform technique used for discrete time signals and systems As you might expect many of the tools and techniques that we developed using Laplace transforms will transfer over to the Ztransform techniques The Ztransform is simply a power series representation of a discretetime se quence For example if we have the sequence x0 x1x2x3 the Ztransform simply multiplies each coefficient in the sequence by a power of 2 corresponding to its index In this example Xz x0 acmz l x2272 9494273 Note that negative powers of 2 are used for positive time indexes This is by convention Comment For a general causal sequence k the Ztransform is written as For a general not necessarily noncausal sequence k 00 FM 2 may k7ocgt As for continuous time systems we will be most interested in causal signals and systems The inverse Ztransform has the rather strange and frightening form 1 j szkildz T 27rj where f is the integral around a closed path in the complex plane in the region of integration Fortunately this is rarely done by hand but there is some very neat theory associated with integrals around closed contours in the complex plane If you want the complete scoop on this you should take complex analysis Notationally we will write Flzl Zfkl flkl Z 1Flzl flkl flkl H Flzl ECE 3640 Lecture 2 7 Z Transforms 2 Example 1 Find the Ztransform of k ykuUs 00 00 1 7 k2 71C 7 1C 7 Flzl7Zv2 ZWz W 1c0 k Recall the formula for the sum of an in nite series Remember it on your deathbed When does this converge 2 2 7 v The ROC is gt Compare with ROC for causal Laplace transform 121 FM Example 2 Find the following Ztransformsi 1 k 6 FM 1 ROC all 2 2 k FM zfli ROC gt 1 3 k cos ki l 2 2 22 7 cos F 7 7 7 7 Z 2 27em27e 1 22722cos l 11 Important and useful functions have naturally been transformed and put into tab ular form Inverse Ztransforms Given the nature of the inverse Ztransform integral we look for other ways of computing the inverse The approach is very similar to what we did for Laplace transforms We break the function down into pieces that we can recognize from the table then do table lookup As for Laplace transforms there will be a variety of properties delay convolution scaling etc that will help us The most important tool however remains the Partial Fraction Expansion However we will nd it convenient to modify it slightly for our purposes here 2 Example 3 Find the inverse Ztransform of FM 2 Knowing what we know it is straightforward to writ flkl 2kulkl Example 4 Find the inverse Ztransform of 82 7 19 F Z 2 7 2x2 7 3 In order to do this we need to expand using PFE into something like 12 22 272 273 FM because this is the form that we know about But recall that the PFE we have come to know and love always just has constants in the numerator So we will create a new function Let F 82 7 19 2 22 7 2z 7 3 ECE 3640 Lecture 2 7 Z Transforms 3 Now do the PFE on GM FM 7 7 k1 k2 kg 2 Glzlnz3 Using CUPI 719 3 k1 k2 k353 so we can write GM FM 4196 32 53 2 2 2 7 2 2 7 3 Now we solve for FM 19 322 532 F if 7 7 lzl 6 2 7 2 2 7 3 Note that by our little trick we have put this into the form we need Now we can read off the inverse directly 19 3 5 flkl ii5lkl WC 3klulkl 6 2 3 11 The point is Computing inverse Ztransforms using PFE is exactly analogous to computing inverse Laplace transforms provided that you form FM 2 rst There is another method of obtaining inverse Ztransforms which is useful if you only need a few terms Recall that the Ztransform is simply a power series All you need to do is nd the coefficients of the power series One way to do this is by long polynomial division This gives you a numerical expression for as many terms of as you choose to compute not a closedform mathematical expression Example 5 If FM 7 5 nd Work through the rst few 1 Properties of Ztransforms In the descriptions of these properties take m H FM Delay property This is very analogous to the differentiation property of Laplace transforms and will similarly allow us to solve differential equations k 71uk 71lt gt Z IFM So 2 1 is the delay operator As 3 is the differentiation operatori Also k 71uklt gt 2 1FM f71 Note the difference between these two This property is used to introduce the initial conditions when we use trans forms to solve difference equations Proof For the more general case of shifting by m Zfk 7 muk 7 ml 7 muk 7 mlzik Z k 7 mlzik k20 km ECE 3640 Lecture 2 7 Z Transforms Now make a a Change of variable let 7 k 7 m so that k 7 mi Zfk 7 muk 7 711 Z rkiourm Z ka 7 0 For the other case Zfk7muk 7 Z k7mw 2 WWW 27m f7kzlC 27ka k21 k 71lt gt 2 1F2 f71 k 7 2 lt gt Z QFM 2 1f71 f72 fk 7 3 H 3512 M71 2 1f72 1693 Left Shift Advance Similar to the last property k ka H szM 7 2 ka Example 6 Find the Ztransforrn of the sequence flkl HUM ulk 6l Plot this Write this as k kuk 7 kuk 7 6 kuk 7 k 7 6uk 7 6 6uk 7 6 Then 2 kuk lt gt W and Z uk 7 6 lt gt 276271 so 2 k 7 6uk 7 6 lt gt 276W Combining 2 2 2 267625 F 7 67 6767 lzl 2712 2 2712 Z 271 2524 ECE 3640 Lecture 2 7 Z Transforms 5 Convolution Like the convolution property for Laplace transforms the convo lution property for Ztransforms is very important for systems analysis and design In words The transform of the convolution is the product of the transforms This holds for both Laplace and Ztransforms lf f k lt gt F z and f2k lt gt F2Z then fllkl f2lkl 7 FllZlF2l2l Where denotes convolution in this case discretetime convolution Proof This is somewhat easier and more general to prove for noncausal sequences Zulikwgvsii Z Z filmlf2lk7ml Z Z f1mf2kim2 k k7oo m7ocgt Z fllml Z f2lk7ml 7k m7ocgt k7ocgt 2 mm 2 fgm w Z fllmlzim Z f2lTlZ TF1lZlF2l l Multiplication by W Multiplication by k Initial Value theorem For a causal k f0l gigolo FM Final Value theorem lfFz has no poles outside the unit circle ie it is stable 313010 fin gage 71gtFltzgt Solution of difference equations Example 7 Solve ylk 2 7 WW 1l 621W 3flk 1l 5flkl With y l and M72 and input Z kuUs First shift the equation so that we can take advantage of the form of the initial conditions We replace k A k 7 2 to obtain ylkl 7 521 71l6ylk 7 2 3flk 71l WW 7 2 ECE 3640 Lecture 2 7 Z Transforms 6 Now take the Ztransform of each part ylkl gt YlZl We are interested in what happens from k 0 and onward so yk 7 1 is to be interpreted as yk 7 1uk and not yk 7 1uk 7 1 In this way we introduce the initial condition information ll yk 71ukltgt 27132 y71 27132 2 1 2 7111 37 yk 7 2uk 42gt 2 YM 2 y71 y72 2 YM 2 g Also take the Ztransform of the input sequence 2 flkl 42gt 2 7 05 For delayed versions of the input function 2 M4 gtT2705 since the function is causal Now combine all of the pieces into the di erence equation 11 11 37 3 5 Y 75 1Y 7 6 1Y 71 i7 7 lzl l2 l2l6l Z M 636l 2752z75 Combining terms lt1ggm7a77 Identify portions due to input and initial conditions 5 6 322 7 952 105 ValVFW Multiply by 22 2 22 7 52 6YM 232 9 52105 2 7 5 Solve for YM 7 2322 7 952 105 2 2 7 5X22 7 52 6 At this point nding the solution is done by PFE Remember to divide by 2 YM 322 7 952 105 k1 k2 kg 2 275227526 275 272 273 Using CUPI we nd that lel 2615 73 185 2 275 272 273 We can now solve for 26 7 18 7 5 k772 c 73k k yln 15H 3 5 M El Note that by keeping the portions due to the initial conditions separate from the portions due to the input we can nd both the zerostate response and the zeroinput response by this method ECE 3640 Lecture 2 7 Z Transforms 7 Transfer Functions Under the assumption of zero initial conditions the zerostate response the general LTl difference equation QlElylkl Plelflkl Equot aHEW1 a1E aoyk WE bule1 b1E bomk may be transformed to 27 a 71zn 1 112 a0Y2 bnzn b 1zn 1 b12 b0F2 Solving for the output 71 7171 I I I YM bnz b71712 1 biz 50gt FM an an712ni a12l7ao We de ne n b n71 b b P m42l7ww Iwo M zquotan12quot quotl112110 as the transfer function Note that 7 YM 7 Zzerostate response 7 FM 7 Zinput and the output is obtained by lel FlZlHlZl The poles of the transfer function are the roots of the characteristic equation and we can determine the stability of the system by examination of the transfer function Example 8 Unit delay yk k 7 1uk 7 1 YM 1Fz 2 1 Re 11 member this 2 Example 9 Find the transfer function for the system ylk 2 M 1 16yk 7 flk 1 32fkl ln operator notation E2 E 16yk E 32fk 2 32 22 2 16 Now if 72 kuk nd the zerostate response all initial conditions zero lel 22 32 22 2 162 5 Don t forget to pull over 2 before the PFE YM 2 722216zi522 28 25 Yz 232 23 83 I 2 yrs gear 7 ltltsgtk 275kuk ECE 3640 Lecture 2 7 Z Transforms 8 If the input is 6k then the output is So Mk ltgt H The transfer function is the Ztransform of the impulse response Nomenclature A discretetime lter which has only a numerator part only zeros except for possible poles at the origin which correspond to delays is said to be a nite impulse response FIR lter Example 10 What is the impulse response of a lter with l 2271 3273 Note that all FIR lters are stable 1 A lter with poles is said to be an in nite impulse response HR lter Example 11 What is the impulse response of a lter with 11 Note that there is no practical way of making an FIR lter for continuous time systems this is available only for digital lters System Realization All of the block diagram operations we talked about with respect to Laplace trans forms still apply Series cascade parallel and feedback con gurations all have the same block diagram simpli cations The same techniques we used for system realization77 of Laplace transforms still apply for Ztransforms The only di erence is to substitute 2 1 for Even though the diagram ends up the same there may be understanding to be gained by working through the steps As before we will take an example of a third order transfer function Ing b222 b12 be H 23 1222 1111 a0 Break this into two pieces Let 1 23 1222 1111 10 X 2 F 2 and let YM X2b323 In b12 be From XM we can write 23XZ IQZQXZ a12X2 20XZ FM 23XZ 7a222Xz 7 a12X2 7 20XZ FM Draw a block diagram Then we connect the rest of the pieces to get ECE 3640 Lecture 2 7 Z Transforms 9 Example 12 Draw a system realization for 2 2 7 22 521 11 Note that in FIR lters the output depends only on the current and previous inputs In HR lters the output depends on these and also on prior outputs 7 there is some kind of feedback It is this feedback that gives them their in nite response This realization is useful in a sort of theoretical sense and gives us a map of what is going on But unlike for continuoustime systems there is no practical way of doing this using resistors capacitors and opamps What the diagram really represents is a computer programi We will now talk about how this is done We will start rst with an FIR lter Consider the particular example of 2 3271 4272 5273 Then YM 2 3271 4272 5273Fz1 Transforming back ylklQflklt3flk1l4flkr2l5flkr3l Draw the block diagram The equation tells us how to program it First we need some way of keeping track of the previous values Let is keep these in an array called fprevious and set it up so that fprevious 0 is the current value of f fprevious 1 is the last value of f and so on Furthermore let is keep track of the coef cients in an array called coefficient set up as follows coefficient0 2 coefficient1 3 coefficient2 4 coefficient3 5 Now we will create a ltering routine and pass the coef cients into it Note this code is provided for demonstration purposes only It may have minor problems with it that the student is expected to be able to understand and correct 1 fir filter version 1 2 double firfiltdouble f double coefficient 3 4 static double fprevious4 a double sum 6 397 fprevious 0 f assign the current input 8 9 compute the filter output 1o sum fprevious0coefficient0 fprevious1coefficient1 11 fprevious 2 coefficient 2 fprevious 3coefficient3 12 13 now shift everything down 14 fprevious 3 fprevious2 15 fprevious 2 fprevious1 1s fprevious1 fpreviousO 1397 13 return sum ECE 3640 Lecture 2 7 Z Transforms 10 This computes the output and shifts everything down Note that we have to save the previous values of the outputs so they can be used for the next call to the lter This has problems 7 suppose you have more than one lter 7 how do you keep things from getting messed up Perhaps a cleaner way to do this would be to pass in the previous values to the lter The cleanest way is probably to use C with a constructor that keeps a separate data set for each instantiation of the lter class I will leave these nessings to the diligent student To generalize our simple lter routine let us allow different numbers of coef cients to be passed in This means that we have to allocate sufficient space for the previous values and add everything up in a loop 1 include ltstdlibhgt put this at the top so calloc is used right 2 3 4 5 397 double firfiltdouble f double coefficientint numcoef version2 8 9 static double fprevious NULL 10 double sum 11 int i 12 13 if fprevious NULL first time in allocate enough space 14 fprevious double calloc numcoefsizeof double 15 16 1397 fprevious 0 f assign the current input 18 19 sum 2o do the filter operations 21 fori O i lt numcoef i 22 sum fpreviousicoefficient i 23 339 24 25 now shift everything down 2e fori numcoef l i gt O i 27 fpreviousi fpreviousi 1 28 339 29 return sum 30 339 For the diligent students interested in speeding things up as much as possible I pose the following ideas 11 Can the lter loop and the shift loop be combined so that only one loop needs to be execute to accomplish both functions 21 The shifting operation is slow and unnecessary How could you use a circular queue to store the previous values so that the shifting operation is no longer necessary Enough about FIR lters Implementing HR lters will also be addressed by means of an example We want to implement the lter represented by 622 22 3 7 22 425 ECE 3640 Lecture 2 7 Z Transforms 11 lel HlZlFlZl 22 42 5Y2 622 22 3Fz In the time domain ylk 2 4ylk 1 5ylk 61 2 21 1 31 Shifting in time and solving for yk ylkl 4ylk 1l 5ylk 2l 6flkl Qflk 1l 3flk 2l Again we have a formula for the lter output Assume that the numerator coef cients are stored in an array numcoeff and the denominator coefficients are stored in an array dencoeff numcoeff0 6 numcoeff1 2 dencoeff1 4 numcoeff2 3 dencoeff2 5 Caution note that the denominator coefficients are the negative of the coef cients in the original transfer function We Will keep the previous input values in an array fprevi ous and keep previous output values in an array yprevious 1 double iirfiltdouble f double numcoeff double dencoeff version 1 2 3 static double fprevious3 4 static double ypreviousS a double y 6 397 fprevious0 f assign the current input 8 9 compute the filter output 10 y fprevious 0 numcoeff 0 get it started 11 y fprevious 1 numcoeff1 fprevious 2 numcoeff 2 12 yprevious 1 dencoeff 1 yprevious 2dencoeff 2 13 14 now shift everything down 15 fprevious 2 fprevious1 1s fprevious1 fprevious0 1397 13 yprevious 2 yprevious1 19 yprevious1 y the output 20 21 return y 22 339 As before we Will generalize this to arbitrary transfer functions of denominator degree degree 1 version 2 2 double iirfiltdouble f double numcoeff double dencoeff int degree 3 4 static double fprevious NULL 5 static double yprevious NULL 6 double y 397 int i ECE 3640 Lecture 2 7 Z Transforms 12 9 if fprevious NULL first time set up space 1o fprevious double callocdegree1sizeof double 11 yprevious double callocdegree1sizeof double 12 339 13 14 fprevious 0 f assign the current input 15 1s compute the filter output 1397 y fprevious 0 numcoeff 0 get it started 1s fori 1 i lt degree i 19 y fprevious i numcoeff i 20 339 21 yprevious 0 y 22 23 now shift everything down 24 fori degree i gt O i 25 fpreviousEi fpreviousEi l 2e ypreviousEi ypreviousEi l 2397 339 28 29 return y 30 339 Again speedups are attainable merge the shift loop into the lter loop or get rid of shifting entirely by using a circular queue Bilateral Ztransform In the most general case we have FW Z flklzik k2700 Let us consider the 2 transform of i ykuk s 1 draw the picture We nd 2 2 7 39y Compare with gk ykuU What gives Must specify region of convergence for these Fz Frequency response Continuous time with transfer function Hs 5th A HjwejW1 An analogous result holds for discrete time systems Let the input to a discretetime system be 2 have to worry about transients Then k everlasting so we don t yk Mk 2k 2k 2 hmz m More particularly consider when 2 aim We nd that 5ij A Hemejmc ECE 3640 Lecture 2 7 Z Transforms 13 5 ij 7 He me jmC Adding cos 0k A ReHem ejmc or in polar form With Hem lHejnlej 3 Hwn we nd cost A lHeml cosQk argHejnk That is the cosine is modi ed in amplitude and phase by the transfer function Example 13 For the system yk 1 7 083AM k 1 determine the frequency response We 2 1 H 7 Z 2 7 08 17 08271 1 1 H J 5 l 17 08570 17 08 cosQ 33908 sinQ Then 1 WW 17 08 cos Q08 sinQ2 and 0 8 Q m 7 1 s1n argHe tan 1 7 O SCOSQ When the input is 1 determine the output What about When cos7r6k 7 02 1 Note that Hem is periodic Frequency response from polezero plot Rubber sheet geometry Let us Write in terms of its poles and zeros 7 b z7 1Z7 YQ39 39 39 2 77quot Consider evaluating this at a point 2 em Which is on the unit circle We nd V 19 137 HW MW we 7V1l lej 7 Let us Write em 7 21 new polar form for the line segment connecting them and em 7 21 dlejez polar form Then 9 T1T2quot39Tn We 1 bmdldwdn lb product of distances from zeros to em 7 product of distances from poles to em Similarly argHem 1 7919n sum of zero angles to em 7sum of pole angles to em Discuss lter design by pole placement and the rubber sheet idea poles increase the gain zeros decrease it Notch lter Overhead Example 14 Design using trial and error77 techniques a digital bandpass lter Which passes at w 250w radsec and has zero transmission at w 0 and w 10007r The highest frequency in the system is f 400 Hz ECE 3640 Lecture 2 7 Z Transforms 14 To must sample at more than twice the highest frequency f5 gt 2f 800 Hz We will take f5 1000 samplessecond so T 1fs 11000 In order to get zero transmission at the speci ed frequencies we must place zeros at ejOT 1 and 511000quotT 71 Draw the zeros To the the response to peak up at w 250 we want to put a pole near it on the unit circle ej250739T aw4 and also at the conjugate location Speci cally we will put the poles at 101 MW4 102 Vei e where y lt 1 to ensure the poles are inside the unit circle What is the e ect of V on the response The transfer function is 271z1 7 2271 Z WW4X2 7 WW4 7 22 7 vz 421 HzK Example 15 We want to design a secondorder notch lter to have zero trans mission at 250 Hz and a sharp recovery on each side of the notch The highest frequency in the system is f 500 Hz Take f5 1000 Hz to T 11000 The notch frequency is UT 27r250T 7r2 We need a zero there To get the re covery gain we need a pole nearby Let up place the pole at ija with a lt 1 for stability The transfer function is 7 Ziszdrj 221 7 Kz ijaz ja 7 22 a2 ECE 3640 Lecture 2 7 Z Transforms 15 Let us choose K to get unity DC gain 2 H17K1a2 SO K1a22i Linear phase FIR lters We have mentioned several times that FIR lters can have linear phase Now we Will show why Suppose that Mk Mn 7 k the coefficients are symmetric In particular consider the example Mk 7 h06k h16k 71 h26k 7 2 h36k 7 3 h46k 7 4 mm 7 5 then HM 7 Mo h1e m Maw mam my h5e j59 571639 lth05152gt9 Here2m h25112gt9 h357112gt9 h4e7j32gt9 h5e7j52gt9gt 7 aim2m 240 cos52Q 2h1cos32Q 2h2 cos12Q Then V argHeJQ 7529 a linear function of phase We can pull a similar stunt With antisymmetry Mk 7hn 7 kli ECE 3640 Lecture 11 7 StateSpace Analysis Objective To learn about statespace analysis for continuous and discretetime systems Perspective Transfer functions provide only an inputoutput perspective of what is going on in a system There may be things going on physically that do not appear in a transfer function due to cancellations etc On the other hand statespace analysis provides a more complete representation Furthermore it can be generalized to timevarying systems multi input or output systems and in some applications leads to very explicit design formulations There is also much that can be done with nonlinear systems in state variable form e have seen that we can describe an LTlC system using a single differential equation In statespace analysis we deal with systems of equations but make it so that all equations are rst order Sometimes this requires introducing some extra variables The variables appearing in these equations with respect to which we differentiate are called the state variables The idea behind the name is this for a rst order differential equation if we know where we are initially the initial condition then this provides all of the information we need to determine where to go In circuits it is common to choose the voltage across the capacitors and the current through the inductors as state variables This provides our rst example Example 1 Circuit Two state variables KCL 02551 2391 7 2392 7 x2 Ohm s 2391 2f 7 951 2392 3951 We obtain 02551 2f 7 x1 7 3x1 7 x 9 51 725951 7 5952 10f Notice that everything is expressed in terms of the state variables x1 and x2 and the input ECE 3640 Lecture 11 7 State Space Analysis 2 Next equation KVL 1552 22394 7 x1 0 since 2394 952 we obtain 552 x1 7 2952 We obtain 551 725951 7 5952 10f 9 52 x1 7 2952 Note every possible output of the circuit 7 every voltage and current 7 can be expressed in terms of the state variables Try a few Express in matrix form 121 Note we have 1 First order di erential equations 2 Each equation is expressed in terms of the state variables and the input For linear equations we can put the equations in matrix form Let 96103 x t i lt gt G Let x denote taking the derivatives individually 110 x t i law In the example above let Then we can write Axt Bfti Note For nonlinear systems we can still put them in state variable form even when we cannot use a matrix for the representation Example 2 9 61 x3 x3 cosx1 x2 f2 562 961 I22 9 53 x3 tanx2x1 Example 3 lmportant Consider the 3rd order equation D3 112D2 MD a0yt f We will introduce some new variables Let 961 9622 963 Then 951952 562 is f0 112563 i 111562 i 110561 f ECE 3640 Lecture 11 7 State Space Analysis We also have an output equation 3 961 We can stack this as follows 951 0 1 0 0 X x2 0 0 1 0 f 953 7110 7111 7112 1 x1 y 1 0 1 x2 3 or X AX bf y CTXi In general a set of statevariable equations can be Written at glx1x2uix f1f2iufj i12iun yzhlx1x2 axnaflaf2 afja i12 ak Note that this could be 0 Nonlinear 0 Multiple inputs 0 Multiple outputs But may not be This represents a considerable degree of exibility A general jinput koutput linear system With 71 state variables can be Written as 561 X AX Bf in y Cx Df Where A is n X n Bis n X j C is k X n and D is k X j Write out the matrices Have a student work the Circuit on the board i ECE 3640 Lecture 11 7 State Space Analysis 4 Transfer functions and state equations Given a transfer function we may want to write a state variable equation for it This is very straightforward by writing a system realization for the transfer function From the system realization we let the state variables be the outputs of the integrators Example 4 23 10 H S 33 832 193 12 Canonical Realization State equations 551 952 552 953 553 712951 7 19952 7 8953 f Output equation y 2952 10951 Matrix form 21 0 1 0 951 0 22 0 0 1 952 0 f 9 53 712 71 is 953 1 x1 y10 2 0 952 3 Comment on the form of the matrix companion matrix Describe form in general What is the characteristic equation of the companion matrix What are the eigenvalues Observer Form Realization Write equations then in matrix form Companion matrix What is the characteristic equation Eigenvalues ECE 3640 Lecture 11 7 State Space Analysis Series form Realization Equations 2 35 1 H S sls334 w1 w1f u 2211 7 3212 mg 5212 u 7 4213 Eliminate 2D using the 2nd eqn Obtain y 0 0 l w Characteristic eqn Eigenvalues Parallel Realization Equations ECE 3640 Lecture 11 7 State Space Analysis 6 H 2 12 Characteristic polynomial Eigenvalues 1 Note There are other ways of writing down the state equations from the transfer function In fact there are an in nite number of ways Laplace transform of state equations When we talk about the Laplace transform of a vector we will mean to apply the transform element by element Thus if then L Liza We nd then that sXs 7 X0 From the state equation X AX Bf we obtain sXs 7 X0 AXS BFS and from the output equation Ys CXS DFS Let us solve for Xs from the rst 31 7 AXs X0 BFs Why the identity Watch the order Xs SI 7 A 1X0 BFS Let ltIgts 317 A 1 We have Xs ltIgtsx0 ltIgtsBFs lnverse transform Xt L 1ltIgtsx0 L 1ltIgtSBFS Identify zeroinput components and zerostate components Output Ys CltIgtsx0 CltIgtSB DFs Transfer function Hs CltIgtSB D Example 5 Two inputs ECE 3640 Lecture 11 7 State Space Analysis 7 Three outputs Identify ABCD 7 1 7 7 71 7 3 3 1 SSI A i f5 12 33l 73S32 l 2 3 Transfer function 54 1 AL m 531s32gt s1s2gt HQ s1ss2gt 51gs2 D 4 52 524s 2 7 52 lts1gtlts2gt W1 T2 2ltse2gt 2 H1 H2 H1 H2 Poles and Eigenvalues Recall 1 8LClJ X detX Without worrying about what the adj is note that the denominator always has the determinant Thus 1 adjsI 7 A 31 A detsI A So the denominator has poles where the eigenvalues of A are Time domain solution We begin by de ning a new function For a square matrix A as in the state transition matrix we de ne 2 3 A L A e IA2 3 Taylor series This is directly analogous to e for scalars except that all arithmetic is done using matrices This is computed using the exmp function in MATLAB not exp Note show this ieAt AeAt eAtA dt The solution to the DE x Ax Bf is given by t Xt eAtX0 eAa B T d7 0 Show that it works by substitution Computing the matrix exponential One way a L 1ltIgts L1SI A 1 Example 6 A jg SLAP Mn 23 1 81 23 J 1 312 43 1 36 s1l s12sl24 736 s12 s4s9 36 s1 ECE 3640 Lecture 11 7 State Space Analysis 8 Taking inverse Laplace transforms element by element we obtain EM 7 70 65 9 1 6e 4 01335 9 7 01335 4 7 7725 9 725 165 9 7 065 Linear transformations For the state equations X Ax Bf y Cx Df let us create a new variable W PX for an invertible matrix P Then X P lw and X P lv vi Substituting we nd P lv v AP lw Bf or w PAP lw PBf Aw Er where A A A PAP 1 B PB Similarly A A y Cw Df where C 0131 D Di Instead of A B C D we have A E a 0 these represent the same system Hs CsI 7 A 1B D Hs 631 7 AWE D Work through details Other observations eigenvalues Eigenvectors 01 A special transformation diagonalizing A Given A PAP l suppose that we want to nd a transformation matrix P such that A is diagonal This is a convenient form since it decouples all the modes How can we nd such a P Let ez be eigenvectors of A and 1 be the eigenvalues of A assumed for our purposes to be unique Form Qe1 e2 en and AQ QA where A diag1 2 i i i An Then A Q lAQ Identify A A P Q71 ECE 3640 Lecture 11 7 State Space Analysis 1 Controllability and observability Example 7 Cascade representation State variable form A10 bm cT01 d0 detsli A s ls 71 Eigenvalues i1 Diagonalize A 1 0 1 1 b 10 2 1 2 uv eigA 39Z 11 has eigenvectors v eigenvalues Q 11 X Check invQAQ 39Z should be diagonal P invQ Ahat PAinvP bhat Pb chat cinvP A lbl ll 393 T 10 Write state equations Second state variable not observable Now the second system As before diagonalize A 1 O 2 1 b 11 2 0 1 uv eigA 39Z 11 has eigenvectors v eigenvalues ECE 3640 Lecture 11 7 State Space Analysis 10 Q 11 X Check invQAQ 39Z should be diagonal P invQ Ahat PAinvP bhat Pb chat cinvP We nd A 7 1 0 A 7 0 AT 7 A 7 0 I b7 14142 C 7 1 017071 Write state equations Second state variable not controllable 1 Note that in both cases the endtoend transfer function hides some information 7 there is cancellation there The transfer function provides a potentially inadequate representation of What is going one In the general case let us write 2 AZ Er y 62 bf Where A is a diagonal matrix 7 all the modes uncoupled If there is a row of zeros in B then f has no in uence on the corresponding state variable That variable is said to be uncontrollable If there is a column of zeros in a then the corresponding state variable is said to be unobservable For many purposes systems should be both controllable and observable Discretetime Most of What can be said for continuous time can also be said for discrete time Xk 1 Axk Bfk yk Cxk Dfk Solution k271 V xm Akx0 ZA C l JBfU j0 Show hoW this works by recursion starting from x1 Ax0 Bf0 Ztransform 2Xz 7 zx0 AX2 BF2 Xz 21 7 A 1zx0 BF2 C217 A 1B D ECE 3640 Lecture 6 7 Sampling Objective To learn and prove the sampling theorem and understand its impli cations The sampling theorem Due to the increased use of computers in all engineering applications including signal processing it is important to spend some more time examining issues of sampling In this chapter we will look at sampling both in the time domain and the frequency domain We have already encountered the sampling theorem and arguing purely from a trigonometricidentity point of view have established the Nyquist sampling cri terion for sinusoidal signals However we have not fully addressed the sampling of more general signals nor provided a general proof Nor have we indicated how to reconstruct a signal from its samples With the tools of Fourier transforms and Fourier series available to us we are now ready to nish the job that was started months ago To begin with suppose we have a signal Mt which we wish to sample Let us suppose further that the signal is bandlimited to B Hz This means that its Fourier transform is nonzero for 727FB lt w lt 27rB Plot spectrum We will model the sampling process as multiplication of xt by the picket fence77 function 6m 60 7 nT We encountered this periodic function when we studied Fourier series Recall that by its Fourier series representation we can write 1 V Mt T 261W n where as The frequency f5 us2w lT is the sampling frequency in samplessec Suppose that the sampling frequency is chosen so that f5 gt 23 or equivalently as gt 47rB The sampled output is denoted as 56 where 503 xt5Tt Using the FS representation we get 1 39nwst Mt 25 Now lets look at the spectrum of the transformed signal Using the convolution property Xw Xw22w6winws ZXwinwsi Plot the spectrum of the sampled signal with both 0 frequency and f frequency Observe the following ECE 3640 Lecture 6 7 Sampling 2 o The spectrum is periodic with period 27r because of the multiple copies of the spectrum 0 The spectrum is scaled down by a factor of lT 0 Note that in this case there is no overlap between the images of the spectrum Now consider the effect of reducing the sampling rate to f5 lt EB In this case the duplicates of the spectrum overlap each other The overlap of the spectrum is aliasing This demonstration moreorless proves the sampling theorem for general signals Provided that we sample fast enough the signal spectrum is not distorted by the sampling process If we don t sample fast enough there will be distortion The next question is given a set of samples how do we get the signal back From the spectrum the answer is to lter the signal with a lowpass lter with cuto wc 2 27rB This cuts out the images and leaves us with the original spectrum This is a sort of idealized point of view because it assumes that we are ltering a continuoustime function 56 which is a sequence of weighted delta functions In practice we have numbers representing the value of the function xnT How can we recover the time function from this Theorem 1 The sampling theorem If xt is bandlimited to B Hz then it can be recovered from signals taken at a sampling rate f5 gt EB The recovery formula is m mew 7 nT n where 7 sin7rfst 7 7M Show what the formula means we are interpolating in time between samples using the sinc function We will prove this theorem Because we are actually lacking a few theoretical tools it will take a bit of work What makes this interesting is we will end up using in a very essential way most of the transform ideas we have talked about sinc7rfsti l The rst step is to notice that the spectrum of the sampled signal 7 l Xw T Xw 7 mos is periodic and hence has a Fourier series The period of the function in frequency is as and the fundamental frequency is 27r l T 10 25 1 By the RS we can write 7a che WT n where the c7 are the RS coefficients 1 i v 2 l 00 l Y en 7 Xwe J Wwa 17 7Xwe J7Wwai 5 W5 5 27r 700 ECE 3640 Lecture 6 7 Sampling 3 But the integral is just the inverse FiTi evaluated at t inT l 27r c7 7 T T 7 957nT Y u Edint jn l Zxnte jnWTi 2 Let gt sinc7rfsti Then gt 42gt Trect yt ZxnTgt 7 nT We will show that yt 95t by showing that Yw Xwi We can compute the RT of yt using linearity and the shifting property Yw xnTT rect 2735 e jW T Trect 21 ZnxnTe jWT Observe that the summation on the right is the same as the RS we derived in step w 2wa Now substituting in the spectrum of the sampled signal derived above m Treat gm 7 w Xltwgt since t is bandlimited to 77rfs lt w lt 7rfs or ifs2 lt f lt fsZ Yw Trect Notice that the reconstruction lter is based upon a sinc function whose trans form is a rect function we are really just doing the ltering implied by our initial intuition In practice of course we want to sample at a frequency higher than just twice the bandwidth to allow room for lter rollo Other issues for sampling Antialias ltering When sampling is done the signal is usually passed rst through an analog lowpass lter with the cutoff frequency set to ensure that no aliasing occurs The discussion above assumes that the signal is sampled by a sequence of impulse functions In practice the signal is sampled by multiplying by some other function ls it still possible to recover the signal exactly Provided that we satisfy the Nyquist sampling criterion the answer is yes The reconstruction is similar Some applications Why digital l Recoverable signals ECE 3640 Lecture 6 7 Sampling 4 2 Flexibility 3 Channel coding theorem Source coding theorem 4 Encryption 0 Time division multiplexing 0 Pulse code modulation Spectral sampling Just as we can sample a bandlimited signal in the time domain and reconstruct it provided that we sample often enough so can we also sample a timelimited signal in the frequency domain and exactly reconstruct the spectrum provided that we take the samples close enough together in the spectrum There is thus a dual to the sampling theorem which applies to sampling the spectrum We can also use this kind of thinking to nd the FT of a periodic signal Let be a causal signal timelimited to 739 seconds lts ET is Fw 0T fte jmdti Now create a periodic extension of by repeating it every To seconds fTO t Em 7 TITO Since fTOt is periodic it has a Rs and we can write fTO t ZDneWo where we 27rT0 and when 739 lt To 1 To V t 1 T V t D To 0 m TD 0 1 Comparing the RS coefficient with the FT above it follows that D7 TLOFUlwol An implication of this is that we can nd the RS coef cients by rst taking the RT of one period of our signal then sampling and scaling the PT In terms of reconstructing the signal spectrum from its samples we can see that as long as To gt 739 the cycles of do not overlap We can then at least in concept reconstruct the entire spectrum of Fw from its samples Conceptually we time limit the function then take its RT The sampling condition can be expressed as follows To gt 739 1 F0lt7 7 So we can reconstruct from samples of the spectrum provided that the samples are close enough by comparison with the timelimit of the function ECE 3640 Lecture 3 7 Building blocks for signals Vector spaces Objective To learn about how to construct signals and other things from basic building blocks as a preparation for studying Fourier series An informal example Before getting to that formality an analogy will be presented We will consider making things out of a bunch of building blocks The things might be for example cakes shampoo or signals For the case of cakes the set of possible ingredients might look like this lngred symbol Name 11 white our 12 wheat our l3 granulated sugar 14 Sweet and Low 15 Powdered sugar 16 Baking soda i7 Baking power 13 Hershey s cocoa 19 egg 110 milk in water 112 vegetable oil 1 N Xanthum gum The ingredients are denoted by ik The mixture for the cake batter consists of certain amounts of each ingredient The ingredients for a cake might be for example 500 ml white our 300 ml granulated sugar 2 eggs 20 ml vegetable oil 200 ml water and 10 ml baking powder Hint don t try to make this at home Assuming that the quantities in the table above are placed in the correct units normalized this recipe could be written as follows c 50011 30013 1017 219 20011120112 The set of all possible cakes forms a vector space If the set of ingredients is able to make every element in the space ie every cake the said of ingredients is complete Notice that a complete cake space is not necessarily able to make everything else we could not for example make every possible shampoo with the set of ingredients to make cakes We don t have for example any aloe in our list above or even any FDampC Red 21 Several interesting questions now arise Given a cake is it possible to determine the quantities of each ingredient that goes into it This is the analysis question Suppose that we only want to use a certain subset of the ingredients say we have run out of ingredients and don t want to run to the store What is the best approximation to a desired cake that we can make What is the error between the desired cake and the cake we actually get This is the approximation question Obviously some of these questions don t make a lot of sense when applied to cakes However these kinds of things will be very applicable when it comes to analyzing signals which may also be built up from a set of building blocks ECE 3640 Lecture 3 7 Building blocks for signals Vector spaces 2 Vector spaces We brie y review the concept of a vector space A vector space V has the following key property If v w E V then av bw E V for any scalars a and b That is linear combinations of vectors give vectors Most of your background with vectors has been for vectors in R But the signals that we deal with are also elements of a vector space since linear combinations of signals also gives a signal This is a very important and powerful ea Recall that in vector spaces we deal with concepts like the length of a vector the angle between vectors and the idea of orthogonal vectors All of these concepts carry over by suitable de nitions to vector spaces of signals his powerful idea captures most of the signi cant and interesting notions in signal processing controls and communications This is really the reason why the study of linear algebra is so important In this lecture we will learn about geometric representations of signals via signal space vector concepts This straightforward idea is the key to a variety of topics in signals and systems 1 It provides a distance concept useful in many pattern recognition techniques 2 It is used in statistical signal processing for the ltering smoothing and prediction of noisy signa s D5 It forms the heart and geometric framework for the tremendous advances that have been made in digital communications u It is every waveformbased transform you ever wanted Fourier series FFT DCT wavelet etc Fquot It is also used in the solution of partial differential equations etc o It relies on our old friend linearity One might even say it is the reason that we care so much about linearity in the rst place We will soon turn our attention to Fourier series which are a way of analyzing and synthesizing signa s Vectors will be written in bold font like the ingredients above Initially we can think of a vector v as an ordered set of 71 numbers written in a column Often to conserve writing this will be written in transposed form V 11 712 van Vector addition is componentbycomponent While we have written a vector as an ntuple that is not what de nes a vector A vector is an element of a vector space which is to say it satis es the linearity property given above Scalar multiplication of vectors is in the usual fashion Matrix multiplication is also taken in the traditional manner Let g 9192agan ECE 3640 Lecture 3 7 Building blocks for signals Vector spaces 3 and flf1f2a afan be two vectors The inner product known to many of you as the dot product of the vectors g and f is written as n T ltgfgt g f 291sz 11 ln words multiply component by component and add them up Two vectors are said to be orthogonal or perpendicular if their inner product is zero f g 0 ill f and g are orthogonal If f and g are orthogonal this is sometimes written f L g Example 1 Let f 1713 and g 73 3 3 Then ltf g 0 so f and g are orthogonal 11 The inner product can be expanded using the following rules 1 For a scalar c ltcf g cltf g f gahgt ltfahgt g h 3 For real vectors which is all we will be concerned about for the moment ltfggt ltg fgt The Euclidean norm of a vector is given by n 12 HXH ltxxgt1Q Ex 11 The distance between two vectors is given by n 12 dX Y HX 7 Y W2 The projection of a vector f onto a vector X is given by x mm pm qui ltxxgt Geometrically this is the amount of the vector f in the direction of X Show a picture Obviously if f and X are orthogonal then the projection of f onto X is 0 Now suppose that we have a vector 11 an ingredient and we have a vector f and we want to make the best approximation to f using some amount of our ingredient Draw a picture We can write f 6111 91 ECE 3640 Lecture 3 7 Building blocks for signals Vector spaces 4 where c1 is the amount of 11 we want and e1 is the error between the thing we want and our approximation of it To get the best approximation we want to minimize the length of the error vector Before we go through and do it the hard way let us make a geometric observation The length of the error is minimized when the error vector is orthogonal to our ingredient vector 11 11 L e1 or f 7 c111L11 f 7 c11111 0 ltf11 c1lt11 11 Giving us ltf11gt 7 f 11gt 1111 7 Note that this is simply the projection of f onto the vector 11 Example 2 Suppose i 1 IF and f 34 The representation C1 fmci has the least amount of error when 1 Now let s do it the hard way we want to nd the amount of 11 to minimize the length of the error The squared length of the error is E Helu2 up c111 2 ltf7 c111f 7 c111 f f 7 2c1ltf11 c1311 11 To minimize this take the derivative with respect to the coefficient and equate to zero dE C1761 72ltf11 2c1lt1111gt 0 Solving for the coefficient Cl ltf 11gt lt11 11 This is the same one we got before We may actually have more than one ingredien 7 vector to deal with Suppose we want to approximate f with the vectors 11 and 12 As before write f 6111 6212 e where e is the error in the approximation Note that we can write this in the following way c f 11 12 l l 1 e C2 using the usual matrix multiplication We want to nd the coefficients c1 and CQ to minimize the length of the error We could to it the calculus way or using our orthogonality idea We will go for the latter The error is orthogonal to the data means that f 7 c111 7 C212 11 0 ECE 3640 Lecture 3 7 Building blocks for signals Vector spaces 5 f 7 c111 7 C21212gt 0 that is the error is orthogonal to each of the ingredient data points 1 Expanding these out gives f 11 610111 620211 ltf112gt 610112 620212 This is two equations in two unknowns that we can write in the form 1111 1211 Cl ltf 11gt 1112 1212 C2 ltf112gt If we know f and the ingredient vectors we can solve for the coefficients Example 3 Suppose f 123T and 11 110T and 12 210 It is clear that there is no exact way to represent f C111 C212 since there is no way to match the third element The formula for the best coefficient given above leads to 2 3 c1 7 3 3 5 c 7 4 Then the approximation vector is This can be solved to give E c111 chQ 31 1 of 7 210T 1 2 0 Note that the approximation f is the same as f in the rst two coef cients What has happened is the vector has been projected onto the plane formed by the vec tors 11 and 121 The error in this case has lengt 31 1 Of course what we can do for two ingredient vectors we can do for n ingredient vectors and 71 may be in nite We want to approximate f as n f Em e 11 We can nd the set of coef cients that minimize the length of the error 9 using the orthogonality principle as before applied 71 times This gives us 71 equations in the n unknowns which may be written as 1111 1211 quot39 in 11gt Cl 1 11gt 1112 1212 quot39 in 12gt C2 ltf112gt lt11 ingt am ltin ingt c m This could be readily solved say using Matlab It would seem that if we take 71 large enough we should be able to represent any vector without any error Analogy given enough ingredients we could make my cake We might not be able to make everything but we could make everything some class of objects If this is true the set of ingredient vectors are said to be complete A more formal name for the ingredient vectors is basis vectors Although we have come up with a way of doing the approximation there is still a lot of work to solve for the coef cients since we have to rst nd a matrix and ECE 3640 Lecture 3 7 Building blocks for signals Vector spaces 6 then invert it Something that is commonly done is to choose a set of basis vectors that is orthogonal That is if ij and ik are any pair of basis vectors then 1ikgt0 iij k Let us return to the case of two basis vectors when the vectors are orthogonal Then the equation for the coef cients becomes 16 lt1f12gtl 2 610111 ltf11gt 620212 ltf12gt so the coef cients are ltf111gt ltf112gt C2 1111 1212 So solving for the coef cients in this case is as easy as doing it for the case of a single vector and the coef cient is simply the projection of f onto its corresponding basis vector This generalizes to 71 basis vectors If the basis vectors are orthogonal then the coef cient is simp y f in iminf C1 C7 Example 4 Let us repeat the previous example then f 1 2 SF only this time let 11 1 10T and 12 3 73 0 Observe that 11 and 12 are orthogonal Then 3 73 l c 7 c i if 1 2 2 18 6 The approximation is A f c111 chQ 1 2 0 The approximation is the same as before but the computations are easier because the ingredient vectors are easier Function spaces One of the neat things about all of this is that we can do the same techniques for in nitedimensional spaces which includes spaces of functions Now our ingredients are not vectors in the usual sense but functions Suppose we have a set of ingredient functions called 2391t 2392t int We want to nd a representation of some other function in terms of these functions M f0 WW 3 H 1 We can ask the same kinds of questions as before What kinds of functions can be represented How do we choose the set of coef cients To get the whole thing going we need to introduce some kind of geometry into the problem We will de ne the inner product between two functions as ltftgtgt m ftgtdt ECE 3640 Lecture 3 7 Building blocks for signals Vector spaces 7 the limits will usually be dropped for ease of writing indicating that the integral is to be taken over all applicable values Compare this inner product with the inner product from before we are multiplying things together and adding them up Two functions are said to be orthogonal if 1 0 903 0 The projection of one function onto another one is de ned as before prom gm The length of a function is de ned by 12 WNI ltftftgt12 f2tdtgt and the distance between two functions is de ned as 61029 f 7 91 7 9 Getting back to our representation f0 WW M a H 1 the kinds of functions that we can represent without error depends upon the kinds of basis functions that we choose If the set of basis functions is able to represent all functions is a given class then the set of functions is said to be complete even if it cannot produce all possible functions Analogy a set of ingredients for cakes may be complete even if it cannot produce all kinds of shampoo To nd the coefficients we proceed as we did in the vector case we want the error between the function and its representation to be as small as possible This produces again the orthogonality theorem the error is orthogonal to the data This leads to the following equation for the n coefficients 103 2105 203 2105 quot39 intai1tgt 103 ltftai1tgt 103 2392 13 203 2392 13 quot39 intai2tgt C203 ltftai2tgt i1taintgt i2taintgt quot39 W03 Mt CW ltftaintgt Comparison of this equation with the one above reveals that they are identical in form It doesn t matter whether you are dealing with vectors or functions the result is the same This means that you can use any geometric insight that you might obtain from vectors and apply it to functions when represented in this way This is an extremely powerful notion and in a sense forms the very heart of digital communications and a good part of signal processing theory As before it is often convenient to deal with orthogonal functions Suppose that the set of basis functions that we choose is orthogonal so that maxim 0 when 239 k Then the equation for the coefficients reduces down to i1tai1tgt 0 0 610 1 210 0 i2tai2tgt 0 C20 ltfti2tgt j 0 int2 nt cnkt ltft 239ntgt ECE 3640 Lecture 3 7 Building blocks for signals Vector spaces 8 The coefficients may then be solved for as ltftiktgt W0 Mt Example 5 Suppose we have a function Ck 1 Ogtgw ft717rltt 27r Suppose we want to nd an approximation to using only the function 2391t sint and we want to choose the coefficient c so that the approximation is as close as possible to the original functioni That is ft m csint The best coefficient in the minimum error sense is 2quot ftsintdt 1 Iquot 2quot 4 027r 7 sint dt isint alt 7 f0 sin2t dt 7quot 0 7r 7quot So the best approximation is 4 t m 7 i t f0 mo Now suppose we want to approximate with two functions 2391t sint 250 sin2t t m c1i1t Cgig and we want to choose the coefficients so the error is as small as possible Note that AU and 2392t are orthogonal In fact 27r sinmt sinnt dt 0 m n 0 7r m n So we can use the simply formula 027rft239ktdt wwwt This gives us Note that Cl has the same value as it did before this always happens when we use orthogonal functions We will learn later what it means that CQ 0 Now we are ready to deal with Fourier series ECE 3640 Lecture 5 Fourier Transforms and their properties Objective To learn about Fourier transforms which are a representation of nonperiodic functions in terms of trigonometric functions Also to see the notation for some useful functions and see their Fourier transforms To learn useful properties of Fourier transforms which not only enable a variety of functions to be transformed but also lead to a variety of engineering applications 0 learn some analytical tools involving Fourier transforms including systems analysis transfer functions and ltering and energy relationships Review of Fourier series formulas Let be periodic with period To Then where we 27rT0 and 1 V D 7 t JWO dt To Tof 5 Representation of nonperiodic functions We have seen how we can represent periodic functions in terms of sines and cosines This is a natural thing to contemplate at least retrospectively What if we want to represent nonperiodic functions in terms of periodic functions This seems kind of strange at rst Why would we want to Part of the answer comes because we know how LTl systems respond to sines and cosines It turns out to be closely related to sinusoidal steadystate analysis of circuits and provide some useful tools for design of signal processing and communication systems To represent a nonperiodic function in terms of periodic functions one thing we will need to to use periodic functions that might have in nite period It will also turn out to add up a whole lot of them more than a countable in nite Here is one approach to the problem u pose we have a function We construct a periodic extension of called fTOt where is repeated every To seconds Since fTOt is periodic it has a Fourier series mt E n where 1 ToQ V D7 7 fTOte W dt To fro2 and we The integral is the same since is zero outside of 7T0 T0 as 1 M v D i t JWO dt To 1 001 gt5 Now let s de ne the function Fw 100 fte jmdt ECE 3640 Lecture 5 7 Fourier Transforms and their properties 2 Comparing these we can see that D 1 F 7 mu 7 T0 0 So we get the RS coefficients by sampling the function Fw In the limit as T A 0 we sample in nitely often Now the RS for fTOt is Fnw0 v t t J wo fTo En To 5 Let Aw 27rT0 and write F A A v mt z lt 50gt n Now in the limit as To A 0 we get 1 CO 39 i M ft Tgim fTOt 2W1 Fwe dw So we have been able to reconstruct our nonpe riodic function from Fw These are important enough they bear repeating This is called the Fourier Transform of t The inverse Fourier transform is ft i 00 Fwejmdw 27r 700 We also write FM fw f0 f llFWH ft gtFw This is notation similar to what we used for Laplace transforms Some things to notice 1 Notice that to get we are doing the same kind of thing we did for PS except that we add up a continuum of frequencies m Suppose that is causal In the Laplace transform set s ejw Then we get the Laplace transform back But notice that the integral goes from 700 to 0 So we explicitly don t assume that is causal We thus do not typically use the FT to examine things like transient response use the Laplace transform for that As will be mentioned below however the FT cannot be used for unstable signals since the integral does not exist in this case The ET is not usually used to examine stability as the LT can 3 Notice again that in the forward transform a negative is used in the exponent ECE 3640 Lecture 5 7 Fourier Transforms and their properties 3 4 The frequency variable in the ET is U which is frequency in radianssec If we make the change of variable 40 27rf and nd the transform in terms of f we get the following transform pair Fem O fte 127 f dt This is sometimes written simply as which strictly speaking is not correct notation so you have to be careful In this notation we would have Fm m mrwdt The inverse transform is N Flt2wfgterw This has the convenience of not having the factor of l27r in front of it This is usually written again by an abuse of notation m m Ffemf df As we did for PS we can plot the magnitude and phase of the PT We can write V FW lFwl514FW Notice that if is real then F7w Fw they are complex conjugates so that lFwl lFwl 4F7w 74Fw or in other words if is a real function then the magnitude function is even and the phase function is od Example 1 Find the FT offt e ut 1 FM m if a gt 0 Does this look familiar The magnitude and phase are Fw 41 7tan 1wa Plot and discuss What kind of lter is this 1 Some useful functions Some functions come up often enough that it is nice to give them names The unit gate or unit pulse is de ned by rectx gt7le O M M M H l i i 2 Some interesting variations Plot rectx2 rectx 7 l2 rectx 7 aTi Note that the total width is T and the function is centered around a ECE 3640 Lecture 5 7 Fourier Transforms and their properties 4 The unit triangle function also known as the hat function or the chapeau function is de ned by 7 0 W gt 1 Ax 172lxl m lt2 Plot Also look at AxTi Notice that the total width of the function is T The sinc function we have already met in the context of the FS of a square wave To reiterate sinx sinc x 7 lt gt x Observe the following sincx is even sincx is zero for x i7r i27r i37r i u sinc0 l sincx decays as lx FWNE The signum function is de ned by 1 t gt 0 Sgnt 71 tlt0 RT of some simple functions Get some students down for this part Example 2 Find the FT offt recttTi recttT 42gt TsincwT2 Plot this function The zeros occur at ianT Also plot as a function of The zeros occur at ilT Notice that the longer the function the narrower the sinc and vice versa What is the bandwidth of the signal What is the nulltonull bandwidth 1 Example 3 Find the FT of Mt 6t gt 1 Notice that every frequency has the same response This is what would be termed a white spectrum all components equa 1 Example 4 Find the inverse RT of 6a Use the inverse FiT formula 1 7 6 27f gt w Multiplying through 1 42gt 27r6w So a constant signal only has a response at w 0 Does this make sense 121 Example 5 Find the inverse RT of 6a 7 we where we is a xed frequency 1 V ew 42gt 6a 7 we ECE 3640 Lecture 5 7 Fourier Transforms and their properties 5 5 42gt 27r6w 7 we Example 6 Find the RT of cosw0t cosw0t 42gt 7r6w we 6a 7 400 Plot and discuss 1 Example 7 Find the RT of the sgn function This function is dif cult the upper and lower limits of integration cannot be handled directly There are actually several approaches to the problem I even wrote a paper describing a different approach But we will go with the approach in the book as it is probably the easiest Note that we can write sgnt lim e O tut 7 eo tu7t ciao Plot and discuss Then we can write fsgnt Clini fkimu 7 feo tut lim 1 2 OCHO ajwia7jw jj There are issues the math guys would have to stew about can we really interchange the limits But we will just believe this 1 Example 8 The real reason why the last example is useful is for this one Find the RT of It is not a simple matter of changing s to jw in the Laplace transform because of region of convergence issues This function does not satisfy the Dirichlet conditions So we have to be a bit tricky Note that um a1 sgnw Using linearity l fut 7r6w System response using Fourier transforms Let be the input to an LTlC system with transfer function Hs and output The response to the everlasting signal ejm is yt Hwejm Thus ft ejnAW A HnAwej AW Now let the input be r j Awt lim0 FnAwe E Awa By the de nition of the FT this is By linearity the output is yt i lim ZFnAwHnAwejnAm 27r Aw7gt0 That is l 00 v 1 00 v i Jwt i 1m yt 27 OO FwHwe dt 27 OO Ywe dt so we can say Yw FwHw In a sense this is the whole point of Fourier analysis ECE 3640 Lecture 5 7 Fourier Transforms and their properties 6 Properties of Fourier Transforms We saw earlier a variety of properties associated with the Laplace transform lin earity time shift quot quot 39 i an i quot These opened up a variety of applications There are similar the properties of RT which are also very useful Linearity The ET is linear flaf bgtl a t WWW This follows from the linearity of the integrals Time Frequency Duality The duality property is one that is not shared by the Laplace transforms While slightly confusing perhaps at rst it essentially doubles the size of our FiTi tables The duality property follows from the similarity of the forward and inverse PT It states that if ft gtFw then Ft 42gt 27rf7w where the function on the left is the function of time and the function on the right is the function of frequency Proof 1 00 i jxt t 2 Lemme dz 27r 16H 1 C Fade pw But observe that the integral on the right is the RT of Now replace t A w to see the results 1 Example 9 We have seen that recttT 42gt T sincwT2 In this case recttT and Fw TsincwT2i Then Ft TsinctT2 and rectwTi By duality TsinctT2 42gt 27rrect7wT 27rrectwTi Example 10 We have already seen another example of the duality property in the FT pairs 6t gt 1 l 42gt 27r6w In terms of the alternative notation in Hz we have that if 90 gtGf then C13 gt 9if ECE 3640 Lecture 5 7 Fourier Transforms and their properties 7 Scaling Property We have seen this for Laplace transforms If f 0 gt F M then 1 at gt FWa lal Proof By studentw 1 Discuss in terms of time and bandwidth when a signal is expanded in time it is compressed in frequency and Vice versa We cannot be simultaneously short in time and short in frequency This is the basis for the famed Heisenberg uncertainty principle TimeShift Property If f t gt F 1 then V ft 7 to 42gt Fwe 1m0 In other words a shift in time corresponds to a change in phase in the FT Proof By student u 1 What is interesting is that higher frequencies experience a greater phase shift than lower frequencies A plot of the phase is linear in frequency Example 11 Find the RT of e lt wl From the table we see that 211 7t He Hl m So 2 7 7 a 39 fe l tol 7a2w25 Jwto Frequencyshift Property This innocuouslooking property forms a basis for ev ery radio and TV transmitter in the world It simply states that if f t gt F 1 then V fteJW t 42gt Fw 7 we Note that this is a dual of the timeshift property Proof By studentw 1 Show a block diagram of what happens Since ejwot is a complex signal this is really only a mathematical description But we can multiply by cosw0ti Using linearity we get ft cosw0t 42gt Fw 7 we Fw 400 What we get out is two images in the frequency domain at positive and negative frequencies As an application suppose that is some informationbearing signal say the signal from a microphone Plot Now multiply by cosw0t and plot the ECE 3640 Lecture 5 7 Fourier Transforms and their properties 8 result and show the effect in frequency This is What KSL does This kind of modulation is called amplitude modulation Observe that we can modulate signals onto a variety of different frequencies This makes it possible to have several radio or TV stations The higher frequencies also propagate further through the air than the baseband frequen cies Convolution Property If f1t 42gt F1w and f2t 42gt F2w then f1t f2t gt F1wF2w Where is convolution and l f1tf2t ltgt QF1U FQQU Proof By studentw 1 Example 12 Show that t ltgt 7rF06w jw Notice that t N we fltxgtdz Then using fut ljw 7r6w the result follows El Time Differentiation If f t gt F 1 then df E ltgt ijw Proof By studentw 1 Time Integration We saw above that 1 mm gt Mango If f is zero mean ices F0 0 then t 42gt L100 00 3w Example 13 Use the time differentiation property to nd the RT of AtTi Note that cl2 f 2 W Tm T2 7 260 m 7 Tm ECE 3640 Lecture 5 7 Fourier Transforms and their properties 9 Then the differentiation property states that de 2 W 42gt 7w Fw Using 6t 7 to 42gt e jmo we get 2 2 39wTQ 7 39wTQ 4 8 r 2 7w Fw 7e 7 2 5 J 7coswT2 7 l 77s1n CUT4 T T T So we get Fw sin2wT4 T2 sinc2wT4 8 PT Example 14 Find the RT of This is hard to do by other tech niques But notice that s nt dt 7 g So 2 WFW flsgn 7 FM 2 2 System Analysis using Fourier Transforms We have seen that we can use Laplace transforms for analysis of LTlC systems We can do similar things with Fourier transforms except that we will be able to obtain only steadystate responses not the transient response For the differential equation QDyt PDft we can use the timedifferentiation property of the FT D CW gt iMkYW so that we can write QjwYw PjwFw YOU HWWW where P39 L 7 HM Qow The function Hw is the transfer function of the system and is related to the transfer function we saw for Laplace transforms Analysis with the ET is not generally preferable to analysis with the LT be cause the system must always be asymptotically stable and we have to lug around jw instead of the more compact 3 However for systems or signals that are non causal and Fourier transformable the analysis may be easier using FiT Example 15 Let H s 7 S 2 ECE 3640 Lecture 5 7 Fourier Transforms and their properties 10 and let Find the zerostate response We have 1 WW l Fw 7r6w Notice that the ET is more complicated than the LT Then ww igwwgt 7r6w 1 f 2 ww 2 1 l l 7r6wjiwijw2 The inverse FT is 1 gm ueamw Example 16 For the same system nd the response when t e uH Note that this is noncausal and hence could not be analyzed using the single sided Laplace transform We have from the table 71 W7 Yw HwFw Doing the PFE we obtain gmmawrw Signal distortion during transmission Fourier transforms form a natural way of looking at the frequency response of lters since they examine the response due to a a trigonometric exponential We have already seen how to characterize a lter by its frequency response using the Laplace transform We can do the same thing somewhat more naturally using Fourier transforms The output of a signal with transfer function Hw is YOU HWWW Let us express this in polar form lYwle YltWgt lFwllHwlej4Fw4Hw ECE 3640 Lecture 5 7 Fourier Transforms and their properties 11 The magnitude response of the output is therefore lYwl lFwllHwla so the magnitude response is the input magnitude response shaped by the system magnitude response In a word the output is ltered We can also consider the phase response 4160 AFW AHW The phase angle of the output is the phase angle of the input plus whatever phase the system contributes There are applications in which we would like the system to not change the input signal as it passes through the system other than to delay the signal and possibly uniformly attenuating the whole signal For example the signals that pass through the air to our radios we would hope that they would arrive at the radio in the same form as they left the transmitter except delayed by the propagation through the air and attenuated A system which does not distort a signal other than delaying it and possibly changing the overall gain is said to be a distortionless system The output of a distortionless system may be written as 3113 If td where k is the overall gain and tag is the delay introduced by the system In terms of Fourier transforms we Yw kFwe jmd So the transfer function of a distortionless system is Hw ke jm Observe that the magnitude does not change with frequency and the phase is a linear function of w lHwl k AHW iwtd In practice distortionless transmission is never exactly obtained over all frequen cies Over a localized region of frequency however the magnitude response may be at enough and the phase response may be linear enough so the distortion is acceptable For any system including those with nonlinear phase we can compute the time delay of a signal as it passes through a system tdw ii H u Example 17 Examine the distortion of the system with frequency response 1 H w a W The magnitude response is 1 H w 7 l lt l Plot the magnitude response Clearly there is magnitude distortion The phase is AHQU itan 1 g 1 Then d w dw alt1 wax Plot Note that the delay is a function of frequency 1 w So we can write 1 00 Ef g loopwmgwdw For a real ft the FT satis es Fw F7w they are conjugates so that 1 m EFQ Fwdw ECE 3640 Lecture 5 7 Fourier Transforms and their properties 13 This is Parseval s theorem for Fourier Transforms It can be written using inner product notation as 1 ltftftgt QltFwaFwgt It can also be generalized for products of di erent functions as 1 ltft9tgt QWWLWWW We can think of an increment of energy lying in an increment of bandwidth 1 AEf glFWHQAw To get the total energy add up all of the pieces The function lFwl2 is therefore referred to as the energy spectral density of the function it tells where the energy is distributed in frequency The energy which is passed by a bandpass lter with cuto frequencies lt01 and lt02 is 1 W2 Em an g WW W1 Example 18 Find the energy in the signal e a ut and nd the bandwidth W such that 95 of the energy is contained in frequencies below Wt 00 1 7 2 7 72at 7 Efff tdt70 e dtiiga The ET is We therefore have the identity 1 00 l l E 7 7d 7i f 27roow2oz2 2a This can actually be veri ed by integrating 00 00 Efl 21 251witanilg i 7r 0 w a 7m 1 0 211 To nd the 95 containment bandwidth we solve 0 95 7 1 W dw 2a 7 7r 0 lt02 a2 for Wt then 095 1 1 w W 7 itan 7 i 211 we a We get 095 1 W 7 tan 7 2 a so W 12706 radi 1 Some observations ECE 3640 Lecture 5 7 Fourier Transforms and their properties 1 F We can use the Parseval s theorem to integrate some messy functions by simply applying the theorems For example we can compute 00 r 2 I s1n xdx 0 x by writing 1 w sin2x 1 w 2 7r 1 7r Iii7w7dxig 7007rrectw2dw71illdwi The previous example also demonstrated how we can sometimes do easier integrals in one domain than the others We can also use the idea of the last example to introduce the idea of an essential bandwidth include enough bandwidth that most of the energy of the signal can get through Often the 95 or 99 level is sufficient

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.