Fast Integer Fourier Transform (FIFT) based on lifting matrices

Author

Thamvichai, R. ; Bose, Tamal ; Radenkovic, Miloje

Author_Institution

Electr. & Comput. Eng., St. Cloud Univ., MN, USA

Volume

4

fYear

2003

fDate

25-28 May 2003

Abstract

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^l DFT sequence for l ≥ 1 can be computed using this algorithm.

Keywords

computational complexity; fast Fourier transforms; fixed point arithmetic; matrix algebra; signal processing; DFT matrix factorization; additions; approximated DFT; binary-number representation; fast integer Fourier transform; fixed-point arithmetic; lifting matrices; shifting operations; Cloud computing; Costs; Digital signal processing; Discrete Fourier transforms; Discrete cosine transforms; Discrete transforms; Fixed-point arithmetic; Fourier transforms; Information processing; Signal processing algorithms;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium on

Print_ISBN

0-7803-7761-3

Type

conf

DOI

10.1109/ISCAS.2003.1205779

Filename

1205779