Spectrum Estimation i226n

Spectrum Estimation Dr. Hassanpour Payam Masoumi Mariam Zabihi Advanced Digital Signal Processing Seminar Department of Electronic Engineering Noushirvani University 1

Course Outlines •Introduction Fourier Series and Transform Time/Frequency Resolutions Autocorrelation & spectrum estimation •Non-parametric Methods Periodogram Modified Periodogram Bartlett’s Method Welch’s Method Blackman-Tukey Method •Parametric Methods

2

Fourier Series and Transform Im

e

sin( k0t )

jk0t

cos(k0t )

Re

t

Fourier basis functions: real and imaginar parts of a complex sinusoid vector representation of a complex exponential. 3

Fourier Series: x(t ) 



 ck e

jk0 t

,

k  

1 ck  T0



T0 2

T0 2

x(t )e

 jk0t

dt

k=…,-1,0,1,…

x(t )

c(k ) T0 n

T0  Ton  Toff

T0 ff

t

1 T0

k

4

Fourier Transform: 

x(t )   X ( f )e

j 2ft



df

x(t )



,

X ( f )   x(t )e  j 2ft dt 

X(f )

T0 ff  t

k

5

Discrete Fourier Transform (DFT) x(0)

X ( 0)

DFT

x(1)

N 1

X (1)

X ( k )   x ( m )e

j

2km N

m 0

x( N  1)

X ( N  1)

N 1

x ( m )   X ( k )e

j

2km N

,

k  ....,1,0,1,....

m 0

6

Autocorrelation & Spectrum estimation Autocorrelation:

N 1 { x(n  k ) x * (n)}  rx (k )  lim N  2 N  1 n   N

Power spectrum : Px (e

 jk

)



 jk r ( k ) e x

k  

Spectrum estimation is a problem that involves j t P ( e )from finite number of noisy estimating x measurements of x(n). 7

Nonparametric methods •Peroidogram •Modified periodogram •Bartlett method •Welch method •Blackman-Tukey method

8

The periodogram Estimated autocorrelation:

1 ˆrx (k )  N

N 1 k

 x ( n  k ) x * ( n) n 0

Estimated power spectrum or periodogram:  jk ˆ Pper (e ) 



 jk ˆ  rx (k )e

k  

9

The periodogram cont. x(n)

x N (n)  wR (n) x(n) 1  1  rˆx (k)   x N (n  k)x N (n)  x N (k)  x  N ( k) N n  N

1 1 j j  j j 2 ˆ Pper (e )  X N (e ) X N (e )  | X N (e ) | N N 10

The periodogram of white noise

x(n) x N (n)

DFT

: white noise with a variance  2 , length N=32

X N (k )

1 | . |2 N

Pˆper (e j 2k

N

)

1 | X N ( k ) |2 N

11

The periodogram of white noise cont.

The estimated autocorrelation sequence

White noise power spectrum

12

v

Periodogram of sinusoid in noise x(n)  A sin( n0   )  v(n)

1 2 A 2

j

Px (e )   v

2

0

2

1 2  A  (  0 ) 2 13



Periodogram of sinusoid in noise cont. win(1) win( 2)

y1 (n)

y 2 ( n)

1 | . |2 N 1 | . |2 N

z1 (n) z 2 ( n)

ˆP (e j1 )  z ( N  1) X 1 PˆX (e j2 )  z 2 ( N  1)

x(n)

win(L)

y L (n)

1 | . |2 N

z L (n)

ˆP (e jL )  z ( N  1) X L 14

Periodogram Bias rˆx (k )

E{}

1 N



E{Pˆper (e j )}   rx (k ) wB (k )e _ jk 

1 E{Pˆper (e j )}  Px (e j ) WB (e j ) 2

N k rx (k )  rx (k )  N n 0

N 1 k

 N | k | | k | 0  w B (k)   N  0 o.w

lim E{Pˆper (e j )}  Px (e j )

N 

Thus, the bias is deference between estimated and actual Power spectrum. 15

Periodogram of sinusoid in noise cont. x(n)  A sin( n0   )  v(n)

1 2 A 4 j 2 1 2 ˆ E{Pper (e )}   v  A [WB (e j ( 0 ) )  WB (e j ( 0 ) )] 4

2  k  0 

2 k N

0

16



Example: x(n)  1sin(0.4n  )  v(n)

N  128

N  512

17

Periodogram Resolution x(n)  A1 sin(n1  1 )  A1 sin( n2   2 )  v(n) j

Px (e )   v

2

1 2 1 2  A1  (  1 )  A2  (  2 ) 2 2

1 2 j 2 ˆ E{Pper (e )}   v  A1 [WB (e j ( 1 ) )  WB (e j ( 1 ) )] 4 1 2  A2 [WB (e j ( 2 ) )  WB (e j ( 2 ) )] 4 Set  equal to the width of main lobe of the spectral window at it’s half power or 6dB point.

2 j ˆ Res[ Pper (e )]  0.89 N

18

Example:

x(n)  1sin(0.4n  1 )  1sin(0.45n  2 )  v(n)

N  128

N  512

19

Properties of the periodogram 1 j ˆ Pper (e )  N

Bias:

n 1

 jn x ( n ) w ( n ) e  R

2

n 0

1 E{Pˆper (e j )}  Px (e j ) WB (e j ) 2

Resolution: Variance:

2 Res[ Pˆper (e j )]    0.89 N

Var {Pˆper (e j )}  Px2 (e j ) 20

Modified Periodogram 1 1 Pˆper (e j )  | X N (e j ) |2  N N

2



 x ( n) w

R

n  

(n)e  jn

Would there be any benefit in replacing the rectangular window with other windows? (for example triangular window)

