Digital Logic Design - Lecture 14: Binary Adders and Subtractors

Lecture 14Binary Adders and SubtractorsOverviewAddition and subtraction of binary data is fundamentalNeed to determine hardware implementationRepresent inputs and outputsInputs: single bit values, carry inOutputs: Sum, CarryHardware featuresCreate a single-bit adder and chain togetherSame hardware can be used for addition and subtraction with minor changesDealing with overflowWhat happens if numbers are too big?Half AdderC A B S 0 0 0 1 A 0 B 0 S 0 C 1 0 0 0 00 1 1 01 0 1 01 1 0 1Dec Binary 1 1+1 +1 2 10Add two binary numbersA0 , B0 -> single bit inputsS0 -> single bit sumC1 -> carry outMultiple-bit AdditionA3 A2 A1 A00 1 0 1A0 1 1 1B3 B2 B1 B0B0 1 0 10 1 1 1 AB0101111 Ai+Bi CiSiCi+1Consider single-bit adder for each bit position.Each bit position creates a sum and carryFull Adder0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1Ci Ai Bi Si Ci+11111CiAiBi0001111001SiFull adder includes carry in CiNotice interesting pattern in Karnaugh map.Full Adder0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1Ci Ai Bi Si Ci+1Si = Ci’. A’i . Bi + Ci’ . Ai . Bi’ + Ci . Ai’ . Bi’ + Ci . Ai . BiFull adder includes carry in CiAlternative to XOR implementationFull AdderSi = Ci’ . Ai’ . Bi + Ci’ . Ai . Bi’ + Ci . Ai’ . !Bi’ + Ci . Ai . BiSi = Ci’ . (A’I . Bi + Ai . B’i) + Ci . (A’I . B’i + Ai . Bi)Si = C’I . (Ai Bi)+ Ci . (Ai Bi)’Si = Ci (Ai Bi) Reduce and/or representations into XORsFull Adder (S in SOP)Full Adder0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1Ci Ai Bi Si Ci+11111CiAiBi0001111001Ci+1Now consider implementation of carry outTwo outputs per full adder bit (Ci+1, Si) Note: 3 inputsFull Adder0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1Ci Ai Bi Si Ci+1CiAiBi00011110011111Ci+1Ci+1 = Ai . Bi + Ci . Bi + Ci . Ai Now consider implementation of carry outMinimize circuit for carry out - Ci+1Full Adder (C in SOP)Full AdderCi+1 = Ai . Bi + Ci Ai’ . Bi + Ci . Ai. B’iCi+1 = Ai . Bi + Ci . (A’I . Bi + Ai . B’i)Ci+1 = Ai.Bi + Ci.(Ai Bi)Recall:Si = Ci (Ai Bi)Ci+1 = Ai.Bi + Ci(Ai Bi)Full AdderSi = Ci (Ai Bi)Half-adderHalf-adderCi+1 = AiBi + Ci(Ai Bi)Full adder made of several half addersFull AdderA full adder can be made fromtwo half adders (plus an OR gate).Hardware repetition simplifies hardware designFull AdderBlock DiagramPutting it all together Single-bit full adderCommon piece of computer hardware4-Bit AdderC 1 1 1 0A 0 1 0 1B 0 1 1 1S 1 1 0 0Chain single-bit adders together.What does this do to delay?Negative Numbers – 2’s Complement. 110 = 0116 = 00000001-110 = FF16 = 11111111 12810 = 8016 = 10000000-12810 = 8016 = 10000000Subtracting a number is the same as:Perform 2’s complementPerform additionIf we can augment adder with 2’s complement hardware?4-bit Subtractor: E = 1+1Add A to B’ (one’s complement) plus 1That is, add A to two’s complement of BD = A - BAdder- Subtractor CircuitOverflow in two’s complement additionDefinition: When two values of the same signs are added:Result won’t fit in the number of bits providedResult has the opposite sign.Overflow?CN-1BN-1AN-1Assumes an N-bit adder, with bit N-1 the MSB10 1101 1010-------- 011111 1110 1101-------- 101101 0011 0110-------- 100100 0010 0011-------- 010100 0010 1100-------- 111011 1110 0100-------- 0010Addition cases and overflowOFLOFL235 3 6-7-2-3-5-3-6 7 2-4-2-2 4 2Addition cases and overflow Binary Parallel Adder (Again)To add n-bit numbers:Use n Full-Adders in parallelThe carries propagates as in addition by handThis adder is called ripple carry adder Src: Mano’s BookRipple Adder DelayHow to improve?Carry Look Ahead AdderHow to reduce propagation delay of ripple carry adders? Carry look ahead adder: All carries are computed as a function of C0 (independent of n !)It works on the following standard principles:A carry bit is generated when both input bits Ai and Bi are 1, orWhen one of input bits is 1, and a carry in bit existsCarry Look Ahead AdderCarry Look Ahead AdderCarry Look Ahead AdderCarry Look Ahead GeneratorCarry Look Ahead AdderConclusion: Each carry bit can be expressed in terms of the input carry Co, and not based on its preceding carry bitEach carry bit can be expressed as a SOP, and can be implemented using a two-level circuit, i.e. a gate delay of 2TCarry Look Ahead AdderBCD AdderBCD digits are valid for decimal numbers 0-9Addition of two BCD numbers will generate an output, that may be greater than 1001 (9).In such cases, the BCD number 0110 is added to the result as a correction stepWhen adding two BCD numbers, the maximum result that can be obtained is:9 + 9 = 18 If we include a carry in bit, then the maximum result that can be obtained is: 19 (10011)Both numbers 18 and 19 are invalid BCD digits. Therefore, a 6 needs to be added to bring them to correct BCD format.Derivation of BCD adderDerivation of BCD adderCombinations 1010 through 1111 need correctionWhen K=1, it is necessary to add 0110 to the binary sumAdding two BCD numbers – CircuitBinary MultiplicationBinary MultiplicationTherefore, for multiplying two 2-bit numbers, AND gates and ADDERS will be sufficientHalf AddersSummaryAddition and subtraction are fundamental to computer systemsKey – create a single bit adder/subtractorChain the single-bit hardware together to create bigger designsThe approach is call ripple-carry additionCan be slow for large designsOverflow is an important issue for computersProcessors often have hardware to detect overflowNext time: encoders/decoder.