Enhancing Mersenne transforms by RNS with application to discrete convolution

Abstract

The paper develops an enhanced algorithm for the exact computation of discrete convolution based on Mersenne transforms and multi-moduli residue number systems (RNSs). The proposed algorithm combines the advantages of Mersenne transforms and the advantages of the RNS system. The computation of Mersenne transforms involves only simple operations: addition and circular shift operations. The RNS system is used to increase the length of input sequences, to extend the unsatisfactory limited numerical range of Mersenne transforms, and to split convolution computations onto several smaller channels. A comparison of this algorithm with the traditional algorithm verifies the ability of this algorithm to solve many convolution problems. Numerical examples and tables are given to illustrate the new algorithm. In addition, practical considerations are discussed.