Published on: **Mar 4, 2016**

Published in:
Engineering

Source: www.slideshare.net

- 1. Design and Implementation of Fast Adder using Redundant Binary Signed Digit Shantanu Thakre , Viplav Mahajan , Shailesh Shukla , Rohan Sasan , Pankaj Jibhkate , Sagar Deoghare. Guided by: Mrs. Gouri Morankar Shri Ramdeobaba College of Engineering and Management, Nagpur-13 achievable processing speed. For making the processing ABSTRACT faster a carry free addition technique is adopted byIn this paper we present the design of an Arithmetic Logic using Redundant Binary Number System. The propertyUnit (ALU) based on Redundant Binary signed Digit of carry propagation chain elimination tends to make(RBSD) Number System. A redundant binaryrepresentation is a numeral system that uses more bits the processing faster. In this paper, the RBSD based fastthan needed to represent a single binary digit because of adder is designed using VHDL.which most numbers have several representations. Thisunique feature of RBSD number system allows addition CARRY FREE ADDITION USING REDUNDANTwithout using a typical carry. The RBSD ALU is designed BINARY SIGNED DIGITusing VHDL and its RTL view is generated by its FPGA The redundant binary representation (RBR) is aimplementation .The FPGA implementation is done in numeral system that uses more bits than needed to represent a single binary digit so that each number willXilinx ISE environment. have several representations. RBR is a place-value INTRODUCTION notation system. In RBR digit set will have more digitsAddition is the most important and frequently used than the radix and digits are pairs of bits, that is, forarithmetic operation in computer systems. Generally, two every place RBR uses a pair of bits. RBR is unlikemethods can be used to speed up the addition operation. usual binary numerical systems, including two‟sOne is to explicitly shorten the carry-propagation chain complement, which use single bit for each digit.by using circuit design techniques, such as detecting the The value represented by an RBR digit can becompletion of the carry chain as soon as possible, carry found using a translation table as shown in Table 1.look-ahead, etc. Another is to convert the operands from This table indicates the mathematical value of eachthe binary number system to a redundant number system, possible pair of bits. As in conventional binarye.g., the signed-digit number system or the residue representation, the integer value of a givennumber system, so that the addition becomes carry-free representation is a weighted sum of the values of the(CF). This implicitly eliminates the Carry-propagation digits. The weight starts at 1 for the rightmost position and goes up by a factor of 2 for each next position.chain so that fast addition can be done, at the expense of Usually, RBR allows negative values. There is noconversion between the binary number system and the single sign bit that tells if a RBR represented number isredundant number system. positive or negative. Most integers have several FAST ADDER can be designed using ripple carry possible representations in an RBR. An integer valueor carry look ahead adder. But in case of ripple carry can be converted back from RBR using the followingadder the delay will be more as the carry should be formula, where „n‟ is the number of digit and d k is thepropagated entire bit width. So speed will be reduced. interpreted value of the kth digit, where „k‟ starts at 0 at the right most position [3]:Carry look ahead adders are faster than ripple carryadders but the complexity of the circuitry increases as thenumber of bits increases. Use of non-conventionalnumber systems in designing ADDER is gainingattention in recent years because of their facility toprovide carry free addition thus enhancing the
- 2. Digits Interpreted value 00 -1 Example: Carry –Free addition using redundant signed 01 0 radix 2 10 0 In conventional binary number system radix 2 number 11 1 digit set contains 0, 1. The number of digits equal to radix. Table 1.Translation table for Redundant Binary Signed Digit [5] Example: Number 6 can be represented in binary as belowThe redundant binary signed digit number (RBSD) 0110representation makes it possible to perform addition Number 4 can be represented as belowwith carry propagation chains limited to a single digit 0100 In case of redundant Signed radix 2 number digit setposition and has been used to speed up the arithmetic contains {-1,0,1}. The number of digits present in theoperations. In order to cope with the problem of carrypropagation the most appropriate approach is digit set will be more than the radix. So each numberelimination of carry propagation. If the numbers can be can be represented in many ways.represented in such a manner that addition does notrequire carry propagation then the addition is said to be Example: Number 6 in decimal can be represented in redundant binary as follows.carry-free or carry eliminated addition, In case of 0 1 1 0 ------- 6RBSD all digit additions can be done simultaneously.The application of interval arithmetic in which carrypropagates only one position and no additional carry is 1 0 -1 0 ------- 6generated; makes possible carry free addition. Number 4 can be represented in redundant binary asThe RBSD carry propagation free addition is follows 0 1 0 0 ---------- 4performed in two steps [5]: 1 -1 0 0 ---------- 4Step 1: In order to eliminate carry, at each position thetransfer digit ti and interim sum digit wi are determined In case of conventional binary addition there will beaccording to Table 2. If Xi and Yi are the two operands carry propagation. Carry will be propagated till thethen the relationship between Xi, Yi, ti and wi is end.mathematically represented as In case of conventional binary addition there will be carry propagation. Carry will be propagated till the Xi+ Yi = 2ti+wi end. Addition in case of RBSD is carry free.Step 2: The incoming transfer digit is added with the In case of RBSD addition the two operands will beinterim sum to obtain the final sum digit with no new added to get the position sum (pi). Then the positiontransfer digit. This step is mathematically represented sum will be divided into interim sum (wi) and transferas digit (ti). Then interim sum and transfer Si= wi+ti digit is added to get the final sum.Where wi is interim sum, ti is transfer digit and Si is In case of conventional binary there are no such steps.sum digit. Let the two operands be Xi = 0 1 1 0 andXi Yi Xi+Yi ti wi Yi = 0 1 0 1-1 -1 -2 -1 0 Xi = 0 1 1 0 ------- (6)10-1 0 -1 -1 1 Yi = 0 1 0 1 ------- (5)100 -1 -1 0 -1-1 1 0 0 01 -1 0 0 0 The final sum should be (11)10 Adding these two numbers using binary. 0 0 0 0 0 0 1 1 0 1 1 0 1 1 -1 0 1 1 0 ---- Xi 0 1 0 1 ---- Yi 1 1 2 1 0 ------------------- Table 2. Transfer Digit and Interim Sum for 1 0 1 1 ---- si Redundant Binary Radix 2 [4]
- 3. The steps involved in adding the two operands using In the RBSD addition first, the 4 bit input numbers RBSD are as below. Xi and Yi are converted into RBSD representation and then each digit of number is converted into its Step 1. Both the operands are added to get the position interpreted value of 2 bits each and then these bits are sum, pi. given to the inputs of full adders as shown in fig. above. As shown bit of one full adder and bit of final Step 2. Interim sum wi and transfer digit ti are sum are initially set to logic 1 and logic 0 respectively. determined from Table 2. The interim sum and transfer After addition process the result can be again digit are selected in such a way that they should be converted into decimal equivalent by the formula as within the digit set i.e. -1,0,1 and after adding interim given in equation [A]. sum and transfer digit the final sum also should be in the selected digit set. ADVANTAGES OF RBSD ADDER Step 3. Transfer digit is added with the interim sum to [1] Carry free addition get final sum si. ---- 0 1 0 1 1 --- (11)10 [2] Independent of word length [3] Highly efficient 0 1 1 0 xi [4] Improved delay +0 1 0 1 yi -------------------------- COMPARISON WITH DIFFERENT TYPES OF 0 0 -1 1 wi ADDERS0 1 1 0 0 ti(0 1 1 -1 1)-------- si= (11)10 DESIGN AND IMPLEMENTATION OF RBSD BASED FAST ADDER Xi SUM RBSD Siinput ADDER Carry Yi Ci Fig.1 Efficiency vs. No. of bits of different adders Fig.1 Pin out diagram of N bit RBSD adder As shown in above figure the efficiency of RBSD adder goes on increasing for large no. of bits which very advantageous as compared to other adders like Fig. 1 shows the pin out diagram of RBSD CLA, CSA, and RCA etc. adder in which Xi and Yi are N-bit long inputs and Si and Ci are sum and carry outputs respectively.Block diagram of 4-bit RBSD fast adder is as shown in figure below: Fig.2 Delay vs. No. of bits of different adders Fig.2 Block diagram of 4 bit RBSD adder
- 4. We can see from fig 2. that the time delay of RBSD REDUNDANT BINARY SIGNED DIGIT ADDER adder remains constant and is less for large no. of Bits also which is also an advantageous property for RBSD adder as compared to other adders like RCA,CLA etc. SIMULATIONS RIPPLE CARRY ADDER CONCLUSION From the above given descriptions we can see that as compared to other adders, RBSD adder is CARRY LOOK AHEAD ADDER 1. Highly efficient with the increase in no. of bits 2. Time delay is constant and less which means the speed of this adder is very high. 3. Complexity of this adder is moderate. REFERENCES [1] Vishal Awasthi et al. / International Journal of Engineering Science and Technology (IJEST) [2] Louis-Philippe Lessard, “Fast Arithmetic on FPGA Using Redundant Binary Apparatus”,2008 [3] Rakesh Kumar Saxena, Member IACSIT, Neelam Sharma and A. K. Wadhwani, “Fast Adder Design using Redundant Binary Numbers with Reduced Chip Complexity”, IACSIT International Journal of Engineering and Technology, Vol.3, No.3, June 2011 [4] Avizienis, A., “Signed digit number representation for fast parallel arithmetic”, IRE Trans. Electron Computer, vol EC-10, pp. 389- 400, sept.1961.
- 5. [5] Rajashekhar, T .N. and Kal, O., “Fast Multiplier Design using[6] Redundant Signed- Digit Numbers”, International Journal of Electronics, vol .69, no. 3, pp –359-368, 1990