Integer convolution via split-radix fast Galois transform
Richard E. Crandall · 1999
Integer convolution can be eected, as is well known, via certain number-theoretical transforms. One particular transform, which we call a discrete Galois transform (DGT), can be used eciently for either cyclic or negacyclic integer convolution. The DGT has the feature that, if an appropriate prime p for the field GF(p 2 ) be specified, the allowed power-of-two signal lengths can be quite large. Though the DGTs we consider involve complex arithmetic (amongst Gaussian integers a + bi mod p), it turns out that the run lengths can, in certain settings, be halved. Thus, the fact of real-valued, integer input signals can be exploited along such lines, to enhance the performance of a resulting fast Galois transform (FGT) algorithm. Furthermore, split-radix FFT structure can be bestowed upon the FGT, again boosting eciency for integer convolution.