1ECE 274 - Digital LogicLecture 12 Lecture 12 – Datapath Components Subtractors Two’s Complement Overflow ALUs Register Files2Subtractor Can build subtractor as we built carry-ripple adder Mimic subtraction by hand Compute borrows from columns on left Use full-subtractor component:  wi is borrow by column on right, wo borrow from column on left4.811000111110-1stcolumn110101001110 11-3rd column11000011100 11-4th columnwoa3abFSwiwo sb3s3a2abFSwiwo sb2s2a1abFSwiwo sb1s1a0a3 a2 a1 a0b3s3s2s1s0wowib2 b1 b0abFSwiwiwo sb0s0(b) (c)4-bit subtractora1100111 1110-2ndcolumn10103Subtractor Example: DIP-Switch Based Adding/Subtracting Calculator Extend earlier calculator example Switch f indicates whether want to add (f=0) or subtract (f=1) Use subtractor and 2x1 muxDIP switches108-bit registerCALCLEDsefclkld88800888882x10110wiciAABBSSco wo8-bit adder 8-bit subtractor4Subtractor Example: Color Space Converter – RGB to CMYK Color Often represented as weights of three colors: red, green, and blue (RGB) Perhaps 8 bits each, so specific color is 24 bits White: R=11111111, G=11111111, B=11111111 Black: R=00000000, G=00000000, B=00000000 Other colors: values in between, e.g., R=00111111, G=00000000, B=00001111 would be a reddish purple Good for computer monitors, which mix red, green, and blue lights to form all colors• Printers use opposite color scheme– Because inks absorb light– Use complementary colors of RGB: Cyan (absorbs red), reflects green and blue, Magenta (absorbs green), and Yellow (absorbs blue) 5Subtractor Example: Color Space Converter – RGB to CMYK Printers must quickly convert RGB to CMY  C=255-R, M=255-G, Y=255-B Use subtractors as shown---RGB888888888255 255 255CMYRGBto CMY6Subtractor Example: Color Space Converter – RGB to CMYK Try to save colored inks Expensive Imperfect – mixing C, M, Y doesn’t yield good-looking black Solution: Factor out the black or gray from the color, print that part using black ink e.g., CMY of (250,200,200)= (200,200,200) + (50,0,0). (200,200,200) is a dark gray – use black ink7Subtractor Example: Color Space Converter – RGB to CMYK Call black part K (200,200,200): K=200 (Letter “B” already used for blue)Compute minimum of C, M, Y values Use MIN component designed earlier, using comparator and mux, to compute K Output resulting K value, and subtract K value from C, M, and Y values Ex: Input of (250,200,200) yields output of (50,0,0,200)RGBto CMK---88C2 M2 Y2 K88888 88 8MINMINCCM YRGRGB to CMYYBMYKRGB88 88Representing Negative Numbers: Two’s Complement Negative numbers common How represent in binary? Signed-magnitude Use leftmost bit for sign bit So -5 would be:1101 using four bits10000101 using eight bits  Better way: Two’s complement Big advantage: Allows us to perform subtraction using addition Thus, only need adder component, no need for separate subtractor component!9Ten’s Complement Before introducing two’s complement, let’s consider ten’s complement But, be aware that computers DO NOT USE TEN’S COMPLEMENT. Introduced for intuition only. Complements for each base ten number shown to right – Complement is the number that when added results in 1098765432112345678910Ten’s Complement Nice feature of ten’s complement Instead of subtracting a number, adding its complement results in answer exactly 10 too much So just drop the 1 – results in subtracting using addition only46107Ð4 +6010203 13133010123456789987654321complements7Ð4=3 7+6=13 3Adding the complement results in an answerexactly 10 too much – dropping t he tens column givestheright answer.--11Two’s Complement is Easy to Compute: Just Invert Bits and Add 1 Hold on! Sure, adding the ten’s complement achieves subtraction using addition only But don’t we have to perform subtractionto have determined the complement in the first place? e.g., we only know that the complement of 4 is 6 by subtracting 10-4=6 in the first place. True – but in binary, it turns out that the two’s complement can be computed easily Two’s complement of 011 is 101, because 011 + 101 is 1000 Could compute complement of 011 as 1000 – 011 = 101 Easier method: Just invert all the bits, and add 1 The complement of 011 is 100+1 = 101 -- it works!Q: What is the two’s complement of 0101?A: 1010+1=1011(check: 0101+1011=10000)aQ: What is the two’s complement of 0011?A: 1100+1=110112Two’s Complement Subtractor Built with an Adder Using two’s complementA – B = A + (-B) = A + (two’s complement of B) = A + invert_bits(B) + 1 So build subtractor using adder by inverting B’s bits, and setting carry in to 11cinBAAdderSBAN-bit13Adder/Subtractor Adder/subtractor: control input determines whether add or subtract Can use 2x1 mux – sub input passes either B or inverted B Alternatively, can use XOR gates – if sub input is 0, B’s bits pass through; if sub input is 1, XORs invert B’s bits14Adder/Subtractor Example: Calculator Previous calculator used separate adder and subtractor Improve by using adder/subtractor, and two’s complement numbersDIP switches108-bit register8-bit adder/subtractorsubCA LCLEDseSABfclkld108888DIP switches108-bitregisterCALCLEDsefclkld88800888882x10110wiciAABBSSco wo8-bit adder 8-bit subtractor15Design ChallengeNot Really a Quiz Determine the two’s complement representation for the following decimal numbers (assume we are using 5-bit binary numbers): -1 -11 -15 Determine the two’s complement representation for same decimal numbers assuming we are using 6-bit binary numbers.16Overflow Sometimes result can’t be represented with given number of bits Either too large magnitude of positive or negative e.g., 4-bit two’s complement addition of 0111+0001 (7+1=8). But 4-bit two’s complement can’t represent number >7 0111+0001 = 1000 WRONG answer, 1000 in two’s complement is -8, not +8 Adder/subtractor should indicate when overflow has occurred, so result can be discarded17Detecting Overflow: Method 1 Assuming 4-bit two’s complement numbers, can detect overflow by detecting when the two numbers’ sign bits are the same but are different from the result’s sign bit If the two numbers’ sign bits are different, overflow is impossible Adding a positive and negative can’t exceed largest magnitude