Full Adders and Subtractors in Digital Circuits

Exploring the implementation of 1-bit full adders and subtractors, including truth tables, Boolean expressions, and concepts like carry propagation and prefix adders. Dive into the intricacies of column generation, propagation, and computation in different types of adders for efficient arithmetic operations in digital circuits.

• Digital Circuits
• Full Adder
• Subtractor
• Boolean Expressions
• Prefix Adder

calir Follow

Uploaded on Sep 21, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. CSE140: Adders Xinyuan Wang 05/24/2019

2. Full Adder/Subtractor How we implement a 1-bit adder/subtractor? Given 2 binary inputs ?,? and a carry in/borrow in bit , calculate ? + ?/? ? 1 0 + 1 1 0 A full adder with input (?,?,???) output (????,?) carry in ? ? borrow in ? ? 0 0 1 1 1 carry out borrow out A full subtractor with input (?,?,???) output (????,?) Write the truth table and derive Boolean expressions 2

3. Truth Tables of Full Adder/Subtractor Derive the Boolean expressions What can we observe by comparing the truth tables? Full Adder Full Subtractor Output ? is same as output ? ? is complemented in subtractor ? = ? ? ??? ????= ?? + ????+ ???? ? = ? ? ??? ????= ? ? + ? ???+ ???? 3

4. Q1: ones complement If bit ? = 0, the function operates as a full adder on (?,?,???); if bit ? = 1, operates on the complement (?,? ,???) fill in the truth table with full adder (?,?,???) (?,? ,???) ? = 0 ? = 1 ??? ? ? ? ???? ? ???? ? 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 Fill in the outputs 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 4

5. Full Adder/Subtractor Carry propagate adders (CPAs) Ripple-carry adders Carry-Lookahead adder When a column will generate a carry out? ?? When a column will propagate a carry in to carry out? ?? How to compute ? and ? for a k-bit block? Prefix Adder a hierarchy structure with segmentations into small blocks parallel prefix operations 5

6. Prefix Adder Compute the carry in for each column as fast as possible Has log2? stages Column 1 holds ???, so ? 1= ???, ? 1= 0 Compute the prefixes: ?0: 1,?1: 1,?2: 1, ?? 1: 1 the generate and propagate for a block spanning bits ?:? ??:?= ??:?+ ??:??? 1:? ??:?= ??:??? 1:? Note: ??:?= ????,??:?= ??+ ??are the generate and propagate for column ? The sum of each column ??= (?? ??) ?? 1: 1 6

7. 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 -1 Prefix Adder 14:13 12:11 10:9 8:7 6:5 4:3 2:1 0:-1 A 16-bit Prefix Adder from slide 27 of Lecture 14 Has 4 stages 14:11 13:11 10:7 9:7 6:3 5:3 2:-1 1:-1 14:7 13:7 12:7 11:7 6:-1 5:-1 4:-1 3:-1 14:-1 13:-1 12:-1 11:-1 10:-1 9:-1 8:-1 7:-1 step 1: column generate and 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 propagate (??:?,??:?) Legend i i i:j step2: block generate and propagate Ai Bi Pi:k Pk-1:jGi:k Gk-1:j Gi-1:-1 Ai Bi (??:?,??:?) (?? 1:?,?? 1:?) (??:?,??:?) step 3: calculate sum ??with ??,??,?? 1: 1 Pi:i Gi:i Pi:j Gi:j Si column generate and propagate block generate and propagate calculate sum 7

8. Prefix Adder 3 2 1 0 -1 Calculate sum of 13, 6 with a 4-bit Prefix Adder, ???= 1 0:-1 2:1 step 1: column generate and propagate 2:-1 1:-1 (??:?,??:?) 3 2 1 0 step2: block generate and propagate (??:?,??:?) (?? 1:?,?? 1:?) (??:?,??:?) step 3: calculate sum ??with ??,??,?? 1: 1 8

9. Prefix Adder 3 2 1 0 -1 Calculate sum of 13, 6 with a 4-bit Prefix Adder, ???= 1 1101 + 0110 step 1: column generate and propagate ? 1: 1,? 1: 1 = 1,0 0:-1 2:1 2:-1 1:-1 3 2 1 0 ?0:0,?0:0 = (0,1) ?1:1,?1:1 = (0,1) ?2:2,?2:2 = (1,1) ?3:3,?3:3 = (0,1) 9

10. Prefix Adder (0,1) (1,1) (1,0) (0,1) (0,1) 3 2 1 0 -1 Calculate sum of 13, 6 with a 4-bit Prefix Adder, ???= 1 1101 + 0110 step 1: column generate and propagate step2: block generate and propagate ??:?= ??:?+ ??:??? 1:? ??:?= ??:??? 1:? Stage 1: 0:-1 2:1 2:-1 1:-1 3 2 1 0 ?0: 1,?0: 1 = (1,0) ?2:1,?2:1 = (1,1) Stage 2: ?1: 1,?1: 1 = (1,0) ?2: 1,?2: 1 = (1,0) 10

11. Prefix Adder Calculate sum of 13, 6 with a 4-bit Prefix Adder, ???= 1 1101 + 0110 (0,1) (1,1) (1,0) (0,1) (0,1) 3 2 1 0 -1 (1,1) (1,0) 0:-1 2:1 step 1: column generate and propagate (1,0) (1,0) 2:-1 1:-1 step2: block generate and propagate 3 2 1 0 step 3: calculate sum ??with ??,??,?? 1: 1 ?0= ?0 ?0 ? 1: 1= 0 ?1= ?1 ?1 ?0: 1= 0 ?2= ?2 ?2 ?1: 1= 1 ?3= ?3 ?3 ?2: 1= 0 ????= ?3: 1= ?3:3+ ?3:3?2: 1= 1 11

