ABSTRACT
The discrete Fourier transform uses floating-point multiplications which result in noninteger outputs even in the case of most importance in practice, when input data are integer numbers. It is thus desired to develop a reversible transform which approximates the Fourier transform and maps integer data into integer ones. For the Fourier transform, we mention two approaches for defining an integer DFT. The first approach is based on approximation of the transform matrix by a matrix with integer coefficients, and the second one suggests using the lifting scheme with an integer quantizer. The integer Fourier transform with integer entries was introduced in [28] and implementation of this transform requires a large number of the fixed-point multiplications. For instance, for inputs of length eight, this transform requires eight fixed-point multiplications instead of two floating-point multiplications for the conventional FFT. The approach based on substitution of the exponential coefficients (twiddle factors) in the DFT by lifting schemes is described in [29]. Each such substitution may increase the resolution of its input by one bit, and there are different choices in parameterizing the lifting coefficients. The transform is effective, because it can be implemented by using only bit shifts and additions.
