Cyclotomic Basis for Computing the Discrete Fourier Transform

G. Jerônimo da Silva Jr., R. M. Campello de Souza

DOI: 10.14209/sbrt.2010.74

Evento: VII International Telecommunications Symposium (ITS2010)

Keywords: FFT DFT multiplicative complexity cyclotomic basis

Abstract

This paper presents a new fast algorithm for computing an N-point discrete Fourier transform. The algorithm meets the Heideman multiplicative complexity lower bound for N = {3, 4, 6, 8, 12} and is based upon the decomposition of the elements of the transform matrix into a cyclotomic basis.

Download