当前位置:首页 >> 信息与通信 >>

fft蝶形算法


第4章 快速傅立叶变换
? 问题的提出

? 解决问题的思路与方法
? 基2时间抽取FFT算法

? 基2时间抽取FFT算法的计算复杂度
? 基2时间抽取FFT算法流图规律

? 基2频率抽取FFT算法
? FFT算法的实际应用

问题的提出
4点序

列{2,3,3,2} DFT的计算复杂度

X [m] ? ?
k ?0

N ?1

km x[k ]WN ,

m ? 0,1,? N ? 1

0 0 0 0 X [0] ? 2WN ? 3WN ? 3WN ? 2WN ? 10 0 1 2 3 X [1] ? 2WN ? 3WN ? 3WN ? 2WN ? ?1 ? j 0 2 4 6 X [2] ? 2WN ? 3WN ? 3WN ? 2WN ?0 0 3 6 9 X [3] ? 2WN ? 3WN ? 3WN ? 2WN ? ?1 ? j

如 何 提 高 DFT 的 运 算 效 率

复数加法 N(N-1)

复数乘法 N 2

?

解决问题的思路
1. 将长序列DFT分解为短序列的DFT
km 2. 利用旋转因子 WN 的周期性、对称性、可约性。

旋转因子
1)周期性

km WN

的性质

(k ? N )m k ( m? N ) km WN ? WN ? WN

2) 对称性
WN
mk ? N 2

?

mk ?W N

?

km ? WN

?

?mk ? WN

3)可约性
mk WN

mk nmk WN ? WnN

mk / n ? WN / n ,

N / n为整数

解决问题的方法

将时域序列逐次分解为一组子序列,利用旋转因子 的特性,由子序列的DFT来实现整个序列的DFT。

基2时间抽取(Decimation in time)FFT算法
? x[2r ] N x[k ] ? ? r ? 0,1,? ? 1 2 ? x[2r ? 1]

基2频率抽取(Decimation in frequency)FFT算法
? X [2m] X [m] ? ? ? X [2m ? 1]

基2时间抽取FFT算法流图

N=2

x[k]={x[0], x[1]}

X [0] ? x[0] ? W20 x[1]
1 X [1] ? x[0] ? W2 x[1] ? x[0] ? W20 x[1]

x[0] x[1] W20 -1

X [0] X [1]

X [m] ? X1[m] ? W4m X 2 [m], m ? 0,1
m 算法流图 4 点基 时间抽取 FFT X[ m ? 2]2 ? X1[m] ? W 4 X 2 [m], m ? 0,1

x[0] x[2] x[1] x[3]
0 W2

X1[0]

X [0]

W20

2点DFT ?1

X1[1]
X2[0]

X [1]

W40
?1

X [2] X [3]

2点DFT ?1

X2[1]

W41
?1

4点基2时间抽取FFT算法流图

x[0] x[2] x[1] x[3]
W40 W40

X1[0] X1[1] X2[0] X2[1]
W40 W41

X[0] X[1] X[2]

?1

?1 ?1

?1

X[3]

X [m] ? X1[m] ? W8m X 2 [m], m ? 0,1,2,3 8点基2时间抽取 mFFT算法流图 X [m ? 4] ? X1[m] ? W8 X 2 [m], m ? 0,1,2,3
x[0]
X1[0] X1[1]

X [0] X [1] X [2] X [3]
?1 ?1 ?1 ?1

x[2]
x[4] x[6] x[1] x[3] x[5] x[7]

4点DFT

X1[2] X1[3]

X2[0] W80
1 W X2[1] 8

X [4] X [5]

4点DFT

X2[2] W82

X [6]
X [7]

X2[3] W83

8点基2时间抽取FFT算法流图
x x[0] [0]
[0] XX [0] 1111

X1[0] X1[1]
2 1 ?1

x[2] [4]
x[4] [2] x

W80 W80 W80 W80

2点DFT

X [0] X [1] X [2] X [3]
?1 ?1 ?1 ?1

?1
2点DFT

[1] XX [1] 1111
0 0 4 点 DFT W W [0] 8 4 XX [0] 1212

X1[2] X1[3]

x[6] [6]
x[1] [1] x
x x[3] [5] x x[5] [3]

?1
2点DFT

W W [1] XX [1] 8 4 1212
[0] XX [0] 21 21 [1] XX [1] 21 21

?1

X2[0] W80
1 W X2[1] 8

X [4] X [5]

?1

4点DFT

