tceic.com
学霸学习网 这下你爽了
相关文章
当前位置:首页 >> 数学 >>

小波分析 快速傅里叶变换_图文

快速傅里叶变换

? 快速傅里叶变换(FFT)并不是一种新的变换,而是离散博 里叶变换(DFT)的一种快速算法。因此,为了很好地理解 和掌握快速傅里叶变换,必须对离散傅里叶变换有充分的 理解与掌握 。

? 由于DFT的计算量太大.即使采用计算机也很难对问题进 行实时处理,所以并没有得到真正的运用。直到1965年库 利(J. W. Coo1ey)和图基(J. W. Tukey)在《计算数学》上发 表了著名的“机器计算傅里叶级数的一种算法”的文 章.提出了DFT的一种快速算法.后来又有桑德(G. Sande) 和图基的快速算法相继出现,情况才发生了根本的改变。 经过人们对算法的改进,发展和完善了一套高速有效的运 算方法,使DFT的计算大大简化,运算时间—般可缩短一、 二个数量级,从而使DFT的运算在实际中真正得到了广泛 的加用。

1 直接计算DFT的问题及改进途径
对于N点有现长序列

x ( n)
N ?1 n ?0

nk X (k ) ? DFT ? x(n)? ? ? x(n)WN

k ? 0,1,
n ? 0,1,

, N ?1
, N ?1

1 N ?1 ? nk x(n) ? IDFT ? X (k )? ? ? X (k )WN N k ?0

二者的差别只在于 WN 的指数符号不同,以及差一个常
数乘因子 1 N ,因而我们只讨论DFT正变换的运算量。 IDFT的运算量是完全相同的。

DFT的运算量分析
? 一次复数乘法需用四次实数乘法和二次实数加法: ? 一次复数加法则需两次实数加法。

(a ? jb)(c ? jd ) ? (ac ? bd ) ? j (ad ? bc)

(a ? jb) ? (c ? jd ) ? (a ? c) ? j (b ? d )

复数乘法

复数加法

实数乘法

实数加法

一个
N ?1 n ?0

X (k )
nk N

? x(n)W

N

N ?1

4N

2 N ? 2( N ? 1)

N 个 X (k )

N

2

N ( N ? 1)

4N 2

2 N (2 N ? 1)

改进途径
利用 WNnk ? e (1)对称性 (2)周期性
?j 2? nk N

的特性

?W ?

nk * N

? nk ? WN

nk ( N ?n ) k n ( N ?k ) WN ? WN ? WN
nk nk / m nk mnk WN ? WN WN ? WmN /m

(3) 可约性
(4) 特殊点

0 WN ?1

WNN / 2 ? ?1

( k ? N / 2) k WN ? ?WN

? FFT算法的基本思想
– 使DFT运算中有些项可以合并; – 可以将长序列的DFT分解为短序列的DFT

? FFT算法分类:
– 时间抽选法 DIT: Decimation-In-Time – 频率抽选法 DIF: Decimation-In-Frequency

2 按时间抽选(DIT)的基-2 FFT算法(库利· 图基算法)
? 算法原理 先没序列点数为 N ? 2,L L为整数。如果不满足这个条件, 可以人为地加上若干零值点,使之达到这一要求。这种 为2 的整数幂的FFT也称基-2 FFT。 N 将 N ? 2 L的序列 x(n) (n ? 0,1, , N ? 1) 先按n的奇偶分成 以下两组:

x(2r ) ? x1 (r )

? ? , r ? 0,1, x(2r ? 1) ? x2 (r ) ?
N ?1 n ?0

N , ?1 2
nk N

X (k ) ? DFT ? x(n)? ? ? x(n)W

? ? x(n)W
n ?0

N ?1

nk N

nk ? ? x(n)WN n ?0

N ?1

n为偶数
N ?1 2 r ?0 N ?1 2 r ?0

n为奇数

2 rk (2 r ?1) k ? ? x(2r )WN ? ? x(2r ? 1)WN

? ? x1 (r ) ?W
r ?0

N ?1 2

2 rk N

?

?W

k N

? x (r ) ?W ?
r ?0 2

N ?1 2

2 rk N

利用系数 WN 的可约性:
2 WN ?e 2? ? j ?2 N ?j

nk

?e

? ? ?W N /2
N ?1 2 r ?0

2? N 2

rk k rk X (k ) ? ? x1 (r )WN ? W x ( r ) W /2 N ? 2 N /2 r ?0

N ?1 2

k ? X1 (k ) ? WN X 2 (k )

式中 X1 (k ) 和 X 2 (k ) 分别是 x1 (r ) 和 x2 (r ) 的N/2点DFT

rk rk X 1 (k ) ? ? x1 (r )WN ? x (2 r ) W ? /2 N /2 r ?0 r ?0

N ?1 2

N ?1 2

