离散傅氏变换快速计算

离散傅氏变换的计算 DFT的线性滤波计算DFTN 1 kn X ( k ) x( n )WN RN ( k ) n 0 1 N 1 kn x( n ) X ( k )WN RN ( n ) N k 0

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法– Chirp-z变换算法

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法X ( k ) x( n )WN knn 0 N 1

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法X ( k ) x( m )W N k ( n m )m 0 N 1 n N

WN kN x( m )WN kmm 0

N 1

x( n ) [ W N

kn

u( n )]

n N

x( m )WN k ( N m )m 0

N 1

x( n ) hk ( n ) n Nn N

x( m )WNm 0

N 1

k ( n m )

yk ( n ) n N

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法Z hk ( n ) W N kn u( n ) Hk( z )

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法

Yk ( z ) 1 X ( z ) 1 W N k z 1 k

Hk( z )

1 1 W N k z 1 ( 1 WN k 1

y ( n ) WN y k ( n ) x( n ) hk ( n ) k y k ( 1 ) 0 X ( k ) yk ( n ) n N y k ( n 1 ) x( n )

1 WN k z 1 z )( 1 W N k z 1 )

1 2 cos( 2 k N ) z 1 z 2 1 1 2 cos( 2 k N ) z 1 z 2

1 WN k z 1

( 1 WN k z 1 )

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法H k ( z ) ( 1 WN z Hk( z ) k 1

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法

)

1 1 2 cos( 2 k N ) z 1 z 2

Vk ( z ) 1 X ( z ) 1 2 cos( 2 k N ) z 1 z 2 2 k vk ( n 1 ) vk ( n 2 ) x( n ) vk ( n ) 2 cos N vk ( 1 ) vk ( 2 ) 0 Yk ( z ) 1 WN k z 1 Vk ( z ) y k ( N ) vk ( N ) W N k v k ( N 1 )

Yk ( z ) Yk ( z ) Vk ( z ) X ( z ) Vk ( z ) X ( z )

Vk ( z ) 1 X ( z ) 1 2 cos( 2 k N ) z 1 z 2 Yk ( z ) 1 W N k z 1 Vk ( z )

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法Hk( z ) H N k ( z ) 1 1 1 WN k z 1 ( 1 WN k z 1 )( 1 WN k z 1 ) 1 1 2 cos( 2 k N ) z 1 z 2 1 WN k z 1 1 WN k z 1

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法Vk ( z ) 1 X ( z ) 1 2 cos( ( 2 k N ) z 1 z 2 2 k vk ( n 1 ) vk ( n 2 ) x( n ) vk ( n ) 2 cos N vk ( 1 ) vk ( 2 ) 0 Yk ( z ) 1 WN k z 1 Vk ( z ) yk ( N ) vk ( N ) WN k vk ( N 1 )

( 1 WN k z 1 )

离散傅氏变换的计算 DFT的线性滤波计算– Goertzel算法– Chirp-z变换算法

离散傅氏变换

的计算 DFT的线性滤波计算– Chirp-z变换算法kn X ( k ) x( n )WN N 1 n 0

0 k N 1 k z W N

x( n )z nn

2 k N

Im Z平面

X ( z ) z W kN

2 N1

Re

离散傅氏变换的计算 DFT的线性滤波计算– Chirp-z变换算法X ( z k ) X ( z ) z zk k 0,1, , M 1

离散傅氏变换的计算 DFT的线性滤波计算– Chirp-z变换算法

z k A V k A0 e j 0 ( R0 e j 0 )kZ 2 Z1Z M 1

X ( z k ) X ( z ) z zk k 0,1, , M 1

z k A V k A0 e j 0 ( R0 e j 0 )kZ 2 Z1Z M 1

R0 1向原点盘旋 R0 1向外盘旋 R0 1圆弧

0

A0 1, R0 1 0Re

A0 Z 0

0 0, 0 2 NM N k z k WN

0

A0 Z 0

0Re

01.0

01.0

X ( zk ) X ( k )

离散傅氏变换的计算 DFT的线性滤波计算X ( zk ) N 1 n 0 N 1 n 0 N 1

离散傅氏变换的计算

x( n )zk n0

1 kn k 2 n 2 ( k n )2 2

DFT的线性滤波计算– Chirp-z变换算法X ( zk ) V V1 1 k 2 N 1 ( k n )2 2 g ( n )V 2 n 0

x( n )( A0e j ) nV kn x( n )( A01 k 2 n 2 ( k n )2 e j 0 ) nV 2 1 ( k n )2

k 0,1, , M 1

n 0 1 1 k 2 N 1 n2 V 2 [ x( n )( A0e j 0 ) nV 2 n 0 1 1 k 2 N 1 ( k n )2 V 2 g ( n )V 2 n 0

1 k 2 N 1 2 g ( n )h( k n 0

n)

]V 2

V

1 k2 2 g( k

) h( k )

离散傅氏变换的计算 DFT的线性滤波计算– Chirp-z变换算法X ( zn ) V X ( zn ) V1 n 2 N 1 2[ x( m )( m 0

离散傅氏变换的计算 DFT的线性滤波计算– Chirp-z变换算法

A0

1 m2 e j 0 ) m V 2

]V

1 ( n m )2 2

x( n )

g( n )V

n2 2

X ( zn )

1 n2 2 g ( n ) h( n ) 1 n2 e j 0 ) n V 2

