Digital Fundamentals Tenth Edition Chapter 6 PDF

Digital Fundamentals Tenth Edition Floyd Chapter 6 © 2009 Pearson Education,©Upper...

Digital Fundamentals Tenth Edition Floyd Chapter 6 © 2009 Pearson Education,©Upper 2008 Pearson Education Floyd, Digital Fundamentals, 10th ed Saddle River, NJ 07458. All Rights Reserved  Summary Half-Adder Basic rules of binary addition are performed by a Inputs Outputs half adder, which has two binary inputs (A and B) A B Cout S and two binary outputs (Carry out and Sum). 0 0 0 0 0 1 0 1 The inputs and outputs can be summarized on a 1 0 0 1 truth table. 1 1 1 0 The logic symbol and equivalent circuit are: S S A S A Cout B Cout B Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved  Summary Full-Adder Inputs Outputs By contrast, a full adder has three binary A B Cin Cout S 0 0 0 0 0 inputs (A, B, and Carry in) and two binary 0 0 1 0 1 outputs (Carry out and Sum). The truth table 0 1 0 0 1 summarizes the operation. 0 1 1 1 0 1 0 0 0 1 A full-adder can be constructed from two 1 0 1 1 0 half adders as shown: 1 1 0 1 0 1 1 1 1 1 S S A A S A S Sum S B B Cout B Cout A S B Cout Cin Cin Cout Symbol Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved  Summary Full-Adder S S 0 Sum 1 A S 1 A S Example 0 B Cout 0 B Cout 1 For the given inputs, determine 1 Cout the intermediate and final outputs 1 of the full adder. Solution The first half-adder has inputs of 1 and 0; therefore the Sum =1 and the Carry out = 0. The second half-adder has inputs of 1 and 1; therefore the Sum = 0 and the Carry out = 1. The OR gate has inputs of 1 and 0, therefore the final carry out = 1. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved  Summary Full-Adder Notice that the result from the previous example can be read directly on the truth table for a full adder. Inputs Outputs A B Cin Cout S S S 0 Sum 0 0 0 0 0 1 A S 1 A S 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 B Cout 0 B Cout 1 0 0 0 1 1 0 1 1 0 1 Cout 1 1 0 1 0 1 1 1 1 1 1 Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved  Summary Parallel Adders Full adders are combined into parallel adders that can add binary numbers with multiple bits. A 4-bit adder is shown. A4 B4 A3 B3 A2 B2 A1 B1 C0 A B Cin A B Cin A B Cin A B Cin Cout S Cout S Cout S Cout S C4 C3 C2 C1 S S S S The output carry (C4) is not ready until it propagates through all of the full adders. This is called ripple carry, delaying the addition process (sequential delay.). Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved  Summary Parallel Adders The logic symbol for a 4-bit parallel adder is shown. This 4-bit adder includes a carry in (labeled (C0) and a Carry out (labeled C4). S 1 1 Binary 2 2 4-bit number A 3 3 sum 4 4 1 Binary 2 number B 3 4 Input Output C0 C4 carry carry The 74LS283 is an example. It features look-ahead carry, which adds logic to minimize the output carry delay. For the 74LS283, the maximum delay to the output carry is 17 ns. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 8 Carry Propagation Because the propagation delay will affect the output signals on different time, so the signals are given enough time to get the precise and stable outputs. The most widely used technique employs the principle of carry look-ahead to improve the speed of the algorithm. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 9 Boolean functions Pi = Ai ⊕ Bi steady state value Gi = AiBi steady state value Output sum and carry Si = Pi ⊕ Ci Ci+1 = Gi + PiCi Gi : carry generate Pi : carry propagate C0 = input carry C1 = G0 + P0C0 C2 = G1 + P1C1 = G1 + P1G0 + P1P0C0 C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0 C3 does not have to wait for C2 and C1 to propagate. This means the carry into the next stage depends on whether the current bit generates a carry or propagates a previous carry. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved  Logic diagram of carry look-ahead generator C3 is propagated at the same time as C2 and C1. All carry bits (C1,C2,C3​) can be computed in parallel without waiting for each previous stage. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved  4-Bit Carry Look-Ahead Adder Example Inputs: A=1011, B=0110, C0=0 Generate (G) & Propagate (P) Values: Pi = Ai ⊕ Bi, Gi = AiBi G0 = 0, P0 = 1 G1 = 1, P1 = 0 G2 = 0, P2 = 1 G3 = 0, P3 = 1 Sum: S=1000 Carry Out:C4 =1 Final result: 10001 Final Result: Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 1 2 4-bit adder with carry lookahead Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 1 3 Binary subtractor M = 1→subtractor ; M = 0→adder Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 1 4 Overflow When the value of M is set to true or 1, the B0⨁M produce the complement of B0 as the output. So the operation would be A0 +B0', which is the 2's complement subtraction of A and B. When the value of M is set to 0, the B0⨁M produce the B0 as the output. It is worth noting in Fig.4-13 that binary numbers in the signed-complement system are added and subtracted by the same basic addition and subtraction rules as unsigned numbers. Overflow is a problem in digital computers because the number of bits that hold the number is finite and a result that contains n+1 bits cannot be accommodated. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 1 5 Overflow on signed and unsigned When two unsigned numbers are added, an overflow is detected from the end carry out of the MSB position. 1111​+0001=10000 ​The result requires 5 bits, but only 4 bits are available. The extra carry indicates an overflow. When two signed numbers are added, the sign bit is treated as part of the number and the end carry does not indicate an overflow. An overflow cann’t occur after an addition if one number is positive and the other is negative. An overflow may occur if the two numbers added are both positive or both negative. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 1 6 Decimal adder BCD adder can’t exceed 9 on each input digit. K is the carry. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 1 7 Rules of BCD adder When the binary sum is greater than 1001, we obtain a non- valid BCD representation. The addition of binary 6(0110) to the binary sum converts it to the correct BCD representation and also produces an output carry as required. To distinguish them from binary 1000 and 1001, which also have a 1 in position Z8, we specify further that either Z4 or Z2 must have a 1. C = K + Z8Z4 + Z8Z2 Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 1 8 Implementation of BCD adder A decimal parallel adder that adds n decimal digits needs n BCD adder stages. The output carry from one stage must be connected to the If =1 input carry of the next higher-order 0110 stage. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 1 9 Binary multiplier Usually there are more bits in the partial products and it is necessary to use full adders to produce the sum of the partial products. And Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 2 0 4-bit by 3-bit binary multiplier For J multiplier bits and K multiplicand bits we need (J X K) AND gates and (J − 1) K-bit adders to produce a product of J+K bits. K=4 and J=3, we need 12 AND gates and two 4-bit adders. Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 2 1 Magnitude comparator The equality relation of each pair of bits can be expressed logically with an exclusive- NOR function as: A = A3A2A1A0 ; B = B3B2B1B0 xi=AiBi+Ai’Bi’ for i = 0, 1, 2, 3 (A = B) = x3x2x1x0 Floyd, Digital Fundamentals, 10th ed © 2009 Pearson Education, Upper Saddle River, NJ 07458. All Rights Reserved 2 2 Magnitude comparator We inspect the relative magnitudes of pairs of MSB. If equal, we compare the next lower significant pair of digits until a pair of unequal digits is reached. If the corresponding digit of A is 1 and that of B is 0, we conclude that A>B. (A>B)= A3B’3+x3A2B’2+x3x2A1B’1+x3x2x1A0B’ 0 (AB A>B A=B A=B Outputs inputs AB A>B A>B +5.0 V A=B A=B A=B A=B Outputs A