Number theoretic transform implementation using microprocessors

Abstract

Since 1974 considerable interest has been shown in the literature in the topic of number theoretic transforms. These transforms provide an efficient integer processing technique for convolution. Microprocessors are suited to integer processing particularly for applications where the required processing load is small. It was therefore a natural step to investigate and tailor the properties of number theoretic transforms to the capabilities of microprocessors to provide cheap and compact processors using efficient signal processing algorithms. It was found that efficient number theoretic transforms could be defined using the Modulus M = 65521 and this is especially convenient for a microprocessor implementation. Relevant aspects of modular arithmetic are investigated. The techniques developed are extended to allow for complex signal processing. In conclusion it is shown that number theoretic transforms can be used to encode and decode Reed-Soloman error correcting codes.