 Open Access
 Total Downloads : 423
 Authors : Mokhtar Mohammadi Ghanatghestani, Behnam Ghavami , Hossein Pedram
 Paper ID : IJERTV3IS110443
 Volume & Issue : Volume 03, Issue 11 (November 2014)
 Published (First Online): 14112014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
An Adder/Multiplier circuit for OneHot Residue Number System
Mokhtar Mohammadi Ghanatghestani1 , Behnam Ghavami 2, Hossein Pedram3
1Department of Computer Engineering, Science and Research Branch, Islamic Azad University,Tehran, Iran
2Shahid Bahonar University, Kerman, Iran
3Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran
AbstractResidue Number System (RNS) is a nonweighted number system. Residue Number System can be performed parallel, fast, low power and secure arithmetic operations. Arithmetic operations in the Residue Number System, such as addition, subtraction and multiplication are executed high speed and in a short period of time without the need to propagation carry. Therefore RNS can be used for some of applications that require to high speed. For increase speed and reduce power consumption in the RNS a method has been proposed that named OneHot Residue Number System. The delay arithmetic operation with using of this method is equivalent to a transistor, and power consumption in this method is minimal. The main problem with this method is the great increase in the number of transistors they are increased in order m2 (m is the module size). Hence OHRNS are suitable for small modules, and practically using this method is impossible for large modules. Proposed design of OHRNS in this paper generates many operations (such as addition, subtraction and multiplication) of two parameters synchronously, without hardware overhead compare to one original design of OHRNS.
KeywordsComputer Arithmetic; one hot Adder/Multiplier; OneHot Residue Number System (OHRNS); Residue Number System (RNS)

INTRODUCTION
Residue Number System is an integer, unconventional and non weighted number system. RNS can be supporting high speed and parallel arithmetic operation. In RNS, an integer is defined by a set of residue with shorter binary representations, which can be processed independently and in parallel. Because the arithmetic operations such as addition, subtraction and multiplication are able to execute in RNS very speed without the need to propagation carry, RNS arithmetic is used in the numeral realtime applications. The inherent fault tolerant properties of the residue number system can be able used for reliable and high performance applications.
The several applications of Residue Number System are as follows:
1implementing DSP algorithm [1] 2Image processing [1,2,3,4]

Numberal Filters [5,6]

Numberal Communication [7]

cryptography algorithm [8]
RNS architectures are also inherently fault tolerant against faults and easily provide fault detection and correction [9].
The important parameters in design and implementing the arithmetic circuits are hardware area, speed and power consumption of arithmetic units.
OneHot is the method that this ability has created arithmetic operation in a RNS that can implementation of the system minimum power consumption and maximum speed. But other important parameter is hardware area in the implementation of arithmetic operation circuits. And hardwarebased provider OneHot is a barrel shifter, which is a regular and simple structure. Adders and multipliers are barrel shifterbased and, therefore, regular and simple.
Although the OneHot the implementation arithmetic circuits is suitable for small modules. On the one hand in some applications need to the large dynamic ranges but for achieving a large dynamic range, must the increased in module size so number of transistors increased in order m2 where m is the module size. If the selected module is m, then the amount of hardware in modular add or subtract in OHR using barrel shifter is in the order of m2.This rate will cause problem when two or more barrel shifters are needed in the circuit. For example when we need both add and subtract operations then we have two barrel shifters. In this case amount of hardware is equal to 2m2. And if we need three operations (such as addition, subtraction and multiplication) amount of hardware is equal to 3m2. In this paper a new design for OHR add/multiply circuit is presented that generate both modular add and multiply results. In this design just one barrel Shifter structure is used.
The rest of this paper is organized as follows: argue about Residue Number System (RNS) in section II and OneHot RNS (OHRNS) in section III. In section IV present design for one hot Adder/Multiplier. And compare proposed structure with basic OHRNS structure in section V, finally conclusion is in section VI.


RESIDUE NUMBER SYSTEM
Residue Number System is a nonconventional and non weighted number system. This System can be performed parallel, fast, low power and secure arithmetic operations.
RNS Advantage a cause which many used in the arithmetic applications such as numeral signal processing systems, image processing, Numeral Filters, implementing DSP algorithm, ad hoc networks and reliable systems is used. On for general is very used of RNS in the systems that usage that a range of numbers and applying addition, subtraction and multiplication of very is repeats.
Residue Number System is defined by moduli set such as 1, 2, 3, , . All modules are positive integers and selection of modules is very important in the Residue Number System. also while all the modules are relatively pair wise prime the system will have the largest possible dynamic range which equals [, +M ) in which is an integer and M is:

ONEHOT RNS
The OHRNS is a method for represents RNS operands using technique onehot encoding. This technique of encoding allows implementation of arithmetic circuits with lower power consumption and maximum speed. The delay arithmetic operations in this method equal one transistor. Because all major operations like as addition, subtraction, multiplication
=
=1
(1)
and modulus conversion are performed using barrel shifters result used of this method is very useful.
Any integer X that X< +M in Residue Number
System show by the set of reminder(1, 2, 3, , )
For every mi Moduli remainders are from zero to mi 1.
.and according to the following formula calculated remaining are:
(1, 2, 3, , ) (2)
Where
= , = 1,2,3, , (3)
And denotes the operation x mod mi. If the integers X and Y have RNS representations (1, 2, 2, , ) and
For mi moduli remainders are shown in fig. 1that OneHot representation a signal line is allocated for each of these numbers: The activity of each signal shows the similar remainder with it. In this representation system in each moment only one of the lines are active. By changing the entrance amount, the amount of two lines changes at maximum level. Therefore the power consumption is minimum level.
0
1
(1, 2, 3, , ) respectively, then the RNS representation of = (where o denotes addition, subtraction, or multiplication) is given by:
Line Number 2
(Digit Value)
Only one line active at any time
(1, 2, 3, , ) (4)
mi 1
Fig. 1. OHRNS representation for number x i .
OneHot Residue Number System is simple and rapid and
=
, = 1,2,3, , (5)
has regular structure. For implementation onehot operands, addition is used of a circuit that named barrel shifter. This
What was expressed to up subject understood that arithmetic operations in the RNS executed to parallel, high seed and without any propagation carry. [10,11,12,13,14].
Also for calculate X number of the remainder used of Chinese Remainder Theorem (CRT). This theorem can be expressed as follows:
circuit shift of one operand by an amount equal to the others value. Barrel shifter, constructed using pass transistors or transmission gates. Which in fig. 2 (a), the two inputs are specified as shift and data to make the internal operation [fig. 2 (b)] easily understood. The barrel shifter generates, in parallel, all possible rotations of the data input, and selects one of them for output. Which one is selected is determined by the shift input.
=1
=
Where:
.
Ã— (6)
The basic hardware in OneHot is Barrel shifters. In addition to mi module one of the operands are shifted as the other shifter. The delay of this circuit is equivalent to a transistor.
=
=1
(7)
Shift Input
And
=
, = 1
, = 1,2,3, , (8)
miLine
Modulo mi Adder
Output
miLine
And the 1 specified in the formula is defined as a
multiplicative inverse of Mi modulo mi [12,13].
In the Residue Number System, executing arithmetics on the remaining to be done independent and separately. Hence if the one remaining fault occurs its effect on another is not transferred as a result of the inherently RNS architecture is fault tolerant. Therefore the characteristics of the Residue Number System used in applications that are needed to reliability.
Data Input
miLine
(a)
Input 1
mi 1
mi 1
0
1
2 1 0
2 1 0
3 2 1
4 3 2
0
1
Input 2
2
mi 1
mi 2
1
Output
(b)
0 mi 1
Fig. 2. OHRNS adder: (a) symbol and (b) architecture.
In fig. 3 a onehot addition is shown for moduli 5 on transistor level. And the transistor delay is shown clearly in this figure. The TG version differs in that it uses transmission gates in place of the pass transistors, and lacks the dual output buffers. Furthermore, the complements of the shift inputs are generated by inverters, one per line, in order to drive the control inputs of the transmission gates.
In4
Fig. 4. one hot adder for module 5
Multiply circuit is similar to add circuit with one difference. This difference is order of output to the circuit. In fig. 5, circuit of a multiplier for module 5 is shown.
In3
In2
In1 In0
Out 0
Out1
Out 2
Out3
Out 4
Sh4
Sp
Sp
Sp
Sh0
Fig. 3. Modulo 5 OHRNS adder model.
One of the important problems of OneHot System is that it couldnt be implemented for large moduli since the number of transistor are increased. Main centralization in this paper is rectifying this problem.