rk rk X 2 (k ) ? ? x2 (r )WN ? x (2 r ? 1) W ? /2 N /2 r ?0 r ?0

N ?1 2

N ?1 2

可看出,一个N点DFT已分解成两个N/2点的DFT,它们又

组合成一个N点DFT。
然而 X1 (k ) 和 X 2 (k ) 以及 x1 (r ) 和 x2 (r ) 都是N/2点的序列:

r , k ? 0,1,

N , ?1 2

X ( k )却有N点.而用上式计算得到的只是 X ( k ) 的前一半项

数的结果,要用 X1 (k ) 和 X 2 (k ) 来表达 X ( k ) 全部的值,还 必须应用系数的周期性,即:
rk WN / 2 ? WN / 2
N ?1 2

r (k ?

N ) 2

N r (k ? ) N rk X1 (k ? ) ? ? x1 (r )WN / 2 2 ? ? x1 (r )WN / 2 ? X 1 (k ) 2 r ?0 r ?0
N ?1 2 N ?1 2 r ?0

N ?1 2

X 2 (k ?

N ) ? ? x2 (r )W 2 r ?0

N r (k ? ) 2 N /2

rk ? ? x2 (r )WN / 2 ? X 2 (k )

nk 再考虑到 WN 的以下性质:

WN

(

N ?k ) 2

k k ? WNN / 2WN ? ?WN

将 X ( k ) 表达为前后两部分 前半部分

X (k ) ? X1 (k ) ? W X 2 (k )
k N

k ? 0,1,

N , ?1 2

后半部分
N k? N N N X (k ? ) ? X 1 (k ? ) ? WN 2 X 2 (k ? ) 2 2 2

? X1 ( k ) ? W X 2 ( k )
k N

k ? 0,1,

N , ?1 2

可以用蝶形信号流图符号表示,当支路上没有标出系数时,

则该支路的传输系数为1。

X 1 (k )

X 1 (k ) ? WNk X 2 (k )

X 2 (k )

WNk

X 1 (k ) ? WNk X 2 (k )

?1

N ? 2L

L?3
X 1 (0)
X 1 (1)

x1 (0) ? x(0)

X (0)
X (1)

x1 (1) ? x(2)
x1 (2) ? x(4)

N/2点 DFT

X 1 (2) X 1 (3)

X (2) X (3)

x1 (3) ? x(6) x2 (0) ? x(1)

X 2 (0)

X (4)
0 WN 1 WN

x2 (1) ? x(3)
x2 (2) ? x(5) x2 (3) ? x(7)
N/2点 DFT

X 2 (1)
X 2 (2)
X 2 (3)

?1 X (5) ?1

X (6)

WN2
3 WN

?1 X (7) ?1

计算量分析:
复数乘法 一个N/2点DFT 复数加法
N N ( ? 1) 2 2 N( N ? 1) 2

?N? ? ? ?2?
N 2
2

2

两个N/2点DFT 一个蝶形运算 N/2个蝶形运算 总计
N 点DFT

1
N 2

2
N
N N2 N ( ? 1) ? N ? 2 2

N N ? 2 2

2

N2

N ( N ? 1)

? 计算量减少一半 ? 可以进一步把每一个N/2点子序列再按其奇偶部分分解 为两个N/4点的子序列

N ? 2L

N/2仍是偶数

x1 (r ) 分解为奇偶两个序列

x3 (l ), x4 (l )

x1 (2l ) ? x3 (l )

? ? , l ? 0,1, x1 (2l ? 1) ? x4 (l ) ?

N , ?1 4

2 lk (2 l ?1) k X 1 (k ) ? ? x1 (2l )WN ? x (2 l ? 1) W ?1 /2 N /2 l ?0 l ?0

N ?1 4

N ?1 4

? ? x3 (l ) ?W
l ?0
?j 2? ?2 N 2

N ?1 4

lk 2 N /2
?j

?

?W
2? N 4

k N /2

? x (l ) ?W ?
l ?0 4

N ?1 4

lk 2 N /2

由于 WN2 / 2 ? e ? ? ? e ? ? ? WN / 4
lk k lk X1 (k ) ? ? x3 (l )WN ? W x ( l ) W /4 N /2 ? 4 N /4 l ?0 l ?0 N ?1 4 N ?1 4

? X 3 (k ) ? W

k N /2

X 4 (k )

k ? 0,1,

N , ?1 4

X 3 (k ) 与 X 4 (k ) 分别是 x3 (l ) 与 x4 (l ) 的N/4点的DFT: 其中,
lk lk X 3 (k ) ? ? x3 (l )WN ? x (2 l ) W ?1 /4 N /4 l ?0 l ?0
N ?1 4 l ?0 N ?1 4 l ?0

N ?1 4

N ?1 4

k ? 0,1,

lk lk X 4 (k ) ? ? x4 (l )WN ? x (2 l ? 1) W ?1 /4 N /4

N , ?1 4