0 0 W [0] W XX [0] 8 4 22 22

x[7] [7] x

2点DFT XX [1] W W 22[1] 8 4 22 ?1 ?1

2 1 ?1

X2[2] W82

X [6]
X [7]

X2[3] W83

基2时间抽取FFT算法
第一级
x[0] x[4] x[2] x[6] x[1] x[5] x[3] x[7]
W80 W80 W80 W80

第二级

第三级
X[0]

?1

X[1]
W80 W82

?1 ?1
W80 W81

X[2] X[3] ?1 ?1 ?1 ?1 X[0] X[1] X[2] X[3]

?1

?1

W80 W82

?1 ?1

W82 W83

?1

算法的计算复杂度

复乘次数
复乘次数

N log 2 N 2

N2

N log2 N 2

N

基2时间抽取FFT算法流图
第一级
x[0] x[4] x[2] x[6] x[1] x[5] x[3] x[7]
W80 W80 W80 W80

第二级

第三级
X[0]

?1

X[1]
W80 W82

?1 ?1
W80 W81

X[2] X[3] ?1 ?1 ?1 ?1 X[0] X[1] X[2] X[3]

?1

?1

W80 W82

?1 ?1

W82 W83

?1

P W FFT算法流图旋转因子 N 规律

0 W 第一级的蝶形系数均为 N ,蝶形节点的距离为1。

0 N/4 第二级的蝶形系数为 WN ,蝶形节点的距离为2。 , WN

0 N /8 2N / 8 3N / 8 第三级的蝶形系数为 WN ,蝶形 , WN , WN , WN 节点的距离为4。

( N / 2?1) 0 1 , WN , ?, WN 第M级 的蝶形系数为 WN ,蝶形 节点的距离为N /2。

k0

k1
0

k2
0 1 x[000] x[100] x[010]

倒序

0

x[k2 k10]
1

0 1

x[110]
x[001]

x[k2 k1k0] 0

0 1 1 x[k2 k11] 1 1 0

x[101]
x[011]

x[111]

基2频率抽取FFT算法
X [m ] ? ?
N / 2? 1

?
k ?0

x[k ]W

mk N

?

N ?1 k?N / 2 N / 2? 1

?

x[k ]W

mk N

N / 2? 1 k ?0 N / 2? 1

?

mk x[k ]WN ?

?
k ?0

m( k ? N / 2) x[k ? N / 2]WN

?

? ?x[k ] ? (?1)
k ?0 N / 2? 1 k ?0 N / 2? 1 k ?0

m

mk x[k ? N / 2] WN

?

X [2r ] ?

rk ? ? x [ k ] ? x [ k ? N / 2 ] W ? N /2 k rk ? ? x [ k ] ? x [ k ? N / 2 ] W W ? N N /2

X [2r ? 1] ?

X [2r ] ?

N / 2? 1 k ?0

rk ? ? x [ k ] ? x [ k ? N / 2 ] W ? N /2 N / 2? 1 k ?0

r ? 0,1? N / 2 ? 1

X [2r ? 1] ?
x[0]

k rk ? ? x [ k ] ? x [ k ? N / 2 ] W W ? N N /2

X[0]

x[1] x[2]
x[3] x[4]
0 WN

4点 DFT

X[2]

X[4]
X[6]

-1 -1 -1 -1

X[1]

x[5] x[6]
x[7]

W

1 N

2 WN

4点 DFT

X[3] X[5] X[7]

W

3 N

x[0] x[1] x[2] x[3] x[4]
-1
0 WN
0 WN

2点
DFT
-1

X[0]

X[4]
X[2] X[6] X[1] X[5] X[3]

W
-1

2 N

2点 DFT 2点 DFT

x[5]
x[6] x[7]

-1
-1

W W

1 N 2 N 3 N
0 WN

-1

W

-1 -1

W

2 N

2点 DFT

X[7]

x[0] x[1] x[2]
-1 -1 -1 -1 -1 -1
0 WN
0 WN 2 WN

X[0]

W
-1

0 N

X[4] X[2]

x[3]
x[4] x[5] x[6] x[7]

-1

0 WN

X[6]
X[1]

W W

1 N
0 WN

2 WN
3 N

-1

0 WN

X[5] X[3]

-1
-1

W

2 N

-1

0 WN

X[7]

FFT算法应用

? 利用N点复序列的FFT计算两个N点实序列FFT ? 利用N点复序列的FFT,计算2N点序列的FFT ? 利用FFT计算IFFT

