Class Note for ENGIN 112 at UMass(20)
Class Note for ENGIN 112 at UMass(20)
Popular in Course
Popular in Department
This 23 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for ENGIN 112 at UMass(20)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 7 Adders Subtractors and Multipliers I BinaryAdders We talked about combinational circuits last week One very important application is to implement circuits that perform binary arithmetic that is addition subtraction and multiplication First consider the problem of adding two 1bit inputs X and yto generate an output sum bit 8 and a carry bit C We have the combinational circuit truth table xy S C 00 O O Sowehave S XXORy 01 1 o C Xy 1O 1 O 11 O 1 These give us the half adder circuit Half Adder Circuit Block Symbol X s x gt gts y I Example Draw a NAND gate implementation of a half adder S X XOR y Xy X y 00 X y Xy 39 X y x NAND y NAND x NAND y C Xy XY X NAND y So half adder has NAND gate implementation D Do D D WW Now if we consider adding multiplebit numbers then the addition for each bit position but the rightmost bit potentially involves three inputs the two bits being added at that position and a carry bit from the position to the right Then the adder forthat bit has three inputs the two bits being added and the carry from the previous bit position and two outputs the sum bit and new carry bit Suppose we want to build an adder for bit position i Let A and B denote the two bits being summed at the ith position and let C denote the carry from position i1 that is the position to the right of position I Let 8 denote the sum bit generated at position iand et C1 denote the carry bit that is generated for carry to position i1 Then we have the truth table Ai Bi Ci Si Ci1 o o o o o This truth tabe generates a combinational circuit known as a full 0 O 1 1 O adden O 1 O 1 O O 1 1 O 1 1 O O 1 O 1 O 1 O 1 1 1 O O 1 1 1 1 1 1 Karnaugh map for 8 30 00 O1 11 1O So 3 C A BAB CA B AB C AXOR B CAXOR B CXOR AXOR B BiICi Karnaugh map for CM A 00 O1 11 10 O 1 SO Ci1 BC AB AC We can directly implement a combinational circuit using the functions found from the Karnaugh maps Alternatively we can make use of the half adders that were already designed Note that if we do not restrict ourselves to prime implicants in the Karnaugh map for CH1 we can get an alternative expression in the form BiICi OO 01 11 1O 0 Cm AiBi AiBCi AIBICI 1 l 1 l I 1 1 AB CAXORB So We need 8 CXOR A1XOR B C1 AB C A XOR B Consider the half adder connection AXOR B C XOR AXOR 3 s Ai gt gt HA HA Bi gt i AiBi J C C A XOR 3 AB C A XOR 3 C So this combinational circuit is a full adder for the ith bit Block symbol A B l 1 CH lt FA lt c i These 1bit full adder blocks can be connected in turn to form multibit adders For example a 4bit adder for summing binary input words A3 A2A1A0 and B3 323130 possibly with an input carry bit Co to generate the sum 83 82 S180 and output carry bit C4 is as shown below A3 Ba A2 B2 A1 B1 A0 B0 H H ll ll Cs 02 01 C4 lt FA lt FA lt FA FA ltC l l l l 83 82 S1 80 This is called a ripple carry adder since the carry bits have to ripple through the stages in order to calculate the sum bits A3A2A1A0 B3323130 Block symbol for 4bit l l l l l l l l adder circuit C4 lt 4bit adder lt Co Example Show the computation steps in using a 4bit ripple carry adder for summing 0111 and 1100 1A01BO0C00 9801C70 1 o H olt FA lt o t 1 2A11B10C10 9 1 0 1 0 H H 0lt FA lt FA lt0 t l 3A21BZ1C20 1 1 1 0 1 0 v v v v v v 9 82 0 C3 1 0 0 7 lt FA lt FA lt FA lt 0 v v v 0 1 1 4A30 B3 1 C31 9 S3 0 C4 1 0 1 1 1 1 0 1 0 v v v V v v v v 1 0 0 80 result 5410011 1lt FA lt FA lt FA lt FA lt 0 Output carry v v v v Note that some time is required for the carry bits to ripple through the adder stages this carry propagation time limits the speed at multi bit adders can work The carry propagation time can be reduced through the use of carry lookahead logic Idea Consider the full adder as a connection of two halfadders HA 0 XOR P s gt P AXOR B Aigt HA B gt J GI AiBi C GiCiPiCi1 G is called the carry generator and P the carry propagate Note that these do not depend on the input carry bit C In terms of these internal variables the equations for generating the carry bits in the 4bit adder are C GO POCO lt depends only on inputs C2 G P1C1 G P1GO POCO lt depends only on inputs not carry bit C1 C3G2P2C2GzP2G1P1C1 GzPzG1P2P1GoP0C0 depends only on inputs not carry bit C2 C4G3P3C362P362P2C2 GzP3G2P3P2G1P1C1 G2 P362 P3P2 G1 P3P2F 7 GO POCO depends only on inputs not carry bit C3 So at the expense of more complex circuitry the carry bits can all be generated directly from the input binary words and input carry bit without having to wait for carry propagation II Binary Subtractors Recall that ifA and B are binary words the subtraction A B can be calculated as A B A 2 s complement of B A 1 s complement of B 1 bitbybiz inverse of B input carry bit This leads to the 4bit subtractor circuit A3 83 A2 82 A B A0 8039 l l l l l l l C4 lt FA lt FA lt FA lt FA lt1 l l l l 83 82 S1 80 Example Consider the 4bit binary circuit for the operation 41O 51O A 0100 B 0101 We have 0 1 1 0 0 1 0 0 l l l l l l l l 0lt FAlt FAlt FAlt FA lt 7 l l l l 1 1 1 1 Result is 1111 signed 2 s complement representation for 110 Finally note that an adder and subtractor can be implemented in a single circuit by defining a mode bit M with M 0 denoting adder and M 1 denoting subtractor We replace the input carry bit 0 for addition and 1 for subtraction with M and replace each B with B XOR M B when M0 addition and B when M1 subtraction 4bitAdderSubtractor with mode bit M B3 B2 B7 BO C3 02 C1 C4 lt FA lt FA lt FA lt FA l III Binary Multiplier To see how to construct a binary multiplier using adders consider the problem of multiplying the 4bit number 83828780 by the 4bit number A3A2A1A0 We have B3 32 B1 BO A3 A2 A1 A0 A033 A032 A031 A030 A133 A132 1413114130 A233 A232 A231 A230 A333 A332 A331 A330 R7 R6 R5 R4 R3 R2 R1 R0 Now Define the binary numbers P4 P3 P2 P1 Po A033 A032 AoB1 A133 A132 A131 A130 Q4 Q3 Q2 Q1 Q0 P4 P3 P2 P1 AZB3 A282 AZB1A2BO Then R0 AOBO R7 P0 R2 Q0 R7 R6 R5 R4 R3 Q4 Q3 Q2 Q1A3B3 A382 A381 A380 80 We have the multiplier circuit A1B3A1BZA1B1A1BO OAOB3AOBZAOB1 A030 H i l i i l l 4bit adder lt 0 P4 1P3 P2 P1 P0 A233 A232 AZB1AZBO 1 i i i i v v 4bit adder 0 l l 00 Q3 02 Q1 R2 R1 R0 continued from last page A353A332A331A350 iii l l 4bit adder O R6 R5 R4 R3 Note We have considered four different scales or levels of detail in discussing the design of digital systems 1 Block Diagrams This is the level at which systems designers develop complex systems as interconnected blocks for example a binary multiplier as a connection of 4bit adders blocks a 4bit adder as a connection of full adder blocks or a full adder as a connection of half adder blocks Example Full adder block diagram Ai 3 HA HA 2 Logic dates OR AND NAND etc This is the level that we use in designing logic circuits to perform desired operations Example NAND gate implementation of half adder block 3 Do 3 m 3 Transistor level This is the level that shows how physical devices transistors are connected to form logic gates Example CMOS NAND gate VIII i 1 393 Y ABl 4 Semiconductor level This is the level at which transistors and other devices are actually constructed using semiconductors and metal depos s Example NMOS transistor construction Polysilicon p suhstrate Electrical and computer systems engineers work at each of these different levels to design the systems that we need
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'