A DFT using number theoretic logarithms

A method for performing complex arithmetic, called the Galois enhanced quadratic residue number system (GEQRNS), is presented. It is shown how a class of complex arithmetic logic units (ALUs) can be realized using a few well-chosen moduli and a fast multiplier-free complex multiplication unit. The elimination of hardware (and often temporal) consuming multiply units will be achieved by interfacing the quadratic RNS with the classic concept of a Galois field. It is shown that the merger of these two procedures will facilitate the design of the desired 32-bit-class complex multiplier having an execution delay of a few tens of nanoseconds. To demonstrate the potential of the ALU, the design of a prime-factor DFT (discrete Fourier transform) having a real-time bandwidth in excess of 10⁶ transforms/s is presented