快速傅里叶变换中计算倒序的新思路

doi:10.11999/JEIT170595

摘要
图/表
参考文献(18)
相关文章 (15)

全文: PDF (213 KB)
输出: BibTeX | EndNote (RIS)

摘要为了提高快速傅里叶变换的运算效率，减少运算时间，该文研究了FFT中倒序序列的计算。研究发现不同长度的倒序序列不相互独立，它们之间有深刻的联系，长度为N的倒序序列可以由长度为N/2的倒序序列生成。根据不同长度的倒序序列之间的相互关联性，给出了新的倒序序列的计算方法及相应的算法流程。通过计算仿真，验证了算法的正确性。该算法实现简单，而且运算效率高。与传统算法相比，新算法可将计算效率提高3个数量级。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	刘大庆
	林浩然
	陈树越

关键词 ：数字信号处理, 快速傅里叶变换, 序列, 倒序

Abstract：In order to improve the efficiency of Fast Fourier Transform (FFT) and reduce the computation time, an algorithm of inversed order sequence in FFT is studied. It is revealed that the inversed order sequences with different length N are not independent but have a deep connection, that is, the inversed order sequence with length N can be produced by the one with length N/2 according to a specific schedule. Based on the interconnectedness, a new approach for calculating the inversed order sequence with length N is proposed and the corresponding procedure flow is shown. The algorithm is simulated and the correctness of the algorithm is verified. The algorithm not only can be realized simply, but also has high efficiency. Compared with the traditional method, the new algorithm can improve the computing efficiency by three orders of magnitude.

Key words： Digital signal processing Fast Fourier Transformation (FFT) Sequence Inversed order

收稿日期: 2017-06-21 出版日期: 2017-12-27

PACS:

TN911.72

基金资助:国家自然科学基金(51176016)

通讯作者: 刘大庆：男，1971年生，副教授，研究方向为电子科学与工程. E-mail: liudq@cczu.edu.cn

作者简介: 刘大庆：男，1971年生，副教授，研究方向为电子科学与工程. 林浩然：男，1995年生，本科生，研究方向为电子科学与工程. 陈树越：男，1963年生，教授，研究方向为图像处理与分析.

引用本文:

刘大庆, 林浩然, 陈树越. 快速傅里叶变换中计算倒序的新思路[J]. 电子与信息学报, 2018, 40(3): 758-762. LIU Daqing, LIN Haoran, CHEN Shuyue. New Approach for Calculating Inversed Order Sequence in FFT. JEIT, 2018, 40(3): 758-762.

链接本文:

http://jeit.ie.ac.cn/CN/10.11999/JEIT170595 或 http://jeit.ie.ac.cn/CN/Y2018/V40/I3/758

[1]	高西全, 丁玉美. 数字信号处理[M]. 第四版, 西安: 西安电子科技大学出版社, 2016: 92-100.
	GAO Xiquan and DING Yumei. Digital Signal Processing [M]. Fourth Edition, Xi,an: Xi,an Electronic and Science University Press, 2016: 92-100.
[2]	吴京. 信号分析与处理[M]. 修订版, 北京: 电子工业出版社, 2014: 129-142.
	WU Jing. Signal Analysis and Processing [M]. Revised Edition, Beijing: Electronic Industry Press, 2014: 129-142.
[3]	柳群, BRIGHAM E O. 快速傅立叶变换[M]. 上海: 上海科学技术出版社, 1979.
	LIU Qun and BRIGHAM E O. Fast Fourier Transform[M]. Shanghai: Shanghai Science and Technology Press, 1979.
[4]	张克俊, 唐勇波. DIT-FFT的倒序算法[J]. 兵工自动化, 2005, 24(5): 46-48. doi: 10.3969/j.issn.1006-1576.2005.05.024.
	ZHANG Kejun and TANG Yongbo. Reverse algorithm DIT- FFT[J]. Ordnance Industry Automation, 2005, 24(5): 46-48. doi: 10.3969/j.issn.1006-1576.2005.05.024.
[5]	朱冰莲, 方敏. 数字信号处理[M]. 第2版, 北京: 电子工业出版社, 2014: 99-114.
	ZHU Binglian and FANG Min. Digital Signal Processing[M]. Second Editiong, Beijing: Publishing House of Electronics Industry, 2014: 99-114.
[6]	徐美清, 孙晨亮. 快速傅立叶变换FFT算法特点分析[J]. 科学与财富, 2016, 1(10): 52-54.
	XU Meiqing and SUN Chenliang. Characteristics analysis of fast Fourier transform FFT algorithm[J]. Journal of Science and Wealth, 2016, 1(10): 52-54.
[7]	郑伟华. 快速傅立叶变换-算法及应用[D]. [博士论文], 湖南大学, 2015.
	ZHENG Weihua. Fast Fourier transform algorithm and its application[D]. [Ph.D. dissertation], Hunan University, 2015.
