DFT computation using shift and addition operations
N. Bhatnagar · 2002
Bhatnagar (see Signal Processing, vol.43, p.93-101, 1995) introduced Ramanujan numbers to implement the discrete fourier transform (DFT) without using any multiplication operation. Ramanujan numbers are related to /spl pi/ and integers which are powers of 2. The computational complexity of the algorithms used, for computing a transform of size N, is O (N/sup 2/) addition and shift operations. In these algorithms, the transform can be computed sequentially with a single adder in O(N/sup 2/) addition times. Parallel implementation of the algorithm can be executed in O(N) addition times, with O(N) number of adders. Use and properties of Ramanujan numbers of order-1 were discussed by Bhatnagar. In this paper, the properties of Ramanujan numbers of order-2, and their application to DFT are discussed. For the same range of values of N, the DFT computation using Ramanujan numbers of order-2 is generally more accurate than using Ramanujan numbers of order-1. Some of these Ramanujan numbers of order-2 are related to the biblical and Babylonian values of /spl pi/.