没有合适的资源?快使用搜索试试~ 我知道了~
FFT的计算机实现.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 186 浏览量
2022-07-14
04:52:23
上传
评论
收藏 251KB PDF 举报
温馨提示
试读
11页
FFT的计算机实现.pdf
资源推荐
资源详情
资源评论
快速傅立叶变换( FFT )的计算机实现
邓凯 电气 0706
1.FFT 运算的原理
DFT 运算过程中如果有限长序列的长度很长时,即 N 很大时,在运算过程
中所做的乘法和加法运算将很多。 即便是采用高速的计算机进行运算, 也很难达
到信息实时处理的要求。由库利、图基等科学家提出的快速傅里叶变换 FFT 算
法大大减少了运算过程中的乘法和加法次数, 适合信息处理对实时性的要求, 从
而得到广泛应用。
按时间抽取的 FFT 算法的基本思想是将输入的有限长序列首先分成奇数序
列和偶数序列,分别计算出奇、偶序列的 DFT,然后根据 DFT 的周期性和对称
性质,将其化简,接着将已分成的奇、偶序列再次分别划分成奇、偶序列,即前
面的奇序列按其长度再划分成奇数序列和偶数序列; 前面的偶序列按其长度再划
分成奇数序列和偶数序列。分别计算其 DFT 后,再按上述方法进行化简。如此
反复,直至被划分成的奇、偶序列长度为 1 为止。
1.1 基二 FFT 算法原理
若设 X(k)=DFT[x(n)] ,且 0≤n, k≤N-1,N 为偶数(如果 N 为奇数,则添上
一个零值点使长度 N 为偶数)。把它分为奇序列和偶序列:
2
1
i) x((i) x )i x((i) x 12
2
)1
2
0(
N
i
又
( i ) ]D F T [ x( k )( i ) ] XD F T [ x( k )X
2211
)1
2
0(
N
i
则有
k
k
N
N
WkXkX
N
kX
WkXkXkX
)()()
2
(
)()()(
21
21
)1
2
0(
N
i
其中,
][
1
kX ][
2
kX
分别是
][
1
ix
和
][
2
ix
的
2
N
点 DFT
即要求
][kX
的值仅仅只需要求
][
1
kX ][
2
kX
在
)1
2
0(
N
i 部分的值即可。
这样,我们就可以将
][kX
n
一直分为奇序列和偶序列来求其值,直到奇偶序列长
度为 1 为止。
1.2 蝶形图
对于 FFT 运算,我们通常用蝶形图来表示
比如
k
k
N
N
WkXkX
N
kX
WkXkXkX
)()()
2
(
)()()(
21
21
我们表示为
][
1
kX
)(
2
kX
k
N
W
k
N
WkXkXkX )()()(
21
k
N
WkXkX
N
kX )()()
2
(
21
图1.21
下面以 N=8 为例,运用 FFT 算法原理计算 DFT,如图 1.22、图 1.23、图
1.24 所示。
N/2 点
DFT
N/2 点
DFT
-1
-1
-1
-1
X(1)
X(0)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
8
W
0
8
W
3
8
W
2
8
W
x1(0)=x(0)
x1(1)=x(2)
x1(2)=x(4)
x1(3)=x(6)
x2(0)=x(1)
x2(1)=x(3)
x2(3)=x(7)
x2(2)=x(5)
X1(0)
X1(2)
X1(3)
X2(0)
X2(1)
X2(2)
X2(3)
X1(1)
图1.22 按时间抽取,将一个 N=8点DFT分解为两个 4 点 DFT
-1
X(1)
X(0)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
0
8W
8
W
2
8
W
3
8
W
X1(0)
X1(2)
X1(3)
X2(0)
X2(1)
X2(2)
X2(3)
X1(1)
x5(1)=x2(2)=x(5)
N/4 点
DFT
N/4 点
DFT
N/4 点
DFT
N/4 点
DFT
-1
-1
-1
-1
-1
-1
-1
X6(0)
X6(1)
X3(0)
X3(1)
X5(1)
X5(0)
X4(1)
X4(0)
x3(0)=x1(0)=x(0)
x4(1)=x1(2)=x(4)
x4(0)=x1(1)=x(2)
x4(1)=x1(3)=x(6)
x5(0)=x2(0)=x(1)
x6(0)=x2(1)=x(3)
x6(1)=x2(3)=x(7)
0
4
W
1
4
W
0
4
W
1
4W
图1.23 按时间抽取,将一个 N=8点DFT分解为四个 2点DFT
-1
X(1)
X(0)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
0
8
W
8
W
2
8
W
3
8
W
X1(0)
X1(2)
X1(3)
X2(0)
X2(1)
X2(2)
X2(3)
X1(1)
x(5)
-1
-1
-1
-1
-1
-1
-1
X6(0)
X6(1)
X3(0)
X3(1)
X5(1)
X5(0)
X4(1)
X4(0)
x(0)
x(4)
x(2)
x(6)
x(1)
x(3)
x(7)
0
4
W
1
4
W
0
4
W
1
4
W
图1.23 按时间抽取,将一个 N=8点DFT分解为 8个 1点DFT
-1
-1
-1
-1
0
2
W
0
2
W
0
2
W
0
2
W
1.3 FFT 算法特点
(1)原位运算。从图 2.9 的 FFT 运算流图中我们可以看出,这种运算是很有规
律可循的。 其中的每级 (每列) 运算都是由 N/2 个蝶形运算所构成, 如式(1.31)
所示。
k
Nmmm
Nmmm
WjXkXjX
WjXkXkX
)()()(
)()()(
11
11
0
(式 1.31)
剩余10页未读,继续阅读
资源评论
lxc15005035395
- 粉丝: 0
- 资源: 7万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功