[8]	郑宇凡. 浅谈FFT(快速傅立叶变换)算法及其应用[J]. 科技展望, 2015, 25(29): 144-145. doi: 10.3969/j.issn.1672-8289. 2015.29.132.
	ZHENG Yufan. Discussion on FFT (fast Fourier transform) algorithm and its application[J]. Science and Technology, 2015, 25(29): 144-145. doi: 10.3969/j.issn.1672-8289.2015.29. 132.
[9]	徐士良. 计算机常用算法[M]. 北京: 清华大学出版社, 1995: 287-291.
	XU Shiliang. Computer Algorithm[M]. Beijing: Tsinghua University Press, 1995: 287-291.
[10]	程乾生. 数字信号处理[M]. 北京: 北京大学出版社, 2003: 7-23.
	CHENG Qiansheng. Digital Signal Processing[M]. Beijing: Peking University Press, 2003: 7-23.
[11]	汪海兵, 徐淑正, 杨华中. 基于查找表的单基FFT原址倒序算法[J]. 清华大学学报, 2008, 48(1): 43-45. doi: 10.3321/ j.issn:1000-0054.2008.01.012.
	WANG Haibing, XU Shuzheng, and YANG Huazhong. The single-base FFT site reverse algorithm based on look-up table[J]. Journal of Tsinghua University, 2008, 48(1): 43-45. doi: 10.3321/j.issn:1000-0054.2008.01.012.
[12]	方志红, 张长耀, 俞根苗. 利用逆序循环实现FFT算法中倒序算法的优化[J]. 信号处理, 2004, 20(5): 533-535. doi: 10.3969/j.issn.1003-0530.2004.05.023.
	FANG Zhihong, ZHANG Changyao, and YU Genmiao. To realize the optimization of reverse FFT algorithm in using reverse circulation[J]. Journal of Signal Processing, 2004, 20(5): 533-535. doi: 10.3969/j.issn.1003-0530.2004.05.023.
[13]	张学智, 蔡辉. 快速实现FFT的逆序方法[J]. 探测与控制学报, 2001, 23(2): 62-65. doi: 10.3969/j.issn.1008-1194.2001. 02.023.
	ZHANG Xuezhi and CAI Hui. Fast implementation of FFT reverse order method[J]. Journal of Detection and Control, 2001, 23(2): 62-65. doi: 10.3969/j.issn.1008-1194.2001.02.023.
[14]	刘仲, 陈海燕, 向宏卫. 使用融合乘加加速快速傅立叶变换计算的向量化方法[J]. 国防科技大学学报, 2015, 37(2): 72-78. doi: 10.11887/j.cn.201502015.
	LIU Zhong, CHEN Haiyan, and XIANG Hongwei. By using fusion and accelerate the vectorization method of fast Fourier transform[J]. Journal of National University of Defense Technology, 2015, 37(2): 72-78. doi: 10.11887/j.cn.201502015.
[15]	薛会, 张丽, 刘以农. 非标准快速傅里叶变换算法综述[J]. CT理论与应用研究, 2010, 19(3): 33-46. doi: 10.3969/j.issn.1003- 2215.2014.11.015.
	XUE Hui, ZHANG Li, and LIU Yinong. Overview of non standard fast Fourier transform algorithm[J]. CT Theory and Applications, 2010, 19(3): 33-46. doi: 10.3969/j.issn.1003- 2215.2014.11.015.
[16]	张大炜. 一种新的级联FFT算法[J]. 舰船科学技术, 2016, 38(5): 60-63. doi: 10.3404/j.issn.1672-7619.2016.05.013.
	ZHANG Dawei. A new cascade FFT algorithm[J]. Ship Science and Technology, 2016, 38(5): 60-63. doi: 10.3404/ j.issn.1672-7619.2016.05.013.
[17]	李龙军, 王布宏, 夏春和. 基于迭代FFT算法的平面阵列交错稀疏布阵方法[J]. 电子与信息学报, 2016, 38(4): 970-977. doi: 10.11999/JEIT150749.
	LI Longjun, WANG Buhong, and XIA Chunhe. Interleaved thinned linear arrays based on modified iterative FFT technigue[J]. Journal of Electronics and Information Technology, 2016, 38(4): 970-977. doi: 10.11999/JEIT150749.
[18]	陈慧, 周继惠, 郭春亮, 等. 基于VB的FFT算法的设计和实现[J]. 华东交通大学学报, 2003, 20(1): 94-96. doi: 10.3969/ j.issn.1005-0523.2003.01.027.
	CHEN Hui, ZHOU Jihui, GUO Chunliang, et al. Design and implementation of FFT algorithm based on VB[J]. Journal of East China Jiaotong University, 2003, 20(1): 94-96. doi: 10.3969/j.issn.1005-0523.2003.01.027.