Fast convolution with finite field fast transforms

Abstract

The fast convolution procedure for processing discrete data requires that a transform of the data and the filter pulse response be formed, followed by the inverse transform of their (complex) product. The finite field fast transform eliminates any roundoff error due to internal multiplication, eliminates truncation of irrational coefficients, and requires only real arithmetic (addition and multiplication). This note develops a realization scheme for such a transform using the Chinese remainder theorem.