A novel overall in-place in-order prime factor FFT algorithm

This paper presents a new prime factor algorithm (PFA) for non-power-of-two point FFT. Compared with the conventional prime factor decomposition algorithms, the approach performs the in-place, in-order algorithm of the small factor DFT, and gets the in-order output finally by reading the results with the address generated by an easy and simple modular adder. It is a general purpose algorithm for variable size FFT/IFFT, which is more suitable for implementation in programmable logic device because of its regular and simple structure. As an example, this paper implements a 3780-point FFT processor for Chinese Digital Terrestrial Multimedia/Television Broadcasting (DTMB) standard, which combines the Winograd Fourier transform algorithm (WFTA) and the mixed-radix algorithm.