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.
