|
Article information
2018 , Volume 23, ¹ 3, p.3-14
Altman E.A.
A method of reducing the number of operations in a fast Fourier transform algorithm
The purpose of this work is studying of methods to reduce the number of calculations which must be performed to calculate the fast Fourier transform (FFT). These methods optimize the well-known FFT algorithms, such as Cooley-Tukey or split-radix. The main idea of these methods is the reduction of operations due to their transfer on the graph of the algorithm through the stages of calculations This method is often used for explanation of split-radix or radix-4 algorithms. In our work, both area and distance of factor transfers are extended for 2 or more stages. Using this idea, we found two methods of cutting down the number of multiplications. In both ways, the transfer is carried out for 4 points through 2 stages of the graph. In the first method, the transfer occurs in the direction of the calculations, in the second - in the opposite direction. In both cases, the methods give a result if at the stage to which the transfer is carried out, there are non-trivial turning factors. Applying these methods to radix-4 FFT algorithm allows reducing the number of calculations, but don’t make them less than the number of calculations in the splitradix FFT. The record of minimal arithmetic operation for FFT algorithm was taken in applying these methods to the mixed algorithm consisting of split-radix and radix4 stages. This approach saves 8 operations in FFT algorithm for 256 points over the modified split-radix FFT (tangent FFT).
[full text]
Keywords: FFT, split radix, radix 4, arithmetic complexity
doi: 10.25743/ICT.2018.3.15955
Author(s):
Altman Evgenii Anatolevich
Office: Omsk State Transport University
Address: 644046, Russia, Omsk
E-mail: AltmanEA@gmail.com
References:
[1] Cooley, J.W., Tukey, J.W. An algorithm for the machine computation of the complex fourier series. Mathematics of Computation. 1965; (19):297–301.
[2] Yavne, R. An economical method for calculating the discrete Fourier transform. Proceedings of the AFIPS '68 Fall Joint Computer Conference. San Francisco, California, USA. 1968; (33):115–125.
[3] Duhamel, P., Hollmann, H. Split radix’FFT algorithm. Electronics Letters. 1984; (20):14–16.
[4] Van Buskirk J. Large FFT – NOT radix-2. Available at: https://groups.google.com/forum/#!msg/comp.dsp/JLjf5KwuxYY/gcAiNhLnHF0J(accessed 20.02.2018).
[5] Johnson, S., Frigo, M. A modified split-radix FFT with fewer arithmetic operations. The IEEE Transactions on Signal Processing. 2007; 55(1):111–119.
[6] Bernstein D. J. The tangent FFT //International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes. Springer, Berlin, Heidelberg; 2007:291-300.
[7] Qadeer, S., Khan, M.Z. Ali, Sattar, S.A., Ahmed A Radix-2 DIT FFT with reduced arithmetic complexity. Advances in Computing, Communications and Informatics (ICACCI, 2014). International Conference on. IEEE. 2014:1892-1896.
[8] Khan M. Z. A., Qadeer S. A new variant of Radix-4 FFT. Wireless and Optical Communications Networks (WOCN), 2016 Thirteenth International Conference on. IEEE. 2016:1-4.
[9] Korde, Ch., Malathi, P., Shelke, S.N., Sharma, M. Design of FPGA Based Radix 4 FFT Processor using CORDIC. Journal of Innovation in Electronics and Communication Engineering. 2015; (5):56–62.
[10] Knyazkov, D.Yu. Effective computation of two-dimensional FFT on a homogeneous or heterogeneous cluster. Program Systems: Theory and Applications. 2017; 8(1):47–62. (In Russ.)
[11] Burrus, C. Fast Fourier Transforms (6 õ 9 Version). Available at: https://cnx.org/contents/Fujl6E8i@5.8:-1XsePkH@10/Preface-Fast-Fourier-Transform (accessed 20.02.2018).
[12] Altman, E. DSP algorithms. Available at: https://github.com/AltmanEA/DSP (accessed 20.02.2018).
[13] Kamar, I., Elcherif, Y. Conjugate pair fast Fourier transform. Electronics Letters. 1989; 25(5):324–325.
Bibliography link:
Altman E.A. A method of reducing the number of operations in a fast Fourier transform algorithm // Computational technologies. 2018. V. 23. ¹ 3. P. 3-14
|
