 Open Access
 Total Downloads : 0
 Authors : Uday J, Sudarshan Patwardhan, Shishir Rai, Sushmitha B, Vaishnavi Devi
 Paper ID : IJERTCONV6IS15060
 Volume & Issue : ICRTT – 2018 (Volume 06 – Issue 15)
 Published (First Online): 05012019
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Implementation of 16 bit Hybrid Modulo 2n1 Adder
Implementation of 16 bit Hybrid Modulo 2n1 Adder
Uday J Asst. Professor SJEC, Mlore
Sudarshan Patwardhan
Scholar SJEC,Mlore
Shishir Rai Scholar SJEC, Mlore
Sushmitha B Scholar SJEC, Mlore
Vaishnavi Devi
Scholar SJEC, Mlore
Abstract: There is a growing demand for fast and efficient adders. There are number of architectures proposed to cop up with the growing demands. A variety of prefix adders are discussed in literature to achieve area and performance optimization. Modular addition plays an important role in data encryption standard, RNS application. In this paper a newVLSI circuit architectures for addition modulo 2n1 are presented, which allows the implementation of highly efficient combinational circuits for modular arithmetic. To realize the architecture we use a new prefix operator known as Star operator and Sparse carry computation unit.
The architectures are implemented on Xilinx Spartan III fieldprogrammable gate array (FPGA) using ISE 8.1. The results indicate that, on an average, the implemented architectures are better in terms of slices, LUT's and memory utilization by comparing all formal proposals.
General Terms: Slices, LUTs, delay, architecture. Keywords: Hybrid Parallel Prefix adders, Star, Sparse.

INTRODUCTION
Modulo 2n 1 adders are used in various applications, ranging from Residue Number System (RNS) applications [1] faulttolerant computer systems [2], and cryptography. In RNS logic, each operand is represented by its moduli with respect to a set of numbers comprising the base. Each of the numbers of the base must not have any common factor with any of the other numbers of the base. Most often, the base consists of three numbers: 2n 1, 2n , 2n +1. Many solutions have been presented for fast modulo 2n 1 addition. In [5] modulo adders are proposed that use a parallel prefix carry computation unit along with an extra prefix level that handles the endaroundcarry. In [6] it was shown that the recirculation of the endaroundcarry can be performed within the existing prefix levels. Therefore, the need of the extra prefix level is cancelled and parallel prefix modulo 2n 1 adders are derived that can perform carry computation in log2n levels. However, the routing requirements are increased. In [7] select prefix modulo 2n – 1 adders have been proposed, that aim at reducing the area
complexity of the parallelprefix structures but suffer from significant delay penalties.
In this paper a new architecture of modulo 2n 1 adder is implemented. This architecture uses new operator called star operator.

PARALLEL PREFIX ADDER
Prefix: The system output is dependent on initial input. Parallel: Execution of an operation in parallel.
This is done by segmentation into smaller pieces that are computed in parallel. We know that computation of the carry input signal for each bit addition is the most critical and time consuming. The carry look ahead adders (CLA), gives an idea how to produce the carry input signals for individual bit addition. This is achieved by generating two signals, generate (gi) and propagate (pi) using the equations
= AND = OR (1)
The carryin signal for any adder block is calculated by
using the formula
+1 = + ( )(2)
Addition of two operands, A= (a0, a1an1) with B =
(b0, b1.bn1) using parallel prefix adder is shown in Fig.1. It mainly consists of three stages, first is Pre Computation or Generation stage, where we find three signals, carry generation (gi), carry propagation (pi) using equation (1) and half sum (hi) using the relation
hi = aixor bi (3)
Second stage is Carry Computation, where we find carry bit for each input bit using carry generate (gi) and carry
Fig 1: Block Diagram of parallel prefix adder
propagate (pi) signal, using equation (2). For computation of carry bit signal we use different tree architecture such as HanCarlson, Koggestone, BrentKung, Ladner Fischer, etc. Finally the last stage is PostProcessing or Summation stage, where we will find final sum for each bit using the following equation
Si = hixor C i1 (4)
f
Parallel Prefix adders compute carryin at each level of addition by combining generate and propagate signals in a different manner (depending upon tree architecture). The implementation o ,and , operators which are used in parallel prefix adders is shown in Fig.2
Fig. 2: Implementation of Operators
The black operator receives two sets of generate and propagate signals (gi , pi),(gj , pj), computes on it and produces a set of generate and propagate signals, (go , po) by using the following equations
(Gi:j, Pi:j) = (go , po) = (gi , pi) o (gj , pj)
= + ( ) and = (5)
The "o" operator in (5) defines prefix operation between a
pair of generate and propagate signals for carry computation.
2.1 Hybrid Parallel Prefix AdderA new parallel prefix adder architecture is developed by using black and Star operators, called Hybrid Parallel Prefix adder. Black operator as been already defined in section II. The Star operator is shown in Fig. 3.
(gi , pi) (gj , pj) (gk , pk)
(g0 , p0)
Fig 3: Star Operator
The Star operator, which takes three pairs of generate and
propagate values ( , ), ( , ), ( , ) asinputs and produces a pair of generate and propagate output values
( , ) as follows
= + ( ) + ( ) (6)
=

