一种频率抽取 FFT蝶形递归算法及其高效应用
赵建洋 ,丁卫红
(
淮阴工学院计算机工程系 江苏 淮安 223001
)
摘 要 :实际应用中全部点的 FFT算法是冗余的 ,为解决少数点的 FFT算法 ,文章导出了蝶形 FFT的递归方程 ,给出实现
少数点应用程序 ,进而提出直接多项式方法 ,较全部点迭代 FFT算法具有更高的效率。
关键词 :蝶形 FFT的递归方程 ;FFT的递归程序 ;直接 FFT多项式
中图法分类号 : TM317 ,TN914 文献标识码 :A 文章编号 :1009 - 7961
(
2002
)
05 - 0049 - 03
1 引 言
许多文献都对蝶形 FFT
(
快速傅里叶变换
)
的
算法进行了图解
(
如图 1 所示
)
,有些还给出了迭代
算法 ,其基本方法是从第一层开始 ,以 i 层的各个
结点 X
i ,k
作为已知点 ,将
(
i +1
)
层的各个结点 X
i + 1 ,k
迭代出来 ,直到算出最后一层为止 ,为了节省存储
空间 ,常常将已算得的对应结点数据替换前一节点
对应数据作为下一轮迭代数据。这种算法容易实
现 ,较 DFT 而言速度提高了 2000 倍
[1]
。
但是 ,这种算法仍然是冗余的。
首先 ,分析 FFT结果的特点可知 X
(
k
)
与 X
(
N
- k
)
有 :
| X
(
k
)
| =| X
(
N - k
)
|
arg
(
X
(
k
)
= - arg
(
X
(
N - k
) )
(
1
)
(
1
)
式表明对 N 点的 FFT只要求出 0 - N/ 2 点 ,
对应点相位取反也就知道了另一半 ,而不必算出全
部点。
其次 ,在求少数点时 ,按照迭代算法 ,要求出
所有结点 ,冗余度会很大。假设只求图中 X
(
4
)
,
只需要通过图中虚线经过的结点做递归 ,而不必
计算图中所有结点。
X
0 ,k
X
1 ,k
X
2 ,k
X
3 ,k
(
X
’
4 ,k
)
X
4 ,k
图 1 16 点频率抽取蝶形 FFT图解
基金项目 :江苏省教育厅自然科学基金资助项目
(
02KJB510010
)
收稿日期 :2002 - 03 - 18 ;修改日期 :2002 - 09 - 10
作者简介 :赵建洋
(
1963 -
)
,男
(
汉
)
,江苏淮安人 ,淮阴工学院讲师。
第 11 卷第 5 期
2002 年 10 月
淮 阴 工 学 学 报
Journal of Huaiyin Institute of Technology
Vol. 11 No. 5
OCT. 2002
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
wj051224410
- 粉丝: 0
- 资源: 10
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- 2023年中国辣条食品行业创新及消费需求洞察报告.pptx
- 2023年半导体行业20强品牌.pptx
- 2023年全球电力行业评论.pptx
- 2023年全球网络安全现状-劳动力资源和网络运营的全球发展新态势.pptx
- 毕业设计－基于单片机的液体密度检测系统设计.doc
- 家用清扫机器人设计.doc
- 基于VB+数据库SQL的教师信息管理系统设计与实现 计算机专业设计范文模板参考资料.pdf
- 官塘驿林场林防火（资源监管）“空天地人”四位一体监测系统方案.doc
- 基于专利语义表征的技术预见方法及其应用.docx
- 浅谈电子商务的现状及发展趋势学习总结.doc
- 基于单片机的智能仓库温湿度控制系统 (2).pdf
- 基于SSM框架知识产权管理系统 (2).pdf
- 9年终工作总结新年计划PPT模板.pptx
- Hytera海能达CH04L01 说明书.pdf
- 数据中心运维操作标准及流程.pdf
- 报告模板 -成本分析与报告培训之三.pptx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论3