A Comparative Analysis of CORDIC-Based versus LUT+Multiplier-Based Schemes for Parallel Computation of Radix-4 FFT Dragonfly
Abstract
This paper analyzes the relative complexities, as expressed in terms of arithmetic and trigonometric memory requirements, of three different solutions for the parallel computation of those arithmetic tasks needing to be performed by the computational unit of the radix-4 fast Fourier transform (FFT) algorithm, denoted CU4 and referred to here as a ‘dragonfly’. The first two solutions are conventional, being based upon different combinations of look-up tables (LUTs), adders and multipliers: the first solution, employing single-level LUTs combined with adders and multipliers, seeks to minimize the arithmetic complexity at the expense of an increased memory requirement, whilst the second, employing a two-level LUT and second-order recursion (involving just adders and multipliers) combined with additional adders and multipliers, seeks to minimize the memory requirement at the expense of increased arithmetic complexity. The third solution takes a non-conventional approach, being based upon the use of three pipelined COordinate Rotation DIgital Computer (CORDIC) arithmetic units (each employing its own adders, together with bit shifters and constant multipliers) combined with additional adders, and has a complexity, unlike that of the other two solutions, that’s dependent upon the word length but independent of the transform length, effectively eliminating the trigonometric memory requirement at the expense of an increased number of adders. With the transform length and word length denoted by N and L, respectively, these properties follow directly from the derived complexity results which state that the first solution possesses O(LN) complexity, the second O(L√N) complexity and the third O(L2) complexity, where N >> L, with the results generalizing in an obvious fashion to the case of CUR, for the radix-R FFT, where R is an arbitrary positive integer. As a result, for those big-data applications involving the use of large transforms, independence of the transform length makes the CORDIC-based solution look particularly attractive, especially when resources – such as fast memory – are limited.