MODULO2 1ADDER
4. 16BIT MODULO2 1 ADDER USING HYBRID
SPARSE STRUCTURE
For large number of bits, there will be more number of interconnection wiring between the black operators in the normal prefix structure, if only black operators are used,
i.e. Using additional carry increment stage (Fig.4a) and EAC (Fig.4b).
Fig 4: Modulo 281 Adder using (a) Additional Carry Increment, (b) End around[8]
This large number of prefix operator and wiring between them can be reduce using Hybrid parallel prefix operator, which is a combination of black and Star operator (Fig.3 ) Therefore by using sparse adder there will be a chance of saving considerable amount of area. Fig.5 shows the architecture of modulo 2161 adder using Hybridsparse structure.
Fig 5: Modulo 281 Adder using Hybrid Sparse

SYNTHESIS RESULTS AND COMPARISON The HybridSparse modulo 2n1 adder for 8bit and 16bit are compared with additional carry increment structure, EAC, Hybrid with Sparse All architectures of modulo adder are implemented using Xilinx ISE 8.1. The device used to implement the architecture is Spartan3 XC3s400 4tq144. Table I, shows Synthesis Result. Fig.6 shows the snapshots simulation of modulo (2161) adder
Fig. 6 Modulo 216 1 adder waveform
Parameter
Additional Carry Increment
End around carry
Hybrid with Sparse
8
bit
16
bit
8bit
16bi t
8bi t
16
bit
Slices
20
46
23
64
16
35
4i/p LUTs
34
80
40
112
27
60
Propagati on delay ns)
26.6
3
34.91
14.06
15.9
1
18.
522
18.66
Table I: Synthesis Result

CONCLUSIONS
Analysis of tabulated result tells that the 8bit and 16bit modulo 2n1 adder and multiplier based on HybridSparse tree is areaefficient, since in proposed architecture the number of slices and LUTs are less compared with other architectures. Hybrid Sparsetree architectures are used in less area utilization applications.

REFERENCES
Computer Systems, PrenticeHall, 1989.
[3] F. Halsall, Data Communications, Computer Networks and Open Systems, Addison Wesley, 1996. [4] R. V. K. Pillai et aI., "A Low Power Approach to Floating Point Adder Design," in Proc. of the IEEE International [5] R. Zimmerman, "Efficient VLSI Implementation of Modulo (2nÂ± 1) Addition and Multiplication," in Proc. of14th Symp. Computer Arithmetic, April 1999, pp. 158167. [6] L. Kalampoukas et aI., "HighSpeed ParallelPrefix Modulo 2n 1 Adders," IEEE Trans. on Computers, vol. 49, no. 7,pp. 673680,JuI. 2000.Conference on Computer Design, Oct. 1997, pp. 178185. [7] Efstathiou et aI., "Modulo 2n 1 Adder Design Using Select Prefix Blocks," IEEE Trans. on Computers, vol. 52, no. 11,pp. 13991406,2003. [8] G. Dimitrakopoulos et aI., "A Family of ParallelPrefix Modulo 2n 1 Adders," in Proc. of IEEE ASAP, 2003, pp. 326 336. [9] Haridimos T. Vergos and andGiorgosDimitrakopoulos, et all,New Architecture for Modulo 2n 1 Adder, IEEE Transaction on computer, IEEE 2009