kl800.com省心范文网

数字信号处理课件第4章快速傅里叶变换FFT_图文

第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶变换(FFT)
4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 分裂基FFT算法 4.5 离散哈特莱变换(DHT)

课件

1

第4章 快速傅里叶变换(FFT)
4.1 引言
DFT是信号分析与处理中的一种重要变换。因直 接计算DFT的计算量与变换区间长度N的平方成正比, 当N较大时,计算量太大,所以在快速傅里叶变换(简 称FFT)出现以前,直接用DFT算法进行谱分析和信号 的实时处理是不切实际的。直到1965年发现了DFT的 一种快速算法以后,情况才发生了根本的变化。

课件

2

第4章 快速傅里叶变换(FFT)
4.2 基2FFT算法

4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为

N ?1
? X (k) ? x(n)WNkn, k ? 0,1,???, N ?1
n?0

(4.2.1)

考虑x(n)为复数序列的一般情况,对某一个k值,

直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次

复数加法。

课件

3

第4章 快速傅里叶变换(FFT)

如前所述,N点DFT的复乘次数等于N2。显然,

把N点DFT分解为几个较短的DFT,可使乘法次数大大

减少。另外,旋转因子WmN具有明显的周期性和对称 性。其周期性表现为

W m?lN N

? j 2? (m?lN )
?e N

? j 2? m
?e N

? WNm

(4.2.2)

其对称性表现为

WN?m ? WNN ?m 或者 [WNN ?m ]? ? WNm

m? N
WN 2

? ?WNm

课件

4

第4章 快速傅里叶变换(FFT)

4.2.2 时域抽取法基2FFT基本原理 FFT 算 法 基 本 上 分 为 两 大 类 : 时 域 抽 取 法
FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取 法FFT(Decimation In Frequency FFT,简称DIF―FFT)。 下面先介绍DIF―FFT算法。
设序列x(n)的长度为N,且满足

N ? 2M , M 为自然数

按n的奇偶把x(n)分解为两个N/2点的子序列

x1(r) ? x(2r),

r ? 0,1,??? N ?1 2

x2(r) ? x(2r ? 1),

r ? 0,1,??? N ?1

课件

2

5

第4章 快速傅里叶变换(FFT)

则x(n)的DFT为

? ? X (k ) ? x(n)WNkn ? x(n)WNkn

n?

n?

N / 2?1

N / 2?1

? ? ?

x(2r)WN2kr ?

x(2r ? 1)WNk (2r?1)

r?0

r?0

N / 2?1

N / 2?1

? ? ?

x1(r) ? WNk

x2 (r)WN2kr

由于

r?0

r?0

W 2kr N

?

? j 2? 2kr
eN

?

j

2? N

kr

?e 2

?

W 2kr N /2

所以

N / 2?1

N / 2?1

? ? X (k) ?

x1(r)WNkr/ 2 ? WNk

x2 (r)WNkr/ 2 ? X1(k ) ? WNk X 2 (k )

r?0

r?0

课件

6

第4章 快速傅里叶变换(FFT)

其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,

即 N / 2?1

? X1(k) ?

x1(r)WNkr/ 2 ? DFT [x1(r)]

r?0

(4.2.5)

N / 2?1

? X 2(k) ?

x2 (r)WNkr/ 2 ? DFT [x2 (r)]

r?0

(4.2.6)

由于X1(k)和X2(k)均以N/2为周期,且

k?N
WN 2

? ?WNk

,所以X(k)又可表示为

X (k) ? X1(k) ? WNk X 2(k)

k ? 0,1,??? N ?1 2

X

(k

?

N 2

)

?

X1(k)

? WNk

X 2 (k )

k ? 0,1,??? N ?1 2

(4.2.7) (4.2.8)

课件

7

第4章 快速傅里叶变换(FFT)

A

A+ B C

C B

A- B C

图4.2.1 蝶形运算符号

课件

8

第4章 快速傅里叶变换(FFT)

x(0 )

X1(0 )

X(0 )

x(2 )

N/2点 X1(1 )

X(1 )

x(4 )

X1(2 )

X(2 )

DFT

x(6 )

X1(3 )

X(3 )

x(1 )

X2(0 )

W

0 N

X(4 )

x(3 )

N/2点 X2(1 )

W

1 N

X(5 )

x(5 )

DFT

X2(2 )

W

2 N

X(6 )

x(7 )

X2(3 )

W

3 N

X(7 )

图4.2.2 N点DFT的一次时域抽取分解图(N=8)

课件

9

第4章 快速傅里叶变换(FFT)

与第一次分解相同,将x1(r)按奇偶分解成两个N/4

长的子序列x3(l)和x4(l),即

x3 (l ) x4 (l )

? ?

x2 x1

(2l (2l

) ?

1)

? ? ?

,

l

?

0,1, ? ? ?,

N 4

?1

那么,X1(k)又可表示为

N / 4?1

N / 4?1

? ? X1(k) ?

x1

(2l

)WN2

kl /2

?

x1(2l

?

1)WNk

(2l ?1) /2

i?0

i?0

N / 4?1

N / 4?1

? ? ?

x3(l )WNkl/ 4 ? WNk / 2

x4 (l )WNkl/ 4

i?0

i?0

? x3(k ) ? WNk /2 X 4 (k ), k ? 0,1,? ? ?N / 2 ? 1

(4.2.9)

课件

10

第4章 快速傅里叶变换(FFT)

? 式中

N / 4?1
x3(k) ?

x3(l)WNkl/ 4 ? DFT [x3(l)]

i?0

N / 4?1

? x4(k) ?

x4 (l)WNkl/ 4 ? DFT [x4 (l)]

i?0

同理,由X3(k)和X4(k)的周期性和Wm N/2的对称

性 Wk+N/4 N/2=-Wk N/2 最后得到:

X X

1 1

