2.161: Lecture 22 Notes

Massachusetts Institute of Technology Department of Mechanical Engineering 2.161 Signal Processing - Continuous and Discrete Fall Term 2008 Lecture 221 Reading: • Proakis and Manolakis: Secs. 12,1 – 12.2 • Oppenheim, Schafer, and Buck: • Stearns and Hush: Ch. 13 1 The Correlation Functions (continued) In Lecture 21 we introduced the auto-correlation and cross-correlation functions as measures of self- and cross-similarity as a function of delay τ . We continue the discussion here. 1.1 The Autocorrelation Function There are three basic definitions (a) For an infinite duration waveform: 1 φf f (τ ) = lim T →∞ T � T /2 f (t)f (t + τ ) dt −T /2 which may be considered as a “power” based definition. (b) For an finite duration waveform: If the waveform exists only in the interval t1 ≤ t ≤ t2 � t2 ρf f (τ ) = f (t)f (t + τ ) dt t1 which may be considered as a “energy” based definition. (c) For a periodic waveform: If f (t) is periodic with period T � 1 t0 +T φf f (τ ) = f (t)f (t + τ ) dt T t0 for an arbitrary t0 , which again may be considered as a “power” based definition. 1 c D.Rowell 2008 copyright � 22–1 Example 1 Find the autocorrelation function of the square pulse of amplitude a and duration T as shown below. f(t) a 0 t T The wave form has a finite duration, and the autocorrelation function is � T ρf f (τ ) = f (t)f (t + τ ) dt 0 The autocorrelation function is developed graphically below f(t) a 0 t T f(t+ t ) a -t 0 r a t T -t ff (t ) 2 r 0 -T � (t ) = a T T −τ ρf f (τ ) = ff 2 (T -t ) t a2 dt 0 = a2 (T − |τ |) = 0 22–2 −T ≤τ ≤T otherwise. Example 2 Find the autocorrelation function of the sinusoid f (t) = sin(Ωt + φ). Since f (t) is periodic, the autocorrelation function is defined by the average over one period � 1 t0 +T φf f (τ ) = f (t)f (t + τ ) dt. T t0 and with t0 = 0 � Ω 2π/Ω φf f (τ ) = sin(Ωt + φ) sin(Ω(t + τ ) + φ) dt 2π 0 1 = cos(Ωt) 2 and we see that φf f (τ ) is periodic with period 2π/Ω and is independent of the phase φ. 1.1.1 Properties of the Auto-correlation Function (1) The autocorrelation functions φf f (τ ) and ρf f (τ ) are even functions, that is φf f (−τ ) = φf f (τ ), and ρf f (−τ ) = ρf f (τ ). (2) A maximum value of ρf f (τ ) (or φf f (τ ) occurs at delay τ = 0, |ρf f (τ )| ≤ ρf f (0), and we note that and � |φf f (τ )| ≤ φf f (0) ∞ ρf f (0) = f 2 (d) dt −∞ is the “energy” of the waveform. Similarly 1 φf f (0) = lim T →∞ T � ∞ f 2 (t) dt −∞ is the mean “power” of f (t). (3) ρf f (τ ) contains no phase information, and is independent of the time origin. (4) If f (t) is periodic with period T , φf f (τ ) is also periodic with period T . (5) If (1) f (t) has zero mean (µ = 0), and (2) f (t) is non-periodic, lim ρf f (τ ) = 0. τ →∞ 22–3 1.1.2 The Fourier Transform of the Auto-Correlation Function Consider the transient case � ∞ ρf f (τ ) e−j Ωτ dτ � �−∞ ∞ �� ∞ = f (t)f (t + τ ) dt e−j Ωτ dτ −∞ � ∞ �−∞ ∞ j Ωt = f (t) e dt. f (ν) e−j Ων dν Rf f (j Ω) = −∞ −∞ = F (−j Ω)F (j Ω) = |F (j Ω)|2 or F ρf f (τ ) ←→ Rf f (j Ω) = |F (j Ω)|2 where Rf f (Ω) is known as the energy density spectrum of the transient waveform f (t). Similarly, the Fourier transform of the power-based autocorrelation function, φf f (τ ) � ∞ Φf f (j Ω) = F {φf f (τ )} = φf f (τ ) e−j Ωτ dτ −∞ � � ∞� � T /2 1 = lim f (t)f (t + τ ) dt e−j Ωτ dτ T →∞ T −∞ −T /2 is known as the power density spectrum of an infinite duration waveform. From the properties of the Fourier transform, because the auto-correlation function is a real, even function of τ , the energy/power density spectrum is a real, even function of Ω, and contains no phase information. 1.1.3 Parseval’s Theorem From the inverse Fourier transform � ∞ � ∞ 1 2 ρf f (0) = f (t) dt = Rf f (j Ω) dΩ 2π −∞ ∞ or � � ∞ 1 f (t) dt = |F (j Ω)|2 dΩ, 2π ∞ −∞ which equates the total waveform energy in the time and frequency domains, and which is known as Parseval’s theorem. Similarly, for infinite duration waveforms � T /2 � ∞ 1 2 lim f (t) dt = Φ(j Ω) dΩ T →∞ −T /2 2π −∞ ∞ 2 equates the signal power in the two domains. 22–4 1.1.4 Note on the relative “widths” of the Autocorrelation and Power/Energy Spectra As in the case of Fourier analysis of waveforms, there is a general reciprocal relationship between the width of a signals spectrum and the width of its autocorrelation function. • A narrow autocorrelation function generally implies a “broad” spectrum f ff (t ) F ff ( jW b r o a d a u to c o r r e la tio n ) n a rro w s p e c tru m t W • and a “broad” autocorrelation function generally implies a narrow-band waveform. f ff (t ) F ff ( jW ) b ro a d s p e c tru m n a r r o w a u to c o r r e la tio n t W In the limit, if φf f (τ ) = δ(τ ), then Φf f (j Ω) = 1, and the spectrum is defined to be “white”. f ff (t ) F im p u ls e a u to c o r r e la tio n 1 t 1.2 ff ( jW ) " w h ite " s p e c tr u m W The Cross-correlation Function The cross-correlation function is a measure of self-similarity between two waveforms f (t) and g(t). As in the case of the auto-correlation functions we need two definitions: � 1 T /2 φf g (τ ) = lim f (t)g(t + τ ) dτ T →∞ T −T /2 in the case of infinite duration waveforms, and � ∞ ρf g (τ ) = f (t)g(t + τ ) dτ −∞ for finite duration waveforms. 22–5 Example 3 Find the cross-correlation function between the following two functions f(t) T a 0 T g (t) T a t 1 0 T t 2 In this case g(t) is a delayed version of f (t). The cross-correlation is r a fg (t ) 2 0 T 2 - T 1 t where the peak occurs at τ = T2 − T1 (the delay between the two signals). 1.2.1 Properties of the Cross-Correlation Function (1) φf g (τ ) = φgf (−τ ), and the cross-correlation function is not necessarily an even function. (2) If φf g (τ ) = 0 for all τ , then f (t) and g(t) are said to be uncorrelated. (3) If g(t) = af (t − T ), where a is a constant, that is g(t) is a scaled and delayed version of f (t), then φf f (τ ) will have its maximum value at τ = T . Cross-correlation is often used in optimal estimation of delay, such as in echolocation (radar, sonar), and in GPS receivers. 22–6 Example 4 In an echolocation system, a transmitted waveform s(t) is reflected off an object at a distance R and is received a time T = 2R/c sec. later. The received signal r(t) = αs(t−T )+n(t) is attenuated by a factor α and is contaminated by additive noise n(t). R tr a n s m itte d w a v e fo rm s (t) r e c e iv e d w a v e fo rm r(t) + r e fle c tin g o b je c t v e lo c ity o f p r o p a g a tio n : c a s (t-T ) d e la y n (t) � T = 2cR ∞ φsr (τ ) = s(t)r(t + τ ) dt �∞∞ = s(t)(n(t + τ ) + αs(t − T + τ )) dt ∞ = φsn (τ ) + αφss (τ − T ) and if the transmitted waveform s(t) and the noise n(t) are uncorrelated, that is φsn (τ ) ≡ 0, then φsr (τ ) = αφss (τ − T ) that is, a scaled and shifted version of the auto-correlation function of the trans­ mitted waveform – which will have its peak value at τ = T , which may be used to form an estimator of the range R. 1.2.2 The Cross-Power/Energy Spectrum We define the cross-power/energy density spectra as the Fourier transforms of the crosscorrelation functions: � ∞ Rf g (j Ω) = ρf g (τ ) e−j Ωτ dτ �−∞ ∞ Φf g (j Ω) = φf g (τ ) e−j Ωτ dτ. −∞ Then � ∞ ρf g (τ ) e−j Ωτ dτ �−∞ ∞ � ∞ = f (t)g(t + τ ) e−j Ωτ dt dτ −∞ �−∞ � ∞ ∞ j Ωt = f (t) e dt g(ν) e−j Ων dν Rf g (j Ω) = −∞ −∞ 22–7 or Rf g (j Ω) = F (−j Ω)G(j Ω) Note that although Rf f (j Ω) is real and even (because ρf f (τ ) is real and even, this is not the case with the cross-power/energy spectra, Φf g (j Ω) and Rf g (j Ω), and they are in general complex. 2 Linear System Input/Output Relationships with Random In­ puts: Consider a linear system H(j Ω) with a random input f (t). The output will also be random f(t) y (t) H ( jW ) f ff ( t) f y y (t) Then Y (j Ω) = F (j Ω)H(j Ω), Y (j Ω)Y (−j Ω) = F (j Ω)H(j Ω)F (−j Ω)H(−j Ω) or Φyy (j Ω) = Φf f (j Ω) |H(j Ω)|2 . Also F (−j Ω)Y (j Ω) = F (−j Ω)F (j Ω)H(j Ω), or Φf y (j Ω) = Φf f (j Ω)H(j Ω). Taking the inverse Fourier transforms � � φyy (τ ) = φf f (τ ) ⊗ F −1 |H(j Ω)|2 φf y (τ ) = φf f (τ ) ⊗ h(τ ). 3 Discrete-Time Correlation Define the correlation functions in terms of summations, for example for an infinite length sequence φf g (n) = E {fm gm+n } = N � 1 fm gm+n , N →∞ 2N + 1 m=−N lim and for a finite length sequence ρf g (n) = N � m=−N 22–8 fm gm+n . The following properties are analogous to the properties of the continuous correlation func­ tions: (1) The auto-correlation functions φ( f f (n) and ρf f (n) are real, even functions. (2) The cross-correlation functions are not necessarily even functions, and φf g (n) = φgf (−n) (2) φf f (n) has its maximum value at n = 0, |φf f (n)| ≤ φf f (0) for all n. (3) If {fk } has no periodic component lim φf f (n) = µ2f . n→∞ (4) φf f (0) is the average power in an infinite sequence, and ρf f (n) is the total energy in a finite sequence. The discrete power/energy spectra are defined through the z-transform Φf f (z) = Z {φf f (n)} = ∞ � φf f (n)z −n n=−∞ and φf f (n) = Z −1 {Φf f (z)} � 1 = Φf f (z)z n−1 dz 2πj � π/T T = Φf f ( ej ΩT ) ej nΩT dΩ. 2π −π/T Note on the MATLAB function xcorr(): In MATLAB the function call phi = xcorr(f,g) computes the cross-correlation function, but reverses the definition of the subscript order from that presented here, that is it computes φf g (n) = N N 1 � 1 � fn+m gm = fn gn−m M −N M −N where M is a normalization constant specified by an optional argument. Care must therefore be taken in interpreting results computed through xcorr(). 22–9 3.1 Summary of z-Domain Correlation Relationships (The following table is based on Table 13.2 from Stearns and Hush) Property Formula Power spectrum of {fn } Φf f (z) = Cross-power Spectrum Autocorrelation Cross-correlation Waveform power Linear system properties ∞ � n=−∞ ∞ � φf f (n)z −n φf g (n)z −n = Φgf (z −1 ) n=−∞� 1 φf f (n) = Φf f (z)z n−1 dz 2πj � 1 φf g (n) = Φf g (z)z n−1 dz 2π j � � 2� 1 E fn = φf f (0) = Φf g (z)z −1 dz 2πj Y (z) = H(z)F (z) Φyy (z) = H(z)H(z −1 )Φf f (z) Φf y (z) = H(z)Φf f (z) Φf g (z) = 22–10