Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Lecture 19: Autocorrelation

Mark Hasegawa-Johnson
All content CC-SA 4.0 unless otherwise specified.

ECE 401: Signal and Image Analysis, Fall 2020

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

1 Review: Power Spectrum

2 Autocorrelation

3 Autocorrelation of Filtered Noise

4 Power Spectrum of Filtered Noise

5 Parseval’s Theorem

6 Example

7 Summary
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Outline

1 Review: Power Spectrum

2 Autocorrelation

3 Autocorrelation of Filtered Noise

4 Power Spectrum of Filtered Noise

5 Parseval’s Theorem

6 Example

7 Summary
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Review: Energy Spectrum and Parseval’s Theorem

The energy spectrum of a random noise signal has the DTFT

form |X (ω)|2 , or the DFT form |X [k]|2 .
The easiest form of Parseval’s theorem to memorize is the
DTFT energy spectrum form:
∞ Z π
X
2 1
x [n] = |X (ω)|2 dω
n=−∞
2π −π

The DFT energy spectrum form is similar, but over a finite

duration:
N−1 N−1
X 1 X
x 2 [n] = |X [k]|2
N
n=0 k=0
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Review: Power Spectrum and Parseval’s Theorem

Energy of an infinite-length signal might be infinite. Wiener

defined the power spectrum in order to solve that problem:
1
Rxx (ω) = lim |X (ω)|2
N→∞ N
where X (ω) is computed from a window of length N samples. The
DTFT power spectrum form of Parseval’s theorem is
(N−1)/2 Z π
1 X
2 1
lim x [n] = Rxx (ω)dω
N→∞ N 2π −π
n=−(N−1)/2
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

