Discrete Fourier transform (DFT) finds various applications in signal processing, image processing, artificial intelligent, and fuzzy logic etc. DFT is often computed efficiently with Fast Fourier transform (FFT). The modified split radix FFT (MSRFFT) algorithm implements a length-N=2m DFT achieving a reduction of arithmetic complexity compared to split-radix FFT (SRFFT). In this paper, a simplified algorithm is proposed for the MSRFFT algorithm, reducing the number of real coefficients evaluated from 5/8N - 2 to 15/32N - 2 and the number of groups of decomposition from 4 to 3. A implementation approach is also presented. The approach makes data-path of the MSRFFT regular similar to that of the radix-2 FFT algorithm. The experimental results show that (1) MSRFFT consumes less time on central processing units (CPUs) with sufficient cache than existing algorithms; (2) the proposed implementation method can save execution time on CPUs and general processing units (GPUs).
BiG., LiG. and LiX., A unified expression for split-radix dft algorithms, In Communications, Circuits and Systems (ICC-CAS), 2010 International Conference on, 2010, pp. 323–326. IEEE.
2.
BouguezelS., AhmadM.O. and SwamyM.N.S., A new radix-2/8 fft algorithm for length-q×2m dfts, Circuits and Systems I: Regular Papers, IEEE Transactions on51(9) (2004), 1723–1732.
3.
BowersK.J., LippertR.A., DrorR.O. and ShawD.E., Improved twiddle access for fast fourier transforms, Signal Processing, IEEE Transactions on58(3) (2010), 1122–1130.
4.
BuckI., FoleyT., HornD., SugermanJ., FatahalianK., HoustonM. and HanrahanP., Brook for gpus: stream computing on graphics hardware, In ACM Transactions on Graphics (TOG)23 (2004), 777–786. ACM.
5.
CooleyJ.W. and TukeyJ.W., An algorithm for the machine calculation of complex fourier series, Math Comput19(90) (1965), 297–301.
6.
DuhamelP. and HollmannH., Split-radix fft algorithm, Electron Lett20 (1984), 14–16.
7.
DuhamelP. and VetterliM., Fast fourier transforms: a tutorial review and a state of the art, Signal Processing19(4) (1990), 259–299.
8.
DuhamelP. and HollmannH., Split radix’fft algorithm, Electronics Letters20(1) (1984), 14–16.
9.
FrigoM. and JohnsonS.G., The design and implementation of fftw3, Proceedings of the IEEE93(2) (2005), 216–231.
10.
GarciaJ., MichellJ.A. and BuronA.M., Vlsi configurable delay commutator for a pipeline split radix fft architecture, Signal Processing, IEEE Transactions on47(11) (1999), 3098–3107.
11.
GrigoryanA.M. and AgaianS.S., Split manageable efficient algorithm for fourier and hadamard transforms, Signal Processing, IEEE Transactions on48(1) (2000), 172–183.
12.
GutierrezE., RomeroS., TrenasM.A. and ZapataE.L., Memory locality exploitation strategies for fft on the cuda architecture, In High Performance Computing for Computational Science-VECPAR 2008, 2008, pp. 430–443. Springer.
13.
JohnsonS.G. and FrigoM., A modified split-radix fft with fewer arithmetic operations, IEEE Trans Signal Processing55(1) (2007), 111–119.
14.
KamarI. and ElcherifY., Conjugate pair fast fourier transform, Electronics Letters25(5) (1989), 324–325. doi: 10.1049/el:19890225.
15.
KwongJ. and GoelM., A high performance split-radix fft with constant geometry architecture, In Design, Automation & Test in Europe Conference & Exhibition (DATE), 2012, pp. 1537–1542. IEEE.
16.
LarsenE.S. and McAllister.D., Fast matrix multiplies using graphics hardware, In Proceedings of the 2001 ACM/IEEE Conference on Supercomputing (CDROM), 2001, pp. 55–55. ACM.
17.
LarssonE.G., GustafssonO., The impact of dynamic voltage and frequency scaling on multicore dsp algorithm design [exploratory dsp], Signal Processing Magazine, IEEE28(3) (2011), 127–144.
18.
MarkW.R., GlanvilleR.S., AkeleyK. and KilgardM.J., Cg: A system for programming graphics hardware in a c-like language, In ACM Transactions on Graphics (TOG), volume 22, 2003, pp. 896–907. ACM.
19.
MartensJ.B., Recursive cyclotomic factorization–a new algorithm for calculating the discrete fourier transform, Acoustics, Speech and Signal Processing, IEEE Transactions on32(4) (1984), 750–761.
20.
MorelandK. and AngelE., The fft on a gpu, In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, 2003, pp. 112–119. Eurographics Association.
21.
NylandL., HarrisM. and PrinsJ., Fast n-body simulation with cuda, GPU Gems3 (2007), 677–695.
22.
DuhamelP., Implementation of split-radix fft algorithms for complex,real, and real symmetric data, IEEE Transactions on Acoustics, Speech and Signal Processing34(2) (1986), 285–295.
23.
RashmanlouH. and BorzooeiR.A., Product vague graphs and its applications, Journal of Intelligent & Fuzzy Systems (2015), 1–12. Preprint(Preprint).
24.
SorensenH., HeidemanM. and BurrusC., On computing the split-radix fft, IEEE Trans Acoust. Speech, Signal Processing34(1) (1986), 152–156.
TakahashiD., An extended split-radix fft algorithm, Signal Processing Letters, IEEE8(5) (2001), 145–147.
27.
TarditiD., PuriS., OglesbyJ., Accelerator: Using data parallelism to program gpus for general-purpose uses, In ACM SIGARCH Computer Architecture Newsvolume 34, 2006, pp. 325–335. ACM.
28.
VetterliM. and NussbaumerH.J., Simple fft and dct algorithms with reduced number of operations, Signal Processing6(4) (1984), 267–278.
29.
WangC., Some properties of entropy of vague soft sets and its applications, Journal of Intelligent & Fuzzy Systems29(4) (2014), 1443–1452.
30.
YalaouiN., AmodeoL., YalaouiF. and MahdiH., Efficient methods to schedule reentrant flowshop system, Journal of Intelligent & Fuzzy Systems26(3) (2014), 1113–1121.
31.
YavneR., An economical method for calculating the discrete fourier transform, in Proc AFIPS Fall Joint Computer Conf33 (1968), 115–125.
32.
YehW.-C. and Chein-WeiJ., High-speed and low-power split-radix fft, Signal Processing IEEE Transactions on51(3) (2003), 864–874.
33.
ZhengW., LiK. and LiK., Scaled radix-2/8 algorithm for efficient computation of length-N = 2m DFTs, IEEE Transactions on Signal Processing62 (2014), 2492–2503. 10.1109/TSP.2014.2310434
