UNIVERSITY OF MASSACHUSETTS Dept of Electrical Computer Engineering Digital Computer Arithmetic CE666 Koren Part 5a 1 ECE 666 Part 5a Fast Addition Israel Koren Spring 2008 Copyright 2008 Koren Ripple Carry Adders Addition most frequent operation used also for multiplication and division fast twooperand adder essential Simple parallel adder for adding xn 1 xn2 x0 and yn 1 yn 2 y0 using n full adders Full adder combinational digital circuit with input bits xi yi and incoming carry bit ci and output sum bit si and outgoing carry bit ci 1 incoming carry for next FA with input bits xi 1 yi 1 si xi yi ci ci 1 xi yi ci xi yi exclusive or AND OR CE666 Koren Part 5a 2 Copyright 2008 Koren Parralel Adder with 4 FAs Ripple Carry Adder In a parallel arithmetic unit All 2n input bits available at the same time Carries propagate from the FA in position 0 with inputs x0 and y0 to position i before that position produces correct sum and carry out bits Carries ripple through all n FAs before we can claim that the sum outputs are correct and may be used in further calculations CE666 Koren Part 5a 3 Copyright 2008 Koren Ripple Carry Adder FA in position i combinatorial circuit sees incoming ci 0 at start of operation accordingly produces si ci may change later on resulting in change in si Ripple effect observed at sum outputs of adder until carry propagation is complete In add operation c0 0 FA can be simpler adding only two bits half adder HA Boolean equations obtained by setting ci 0 FA used for adding 1 in least significant position ulp to implement subtract operation in two s complement One s complement of subtrahend taken and a forced carry added to FA in position 0 by setting c0 1 CE666 Koren Part 5a 4 Copyright 2008 Koren Example x0 1111 y3 y2 y1 y0 0001 FA operation time delay Assuming equal delays for sum and carry out Longest carry propagation chain when adding two 4 bit numbers In synchronous arithmetic units time allowed for adder s operation is worst case delay n FA Adder assumed to produce correct sum after this fixed delay even for very short carry propagation time as in 0101 0010 Subtract 0101 0010 adding two s complement of subtrahend to minuend one s complement of 0010 is 1101 forced carry c0 1 result 0011 CE666 Koren Part 5a 5 Copyright 2008 Koren Reducing Carry Propagation Time 1 Shorten carry propagation delay 2 Detect completion of carry propagation no waiting for fixed delay n FA Second approach variable addition time inconvenient in a synchronous design Concentrate on first approach several schemes for accelerating carry propagation exist Exercise Find a technique for detection of carry completion CE666 Koren Part 5a 6 Copyright 2008 Koren Carry Look Ahead Adders Objective generate all incoming carries in parallel Feasible carries depend only on xn 1 xn 2 x0 and yn 1 yn 2 y0 information available to all stages for calculating incoming carry and sum bit Requires large number of inputs to each stage of adder impractical Number of inputs at each stage can be reduced find out from inputs whether new carries will be generated and whether they will be propagated CE666 Koren Part 5a 7 Copyright 2008 Koren Carry Propagation If xi yi 1 carry out generated regardless of incoming carry no additional information needed If xi yi 10 or xi yi 01 incoming carry propagated If xi yi 0 no carry propagation Gi xi yi generated carry Pi xi yi propagated carry ci 1 xi yi ci xi yi Gi ci Pi Substituting ci Gi 1 ci 1Pi 1 ci 1 Gi Gi 1Pi ci 1Pi 1Pi Further substitutions All carries can be calculated in parallel from xn 1 xn 2 x0 yn 1 yn 2 y0 and forced carry c0 CE666 Koren Part 5a 8 Copyright 2008 Koren CE666 Koren Part 5a 9 Example 4 bit Adder Copyright 2008 Koren Delay of Carry Look Ahead Adders G delay of a single gate At each stage Delay of G for generating all Pi and Gi Delay of 2 G for generating all ci two level gate implementation Delay of 2 G for generating sum digits si in parallel two level gate implementation Total delay of 5 G regardless of n number of bits in each operand Large n 32 large number of gates with large fan in Fan in number of gate inputs n 1 here Span of look ahead must be reduced at expense of speed CE666 Koren Part 5a 10 Copyright 2008 Koren Reducing Span n stages divided into groups separate carry look ahead in each group Groups interconnected by ripple carry method Equal sized groups modularity one circuit designed Commonly group size 4 selected n 4 groups 4 is factor of most word sizes Technology dependent constraints number of input output pins ICs adding two 4 digits sequences with carry look ahead exist G needed to generate all Pi and Gi 2 G needed to propagate a carry through a group once the Pi Gi c0 are available n 4 2 G needed to propagate carry through all groups 2 G needed to generate sum outputs Total 2 n 4 3 G n 2 3 G a reduction of almost 75 compared to 2n G in a ripple carry adder CE666 Koren Part 5a 11 Copyright 2008 Koren Further Addition Speed Up Carry look ahead over groups Group generated carry G 1 if a carry out of group is generated internally Group propagated carry P 1 if a carry in to group is propagated internally to produce a carry out of group For a group of size 4 Group carries for several groups used to generate group carry ins similarly to single bit carry ins A combinatorial circuit implementing these equations available carry look ahead generator CE666 Koren Part 5a 12 Copyright 2008 Koren Example 16 bit 2 level Carry look ahead Adder n 16 4 groups Outputs G 0 G 1 G 2 G 3 P 0 P 1 P 2 P 3 Inputs to a carry look ahead generator with outputs c4 c8 c12 CE666 Koren Part 5a 13 Copyright 2008 Koren Example Cont Operation 4 steps 1 All groups generate in parallel Gi and Pi delay G 2 All groups generate in parallel group carry generate G i and group carry propagate P i delay 2 G 3 Carry look ahead generator produces carries c4 c8 c12 into the groups delay 2 G 4 Groups calculate in parallel individual sum bits with internal carry look ahead delay 4 G Total time 9 G If external carry look ahead generator not used and carry ripples among the groups 11 G Theoretical estimates only delay may be different in practice CE666 Koren Part 5a 14 Copyright 2008 Koren Additional Levels of Carry lookahead Carry look ahead generator produces G and P section carry generate and propagate section is a set of 4 groups and consists of 16 bits For 64 bits either use 4 circuits with a ripplecarry between adjacent sections or use another …