FFT Circuitry for a 4G Age

Centar LLC is a provider of fast Fourier transform (FFT) intellectual property (IP) for use in FPGA and ASIC-based embedded applications.  It has developed a novel parallel matrix-based formulation of the discreet Fourier transform (DFT), which decomposes it into structured sets of multiplication-free 4-point discreet Fourier transforms.  All FFT circuits are constructed from synchronous, fine-grained, locally connected, regular arrays of small processing elements (PEs), consisting of a few registers, some multiplexors and an arithmetic element.  Salient features of this technology are:

• Speed: Clock rates >500MHz using 65nm technology (e.g., Altera Stratix III).
• Throughput:  Data rates as high as ~10G complex samples per second
• Dynamic Range:  Combined block floating point and floating point architecture provides ~6db per bit, e.g.,  (16-bits in and 16-bits out) provides ~96db SQNR
• Programmability:  The same circuit architecture can easily be optimized for different FFT sizes and functionality.
• Non-powers-of-two transform sizes:  A single ROM memory can store control parameters to support any number or size FFTs
• Scalability: Faster transforms can be implemented without architectural changes by increasing the array size along one dimension or duplicating the array structure
• Power: Interconnects are entirely local, reducing parasitic routing capacitances to keep power dissipation low and speed high
• Latency: Can be ~N cyles less than typically pipelined FFTs, where N is the transform size

Products

(1) Power-of-two FFT

These products take computational advantage of the radix-4 butterfly matrix which allows multiplications to be replaced with multiplexors and adders and can be fixed-size or variable (programmable at run-time).

(2) Non-power-of-two FFT

The reachable transform sizes for this class of designs are those that can be factored into a composite form based on small integers up to sizes of ~10.  For example, the SC-FDMA LTE requirements would use the integers {2,3,5} to compute all 35 transform sizes, e.g., N=2ⁿ3^m5^q, where n,m, and q are integers.  These can be fixed-size or variable and the different sizes used can be programmed at run-time.

Tools

Because there are always a large number of (parallel) circuit architectures that can be obtained from an algorithm specification, Centar has developed an automated CAD tool, Symbolic Parallel Algorithm Development Environment (SPADE), to make the best choices. SPADE is the only such tool in existence that can find latency optimal circuits.