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

doi:10.11999/JEIT170595

Abstract
Figure/Table
References (18)
Related Citation (15)

Download: PDF (213 KB)
Export: BibTeX | EndNote (RIS)

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

Received: 21 June 2017 Published: 27 December 2017

PACS:

TN911.72

Fund:The National Natural Science Foundation of China (51176016)

Corresponding Authors: LIU Daqing E-mail: liudq@cczu.edu.cn

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	LIU Daqing
	LIN Haoran
	CHEN Shuyue

Cite this article:

LIU Daqing,LIN Haoran,CHEN Shuyue. New Approach for Calculating Inversed Order Sequence in FFT[J]. JEIT, 2018, 40(3): 758-762.

URL:

http://jeit.ie.ac.cn/EN/10.11999/JEIT170595 OR http://jeit.ie.ac.cn/EN/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.