ON COMPUTATION OF CERTAIN DISCRETE FOURIER-TRANSFORMS USING BINARY CALCULUS

Completely multiplyless algorithms are proposed to approximately compu te Discrete Fourier Transform (DFT). The computational complexity of t he proposed algorithms for a transform of size N, is O(N-2) addition a nd shift operations. In these algorithms, the DFT can be computed sequ entially, with a single adder in O(N-2) addition times. Parallel versi ons of the algorithms can be executed in O(N) addition times, with O(N ) number of adders. The accuracy of the trigonometric approximations u sed, is bounded by O(N-1). For more elaborate algorithms, the accuracy of the trigonometric approximations is bounded by O(N-2). The degree of approximation in the transformation can be characterized by the rat io of the average magnitude squared error in the transformed sequence, and the average magnitude square of the transformed sequence. This ra tio is very low for higher values of the transform length, N. For smal ler values of the transform length, this value is generally low. A sti pulation is made, that the size of the transform be a Ramanujan number . These Ramanujan numbers are related to pi and integers which are pow ers of 2. It is assumed in this paper that it is more expensive to per form a multiplication than a shift operation.