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 ) ?? 傅氏变换 ? ??? (? ) ? 第四章 信号的小波变换与分析 ---...

快速傅里叶和小波变换.ppt

FFT和小波变换基本原理的串讲FFT和小波变换基本原理的串讲隐藏>> 快速傅里叶变换(FFT) 陈 Email:amy0938@hotmail.com 本讲在分析直接计算DFT的特点的基础上介绍...

一种基于离散傅里叶变换的小波变换的快速算法_图文.pdf

一种基于离散傅里叶变换小波变换快速算法 - 第 卷 第期年月 ( ) 南京工

基于快速傅里叶变换(FFT)和小波变换的大型风机机械振动....doc

基于快速傅里叶变换(FFT)和小波变换的大型风机机械振动故障的分析 - 龙源期刊网 http://www.qikan.com.cn 基于快速傅里叶变换(FFT)和小波变换的 大型风机机械...

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

基于小波变换快速傅里叶变换的谐波检测 - 小波变化,傅里叶变化,区别,定义,原理,... 2012 第7期 基于小波变换快速傅里叶变换的谐波检测桑松, 柴玉华, 孙影(...

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

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

结合二代小波与快速傅里叶变换的电能质量数据压缩算法.pdf

结合二代小波快速傅里叶变换的电能质量数据压缩算法 - 针对大量电能质量数据的传输和储存问题,提出一种结合快速傅里叶变换(FFT)和二代小波(SGWT)的电能质量数据...

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

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

小波变换与傅里叶变换.doc

小波变换傅里叶变换 - 小波变换傅里叶变换 如果有人问我, 如果傅里叶变换没有学好 (深入理解概念) 是否能学好小波。 , 答案是否定的。 如果有人还问...

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

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

小波变换与傅里叶变换.txt

小波变换傅里叶变换 - 小波变换傅里叶变换 分类: 图像处理与机器视觉 2010-09-15 16:16 1084人阅读 评论(0) 收藏 举报 如果有人问我,如果傅里叶变换...

小波变换与傅里叶变换比较_图文.ppt

小波变换傅里叶变换比较 - 小波变换傅里叶变换比较 小波变换 ? 什么是小波

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

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

详解傅里叶变换与小波变换.pdf

详解傅里叶变换小波变换 - 详解傅里叶变换与小波变化 希望能简单介绍一下小波变换, 它和傅立叶变换的比较, 以及它在移 动平台做 motion detection 的应用。...

结合二代小波与快速傅里叶变换的电能质量数据压缩算法_....pdf

结合二代小波快速傅里叶变换的电能质量数据压缩算法 - 201 3年第 7卷第

傅立叶变换与小波变换区别分析_图文.pdf

傅立叶变换小波变换区别分析 - 第34卷增刊 V01.34增刊 河北工业大学学

计算机-小波变换与傅里叶变换.pdf

计算机-小波变换傅里叶变换 - 如果有人问我,如果傅里叶变换没有学好(深入理解概念),是否 能学好小波。答案是否定的。如果有人还问我,如果第一代小波变换没...

傅里叶变换与小波变换区别.doc

傅里叶变换小波变换区别 - 傅里叶变换的特点: 对于数据信号的去噪,傅立叶变换是将信号完全的放在频率域中分析,但无法给出 信号在每一个时间点的变化情况,无...

短时傅里叶变换和小波变换.doc

短时傅里叶变换小波变换 - 短时傅里叶变换小波变换 吴桐 (西南交通大学峨眉校区机械工程系铁道车辆一班 学号 20116432) 摘要:短时傅里叶变换(STFT,short-...

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