同样可以计算 X 3 (k ) 在N/4到N/2-1的值
lk WN / 4 ? WN / 4 l (k ? N ) 4

由于

W

N ?k ) 4 N /2 (

k k ? WNN/ /24WN ? ? W /2 N /2

N X 3 (k ? ) ? ? x3 (l )WN / 4 4 l ?0
N ?1 4

N ?1 4

l (k ?

N ) 4

lk ? ? x3 (l )WN / 4 ? X 3 (k ) l ?0

N ?1 4

N l (k ? ) N lk X 4 (k ? ) ? ? x4 (l )WN / 4 4 ? ? x1 (l )WN / 4 ? X 4 (k ) 4 l ?0 l ?0

N ?1 4

k ? 0,1,

,

N ?1 4

因此:

N N N X 1 (k ? ) ? X 3 (k ? ) ? WN / 2 X 4 (k ? ) 4 4 4
(k ?

N ) 4

k ? X 3 (k ) ? WN / 2 X 4 (k )

x3 (0) ? x1 (0) ? x(0)
x3 (1) ? x1 (2) ? x(4)

X 3 (0)

X 1 (0)
X 1 (1)

N/4点 DFT

X 3 (1)

x4 (0) ? x1 (1) ? x(2)
x4 (1) ? x1 (3) ? x(6)

X 4 (0)

X 1 (2)
0 WN /2

N/4点 DFT

?1

X 4 (1)
1 WN /2

X 1 (3)
?1

x2 (2l ) ? x5 (l )

? ? , l ? 0,1, x2 (2l ? 1) ? x6 (l ) ?

N , ?1 4
N ?1 4

X 2 (k ) ? X 5 (k ) ? W

k N /2

X 6 (k )

N k X 2 (k ? ) ? X 5 (k ) ? WN / 2 X 6 (k ) 4

k ? 0,1,

,

X 5 (k ) 与 X 6 (k ) 分别是 x5 (l ) 与 x6 (l ) 的N/4点的DFT: 其中,
lk lk X 5 (k ) ? ? x5 (l )WN ? x (2 l ) W ? 2 /4 N /4 l ?0 l ?0 N ?1 4 l ?0 N ?1 4 l ?0 N ?1 4 N ?1 4

lk lk X 6 (k ) ? ? x6 (l )WN ? x (2 l ? 1) W ? 2 /4 N /4

x5 (0) ? x2 (0) ? x(1) x5 (1) ? x2 (2) ? x(5)

X 5 (0)

X 2 (0)

N/4点 DFT

X 5 (1)

X 2 (1)

x6 (0) ? x2 (1) ? x(3) x6 (1) ? x2 (3) ? x(7)

X 6 (0)

X 2 (2)
0 WN /2

N/4点 DFT

?1

X 6 (1)
1 WN /2

X 2 (3)
?1

k 2k W ? W 由于: N / 2 N

r W 将系数统一成 N 形式

N N=8的DFT可以分解为4个 ? 2 点DFT: 4

计算量又减少一半

x3 (0) ? x1 (0) ? x(0)
x3 (1) ? x1 (2) ? x(4)

X 3 (0)

X 1 (0)
X 1 (1)

X (0)

N/4点 DFT

X 3 (1)

X (1)

x4 (0) ? x1 (1) ? x(2)
x4 (1) ? x1 (3) ? x(6)

X 4 (0)

X 1 (2)
?1

X (2) X (3)

N/4点 DFT

0 WN

X 4 (1)
WN2

X 1 (3)
?1

x5 (0) ? x2 (0) ? x(1) x5 (1) ? x2 (2) ? x(5)

X 5 (0)

X 2 (0)

X (4)
0 WN

N/4点 DFT

?1

X 5 (1)

X 2 (1)

X (5)
?1

1 WN

x6 (0) ? x2 (1) ? x(3) x6 (1) ? x2 (3) ? x(7)

X 6 (0)

X 2 (2)
0 WN

X (6)
WN2

N/4点 DFT

?1

?1

X 6 (1)
WN2

X 2 (3)
?1
3 WN

X (7)
?1

讨论
? 按偶数与奇数的分解过程中序列标号的变化。
对于一个N=8点的DFT的例子,输入序列按偶数点与奇数 点第一次分解为两个N/2点序列:

再经过一起分解,剩下的是2点DFT,对于此例N=8,就
是4个
N ? 2 点DFT,其输出为 X 3 (k ) X 4 (k ) X 5 (k ) X 6 (k ) 4

k ? 0,1 可以方便地计算出来,例如:

X 3 (0) ? x3 (0) ? W20 x3 (1) ? x(0) ? W20 x(4) ? x(0) ? x(4)
X 3 (1) ? x3 (0) ? W21x3 (1) ? x(0) ? W21x(4) ? x(0) ?W20 x(4) ? x(0) ? x(4)

X 4 (0) ? x4 (0) ? W20 x4 (1) ? x(2) ? W20 x(6) ? x(2) ? x(6)
X 4 (1) ? x4 (0) ? W21x4 (1) ? x(2) ? W21x(6) ? x(2) ?W20 x(6) ? x(2) ? x(6)

X 5 (0) ? x5 (0) ? W20 x5 (1) ? x(1) ? W20 x(5) ? x(1) ? x(5)
X 5 (1) ? x5 (0) ? W21x5 (1) ? x(1) ? W21x(5) ? x(1) ?W20 x(5) ? x(1) ? x(5)

X 6 (0) ? x6 (0) ? W20 x6 (1) ? x(3) ? W20 x(7) ? x(3) ? x(7)
X 6 (1) ? x6 (0) ? W21x6 (1) ? x(3) ? W21x(7) ? x(3) ?W20 x(7) ? x(3) ? x(7)

偶序列
x(2r ) ? x1 (r )

奇序列

x(2r ? 1) ? x2 (r )
0,1,2,3 1,3,5,7 偶序列 奇序列

r n

0,1,2,3 0,2,4,6 偶序列
x1 (2l ) ? x3 (l )

奇序列

x1 (2l ? 1) ? x4 (l ) x2 (2l ) ? x5 (l )

x2 (2l ? 1) ? x6 (l )
0,1 1,3 3,7

l

0,1 0,2 0,4

0,1 1,3 2,6

0,1 0,2 1,5

r n

x(n) 的排列规律,将 n ? 0,1,

, N ?1 写成二进制,将二进制的

数码翻转,即得到正确的输入序列

这种方法的每一步分解那是按输入序列在时间上的次序 是属于偶数还是属于奇数来分解为两个更短的子序列,所 以称为“按时间抽选法”。

以N=8为例

x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7)

