Sparse fast Fourier transform implementation on multicore DSP

Sparse Fast Fourier Transform (SFFT) is a recently proposed highly efficient Fourier transform algorithm. It can also be utilized to extract the K largest frequency coefficients from the N-point sequence, which is sparse in the frequency domain. This chapter presents a parallel implementation of SFFT on the Texas Instruments' TMS320C6678 multicore Digital Signal Processor (DSP). The result showed that the SFFT implementation on multicore DSP could obtain an acceleration of up to 1.9 times that of a single-threaded PC. With the advantages of low power and low cost, DSP-based SFFT implementation is particularly suitable for embedded systems. The chapter provides a parallel SFFT on the TI TMS320C6678 multicore DSP, utilizes the intrinsic operations, and presents C6000 DSP libraries for further improving of the SFFT performance. SFFT can be applied in computing the Discrete Fourier Transform (DFT) of a time domain signal, which is sparse in the frequency domain, and SFFT is faster than FFTW for DFT.