(k (k

) ? X3(k ? N / 4)

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

2

X

4

(k

)

?? ? ??

,

k

?

0,1, ? ? ?,

N

/

4

?1

(4.2.10)

课件

11

第4章 快速傅里叶变换(FFT)

用同样的方法可计算出

X X

2 2

(k (k

) ? X5(k ? N / 4)

) ? WNk ? X5k

/2
?

X 6 (k Wk
N /2

) X

6

(k

)

?? ? ??

,

k

?

0,1, ? ? ?N

/

4

?1

其中

N / 4?1

? X5(k) ?

x5(l)WNkl/ 4 ? DFT [x5(l)]

i?0

N / 4?1

? X 6(k) ?

x6 (l)WNkl/ 4 ? DFT [x6(l)]

i?0

x5 (l ) x6 (l )

? ?

x2 x2

(2l (2l

) ?

1)

? ? ?

,

l

?

0,1, ? ? ?N

/

4

?1

(4.2.11)

课件

12

第4章 快速傅里叶变换(FFT)

x(0 )

N/4点 X3(0 )

x(4 )

DFT X3(1 )

x(2 )

N/4点

X4(0 )

W

0 N

2

x(6 )

DFT

X4(1 )

W

1 N

2

x(1 )

N/4点

x(5 )

DFT

x(3 )

N/4点

x(7 )

DFT

W

0 N

2

W

1 N

2

X1(0 )

X1(1 )

X1(2 )

X1(3 )

X2(0 )

W

0 N

X2(1 )

W

1 N

X2(2 )

W

2 N

X2(3 )

W

3 N

X(0 ) X(1 ) X(2 ) X(3 ) X(4 ) X(5 ) X(6 ) X(7 )

图4.2.3 N点DFT的第二次时域抽取分解图(N=8)

课件

13

第4章 快速傅里叶变换(FFT)

A(0 ) x(0 )

A(1 )

x(4 )

A(2 )

W

0 N

x(2 )

A(3 )

x(6 )

A(4 )

W

0 N

x(1 )

A(5 )

x(5 )

A(6 )

W

0 N

x(3 )

A(7 )

x(7 )

W

0 N

A(0 )

A(1 )

A(2 )

W

0 N

A(3 )

W

2 N

A(4 )

A(5 )

A(6 )

W

0 N

A(7 )

W

2 N

A(0 )

A(1 )

A(2 )

A(3 )

A(4 )

W

0 N

A(5 )

W

1 N

A(6 )

W

2 N

A(7 )

W

3 N

图4.2.4 N点DIT―FFT运算流图(N=8)
课件

A(0 ) X(0 ) X(1 ) X(2 ) X(3 ) X(4 ) X(5 ) X(6 )
A(7 ) X(7 )
14

第4章 快速傅里叶变换(FFT)

4.2.3 DIT―FFT算法与直接计算DFT运算量的比较

每一级运算都需要N/2次复数乘和N次复数加(每个 蝶形需要两次复数加法)。所以,M级运算总共需要的 复数乘次数为

CM (2)

?

N 2

?M

?

N 2

log2

N

复数加次数为

CA(2) ? N ? M ? N log2 N 例如,N=210=1024时

N2

? 1048576 ? 204.8

(N / 2) log2 N 5120

课件

15

第4章 快速傅里叶变换(FFT)

图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线

课件

16

第4章 快速傅里叶变换(FFT)
4.2.4 DIT―FFT的运算规律及编程思想 1.原位计算 由图4.2.4可以看出,DIT―FFT的运算过程很有规
律。N=2M点的FFT共进行M级运算,每级由N/2个蝶 形运算组成。
2.旋转因子的变化规律 如上所述,N点DIT―FFT运算流图中,每级都有 N/2个蝶形。每个蝶形都要乘以因子WpN,称其为旋转 因子,p称为旋转因子的指数。

课件

17

第4章 快速傅里叶变换(FFT)
观察图4.2.4不难发现,第L级共有2 L-1个不同的旋 转因子。N=23=8时的各级旋转因子表示如下:
L=1时,WpN=WJ N/4=WJ2L, J=0 L=2时, WpN =WJ N/2=WJ2L, J=0,1 L=3时, WpN =WJN=WJ2L, J=0,1,2,3 对N=2M的一般情况,第L级的旋转因子为

WNp ? W2J L, J ? 0,1, 2,? ? ?, 2L?1 ? 1 2L ? 2M ? 2L?M ? N ? 2L?M

WNP

?WJ N 2L?M

? WNJ

, J 2M ?L

? 0,1, 2,? ? ?, 2L?1 ? 1

(4.2.12)

p ? J 2M?L

(4.2.13)

课件

18

第4章 快速傅里叶变换(FFT)
3. 蝶形运算规律 设序列x(n)经时域抽选(倒序)后,存入数组X中。 如果蝶形运算的两个输入数据相距B个点,应用原位计 算,则蝶形运算可表示成如下形式:
X (J) ? XL-1(J)+X L-1(J+B)WpN XL(J+B) ? XL-1(J)-X L-1(J+B)WpN
式中 p=J·2 M-L;J=0,1,…,2 L-1-1;L=1,2,…,M

课件

19

第4章 快速傅里叶变换(FFT)

下标L表示第L级运算,XL(J)则表示第L级运算后 数组元素X(J)的值。如果要用实数运算完成上述蝶形 运算,可按下面的算法进行。



T=X L-1(J+B)WpN=TR+jTI

X L-1(J)=X′R(J)+jX′I(J) 式中下标R表示取实部,I表示取虚部,

TR

?

X R? (J

? B) cos 2?
N

p ? X R? (J

?

B)I

sin

2?
N

p

TI

?

X I? (J

? B) cos 2?
N

p?

X R? (J

?

B)I

sin

2?
N

p

课件

20

第4章 快速傅里叶变换(FFT)

XL(J ) ? XR(J ) ? j(J )



X R (J ) ? X R? (J ) ? TR

X I (J ) ? X I?(J ) ? TI

X R (J ? B) ? X R? (J ) ? TR

X I (J ? B) ? X I?(J ) ? TI

课件

21

4. 编程思想及程序框图
图4.2.6 DIT―FFT运算和程序框图
课件

第4章 快速傅里叶变换(FFT)
开始 送 入x(n),M
N= 2M 倒序 L= 1 M, B 2 L-1 J= 0 B, - 1 P= 2M -LJ k = J , N- 1 , L2 X (k) ? X (k) ? X (k ? B)WNp X (k ? B) ? X (k) ? X (k ? B)WNp
输出 结束
22

5. 序列的倒序

第4章 快速傅里叶变换(FFT)

DIT―FFT算法的输入序列的排序看起来似乎很乱, 但仔细分析就会发现这种倒序是很有规律的。由于

N=2M , 所 以 顺 序 数 可 用 M 位 二 进 制 数 (nM-1nM-2…n1n0) 表示。

0 0
1 0
0 1
1

000 0 100 4 010 2 110 6

0 0
1 1
0 1
1

(n2n1n0)2

001 1 101 5 011 3 111 7

图4.2.7 形成倒序的树状图(N=23)

课件

23

第4章 快速傅里叶变换(FFT) 表4.2.1 顺序和倒序二进制数对照表

课件

24

第4章 快速傅里叶变换(FFT)
x(0 ) x(1 ) x(2 ) x(3 ) x(4 ) x(5 ) x(6 ) x(7 ) A(0 ) A(1 ) A(2 ) A(3 ) A(4 ) A(5 ) A(6 ) A(7 )

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

图4.2.8 倒序规律

课件

25

LH ? N 2 J ? LH N1 ? N ? 2
I= 1 N, 1
Y I≥ J
N T ? X (I) A(I ) ? X (J ) A(J ) ? T

第4章 快速傅里叶变换(FFT)

K ? LH

J <K

N

Y

J ?J?K

J ?J?K K?K 2

图4.2.9 倒课序件程序框图

26

第4章 快速傅里叶变换(FFT)

4.2.5 频域抽取法FFT(DIF―FFT)

在基2快速算法中,频域抽取法FFT也是一种常用 的快速算法,简称DIF―FFT。

设序列x(n)长度为N=2M,首先将x(n)前后对半分

开,得到两个子序列,其DFT可表示为如下形式:

N ?1
? X (k) ? DFT[x(n)] ? x(n)WNk
n?0

N / 2?1

N ?1

? ? ?

x(n)WNkn ?

x(n)WNkn

n?0

n?N /2

? ? N / 2?1
?
n?0

N / 2?1
x(n)WNkn ?
n?0

x(n

?

N 2

)W k (n?N / 2) N

?N / 2?1
?
n?0

[x(n)

?

W kN / 2 N课件

x

(n

?

N 2

)]WNkn

27

第4章 快速傅里叶变换(FFT)

W kN / 2 N

?

(?1)k

?

??1, ????1

k ? 偶数 k ? 奇数

将X(k)分解成偶数组与奇数组,当k取偶数

(k=2r,r=0,1,…,N/2-1)时

?N / 2?1
X (2r) ?
n?0

[x(n)

?

x(n

?

N 2

)]WN2rn

?N / 2?1
?
n?0

[x(n)

?

x(n

?

N 2

)]WN2

rn /2

(4.2.14)

课件

28

第4章 快速傅里叶变换(FFT)

当k取奇数(k=2r+1,r=0,1,…,N/2-1)时

?N / 2?1
X (2r ? 1) ?
n?0

[x(n)

?

x(n

?

N 2

)]WNn ( 2 r ?1)

?N / 2?1
?
n?0

[x(n)

?

x(n

?

N 2

)]WNn

W nr N /2

(4.2.15)

将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式,可得

? ?
??

X

?

(2r)

?

N / 2?1
x1(n)WNrn/ 2
n?0
N / 2?1

? ?
??

X

(2r

?

1)

?

n?0

x2 (n)WNrn/ 2

(4.2.16)

课件

29

第4章 快速傅里叶变换(FFT)

图4.2.10 DIF―FFT蝶形运算流图符号

课件

30

第4章 快速傅里叶变换(FFT)

x(0 )

x1(0 )

X(0 )

x(1 )

x1(1 ) N/2点

X(2 )

x(2 )

x1(2 )

X(4 )

DFT

x(3 )

x1(3 )

X(6 )

x(4 )

W

0 N

x2(0 )

X(1 )

x(5 )

W

1 N

x2(1 ) N/2点

X(3 )

x(6 )

W

2 N

x2(2 ) DFT

X(5 )

x(7 )

W

3 N

x2(3 )

X(7 )

图4.2.11 DIF―FFT一次分解运算流图(N=8)

课件

31

第4章 快速傅里叶变换(FFT)

x(0 )

N/4点

X(0 )

x(1 )

DFT

X(4 )

x(2 )

W

0 N

N/4点

X(2 )

x(3 )

W

2 N

DFT

X(6 )

x(4 )

W

0 N

N/4点

X(1 )

x(5 )

W

1 N

DFT

X(5 )

x(6 )

W

2 N

W

0 N

N/4点

X(3 )

x(7 )

W

3 N

W

2 N

DFT

X(7 )

图4.2.12 DIF―FFT二次分解运算流图(N=8)

课件

32

第4章 快速傅里叶变换(FFT)

x(0 )

X(0 )

x(1 )

W

0 N

X(4 )

x(2 )

W

0 N

X(2 )

x(3 )

W

2 N

W

0 N

X(6 )

x(4 )

W

0 N

X(1 )

x(5 )

W

1 N

W

0 N

X(5 )

x(6 )

W

2 N

W

0 N

X(3 )

x(7 )

W

3 N

W

2 N

W

0 N

X(7 )

图4.2.13 DIF―FFT运算流图(N=8)

课件

33

第4章 快速傅里叶变换(FFT)

x(0 )

x(1 )

x(2 )

x(3 )

x(4 )

W

0 N

x(5 )

W

0 N

x(6 )

W

0 N

x(7 )

W

0 N

X(0 )

W

0 N

X(4 )

W

0 N

X(2 )

W

0 N

W

2 N

X(6 )

X(1 )

W1N

X(5 )

W

2 N

X(3 )

W

2 N

W

3 N

X(7 )

图4.2.14 DIT―FFT的一种变形运算流图

课件

34

第4章 快速傅里叶变换(FFT)

x(0 )

x(1 )

x(2 )

x(3 )

x(4 )

W

0 N

x(5 )

W

0 N

x(6 )

W

0 N

x(7 )

W

0 N

W

0 N

W

0 N

W

2 N

W

2 N

W

0 N

W 1N

W

2 N

W

3 N

X(0 ) X(1 ) X(2 ) X(3 ) X(4 ) X(5 ) X(6 ) X(7 )

图4.2.15 DIT―FFT的一种变形运算流图

课件

35

第4章 快速傅里叶变换(FFT)

4.2.6 IDFT的高效算法

上述FFT算法流图也可以用于离散傅里叶逆变换

(Inverse Discrete Fourier Transform,简称IDFT)。比较

DFT和IDFT的运算公式:

N ?1
? X (k) ? DFT[x(n)] ? x(n)WNk
n?0

? x(n) ? IDFT[x(n)] ?

1 N ?1 N k?0

X (k )WN?kn

课件

36

第4章 快速傅里叶变换(FFT)

1N

X(0 )

x(0 )

1N

X(1 )

x(4 )

X(2 )

W

0 N

1N x(2 )

X(3 ) X(4 ) X(5 ) X(6 ) X(7 )

W

0 N

W

?1 N

W

?2 N

W

?3 N

W

?2 N

1N x(6 )

1N x(4 )

1N x(5 )

W

0 N

1N x(3 )

W

?2 N

1N x(7 )

图4.2.16 DIT―IFFT运算流图

课件

37

第4章 快速傅里叶变换(FFT)

X(0 ) X(1 ) X(2 ) X(3 ) X(4 ) X(5 ) X(6 ) X(7 )

12

12

12

12

1 2

W

0 N

1 2

W

?1 N

1 2

W

?2 N

1 2

W

?3 N

12

12

x(0 )

12

1 2

W

0 N

1 2

W

?2 N

12

1 2

W

0 N

12

1 2

W

0 N

x(4 ) x(2 ) x(6 )

x(1 )

12

12

1 2

W

0 N

1 2

W

?2 N

1 2

W

0 N

12

1 2

W

0 N

x(5 ) x(3 ) x(7 )

图4.2.17 DIT―IFFT运算流图(防止溢出)

课件

38

第4章 快速傅里叶变换(FFT)

如果希望直接调用FFT子程序计算IFFT,则可用下

面的方法:

由于

? x(n) ? 1 N ?1
N k?0

X (k )WN?kn

? x?(n) ? 1 N ?1
N k?0

X ?(k )WNkn

对上式两边同时取共轭,得

? x(n) ?

1

N ?1
[

N k?0

X ?(k )WNkn ]? ?

1 ?DFT [ X ?(k)]
N

??

课件

39

第4章 快速傅里叶变换(FFT)
4.3 进一步减少运算量的措施
4.3.1 多类蝶形单元运算 由DIT―FFT运算流图已得出结论,N=2M点FFT共
需要MN/2次复数乘法。 由 (4.2.12) 式 , 当 L=1 时 , 只 有 一 种 旋 转 因 子
W0N=1,所以,第一级不需要乘法运算。

课件

40

第4章 快速傅里叶变换(FFT)

综上所述,先除去第一、二两级后,所需复数乘法

次数应是

CM

(2)

?

N 2

(M

? 2)

从L=3至L=M共减少复数乘法次数为

(4.3.1)

? ? M
L?3

N 2L?1

?

M
2N
L?3

(1)L ? N ? 2 22

(4.3.2)

因此, DIT―FFT的复乘次数降至

CM (2)

?

N 2

(M

? 2)

?(N 2

? 2)

?

N 2

(M

? 3)

?2

(4.3.3)

课件

41

第4章 快速傅里叶变换(FFT)

2 (1 ? j)(x ? jy) ? 2 (x ? jy ? jx ? y)

2

2

? 2 [(x ? y) ? j(x ? y)] 2
def
? R ? jI

R ? 2 (x ? y) 2

I ? ? 2 (x ? y) ? 2 (y ? x)

2

2

课件

42

第4章 快速傅里叶变换(FFT)

从实数运算考虑,计算N=2M点DIT―FFT所需实数

乘法次数为

RM (2)

?

4[ N 2

(M

? 3) ? 2] ? ( N 2

? 2)

? N (2M ? 13) ? 10 2

(4.3.4)

课件

43

第4章 快速傅里叶变换(FFT)
4.3.2 旋转因子的生成 在FFT运算中,旋转因子WmN=cos(2πm/N)-
jsin(2πm/N),求正弦和余弦函数值的计算量是很大的。

课件

44

第4章 快速傅里叶变换(FFT)

4.3.3 实序列的FFT算法

设x(n)为N点实序列,取x(n)的偶数点和奇数点分

别作为新构造序列y(n)的实部和虚部,即

x1(n)

?

x(2n), x2(n)

?

x(2n

? 1), n

?

0,1, ? ? ?,

N 2

?1

y(n)

?

x1(n) ?

jx2(n), n

?

0,1, ? ? ?,

N 2

?1

对y(n)进行N/2点FFT,输出Y(k),则

X X

1(k ) 2 (k )

? ?

DFT[x1(n)] ? Yep (k) DFT [x2(n)] ? ? jYop

(k

)

?? ? ??

,

k

?

0,1, ? ? ?,

N 2

?1

根据DIT―FFT的思想及式(4.2.7)和(4.2.8),可得到

X

(k)

?

X1(k)

? WNk

X 2(k), k

?

0,1, ? ? ?

N 2

课件

45

第4章 快速傅里叶变换(FFT)
由于x(n)为实序列,所以X(k)具有共轭对称性, X(k)的另外N/2点的值为
X (N ? k) ? X ?(k),k ? 1, 2,???, N ?1 2

课件

46

第4章 快速傅里叶变换(FFT)
4.4 分裂基FFT算法

4.4.1 分裂基FFT算法原理

当n=pq,且p=N/4,q=4时,n可表示为

n

?

pn1

?

n0

?

N 4

n1

?

n0 ,

并有

N ?1

? X (k ) ? x(n)WNkn

n?0

0

?

n1

?

3, 0

?

n0

?

N 4

?1

? ? N / 4?1 3
?
n?0 n1?0

x(

N 4

n1

?

n )W k

(

N 4

n1

?n0

)

0N

课件

47

第4章 快速傅里叶变换(FFT)

? ? N / 4?1

3

?

W kn0 N

n0

n1

x(

N 4

n1

?

n0 )W4kn1

]

