Algorithm for constructing the adder of residues of two numbers modulus

Abstract

An urgent scientific and applied problem is the problem of constructing the adder structure, which is performed on logical elements with two stable states and operates according to an arbitrary modulo m_i. This type of adder is used both in the positional binary number system (PNS) and in the non-positional number system in residual classes (RNS). If the residuals a_i and b_i of numbers  А = (a₁||a₂||…||a_i||…||a_k ) and B = (b₁||b₂||…||b_i||…||b_k ), represented in the RNS are given in a binary PNS, then the adder of two residuals a_i and b_i modulo m_i is a set of n = [log₂ (m_i - 1)+1] binary one-bit adders (BOBA). Simultaneously, all BOBA are connected as positional binary adders. The purpose of the article is to develop an algorithm for constructing the adder structure of two residuals a_i and b_i of numbers A and B for an arbitrary modular value m_i  of RNS. This process is realized by organizing new inter-bit connections of BOBA, using a positional adder modulo M = 2ⁿ - 1. It is noted, that there are special sets of modules that are used when processing data in RNS. So, when performing the operation of modular addition of the remainders of numbers, one of three mutually pairwise primes (of the form M = 2ⁿ - 1, M = 2ⁿ or M = 2ⁿ + 1) can be used. It is shown that in order to synthesize an adder modulo m_i  RNS, in the adder structure modulo M, it is necessary to appropriately form the additional connections.