A Generalized Conflict-Free Memory Addressing Scheme for Continuous-Flow Parallel-Processing FFT Processors With Rescheduling

This paper presents a generalized conflict-free memory addressing scheme for memory-based fast Fourier transform (FFT) processors with parallel arithmetic processing units made up of radix-$2^{q}$ multi-path delay commutator (MDC). The proposed addressing scheme considers the continuous-flow operation with minimum shared memory requirements. To improve throughput, parallel high-radix processing units are employed. We prove that the solution to non-conflict memory access satisfying the constraints of the continuous-flow, variable-size, higher-radix, and parallel-processing operations indeed exists. In addition, a rescheduling technique for twiddle-factor multiplication is developed to reduce hardware complexity and to enhance hardware efficiency. From the results, we can see that the proposed processor has high utilization and efficiency to support flexible configurability for various FFT sizes with fewer computation cycles than the conventional radix-2/radix-4 memory-based FFT processors.

I. Introduction

Fast Fourier transform (FFT) plays an important role in digital signal processing applications, such as telecommunications, image processing, medical signal processing, and spectrum analyzing. Recently, as orthogonal frequency-division multiplexing (OFDM) techniques become popular in wireless communication systems, dedicated hardware implementation of an FFT processor attracts much attentions. For example, 64- and 128-point FFT operations are used in IEEE 802.11a/g/n. FFT sizes from 128 to 2048 are required in 3GPP-LTE and IEEE 802.16e. Consequently, a configurable and hardware-efficient FFT processor which is capable of processing various-size FFT operations in multiple standards is desired [1] and becomes one of the keys to the development of the software defined radio (SDR) system.