?N / 4?1
?
n0 ?0

[ x(n)W40

?

x(n0

?

N 4

)W4k

?

x(n0

?

N 2

)W42k

?

x(n0

?

3N 4

)W43kWN3k

]WNkn0

再将上式中的k表示为

k

?

4k1

? k0,0

?

k1

?

N 4

? 1, 0

?

k0

?

3

课件

48

第4章 快速傅里叶变换(FFT)

可得

X (k) ? X (4k1 ? k0 )

?N / 4?1
?
n0 ?0

[x(n0 ) ? x(n0 ?

N 4

)W (4k1?k0 4

)

?

x(n0

?

N 2

)W 81?2k0 4

?

x(n0

?

3N 4

)W ]W 3(4k1?k0 ) 4

(4k1?k0 )n0 N

?N / 4?1
?
n0 ?0

[x(n0 ) ? x((n0 ?

N 4

)W4k0

?

x(n0

?

N 2

)W42k0

?

x(n0

?

3N 4

)W43k0

]W (4k1?k0 )n0 N

对k0=0,1,2,3,并用k表示k1,用n表示n0,可以

写出

课件

49

第4章 快速傅里叶变换(FFT)

? ?
?

X

?

(4k )

?

N / 4?1
[x(n)
n?0

?

x(n

?

N 4

)

?

x(n

?

N 2

)

?

x(n

?

3N 4

)]WN4kn

? ?
?

X

(4k

?

? 1)

?

N / 4?1
[x(n)
n?0

?

jx(n

?

N 4

)?

x(n

?

N 2

)

?

jx(n

?

3N 4

)]WN4kn?n

? ?
?

X

?

(4k

?

2)

?

N / 4?1
[x(n)
n?0

?

x(n

?

N 4

)

?

x(n

?

N 2

)

?

x(n

?

3N 4

)]WN4kn?2n

? ?
? X (4k ?

? 3)

?

N / 4?1
[x(n) ?
n?0

jx(n ?

N)? 4

x(n ?

N)? 2

jx(n ?

3N 4

)]WN4kn?3n

? ???

0 ? k ? N ?1 4

(4.4.1)

课件

50

第4章 快速傅里叶变换(FFT)

? ?
?

X

(2k )

?

N

/ 2?1

?

n?0

[x(n) ? x(n ?

N 2

)]WN2kn

,

0

?

k

?

N 2

?1

? ?
? X (4k ?

? 1)

?

N / 4?1 ??[x(n) ? n?0 ?

jx(n ?

N)? 4

x(n

?

N)? 2

jx(n ?

3N 4

)]WNn

???WN4

kn

? ? ?

0 ? k ? N ?1 4

? ?
? X (4k ?

? 3)

?

N / 4?1 ??[x(n) ? n?0 ?

jx(n ?

N)? 4

x(n ?

N)? 2

jx(n ?

3N 4

)]WN3n

???WN4kn

? ? ??

0 ? k ? N ?1 4

(4.4.2)

课件

51

第4章 快速傅里叶变换(FFT)



? ?

x2

(

n)

?

? ?

x41

(

n)

? ?

x(n) ? x(n ? [x(n) ? jx(n

N ), 2 ?N
4

)

?

0?n? x(n ? N )
2

N 2
?

?1 jx(n

?

3N 4

)]WNn

?

? ?

x42

(n)

?

[x(n)

?

jx(n

?

N 4

)

?

x(n

?

N 2

)

?

jx(n

?

3N 4

)]WN3n

? ?

0 ? n ? N ?1

(4.4.3)

?

4

课件

52

第4章 快速傅里叶变换(FFT)
则(4.4.2)式可写成如下更简明的形式:

? ?
?

X

(2k )

?

N

/ 2?1

x2 (n)WN2kn ? DFT [x2(n)],

?

n?0

0 ? k ? N ?1 2

? ?
?

X

(4k

? 1)

?

N

/ 4?1

x41

(n)WN4kn ? DFT [x41(n)],

?

n?0

0 ? k ? N ?1 4

? ?

N / 4?1

? X (4k ? 3) ?

x42 (n)WN4kn ? DFT [x42 (n)],

?

n?0

0 ? k ? N ?1 4

(4.4.4)

课件

53

x(1 ) x??1? N ?? ? 4?



第4章 快速傅里叶变换(FFT)





x2(1 ) N点 2

x2(1 +N/4 )

DFT









x??1? N ??

? 2?

-1



x14 (1) WN1



N点 4
DFT



x??1 ? 3N ?? ? 4?





-1 -j

-1

x42 (1) WN3



N点 4 DFT



图4.4.1 分裂基第一次分解L形流图

课件

54

第4章 快速傅里叶变换(FFT)
例如,N=16,第一次抽选分解时,由式(4.4.3)得

x2(n)=x(n)+x(n+8),

0≤n≤7

x14(n)={[x(n)-x(n+8)]-j[x(n+4)-x(n+12)]}Wn16,

0≤n≤3

x24(n)={[x(n)-x(n+8)]+j[x(n+4)-x(n+12)]}W3n16, 0≤n≤3

把上式代入式(4.4.4),可得

X(2k)=DFT[x2(n)], X(4k+1)=DFT[x14(n)], X(4k+3)=DFT[x24(n)],

0≤k≤7 0≤k≤3 0≤k≤3

课件

55

第4章 快速傅里叶变换(FFT)

(a)

(b)

图4.4.2 分裂基FFT算法L形排列示意图与结构示意图

(a)分裂基FFT算法L形排列示意图;

(b)分裂基FFT算法运课算件流图结构示意图

56

x(0 ) x(1 ) x(2 ) x(3 ) x(4 ) x(5 ) x(6 ) x(7 ) x(8 ) x(9 ) x(1 0) x(1 1) x(1 2) x(1 3) x(1 4) x(1 5)

第4章 快速傅里叶变换(FFT)

x2(0 ) x2(1 ) x2(2 ) x2(3 ) x2(4 ) x2(5 ) x2(6 ) x2(7 )
-1 -1 -1 -1 -1 - j -1 - j -1 - j

N 2
(8 ) 点 DFT

WN0 WN1 WN2 WN3 -1 WN0 -1 WN3 -1 WN6

x14 (0) x14 (1) x14 (2) x14 (3) x42 (0) x42 (1) x42 (2) x42 (3)

N ?4 4
点 DFT
N ?4 4
点 DFT

X(0 ) X(2 ) X(4 ) X(6 ) X(8 ) X(1 0) X(1 2) X(1 4) X(1 ) X(5 ) X(9 ) X(1 3) X(3 ) X(7 ) X(1 1) X(1 5)

X(2k ) X(4k+ 1) X(4k+ 3)

图4.4.3 16点分裂基第一次分解L形流图(图中省去箭头)

课件

57

第4章 快速傅里叶变换(FFT)

第二次分解:

先对图4.4.3中N/2点DFT进行分解。

令X1(l)=X(2l),则有 X1(2l)=DFT[y2(n)], X1(4l+1)=DFT[y14(n)], X1(4l+3)=DFT[y24(n)],

0≤l≤3 0≤l≤1 0≤l≤1

课件

58

其中

第4章 快速傅里叶变换(FFT)

y2(n)=x2(n)+x2(n+4),

0≤n≤3

y14(n)={[x2(n)-x2(n+4)]-[x2(n+2)x(n+6)]}Wn8,n=0,1

y24(n)={[x2(n)-x2(n+4)]+j[x2(n+2)x2(n+6)]}W3n8,n=0,1

课件

59

x2(0 ) x2(1 ) x2(2 ) x2(3 ) x2(4 ) x2(5 ) x2(6 ) x2(7 )

第4章 快速傅里叶变换(FFT)

y2(0 ) y2(1 ) y2(2 ) y2(3 )

N4
(4 ) 点 DFT

-1 -1 -1 - j -1 - j

y14 (0)

y14 (1)

WN1 2 y42 (0) - 1

-1

y42 (1)

- 1 WN3 2

-1

X1(0 ) =X(0 ) X1(2 ) =X(4 ) X1(4 ) =X(8 ) X1(6 ) =X(1 2) X1(1 ) =X(2 ) X1(5 ) =X(1 0) X1(3 ) =X(6 ) X1(7 ) =X(1 4)

X1(2l)
X1(4l+ 1) X1(4l+ 3)

图4.4.4 图4.4.4中N/2点DFT的分解L形流图

课件

60

第4章 快速傅里叶变换(FFT)

v(0 )

V(0 )

v(1 )

- 1 V(2 )

v(2 )

-1

V(1 )

v(3 )

-1 - j

- 1 V(3 )

图4.4.5 4点分裂基L形运算流图

课件

61

第4章 快速傅里叶变换(FFT)

x(0 )

X(0 )

x(1 )

-1

X(8 )

x(2 )

-1

X(4 )

x(3 )

-1

- j -1

X(1 2)

x(4 )

-1

X(2 )

x(5 ) x(6 )

-1

-1

-j

-1

WN 2

-1

X(1 0) X(6 )

x(7 )

x(8 )

-1

-1

-j

-1

WN 6

-1

X(1 4) X(1 )

x(9 ) x(1 0) x(1 1) x(1 2)

-1 -1 -1 -1

-j

WN1

WN2

-1

WN3

-1

-1

-1

-j

-1

X(9 ) X(5 ) X(1 3) X(3 )

x(1 3) x(1 4) x(1 5)

-1 -1 -1

-j -j -j

-1

WN3

-1

WN6

-1

-1

WN9

-1

-1

-j

-1

X(1 1) X(7 ) X(1 5)

图4.4.6 16点分裂基FFT运算流图

课件

62

第4章 快速傅里叶变换(FFT)
4.4.2 分裂基FFT算法的运算量
设 第 j 级 有 lj 个 L 形 , j=1,2,…,M-1,M=log2N , 则 有 l1=N/4。由图4.4.2(b)可见,第j-1列中的L形包含了第j 列中的一部分结点的计算,即空白部分,所占结点数 刚好等于第j-1列中所有L形对应结点的一半,所以第j 列L形个数就减少l j-1/2个,即

课件

63

第4章 快速傅里叶变换(FFT)

lj

?

N 4

?

l j?1 2

l1

?

N 4

l2

?

N 4

?

l1 2

?

N 4

(1 ?

1) 2

l3

?

N 4

?

l2 2

?

N 4

(1 ?

1 2

?

1) 4

? l j

?

N 4

j ?1 i?0

(? 1 )i ? N (1 ? 1 ? 1 ) j ] 2 4 24