000, 001, 010, 011,100,101,110,111 000,100, 010,110, 001,101, 011,111
x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)
称为到位序规律

运算量分析:
? 由按时间抽选法FFT的流图可见,当 N ? 2 L 时,共有L级

蝶形,每级都由N/2个蝶形运算组成,每个蝶形有一次复
乘、二次复加.因而每级运算都需N/2次复乘和N次复加, 这样L级运算总共需要: N N 复乘数 mF ? L ? log 2 N 2 2 复加数 a ? NL ? N log N
F 2
0 实际计算量与这个数字稍有不同,因为 WN ? 1

WNN / 4 ? ? j

这几个系数都不用乘法运算,当N较大时,这些特例相

对而言就很少。

出于计算机上乘法运算所用时间比加法运算所需时间多得多、故
以乘法为例,在直接计算DFT与FFT算法的计算量之比为:
2N N 2 ? N N log N 2 log 2 N log 2 N 2 2 N2

N
2
4 8

N2
4
16 64

N log 2 N 2
1
4 12

N2

N log 2 N 2

4.0
4.0 5.4

16
32 64

256
1024 4096

32
80 192

8.0
12.8 21.4

128
256 512

16394
65536 262114

448
1024 2304

36.6
64.0 113.8

1024
2048

1048576
4194304

5120
11264

204.8
372.4

x3 (0) ? x1 (0) ? x(0)
x3 (1) ? x1 (2) ? x(4)
0 WN

X 3 (0)

X 1 (0)
X 1 (1)

X (0)

X 3 (1)
?1

X (1)

x4 (0) ? x1 (1) ? x(2)
x4 (1) ? x1 (3) ? x(6)
0 WN

X 4 (0)
0 WN

X 1 (2)
?1

X (2) X (3)

X 4 (1)
?1
WN2

X 1 (3)
?1

x5 (0) ? x2 (0) ? x(1) x5 (1) ? x2 (2) ? x(5)
0 WN

X 5 (0)

X 2 (0)

X (4)
0 WN

?1

X 5 (1)
?1

X 2 (1)

X (5)
?1

1 WN

x6 (0) ? x2 (1) ? x(3) x6 (1) ? x2 (3) ? x(7)
0 WN

X 6 (0)
0 WN

X 2 (2)
?1
WN2

X (6)
?1

X 6 (1)
?1
WN2

X 2 (3)
?1
3 WN

X (7)
?1

算法特点
? ? ? ? 1 同址运算 2 到位序规律 3蝶形运算两节点的“距离” 4 WNr的确定

r xm?1 ( p) ? xm ( p) ? WN xm (q)

xm?1 (q) ? xm ( p) ? W x (q)
r N m

p, q是参与本碟形单元运算的上下节点的序号。第m级序号为p, q的两点只参与这一个碟形单元的运算,其输出在第m+1级, 并且这一碟形单元不涉及别的点,即某一列的N个数据送到存 储器后,经蝶形运算,其结果为另—列数据,它们以蝶形为单 位仍存储在这同一组存储器中,直到最后输出,中间无需其他 存储器。也就是蝶形的两个输出值仍放回蝶形的两个输人所在 的存储器中。每列的N/2个蝶形运算全部完成后,再开始下 一列的蝶形运算。这样存储数据只需N个存储单元。下一级的 运算仍采用这种原位方式,只不过进人蝶形结的组合关系有所 不同。这种原位运算结构可以节省存储单元,降低设备成本。 称同址运算

