THE fast Fourier transform (FFT) is a commonly used algorithm in digital signal processing areas, such as imaging applications and communication systems. Memory-based FFTs pass the data multiple times through a single butterﬂy processing element (PE) or set of PEs, with several memory banks to hold intermediate results, processing the data recursively regardless of computation length. Conﬂict-free address schemes for concurrent data access from different memory banks become an essential problem. A parity bit check method for one or more radix-2 PEs is ﬁrst introduced. An in-place strategy reduces the total memory storage to minimum N. A mixed radix-4/2 in-place scheme makes the input and output bits symmetric, and then, the conﬂict-free scheme is extended to a mixed-radix algorithm. A multiple radix-2 PE scheme is demonstrated to increase the throughput of FFT processors.
Multipath Delay Commutator (MDC):
A multipath delay commutator (MDC) architecture with high radix is used to replace the complex PE in conventional memory-based FFTs. a generalized conﬂict-free address scheme with single or multiple radix-2q MDC architectures for 2n-point FFTs is illustrated. However, this scheme does not extend the principle to arbitrary-length FFTs and more general decomposition algorithms.
Fig 1: Architecture of a multiple-PE, memory-based FFT processor
- More number of computation cycles
- Complexity of the computation
High radix–small-butterﬂy (HRSB):
A memory-based FFT processor design methodology with a generalized conﬂict-free address scheme for arbitrary-length FFTs. We unify the conﬂict-free address schemes of three different FFT lengths, including the single power point (SPP) FFTs, the common non single-power point (NSPP) FFTs, and the NSPP FFTs applied with the PFA, to the same address generation format. The memory bank index and the internal address are all generated by
Fig 2: Block diagram of the proposed FFT processor architecture
Xilinx ISE 14.7