课件

64

第4章 快速傅里叶变换(FFT)

由于每个L形有两次复(数)乘运算,所以全部复

乘次数为

? CM

M ?1
? 2 lj
j ?1

?

N 3

[M

?

2 3

?

2 (? 1)M ] 32

?

1 3

N

log2

N

?

2 9

N

? (?1)M

2 9

(4.4.5)

课件

65

第4章 快速傅里叶变换(FFT)
4.5 离散哈特莱变换(DHT)

4.5.1 离散哈特莱变换定义

设x(n),n=0,1,…,N-1,为一实序列,其DHT定义为

?N ?1
X H (k) ? DHT[x(n)] ?
n?0

x(n) cos( 2?
N

kn), k ? 0,1,???, N ?1

式中,cas(α)=cosα+sinα。其逆变换(IDHT)为

? x(n)

?

IDHT [ X H

(k )]

?

1 N

N ?1 k ?0

XH

(k) cos( 2?
N

kn), n

?

0,1, ? ? ?,

N

?1

(4.5.3)

课件

66

第4章 快速傅里叶变换(FFT)

逆变换证明如下:

?N?1 cos( 2? kn) cos( 2? k? )

k ?0

N

N

?N ?1
?

[cos( 2?

kn) ? sin( 2?

kn)][cos( 2?

k? ) ? sin( 2?

k? )]

