Fast Integer Fourier Transform (FIFT) based on lifting matrices
Ratchaneekorn Thamvichai, Tamal Bose, Miloje S. Radenković · 2003
This paper proposes a fast algorithm for computing the approximated DFT, called the Fast Integer Fourier Transform (FIFT). The new transform is based on the factorization of the DFT matrix into a product of some specified matrices and lifting matrices. The elements of the lifting matrices are quantized to the nearest binary-number representation. Therefore, the proposed algorithm can be implemented in fixed-point arithmetic using only shifting operations and additions. Any length-2/sup l/ DFT sequence for l /spl ges/ 1 can be computed using this algorithm.