|Table of Contents|

An Improved Fast Implementation Method for FFT Pruning Algorithm(PDF)

南京师范大学学报（工程技术版）[ISSN:1006-6977/CN:61-1281/TN]

Issue:
2005年04期
Page:
42-45
Research Field:
Publishing date:

Info

Title:
An Improved Fast Implementation Method for FFT Pruning Algorithm
Author(s):
LI Zhonghui; ZENG Yumin; YIN Xiaoqi; WU Tingting
School of Physical Science and Technology,Nanjing Normal University,Jiangsu Nanjing 210097,China
Keywords:
FFT Prun ing algor ithm;  imp lem enta tion o f a lgor ithm;  dig ital signa l processing;  spectrum reso lution
PACS:
TN911.7
DOI:
-
Abstract:
Considering the FFT Prun ing a lgor ithm propo sed in lite rature[ 5], this paper improves it and obtains an improv ed fast im plem en tation m ethod fo r FFT prun ing algorithm in which only part spectra l o f thew ho le FFT. s spectra l need to be ca lculated. Accord ing to struc tura l charac teristics o f the input and output data, the im proved m ethod utilizes the data replication and assistantm atrix to decrease the com putationa l com plex ity and enhance the im plem entary flex ib ility of the FFT Prun ing algorithm. The improved m ethod is realized in C and run in C5402 Dev ice S imu lator o f CCS w hich is the integ rated explo itive circum stance fo rDSP. The C prog ram s correspond ing to the a lgo rithm in reference [ 5] and basic FFT algor ithm a re run respective ly in the sam e c ircum stance too. A fter the three C prog ram files a re execu ted, the executive tim e o f each a lgor ithm are recorded to compare the e fficiency o f them. The emu lational expe rim en ts show that in the sam e cond ition, contrasted w ith other me thods, the im proved m ethod consumes less tim e obv iously wh ile the co rresponding spectra can be obta ined qu ickly and correctly, and tha t it doesn. t lim it the leng th o f the input and output data too.

References:

[ 1] M arke l J D. FFT pruning [ J]. IEEE Trans on Audio E lectroacoust, 1971, 19( 4): 305- 311.
[ 2] Skinner D P. Prun ing the dec im ation in time FFT algor ithm [ J]. IEEE T rans on ASSP, 1976, 24( 3): 193- 194.
[ 3] S reeniv as T V, Rao P V S. FFT a lgor ithm fo r both input and output prun ing[ J]. IEEE Trans on ASSP, 1979, 27 ( 3): 291- 292.
[ 4] N aga i K. Prun ing the decim a tion- in- tim e FFT a lgo rithm w ith frequency shift[ J]. IEEE Trans on ASSP, 1986, 34 ( 4): 1008 -1010.
[ 5] A lves R G, O sor io P L, Sw am y M N S. General FFT prun ing [ C ] / / Proceed ing s of the 43rd IEEE M idwest Symposium. M ich igan: Lansing, 2000: 1192- 1195.
[ 6] 胡广书. 数字信号处理) ) ) 理论、算法与实现[M ] . 2 版. 北京: 清华大学出版社, 2003: 187- 192.

Memo

Memo:
-
Last Update: 2013-04-29