k ?0

N

N

N

N

?N ?1
?

[cos( 2?

kn) cos( 2?

k? ) ? sin( 2?

kn)sin( 2?

k? )

k ?0

N

N

N

N

? cos( 2? kn)sin( 2? k? ) ? sin( 2? kn) cos( 2? k? )]

N

N

N

N

?N ?1
?

[cos 2?

k(n ?? ) ? sin 2?

k(n ?? )]

k ?0

N

N

?

?? N ???0,

,

n ?? n ??

课件

(4.5.4)
67

第4章 快速傅里叶变换(FFT)

将式(4.5.2)代入式(4.5.3)得

? ? 1 N?1 N?1 x(? ) cos( 2? k? ) cos( 2? kn)

N k?0 ? ?0

N

N

? ? ?

1 N ?1

N ?1
x(? )

cos( 2? kn) cos( 2? k? )

N k?0

? ?0

N

N

? ? 1 N ?1 N k?0

x(?

)

?? N ???0,

,

? ?0 ? ?0

课件

68

第4章 快速傅里叶变换(FFT)

4.5.2 DHT与DFT之间的关系

为了便于比较,重写DFT如下:

(4.5.5)

? ? N?1
X (k) ? DFT[x(n)] ?

? j 2? kn
x(n)e N

N ?1
?

