Design of a balanced 8-modulus RNS

Abstract

In this paper the design of a balanced 8-modulus RNS system is presented. This RNS is based on the modulus set A = {2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-5</sup> - 1, 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-3</sup> - 1, 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-3</sup> + 1, 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-2</sup> + 1, 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-1</sup> - 1, 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-1</sup> + 1, 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> , 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> + 1}; n = 2k, k = 4, 5, 6, ..., which comprises non co-prime moduli. The system is balanced, in the sense that adjacent moduli are of similar word length and achieve fast internal processing and dynamic ranges larger than 32 bits. Its weighted-to-RNS converter is an efficient two-level converter. Its RNS-to-weighted converter is a three-level converter based on a combination of an efficient Chinese Remainder Theorem (CRT), the Mixed Radix Conversion (MRC) technique and an efficient implementation of a 2-channel CRT based on non co-prime moduli.