Parallel-computing Approach for FFT Implementation on Digital Signal Processor (DSP)

Authors: Yi-Pin Hsu, Shin-Yu Lin

Abstract:

An efficient parallel form in digital signal processor can improve the algorithm performance. The butterfly structure is an important role in fast Fourier transform (FFT), because its symmetry form is suitable for hardware implementation. Although it can perform a symmetric structure, the performance will be reduced under the data-dependent flow characteristic. Even though recent research which call as novel memory reference reduction methods (NMRRM) for FFT focus on reduce memory reference in twiddle factor, the data-dependent property still exists. In this paper, we propose a parallel-computing approach for FFT implementation on digital signal processor (DSP) which is based on data-independent property and still hold the property of low-memory reference. The proposed method combines final two steps in NMRRM FFT to perform a novel data-independent structure, besides it is very suitable for multi-operation-unit digital signal processor and dual-core system. We have applied the proposed method of radix-2 FFT algorithm in low memory reference on TI TMSC320C64x DSP. Experimental results show the method can reduce 33.8% clock cycles comparing with the NMRRM FFT implementation and keep the low-memory reference property.

Keywords: Parallel-computing, FFT, low-memory reference, TIDSP.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332410

References:

[1] A. V. Oppenheim and C. M. Rader, Discrete-Time Signal Processing, 2nd ed. Upper Saddle River, NJ:Prentice-Hall, 1990, 0137549202.
[2] G. D. Bergland, "A radix-eight fast-Fourier transform subroutine for real-valued series," IEEE Trans. Audio Electroacoust., vol. AE-17, no. 2, pp.138-144, Jun. 1969.
[3] R. C. Singleton, "An algorithm for computing the mixed radix fast Fourier transform," IEEE Trans. Audio Electroacoust., vol. AE-17, no. 2, pp.93-103, Jun. 1969.
[4] D. P. Kolba and T. W. Parks, "A prime factor FFT algorithm using high-speed convolution," IEEE Trans Acoust. Speech, Signal Process., vol. ASSP-25, no. 4, pp.281-294, Aug. 1977.
[5] A. R. Varkonyi-Koczy, "A recursive fast Fourier transform algorithm," IEEE Trans Circuits Syst. II, vol. 42, no. 9, pp.614-616, Sep. 1995.
[6] Y. Wang, Y. Tang, Y. Jiang, J. G. Chung, S. S. Song and M. S. Lim, "Novel memory reference reduction methods for FFT implementation on DSP processors," IEEE Trans Signal Processing, vol. 55, no. 5, pp.2338-2349, May 2007.
[7] Y. Zhou, J. M. Noras and S. J. Shephend, "Novel design of multiplier-less FFT processors," signal processing, vol.87, Issue 6, pp. 1402-1407,June 2007.
[8] B. M. Baas, "A low-power, high-performance, 1024-point FFT processor," IEEE J . Solid-State Circuits, vol. 34, no. 3, pp.380-387, Mar. 1999.
[9] L. He and X. Liao, "Specialising for High Performance FFT Algorithms Based on Fixed-Point DSP," in Proc. IEEE Int. Conf. Communication, Circuits and Systems, Vol. 1, pp. 563-566, June 2006.
[10] "TMS320C64 DSP Library Programmer's Reference (Rev. G)," Texas Instrument, Oct., 2003, SPRU7198G.
[11] "TMS320C6000 Programmer-s Guide," Texas Instrument, Mar., 2006, SPRU1981.
[12] "TMS320C64/C64x+ DSP CPU and Instruction Set Reference Guide," Texas Instrument, Aug., 2006, SPRU732C.