x(n)[cos( 2?

kn) ?

j sin( 2? kn)]

n?0

n?0

N

N

? ? x(n) ?

1

N ?1

j 2? kn
X (k)e N ?

1

N ?1

X (k)[cos( 2? kn) ?

j sin( 2? kn)]

N k?0

N k?0

N

N

(4.5.6)

容易看出,DHT的核函数cos(2? kn) ? cos( 2? kn) ? sin( 2? kn)

DFT的核函数

j 2? kn
eN

?

cos( 2?

N kn) ?

j( 2?

kn)

N

N

N

N

的实部与虚部之和。

课件

69

第4章 快速傅里叶变换(FFT)

将XH(k)分解为奇对称分量XHo(k)与偶对称分量 XHe(k)之和

X H (k ) ? X He (k ) ? X Ho (k )

X

He (k )

?

1 2

[X

H

(k)

?

X

H

(N

?

k )]

(4.5.7) (4.5.8)

X

Ho (k )

?

1 2

[X

H

(k)

?

X

H

(N

?

k )]

(4.5.9)

由DHT定义有

?N ?1
X He (k ) ?
n?0

x(n) cos( 2?
N

kn)

?N ?1
X Ho (k ) ?
n?0

x(n)sin( 2?
N

kn)

(4.5.10a) (4.5.10b)

