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 of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N \log N</tex> additions, 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.