蝶形运算两节点的“距离” 以8点FFT为例,其输入是倒位序的,输出是自然顺序的, 其第一级(第一列)每个蝶形的两节点间“距离”为1,第

二级每个蝶形的两节点“距离’’为2,第二级每个蝶
形的两节点“距离”为4,由此类推得,对 N ? 2L 每个蝶形的两节点“距离”为 2m?1 。 点FFT,

当输人为倒位序,输出为正常顺序时,其第m级运算,

(从左到右,第一级,第二级,…,第m级)

r 的确定 WN

r xm ( p) ? xm?1 ( p) ? WN xm?1 ( p ? 2m?1 ) r xm ( p ? 2m?1 ) ? xm?1 ( p) ? WN xm?1 ( p ? 2m?1 )

从最右边一级开始,看
m ? L(2 L ? N ), WNr , r ? 0,1, m ? 3, W8r , r ? 0,1, 2,3 m ? 2, W4r , r ? 0,1 m ? 1,W2r , r ? 0

分布规律
N ?1 2

任意第m级

W , r ? 0,1,
r 2m

2

m?1

?1

4按频率抽选(DIF)的基-2 FFT算法 (桑德· 图基算法)
这里讨论另一种FFT算法,称为按频率抽选(DIF)的FFT算 法,它是把输出序列 X ( k ) (也是N点序列)按其顺序的奇偶 分解为越来越短的序列。

算法原理
仍设序列点数为 N ? 2 L ,L为整数。在把输出 X ( k ) 按k的 奇偶分组之前,先把输入按n的顺序分成前后两半(注意,这 不是频率抽选);
N ?1 2 n ?0

nk nk nk X (k ) ? ? x(n)WN ? ? x(n)WN ? ? x(n)WN n ?0 n? N 2

N ?1

N ?1

nk ? ? x(n)WN n ?0 N ?1 2

