Advanced Arithmetic Circuits: Adders, Subtraction, and Overflow Explained

COMP541 Arithmetic Circuits Montek Singh Mar 23, 2015 1

Todays Topics Adder circuits ripple-carry adder (revisited) more advanced: carry-lookahead adder Subtraction by adding the negative Overflow 2

Iterative Circuit Like a hierarchy, except functional blocks per bit 3

Adders Great example of this type of design Design 1-bit circuit, then expand Let s look at Half adder 2-bit adder, no carry in Inputs are bits to be added Outputs: result and possible carry Full adder includes carry in, really a 3-bit adder We have already studied adder in Lab 3/Comp411 here we look at it from a different angle modify it to be faster 4

Half Adder Produces carry out does not handle carry in Figure 5.1 1-bit half adder 5

Full Adder Three inputs third is carry in Two outputs sum and carry out 6

Two Half Adders (and an OR) 7

Ripple-Carry Adder Figure 5.5 32-bit ripple-carry adder Straightforward connect full adders Carry-out to carry-in chain Cin in case this is part of larger chain, or just 0 8

Lab 3: Hierarchical 4-Bit Adder We used hierarchy in Lab 3 Design full adder Used 4 of them to make a 4-bit adder Used 2 4-bit adders to make an 8-bit adder 9

Specifying Addition in Behavioral Verilog // 4-bit Adder: Behavioral Verilog module adder_4_behav(A, B, C0, S, C4); input[3:0] A, B; input C0; output[3:0] S; output C4; Addition (unsigned) assign {C4, S} = A + B + C0; endmodule Concatenation operation 10

Whats the problem with this design? Delay Approx how much? Imagine a 64-bit adder Look at carry chain 11

Delays (after assigning delays to gates) Delays are generally higher for more significant bits 12

Multibit Adders Several types of carry propagate adders (CPAs) are: Ripple-carry adders (slow) Carry-lookahead adders (fast) Prefix adders (faster) Carry-lookahead and prefix adders are faster for large adders but require more hardware. A B N N Adder symbol (right) Cout Cin + N S

Carry Lookahead Adder Note that add itself just 2 level sum is produced with a delay of only two XOR gates carry takes three gates, though Idea is to separate carry from adder function then make carry faster actually, we will make carry have a 2-gate delay total, for all the bits of the adder! these two gates might be huge though 14

Four-bit Ripple Carry Reference Adder function separated from carry Notice adder has A, B, C in and S out, as well as G,P out. 15

Propagate The P signal is called propagate P = A B Means to propagate incoming carry 16

Generate The G is generate G = AB, so new carry created So it s ORed with incoming carry 17

Said Differently If A B and there s incoming carry, carry will be propagated And S will be 0, of course If AB, then will create carry Incoming will determine whether S is 0 or 1 18

Ripple Carry Delay: 8 Gates Key observation: G and P are produced by each adder stage without needing carry from the right! need only 2 gate delays for all G s and P s to be generated! critical path is the carry logic at the bottom the G s and P s are off the critical path 19

Turn Into Two Gate Delays Refactor the logic changed from deep (in delay) to wide for each stage, gather and squish together all the logic to the right 20

C1 Just Like Ripple Carry 21

C2 Circuit Two Levels G from before and P to pass on This checks two propagates and a carry in 22

C3 Circuit Two Levels Generate from level 0 and two propagates G from before and P to pass on This checks three propagates and a carry in 23

What Happens as Scale Up? Can I realistically make 64-bit adder like this? Have to AND 63 propagates and Cin! Compromise Hierarchical design More levels of gates use a tree of AND s delay grows only logarithmically 24

Making 4-Bit Adder Module Create propagate and generate signals for whole module 25

Group Propagate Make propagate of whole 4-bit block P0-3 = P3P2P1P0 26

Group Generate Indicates carry generated within this block 27

Hierarchical Carry A B A B 4-bit adder G 4-bit adder G S P Cin S P Cin C4 C8 Look Ahead C0 Left lookahead block is exercise for you 28

Practical Matters FPGAs like ours have limited inputs per gate Instead they have special circuits to make adders So don t expect to see same results as theory would suggest 29

Other Adder Circuits What if hierarchical lookahead too slow Other styles exist Prefix adder (explained in text) had a tree to computer generate and propagate Pipelined arithmetic units multicycle but enable faster clock speed These are for self-study 30

Adder-Subtractor Need only adder and complementer for input to subtract Need selective complementer to make negative output back from 2 s complement 31

Design of Adder/Subtractor S low for add, high for subtract Inverts each bit of B if S is 1 Adds 1 to make 2 s complement Output is 2 s complement if B > A 32

Overflow Two cases of overflow for addition of signed numbers Two large positive numbers overflow into sign bit Not enough room for result Two large negative numbers added Same not enough bits Carry out by itself doesn t indicate overflow 33

Overflow Examples 4-bit signed numbers: Sometimes a leftmost carry is generated without overflow: -7 + 7 5 + (-3) Sometimes a leftmost carry is not generated, but overflow occurs: 4 + 4 34

Overflow Detection Basic condition: if two +ve numbers are added and sum is ve if two -ve numbers are added and sum is +ve Can be simplified to the following check: either Cn-1 or Cn is high, but not both 35

Summary Today adders and subtractors overflow Next class: full processor datapath 36