A NEW APPROACH TO SOLVE THE SEQUENCE-LENGTH CONSTRAINT PROBLEM IN CIRCULAR CONVOLUTION USING NUMBER THEORETIC TRANSFORM

When the Mersenne or Fermat transform is used, the lengths of the sequences which can be convoled are linearly proportional to the word length. As a consequence, the one-dimensional circular convolution using number theoretic transform with modulo a Mersenne or Fermat number can only have short sequence lengths. This is known as the sequence-length constraint problem. A solution to this problem by using a two-dimensional implementation was offered by Radar, Agrawal, and Burrus. Using two-dimensional implementation of a one-dimensional convolution, the maximum length of sequences equals twice the square of the word length. The objective of this paper is to offer a new approach to solve this problem by proposing a new formula to produce generalized modulo numbers for number theoretic transforms. By selecting a prime M as the modulo number and choosing the least primitive root M as the alpha in the number theoretic transform, the sequence lengths become exponentially proportional to the word length. Therefore, the sequence length constraint problem in one-dimensional convolution using number theoretic transform is solved. The set of generalized modulo numbers includes Mersenne and Fermat numbers. This set provides not only more choices of modulo numbers for number theoretic transform, but also simple implementation of circular convolution because of the special structure of the new formula. As with the Mersenne and Fermat transforms, the circular convolution obtained by this new method is accurate, i.e., without roundoff error.