课件

70

所以,x(n)的DFT可表示为

第4章 快速傅里叶变换(FFT)

X (k) ? X He (k) ? jX Ho (k)
同理,x(n)的DHT可表示为

(4.5.11)

X H (k) ? He(k) ? Im[ X (k)]

(4.5.12)

因此,已知x(n)的DHT,则DFT可用下式求得:

X (k)

?

1 2

[

X

H

(k

)

?

XH (N

? k)] ?

1 2

j[ X H (k)

?

X H (N

? k)]

(4.5.13)

课件

71

第4章 快速傅里叶变换(FFT)
4.5.3 DHT的主要优点 (1)DHT是实值变换,在对实信号或实数据进行谱
分析时避免了复数运算,从而提高了运算效率,相应 的硬件也更简单、更经济;
(2)DHT的正、反变换(除因子1/N外)具有相同的形 式,因而,实现DHT的硬件或软件既能进行DHT,也 能进行IDHT;
(3)DHT与DFT间的关系简单,容易实现两种谱之 间的相互转换。

课件

72

第4章 快速傅里叶变换(FFT)
4.5.4 DHT的性质 1. 线性性质 x1 ? X1H (k), x2 (n) ? X 2H (k) ax1(n) ? bx2(n) ? aX1H (k) ? bX 2H (k ) (4.5.14) 2. x(N-n)的DHT

x(n) ? X H (k), x(N ? n) ? X H (N ? n)

?N ?1
XH(N ? k) ?
n?0

x(n)[cos( 2?
N

kn) ? sin( 2?
N

kn)], k ? 0,1,???, N ?1

(4.5.15)

其中,当k=0时,XH(N-k)=XH(N)=XH(0)。

课件

73

第4章 快速傅里叶变换(FFT)

证明 由DHT定义

?N ?1
DFT[x(N ? n)] ?

x(N ? n) cos( 2? kn)

n?0

N

?N ?1
?

x(n) cos( 2?

k(N ? n))

n?0

N



?N ?1
?

x(n)[cos( 2?

kn) ? sin( 2?

kn)]

n?0

N

N

?N ?1
XH(N ? k) ?
n?0

x(n) cos( 2?
N

(N ? k)n)

?N ?1
?

x(n)[cos( 2? kn) ? sin( 2? kn)] ? DFT[x(N ? n)]

n?0

N

N

课件

74

第4章 快速傅里叶变换(FFT)

3. 循环移位性质

x((n

?

n0 ))N

RN

(n)

?

XH

(k) cos( 2?
N

kn0 )

?

H(N

?

k)sin( 2?
N

kn0 )

x((n

?

n0 ))N

RN (n)

?

X

H

(k

)

cos(

2?
N

kn0 )

?

H(N

?

k)sin( 2?
N

kn0 )

证明 由DHT定义有

(4.5.16) (4.5.17)

DHT[x(n ? no )N RN (n)]

?N ?1
?
n?0

x((n

?

no ))N

cos( 2?
N

kn)

?N ?1
?
n?0

x(n) cos( 2?
N

k(n

?

no ))

?N ?1
?
n?0

x(n)[cos( 2?
N

kn) cos( 2?
N

kno )

? sin( 2?
N

kn)sin( 2?
N

kno )

? sin( 2?
N

kn) cos( 2?
N

kno

) ? cos(
课件

2?
N

kn)sin( 2?
N

kno )]

75

第4章 快速傅里叶变换(FFT)

?N ?1
?
n?0

x(n)[cos( 2?
N

kn) ? sin( 2?
N

kn)]cos( 2?
N

kno )

?N ?1
?
n?0

x(n)[cos( 2? kn) ? sin( 2? kn)]sin( 2?

N

N

N

kno )

?

XH

(k) cos( 2?
N

kno )

?

XH

(N

?

k)sin( 2?
N

kno )

课件

76

第4章 快速傅里叶变换(FFT)
4. 奇偶性 奇对称序列和偶对称序列的DHT仍然是奇对称序 列或偶对称序列,即DHT不改变序列的奇偶性。 5.循环卷积定理

x1(n) ? X1H (k ), x2 (n) ? X 2H (k )

(4.5.18)

x1(n) x2 (n) ? X 2H (k ) X1He (k ) ? X 2H (N ? k ) X1Ho (k )

x1(n) x2 (n) ? X1H (k ) X 2He (k ) ? X1H ( N ? k ) X 2Ho (k )

(4.5.19)

课件

77

第4章 快速傅里叶变换(FFT)
证明 下面利用DFT的循环卷积定理和DHT与DFT 之间的关系来证明
DFT[x1(n) x2(n)] ? X1(k) X 2(k) 其 中 , X1(k)=DFT [ x1(n) ] ,X2(k)=DFT [ x2(n) ] , 根据DHT与DFT之间的关系,则有

X1(k) ? X1He (k) ? jX1Ho (k)

X 2 (k) ? X 2He (k) ? jX 2Ho (k)

?

1 2

[

X

2

H

(k

)

?

X2H (N

? k)] ?

1 2

j[ X 2H (N

? k)]

课件

78

第4章 快速傅里叶变换(FFT)

将上面两式代入式(4.5.20)并整理后,得

X (k)

?

1 2

X 2H (k )[ X1He (k ) ?

X1Ho (k )

?

jX1He (k ) ?

jX1Ho (k )]

1 ? 2 X 2H (N ? k )[ X1He (k ) ? X1Ho (k ) ? jX1He (k ) ? jX1Ho (k )]

X H (k) ? DFT[x1(n) x2(n)]

? Re[ X (k)] ? Im[ X (k)]

? X 2H (k ) X1He (k ) ? X 2H (N ? k ) X1Ho (k )
所以式(4.5.18)成立。同理可证明式(4.5.19)亦成立。 当x1(n)或x2(n)是偶对称序列时,则由DHT的奇偶性有

x1(n) x2 (n) ? X H (k ) ? X1H (k ) X 2H (k )
课件

(4.5.21)
79

第4章 快速傅里叶变换(FFT)

4.5.5 DHT的快速算法(FHT)

1.基2DIT―FHT算法及运算流图

仿照快速DFT的分解方法,可通过时域抽取或频域 抽取的方式实现快速DHT。

