New Developments on the Core Function for Efficient Implementation of the Difficult Residue Number System Operations

摘要

This paper develops new properties of the core function on a residue number system (RNS) which allows efficient implementation of the operations of comparison, overflow detection, sign determination, parity determination, scaling, and general division. Previously these operations have been considered difficult to implement in high speed hardware and have not taken advantage of the parallel structure of a residue class architecture. In 1977, Akushskii, Burcev and Pak introduced the core function and presented algorithms for these difficult operations. While these algorithms were superior to previous techniques, the evaluation of the core function required, in general, an iterative, complex procedure. Moreover, while these techniques were theoretically attractive, they were unable to construct a methodology for determining a suitable core function for a realistic moduli set. In the present work, a new method for evaluating the core function is introduced. This method utilizes a redundant modulus and its computational complexity is equivalent to that of the first iteration of the method of Akushskii et al. While this new method requires additional hardware to carry on this redundant modulus calculation, it provides more information and allows more flexibility than the previous method. New and much more efficient algorithms for the difficult RNS operations are developed. In addtition, new structural properties of the core function are developed, and the optimality of the function is characterized. The selection of an optimal core function for any moduli set is cast as an integer programming problem.