### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Digital Signal Processing With Applications ECE 43800

Purdue

GPA 3.59

### View Full Document

## 121

## 0

## Popular in Course

## Popular in Electrical Engineering & Computer Science

This 118 page Class Notes was uploaded by Cassidy Casper on Saturday September 19, 2015. The Class Notes belongs to ECE 43800 at Purdue University taught by Staff in Fall. Since its upload, it has received 121 views. For similar materials see /class/207907/ece-43800-purdue-university in Electrical Engineering & Computer Science at Purdue University.

## Similar to ECE 43800 at Purdue

## Popular in Electrical Engineering & Computer Science

## Reviews for Digital Signal Processing With Applications

### 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: 09/19/15

Sec 15 Sampling 85 Input x Output y System S Figure 142 System block diagram I 15 Sampling I 151 Motivation As we have covered the basic theoretical foundations and start considering several prac tical issues it is useful to brie y summarize what we have accomplished so far and to motivate what lies ahead We started by considering some examples of signal processing algorithms in action and saw that all those examples t into one basic picture Fig 142 We have talked about a few very basic notions which the whole eld of signal processing is based on such as the notions of signals and systems We concentrated on linear timeinvariant systems and saw that in order to analyze such systems it was important to study representations of signals in orthogonal bases sltngt Zapkm k For example 0 when we represented our input signal as the sum of shifted and scaled impulses we obtained the interpretation of an LTl system as the convolution of its impulse response with the input when we represented our input signal as the sum of complex exponentials we got an equally important interpretation of an LTl systeminamely that it modi es different frequency components independently of each other by multiplying each component by a complex number We called these frequency dependent complex numbers the frequency response and saw that it was the discretetime Fourier transform of the impulse response We moreover studied the FFT which a fast algorithm for computing spectral representations of signalsispeci cally the DFT Because of these properties of LTl systems it is very important to be able to think of signals both in time domain and in frequency domain The background material that we covered allows us to begin considering several important practical matters One example which will be considered in the lab portion of this course is lter design where the goal may be to attenuate certain frequencies in a signal and enhance other frequencies Every time you adjust the bass or treble on your audio equipment you are modifying a digital lter Every time you click enhance in an image editing program you are applying a digital lter to the image 86 CHAPTER 1 ANALYSIS OF DISCRETETIME LINEAR TIME7NVARANT SYSTEMS Another practical issue that we will start studying shortly is sampling You may have noticed that most real world signals are continuous time or continuous space When you go to a concert the music you hear is a continuous time signal How can you reliably store it as discrete samples on a compact disc Similarly the world you see around you is continuous How can we store digital images on a computer and make them look realistic and distortion free Sampling theory will provide partial answers to these questions I 152 Ideal Sampling In the following we denote the sampling period by T9 and the sampling frequency by f5 We begin by summarizing some facts about continuous time signals CTFT The forward and inverse continuous time Fourier transform CTFT formulas are Xm mxlttgte i dt m 0 Xfe quotf df It is possible to extend the de nition of the CTFT to generalized functions called tempered distributions One example of a tempered distribution is the continuous time impulse 6t In this framework it can be shown that the Poisson formula holds so 2 Winn a Saki Z 6ltfiTlsgt7 ie that the CTFT of a periodic impulse train is another periodic impulse train as shown in Fig 143 Convolution with 6t0t 6t 7 to is simply a translation by to 00 m 6075 67 7 t0xt 7 m7 7 w 7 to 700 We represent the ideal sampling process as a multiplication of a signal by a periodic train of continuous time impulses as shown in Fig 144 Referring to this system we have xstmctst X50 XCSf co Tisngmxc 107 136 Sec 15 Sampling 87 1 CTFT TL e Figure 143 CTFT of a periodic impulse train Convert impulse zcnTs train to DT gt sequence Figure 144 Block diagram of an ideal sampler 72Ts 7T 0 T 2T t 72 71 0 1 2 n a The signals is t and wstv b The signals is t and Figure 145 An example of xct and the resulting xst and for Fig 144 88 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS To analyze what happens in the frequency domain7 we need to relate the DTFT of to the CTFT s of m5t and zct We do this by using a different method to calculate the CTFT of ms ms nimzmnwwnn X50 ningnnwrmwainnn 00 glean 1 6t7 nTse j2quotftdt i WWW X 67 lw2 fTs Therefore7 Xsm Xequot2quotfTS V hf x CTFT of 15t DTFT of m Xe7 X9 From this derivation7 we see that in order to get X elm from X90 7 we just need to rescale the frequency axis by replacing 1 5 with 271397 with 7139 etc We can now use Eq 136 to express the spectrum of the DT sampled signal in terms of the spectrum of the original CT signal zct 0 aw J i J 1 Xe 7Xs Ms 7 Ts EGOXC Ms T9 The major point of concern here is how accurately these discrete samples represent the original CT signal We will try to answer this question by looking at the spectra and determining whether the original spectrum X00 can be recovered by low pass ltering X ejw Example 128 Sampling and reconstruction Consider a signal with the spectrum of Fig 14 6 Under what circumstances can we reconstruct this signal from its samples by ideal low pass ltering Case 1 gt a In this case the spectrum of the continuous time sampled signal zst is giuen in Fig 147 The original spectrum of Fig 146 can clearly be recouered by ltering Sec 15 Sampling 89 Figure 146 Spectrum of the continuoustime signal xct of Ebrample 128 if ia0a f f Figure 147 Spectrum of the sampled continuoustime signal xst from Example 128 When the sampling rate is greater than 2a Hm m Ts m 7 f Figure 148 Reconstruction of xct from xst If the sampling rate is higher than 2a perfect reconstruction With an ideal lowpass lter is possible Figure 149 Spectrum of the sampled continuoustime signal xst from Example 128 When the sampling rate is less than 2a 90 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS aliasing error a frequency truncation error f Figure 151 Illustration to Example 128 Case 2 pre ltering before sampling Xsf with an ideal low pass lter whose cuto frequency is fsQ This is shown in Fig 148 Thus perfect reconstruction with an ideal low pass lter is possible if the sampling frequency is larger than twice the highest frequency of the signal Case 2 g a Referring to Fig 149 we see that it is impossible to recouer 0 with a low pass lter without distortion The distortion occurs because the spectra of neighboring copies interfere with the original spectrum When we lter Xsf with we recouer the distorted signal whose spectrum is shown in Fig 150 One possible way of auoiding this distortion is as we haue seen in Case 1 to sample at a higher rate Howeuer if we cannot sample at a higher rate there is still something that we can do in order to improue the quality of the reconstruc tion Speci cally we can pre lter the continuous time signal before sampling to ensure that the highest frequency of the signal to be sampled is not larger than Fig 151 Let be the result of pre ltering zct with the ideal low pass lter depicted in Fig 151 Let be the corresponding continuous time sampled signal If we now try to recouer zct from with our ideal low pass lter we get back Its spectrum depicted in Fig 152a is closer to the original spectrum than our preuious result of Fig 150 The frequencies in the range f9 7 a are now recouerediin other words the aliasing error is remoued The frequency truncation error is howeuer still present Sec 15 Sampling 91 7 0 2 5 f if 0 f9 f a b Figure 152 E ects of pre ltering sampling and reconstruction on the spectrum of the signal of Ebrample 128 Case 2 a The spectrum which results from pre ltering with an ideal lowpass lter b the spectrum of the sampled pre ltered signal The pre ltered signal can be reconstructed from the samples by ideal lowpass ltering Figure 153 If sampling rate is lower than the Nyquist rate some information about the continuous time signal will be lost in the sampled signal I 153 Nyquist Sampling Theorem Let 005 be a band limited signal with X00 0 for l gta The parameter a is called the Nyquist frequency and 2a is called the Nyquist rate If mct is sampled at the rate of f5 samples per second which is larger than the Nyquist rate f9 gt 2047 then mct can be recovered from its samples xcnT n 0 i1 i2 by ideal low pass ltering If there is no restriction on the bandwidth of the signal unique reconstruction from samples is impossible This is illustrated in Fig 153 where the discrete samples form a constant signal whereas the continuous time signal is allowed to change rapidly between the samples 92 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Hm 0 Huge Hm m 1 42 yaw gm Ts m gt DgtC gt 74 A 7e e Figure 154 A system for sampling DT processing and reconstruction Ebrample 129 X00 12 12 7a a f Figure 155 Input spectrum Xcf to the system of Example 129 Example 129 DT processing of CT signals Suppose we wanted to conuert an old analog recording to digital format store it on a compact disc CD and then play it back on a CD player Fig 154 illustrates in a uery idealized manner the steps we would take Note that before storing the signal on a CD we might want to do some signal processing for example in order to enhance the quality of the audio signal This step is represented by Hd Once we have our CD we would like to play it on our audio equipmentiie we would like to conuert the DT signal on the CD to a CT music signal While this diagram is just a simple example its structure is quite similar to the structure of real systems In Example 128 we considered euery component of this diagram exceptfor the middle portion DTprocessing Let us consider how this system will process the input signal whose Fourier transform Xcf is depicted in Fig 155 First we use the inuerse C TFT formula to calculate the signal xct mt foo Xcfej2quotftdf 6fiaej2quotftdf 6faej27 ftdf 1 1 7 7j27rat 7 5 5 2 2 j27rat cos 27rat Now we consider the same two cases as in Example 128 Sec 15 Sampling 93 Case 1 f5 gt 2a 139 XcfHf Xe Hm 41quotquot 7 a 0 a g f 2 Xf X20 5f Xf X2ltfgt326f7 l 1 1 l 1 1 recall that fS S 7 s 7 0 s 3 XW x f a Shae f Rescale the frequency axis 7T 7T Also7 adjust the areas of the 67s recall that a E16007 1 l 1 1 l 1 and so I I Th6 27 ZJES w 7T6w 727T ih a 0 2 27139 w 4WWPXWWNW where HAG 7 w 0 7m 27m 727T fs 0 fs 27139 w We 2a7r 2a7r fs fs 1 l 1 1 l I 1 I 27m 27m I 727139 7 f f 27139 w 94 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS 5 To get Yc f7 re label the frequency axis back and rescale the impulses 6 Ycf YlfHf f TSYcf lfl S 0 lfl gt Tsa6f a 6f a i yt 2aTS cos 27rat 7a a f Therefore the ouerall e ect of the system on this particular input signal is equiv alent to multiplication by QaTs Case 2 f5 lt 2a In this case the output will be zero because the whole input signal will be ltered out by the rst low pass lter Let us now look closer at the reconstruction of an ideally sampled signal First7 we assume that there is no pre ltering Assume that after sampling a continuous time signal zct7 we get the samples m5t as in Fig 157a What happens when m5t goes through the low pass lter as in Fig 156 Note that the comb function st and the low pass lter Hf are as previously de ned in Example 1297 and thus we have ms Z gamma 7 nTs Figure 156 Signal reconstruction system Sec 15 Sampling 95 15 15 1 1 05 T 05 39 0 0 AVA A 39I Jayl AA VV VVV 05 05 5 4 3 2 1 01 2 3 4 5 5 4 3 2 1 01 2 3 4 5 n n a 15t of the system in Fig 156 b The reconstructed signal m Figure 157 Interpolation With sincs The reconstructed spectrum is X70 XsfHf7 therefore 95 t x5tht m5tsincf9t zcnTs6t 7 71 sincf5t V L Z zcnTssincfst 7 mm 137 71 where we used the inverse CTFT formula to obtain 7125 W 1Hfequot2quot df Ts ejzw ft f4 j27rt fJZ S sincf9t From Eq 137 it is seen that in the time domain reconstruction by low pass ltering is equivalent to interpolating the DT signals with sinc functions The sinc functions are scaled and added up together to form the reconstructed signal Fig 157 Again we have a representation of the form mt Zakgw k 96 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS where now gk s are sinc functions The original CT signal 005 may contain frequencies above However pre ltering mct with an LPF to avoid aliasing is the orthogonal projection of the signal onto the space of all bandlimited signals with highest frequency as shown in Fig 158 This results in a reconstruction which is the closest to 005 among all possible signals in this space Fig 158 It turns out that sincf5t 7 nTs is an orthogonal basis for this space 7L OO 00 7 has frequencies above I pre ltering is the orthogonal projection I G 7 space of all bandlimited signals with highest frequency m t Figure 158 Pre ltering with an LPF to avoid aliasing is the orthogonal projection of the original signal on to the space G of all bandlimited signals with highest frequency Why is this interpretation important The space of all bandlimited signals is good for approximating smooth signals whose energy is concentrated at low frequencies It is well adapted to sound recordings which are well approximated by lower frequency harmonics For discontinuous signals such as images a low frequency restriction produces the Gibbs oscillations If you try to approximate a square pulse Fig 159a with low frequency components you will get a reconstruction which looks like Fig 159b 1 1 0 05 in 05 u 0 2 15 105 0 05 1 15 2 215 105 0 05 1 15 2 i i a A square pulse b Reconstruction with Gibbs oscillations Figure 159 The effects of Gibbs oscillations The visual quality of images is degraded by these oscillations so it is not a good Sec 15 Sampling 97 idea to sample images in the same way sound signals are sampled For the sampling and reconstruction of images it may be better to pick a basis which is different from the sinc basis and to project onto a different subspace However the basic vector space paradigm will remain the same This is yet another illustration of the importance of linear algebra in signal process ing It is very important to get used to thinking about signals as vectors This allows one to get a broader viewinamely that much of what we have done in this course is de composing signals into different bases and working with projections of signals onto the bases vectors We have seen that this is the basic idea behind convolution frequency analysis and also sampling We next consider several deviations from the ideal sampling model I 154 Effects of Zero Order Hold Sampling It is impossible to produce ideal impulses of in nite energy and zero duration Real systems try to get around this by using the sample and hold scheme where the value of a sample is held until the value of the next sample is available So instead of an impulse train the result of this sampling operation is a staircase function zZOH Fig 160 This function can be represented as the convolution of the ideally sampled signal 505 and a square pulse qt as shown in Fig 160 wonm ESQ gtk l11 Figure 160 The staircase function which results from the sampleand hold is equal to the ideally sampled signal convolved with a square pulse Therefore XZOHU Xsf TFTMW Xsf qte j27rftdt Ts X9f e j2quotftdt 0 1 1 7i 73927rf TS Xsf 2f to Xsf 1 7 yawn 98 CHAPTER 1 C 215105 0 05 1 15 2 f a The original spectrum xsm Tslsmd s 3901 Tslsincf 39s xsm ZOHf C 39 1 2 5 1 05 0 05 f b Sampleiandihold for fs 05 A xsm Tslsmd s 3901 0 0391 Tslsincf 39s xsm 215105 O 05 1 15 2 f d Sampleiandihold for fS 15 2 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS 15 215105 0 05 1 f c lXZOHltfgtl for f5 05 05 C 15 2 Il C M 2 15 1 05 0 05 1 15 f e lXZOHfl for fs 1395 2 Figure 161 An illustration of the sampleand hold scheme a The original spectrum b The ideally sampled spectrum Xsf and the magnitude of the spectrum of the square pulse qt for fS 05 c The magnitude of the spectrum of the signal obtained With sampleand hold7 Which is the product of the tWo spectra in de The same experiment With sampling rate fS 15 Sec 15 Sampling 99 X6jw f9 Ax A Q 39 27r in Figure 162 Sampling at Nyquist rate 1 1 XSWEKMTS T Ema 757mm 7 wan 7 X5fTse 7 WfTs XsfTse 7quotfTSsincfTs Hence lXZOHfl Tlesfl lsincfTsl ie XZOHf is a distorted version of X90 as exempli ed by Fig 161bc One possible method of reducing the distortion is to oversample ie to increase the sampling rate beyond the Nyquist rate As shown in Fig 161de this both spreads the aliases farther apart and makes the center alias less distorted I 155 Discrete Time Interpolation Increasing the Sampling Rate Another important deviation from the ideal scenario is that it is impossible to build an ideal analog low pass lter 7 that is a lter which would be exactly a non zero constant for some range of frequencies and exactly zero everywhere else Moreover it is very dif cult and expensive to build even a good approximation to such a lter However it is much easier to build a good digital lter that performs this function What are the implications Suppose we sampled at the Nyquist rate barely avoiding aliasing Fig 162 Just converting to CT and reconstructing will not work as we would need an ideal lter Instead we could partially solve this problem in DT by intemolatmg as shown in Fig 163 Interpolation consists of two steps upsampling and low pass ltering Step 1 Upsampling by a factor of L is inserting L 7 1 zeros after each sample muLn muLn1 mnLn2 muLnL71 0 100 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS xun L HLPFleW 7r 7r 5 Figure 163 System diagram of an interpolation scheme 1 ms 11 0 we 10 12 I 0 1 2 n 0 1 2 3 4 5 6 n a A DT signal b The result of upsampling With L 3 1M5 12 Figure 164 Upsampling a signal An example with L 3 is shown in Fig 164 Therefore7 Xu57 Zmukeiwk k Z m Ln i dLn since zuUc 0 only if k is an integer multiple of L VL Z 0057 an V L Xej L Step 2 Low pass lter the interpolated signal How is the signal reconstructed We begin from Fig 16507 mimm mu gtk hn 138 where hn is the impulse response of the low pass lteriie7 it is the inverse DTFT of HLPF of Fig 16510 7r Mn HLPF ejwejwndw W 1 i Lewndw 27139 7 Sec 15 Sampling 101 sinc 139 Putting Eq 139 into Eq 1387 we have the following i n 7 k minim Zmuksinc L k ZmumLsinc m Zzmsinc 140 m Now we can get away with a poor analog LPF and still reconstruct the original signal very well7 because the signal spectrum replicas are further apart Fig 165c Note that Eq 140 has a form that is similar to the CT reconstruction formula7 Eq 137 wt Zznsinc n 102 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS Xint2 Xint3x1 6X2 int Figure 166 Lowpass ltering the upsarnpled signal interpolates the reconstructed data points Via sinc functions As in the continuous time case7 the reconstruction is produced by a series of sinc functions It is good for slowly varying signals but not good for signals with sharp transitions because of Gibbs oscillations Sec 15 Sampling I 156 Decimation Decreasing Sampling Rate There are situations where we may have to decrease the sampling rate7 eg due to the lack of processing speed or the lack of available memory Downsampling by a factor of D is taking every D th sample from a DT signal 101 141 It is illustrated in Fig 167 13 m0 13 10 12 15 0M0 10 11 14 15 1A2 15 l l l o 1 2 3 4 5 5 n o 1 2 n a A DT signal b The result of downsampljngv Figure 167 Downsampling a signal by a factor of 3 Let us now pretend that was obtained by sampling a CT signal 005 Then mcnTs7 and7 as shown above7 1 w 7 27m X W X 5 T9 27 Moreover zdn mcnDT57 and so we can use the above formula with T9 replaced by DTS to get 1 w 7 27m X M X 142 45 DTS in 0lt 27rDT5 gt To relate X4571 to X5739 7 we perform a change of variables nkrDwith fooltrlt0070 k D71 Then we have D71 00 1 1 w727rk727er X 7 X 45 Dk0 THE 27rDT5 7 1f 1 1 i X f iwr Dk0 277 0 27rT5 1 D71 41727rk 5 Xlt57 gt 143 w H o 104 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS The spectrum of the downsampled signal is therefore the sum of shifted replicas of the stretched spectrum of the original DT signal7 as illustrated in Fig 168 Xaf 7a a f Xe f5 A A I I I I I I 727139 72717171 27raTs 27r u L me D I I I I 727139 727139aDT5 27l l1DTS 27r 0 f 117x e717 75 72w 72w 727nzDTS 27raDTS M 2m w 117x awn I 72WD27r 27r Figure 168 Comparison between signal spectra In this pictorial example D 2 Refer to the derivation of Eq 143 From Fig 1687 when 27raTsD gt 7r7 we have 271sz9 gt This causes aliasing in the resulting spectrum Just as in the continuous time case7 we pre lter to avoid aliasing Fig 169 HLPF5jw zIn 1 7r 7r 7 5 Lu Figure 169 System diagram of a decimation scheme Chapter 1 Analysis of DiscreteTime Linear TimeInvariant Systems I 11 Signals I 111 Definitions and Notation A signal is a function signal and function are synonymous The two notions are the same and we will be using them interchangeably The historical reason for the existence of these two terms to denote the same thing is that function is the standard term from mathematics whereas signal is an engineering term which originally was used to denote measurable physical quantities like a voltage signal Continuous time CT or analog signals are 0 de ned for every value of time on an interval possibly an in nite interval AND 0 take on values in an interval A graph of a continuous time function is shown in Fig 11a Discrete Time DT signals or sequences are de ned only at integer values of time A graph of a discretetime function is shown in Fig 11b To emphasize the difference between continuous time and discrete time we will use n instead oft for discrete time A digital signal or digital sequence is a DT signal which can take on only integer values Fig 11c is a digital signal which takes on only two different values sometimes such signals are called binary signals Sometimes notation such as f Z a R is used to indicate that f is a discretetime signal Here R is the set of all real numbers ie the real line Z is the set of all integers 7271012 In order to completely understand this notation it is important to recall that a function is a mapping from one set to another WHAT IS A FUNCTION A function is a RULE for producing a number in its range given a number from its domain It is helpful to think of a function as a block diagram shown in Fig 12a 10 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS 5 2 1 0 1 0 5 1 0 50 100 0 5 0 0 2 4 t n n a b c Xt fn fn Figure 11 a A continuoustime function b A discretetime function c A digital function a single number n a single number aken from t in the range Value nS t he argument n domain of f D of f R an mteger Function a real number function f f 7 djvide by 3 a A generic function b Function nS Figure 12 Functions as block diagrams Example 11 The concept of function or signal has a straightforward programming analogy you can think of a signal as a program that takes a single number as its input and produces another number as the output for example float divideby3n int n float x x n30 returnx The function which performs diuision by three can be thought of as this module of code or a rule or an algorithm Then you can call this subroutine from elsewhere and eualuate it for a particular argument for example main x divideby35 Sec 11 Signals 11 When you eualuate the function you will be assigning to m a particular number in this case 53 or approximately 53 modulo computer precision So a function is a procedure which takes in one number and produces another number I When we write R a R to describe continuous time functions we mean that continuous time functions can take in any number on the real line and produce another number anywhere on the real line1 Discrete time functions on the other hand can only take in an integer number but can produce a real number Z a R Digital functions take in an integer and produce an integer Z a Z Note the important distinction between a discrete time signal f and its n th sample fn which is a single number Sometimes it is convenient to abuse this notation and refer to signal fn In this case it is implied that we are referring to a signal f de ned for integer n I 112 Specifying 3 Signal There are many different ways to specify or represent a function a formula eg fn n3 for n O 1 2 34 b graphical representations note that for 2 D functions surface plots and intensity images can be very useful c a list of all values for all arguments n n d A vector in an N dimensional space see Fig 13 which will be used for o N point signals 1More generally a continuoustime signal is described by 1 gt 2 where 1 and 2 are two intervals on the real line Similarly for DT signals and digital signals 12 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS o periodic signals with period N This is done by recording the N values of the signal fn as a column vector We will typically denote vectors by boldface letters thus the vector corresponding to an N point or an N periodic signal 1 is f m 1 This approach is very important and will be emphasized throughout the course It provides geometric intuition into many key theoretical results and helps turn complicated formulas and proofs into very natural intuitive statements For example when signals are viewed as vectors in an N dimensional Euclidean space it turns out that the Discrete Fourier Transform is essentially a rotation in this space see Fig 13b Parseval s theorem therefore simply says that if you rotate a vector you do not change its length We will also occasionally treat random variables as vectors to gain geometric insight into linear prediction and recursive estimation I 113 Properties of Signals Different types of functions require different processing tools It will be important for us to know is a function periodic or not ls it nite duration ls it bounded ls its energy nite a Periodicity lf fn fnN for some xed N and all n we say that f is periodic with period N For example the function given by the formula f1 71 for all integer n is periodic with period 2 as shown in Fig 14 left we assume here that the signal 1 i i i i i 72 n n g 2 extends 1n n1tely in both directions The function f2n 0 Olhlerwise not periodic as shown in Fig 14 right b Finiteinfinite duration If fn 0 outside of a nite interval 1 is a signal of nite duration otherwise 1 is a signal of in nite duration For example the signal f1n de ned above is in nite duration f2 is nite duration c The energy of a signal 1 will be denoted f A more standard notation which you will nd in mathematics literature is The energy is de ned as follows 51 Z lleZ 11 Sec 11 Signals 13 X1 M Figure 13 a A vector space representation for Npoint or Nperiodic signals With N 3 b In this framework the Fourier transform is Very similar to a rotation it preserves distances and angles 1 5 0 000 P Too f1ltn gm 1 5 0 5 4 2 0 2 4 n n Figure 14 A periodic signal left and a nonperiodic signal right The absolute value needs to be in the de nition for the case when fn is complex valued For example the energy of fl is 1 1 1 which is in nite The energy of f2 isU 241 2127 24221 An important remark here is that since we will often be dealing with sums of the type 1qfw 14 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS it is useful to remember the formulas for summing the geometric series m m1 N71 7 qmin lfmN Zand0 mltNthenq q q 7 1 q 00 gm d f0lt lt1 th an1 in en q liq nm To verify the rst formula multiply both sides by 1 7 q and cancel some terms on the lefthand side To verify the second formula take the limit of both sides of the rst formula as N a 00 Why would the second formula not work for lql 2 17 d The magnitude of a signal 1 is the maximum of its absolute value MU max WON 12 ieoltnlteo Another notation for the magnitude of f is For example the magnitude of fl is 1 the magnitude of f2 is 4 If a signal has a nite magnitude we say that it is bounded I 114 Special Signals 1 1 Q A 0305 gas 0 4 2 0 2 4 4 2 0 2 4 11 11 Figure 15 Unit sample left and unit step right There are several special signals which we will encounter very often a Unit sample or unlt ImPUIse7 6W i 07 n 7g 0 1 n 2 0 In Unit step 7 07 n lt 0 c Sinusoids sinum gt or cosum gt Sec 11 Signals 15 cosTct cos3Tct and cosnncos37cn l cosZTcn cos0n 1 05 O 4 2024 11 Figure 16 Left the DT frequency 27r is the same as the DT frequency zero Right adding 27r t0 the frequency does not Change the DT signal Q 0 Q Apparent motionk J Actual motion Figure 17 I 115 Peculiar Properties of DT Sinusoids a The highest rate of oscillation in a discrete time sinusoid is attained when w 7139 or w 77139 For example the DT frequency 27139 is actually smaller than the DT frequency 7139 Indeed since 71 is integer we have cos27m 1 cosO 71 for all 71 SO the DT frequency 27139 is the same as the DT frequency 0 16 CHAPTER 1 ANALYSIS OF DISCRETEeTIME LINEAR TIMEelNVARIANT SYSTEMS b Discrete time sinusoids whose frequencies differ by an integer multiple of 27139 are iden tical cosw 27139n gt cosum gt This is illustrated in Fig 16 right Notice that the continuous time signals cos7rt and cos37rt are the same at integer points So if we sample either of these signals at integer points we will get the same signal cos7r0 cos37r0 cos7r1 cos37r1 cos7r2 cos37r2 cos7m cos37m for any integer n More generally cosw 27139n gt cosum gt 1 27m coswn gtcos27rn 7 sinwn gtsin27rn cosum gt 17 sinum gt 0 cosum gt Even though the two continuous time signals in Fig 16 right are different their sampling at integer points is the same The dashed continuous time signal oscillates faster but it all happens in between sampling instants The sampling points so not see this activity This is why two different continuous time frequencies can appear to be the same discretetime frequency This phenomenon is called aliasing You have all encountered aliasing when watching a movie You must have noticed that sometimes a car moves in one direction but its wheels seem to be rotating in the opposite direction A simplistic picture of this is shown in Fig 17 Between each pair of consecutive movie frames the wheels rotate 270 degrees threequarters of one full revolution which looks like a 90 degree rotation backwards c DT sinusoids are not necessarily periodic Suppose you are sampling a CT sinusoid t at integer points 71 0i1i2 If z0 1 as in Fig 18left then in order for the DT sinusoid to be periodic it has to have a value of one again some time in the future In Fig 18left this happens at n 5 From then on the DT signal will start repeating For this particular example 5 4quot and so an 43quot Even in the case when the DT sinusoid is periodic its period may be different from the period of Note that while the fundamental period of cos 437 is 25 the fundamental period of cos is 5 But suppose now that w 1 as in Fig 18b Then there is no value of n besides n 0 for which 1 So the value of the sample z0 will never repeat As you can see cos6 is pretty close to 1 it is in fact approximately 096 however there is no integer 71 except 0 for which cosn is exactly equal zero2 2ltisposTowhoweverthatcosn can be arbitrarily Close to zero In other words for any E gt 0 no matter how small there exists a positive integer n for which cosn gt 1 7 E Sec 11 Signals 17 cos4Tct5 cos4nn5 cost cosn 1 A l 0 l l l 1 1 0 1 2 3 4 5 6 tn tn i O Figure 18 Left DT sinusoid Whose frequency 0 47r5 is a rational multiple of 7r is periodic Right DT sinusoid Whose frequency 0 1 is not a rational multiple of 7r is not periodic What should happen for the sampled signal to be periodic An integer number of the continuous time periods has to eventually become an integer In other words7 there must exist two integers k and m such that k 2quot m 17 ie the continuous time period 3 must be a rational number If this happens7 then the sample at n m will have the same value as the sample at n 07 and the resulting sinusoid will be periodic If this never happens7 then no sample will ever have the same value as the sample at n O Sec 1 6 Transform 105 I 16 Z Transform The z tmnsform is an important tool for lter design and for analyzing the stability of systems It is de ned as Xe 2 my 144 n7oo where z is a complex variable ie z lzlew Figure 1 70 Ztransform DTFT can be interpreted as the z transform evaluated on the unit circle Xej Xzl 145 I 161 Rational Z Transform We will mostly be interested in z transforms that are rational functions of 2 ie ratios of two polynomials 146 where and are polynomials Rational z transforms are transfer functions of LTl systems described by linear constant coe icient difference equations such as N71 M yn Emma izakmik 147 i0 k1 We now introduce some terminology o If there is no second term in the right hand side of Eq 147 then the system is called non recursive or nite duration impulse response FIR system 106 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS o Otherwise7 it is recursive because the current output sample is expressed in terms of the past output samples If it cannot be written as non recursive7 then it is an in nite duration impulse response system ZT 357 71 2 iXz 148 N71 M Yz Z biz 1X2 7 Zakz kYz 10 M N71 k 1 Yz lt17 Zakzikgt Xz Z bizquotl k1 i0 Therefore7 the transfer function can be written as 149 Zips w H H where the last equality comes from the fact that polynomials of degrees N 7 1 and M have N71 and M roots7 respectively The values ofz for which 0 ie7 the roots of the numerator 21 22 7ZNA are called the zeros of whereas the values for which is in nite ie7 zeros of the denominator 191192 7pM are called the poles i i ifM gt N7 17 then there are M 7 N7 1 zeros at z 0 Of In addltlon if M lt N 7 17 then there are N 7 1 7 M poles at z O Poles and zeros may also occur at z oo zero at 0077 means lim O7 M700 poles at 0077 means lim 00 z 700 Sec 16 Transform Example 130 Let us consider the z transform of a u ZTanun Zanz n n0 2 7 a The region of convergence R00 is the set of all values of z for which the z transform converges In this example it is gt a OZero gtlt Pole El ROG A Tmz Rez Figure 171 The region of convergence of the series in Ebrample 130 Let us now consider the lter Whose transfer function is the z transform of Exam ple 130 Example 131 Let 2 H Z Z 7 a a Difference Equation To see how the z transform is related to the time domain representation we expand it 39 Yz 7 1 Xz 7 17 az l Yz 7 azilY z Xz 7 az 1YzXz N Inuerting the z transfor39m we have 108 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS b System Diagram The system diagram is depicted in Fig 172 Figure 172 The system diagram of Ebrample 131 z 1 delays a signal by one time unit C Frequency Response The frequency response of the system can be obtained by replacing z with 57quot in the transfer function 1 1 7 ae j H 5 H 57quot t 17ae 7 17aejw 1 172acoswa2 1 17 a2 2a17 cosw Hejm IoANovoImxloocoo A 32101234 0 Figure 173 Magnitude response of the lter in Example 131 for several Values of the parameter a Fig 173 shows the magnitude response of the lter for di erent ualues of a In Sec 1 6 Transform 109 particular note that the height of the peak is determined only by a since the term with the cosine is removed when w 0 The closer a is to the unit circle the sharper the peak and the thinner the passband As we have seen from Example 131 in general a pole near the unit circle will cause the frequency response to increase in the neighborhood of that pole a zero will cause the frequency response to decrease in the neighborhood of that zero Fig 174 11112 j9 I 9 R69 Hejw 9 5719 I I a Zeros on the unit circle b A bandstop lter corresponding to a 11112 lHe l 771 719 19 71 c Poles near the unit circle d A bandpass lter corresponding to Figure 174 The e ects of zeros and poles near the unit Circle I 162 Region of Convergence ROC of the Z Transform Example 132 Let Then 00 00 2 r L X 2 in ltzgt Z 2 22 n0 n0 When can we sum this seriesf2 In other words when does this series convergef2 Consider these two cases 1 If g 2 then Z 1 This means that every term in the series has an absolute value greater than or equal to 1 If it is greater than 1 then every successive terms grows larger If it is equal to 1 then we are just adding 1 an in nite number of times In both cases the series diverges 110 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS 2 On the other hand if gt 2 then the geometric series conuerges because lt 1 and we have H Xa 150 1 71 Mgt2 unde ned g 2 Imz ROC Figure 175 The ROC of Example 132 Usually gt 2 is called the region of conuergencequot R00 of the z transform because when 2 lies in this region the series actually conuerges to the function 150 A slightly more accurate term would be the region of de nitionquot since the z transfor39m is unde ned outside of this region Example 133 Let 72 u7n 71 Then Yz 2727327 n71 0 7 Z 27milzm1 where m in 71 m0 8 1 If 2 2 the series diuerges Sec 1 6 Transform 1 1 1 2 if lt 2 the series conuerges and Putting it all together unde ned Z 2 Yz 1 Mlt2 We get the same expression for the z transform as in Example 132 but the R00 is di erent and in fact does not intersect the ROC from Example 132 Example 134 Let wn 2 for 7 00 lt n lt 00 Then 2nun 2nu7n 71 7 yn7 where and are from Examples 132 and 133 respectively Hence Xz 7 Yz 2 2 17 17 0 What is wrong with this deriuation As we saw in the two preuious examples Xz and Yz have no common R00 0 Xz is unde ned for g 2 o Yz is unde ned for Z 2 This means that is not de ned for any 2 De nition 112 The region of conuergence of Z xnz n n7oo is the set of all z for which this series is absolutely conuergent ie 112 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS We use absolute convergence to avoid certain pathological series which converge7 but do not converge absolutely An example of this is 00 n 1 in 7 70071 at z 71 I 163 Properties of ROC Poles and Zeros The following is a list of several important properties of the z transform 1 The R00 is a ring or a disc centered at the origin 71 lt z lt r2 Note that 71 or r2 could be 0 or 00 El ROG 1m 1m lmz Rez Rea Rea a leftesided b Generic c rightisided Figure 176 The geometries of the ROC to The ROC cannot contain any poles 03 lf is a niteduration sequence ie7 0 except for N1 n N27 then the R00 is the whole z plane except possibly 2 O 4 If is a right sided sequence 0 for n lt N17 then the R00 is M gt 1pmam17 where pm is the outermost nite pole of 5 If is a left sided sequence 0 for n 2 N27 then the R00 is 121 lt 1pmin17 where pmm is the innermost non zero pole of 6 Generalizing Example 132 and Example 1337 we have 1 anun lt gt m Where the R00 is gt lal 151 1 where the R00 is lt lal 152 701239 Sec 1 6 Transform 1 1 3 7 An LTI system is BlBO stable if and only if the ROC of its transfer function includes 2 1 ie includes the unit circle lt 00 21 11 Z lhnl lt oo cgt BIBO stability 71 Note that this stability criterion is applicable to LTl systems only Example 135 Find all sequences whose z transform is 1 7 4271 X Z 17 3271 2272 Solution We decompose Xz into partial fractions 17 4271 A1 A2 WW 17271 17227139 153 Then we solve for A1 and A2 Method 1 Rearranging the equation we have A117 2271 A217 271 7 A1 A2 7 2A1 A2Z71 Xlzl 17271172271 172 1172Z 1 Comparing terms we solve for A1 and A2 39 A1A2 1gt A1 3 2A1A2 4 A2 72 Method 2 Using 153 X217 was 1 141 sigziwk 3 A1 lX21722 1lz2 A1114LZ 7 2 114 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS Thus we have 2 X 7 Z 17 271 17 2271 We now consider the three possible ROC s that this z tmnsform can have Case 1 ROC gt 2 Using 151 3 1 un 7 2 2nun 3 7 2n1un Case 2 R00 1 lt lt 2 Using 151 and 152 3 1 un 2 2nu7n 71 Case 3 ROClt1 Using 152 73 2n1u7n 71 Imz Case 1 Rez Case 2 Figure 177 ROC for the cases in EbCample 135 u s s e E 30 E 1 f E 1 X X X 1 1 Mil 50 3 3quot 0 O 1 I 5 3 1 1 3 5 5 3 1 1 3 5 5 3 1 1 3 5 n n n a1z1gt 2 b 1 lt1z1lt 2 C1Z1lt 1 Figure 178 The inverse Ztransforms for the 3 possible ROC S of Example 135 Sec 1 6 Transform 1 1 5 I 164 Discrete Time Exponentials 23 are Eigenfunctions of Discrete Time LTI systems Suppose that a discrete time complex exponential 23 is the input signal to an LTl system with impulse response Then the output is W Z hltkgtzltnekgt 23 Z hkzak k7eo If 20 is in the ROC of H27 we can write 2471 23 ZT 71W lzzo 2311190 as shown in Fig 179 101 H20237 26L LTl system if 20 6 ROC of gt with impulse gt response hn Figure 179 An LTI system with ZS as the input The transfer function is the z transform of the impulse response It is also the scaling factor of 2 when 2 goes through the system Recall that we have already considered the case of 20 57m The frequency response H57 0 is o the DTFT of the impulse response Mn 0 the scaling factor when 57 is the input7 as shown in Fig 180 giwon LTI system Hgiwo5jwon gt with impulse gt response hn Figure 180 An LTI system with 67mm as the input 116 CHAPTER 1 ANALYSIS OF DISCRETErTIME LINEAR TIMErlNVARIANT SYSTEMS X 67 f9 I I 27I39 27r w a Input signal spectrum before interpolation Xu 6 f9 I I I I I I I I I I 27r 7r 7r 27r 27I39 T f f T 27r w b The spectrum of the upsampled signal HLPF 67 I I 7r 7r 727 f f 27r w 6 Frequency response of the lowipass lter th 67 st I I I I I I 7r 7r 727 f f 27r LA d The spectrum of the interpolated signal Figure 165 The e ect of interpolation on the spectrum of the input signal x ECE 438 CLASS NOTES FALL 2004 Digital Signal Processing with Applications Ilya Pollak Purdue University 2004 Purdue University All Rights Reserved Chapter 0 Introduction Why does an Electrical Engineering major need a course on digital signal processing Simply because it is everywhere Whether you become a practicing engineer or go to graduate school you are bound to use the material we cover in this course both if you stay in Electrical and Computer Engineering and if you go into many other branches of science and engineering Some application areas are 0 Consumer Electronics watermarking for copyright protection speech recognition image enhancement Military target tracking detection 0 Finance risk minimization pricing Medicine computer guided procedures medical image analysis for diagnostic pur poses Law Enforcement superresolution of low quality video from surveillance cameras signal enhancement The synthetic example of Fig 1 is prototypical of a situation often encountered in many applications a binary signal top was sent but its noisy version middle was received A signal processing algorithm was used to extract from the received signal a close approximation bottom of the transmitted one The next example involves processing of images A digital grayscale image is simply a rectangular array of numbers typically integers corresponding to image intensities usually 0 for black 255 for white and the numbers in between represent various shades of gray see Fig 2 One bin of a digital image is called a pixel There are various types of pictures which result from medical imaging procedures It is often important to design an computer algorithm for automatic extraction of objects from such imagesiobjects corresponding to for instance internal organs or tumors For example the task in Fig 3 is to extract the outline of a thyroid from an ultrasound image While a humaniespecially a trained professionalimay do this quite successfully writing a computer program that would do this is rather tricky because the image quality is quite poor there is largeamplitude noise and blurring CHAPTER 0 INTRODUCTION 6 0 200 400 600 800 1000 6 4 2 72 Tquot0 200 400 600 800 1000 6 4 2 0 72 0 200 400 600 800 1000 Figure 1 Noise removal in 1D original signal top received noisy data middle an estimate recovered from the noisy data using a signal processing algorithm bottom 0 black 255 igure 2 A digital grayscale image is a rectangular array of numbers which typically range from from 0 black to 255 white The underlying algorithm here is nothing more than a difference equation the algorithm produces a movie whose frame at time n 1 is a certain transformation applied to the frame at time n The initial frame is the input image shown in Fig 3a the nal frame is the two region segmentation of 3d This underlying difference equation is very complicated because it is nonlinear multidimensional and also because its coef cients are discontinuous However by the end of this course we will develop a Sec 0 1 Basic Problems 5 b Segmentation with 2000 regions d 2 regions a Ultrasound image c 170 regions Figure 3 Multiscale segmentation of an ultrasound image basic understanding regarding such algorithms Another image processing example that we will touch upon in the later stages of the course is image compression using transform coding The FBI has approximately 30 million sets of ngerprints 300 million ngers which need to be stored7 and 40000 new sets arrive every day These papers7 stored in le cabinets7 used to occupy a whole oor in the FBI building Digitized at 500 dots per inch7 the eight bit grayscale image of a single ngerprint can be as large as 10Mb Electronic storage of this data base would therefore require roughly three million Gb An effective image compression algorithm is needed A key requirement for any such algorithm is that it must preserve all the image features which are required by law enforcement experts in order to identify a ngerprint The FBI ngerprint compression standard uses wavelets7 resulting in acceptable image quality at compression ratio of about 15 JPEG is another compression standard which is widely used for images for example7 many pictures you see on the Web are JPEG images JPEG uses the Discrete Cosine Transform DCT I 01 Basic Problems The signal processing techniques illustrated above all t neatly into the basic diagram shown in Fig 4a Most applications covered in this course will fall into one of four broad categories of problems that one can pose regarding this diagram 6 CHAPTER 0 INTRODUCTION Input x Output y Sx data Output System S gt computer program a A generic system b A software system tumor medical image license plate toll booth video medical imaging 53 5th surveillance camera c An example of a system d An example of a system Figure 4 A generic system and several examples H Filter Design lnput z is known we want to change it according to some objective eg it may be desired to remove some unwanted frequencies from x or to change relative amplitudes of frequency components The question is How to design S This problem has a straightforward programming analogy How to design a com puter program knowing the possible inputs as well as the output speci cations to System IDmodeling Several pairs of m y are known What is a plausible S A programming analogy is to investigate the inner workings of some patented software for which you do not have the source code What you may try to do is to look at how it behaves for many kinds of input data OJ Signal recovery reconstruction enhancement The output y and the sys tem S are known or partially known What is a plausible z Both examples of Fig 4cd fall into this category Eg in Fig 4c an object of interest is imaged by an imperfect device to yield a picture such as that of Fig 3 Given this picture the objective is to reconstruct or partially reconstruct the original object 4 When we start our discussion of systems we will begin with the most basic prob lem in systems analysis How to nd y when x and S are known Later in the course you will be exposed to these problems in the context of several applications Before we plunge into that however we need to carefully study some general techniques for approaching these kinds of problems The framework of Fig 4a is too general to make any progress We will therefore concentrate mostly on one class of systems namely linear timeinvariant LTl systems Some of the reasons for studying LTl systems are c it is still a very rich class of systems capable of modeling many phenomena 0 it is tractable o non linear systems can sometimes be approximated by linear ones Sec 0 2 Approximate Syllabus 7 I 02 Approximate Syllabus 1 to 03 Analysis of DiscreteTime DT Linear TimeInvariant LTI Systems 11 Signals We will start by considering one of the two basic ingredients of Fig 4a namely signals 12 Systems We will continue with the other basic ingredientisystems through which signals ow 13 Fourier Series and Transforms We will then proceed to frequency analysis and look at what it means that one frequency is lower than another and how they can appear to be the same frequency if sampled incorrectly 14 FFT Our next topic will be the Fast Fourier Transform which is not a new transformiit is just an algorithm to ef ciently compute the Fourier transform 15 Sampling The importance of this topic is due to the fact that while most signals in the physical world are continuous time or continuous space signals our most convenient and powerful signal processing tools deal with discretetime and discrete space signals Sampling is how DT signals are obtained from CT signals 16 Ztransform Next we will cover Z transformsia very useful technique for analyzing DT systems and in particular for talking about system stability Random sequences Since many real world signals are too complex to be mod eled exactly we will next consider random signals Instead of asking what is the exact value of a signal at a point we will be analyzing the average behavior of classes of signals We will be interested in the probability that a signal from a certain class attains a particular value at a particular point This framework is necessary in order to effectively address many of the problems considered above If you have a noisy communications channel there may be no way to exactly model the distortion However it could be possible to devise a good probability model of the average behavior of the noise and from that to obtain a good algorithm for combating the noise Similarly it may not be possible to exactly model the distortions that a medical imaging device introduces into an image But there may be a way to say something useful about this distortion on average and then use that to enhance the image quality or extract some information from the images 21 Introduction to Random Sequences Detection and Estimation 22 Speech processing and linear prediction 23 Geometric interpretation of linear prediction and recursive estimation Image processing noise removal enhancement multiscale ltering tomogra phy compression 8 CHAPTER 0 INTRODUCTION It would be incorrect to think that Topics 22 and 3 are the only ones worth studying7 and the rest is just something we have to do in order to get to them There is really a lot of beautiful mathematics herekwhich is what makes this subject really interesting It would also be incorrect to think that the mathematical theory is decoupled from the applications When you study the fundamentals7 you should keep in mind the underlying goaliwhich is to understand and analyze Fig 4a7 for a particular class of systems And the reason why we are interested in this picture is to be able to address the types of problems illustrated above These examples constitute the basic motivation for what we will be studying in this course and are the answer to the question that many students have when learning fundamental theory Wait a second7 why are we studying all this77 The ow of events you should have in mind is shown in Fig 5 l Motivating applications Topics 22 and 3 Input X The basic framework gt System S Output y SX Analysis Topics 1 21 and 23 Figure 5 The ow diagram for the course 18 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Range of S R a set of signals Domain of S D a set of signals numb ers b Figure 19 a A signal is a mapping between two sets of numbers b A system is a mapping between two sets of signals input 1 output or response y Sh a DT signal a DT signal a argument n value nS input 1 Output y Sh 13 6 11 integer Fun tion a real number a DT signal system a DT signal f vide by 3 S divide by 3 b C Figure 110 a A generic block diagram for a system b DT signal divide by 3 C DT system divide by 3 I 12 Systems I 121 What is a System The concept of a system is very similar to that of a signal Recall that a signal is a rule for producing a number in its range given a number from its domain Both the domain and the range of a signal are thus sets of numbers as shown in Fig 19a A system is also a mapping between two sets however both the domain and the range of a system are sets of signals A system is thus a rule for producing a signal in its range given a signal from its domain Recall also that we classi ed signals according to their domains and ranges For example a signal whose domain is an interval of integers and whose range is an interval of reals is called a discrete time signal We can similarly classify systems Speci cally we will distinguish two important classes of systems For a discretetime DT system both the range and the domain are sets of DT signals For a continuoustime CT system both the range and the domain are sets of CT signals A system can be represented as a block diagram as in Fig 110a It is important to remember that the input and output are not single numbers they are signals The 3A more general View of systems which is beyond the scope of this course de nes a system as anything that imposes constraints on a set of signals Sec 12 Systems 19 yltngt cosltngt3 cosn System z cos 5 vvdivide by 377 y cos3 Figure 111 System divide by 3 for the speci c case when the input signal is x cos System S Figure 112 Another View of what a system is speci cation of a range and a domain are crucial for de ning both signals and systems In fact7 the actual mapping may be identical for a signal 1 and a system S the two will however always have different ranges and domains the range and the domain for f are sets of numbers while the range and the domain for S are sets of signals To illustrate this point7 let us consider the example of the discrete time function divide by 3 7 shown in Fig 110b We can also de ne the system divide by 3 7 shown in Fig 110c The two objects are completely different the function divide by 3 takes in a single integer number n and produces a single real number 7137 whereas the system divide by 3 takes in a DT signal z and produces another DT signal y such that for all integer values of n A speci c example of this is given in Fig 111 supposing that the input signal is 00371 the output is another signal7 yn cosn3 In other words7 z is a rule for transforming a single number into another number the system changes this rule into y Another way of thinking about what a system does is that the whole graph of the input signal z is fed into S7 and it produces the whole graph of the output signal 20 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS y as depicted in Fig 112 To emphasize that the input of S is the whole signal m we will be using SM to denote the output signal y rather then The latter notation is also acceptable provided you keep in mind that what it really stands for is for all n ie that S operates on all the samples of z Once the system s response is known it can be evaluated at a particular n is synonymous with and means the n th sample of y where y is the response of system S to input m Very often systems are speci ed by input output relationships As we saw above the expression 9001 ynT7ooltnltoo speci es a system I 122 Properties of Systems Linearity and Time Invariance a Linearity A system S is linear if for any two input signals 1 and 2 from the domain of S and for any two numbers a1 and a2 it satis es Sa1m1 azwzl Spill azslwzl 13 That is if the response to any linear combination of any two inputs is the same linear combination of the responses to these two inputs then the system is linear This is illustrated in Fig 113 If a system is linear we can therefore compute the response to a complicated signal as the sum of responses to simpler signals We will exploit this property many times in our treatment of linear systems Example 12 Let us consider the system speci ed by the following input output rela tionship 24W TL Zzk n 2 0 k0 0 Before trying to determine whether the system is linear it is useful to try to guess the answer Since euery sample of the output is just a sum of seueral samples of the input we guess that the system is linear In order to proue our conjecture we have to show that this system satis es our de nition of linearity Suppose that 1 and 2 are two arbitrary input signals and a1 and a2 are two arbitrary numbers Let m3 alml agzg Then the responses of the system to to 1 2 and 3 are respectiuely as follows nlt0 7 951007 71 Z 07 71 7 k0 0 n lt 0 71 m k n gt 0 12 kg 2 0 n lt 0 Sec 12 Systems 21 input 11 multiply by a1 output Sa111 agzgl input 12 multiply by a input 11 multiply by a1 0 output a1511l a2512 input 12 multiply by a Figure 113 System S is linear if and only if the outputs of the two systems above are identical for any pair of signals I1 and I2 and any pair of numbers 11 and a2 2353a n20 i Zna1m1ka2m2k7 n20 k 0 07 n lt 0 07 n lt 0 TL 71 k k gt 0 ng azkgoz 7 n i alyl a2y2n for all integer n 0 n lt 0 7 Since this holds for any inputs m1 m2 and any numbers a1 a2 the system is indeed linear I Example 13 The system speci ed by the following input output relationship 2mn 37 for all integer n7 is actually nonlinear To show this we need just one example that uiolates the de nition of linearity If in that de nition we set a2 0 and a1 2 we see that if a system is linear then multiplying the input signal ml by 2 must produce the response 2y1 where yl is the response to 1 This does not necessarily happen here supposing that 101 1 22 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS Figure 114 System S is timeinvariant if it commutes with any shift operator in other words if the outputs of the two composite systems above are the same for any input x and any shift no 82 82 for all integer n we get y1n 2 1 3 5 for all integer n but the response to 2m is 2 2 3 7 for all integer n which is not the same as 2y1n 10 Therefore the system is nonlinear I Note again that in order to prove that a system is linear we need to prove the condition stated in the de nition of linearity for every possible pair of inputs In order to show that a system is non linear however one counterexample to that statement is enough b Time Invariance A system S is time invariant if shifting the input results in only an identical shift of the output Otherwise S is called time varying Suppose that y is the response of S to m and that y and m are shifted versions of y and m respectively with integer shift no Zn 2471 r not mn xn 7 no The de nition above says that if SW y for any input signal z and any integer shift no then system S is timeinvariant This is illustrated in Fig 114 Let us now look at the two systems of Examples 12 and 13 and determine whether they are timeinvariant A rule of thumb for determining this is to look for the explicit occurrence of the time variable n in the system speci cation If it does occur explicitly then the system is usually time varying if n only occurs as an argument of signals such as Mn yn etc but does not occur by itself the system is usually time invariant This is not a hard and fast rule however it is only useful for guessing the answer Once we guess the answer we still have to rigorously prove it using the de nition of time invariance Example 14 In the following system speci cation TL Zzk n 2 0 k0 0 2471 n lt 0 7 Sec 12 Systems 23 the time uariable n appears as the upper limit of the summation We therefore guess that the system is time uarying In order to show that the system is time uarying we need to come up with a signal m and a shift n0 for which shifting Sh by no is not the same thing as applying S to a shifted uersion of m Since we are just looking for one example a reasonable strategy is to try a uery simple signal rst For example let 1 for all integer n and let the system s response to m be y Shifting m by no 1 results in z de ned by mn xn 7 1 for all integer n Clearly the signal z is in this case the same as m and is identically equal to one for all integer n Let y and y1 be the responses of the system to the inputs m and m respectiuely and let 3 be de ned by yn yn 7 no yn 7 1 Note that since the inputs m and z are identical we also haue y yl Zn yn17 Mn 2471 For the system to be time inuariant it must be that yn y1n ie that yn 7 1 Taking n 1 we must have y0 But in fact y0 M0 1 while y1 M0 M1 2 7 We therefore have come up with an input signal m a shift no and a time instant n for which the statement in the de nition of time inuariance is uiolated The system is therefore time uarying I Example 15 The system 2mn 3 is easily seen to be time inuariant since shifting the response to m produces yn7 no 2xn 7 no i 3 which is the same signal as the response of the system to m de ned by mn xn 7 no I It is important to emphasize once again the following part in the de nition of time invariance for any x and any shift no This means that in order to prove that a system is time invariant we have to prove it for all possible input signals and all possible time shifts On the other hand in order to prove that a system is not time invariant we only need to come up with one speci c counter example I 123 Impulse Response and Convolution We now take a closer look at LTl systems in the input output form and develop a method to compute the output of an LTl system given its input Speci cally we will see that the output is the convolution of the input with the impulse response Our plan for deriving this fact is 1 Write the input signal as a linear combination weighted sum of shifted unit impulse signals 2 Use linearity to write the response as the sum of responses to shifted impulses 3 Use timeinvariance to nd the response to a shifted impulse Speci cally the response of a time invariant system to signal 6n 7 k is hn 7 k where hn is the unit impulse response 24 CHAPTER 1 ANALYSIS OF DISCRETETIME LINEAR TIMEINVARIANT SYSTEMS 171 3 11 2 1 1 n 72 2 J 71 1 Figure 115 The signal is represented as a sum of impulse signals Let us begin with signal 36n 1 7 26n 26n 717 de ned for all integer 71 As shown in Fig 1157 this signal can be represented as follows 9671 1571n 050n 151n7 where 6k is the unit impulse shifted by k ie 6km 6n 7 k for all integer n and k Similarly7 any arbitrary signal can be represented as the following weighted sum of shifted impulse signals z7262n z7161n m060n x161n m262n Z mk6kn7 for all integer n k7oo Sec 12 Systems 25 lf signal z is put through a linear system S we can use the above equation and the linearity of the system to write the response y of the system as follows 2471 Slg lW S x72672 x7161 m060 m161 m262 W mzcmsimmzcnsemmumsmmgt z1S61n z2S62n Z k5l5kln k7oo co EZMMMML no k7oo where we denoted by hk Shh the system s response to the shifted impulse 6 If system S in addition to being linear is timeinvariant then hkn hn 7 k for all integer n and k where h is the response to the unit impulse 6 Substituting this into Eq 14 yields 00 2471 2 950071017 k7 k7oo which is the formula for the discretetime convolution We will use the following notation to indicate that signal y is the convolution of signal z with signal h y z h The n th sample of y is then z We have thus shown that the output of a discretetime LTl system is the discrete time convolution of the input and the impulse response Example 16 Consider the following input output speci cation of a system 1 71 for all integer n 7n7L 1 0 Let us nd the response to 2 n 7 g7 71 17 0 otherwise 7 The impulse response h of the system is the response to the unit impulse 1 1 n 0 mmamymen sinL 0 otherwise 26 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS hn 1 hn 1m71 1 a a a a a a a a a a a a l l 1 2 3 E k 1 n m1 l gt n 71 0 1 71 0 1 M hn0 a a 1 a a a a a a 1 a a a 1 1 k 0 39 n 39 m0 39 n 71 0 1 71 0 1 hn 7 1 hn 7 1m1 1 2 a a a a a a a a a a a a 1 3 1 5 k 1 39 n 39 m1 39 n 71 0 1 2 71 0 1 2 21W 1 Z 6 a a a 1 a a a 1 n 71 0 1 2 Figure 116 Illustration to EbCample 16 the convolution of h and x is a Weighted lineal combination of shifted Versions of h With the Weights given by the samples of x Therefore the response to m is 00 Z mkhn7 k z71hn 1 z0hn z1hn717 for all integer n k7oo We can eualuate this conuolution by directly calculating the linear combination of shifted uersions of h We start by plotting hn 7 k as a function of n for each h and proceed as shown in Fig 116 A more conuenient method is illustrated in Fig 117 It inuolues plotting signal as a function of k and plotting signals hn 7 k as a function of k for each n Here is the basic procedure for calculating the n th sample of y 1 ip 71 2 for a xed n shift h by n 5 for the same xed n multiply by hn 7 k for each k 0 4 Sum the products ouer k 2 7 k k7oo Sec 12 Systems 27 2 1 12 k M72 7 k hltlt72gt 7 73 H 2 40 hlt gtg n 7239 ltgtltgt 3 2 1 1 2 gtk M72 kgjkh72 7 k 0 M717 k 1 4 2 1 1 2 gtk y71kjkgthilikgt 1 wk 1 Figure 117 Evaluating the convolution sum of EbCample 16 Both methods of course lead to the same result g n 1 2 2471 57 n 0717 0 otherwise I 7 Example 17 To eualuate the conuolutz39on of signals 271m and hn un 28 CHAPTER 1 ANALYSIS OF DISCRETEiTIME LINEAR TIMEilNVARIANT SYSTEMS we substitute the two expressions into the de nition of conuolution xhn Z Q Wumik k7oo n 2 27M k7oo For n g 0 the summation is only ouer nonpositiue ualues of k and therefore can be replaced with 7k QWFI7 for any integer n g 07 where we substituted in 7k When n gt 0 the summation can be broken into two pieces one for nonpositiue ualues of k ie for h from 700 to 0 and the other for positiue ualues ofk ie for h from 1 to n 0 n an z 2 2246 k1 k7oo 2 27m 2 27k m0 k1 1 121 12 1 1712 17 12 3 7 2 for any integer n gt 0 Putting together the two cases 7 2W1 n O y 372 ngt0 I I 124 Further Properties of Systems a Causality A system is causal if the output at any time does not depend on the future values of the input7 ie7 if does not depend on for k gt n7 for any input z and any time n This is equivalent to saying that7 Whenever two input signals are identical up to some time instant no7 the system s responses to them must also be identical up to no It is easily seen that both systems in Examples 12 and 13 are causal Sec 12 Systems 29 For LTl systems there is a simple criterion which allows you to determine whether the system is causal or not Recall that if x is the input to an LTl system with impulse 00 response h then the output is Z 7 Therefore for an LTl system koo to be causal the portion of this summation involving all the terms xn 7 k for k lt 0 must be zero for any input x This can only happen if hk 0 for k lt 0 Conversely if hk 0 for k lt 0 then the system is clearly causal We therefore have the following result Causality for LTl Systems An LTl system is causal if and only if its impulse re sponse h satis es hn 0 for n lt 0 It is important to remember that this criterion is applicable only to LTl systems For example we cannot use this criterion to determine whether systems of Examples 12 and 13 are causal since neither of these two systems is LTl It is purely coincidental that in both these cases the impulse response satis es hn 0 for n lt 0 Consider a system given by the following input output relationship xn 1 7 6n 1 for all integer n The impulse response of this system is identically zero hn 0 for all integer n However the system is clearly noncausal The causality criterion derived above is not applicable since the system is not LTl On the other hand consider the following system 6n 1 for all integer n The impulse response of this system is hn 6n 6n 1 and therefore h71 1 Despite this fact the system is causal Again the causality criterion is not applicable since the system is not LTl In order to determine whether a non LTl system is causal we have to use the de nition of causality b BIBO Stability A system S speci ed by an input output relationship is said to be bounded input bounded output BIBO stable if every bounded input produces a bounded output ie if the fact that is nite implies that is nite Example 18 To show that the system of Example 12 is not BIBO stable let 1 for all integer n In this case n 1n1 n20 2471 H 0 nlt0 which is an unbounded signal Recall that a signal is bounded if a xed number L can be found such that all the sample ualues of the signal are between 7L and L Clearly no such number exists for as n 7gt oo 7gt 00 We thus found a bounded input signal x which produced an unbounded response y Therefore the system is not BIBO stable I 30 CHAPTER 1 ANALYSIS OF DISCRETEeTIME LINEAR TIMEeINVARIANT SYSTEMS Example 19 To show that the system of Example 13 is BIBO stable note that l2zn3l lenl3 for alln Here we used the fact that labl lallbl Maximizing both sides of this inequality ouer n we get lt icorrgl m WM 7 2 i i m 136001 3 MW 3 So ifz is bounded ie if is nite then y is also bounded Therefore the system is BIBO stable I Theorem 11 BIBO Stability for LTI Systems An LTI system is BIBO stable if and only if its impulse response is absolutely summable ie if 2 Wk is nite 15 k7oo Proof Let us rst show the only if77 part Suppose that an LTI system with impulse response h is 131130 stable and let us show that its impulse response must be absolutely summable Note that k7oo Now consider the following input signal 1 h 7k 0 Mk 71 hlik lt 0 Substituting this particular input signal into the above expression for y0 we get that in this case the zeroth sample of the output is 00 240 2 WW k7oo Since z is bounded and since our system is by assumption BlBO stable y must be bounded and in particular y0 must be a nite number This implies Eq 15 Now let us prove the if part Suppose that the impulse response h of an LTI system is absolutely summable and let us show that the system is 131130 stable By assumption the sum of the absolute values of hn is a nite number Let us call this number L 00 2 WW L k7oo Consider an arbitrary bounded input z to the system We have 00 Z warm 7 k k7oo WM Sec 12 Systems 31 l A M E 3 S 3 e k7oo Z Mltzgtlhnikl k7oo MM 2 WWW k7oo The absolute value of each output sample is therefore bounded from above by MzL which means that the output signal y is bounded Since this holds for any bounded input the system is BIBO stable I This stability criterion just like the causality criterion discussed before is only applicable to LTl systems In particular we cannot use this criterion to judge whether the systems of Examples 12 and 13 are BIBO stable since neither of these two systems is LTl It is purely coincidental that the impulse response of the rst system which is BIBO unstable is not absolutely summable The second system speci ed by 2x01 3 for all integer n was shown to be stable in Example 19 Yet its impulse response hn 26n 3 CO CO is clearly not absolutely summable since 2 2 Z 3 00 The BIBO 700 n7oo stability criterion derived above is not applicable since the system is not LTl Moreover consider a system speci ed by the following input output relationship 24W TL Hz s n gt 0 k0 0 n O The impulse response of this system is identically zero hn 0 for all integer n and therefore h is absolutely summable However the system is clearly not BIBO stable since the bounded constant input 2 produces an unbounded response The BIBO stability criterion derived above is not applicable since the system is not LTl In order to determine whether a non LTl system is BIBO stable we must use the de nition of BlBO stability Chapter 2 Random Signals So far in this course we only considered deterministic signals In many practical sit uations this is not enough It is much more convenient to model many processes as random signals For example images acquired with a medical imaging device always have noise The exact intensity values vary from image to image They depend on many different factors which are beyond our control and which therefore cannot be reliably modeled However what we may be able to reliably model is the average behavior of these signals In other words if some averaging procedure is performed over a hundred images perhaps it will be possible to predict how the next hundred images will behave on average Once we have a good probabilistic model we could pose and solve various useful estimation problems in order to eg remove noise and enhance the image quality Our objective for this topic1 will be to develop the analysis tools for random signals We will start by reviewing some basic facts about probability I 21 Introduction to Random Sequences Detection and Estimation I 211 Events and Probability The main concepts are as follows 0 An outcome of an experiment or an elementary event 0 The sample space 9 for an experiment is the set of all possible outcomes of the experiment 0 An event is a set in the sample space2 We say that event A occurs if one of the outcomes in the set A occurs 0 A probability measure is a function which assigns a probability a number PA to each event A and which satis es the following properties 1Probabilistic modelingeie assigning probabilities t0 eventsewill not be studied here We will always assume either that a probabilistic model is given or that it can be easily constructe 2Not every set in the sample space must necessarily be an event with a wellde ned probability We will not discuss this here deferring to advanced courses on probability and measure theory 118 CHAPTER 2 RANDOM SIGNALS 1 It is non negative PA 2 O 2 The probability of the whole sample space is 1 PQ 1 3 It is countably additive 00 00 P Aigt ZPAi if Ai Aj Q for any i j i1 i1 Recall A1 1 A2 A1 U A2 11111011 Of A1 A2 A1 or A2 ie the union of A1 and A2 consists of every outcome which is in A1 or A2 or both A1A2 A1 A2 intersection of A1 A2 A1 and A2 ie the intersection of A1 and A2 consists of every outcome which is both in A1 and in A2 note that A1 A2 9 means that A1 and A2 are mutually exclusive events A0 A complement of A not A ie the complement of A consists of all the elements of Q which are not contained in A Example 21 Consider a random experiment where a fair six sided die is thrown once Its sample space is Q 1234 5 6 and We de ne the following euents A1 an euen number turns upquot ie A1 246 A2 a prime number turns up quot ie A2 23 5 A3 one turns upquot ie A3 We can calculate PA1 l l by property 5 additiuity 6 2 A1 1 A2 A1 U A2 the number which turns up is either euen or prime or bothquot 2737 47 57 6 A1A2 A1 A2 the number which turns up is both euen and primequot 2 Sec 2 1 Introduction to Random Sequences Detection and Estimation A1 an odd number turns upquot 1 3 5 A2 a non prime number turns upquot 1 4 6 ZlUZZ 13456A1 A2 Zl A z 1A1UA2 I 212 Conditional Probability In observing the outcomes of a random experiment we are often interested in how the outcome of one event A is in uenced by that of another event B For example in one extreme case A may always occur whenever B does as in Fig 21a while in the other extreme case A never occurs if B does as in Fig 21b A a A always occurs if B does b A never occurs if B occurs Figure 21 Two illustrations of dependence between events A and B To characterize the relationship between A and B we introduce the conditional probability of A given B which is the probability of A occurring if B is known to have occurred De nition 21 The conditional probability of A given B is de ned as follows dif PA m B PltAiBgt i PUB assuming that PB gt 0 Conditional probabilities specify a probability law on the new universe B it can be shown that they satisfy all three axioms Therefore all general properties of probability laws remain valid for conditional probabilities 120 CHAPTER 2 RANDOM SIGNALS Example 22 In the preuious die throwing experiment Ex 2 what is PA1 A2f2 PA1 A2 Peuen number turns up giuen that a prime number turned up PA1 A2 P A2 P2 P2 3 5 16 1 2 1 g If we look at Fig 22 we immediately see thatPA1 A2 because giuen that A2 has occurred only one outcome ie 2 out of three equiprobable outcomes 235 makes A1 occur A2 Figure 22 A diagram for the diethrowing experiment When we are conditioning on A2 we are no longer operating in the whole of 9 A2 becomes the sample space and hence all probabilities conditioned on A2 are normalized by PA2 In particular PA2 1 Properties of conditional probabilities 10 PA B 1 21fA B Q then PA B 0 3 If B C A ie B a A then PA B 1 Sec 2 1 Introduction to Random Sequences Detection and Estimation A Figure 23 When B is a subset of A7 PAlB 1 4 If 1411427 are mutually exclusive with 00 A U Ak k1 then we have Figure 24 PAlB ZPMMB k1 5 Total Probability Theorem A1 B A2 A3 Figure 25 The set B is contained in the union of mutually exclusive sets A1 A2 and A3 122 CHAPTER 2 RANDOM SIGNALS If the sample space is partitioned into sets A17 A27 and A3 as in Fig 257 then the probability of any event B can be computed as follows PB PBoA1PBoA2PBoA3 PBlA1PA1 PBlA2PA2 PBlA2PA3 More generally7 133 ZPBlAiPAi7 if Ai s are mutually exclusive and B C UAi i 6 Bayes7 Rule is used for combining evidence It tells us how to compute prob abilities PAilB if PAi and PB are known Here is some commonly used terminology 0 Prior model probabilities PA 0 Measurement model PBlAl the conditional probability to observe data B given that the truth is A o Posterior probabilities PAilB the conditional probability that the truth is Ai given that we observed data B PAl O B PBlAiPAl W W PltBgt total pergrbearsility PB AiPAi ZPBlAjPAj 739 7 Multiplication Rule n n71 P Aigt PA1PA2lA1PA3lA1 m A2 P A AJ i1 j1 provided that all the conditioning events have positive probability Example 23 You leaue point 0 choosing one the roads 0B1 0B2 0B3 0B4 at random with equal probabilities Fig 26 At euery subsequent crossroads you again choose a road at random with equal probabilities What is the probability that you will arriue at A Solution fork 1234 1 Parriue at Bk from O Z Sec 2 1 Introduction to Random Sequences Detection and Estimation 0 B4 Figure 26 Illustration of Ebtample 23 Applying the property 5 of conditionalprobabilities we get the notation X lt Y means that we arrive at X from Y Parriye at A PA lt BllBl lt O PB1 lt O PA lt leBg lt 0 PB2 lt O PA lt Bngg lt 0 PB3 lt O PAlt B4lB4 lt OP B4 0 i 1 11 11 1 2 1 7 3 4 5 4 i 1 10153012 7 4 30 i 67 7 120 This property often allows us to break complicated problems into simpler steps and e iciently solve them This basic principle is at the heart of Kalman ltering and more general techniques of estimation on graphs as well as e icient coding algorithms I 213 Statistical Independence De nition 22 If PA B PAPB then the events A and B are said to be statistically3 independent Otherwise they are said to be statistically dependent Recall that we introduced conditional probability to talk about the information that the occurrence of one event provides about another event Independent events constitute a special case when no such information is provided Since PA O B 3The quali er statistical is used to avoid confusion of the notion of independence of events or random Variables With the notion of linear independence of Vectors When there is no danger of ambiguity We Will simply say that events A and B are independent CHAPTER 2 RANDOM SIGNALS PAlBPB PBlAPA7 independence is the same as PAlB PltAgt ifPltBgt y 0 PBlA PB if PA 7 0 In other words7 the occurrence of B has no in uence on the probability ofthe occurrence of A7 and Vice versa Example 24 Pick a card from a full deck and de ne the following events A the card picked at random from a full deck is a spade B the card picked at random from a full deck is a queen Are the events A and B independent The probabilities of events A and B are 13 1 PA 51 4 1 PB 5 Then the probability of their combined occurrence is PA O B Pthe card is the queen of spades Hence A and B are independent Example 25 Disjoint does not mean independent In fact if the events A and B are disjoint and if PA gt 0 and PB gt 0 then PA O B P03 0 PAPB gt 07 and therefore A and B are dependent Statistical independence of a collection of events A collection of events is called inde pendent if information on some of the events tells us nothing about probabilities related to the remaining events De nition 23 A17 A27A37 A are called statistically independent if P A Upon is is Sec 2 1 Introduction to Random Sequences Detection and Estimation 125 for every subset S of 1 2 n In other words PA Aj PAPAj for every pair i j PA Aj Ak PA39PAjPAk for every triplet i j k PA1 A2 Q An PA1PA2 Example 26 Throw a pair dice and de ne the following events A1 rst die turns up an odd number A2 second die turns up an odd number A3 the total of both numbers is odd Are these events pairwise independent Furthermore are they independent Solution We have PA1 PA2 12 Assuming that all 36 outcomes of the pair of throws are equally likely PA1 A2 936 14 PA1PA2 and therefore A1 and A2 are independent Moreover 1 PA3 Given that A1 has occurred A3 occurs if and only if the second die turns up even PA3iA1 PA3 A1 and A3 are independent Similarly 1 PA3iA2 5 PA3 A2 A3 are independent However A3 cannot occur if A1 and A2 both occur and so PA1 A2 A3 0 whereas PA1PA2PA3 7g PA1 A2 A3 Thus A1 A2 and A3 are not independent I 214 Random Variables De nition 24 A random variable is an assignment of a value number to every possible outcome We refer to this number as the numerical value or the experimental outcome of the random variable In other words a random variable is a function from the sample space to the real numbers 9 gt R 126 CHAPTER 2 RANDOM SIGNALS Example 27 Suppose our experiment consists of two independent tosses of a fair coin Let X the number of tails Then X is a random uariable 0 Notation 7 Random variable X 7 Experimental value x or k or any other letters 0 We will often analyze random variables without specifying the experiment which they come from However it is important to always remember that a random variable is a function from the sample space of some random experiment to a set of numbers A random variable is called discrete if its range the set of values it can take is nite or at most countably in nite De nition 25 Probability mass function of a discrete random uariable X is X is a continuous random variable if there is a function fm 2 0 called the probability density function of X or pdf of X such that PX E B fmzdm for any B C R B Note that for a discrete random variable PX e B 2pm 63 De nition 26 The cumulatiue distribution function cdf of a random uariable X is de ned as PX This de nition applies to any random uariable X Example 28 Throw a die X is the number which turns up Sec 2 1 Introduction to Random Sequences Detection and Estimation 127 T O 4 5 6 7 8 O 1 2 3 4 5 6 7 8 X X a PMF of X b GDP of X Figure 27 The pmf and Cdf of the diethrowing experiment Example 29 Toss a point at randomquot onto the interval 07 6 X is the point where it lands I 39 I I I 39 I I PDF fXX a PDF of X b GDP of X Figure 28 The pdf and Cdf of the pointtossing experiment Some properties 0 is non decreasing o 0 as x a foo alaszaoo 128 CHAPTER 2 RANDOM SIGNALS o If X is a continuous random variable o If X is a continuous random variable PaltXltb Pa XltbPaltX bPa X b Fxb 7 Fxa abfxzdz Fxltbgt Ommdz 1 fXxd 1 Expectation or expected value E goo if gltzgt me dz pdf of X is called the expectation or expected value of the random variable gX Note when gX is a discrete this is just E9X Z 9PX90 Expected value of X Second moment of X Variance of X VarX EX 7 EX2 0 x 7 EX2fXzdz The expectation is linear in the following sense EagX bhX c aEgX bEhX C Therefore EX EX2 E X2 2XEX EX2 19le 2EX 2 EX2 E X2 7 ltEltXgtgt2 Sec 2 1 Introduction to Random Sequences Detection and Estimation 129 Example 210 Throw a die and let X be the number that turns up The expected value ofX is m1 1 1 2 6 6 6 21 6 735 Note that EX is not necessarily a value that X can assume The second moment ofX is EX2 im2PXm 11 1 1 1 1 1 E 114 g 111736 6 91 6 1 15 6 The variance ofX can then be calculated using Eq 21 VarX E X2 7 EX2 i 91 49 6 4 7 1827147 12 i 35 1239 Example 211 Random variable X is uniformly distributed on 06 Fig 29 fXI 6 l O 6 x Figure 29 The pdf of X in Ebtample 211 130 CHAPTER 2 RANDOM SIGNALS The expected value ofX is 6 2 EXO 6d712 3 The second moment of X is 61 3536 EX2 2d 12 l 06 a 180 The variance of X is VarX 12 7 32 3 I 215 Two Random Variables De nition 27 The joint cumulative distribution function for two random variables X and Y is de ned as FXymy PX m and Y The joint probability density function for X and Y is 82FXY7 y fXY967 y awy We have m y FXyzygt fXylta6gtd da 00 00 The individual pdf s fXm and fyy are then called marginal pdf s to distinguish from the joint pdf fXymy How can we get fXm and fyy from fXyzy7 We note that PX m PX xYltoo FXYz7 00 1 00 fX3tz7 3MB la 22 00 00 On the other hand7 in the previous section7 we saw that 1 PX x fXada 23 00 Identifying the integrands in Eq 22 and Eq 237 we see that 00 ma mo BM 700 or fXz 0 fXymydy 24 Sec 2 1 Introduction to Random Sequences Detection and Estimation Similarly7 fYW 1 fXYmydz Example 212 Let f 7 A OSySz l X Y 7 07 else 1 Find A 2 Find 186 Solution Figure 210 The support of the function ayLy of Example 212 is the shaded triangle Within the triangle7 fx7ye y A 1 To nd A 00 CO 1 fXYzydm dy 00 00 A area of the triangle 1 7 A 5 a A 2 2 We can nd fX by using Eq 1fXYlt7Z 9gtdy fad 1 Ie in order to nd the marginal pdf of X we integrate y out by computing the line integral of ny along the dashed segment in Fig 210 More generally 1 Qdy 2x nggl otherwise fX fXY7yd g 7 132 CHAPTER 2 RANDOM SIGNALS fXW Figure 211 The marginal density from Example 212 De nition 28 The random variables X and Y are independent if hex9671 fX90fYy This de nition of independence implies that any event involving X is independent of any event involving Y Conditional density baaW y if fXgtY 7 3 fYW If X and Y are independent then 7 7 fXfYy 7 qule 7 y 7 fyy 7 fX7 ie7 the knowledge that Y y does not provide any information about X Expected value EltgltXYgtgt W W gm mime was dy Note that this de nition is consistent with our previous de nition of the expected value of a single random variable EltgltXgtgt 1amp1m9fxym7yddy 1995 fXYm7ydydm co cogfxdm Sec 2 1 Introduction to Random Sequences Detection and Estimation 133 Correlation of X and Y is EXY Covariance of X and Y is m CovltX Y if E M 7 MW 7 Eco EXY 7 EXEY De nition 29 X and Y are uncorrelated if Xy 0 The following are some remarks about these terms 1 X and Y are uncorrelated if and only if EXY 2 If X and Y are independent then they are uncorrelated because in this case 00 00 00 00 EltXYgt 22mm was dy zyfxltzgtfyltygtdz dy OO 00 OO 00 commast Ozmm EXEY 3 However ifX and Y are uncorrelated it does not imply that they are independent But if X and Y are eg Gaussian random variables the notions of independence and uncorrelatedness are equivalent 4 VarX CovX X 5 The correlation coe cient is CovX Y 0 VarXVa Y It is possible to show that 71 pr 1 and that 39 PXY 0 a X and Y are uncorrelated 0 prlXaYbwithagt0 0 pr7l XaYbwithalt0 Why do we need the notion of uncorrelatedness in addition to independence This is because 0 it also indicates to what extent X and Y are related and in some cases is equiv alent to independence 0 to determine whether X and Y are independent we need to know nyzy to determine whether X and Y are uncorrelated we only need to know the rst and second moments which are easier to estimate 134 CHAPTER 2 RANDOM SIGNALS I 216 Random Sequences De nition 210 A DT random or stochastic process or DT random signal or random sequence Xn 700 lt n lt 00 is a sequence of random variables 39 de ned on the same probability space Alternative notation Xn 7X717X07X17m Example 213 Suppose we flip a coin every second and assign 7 1 if the n th flip is heads X01 7 71 if the n th flip is tails This sequence of binary random variables Xn is a random process The observations associated with physical processes are often most appropriately modeled as random It is typically the case however that their probability distribution is unknown and has to be deduced from the data For example when we ip a coin we do not know a priori that Pheads if the coin is unfair then we may have Pheads 7 I 217 Estimating Distributions Example 214 Repeatedly and independently flip a coin and let X01 7 1 if the n th observation is heads 7 71 if the n th observation is tails Figure 212 Probability mass function of Xn for the cointossing experiment Suppose we do not know p How do we learn it from observing Xn2 Sec 2 1 Introduction to Random Sequences Detection and Estimation 135 Solution We construct the empirical distribution of Xn by tallying the number of occurrences of heads and the number of occurrences of tails Fig 213 71 Heads Tails 15mm 1 1 I3N 2 A 3 PN 4 1 1 x A number of heads out of N experiments pN Figure 213 Estimated probability distribution of the cointossing experiment How good is this estimatef2 Let 07 else Then EHn p11p0p7 E p7 and therefore VMHW p 7 292 Note that N ZHW A 711 pN N 7 and that it is a random uariable Its expected value is 1 N E W2mm n1 1 N Ein 32l The expected value of our estimate E is equal to the quantity that we are trying to estimate Estimators that have this property are called unbiased Let us now calculate VarpN First consider two properties of variance 136 CHAPTER 2 RANDOM SIGNALS 1 If we scale the random variable W by a constant 04 the resulting variance will be scaled by 042 VaraW E aW7EaW2 E MW 7 mm QZE W EW2 anarW 2 What is the variance of a sum of random variablesf2 It depends For example a Suppose W1 W2 WN W then N Var W VarNW NZVarW n1 b Suppose W1 W2 WN are independent random variables then N N 2 Var W E i 1 n1 E 044 7 EW2 n1 2 2 Wm EWnWm EWm nm N 2E WV 7 EWn2 n1 2 2 EW 7 EWEWm 7 EWm N nm ZVarWn n1 Thus if we only made one experiment but counted its result N times 1 N V A V H arpN ar NE 1 N WVar 71 VarHn Sec 2 1 Introduction to Random Sequences Detection and Estimation 137 However if the N experiments are independent then 1 N VarpN mVarZHn n1 1 N m ZVarHn n1 1 NVarHn 19 N Therefore Var gt 0 as N gt 0 Estimators whose variance approaches zero as the sample size grows to in nity are called consistent estimators We have therefore just shown that 131V is a consistent estimate of p In other words as the number of experiments increases our estimate becomes more reliable Since the estimate itself is a random variable the variance of the estimate gives us a measure of its reliability Roughly speaking a larger variance of the estimate implies a larger spread of distribu tion Hence we have a larger chance of ending up with an estimate that is far from the correct value ofp On the other hand if the variance of the estimate is small there is a higher chance of the estimate being in the vicinity of the correct value ofp as shown in Fig 214 Note that this gure is not meant to be a precise characterization of this particular estimator since for example it is a discrete random variable and therefore its PDF is actually a sequence of impulses fmv f m i p a p a a Distribution of 131v for small N b Distribution of 131v for large N Figure 214 For larger Values of N the Variance of 131v is smaller Which means that the estimate is more likely to be Close to the correct Value of p Example 215 X1 XN are independent identically distributed iid contin uous random variables with unknown pdf How to estimate One possible method is 1 Partition the m axis into L intervals x0z1 12 xL1 mL CHAPTER 2 RANDOM SIGNALS Figure 215 An unknown distribution to be estimated 2 Estimate 1 p Px391 Xn M71 as follows A number of outcomes that fall into the i th interual PN N 3 Note that if is approximately constant on the i th interual nub m then m fltzgtdz m M x 7 M71 Hence we can estimate on the i th interval as 4139 N PN 1 3 7 35H Unless something is known a priori about how fast changes this method will not necessarily be successful in estimating Let 17 2f 95121 S X01 S 95w 0 else Hit Then EHiln 19 E935 Wizf mw pa which means that our estimate of p is unbiased We also haue N i 239 Ai Z7 Z7 Var pg r r 2 Var N 2 1707 pm Erma Nmiimi1 Sec 2 1 Introduction to Random Sequences Detection and Estimation 139 50 bins N 100 08 I I I I I I I I 1 0 1 10 bins N 100 1 0 1 50 bins N 10000 I 53000 NCOJ Figure 216 The tWo upper panels illustrate the tradeOH between the number of bins and the size of a bin if the bins are too small the estimate can be Very noisy if there are too few bins the estimate may be too coarse The bottom panel illustrates the in uence of the number N of experiments for the same bin size increasing N leads to a less noisy estimate Therefore if the bin size 7amp4 is small we need a large number N of experiments to get a reliable estimate However if the bin size is too large then may not be approximately constant within each interval resulting in an estimate which does not track the actual uery well This trade o is illustrated in Fig 216 Sometimes it is not necessary to estimate the whole pdf Often there are practical situations when there are only one or several parameters of interest Example 216 Suppose we are interested in measuring some quantity A but what we 140 CHAPTER 2 RANDOM SIGNALS actually measure is Y1 A X1 V what we actually observe 5 4mm of Wm measurement noise Y2 A X2 second measurement independently obtained YN A XN Suppose it is known that the pdf of Xn is the same for all n and 0 but the speci c form of the pdf is unknown How do we estimate A Solution One possibility is the following estimate 1 N ANNYn Then 1 N 1 N E AN N EEO71 N ZEA Xn 1 n1 7 A i unbiased A 1 Var AN W NVarXn VaTXn VW WQX 0 as N gt oo 7 consistent N 7 I The uariance approaches zero as the number of measurements increases to in nity Central limit theorem Suppose 1 N Zn gmn where Xn are iid with mean zero and uariance 0392 Then as N gt 00 the CDF of Zn gt Gaussian C DF with mean zero and uariance 0392 The pdf of a Gaussian normal random uariable R with mean m and uariance 02 is 1 Jim fRr e 202 27117 0 For large N the distribution of our estimate is approximately Gaussian 0 As N gets larger it becomes more and more probable that AN which we compute from our obseruations is near A Sec 2 1 Introduction to Random Sequences Detection and Estimation 141 Figure 217 The pdf of the estimate AN of EbCample 216 A widely used parameter estimation strategy is maximum likelihood or ML estimation To describe it7 we will use the following notation If the probability density of a random vector Y depends on some non random but unknown parameter A7 we call it the likelihood of A and denote it by fY AyiA Given an observation y of Y7 the maximum likelihood estimate AML of the parameter A is the number which maximizes the likelihood function with respect to A Am argmgfoiAMAi Eg7 suppose that in Example 2167 each Xn is a zero mean Gaussian random variable Then each Yn is a Gaussian random variable with mean A Since the Xn s are independent7 so are Yn s7 and therefore the likelihood function in this case is N inAYiA H fYniAyniA39 n1 Taking the log of this and substituting appropriate expressions for Gaussian densities7 we get N 10 fYAYiA ZlongniAyniA n1 N 1 W 7 A 7 7 log m i 7 which means that maximizing the likelihood is equivalent to minimizing 7 A2 which is done by setting to zero the derivative with respect to A N N A 1 N 22147 2 NA 7 0AML N n1 n1 n1 which means that the estimate we considered in Example 216 is the ML estimate in this case 142 CHAPTER 2 RANDOM SIGNALS Example 217 Estimate the variance of iid random variables X17 7XN Solution 1 If the mean m is known try N EGG 7 m2 X n1 N Then A 1 E A NE 7 m2 VarXn unbiased 2 If the mean m is unknown a estimate the mean as in Example 216 1 N m W Z Xn I try 5 i 1 N X A 2 7 N n 7 m 7 1 N X A 2 7 g n7m7m7m 1 N 1 N W ZltXn 7 7702 7 2W 7 m N ZltXn 7 m 1 n1 m7m 2mim2 1 N t W Z 7 7 7702 n1 mimv 1 N 7 ZltXn 7 7702 7 m 7 7702 n1 E vmX 7 Var m VarXn 7 M N 7 1VarXn 7 biased Sec 2 1 Introduction to Random Sequences Detection and Estimation 143 N A 1 2 7 m2 is unbiased because 7 A N A A N A 7 7 NilijQ N71 A VarXn I 218 Sampling From A Distribution Suppose you have hypothesized or built a probabilistic model ie7 you have assumed or estimated a probability distribution of your observation eg7 using techniques from the previous section It is often very important to be able to synthesize samples from this probability distribution Eg7 texture synthesis is needed in rendering7 printing7 and other computer vision and imaging applications One possible approach to texture synthesis is 1 Model texture as a 2 D random process 2 Synthesize an image or a texture patch by sampling4 from the probabilistic model While thorough consideration of the texture synthesis problem is beyond the scope of this course7 we now consider the problem of sampling from a distribution Example 218 Suppose we have a cdf How do we generate samples of a random variable with this cdf Solution Suppose we know how to generate samples of a uniform variable Y whose pdf is shown in Fig 218 fYl Figure 218 The pdf of the uniform Variable Y in Ebrample 218 What is the cdf of W Fglor 4Note the Word sampling used here means drawing a random sample from a probability distribution Which is completely di erent from the meaning it had in the earlier sections Which dealt With converting CT signals to DT and Where sampling meant discretization 144 CHAPTER 2 RANDOM SIGNALS Figure 219 An illustration of Fgl because FX Fwltwgt PltW w PltFg1ltygt w PltY Fxltwgtgt Fxltwgt So the cdf of W is FX Use Fgl to transform the uniform distribution into Ex I 219 Filtering A Random Process What happens to a random process when it is put through an LTl system In general7 this is a very dif cult question however7 we can say what will happen to its rst and second order statistics De nition 211 If Xn Yn are real ualued random sequences the autocorrelation function of Xn is TXXUHW EXmXn How strongly are the points ofX at m and n are correlated The cross correlation function of Xm and Yn is eggm n How strongly are X and Y correlated A note on complex ualued random variables and processes CouXY EX7mXYimy Correlation E XY rXXm7 n E XmXn yarm7 n E XmYn De nition 212 A random sequence Xn is wide sense stationaryquot W35 if Sec 2 1 Introduction to Random Sequences Detection and Estimation 145 1 E is constant for all n 2 rxxm n TXXlt07n7m for any n7 m abuse of OZLZZO H rxxn 7 m If both X and Y are WSS then chkn chn 7 What will happen to the mean and autocorrelation of a random process when it goes through an LTl system Consider the system illustrated in Fig 220 Real Valued7 WSS7 with X mean itx 7 and autocorrelation TXX LTI system With real Valued Figure 220 System With a WSS input Given pm rXXn7 and hn7 can we nd and Tyy 1 EYn E Z hm 7 mXm linearityofE Z hltnimgtEltXltmgtgt m7oo 00 since Xn is W55 2 I101 7 mnw m7oo 00 146 CHAPTER 2 RANDOM SIGNALS 2 Rxmm E XmYn E Xm Z hm 7 kXk k7oo Z hm 7 kE XmXk k7oo i0 hn7krxxk7m k7oo 55 Z W 7 m 7 mm lt1 1700 hrXXn7m 7 only depends on 7177717 tan71 h Txxw 3 Taximm E YmYn WM 2 M71 kXk k7oo Z hm 7 kE XkYm k7oo i hn 7 kchm 7 k k7oo i hn 7 kCYXk 7 m k7oo 55 Z W 7 m 7 zgtcyxltzgt k7oo hcyx 717771 h ch m 7 n7 where 7101 h7n Again7 TYYltm77l TYYlt7Lmgt ryyn 7 m Also7 we found that is constant Y ls WSS39 Sec 2 1 Introduction to Random Sequences Detection and Estimation So7 if the input to an LTl system is WSS7 then the output is also WSS7 with Tyyltngt hi CXY hhTXy gtk CYX reversal Figure 221 Decomposition of the steps in calculating TYY7 L from rXX Example 219 Let Yn Xn Xn 7 1 in the system illustrated in Fig 222 Find ryyn Ie how correlated is the output with itself shifted by some lag ualue n iid Gaussian zero mean and Variance 7 Figure 222 System in Example 219 Solution won EXltngtXltnmgt 7 0 m 0 7 07 m 7 0 since X is independent 03430 A process such as this for which Xn is uncorrelated with Xm unless n m is called a white noise process chm 148 CHAPTER 2 RANDOM SIGNALS Alternatively chm EXnYnm EXnXnmXnm71 7 a ifm00rm1 07 else because of independence 1 1 0 0 Tyyltmgt hgtkeXym 71 0 0 1 217 0 0 Figure 223 Scatter plots for EbCample 219 Yn 2 Yn Xn Xn 3 5 5 5 5 3 Yn 1 3 1 3quot Xn 1 Sec 2 1 Introduction to Random Sequences Detection and Estimation 149 150 CHAPTER 2 RANDOM SIGNALS Estimating Correlation Functions For Widesense stationary processes EXnXm EXnYm How to estimate TXXm7 Again compute sample averages MIT ml N 0 A An estimate of Txx2 K autocorrelation TXXltmgt 7 cross correlation erm 3 4 5 6 l lt Xlt0gtXlt2gt Xlt1gtXlt3gt Xlt2gtXlt4gt XltK71gtXltK1gt gt More generally if N points of Xn are available form 1 Nilmlil W Z XnXnlml 7N71m N71 n0 TXXm What is this useful for Well there are a lot of different applications one of which is radar detection The key to this application is the following property of the autocorre lation function lTXXwH S Txx0 And in fact for many random processes which model natural phenomena the random variables become less and less correlated as they become more separated in time i 7 2 go man 7 WM So a typical autocorrelation function might look like the one in Fig 224 rxx Figure 224 A typical autocorrelation function Sec 2 1 Introduction to Random Sequences Detection and Estimation 151 A random variable is very much correlated with itself it may be somewhat corre lated with its neighbors and is basically uncorrelated from random variables which are far in the future or in the past An estimate of the autocorrelation function may look like Fig 225 1 05 5 g 0 O5 100 50 O 50 100 Figure 225 An estimate of the autocorrelation function In radar or sonar you transmit a signal X n and then receive its re ection from an object By measuring the delay between Xn and Yn you can estimate the distance to the object Xn transmitted signal Yn received signal attenuated noisy delayed version of X It is usually impossible to tell the delay just by looking at Xn and However by comparing an estimate of cross correlation ch such as the one shown in Fig 226 to the estimate of TXX it becomes easy to estimate the delay 152 CHAPTER 2 RANDOM SIGNALS 1 05 E Q o O O5 100 50 O 50 100 Figure 226 An estimate of the crosscorrelation function In this gure the delay is n 50 I 2110 Noise Removal and Detection For the past few sections we have been considering random sequences 7 that is se quences of random variables Exactly predicting the behavior of such a sequence is impossible but as you have learned in the past three sections in some cases it is pos sible to estimate certain parameters 7 like the mean or the autocorrelation functions 7 from a realization of a random sequence The main idea here was that if you have a sequence of identical random variables preferably independent you can estimate cer tain parameters by computing time averagesln this section we continue the discussion of estimation and consider examples of detecting or estimating a signal corrupted by additive noise Problem 1 Binary hypothesis testing in DT additive white Gaussian noise Hypothesis H0 Y W Hypothesis H1 Y x W Where W is a vector of uncorrelated zero mean Gaussian random variables with vari ance 02 For example a situation like Fig 227 can be encountered in a communication system One possible objective having observed Y y choose H0 or H1 so as to maximize the likelihood of the observation H1 PYH1YlH1 2 PYHOYlH0 Ho Sec 2 1 Introduction to Random Sequences Detection and Estimation 153 Noise7 W Transmitted s ignal sm a 7710 500 YsmW m0 or 51 X or m 1 7 1 Figure 227 Model of a communication system H1 N n 7w n 2 N 2 H 1 W 20 2 H 1 6 20 1 V 27117 1 V 27139 Ho i log i log H1 1 N 1 N m 29471 9001 2 m ZWWW 1 n1 H0 H1 N N 7 2 WWW 224009001 9001 2 ZWWW 1 n1 H0 H1 N N 2 2 WWW 2 2M n1 n1 H0 H1 2lty7Xgt 2 H X HZ H0 H1 lty7 Xgt lt H X HZ Ho 154 CHAPTER 2 RANDOM SIGNALS o calculate the projection of the data y onto X o if the coefficient is greater than decide that X is present if not decide that X is not present It is Very likely that this y resulted from x Say 1 It s Very likely that this y is just due to noise Say Ho Everything which is l x Figure 228 Vector spa3e interpretation of hypothesis testing This is quite intuitive In order to isolate X we need to represent our observations Y in a basis where X stands out namely a basis where X is one of the basis vectors If indeed Y was equal to X plus noise we would eXpect its projection onto X to be large whereas otherwise there is no reason to eXpect this projection to be large Let us now generalize this idea to a slightly more complicated situation Here we do not know the underlying signal X exactly but we know for example that it is a sinusoidal signal or a sum of sinusoids If we represent a noisy sinusoid in a Fourier basis by computing its DFT we would see two large spikes corresponding to the frequency of the sinusoid and then there will be noise One simple method to get rid of noise would then be to H set all the coefficients which are below a certain threshold to zero so that we are left with just these two spikes to reconstruct our signal from the remaining coefficients Now let us analyze this procedure a little more closely Problem 2 Noise removal Via representations in orthogonal bases Let Y X W where X is the sum of a few non random sinusoids of unknown frequencies with suffi ciently large amplitudes 155 Sec 2 1 Introduction to Random Sequences Detection and Estimation 2 W is the vector of uncorrelated7 zero mean random variables with variance 0 WW W1 W ltgt WN71 TakeDFT YAYAAWW7 where Y is the DFT of Y and A is the DFT matrix 1 1 1 392 1 392 1 392 1 6771 1 6771 2 67N71 A 392 N71 392 N71 392 N71 1 7 MN 1 67 7rN 2 6 MN Nil 2yon 0 n g N7 1 then kkoorkN7k0 07 otherwise 1 Suppose acos 320 2 What is W the DFT of white noise W E W EAW AEW 0 Where E denotes E W0 E W it is the mean of W 156 CHAPTER 2 RANDOM SIGNALS The covariance of W AW 7 EW7mW7mWH W0 mWlt0gt E W1mwquot1 lt 7 mWOgt H gt WN 7 1 7 mWUm Var ltWOgt Cov ltW0 WN 71 i 001 ltWN 71W0gt Var ltWN 71 AE WWH AH A AH AAHUZ 1 NaZAA l the IDFT matrix B A l FAH 7 AH NA l N02 So7 the DFT of white noise is white noise with zero mean and standard deviation xJVU As long as N WU ltlt QT we can remove noise by thresholding the DFT coefficients 0 Calculate DFT of Y 0 Set all coe icients Whose absolute value is less than7 say 3W0 to zero 0 Reconstruct Sec 2 1 Introduction to Random Sequences Detection and Estimation Xn xrn 600 500 400 300 200 100 DFTXnWn 3 3 I 2 2 I 1 E 1 c 1 g 1 2 2 I 3 3 0 500 1 000 0 500 1000 n n a Noisefree sinusoid b Noisy sinusoid 3 2 E 1 E 1 E 2 L5 3 0 500 1 000 n d DFT of noisy sinusoid c Reconstructed sinusoid Figure 230 Noise removal through thresholding DFT coef cients CHAPTER 2 RANDOM SIGNALS 158 3 2 1 E 3 o E X E 1 gt2 2 3 0 500 1 000 n n a Sum of two sinusoids b Noisy signal 3 2 E A 1 5 o E X 1 E 2 o 3 0 500 1 000 n c Reconstruction d DFT of noisy signal Figure 231 Noise removal for a sum of two sinusoids Note that the reason why we chose the Fourier basis is that we knew that our signals of interest were sinusoids In other scenarios you would choose a different basis Note that our analysis would still hold for any orthogonal basis because in our derivation of the fact that the transform of white noise is still white noise we never used the fact that our basis vectors were Fourier vectors I 2111 Quantization Suppose we have a CT real valued signal How do we store and manipulate it on a digital computer Sec 2 1 Introduction to Random Sequences Detection and Estimation 159 CT signa Quantized CT signal 7 O Quantized sampled signal 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 9 O 1 2 3 4 5 Figure 233 Uniform quantization with quantization interval A 2 9 7 5 3 1 T T 1 3 5 CT signal 7 O Sampled signal 9 0 1 2 3 4 5 Figure 232 A CT realValued signal and its DT Version First of all we must retain only a discrete actually a nite set of values because we cannot store an uncountable set of values Earlier we considered a number of possibilities for doing this The simplest one was to retain some samples of the signal More generally we could decompose the signal in a basis and keep the coefficients of this decomposition 00 Mt Z akgkt store ak s k7oo We saw that our ideal sampling model is a particular case of this general strategy where gk s are sinc functions However we are not done yet If we have a nite set of samples each of which can take on any real value we still would not be able to store our signal on a computer CHAPTER 2 RANDOM SIGNALS 9671 l I 201 QHQHI i pr CT continuous valued DT discrete valued Figure 234 Quantization system What we need to do now is to make sure that the number of distinct values that each sample can assume is also nite This is accomplished with quantization see Fig 233 In this gure each value between 1 and 1 is quantized to zero each value between 1 and 3 is quantized to 2 etc From now on we assume that sampling is done before quantization and therefore the input to the quantizer is a DT signal Mn as shown in Fig 234 The output of the quantizer is denoted by In general the quantized signal is different from the input We would like to make this difference small in some sense Error distortion 7 A uniform quantizer partitions the range of into several equal bins and then quantizes all values within each bin to the middle value This is illustrated in Fig 235 for seven bins of size A 101 4 3A 2A 7 5A 7 3A 7 A A T T T I I I I I I I I I I I I I I I I I I I I I I I I I I A 3A 5A 7 7A x1 E T T 8 T T 2 A max possible value of ac min possible value of acn 42 72A 41 73A Notataion L11 qN quantization levelsl 1112 1213 IN IN1gt corresponding quantization intervals 11 minzn could be fool IN1 maxzn Could be ool Figure 235 3bit uniform quantizer Sec 2 1 Introduction to Random Sequences Detection and Estimation xngt35 is very unlikely 0 04 xn z 0 is very like fXxltn xn Figure 236 Distribution of a Gaussian random variable 9671 101 Quantizer CT continuous valued DT discrete valued random sequence random sequence Figure 237 Quantization system with random sequences as input Is this a good strategy Perhaps if we do not know much about the distribution of the values of between min and maxzn But suppose we know are observations of a zero mean Gaussian random variable with variance 02 whose pdf is shown in Fig 236 Then it does not make sense for example to waste two separate quantization levels on 10000 and 10010 since we are unlikely to ever see either of these values The correct strategy in this situation is 0 use more bits to represent values near 0 0 use fewer bits for large values This should reduce the mean square error Max Quantizer We now suppose that the input to the quantizer is a sequence of random variables Xn each of which has pdf x see Fig 237 We assume that 0 x does not contain 6 s ofmgt0f0riooltmltoo 162 CHAPTER 2 RANDOM SIGNALS We would like to nd the quantization intervals m1z2 m2z3 zNmN1 and corresponding quantization levels ql qN which minimize the mean square error 00 minimize Emmi 7 Xn2 y 7 macaw 700 N Z lly 7 zgt2fltzgtdz k1 M N mk1 2 qkim2fxdx 25 k1 M We rst minimize Eq 25 with respect to qk s by setting to zero the partial derivative with respect to each qk aElOn Xn2l 8 m 12ltqiizgtfltzgtdz 0 k1qkfxdz k1 W mfmdm qi E mm Xltngt w fxdx k Therefore the k th quantization level is the conditional expectation of Xn given that it falls within the k th quantization interval Now minimize with respect to ms 0 Since by assumption x 7 O we have 1 foo and zN1 oo o For 2 g k g N E 301 Xn2l azk 7 0 8 mk gm 7 x2fxdz ltqi 7 Mom 0 Qkil 90k2f90k qk 90k2f90k 0 Qkil 7 61192 w i 9 HM 0 Sec 2 1 Introduction to Random Sequences Detection and Estimation 163 w 7 2 mk le we need to solve a nonlinear system of 2N 7 1 equations mk1 qk1 k12N 26 wk mkQk712qk7 k2N 27 Remarks 1 We can nd a closed form solution only for very simple f s In general we nd an approximate solution numerically via an iterative algorithm 0 Guess qk s c Find xk s from Eq 27 c Find a better guess for qk s from Eq 26 o Re calculate xk s from Eq 27 etc to The argument above is easily modi ed to accommodate x containing 6 functions and x 0 for some x s 3 If x is unavailable estimate it using eg a histogram Example 220 Let x be given as in Fig 238 02 015 01 fX 005 0 02468101214 X Figure 238 for Example 220 OIEUjm N m WgtZUOlt wozgtrw Harp 3539 M4me RH H P 82 H HP 53 efl Hamp H I H g B U MSm gs oa S a wma aw 3m 93 a sa wma 3 3 3mm Sec 2 2 Speech Processing 165 I 22 Speech Processing We will now address another very important application namely processing of speech signals This is a very rich area which has many interesting problems We will be applying some of the things we studied about systems frequency analysis and random processes to some of these problems Three main areas of interest in speech processing are 0 Speech synthesis 0 Speech recognition 0 Speech coding The goal of speech synthesis is to develop a machine that accepts a piece of text as input and converts it to speech which would be as intelligible and natural sounding as if spoken by a person enabling for example your computer to talk to you Speech recognition is important because you may want to talk to your computer The ultimate goal here is to produce a system which can recognize which human accuracy speech from any speaker of a given language One application is being able to dictate to a computer instead of typing Another common application is automated telephone answering systems which recognize vocal commands to determine the next action The goal of speech coding or compression is to reliably represent speech signals with as few bits as possible This is very important for storage and transmission When you store a lot of data you would like to conserve space as much as possible and when you transmit you want to use as few bits as you can to transmit as much information as you can Ef cient coding of speech turns out to be possible because speech is very redundant I 221 Voiced and Unvoiced Speech Voiced sounds eg a b are essentially due to vibrations of the vocal cords and are oscillatory Therefore over short periods of time they are well modeled by sums of sinusoids This makes short time Fourier transformito be discussed lateria useful tool for speech processing Unvoiced sounds such as s sh are more noise like as shown in Fig 239 For many speech applications it is important to distinguish between voiced and unvoiced speech There are two simple but effective methods for doing it o Short time power function Split the speech signal into blocks of 10 20 ms and calculate the power within each block 1 L 7 2 PM 7 Enilm Typically7 Pavv0iced gt Pavunv0iced CHAPTER 2 RANDOM SIGNALS Utterance of the word quoterasequot En 02 04 06 08 time seconds Voiced Speech Segment Unvoiced Speech Segment 1quot 1quot 10 10 8 8 6 6 4 4 2 2 o OWWWWWWWWWW 2 2 4 4 0315 032 0325 033 0335 034 0345 quot 0515 052 0525 053 0535 054 0545 time seconds time seconds Figure 239 Distinction between Voiced and unvoiced speech Sec 2 2 Speech Processing 167 Voiced Periodic pulse train 5 Vocal tract gt White noise 0 Impulse response 11t Unvoiced Figure 240 Human speech production system c Zero crossing rate the signal has a zero crossing at no means that mn0mn0 1 lt 0 Unvoiced signals oscillate much faster so they will have a much higher rate of zero crossings I 222 Source Filter Model of Speech Production Sound is variations in air pressure The creation of sound is the process of setting the air in rapid vibration Our model of speech production will have two major components 0 Excitation How air is set in motion Voiced sounds Periodic air pulses such as in Fig 241a pass through vibrating vocal chords Unvoiced sounds Force air through a constriction in vocal tract producing turbulence 0 Vocal tract Guides air This system is illustrated in Fig 240 lts upper part the production of voiced sounds is very much akin to playing a guitar Fig 240 you produce a sequence of impulsive excitations by plucking the strings and then the guitar converts it into music The strings are sort of like the vocal cords and the guitar s cavity plays the same role as the cavity of the vocal tract A periodic pulse train excitation is illustrated in Fig 241a The period T is called the pitch period and 1T is called the pitch frequency On average 168 CHAPTER 2 RANDOM SIGNALS a Periodic pulse train lXfl lCTFT96tl 10 Frequency response Figure 241 Time domain and frequency domain perspectives of Voiced sounds male T x 8ms pitch 125H2 female T x 4ms pitch z 250H2 Vocal tract 0 Different voiced sounds are produced by changing the shape of the vocal tract this system is time varying 0 However it is slowly varying As we saw in Fig 239 changes occur slowly compared to the pitch period In other words each sound is approximately periodic but different sounds are different periodic signals This implies that we can model the vocal tract as an LTl lter over short time intervals Moreover since the vocal tract is a cavity it resonates In other words when a wave propagates in a cavity there is a set of frequencies which get ampli ed They are called natural frequencies of the resonator and depend on the shape and size of the resonator Therefore the magnitude response of the vocal tract for one voiced sound phoneme can be modeled as in Fig 242 The waveform for this particular phoneme will then be the convolution of the driving periodic pulse train t with the impulse response vt as illustrated in Fig 243k and the magnitude of its spectrum lSf will be the product of Xf and the magnitude Sec 2 2 Speech Processing Figure 242 Magnitude response of the Vocal tract W vrn a Voice tract transfer function 5t t gtk Mt m t b Resulting sound wave Sf Formant frequencies c Magnitude response of the resulting sound wave Figure 243 The Vocal tract as an LTI lter response lVfl7 as illustrated in Fig 243c The maxima of lSfl are called the formant frequencies of the phoneme o Typically7 one formant per 1 kHz 0 Locations are dictated by the poles of the transfer function 170 CHAPTER 2 RANDOM SIGNALS o Roll off is such that the rst 3 7 4 formants range up to 35 kHz are enough for reasonable reconstruction Thus sampling at 352 kHz 7 kHz is typically enough Depending on the application the sampling rate is usually 7 7 20 kHz Suppose we discretized speech and want to model the vocal tract as a digital lter The following gives a very rough idea of how to this If we knew the formant frequencies we could use what we learned about designing frequency selective lters 17212 Re 0 W1 a A pole near the unit circle 10 Magnitude response Figure 244 Poles near the unit Circle correspond to large Values of Hejw Poles of near the unit circle correspond to large values of H 57 Fig 244 So we can design an all pole lter with poles which are close to the unit circle cor responding to formant frequencies The larger the magnitude response at the formant frequency the closer the corresponding poles to the unit circle Example 221 A phoneme whose pitch is 100 Hz is sampled at 6 kHz It has two formants a weak one at 500 Hz and a stronger one at 2 kHz Find D the DT pitch period Sketch the approximate pole locations of Solution DT frequency w 27139 corresponds to 6 kHz Therefore 100 Hz corresponds to 100 33 76 a D 60 500 Hz corresponds to 500 g 2000 H2 corresponds to 623 2000 Sec 2 2 Speech Processing 171 lH 6W Rez I I I 39 l I 2 w 5 s a Complex plot of Example 221 b Magnitude response Figure 245 Poles near the unit Circle correspond to large Values of Hej Remarks 0 A pair of complex conjugate poles for each formant to make the frequency response real 0 The ones at i2 are closer to the unit circle since the corresponding peak of lH ejw is larger

### 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 made $350 in just two days after posting my first study guide."

#### "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!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.