利用N点复序列的FFT算法计算

两个N点实序列FFT
x1[k], x2[k]是实序列, 将其构成复序列y[k]=x1[k]+j x2[k] DFT{x1[k]+j x2[k]}=YR [m]+jYI [m]
DFT?x1[k ] ? jx2 [k ]? ? YR [(?m) N ] ? jYI [(?m) N ]
1 DFT ?x1[k ]? ? ?YR [m] ? YR [( ?m) N ] ? j (YI [m] ? YI [( ?m) N ])? 2

DFT?x1[k ]? ? ? DFT?x2 [k ]? ? ?

1 ?YR [m] ? YR [(?m) N ] ? j (YI [m] ? YI [(?m) N ])? DFT?x2 [k ]? ? 2j

利用N点复序列的FFT,计算2N点序列的FFT

y[k]是一个长度为2N的序列
? x1[k ] ? y[2k ] y[k ] ? ? k ? 0,1,? N ? 1 ? x2 [k ] ? y[2k ? 1]

Y [m] ? X 1[m] ? W2m N X 2 [m] Y [m ? N ] ? X 1[m] ? W2m N X 2 [m]

m ? 0,1,?, N ? 1

问题:如何利用N点FFT,计算4N点序列的FFT?

利用FFT实现IFFT
X [m] ? DFT?x[k ]? ?
N ?1

? k ?0

mk x[k ]WN

1 x[k ] ? IDFT?X [m]? ? N
? N ?1

? m ?0

N ?1

?mk X [m]WN
?

1 ? mk ? x[k ] ? ? X [m]WN ? ? ? ? N ? m ?0 ?

步骤:A) 将X [m]取共轭

B) 用FFT流图计算DFT{X [m]}
C) 对B)中结果取共轭并除以N

?


相关文章:
FFT算法设计与实现
因此我们就可以构造循环来实现蝶形运算。 2、 FFT 算法流程图 倒位序流程图: 输入数组指针 a,长度 n n=0? Y N i=0 i<n? N Y i%2==0? N temp[...
快速傅里叶变换_蝶形运算_按时间抽取基2-fft算法_MATLA...
快速傅里叶变换_蝶形运算_按时间抽取基2-fft算法_MATLAB代码_计算机软件及应用_IT/计算机_专业资料。function y=MyFFT_TB(x,n) %MYFFT_TB:My Fast Fourier ...
三种C语言实现的FFT例程
//FFT 运算核,使用蝶形运算完成 FFT 运算 //计算 l 的值,即计算蝶形级数 // 控制蝶形结级数 //m 表示第 m 级蝶形,l 为蝶形级总数 //le 蝶形结距离...
64点FFT算法实现
64 点 FFT 硬件算法实现本文对 FFT 算法中的截位问题进行分析,并给出了硬件实现的基本流程。 1.截位分析以前的 FFT 算法中奇数级 ( 1,3,5 ) 蝶形运算...
FFT算法与采样定理
例如 8点的时域抽取FFT算法,需要做三次蝶形运算。 实验结论 蝶形运算示意图 8点的时域抽取FFT算法,需要做三次蝶形运算。 由图可以看到,再做变换之前,先做...
范例_FFT算法程序及分析
L 点序列,依次类推,可以一直分解到只有两点的 DFT 与 FFT 运算量的比较: L 由按时间抽选法 FFT 的流图可见,当 N=2 时,共有 L 级蝶形,每级都由 N/2...
fft算法代码注释及流程框图
基2 的 DIT 蝶形算法源代码及注释如下: /***FFT***/ 节约空间 #include <stdio.h> #include <math.h> #include <stdlib.h> #define N typedef struct...
FFT原理与实现
N 点基-2 FFT 算法的计算量 从图 3 可以看到 N 点 DFT 的 FFT 变换可以转为 log2(N)级级联的蝶形运算,每 一级均包含有 N/2 次蝶形计算。而每一个...
基-2FFT算法的软件实现
运算流图 图 2.3 N=8 点 DIT-FFT运算流图 (2)算法效率 由图 2.3 可见,N=2M 时,DIT-FFT 运算流图由 M 级蝶形构成,每级有 N/2 个蝶形。...
FFT算法分析
按照抽取方式的 不同可分为 DIT-FFT(按时间抽取)和 DIF-FFT(按频率抽取)算法。按照蝶形运算的构成 不同可分为基 2、基 4、基 8 以及任意因子(2n,n 为...
更多相关标签: