Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341:DISCRETE-TIME SIGNAL PROCESSING OpenCourse Ware 2006 Lecture 18 Periodogram Reading:Sections 10.6 and 10.7 in Oppenheim,Schafer Buck(OSB). We begin this lecture by introducing three common illusions in spectral analysis: THREE ILLUSIONS .If you can't see it,it's not there.(the picket fence effect) The more zero padding,the better the spectral resolution.(resolution vs.sampling, spectral smearing) For a random process,as the data record length-oo,the magnitude-squared of the DTFT converges to the power spectral density.(the periodogram) In the last lecture,we discussed the first and the second illusions.The picket fence effect re- sults from the spectral sampling imposed by the DFT and can be avoided using zero padding. However,zero padding does not improve the spectral resolution which depends on the shape and length of the window. In this lecture,we will see the third illusion which relates to spectral analysis of stochastic signals.For a deterministic signal,more data (i.e.longer window)results in better frequency resolution,but this does not hold for a stochastic signal. The power spectral density(PSD)of a random process is useful for the following purposes: 1.System Identification x(t) h(t) +y(t) Piy()=Pz()H(j)2 P4x(2)=Pxx(2)H(j2) From the PSDs of input and output,we can estimate the frequency response of the system. 1
Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341: Discrete-Time Signal Processing OpenCourseWare 2006 Lecture 18 Periodogram Reading: Sections 10.6 and 10.7 in Oppenheim, Schafer & Buck (OSB). We begin this lecture by introducing three common illusions in spectral analysis: THREE ILLUSIONS • If you can’t see it, it’s not there. (the picket fence effect) • The more zero padding, the better the spectral resolution. (resolution vs. sampling, spectral smearing) • For a random process, as the data record length → ∞, the magnitude-squared of the DTFT converges to the power spectral density. (the periodogram) In the last lecture, we discussed the first and the second illusions. The picket fence effect results from the spectral sampling imposed by the DFT and can be avoided using zero padding. However, zero padding does not improve the spectral resolution which depends on the shape and length of the window. In this lecture, we will see the third illusion which relates to spectral analysis of stochastic signals. For a deterministic signal, more data (i.e. longer window) results in better frequency resolution, but this does not hold for a stochastic signal. The power spectral density(PSD) of a random process is useful for the following purposes: 1. System Identification 2 - y(t) - Pyy(Ω) = Pxx(Ω) H(jΩ) x(t) h(t) | | Pyx(Ω) = Pxx(Ω)H(jΩ) From the PSDs of input and output, we can estimate the frequency response of the system. 1
2.Noise Removal Consider a signal:x(t)=s(t)+n(t),where s(t)is a deterministic signal,and n(t)is a stochastic noise process.In order to filter out the noise using a frequency-selective filter, we need to determine the PSD of the noise. The Periodogram Let xe(t)be a bandlimited stationary random process,then it can be sampled without aliasing. xc(t) xn] C/D T The power spectrum of xn]is proportional to that of ce(t): P)-P..( l<π Therefore,we can estimate Prere()from a reasonable estimate of P(w).The periodogram, defined as below,can be used as an estimate of the PSD of xIn]: o)e2ve那， where V(e)is the Fourier transform of the windowed sequence vln]=RL[n]x[n].The process of computing the periodogram of x[n]is illustrated in the figure below: wIn]=RLIn] xn- +⑧ vin DFT V [k] 12 IV[k]12 =IV(ej)2 L=2nk/L The PSD is the Fourier transform of the autocorrelation function of the signal if the signal can be treated as a stationary random process.Using the properties of Fourier transform,it can be shown that )=DTFT网*- L-m-1 ulnjuln m]h 2
2. Noise Removal Consider a signal: x(t) = s(t) + η(t), where s(t) is a deterministic signal, and η(t) is a stochastic noise process. In order to filter out the noise using a frequency-selective filter, we need to determine the PSD of the noise. The Periodogram Let xc(t) be a bandlimited stationary random process, then it can be sampled without aliasing. xc(t) - C/D -x[n] 6 T The power spectrum of x[n] is proportional to that of xc(t): 1 Pxx(ω) = Pxcxc (Ω) Ω=ω/T , |ω| < π T | Therefore, we can estimate Pxcxc (Ω) from a reasonable estimate of Pxx(ω). The periodogram, defined as below, can be used as an estimate of the PSD of x[n]: 1 I(ω) � L|V (ejω) 2 | , where V (ejω) is the Fourier transform of the windowed sequence v[n] = RL[n]x[n]. The process of computing the periodogram of x[n] is illustrated in the figure below: w[n] = RL[n] x[n] -�× ? v[n] - DFT V [k] - | · | 2 - |V [k]| 2 = |V (ejω)| 2 |ω=2πk/L The PSD is the Fourier transform of the autocorrelation function of the signal if the signal can be treated as a stationary random process. Using the properties of Fourier transform, it can be shown that 1 I(ω) = DT F T{v[n] ∗ v[−n] L } 1 L−|m|−1 = DT F T{ � v[n]v[n + m]}. L n=0 2
Therefore,the periodogram is in fact the Fourier transform of the autocorrelation of the win- dowed data sequence. 4 150 200 260 300350 400 00 100 15020025030030 400 (a)Periodogram of White Noise (b)Periodogram of Colored Noise Figure(a)above shows a white noise process and its periodogram using the 512-point DFT and linear interpolation.The PSD of the noise process is indicated as the flat line in the peri- odogram figure.Notice that the periodogram has many deviations from the actual PSD.Figure (b)shows a colored noise process,its periodogram,and PSD.Although the periodogram looks very different from the actual PSD,it is apparent that the process has significant content only in low frequency. It is clear from the figure above that the periodogram is not very good estimate of the PSD in this example.We have already learned in the last lecture that increasing the size of the DFT does not improve the frequency resolution.However,in this case,increasing the length of the window is not helpful either,as discussed in the following section. Properties of the Periodogram An estimator is unbiased if its expectation is equal to the quantity that is being estimated.A consistent estimator is an estimator that converges to the quantity being estimated as the data size grows.We can determine whether the periodogram is biased and whether it is consistent by computing its mean and variance.As developed in OSB Section 10.6.2, ())DFT 3
Therefore, the periodogram is in fact the Fourier transform of the autocorrelation of the windowed data sequence. (a) Periodogram of White Noise (b) Periodogram of Colored Noise Figure (a) above shows a white noise process and its periodogram using the 512-point DFT and linear interpolation. The PSD of the noise process is indicated as the flat line in the periodogram figure. Notice that the periodogram has many deviations from the actual PSD. Figure (b) shows a colored noise process, its periodogram, and PSD. Although the periodogram looks very different from the actual PSD, it is apparent that the process has significant content only in low frequency. It is clear from the figure above that the periodogram is not very good estimate of the PSD in this example. We have already learned in the last lecture that increasing the size of the DFT does not improve the frequency resolution. However, in this case, increasing the length of the window is not helpful either, as discussed in the following section. Properties of the Periodogram An estimator is unbiased if its expectation is equal to the quantity that is being estimated. A consistent estimator is an estimator that converges to the quantity being estimated as the data size grows. We can determine whether the periodogram is biased and whether it is consistent by computing its mean and variance. As developed in OSB Section 10.6.2, 1 ∞ Pxx(ω) ∗ DT F T{ � E{I(ω)} = RL[n]RL[n + m] L n= } −∞ 3
where P)isthe PSD of the signal.The termmisthe autocorrelation of the rectangular window,thus it has a shape of a triangle.Denoting the Fourier transform of the window as W(e),let B(w)=DTFT RL[n]RLIn m]}=W(ej)2 n=-00 then, E(I())=P(w)+B(w). This can be interpreted similarly as in the deterministic case:the desired quantity is smeared by the spectrum of the window (W(jw)2 in this case).Since Efl(w)}is not equal to Pw), we see that the periodogram is a biased estimate of the power spectrum. As L goes to infinity,W(e)approaches an impulse,and thus B(w)also approaches an impulse at the origin.In this case,EfI(w)Pr(w),so the periodogram is an asymptotically unbiased estimator. It has been shown that as the window length increases, var{I(w)}≈P2(w). Therefore,the variance does not approach zero as Loo,and the periodogram is not a con- sistent estimate of the power spectrum density. OSB Figure 10.20 shows the periodograms of a white-noise sequence with variance 1.The correct PSD for this process is a constant of 1.We can see that as the window length in- creases from L 16 in (a)to L 1024 in (d),the variation from the mean does not go to zero, and the periodogram with longer window does not give a better estimate of the power spectrum. Periodogram Averaging In order to reduce the fluctuations and obtain a smooth spectrum estimate,we can average multiple measurements of periodogram estimates. Let r[n]be an ergodic random signal,then the expectation can be calculated by time averaging. Assume that we want to estimate the mean defined as follows: Nim 2rinl Efxn]}=mz=lim -0 Consider using the following estimator: xn] 4
where Pxx(ω) is the PSD of the signal. The term �∞ RL[n]RL[n+m] is the autocorrelation n=−∞ of the rectangular window, thus it has a shape of a triangle. Denoting the Fourier transform of the window as W(ejω), let ∞ B(ω) = DTFT{ � RL[n]RL[n + m]} = |W(ejω) 2 | n=−∞ then, 1 E{I(ω)} = Pxx(ω) ∗ B(ω). L This can be interpreted similarly as in the deterministic case: the desired quantity is smeared by the spectrum of the window ( W(jω) 2 | | in this case). Since E{I(ω)} is not equal to Pxx(ω), we see that the periodogram is a biased estimate of the power spectrum. As L goes to infinity, W(ejω) approaches an impulse, and thus B(ω) also approaches an impulse at the origin. In this case, E{I(ω)} ≈ Pxx(ω), so the periodogram is an asymptotically unbiased estimator. It has been shown that as the window length increases, xx var{I(ω)} ≈ P (ω). 2 Therefore, the variance does not approach zero as L → ∞, and the periodogram is not a consistent estimate of the power spectrum density. OSB Figure 10.20 shows the periodograms of a white-noise sequence with variance 1. The correct PSD for this process is a constant of 1. We can see that as the window length increases from L = 16 in (a) to L = 1024 in (d), the variation from the mean does not go to zero, and the periodogram with longer window does not give a better estimate of the power spectrum. Periodogram Averaging In order to reduce the fluctuations and obtain a smooth spectrum estimate, we can average multiple measurements of periodogram estimates. Let x[n] be an ergodic random signal, then the expectation can be calculated by time averaging. Assume that we want to estimate the mean defined as follows: +∞ 1 E{x[n]} = mx = lim �x[n] N→∞ 2N −∞ Consider using the following estimator: 1 K mˆ x = �x[n] K 1 4
Then,m is an unbiased estimator since Efm=m.If we assume that all the observation of x[n]are independent,and denote the variance of x[n]as o2,then varfm=o2.Therefore, varfmh0 as K-oo,and m is a consistent estimator. Similarly,we can construct a consistent estimator of power spectrum utilizing an arbitrarily long data record.If we have multiple measurements of I(w),we can think of averaging them: K r=1 Then, E(I.(w)-E(LWw)-P.(w).B(w) and war{Iz())-var(Ir(w)-Pw) so as Koo,Ir(w)converges to Prt(w)*B(w). Now,consider a fixed data record of length Q.If there is no overlap,Q=KL,where L is the length of the window,and K is the number of measurements of I(w).We get more accurate estimate of I(w)if K is larger,but we also need a longer window in order to increase spectral resolution.So,there is a tradeoff between K and L as illustrated in OSB Section 10.6.5 and summarized in the following example. Example: Consider the sequence xin]Acos(won+0)+eln], where 0 is a random variable uniformly distributed between 0 and 2m,and eln]is a zero- mean white-noise sequence that has a constant power spectrum Pee(w)=o2 for all w.It can be shown that E.(o}=4A2L +o2 4 OSB Figure 10.23 shows average periodogram estimates for A =0.5,o2 =1,and with different values of L and K.Notice that as K increases(i.e.more sections are averaged),the periodogram becomes smoother because the variance of the estimate decreases.However, since the data length is fixed,the window length should become shorter to average more sections.As a result,the frequency resolution decreases because of the smearing effect,and in OSB Figure 10.23(d),the spectral peak due to the cosine is very broad and barely above the noise. 5
Then, mˆ x is an unbiased estimator since E{mˆ x} = mx. If we assume that all the observation of x[n] are independent, and denote the variance of x[n] as σ2, then var{ ˆ 1 σ2. Therefore, mx} → 0 as K → ∞, and ˆ x mx} = K x var{ ˆ mx is a consistent estimator. Similarly, we can construct a consistent estimator of power spectrum utilizing an arbitrarily long data record. If we have multiple measurements of I(ω), we can think of averaging them: ¯Ixx(ω) = 1 K � K Ir(ω) r=1 Then, E{¯Ixx(ω)} = E{Ir(ω)} = 1 L Pxx(ω) ∗ B(ω) and var{¯Ixx(ω)} = 1 K var{Ir(ω)} = 1 K P2 xx(ω), ¯ 1 so as K → ∞, Ixx(ω) converges to Pxx(ω) ∗ B(ω). L Now, consider a fixed data record of length Q. If there is no overlap, Q = KL, where L is the length of the window, and K is the number of measurements of I(ω). We get more accurate estimate of I(ω) if K is larger, but we also need a longer window in order to increase spectral resolution. So, there is a tradeoff between K and L as illustrated in OSB Section 10.6.5 and summarized in the following example. Example: Consider the sequence x[n] = A cos(ω0n + θ) + e[n], where θ is a random variable uniformly distributed between 0 and 2π, and e[n] is a zeromean white-noise sequence that has a constant power spectrum Pee(ω) = σ2 for all ω. It e can be shown that A2L E{I ¯ xx(ω)} = 4 + σ2. e OSB Figure 10.23 shows average periodogram estimates for A = 0.5, σe 2 = 1, and with different values of L and K. Notice that as K increases (i.e. more sections are averaged), the periodogram becomes smoother because the variance of the estimate decreases. However, since the data length is fixed, the window length should become shorter to average more sections. As a result, the frequency resolution decreases because of the smearing effect, and in OSB Figure 10.23(d), the spectral peak due to the cosine is very broad and barely above the noise. 5
In OSB Figure 10.23(b),we used overlapped sections when averaging periodograms.The vari- ance is reduced by almost a factor of 2 when the overlap is one-half the window length.Our last example illustrates periodogram averaging using a non-rectangular window and overlapping sections. Example: Consider the two sequences shown below:a noisy sequence and a "clean"sequence after filtering noise using an elliptic filter.If we apply a Fourier transform to the entire sequences using the FFT (covered in the next lecture),the resulting figures are hard to interpret because of fluctuations. FFT Q 6
10.23(b), we used overlapped sections when averaging periodograms. The variby almost a factor of 2 when the overlap is one-half the window length. Our illustrates periodogram averaging using a non-rectangular window and overlapping the two sequences shown below: a noisy sequence and a ”clean” sequence after noise using an elliptic filter. If we apply a Fourier transform to the entire sequences the FFT (covered in the next lecture), the resulting figures are hard to interpret of fluctuations. Example: Consider filtering using In OSB Figure ance is reduced last example because sections. 6
The figures below show averaged periodograms using 4096-and 1029-point Hamming win- dows,respectively.In both cases,neighboring segments are overlapped by one-half the window length.Notice that shorter window results in increased bias.but the estimate is smoother because more segments are averaged. 10 -0 -30 40 02 42 nnin 00 Window:4096 point,Hamming,Overlap:50% -0 Window:1024 point,Hamming,Overlap:50% 7
The figures below show averaged periodograms using 4096- and 1029-point Hamming windows, respectively. In both cases, neighboring segments are overlapped by one-half the window length. Notice that shorter window results in increased bias, but the estimate is smoother because more segments are averaged. Window: 4096 point, Hamming, Overlap: 50 % Window: 1024 point, Hamming, Overlap: 50 % 7
