Abstract:
The two-dimensional (2-D) discrete Fourier transform (DFT) is widely used in digital signal processing (DSP) and computing applications. Fast Fourier transforms (FFTs) are
widely used as low-complexity algorithms for the computation of the DFT as it reduces the required computation operations from O(N2) to O(N log2 N). The multiplicative complexity is used as a benchmark in comparing different algorithms as it affects the circuit complexity, chip area and power. This paper introduces a new class of multiplierless hardware algorithm consisting only of arithmetic adder circuits that closely approximates the 2-D version of the 8-point DFT. The paper discusses the theory behind the proposed new algorithm, with the DFT presented in the form of an 8 × 8 matrix. Furthermore it provide a multi-beam RF aperture application example where the 2-D DFT approximation
has been used to closely obtain the antenna array patterns.