Fast Fourier Transforms using the complex logarithmic number system

The complex-logarithmic number system (CLNS), which represents each complex point in log/polar coordinates, may be practical to implement the Fast Fourier Transform (FFT). The roots of unity needed by the FFT have exact representations in CLNS and do not require a ROM. We present an error analysis and simulation results for a radix-two FFT that compares a rectangular fixed-point representation of complex numbers to CLNS. We observe that CLNS saves 9-12 bits in word-size for 256-1024 point FFTs compared to the fixed-point number system while producing comparable accuracy. The consequence of the word-size advantage is that the number of full adders required for CLNS is significantly smaller than for an equivalent fixed-point implementation. The major cost of CLNS is the memory, which unlike conventional LNS, is addressed by both real and imaginary parts. Table-reduction techniques can mitigate this. The simplicity of the CLNS approach requires significantly fewer full adders, which pays for some or all of the extra memory. In applications needing the magnitude of the complex parts, such as a power spectrum, the CLNS approach can actually require less memory than the conventional approach.