n 0,1, , M 1 n 0,1, , N 1A nV2 n 2

g( n ) x( n )( A0 h( n ) Vn2 2

V

2 n 2

离散傅氏变换的计算 Chirp-z变换的推导f(t) fs(n)

离散傅氏变换的计算证明：设实信号f t cos( 0 t at 2 )其瞬时频率 ( t ) g(t)

h(t)

g1 (t)

d ( t ) 0 2at dt则 g1( t ) fs ( t ) h( t ) j( 0 a ) j[ 0( t ) a( t )] e d f ( )e2 2

s(t)

s(t)

h( t ) e j( 0t at s( t ) ej ( 0 t at 2 )

2

) j 2 0 t

g ( t ) F ( 2at )e

j 2at e j( 0t at ) d f ( )e

2

e j( 0t at )F( 2at ) g( t ) e j2 0t F( 2at )

2

离散傅氏变换的计算 DFT的线性滤波计算– Chirp-z变换算法x( n ) g( n )n2 V 2

离散傅氏变换的计算 DFT的线性滤波计算– Chirp-z变换算法X ( zn )

X ( zn ) V X ( zn ) V

1 n 2 N 1 2[ x( m

)(

m 0 1 n2 2 g ( n ) h( n )

A0 e j 0 ) m V

1 m2 2

1

]V 2

( n m )2

n 0,1, , M 1 n 0,1, , N 1

A nV

2 n 2

V

2 n 2

g( n ) x( n )( A0 h( n ) Vn2 2

1 n2 e j 0 ) n V 2

离散傅氏变换的计算 DFT的线性滤波计算– Chirp-z变换算法X ( zn ) V1 n2 2 g( n )

离散傅氏变换的计算 DFT的线性滤波计算– Chirp-z变换算法X ( zn ) V

L N M 1L h( n ) n 0,1, , M 1 n 0,1, , N 1

L N M 1) H ( k )] n 0,1, , M 11 n2 2

1 n2 2 IDFT[ G( k

g ( n ) x( n )( A0 V h( n ) 0 ( n L )2 2 Vn2 2

1 n2 e j 0 ) n V 2

g ( n ) x( n )( A0 e j 0 ) n V V h( n ) 0 ( n L )2 2 Vn2 2

n …… 此处隐藏：2654字，全部文档内容请下载后查看。喜欢就下载吧 ……