x(n)的N=2M点DHT如下式:

?N ?1
X H (k) ?
n?0

x(n) cos( 2?
N

kn),

0 ? k ? N ?1

对x(n)进行奇偶抽取

(4.5.22)

x0 (r ) x1(r)

? ?

x(2r x(2r

) ?

1)

? ? ?

,

0 ? r ? N ?1 2

(4.5.23)

N ?1

N ?1

? ? 2
X H (k) ?
r?0

x(2r) cos( 2? 2rk) ? 2

N

课件 r ?0

x(2r ? 1) cos( 2? (2r ? 1)k)
N 80

第4章 快速傅里叶变换(FFT)
与DFT的时域抽取分解比较,cos( 2? k(2r ?1))
不是 一个指数函数,所以处理要比W(2rN+1)kN麻烦一
些。 根据三角公式有

cos(? ? ? ) ? cos? ? cos ? ? cos(?? )sin ?

(4.5.24)

? ?1

? ?1

? ? 2
X H (k) ?
r?0

x0(r) cos(

2?
N /2

rk )

?

cos( 2?
N

2
k)
r?0

x1(

r

)

cos(

2?
N /2

rk

)

? ?1

? ?

sin( 2?

2
k)

N r?0

x1(r)

cos(?

2?
N /2

rk

)

(4.5.25)

课件

81

第4章 快速傅里叶变换(FFT)

令X0H(k)=DHT[x0(n)],X1H(k)=DHT[x1(n)],并 考虑DHT的周期性,(4.5.25)式可写成

X H (k)

?

X0H (k)

? cos( 2?
N

k

)

X

1H

(k

)

?

sin(

2?
N

k

)

X1H

(

N 2

? k)

为了使以下推导中公式简明,记

C(k)=cos (2π/N)k ,S(k)=sin (2π/N)/k 。将式(4.5.26) 中的k分别取k,N/2+k,N/2-k和N-k四个值,并考虑 X0H(k)和X1H(k)以N/2为周期,得到

课件

82

第4章 快速傅里叶变换(FFT)

X H (k)

N XH( 2

X

H

(

N 2

?

X 0H (k ) ? [C(k ) X1H (k ) ?

N S(k)X1H ( 2

? k )]

N ? k ) ? X 0H (k ) ? [C(k ) X1H (k ) ? S(k ) X1H ( 2 ? k )]

? ? ? ?
?0 ? k ?

? k)

?

X

0

H

(

N 2

?

k

)

?

[S

(k

)

X

1H

(

k

)

?

C

(k

)

X

1H

(

N 2

?

?

k

)]? ?

N

?8

N 4

X H (N

?

k)

?

X

0

H

(

N 2

?

k) ? [S(k)X1H (k)

?

C

(k

)

X

1

(

N 2

? k)]

?

? ?

(4.5.27)

课件

83

第4章 快速傅里叶变换(FFT)
当k=0时,式(4.5.27)中有重复,可单独写成

?? X H (0) ? X0H (0) ? X1H (0)

? ??

X

H

(

N 2

)

?

X0H

(0)

?

X1H

(0)

(4.5.28)

同理,在k=N/4时有

? ??

X

H

(

N 4

)

?

X0H

(

N 4

)

?

X

1H

(

N 4

)

?

? ??

X

H

( 3N 4

)

?

X0H

(

N 4

)

?

X1H

(

N 4

)

(4.5.29)

课件

84

x(0 ) x(2 )
x(N- 2) x(1 ) x(3 )
x(N- 1)





第4章 快速傅里叶变换(FFT)

N2 点 DFT

X0H(k ) X0H(N/2 -k)

N2 点 DFT

X1H(k) c(k)

s(k )

X1H(N/2 -k)

s(k )

- c(k)

XH(k )
XH(N/2 -k)
XH(N/2 +k) -1
XH(N- k ) -1

图4.5.1 基2DIT-FHT原理和哈特莱碟形

课件

85

第4章 快速傅里叶变换(FFT)

x0(0 )=x(0 )

x0(2 )=x(2 )

-1

x1(0 )=x(1 )

-1

x1(1 )=x(3 )

-1

-1

图4.5.2 4点DFHT蝶形图
课件

XH(0 ) XH(1 ) XH(2 ) XH(3 )
86

x(0 )

x(8 )

-1

x(4 )

x(1 2)

-1

x(2 )

x(1 0)

-1

x(6 )

x(1 4)

-1

x(1 )

x(9 )

-1

x(5 )

x(1 3)

-1

x(3 )

x(1 1)

-1

x(7 )

x(1 5)

-1

第4章 快速傅里叶变换(FFT)

-1

-1

-1

c2 s2

-1

-1

s2

-1

-1

- c2

-1

-1

-1

-1

c2 s2

-1

-1

s2

-1

-1

- c2

-1

-1

c1 s1

-1

c2 s2

-1

c3 s3

-1

s3

-1

- c3 s2

-1

- c2 s1 - 1

- c1

-1

图4.5.3 16点基2DIT―FHT流图
课件

X(0 ) X(1 ) X(2 ) X(3 ) X(4 ) X(5 ) X(6 ) X(7 ) X(8 ) X(9 ) X(1 0) X(1 1) X(1 2) X(1 3) X(1 4) X(1 5)
87

第4章 快速傅里叶变换(FFT)

2. 基2DIT―FHT的运算量

观 察 图 4.5.3 可 知 , 运 算 流 图 中 都 是 实 数 运 算 。 N=2M点FHT流图共分为M级。用L表示流图自右向左 的蝶形级数。第L级乘法次数为2L(N/2L-2),但最后二 级无乘法运算,所以,总的乘法次数MH为

?M ?2
MH ?
L?1

2L

(

1 2L

? 2)

?

NM

? 3N

?

4

同理可求得总的加法次数AH为

AH

?

3 2

NM

?

3 2

N

?2

(4.5.30) (4.5.31)

课件

88

第4章 快速傅里叶变换(FFT)
4.5.6 实信号的快速循环卷积
用DIT―FFT计算两个实信号x1(n)和x2(n)的循环卷 积时,最直接的方法是将信号的虚部都置为零,再按 复序列用FFT计算。显然这样做是很浪费的。现在我们 可用基2DIT―FHT直接进行实正交变换来处理实信号 的循环卷积问题。

FHT
x1(n) ? X1H (k ) ?
FHT
x2 (n) ? X 2H (k ) ?

计算式 (4.5.18)

IFHT
? YH (k) ? y(n) ? x1(n) x2(n)

课件

89