Novel Reversible Integer Fourier Transform With Control Bits

摘要

This paper presents a novel concept of the reversible integer discrete Fourier transform (RiDFT) of order $2{r}$ , $r>2$, when the transform is split by the paired representation into a minimum set of short transforms, i.e., transforms of orders $2{k}$, $k≪r$ . By means of the paired transform the signal is represented as a set of short signals which carry the spectral information of the signal at specific and disjoint sets of frequencies. The paired transform-based fast Fourier transform (FFT) involves a few operations of multiplication that can be approximated by integer transforms. Examples of 1-point transforms with one control bit are described. Control bits allow us to invert such approximations. Two control bits are required to perform the 8-point RiDFT, and 12 (or even 8) bits for the 16-point RiDFT of real inputs. The proposed forward and inverse RiDFTs are fast, and the computational complexity of these transforms is comparative with the complexity of the FFT. The 8-point direct and inverse RiDFTs are described in detail.