12. HW: Zero-deficiency prefix circuit Denote a prefix circuit with ? inputs as ?(?) width of ?(?) is ? size of ?(?) is ??(?)= number of computation nodes depth of ?(?) is ??(?)= number of levels Deficiency of size of ?(?) 3 2 1 0 -1 0:-1 2:1 2:-1 1:-1 ??? ? ? = ??(?)+ ??(?) (2? 2) 3 2 1 0 legend zero-deficiency: ??? ? ? Implement the zero-deficiency prefix adder = 0 12

13. Carry Save Adder A Redundant Number System Save the Partial Solution for Multiple Additions One Bit Propagation for Each Addition digit ? + ? digit ? digit ? ? ? 1 ? ? 2 ? + 2 13

14. Carry Save Adder Example: calculate the sum of 23, 11, 17 Weight 32 16 8 4 2 1 n1=23 0 1 0 1 1 1 n2=11 0 0 1 0 1 1 n3=17 0 1 0 0 0 1 14

15. Carry Save Adder Example: calculate the sum of 23, 11, 17 Weight 64 32 16 8 4 2 1 n1=23 0 0 1 0 1 1 1 n2=11 0 0 0 1 0 1 1 n3=17 0 0 1 0 0 0 1 Addend in one bit n1 00 00 10 00 10 10 10 Redundant system n2 0 0 0 1 0 1 1 A=n1+n2 n3 B=A+n3 Sum 15

16. Carry Save Adder Example: calculate the sum of 23, 11, 17 Weight 64 32 16 8 4 2 1 n1=23 0 0 1 0 1 1 1 n2=11 0 0 0 1 0 1 1 n3=17 0 0 1 0 0 0 1 n1 00 00 10 00 10 10 10 Add three bits with one bit propagation carry carry carry carry carry n2 0 0 0 1 0 1 1 A=n1+n2 00 00 10 10 11 01 00 n3 sum B=A+n3 Sum 16

17. Carry Save Adder Example: calculate the sum of 23, 11, 17 Weight 64 32 16 8 4 2 1 n1=23 0 0 1 0 1 1 1 n2=11 0 0 0 1 0 1 1 n3=17 0 0 1 0 0 0 1 n1 00 00 10 00 10 10 10 n2 0 0 0 1 0 1 1 Partial Solution A=n1+n2 00 00 10 10 11 01 00 n3 0 0 1 0 0 0 1 B=A+n3 Sum 17

18. Carry Save Adder Example: calculate the sum of 23, 11, 17 Weight 64 32 16 8 4 2 1 n1=23 0 0 1 0 1 1 1 n2=11 0 0 0 1 0 1 1 n3=17 0 0 1 0 0 0 1 n1 00 00 10 00 10 10 10 n2 0 0 0 1 0 1 1 A=n1+n2 00 00 10 10 11 01 00 Add three bits with one bit propagation n3 0 0 1 0 0 0 1 B=A+n3 00 01 00 11 00 10 10 Sum 18

19. Carry Save Adder Example: calculate the sum of 23, 11, 17 Weight 64 32 16 8 4 2 1 n1=23 0 0 1 0 1 1 1 n2=11 0 0 0 1 0 1 1 n3=17 0 0 1 0 0 0 1 n1 00 00 10 00 10 10 10 n2 0 0 0 1 0 1 1 A=n1+n2 00 00 10 10 11 01 00 n3 0 0 1 0 0 0 1 Partial Solution An extra addition is needed! B=A+n3 00 01 00 11 00 10 10 Sum 19

20. Carry Save Adder Example: calculate the sum of 23, 11, 17 Weight 64 32 16 8 4 2 1 n1=23 0 0 1 0 1 1 1 n2=11 0 0 0 1 0 1 1 n3=17 0 0 1 0 0 0 1 n1 00 00 10 00 10 10 10 n2 0 0 0 1 0 1 1 A=n1+n2 00 00 10 10 11 01 00 n3 0 0 1 0 0 0 1 B=A+n3 00 01 00 11 00 10 10 Two bits of B 0 1 0 1 0 0 0 Split the redundant number 0 0 0 1 0 1 1 Sum 20

21. Carry Save Adder Example: calculate the sum of 23, 11, 17 Weight 64 32 16 8 4 2 1 n1=23 0 0 1 0 1 1 1 n2=11 0 0 0 1 0 1 1 n3=17 0 0 1 0 0 0 1 n1 00 00 10 00 10 10 10 n2 0 0 0 1 0 1 1 A=n1+n2 00 00 10 10 11 01 00 n3 0 0 1 0 0 0 1 B=A+n3 00 01 00 11 00 10 10 Two bits of B 0 1 0 1 0 0 0 0 0 0 1 0 1 1 Sum 0 1 1 0 0 1 1 21

22. HW: Carry Save Adder Add five numbers for each addition Weight 0 (0, 0, 0, 0, 0) 000 Weight 1 (1, 0, 0, 0, 0) (0, 1, 0, 0, 0) (0, 0, 0, 0, 1) 001 Weight 5 (1, 1, 1, 1, 1) 100 How many bits should be propagated? digit ? + ? digit ? digit ? ? Addend in 5 bits ?4:0? + 1 Addend in 5 bits ?4:0[?] Addend in 5 bits ?4:0[? 1] Addend in 2 bits Addend in 2 bits Addend in 2 bits Adder Block ?2:0? + 1 Adder Block ?2:0? Adder Block ?2:0? 1 carry in to digit i-1 carry out from ?2[? 2] carry out from ?2[? 3] carry out from ?1[? 1] 22 sum in 3 bits sum in 3 bits sum in 3 bits