Fast Convolution using fermat number transforms with applications to digital filtering

Abstract

The structure of transforms having the convolution property is developed. A particular transform is proposed that is defined on a finite ring of integers with arithmetic carried out modulo Fermat numbers. This Fermat number transform (FNT) is ideally suited to digital computation, requiring on the order ofN \log Nadditions, subtractions and bit shifts, but no multiplications. In addition to being efficient, the Fermat number transform implementation of convolution is exact, i.e., there is no roundoff error. There is a restriction on sequence length imposed by word length but multi-dimensional techniques are discussed which overcome this limitation. Results of an implementation on the IBM 370/155 are presented and compared with the fast Fourier transform (FFT) showing a substantial improvement in efficiency and accuracy.