The purpose of this article is to consider an algorithm for synthesizing the structure of the adder of two residuals ai and bi numbers A (a1, a2 ,..., ai ,..., ak ) and B (b1,b2 ,...,bi ,...,bk ) for an arbitrary value of the module mi of the residual class system (RCS), by organizing interbit connections between binary one-bit adders (BOA), the combination of which makes up the structure of modulo adder. The algorithm for the synthesis of adders by arbitrary modules is based on the usage of existing adders by module M 2n 1 , which consists of a set of sequentially located BOA, by introducing and using additional inter-bit connections of the form i j . Specific examples of the synthesis of structures of binary adders for various values of the RCS modules mi are given.
The operation of adding two numbers is the main operation, which is implemented by a computer
system (CS), both in a positional binary notation (PN) and in a non-positional notation of residual
classes [
The article discusses the synthesis of an adder of two residues of numbers by an arbitrary RCS module mi. Synthesis of modulo adder is a procedure for constructing the structure of a non-positional adder from positional binary one-bit adders (BOA). In a non-positional adder by an arbitrary module mi, an addition circuit is used, which is implemented in the structure of adder by module M 2n 1 . This is achieved by organizing and using additional inter-bit connections i j , in the general case, between the j th and the i th BOA of the adder module M .
An arbitrary initial structure of a n -bit binary adder by the module M 2n 1 is shown in Fig. 1.
The task of an adder by module mi synthesis is to ensure the modular addition of two residues for given modules by means of an adder by module M 2n 1 . In this article, this is achieved by introducing into the adder by module M additional links of the form i j , where the sign i j denotes the connection between the output of the j -th BOA and the input of the i th BOA. A diagram of the organization of such an additional connection between the output of the j th BOA and the input of the i th BOA is shown in Fig. 2.
The essence of constructing adders by module RCS is as follows. In the initial adder by module
M 2n 1 , on the basis of certain rules, additional connections i j are formed [
In the general case, the modulo adder synthesis algorithm consists of a sequence of performing the following operations.
1. Obtaining the structure of the adder by module M 2n 1 , where
n [log2 (mi 1)] 1 .
2. Determination of the adder binary bits Si for which equality Si 0 is true. The process of determining the condition Si 0 is based on the representation of the module in binary code. 3. Additional connection i j begins with the most significant bit of the adder.
4. Additional connection i j goes to the BOA input, for which Si 0 .
Two examples of synthesis of structures of adder are considered.
Example 1. mi 53 . The stages of the synthesis of an adder by the module of RCS are as follows. 1. In accordance with the size of the module mi 53 , the number n of BOA of an adder by the module M 2n 1 is determined. For the module mi 53 there is
n [log2 (mi 1)] 1 [log2 (53 1)] 1 6 .
The structure of the adder by module will be the following (Fig. 3).
M 2n 1 63
The initial structure of the adder by module mi 53 without additional connections i j will be the same.
2. Module mi 53 in binary code S6 S5 S4 S3 S2 S1 is 110101, which means
S6 1, S5 1, S4 0 , S3 1 , S2 0 and S1 1.
From the form of the module mi 53 which is represented in the binary code,
S2 S4 0 is determined.
3. Based on the obtained results, the structure of the adder by the module mi 53 is represented in the following form
In accordance with the synthesis method, two additional connections 46 and 26 are introduced into the adder by module M 26 1. In order to check the correctness of the synthesis of the adder by module mi 53 , the value of the RCS module M mi for a given adder structure is determined. Based on the given structure of the adder (Fig. 4), a number of structures of individual parts of the adder by the module mi 53 are composed. The first part of the adder structure is shown in Fig. 5.
The first part of the adder structure module M1 will be the following
M1 3 5 4 1 .
The second part of the adder structure is shown in Fig. 6.
For this part of the adder, the structure module M 2 will be the following
M 2 M1 3 2 1 ( 6 5 4 1) 3 2 1 .
For adder, by module, the value of module M mi of RCS will be determined as follows (fig. 4-6) mi M 2 1 1 ( 6 5 4 1) 3 2 1 1 1 (23 1) 22 1 2 1 53 .
Based on the performed calculations, there is the conclusion that the synthesis of the adder by module mi 53 (fig. 4) was carried out correctly.
Example 2. mi 97 . The stages of the synthesis of an adder by the module of RCS are as follows. 1. In accordance with the size of the module mi 97 , the number n of BOA of an adder by the module M 2n 1 is determined. For the module mi 97 there is
n log2 mi 1 1 log2 97 1 1 7 .
The structure of the adder by module will be the following (Fig. 7). 2. Module mi 97 in binary code S7S6 S5 S4 S3 S2 S1 is 1100001, which means
S7 1, S6 1, S5 S4 S3 S2 0, S1 1.
3. Based on the obtained results, the structure of the adder by the module mi 97 is represented in Fig. 8.
In accordance with the synthesis method, four additional connections Х 57 , Х 47 , Х 37 , Х 27 are introduced into the adder by module M 27 1 . In order to check the correctness of the synthesis of the adder by module mi 97 , the value of the RCS module M mi for a given adder structure is determined.
The first part of the adder structure is shown in Fig. 9.
The first part of the adder structure module M1 will be the following M1 7 6 5 1 .
The second part of the adder structure is shown in Fig. 10.
The first part of the adder structure module M2 will be the following M 2 M1 4 1 .
The third part of adder structure is shown in Fig. 11.
The first part of the adder structure module M3 will be the following M3 M 2 3 1.
The fourth part of the adder structure is shown in Fig. 12.
The first part of the adder structure module M4 will be the following M 4 M3 2 1 .
The fifth part of the adder structure is shown in Fig. 13. The value of module mi :
M1 7 6 5 1 (Fig. 9);
M 2 M1 4 1 7 6 5 1 4 1 (Fig. 10);
M3 M 2 3 1 7 6 5 1 4 1 3 1 (Fig. 11);
M 4 M 3 2 1 7 6 5 1 4 1 3 1 2 1 (Fig. 12);
M5 M4 1 1 7 6 5 1 4 1 3 1 2 1 1 1 (Fig. 13).
In this case, the result of the synthesis of the adder by module mi 97 (Fig. 8) is correct.
The given examples of the synthesis of the structure of adders by the module of RCS confirm the possibility of practical usage of the algorithm which is considered in the article.
The article considers an algorithm for synthesizing the structure of adders by the module mi of RCS. The algorithm for the synthesis of adders is based on the usage of existing adders by modules M 2n 1 , which are widely used in CS, operating both in the PN and in the RCS. The article directly provides an algorithm for the synthesis of an adder by module mi . The algorithm is implemented by introducing and using additional inter-bit connections i j . The article formulates the rules for introducing these additional connections. The usage of additional connections (based on the structure of adder by module M 2n 1 ) allows creating an adder that implements the operation of adding two residues ai and bi of numbers. A set of k adders by the module is an adder of two numbers A (a1, a2 ,..., ai ,..., ak ) and B (b1,b2 ,...,bi ,...,bk ) in RCS. Specific examples of the synthesis of adders by the module for various values of the RCS modules mi are given.
This work was supported in part by the National Research Foundation of Ukraine under Grant 2020.01/0351.