A Method for Implementing the Operation of Modulo Addition of the Residues of Two Numbers in the Residue Number System
- PDF / 150,948 Bytes
- 10 Pages / 594 x 792 pts Page_size
- 13 Downloads / 172 Views
A METHOD FOR IMPLEMENTING THE OPERATION OF MODULO ADDITION OF THE RESIDUES OF TWO NUMBERS IN THE RESIDUE NUMBER SYSTEM V. A. Krasnobayev,1† A. A. Kuznetsov,1‡ S. A. Koshman,1†† and K. O. Kuznetsova1‡‡
UDC 681.04
Abstract. The paper describes a method for implementing the arithmetic operation of modulo mi addition of the residues of two numbers in the residue number system (RNS). The method is based on the use of modulo M = 2 n - 1 adders, which consist of a set of sequential binary single-bit adders, by introducing and using additional feedbacks. The authors formulate the rules for introducing additional feedbacks, which makes it possible to implement the addition operation for an arbitrary modulo of RNS. Examples of the synthesis of binary adders and examples of the operation of RNS modulo addition of two numbers residues are given. Keywords: computer system, residue number system, small-bit binary adder, positional number system, modular addition. INTRODUCTION The arithmetical operation of addition of two numbers A = ( a1 || a 2 || K || a i || K || a k ) and B = ( b1 || b2 || K || bi || K || bk ) in the residue number system (RNS) is performed by addition of appropriate residues a i and bi modulo mi ( i = 1, k ) independently and in parallel in time on each of k RNS bases [1–3]. Small-bit residues a i and bi in the representation of the terms of the numbers in RNS allows performing the modular addition operation ( a i + bi ) mod mi based on small-bit binary modulo adders. For an ordered (mi < mi +1 ) RNS, performance of number addition operation depends on the time necessary to obtain the result of operation ( a k + bk ) mod mk with respect to the greatest RNS basis mk . One of the methods of implementation of modular addition operation ( a i + bi ) mod mi is based on binary adders [4–6]. This approach provides an ample choice of possible implementations of the inner pattern of such adder. It allows using, to the full extent, the available practical experience of designing binary adders [7–9]. ADDERS OF TWO NUMBERS IN RESIDUE NUMBER SYSTEM One of the main components of a computer system (CS) is adder of two numbers. In particular, adders of two numbers modulo mi can be components of the CS. This type of adders is widely used both in positional number systems (PNS) and in non-positional ones [10–12]. Such problem is especially important for CS that operate in RNS. The adder of numbers A = ( a1 || a 2 || K || a i || K || a k ) and B = ( b1 || b2 || K || bi || K || bk ) in RNS consists of the set of k n-bit adders, n = [ log 2 ( mi - 1) + 1] , modulo mi . In this aspect, constructing adders that operate with respect to an arbitrary modulo mi , performed on logical elements with two stable conditions, is an important scientific and applied problem. 1
V. N. Karazin Kharkiv National University, Kharkiv, Ukraine, †[email protected]; ‡[email protected]; [email protected]; ‡‡[email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 6, November–December, 2020, pp. 192–202. Original article su
Data Loading...