White Noise
White noise is a type of noise whose samples are uncorrelated
(E [x[n]x[m]] = E [x[n]]E [x[m]], unless n = m). If it is also
zero mean and unit variance, then
(
1 n=m
E [x[n]x[m]] =
0 n 6= m
The Fourier transform of any zero-mean random signal is,
itself, a zero-mean random variable:
E [X (ω)] = 0
The power spectrum is also a random variable, but its
expected value is not zero. The expected power spectrum of
white noise is flat, like white light:
 
1 2
E [Rxx (ω)] = E |X (ω)| = 1
N
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: DTFT and Power Spectrum of White Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Expected DTFT and Power Spectrum of White

Noise
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Colored Noise

Most colored noise signals are well modeled as filtered white

noise, i.e., y [n] = h[n] ∗ x[n]. The filtering means that the
samples of y [n] are correlated with one another.
If x[n] is zero-mean, then so is y [n], and so is Y (ω):

E [Y (ω)] = 0

The expected power spectrum is |H(ω)|2 :

 
1
E [Ryy (ω)] = E |Y (ω)| = |H(ω)|2
2
N
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Filtered Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Outline

1 Review: Power Spectrum

2 Autocorrelation

3 Autocorrelation of Filtered Noise

4 Power Spectrum of Filtered Noise

5 Parseval’s Theorem

6 Example

7 Summary
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Finite-Duration Power Spectrum

In practice, we will very often compute the power spectrum from a

finite-length window:
1 1
Rxx (ω) = |X (ω)|2 , Rxx [k] = |X [k]|2
N N
where X (ω) is computed from a window of length N samples. The
DTFT power spectrum form of Parseval’s theorem is then
N−1 Z π N
1 X 2 1 1 X
x [n] = Rxx (ω)dω = Rxx [k]
N 2π −π N
n=0 k=0
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Inverse DTFT of the Power Spectrum

Since the power spectrum of noise is MUCH more useful than the
expected Fourier transform, let’s see what the inverse Fourier
transform of the power spectrum is. Let’s call Rxx (ω) the power
spectrum, and rxx [n] its inverse DTFT.

1 1
Rxx (ω) = |X (ω)|2 = X (ω)X ∗ (ω)
N N
where X ∗ (ω) means complex conjugate. Since multiplying the
DTFT means convolution in the time domain, we know that
1
rxx [n] = x[n] ∗ z[n]
N
where z[n] is the inverse transform of X ∗ (ω) (we haven’t figured
out what that is, yet).
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Inverse DTFT of the Power Spectrum

So what’s the inverse DFT of X ∗ (ω)? If we assume that x[n] is

real, we get that
∞
!∗
X
X ∗ (ω) = x[n]e −jωn
n=−∞
∞
X
= x[n]e jωn
n=−∞
X∞
= x[−m]e −jωm
m=−∞

So if x[n] is real, then the inverse DTFT of X ∗ (ω) is x[−n]!

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Autocorrelation

The power spectrum, of an N-sample finite-length signal, is

1
Rxx (ω) = |X (ω)|2
N
Its inverse Fourier transform is the autocorrelation,
∞
1 1 X
rxx [n] = x[n] ∗ x[−n] = x[m]x[m − n]
N N m=−∞

This relationship, rxx [n] ↔ Rxx (ω), is called Wiener’s theorem,

named after Norbert Wiener, the inventor of cybernetics.
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Autocorrelation of White Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

A warning about python

Notice, on the last slide, I defined autocorrelation as

∞
1 1 X
rxx [n] = x[n] ∗ x[−n] = x[m]x[m − n]
N N m=−∞

Python defines an “energy version” of autocorrelation, instead of

the “power version” shown above, i.e., [Link] computes:
∞
X
rpython [n] = x[m]x[m − n]
m=−∞

The difference is just a constant factor (N), so it usually isn’t

important. But sometimes you’ll need to be aware of it.
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Autocorrelation is also a random variable!

Notice that, just as the power spectrum is a random variable,

the autocorrelation is also a random variable.
The autocorrelation is the average of N consecutive products,
thus
" N−1 #
1 X
E [rxx [n]] = E x[m]x[m − n] = E [x[m]x[m − n]]
N
m=0

The expected autocorrelation is related to the covariance and

the mean:

E [rxx [n]] = Cov (x[m], x[m − n]) + E [x[m]] E [x[m − n]]

If x[n] is zero-mean, that means

E [r [n]] = Cov (x[m], x[m − n])

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Autocorrelation of white noise

If x[n] is zero-mean white noise, with a variance of σ 2 , then

(
σ2 n = 0
E [rxx [n]] = E [x[m]x[m − n]] =
0 otherwise

We can write
E [r [n]] = σ 2 δ[n]
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Outline

1 Review: Power Spectrum

2 Autocorrelation

3 Autocorrelation of Filtered Noise

4 Power Spectrum of Filtered Noise

5 Parseval’s Theorem

6 Example

7 Summary
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Filtered Noise

What happens when we filter noise? Suppose that x[n] is

zero-mean white noise, and

y [n] = h[n] ∗ x[n]

What is y [n]?
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Filtering of White Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Filtered Noise

∞
X
y [n] = h[n] ∗ x[n] = h[m]x[n − m]
m=−∞

y [n] is the sum of zero-mean random variables, so it’s also

zero-mean.
y [n] = h[0]x[n] + other stuff, and
y [n + 1] = h[1]x[n] + other stuff. So obviously, y [n] and
y [n + 1] are not uncorrelated. So y [n] is not white noise.
What kind of noise is it?
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

The variance of y [n]

First, let’s find its variance. Since x[n] and x[n + 1] are
uncorrelated, we can write
∞
X
σy2 = h2 [m]Var(x[n − m])
m=−∞
∞
X
= σx2 h2 [m]
m=−∞
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

The autocorrelation of y [n]

Second, let’s find its autocorrelation. Let’s define

rxx [n] = N1 x[n] ∗ x[−n]. Then

1
ryy [n] = y [n] ∗ y [−n]
N
1
= (x[n] ∗ h[n]) ∗ (x[−n] ∗ h[−n])
N
1
= x[n] ∗ x[−n] ∗ h[n] ∗ h[−n]
N
= rxx [n] ∗ h[n] ∗ h[−n]
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Autocorrelation of Colored Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Expected autocorrelation of y [n]

ryy [n] = rxx [n] ∗ h[n] ∗ h[−n]

Expectation is linear, and convolution is linear, so

E [ryy [n]] = E [rxx [n]] ∗ h[n] ∗ h[−n]

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Expected autocorrelation of y [n]

x[n] is zero-mean white noise if and only if its autocorrelation is a

delta function:
E [rxx [n]] = σx2 δ[n]
If y [n] = h[n] ∗ x[n], and x[n] is zero-mean white noise, then

E [ryy [n]] = σx2 (h[n] ∗ h[−n])

In other words, x[n] contributes only its energy (σx2 ). h[n]

contributes the correlation between neighboring samples.
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Expected Autocorrelation of Colored Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example

Here’s an example. The white noise signal on the top (x[n]) is

convolved with the bandpass filter in the middle (h[n]) to produce
the green-noise signal on the bottom (y [n]). Notice that y [n] is
random, but correlated.
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example

Here’s another example. The white noise signal on the left (x[n])
is convolved with an ideal lowpass filter, with a cutoff at π/2, to
create the pink-noise signal on the right (y [n]). Notice that y [n] is
random, but correlated.
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example
Here’s a third example. The white noise signal on the left (x[n]) is
convolved with an ideal highpass filter, with a cutoff at π/2, to
create the blue-noise signal on the right (y [n]). Here, it’s a lot less
obvious that the samples of y [n] are correlated with one another,
but they are: in fact, they are negatively correlated. If y [n] > 0,
then y [n + 1] < 0 with a probability greater than 50%.
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Outline

1 Review: Power Spectrum

2 Autocorrelation

3 Autocorrelation of Filtered Noise

4 Power Spectrum of Filtered Noise

5 Parseval’s Theorem

6 Example

7 Summary
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Power Spectrum of Filtered Noise

So we have ryy [n] = rxx [n] ∗ h[n] ∗ h[−n]. What about the power
spectrum?

Ryy (ω) = F {ryy [n]}

= F {rxx [n] ∗ h[n] ∗ h[−n]}
= Rxx (ω)|H(ω)|2
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example

Here’s an example. The white noise signal on the top (|X [k]|2 ) is
multiplied by the bandpass filter in the middle (|H[k]|2 ) to produce
the green-noise signal on the bottom (|Y [k]|2 = |X [k]|2 |H[k]|2 ).
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Units Conversion

The DTFT version of Parseval’s theorem, assuming a finite window

of length N samples, is
Z π
1 X 2 1
x [n] = Rxx (ω)dω
N n 2π −π

Let’s consider converting units to Hertz. Remember that ω = 2πfFs ,

2π
where Fs is the sampling frequency, so dω = Fs df , and we get that
Z Fs /2  
1 X 2 1 2πf
x [n] = Rxx df
N n Fs −Fs /2 Fs
 
2πf
So we can use Rxx Fs as if it were a power spectrum in
continuous time, at least for − F2s < f < Fs
2 .
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Power Spectrum of Colored Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Expected Power Spectrum of Colored Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Outline

1 Review: Power Spectrum

2 Autocorrelation

3 Autocorrelation of Filtered Noise

4 Power Spectrum of Filtered Noise

5 Parseval’s Theorem

6 Example

7 Summary
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Parseval’s Theorem

Now we have everything we need to prove Parseval’s theorem.

Let’s prove the DTFT power form of the theorem, for a
finite-length signal:
N−1 Z π
1 X 2 1
x [n] = Rxx (ω)dω
N 2π −π
n=0

where
1
Rxx (ω) = |X (ω)|2
N
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Parseval’s Theorem

N−1 Z π
1 X 2 1
x [n] = Rxx (ω)dω
N 2π −π
n=0

Notice that the left-hand side is the autocorrelation, with a lag of

0:
N−1
1 X
rxx [m] = x[n]x[n − m]
N
n=0

So Parseval’s theorem is just saying that

Z π
1
rxx [0] = Rxx (ω)dω
2π −π
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Wiener’s Theorem

Wiener’s theorem says that the power spectrum is the Fourier

transform of the autocorrelation:
Z π
1
rxx [n] = Rxx (ω)e jωn dω
2π −π

But notice what happens if we plug in n = 0:

Z π
1
rxx [0] = Rxx (ω)dω
2π −π

Q.E.D.
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Outline

1 Review: Power Spectrum

2 Autocorrelation

3 Autocorrelation of Filtered Noise

4 Power Spectrum of Filtered Noise

5 Parseval’s Theorem

6 Example

7 Summary
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Autocorrelation of White Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Power Spectrum of White Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Expected Power Spectrum of White Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Filtering of White Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Power Spectra of White and Colored Noises

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Autocorrelation of Colored Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Power Spectrum of Colored Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Example: Expected Power Spectrum of Colored Noise

Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Outline

1 Review: Power Spectrum

2 Autocorrelation

3 Autocorrelation of Filtered Noise

4 Power Spectrum of Filtered Noise

5 Parseval’s Theorem

6 Example

7 Summary
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Wiener’s Theorem and Parseval’s Theorem

Wiener’s theorem says that the power spectrum is the DTFT

of autocorrelation:
Z π
1
rxx [n] = Rxx (ω)e jωn dω
2π −π

Parseval’s theorem says that average power in the time

domain is the same as average power in the frequeny domain:
Z π
1
rxx [0] = Rxx (ω)dω
2π −π
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

Filtered Noise

If y [n] = h[n] ∗ x[n], x[n] is any noise signal, then

ryy [n] = rxx [n] ∗ h[n] ∗ h[−n]

Ryy (ω) = Rxx (ω)|H(ω)|2
Review Autocorrelation Autocorrelation Spectrum Parseval Example Summary

White Noise and Colored Noise

If x[n] is zero-mean unit variance white noise, and

y [n] = h[n] ∗ x[n], then

E [rxx [n]] = δ[n]

E [Rxx (ω)] = 1
E [ryy [n]] = h[n] ∗ h[−n]
E [Ryy (ω)] = |H(ω)|2