N ?1 2

)k N ( n? N 2 ? ? x(n ? )WN 2 n ?0

N ?1 2

N k? ? N nk 2 ? ? ? x(n) ? x(n ? )WN ? WN 2 n ?0 ? ?

nk nk 式中用的WN 是,不是WN / 2 ,因而这并不是N/2点DFT。

N /2 因为 WN ? ?1

所以 W Nk / 2 ? (?1)k N

N ? nk ? k X (k ) ? ? ? x(n) ? (?1) x(n ? ) ? WN 2 ? n ?0 ?
k为偶数时 k为奇数时

N ?1 2

(?1)k ? 1
(?1)k ? ?1

按照k的奇偶将 X ( k ) 分为两部分

? k ? 2r ? ? k ? 2r ? 1

r ? 0,1,

,

N ?1 2

N ? 2 nr N ? nr ? ? X (2r ) ? ? ? x(n) ? x(n ? ) ? WN ? ? ? x(n) ? x(n ? ) ? WN / 2 2 ? 2 ? n ?0 ? n ?0 ?

N ?1 2

N ?1 2

N ? 2 nr n N ? n nr ? ? X (2r ? 1) ? ? ? x(n) ? x(n ? ) ? WN WN ? ? ? x(n) ? x(n ? ) ? WN WN / 2 2 ? 2 ? n ?0 ? n ?0 ?


N ?1 2

N ?1 2

N x1 (n) ? x(n) ? x(n ? ) 2 N ? n ? x2 (n) ? ? x(n) ? x(n ? ) ? WN 2 ? ?

n ? 0,1,

,

N ?1 2

nr X (2r ) ? ? x1 (n)WN /2 n ?0 N ?1 2 n ?0

N ?1 2

r ? 0,1,

nr X (2r ? 1) ? ? x2 (n)WN /2

N , ?1 2

x ( n)

N x ( n) ? x ( n ? ) 2

N x(n ? ) 2
?1

N ? n ? x ( n ) ? x ( n ? ) ? WN ? 2 ? ? WNn

x(0)
x(1)

X (0)
X (1)

x(2) x(3)

N/2点 DFT

X (2) X (3)

x(4) x(5) x(6) x(7)
?1 ?1 ?1 ?1
0 WN 1 WN

X (4) X (5)
N/2点 DFT

X (6) X (7)

WN2
3 WN

与时间抽选法的推导过程一样,由于 N ? 2 L ,N/2仍是—个

偶数,因而可以将每个N/2点DFT的输出再分解为偶数组与奇
数组,这就将N/2点DFT进一步分解为两个N/4点DFT。这两 个N/4点DFT的输入也是先将N/2点DFT的输入上下对半分开 后通过蝶形运算而形成。这样的分解可以一直进行到第L次 ( N ? 2 L ),第L次实际L是做两点DFT,它只有加减运算。但

是,为了比较并为了统一运算结构,我们仍然采用系数为
的蝶形运算来表示,这N/2个两点DFT的N个输出就是
WNn

x ( n)

的N点DFT的结果 X ( k ) 。

x(0)
x(1)

X (0)
N/4点 DFT

X (4)

x(2)
?1
0 WN

X (2)
N/4点 DFT

x(3)
?1
WN2

X (6)

x(4)
?1

X (1)
0 WN

x(5)
?1

N/4点 DFT

X (5)

1 WN

x(6)
?1
WN2

X (3)
?1
0 WN

x(7)
?1
3 WN

N/4点 DFT

X (7)

?1

WN2

x(0)
x(1)
?1
0 WN

X (0)

X (4)

x(2)
?1
0 WN

X (2) X (6)
?1
WN2

x(3)
?1
0 WN

x(4)
?1

X (1)
0 WN

x(5)
?1

X (5)
?1
0 WN

1 WN

x(6)
?1
WN2

X (3)
?1
0 WN

x(7)
?1
3 WN

X (7)
?1
WN2

?1

0 WN

算法特点
? 1 同址运算 ? 2蝶形运算两节点的“距离” ? 3 WNr 的确定

X m (k ) ? X m?1 (k ) ? X m?1 ( j )

X m ( j ) ? ? X m?1 (k ) ? X m?1 ( j ) ?WNr

X m (k )

X m ?1 (k ) ? X m?1 ( j )

X m ( j)
?1

? X m?1 (k ) ? X m?1 ( j )?WNr
WNr

蝶形运算两节点的“距离” 以8点FFT为例,其输入是自然顺序的,输出是倒位序的, 其第一级(第一列)每个蝶形的两节点间“距离”为4,第

二级每个蝶形的两节点“距离’’为2,第二级每个蝶
形的两节点“距离”为1,由此类推得,对 N ? 2L
N L?m 每个蝶形的两节点“距离”为 2 ? m 2

点FFT,

当输人为自然顺序,输出为倒位序时,其第m级运算, 。

(从左到右,第一级,第二级,…,第m级)

r 的计算 WN

N X m (k ) ? X m ?1 (k ) ? X m ?1 (k ? m ) 2 N N ? ? X m (k ? m ) ? ? X m ?1 (k ) ? X m ?1 (k ? m ) ? WNr 2 2 ? ?

从最左边一级开始,看
N N r ,WN , r ? 0,1, ?1 2 2 N N r m ? 2, ,WN , r ? 0, 2, ?2 4 2 m ? 1, m ? l, N r l ?1 , W , r ? k ? 2 , k ? 0,1, N l 2

分布规律

,

N ?1 l 2

任意第m级

W ,r ? k ?2
r N

m ?1

, k ? 0,1,

N ?1 m 2

按频率抽选法与按时间抽选法的异同
?
DIF的基本蝶形与DIT的基本蝶形运算顺序有所不问, 这才是实质的不同,DIF的复数乘法只出现在减法之后,

DIT则是先作复乘后作加减法。

?
mF ?

DIF与DIT就运算量来说则是相同的,即都有L级(列) 运算,每级运算需N/2个蝶形运算来完成,总共需要
N N L ? log 2 N 2 2

次复乘与 aF ? NL ? N log2 N

次复


?

DIF法与DIT法都可进行同址运算。

离散傅里叶反变换(IDFT)的快速计算方法
上面的FFT算法同样可以适用于离散傅里叶反变换(1DFT)运
算,即快速傅里叶反变换(IFFT)。比较IDFT和DFT公式:

1 x ( n) ? N

? nk X ( k ) W ? N k ?0

N ?1

nk X (k ) ? ? x(n)WN n ?0

N ?1

只要把DFT运算中的每一个系数 W nk 换成 W ? nk ,最后再乘以 N N 常数1/N,则以上所有按时间抽选或按频率抽选的FFT都可以拿 来运算IDFT。

上面这种IFFT算法虽然编程很方便,但是需要稍稍改动 FFT的程序和参数才能实现。下面讨论一种完全不用改

变FFT的程序就可以计算IFFT的方法。我们对IDFT公式
式取共轭:

?W ?

nk * N

? nk ? WN

N ?1 1 nk x* (n) ? ? X * (k )WN N k ?0



* 1? 1 * nk ? * x(n) ? ?? X (k )WN ? ? ?DFT [ X (k )]? N ? k ?0 ? N N ?1

*

这说明,只要先将X(k)取共轭,就可以直接利用FF丁子程 序,最后再将运算结果取一次共扼,并乘以1/N,即得到 x(n)值。因此,FFT运算和IFFT运算就可以共用一个子程 序块。

基-4FFT算法
L N ? 4 ? 时就是基-4FFT算法

频率抽取的基-4FFT算法
nk nk X (k ) ? ? x(n)WN ? ? x(n)WN ? n ?0 n?
N ?1 4

N ?1 4

N ?1 2 N 4

3N ?1 4

?
N 2

nk x(n)WN ?

?
n?
N ?1 4

N ?1 3N 4

nk x(n)WN

n?
N ?1 4

nk ? ? x(n)WN n ?0

N ?1 4

N ? ? x(n ? )W 4 n ?0

N ( n? ) k 4 N

N ? ? ? x(n ? )W 2 n ?0

N ( n? ) k 2 N

N )k 3N ( n ? 34 ? ? x( n ? )WN 4 n ?0

N N 3N 3 Nk / 4 ? nk ? ? ? x(n) ? x(n ? )WNNk / 4 ? x(n ? )WNNk / 2 ? x(n ? )WN WN ? 4 2 4 ? ?

令 k ? 4r , k ? 4r ? 1, k ? 4r ? 2, k ? 4r ? 3, r ? 0,1,
利用
nk nk / m nk mnk WN ? WN WN ? WmN /m

N , ?1 4

kN N /4 N /2 3N / 4 WN ? 1,WN ? ? j,WN ? ?1,WN ?j

N N 3N ? 4 nr ? X (4r ) ? ? ? x(n) ? x(n ? ) ? x(n ? ) ? x(n ? ) ? WN 4 2 4 ? n ?0 ? ?? N ? ? N 3N ? ? nr ? ? ? ? x ( n) ? x ( n ? ) ? ? ? x ( n ? ) ? x ( n ? ) ? ? WN / 4 2 ? ? 4 4 ?? n ? 0 ??
N N 3N ? 4 nr n ? X (4r ? 1) ? ? ? x(n) ? jx(n ? ) ? x(n ? ) ? jx(n ? ) ? WN WN 4 2 4 ? n ?0 ? ?? N ? ? N 3N ? ? nr n ? ? ?? x ( n) ? x ( n ? ) ? ? j ? x ( n ? ) ? x ( n ? ) ? ? WN / 4WN 2 ? ? 4 4 ?? n ? 0 ??
N ?1 4 N ?1 4

N ?1 4

N ?1 4

N N 3N ? 4 nr 2 n ? X (4r ? 2) ? ? ? x(n) ? x(n ? ) ? x(n ? ) ? x(n ? ) ? WN WN 4 2 4 ? n ?0 ? ?? N ? ? N 3N ? ? nr 2 n ? ? ?? x ( n ) ? x ( n ? ) ? ? ? x ( n ? ) ? x ( n ? ) ? ? WN / 4WN 2 ? ? 4 4 ?? n ? 0 ??
N ?1 4
N ?1 4

N ?1 4

N N 3N ? 4 nr 3n ? X (4r ? 3) ? ? ? x(n) ? jx(n ? ) ? x(n ? ) ? jx(n ? ) ? WN WN 4 2 4 ? n ?0 ? ?? N ? ? ? ?? x ( n ) ? x ( n ? ) ? ? 2 ? n ? 0 ??
N ?1 4

N 3N ? ? nr 3n ? j ? x(n ? ) ? x(n ? ) ? ? WN / 4WN 4 4 ?? ?

? 可以把一个DFT分成4个N/4点的DFT

实序列的FFT算法
? 实际工作中序列一般都是实序列,如果直接按照FFT的算 法计算,就是把序列看成是虚部为零的复序列计算,这增 加了存储量和运算时间。

解决方法一:
一个N点的FFT计算两个N点的实序列FFT,一个序列作实部,

另一个序列作虚部,计算完FFT后,有DFT的共轭对称性,
由输出X(k)得到两个实序列的N点DFT

? 方法二 设x(n)为N点序列,取x(n)的偶数点和奇数点作为新序列的 实部和虚部:

x1 (n) ? x(2n) x2 (n) ? x(2n ? 1), n ? 0,1, N , ?1 2

y(n) ? x1 (n) ? jx2 (n)

? 对y(n)进行N/2点的FFT, 输出Y(k) 则: X 1 (k ) ? DFT [ x1 (n)] ? Yep (k )
X 2 (k ) ? DFT [ x2 (n)] ? ? jYop (k ), k ? 0,1, N , ?1 2

再根据DIT-FFT的思想:
k X (k ) ? X 1 (k ) ? WN X 2 (k ), k ? 0,1,

,

N ?1 2

由于x(n)为实序列,所以X(k)具有共轭对称性的,可 求另外n/2点的值
X ( N ? k ) ? X (k ), k ? 0,1,
*

N , ?1 2


推荐相关:

小波分析 快速傅里叶变换_图文.ppt

小波分析 快速傅里叶变换 - 快速傅里叶变换 ? 快速傅里叶变换(FFT)并不是

快速傅里叶变换FFT_图文.ppt

快速傅里叶变换FFT - 4.1 综述 ? 小波函数(快衰减振荡波形) ? 设基本小波 ? (t ) ?? 傅氏变换 ? ??? (? ) ? 第四章 信号的小波变换与分析 ---...

快速傅里叶变换(FFT)与小波变换技术_图文.pdf

快速傅里叶变换(FFT)与小波变换技术 - 维普资讯 http://www.cq

小波分析与实例._图文.ppt

小波分析与实例. - 小波分析 小波分析讲解 ? 傅里叶变换与小波分析 ? 小波分析的基本知识 ? 多尺度分析与Mallat算法 ? 小波分析的应用 1、傅里叶变换与小波...

小波分析与实例_图文.ppt

小波分析与实例 - 小波分析 小波分析讲解 ? 傅里叶变换与小波分析 ? 小波分析的基本知识 ? 多尺度分析与Mallat算法 ? 小波分析的应用 1、傅里叶变换小波分析...

06小波变换压缩算法解析_图文.ppt

06小波变换压缩算法解析 - 第6章 小波变换 压缩算法 主要内容 ? ? ? ? 小波变换用于图像压缩的理由 傅里叶变换 窗口傅里叶变换 小波变换的原理 ? ? 小波...

压气机喘振声音信号的快速傅里叶变换和小波变换分析_图文.pdf

压气机喘振声音信号的快速傅里叶变换小波变换分析 - 第 31 卷第 3 期 2

基于傅里叶变换和小波分析的拖拉机振动研究_郝欢欢_图文.pdf

本文用快速傅里叶变换分析方法 , 讨论了拖拉机 不同车速下座椅的振动特性 , 并基于小波分析的方法 对拖拉机整车振动信号进行了处理分析 , 从而为拖拉 机减振研究...

傅里叶变换和小波变换简介_图文.ppt

傅里叶变换小波变换简介 - 简要介绍了傅里叶变换的历史和小波变换应用,几个小波变换示例。

傅立叶分析和小波分析之间的关系之通俗终极版_图文.doc

傅立叶分析和小波分析之间的关系之通俗终极版转载请注明出处和作者 知乎作者:咚懂咚懂咚 从傅里叶变换小波变换,并不是一个完全抽象的东西,完全可以讲得很形象...

006-小波分析(第一讲)-小波基础+连续小波_图文.ppt

006-小波分析(第一讲)-小波基础+连续小波_经济学_高等教育_教育专区。小波分析...13/ 102 快速傅里叶变换快速傅立叶变换,简称FFT,计算DFT的快速算 法的统称 ...

数字信号处理,DSP 第四章 快速傅里叶变换_图文.ppt

第四章 快速傅里叶变换 1、直接计算DFT的问题 2、按时间抽选(DIT)的基2FFT...(4)汽车速度和里程的测量例,用FFT估算小波 变换 (变尺度卷积)所处理的频率...

傅里叶变换与小波变换在信号去噪中的应用_图文.pdf

傅里叶变换小波变换在信号去噪中的应用 - 第 19 卷 第4期 电子设计工程

基于FFT与db10小波变换的电网谐波综合分析_图文.doc

目前,比较经典的谐波检测方法就是快速傅里叶变换(FFT),它 能快速且准确地计算出稳态谐波,但是对于非稳态谐波信号就无能为力了。小波分析 (DWT)能有效地检测非...

基于快速傅里叶变换的id-iq谐波检测算法_图文.pdf

近 2基于LF的 P 谐波检测算法 基 于神 经网络 的谐 波检测、基于小波变换 ...d。- 31快速傅里叶变换与谱分析 . 和频率为 的2倍 的交 流分量 。因此 ...

小波变换与傅里叶变换的对比、异同.doc

小波变换傅里叶变换的对比、异同 - 小波变换傅里叶变换的对比、 小波变换傅里叶变换的对比、异同 一、基的概念 两者都是基,信号都可以分成无穷多个他们...

基于小波变换和快速傅里叶变换的谐波检测_论文.pdf

基于小波变换快速傅里叶变换的谐波检测 - 基于傅里叶变换的谐波检测方法可以确定平稳信号中各次谐波的频率和幅值,小波变换可以准确把握信号的局部细节。利用两种...

FFT与DWT(快速傅里叶变换和离散小波变换).doc

FFT与DWT(快速傅里叶变换和离散小波变换)_信息与通信_工程科技_专业资料。

连续小波变换快速带通滤波实现算法的研究_图文.pdf

在众多的小 波分析方法中,应用最多的方法是二进离散小波变换 和连续小波变换。...(m)进行快速傅里叶变换(InverseFourierfast 以相同的采样频率厶进行抽样。当...

傅里叶变换_图文.pdf

离散时间傅里叶变换 离散傅里叶变换 快速傅里叶变换 分傅立 短距傅立 小波分析 散小波 file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com