PROPOSED DESIGN FOR ONEHOT ADDER/MULTIPLIER Delay of OneHot RNS is equal the delay of only one
transistor. However, the amount of needed hardware is in the order of m2, where mis selected module. For example in fig. 4, an adder for module 5 (m=5)is presented. Delay of this adder is equal to delay of one transistor. 25 transistors are needed to compose this circuit.
Fig. 5. one hot Multiplier for module 5
As shown in fig. 4 and fig. 5 for every value of input 1 and input 2, only one transistor will be activated. Therefor only one line in output will be activated. For example if line number 2 of input 1 and line number 3 of input 2 are active, only one transistor in adder circuit switched on and line number 0 in adder output will be activated. And in multiplier circuit line number 1 in multiplier output will be activated.
Proposed adder/multiplier circuit for OHR system has two inputs, a and bfor barrel shifter structure, and two outputs, addoutand multiplyout. Each of them has five bits. That is, the module is 5. fig. 6 shows proposed adder/multiplier in OHR for module in special m=5.

COMPARISON
When ever we need both add and multiply operations then we have two barrel shifters. In this case amount of hardware is equal to 2m2. And if we need three operations (such as addition, subtraction and multiplication) amount of hardware is equal to 3m2. Proposed design one hot adder/multiplier circuit generates both modular add and multiply results. In this design just one barrel Shifter structure is used.

CONCLUSION
Proposed design in this paper generates two operation results (addition and multiplication) synchronously, without change delay, and power consumption in original OHRNS. This design can use for every module and every operation. Proposed method is a MISD and can be used for parallel and pipe line processing.
REFERENCE
Fig. 6. one hot Adder/Multiplier for module 5
The structure of the proposed one hot Adder/Multiplier can be described as follow.
If line number i (ai) of input 1 and line number j (bj) of input 2 are active, only one transistor of proposed circuit switched on. As shown in fig. 7 , if output of active transistor connected to proper line in adder output and multiplier output, only one line of addout and one line of multiplyout will be activated. Therefor proposed design generates addout and multiplyout synchronously.
Fig. 7. one transistor of proposed one hot Adder/Multiplier circuit
Proposed design shown in figure 6 present for addition/multiplication operation in module 5. But this method can use for every module 'm' and every operation.

W. L. Freking and K. K. Parhi, 1997, Lowpower FIR numberal filters using residue arithmetic, 31st Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, Vol. 1, pp. 73943.

P. G. Fernandez, et al.,2000, A RNSBased MatrixVectorMultiply FCT Architecture for DCT Computation, Proc. 43rd IEEE Midwest Symposium on Circuits and Systems, pp. 350353.

R. Conway and J. Nelson,2004, Improved RNS FIR Filter Architectures,IEEE Transactions On Circuits and Systems II, Vol. 51, No. 1, pp. 2628.

A. D. Re, A. Nannareli and M. Re, 2004, A Tools for Arithmetic Generation of RTLLevel VHDL Description of RNS FIR Filters, IEEE Proceeding of the Design, Automation and Test in Europe Conference and Exhibition, pp. 686687.

N. Szabo and R. Tanaka, 1967, Residue arithmetic and its applications to computer technology, New York, McGrawHill.

F. Taylor, 1985, A Single Modulus ALU for Signal Processing, IEEE Transactions on Acoustics, Speech, Signal Processing, Vol. 33, pp. 13021315.

J. Ramirez, et al., 2002, Fast RNS FPLBased Communications Receiver Design and Implementation, Proc. 12th Intl Conf. Field Programmable Logic, pp. 472481.

S. Yen, S. Kim, S. Lim and S. Moon, 2003, RSA Speedup with Chinese Remainder Theorem Immune against Hardware Fault Cryptanalysis, IEEE Transactions On Computers, pp. 461472.

Konoshita E. and lee K., 1997, A Residue Arichmetic Extension for Reliable Scientific Computation, IEEE Trans. On Computers, Vol. 46, No.2.

A. Chren, Jr., 1998, OneHot Residue Coding for Low DelayPower Product CMOS Design, IEEE Transactions On Circuits And Systems II: Analog And Numberal Signal Processing, Vol. 45, No. 3.

A. F. Gonzalez, and P. Mazumdar, Redundant Arithmetic, 2000, Algorithms and Implementations, Integration: The VLSI Journal, Vol. 30, No. 1, pp. 1353.

M. Hosseinzadeh, K. Navi and S. Timarchi, 2006, Design Residue Number System Circuits in Current mode, 14th Iranian Conference of Electrical Engineering.

M. Hosseinzadeh, K. Navi and S. Timarchi, 2006, New Design of 43 Compressor, 11thInternational CSI Computer Conference of Iran.

S. Hanzawa, T. Sakata, K. Kajigaya,R. Takemura, and T. Kawahara, 2005, A LargeScale and LowPower CAM Architecture Featuring a OneHotSpot Block Code for IPAddress Lookup in a Network Router, IEEE Journal of SolidState Circuits, Vol. 40, No. 4.