1 j j j 2 ˆ Pper (e )  Px (e ) * WR (e ) , 2N 1 PˆM (e j )  NU 1 U N

N 1

2

sin( N 2)  j ( N 1) 2 WR (e )  e sin( 2) j



2

 x ( n) w

 jn ( n ) e R

n  

1 w ( n )   2N n 0



  W (e 

j

2

) d

21

Example:

x(n)  0.1sin(0.2n  1 )  1sin(0.3n  2 )  v(n)

N=128 Rectangular Window

N=128 Hamming Window

22

Properties of the M-periodogram 1 PˆM (e j ) NU



 jn x ( n ) w ( n ) e  R

n  

1 U N

Bias:

N 1

 w(n)

Variance:

2

n 0

E{PˆM (e j )} 

Resolution:

2

1 j j 2 Px (e )  W (e ) 2NU

window dependent Var {PˆM (e j )}  Px2 (e j ) 23

Bartlett’s method (periodogram averaging) 1 i j ˆ Pper (e )  L

L Points

2

L 1

 jn x ( n ) e ; i  1 , 2 , ..., k  i n 0

L Points

L Points

.... x1 (n)

x2 ( n )

xk (n)

24

Properties of Bartlett’s method 1 j ˆ PB (e )  N

Bias:

 jn x ( n  iL ) e 

2

i 0 n 0

1 E{PˆB (e j )}  Px (e j )  WB (e j ) 2

Resolution: Variance:

k 1 L 1

2 Res[ PˆB (e j )]  0.89k N

1 2 j j ˆ Var {Pper (e )}  Px (e ) k 25

Example:x(n)  1sin(0.25n  1 )  3sin(0.45n  2 )  v(n)

N  512 k 1

N  512 k 4

N  512 k  16 26

Example:x(n)  1sin(0.25n  1 )  3sin(0.45n  2 )  v(n)

N  128 k 4

N  512 k 4

N  1024 k 4 27

Welch’s method (M-periodogram averaging) xi (n)  x(n  iD )

;

n  0 ,1,....., L  1

Overlap = L-D

.... 28

Properties of Welch’s method PˆW (e j ) 

1 KLU

k 1 L 1

  x(n  iD)e

k 1 1 PˆW (e )   PˆM( i ) (e j ) L i 0

E{PˆB (e j )} 

Resolution

 jn

i 0 n 0

j

Bias

2

,

1 L 1 2 U   w(n) L n 0

1 j j 2 Px (e )  W (e ) 2LU

Window dependent Variance

9 L 2 j j ˆ Var {Pper (e )}  Px (e ) 16 N

with 50% overlap 29

Example:

x(n)  1sin(0.2  1 )  3 sin(0.25   2 )  v(n)

N  512 k 4

N  512 , L  128

30 overlap  50% , hamming

Resolution:x(n)  1sin(0.2n  1 )  3sin(0.25n  2 )  v(n)

N  512 , L  64 overlap  50% , hamming

N  512 , L  128 overlap  50% , hamming

N  512 , L  256 overlap  50% , hamming

31

windowing:x(n)  1sin(0.2n  1 )  3sin(0.25n  2 )  v(n)

N  512 , L  128 overlap  50% , Rectangular

N  512 , L  128 overlap  50% , Bartlett 32

windowing:x(n)  1sin(0.2n  1 )  3sin(0.25n  2 )  v(n)

N  512 , L  128 overlap  50% , Hanning

N  512 , L  128 overlap  50% , Hamming

N  512 , L  128

33

overlap  50% , Blackman

Blackman-Tukey’s method (Periodogram smoothing) •Note: Bartlett & Welch are design to reduce the variance if the priodogram by averaging and modified it. •Periodogram is computed by taking the Fourier transform of a consistent estimate of the auto correlation sequence. •For any finite data record of length N, the variance of rˆ (k ) will be large x for values of k that are close to N. for example:

rˆx ( N  1) 

1 x( N  1) x(0) N

at lag k  n  1

•In Bartlett & Welch, the variance is decreased by reducing the variance of autocorrelation estimate by averaging.

34

Blackman-Tukey’s method cont. •In the Blackman-Tukey method, the variance is decreased by applying a window to rˆ ( k ) in order to decrease the contribution of the unreliable x estimates to the periodogram. Specifically, the Blackman-Tukey spectrum estimation is:

PˆBT (e )  j

M

 jk ˆ r ( k ) w ( k ) e x

k  M

•For example, if w(k) is a rectangular window extending from –M to M with M
35

Properties of B-T’s method PˆBT (e j ) 

Bias

M

 jk ˆ r ( k ) w ( k ) e x

k  M

1 j ˆ E{PBT (e )}  Px (e j ) W (e j ) 2

Resolution

Window dependent

1 ˆ Variance Var {PBT (e )}  P (e ) N j

2 x

j

M

2 w  (k ) M

36

windowing: x(n)  3 sin(0.2  1 )  1sin(0.25   2 )  v(n)

N  512 , M  128 Rectangular

N  512 , M  128 Hanning

N  512 , M  128 Bartlett

N  512 , M  128 Blackman

37

Performance comparisons •We can summarized the performance of each technique in of two criteria.

(I) Variability (which is a normalized variance)

Var {Pˆx (e j )}  2 E {Pˆx (e j )} (II) Figure of merit

   •That is approximately the same for all of the nonparametric methods

38

Summery variability  Periodogram Bartlett Welch Blackman Tukey

1 1 k 91 8k 2M 3 N

Resolution  2 0.89 N 2 0.89k N 2 1.28 L 2 0.64 M

Figure of merit  2 0.89 N 2 0.89 N 2 0.72 N 2 0.43 N

***50% overlap and the Bartlett window***

39