Digital Logic Design - Lecture 18: Recap

DLDLecture 18RecapRecapNumber System/Inter-conversion, ComplementsBoolean AlgebraMore Logic Functions: NAND, NOR, XORMinimization with Karnaugh MapsMore Karnaugh Maps and Don’t CaresNAND and XOR ImplementationsCircuit Analysis and Design ProceduresBinary Adders and Subtractors Magnitude Comparators and MultiplexersEncoders, Decoders and DeMultiplexersDigital SignalsDecimal values are difficult to represent in electrical systems. It is easier to use two voltage values than ten.Digital Signals have two basic states:1 (logic “high”, or H, or “on”)0 (logic “low”, or L, or “off”)Digital values are in a binary format. Binary means 2 states.A good example of binary is a light (only on or off)onoffPower switches have labels “1” for on and “0” for off.Number SystemsDecimal is the number system that we useBinary is a number system that computers useOctal is a number system that represents groups of binary numbers (binary shorthand). It is used in digital displays, and in modern times in conjunction with file permissions under Unix systems. Hexadecimal (Hex) is a number system that represents groups of binary numbers (binary shorthand). Hex is primarily used in computing as the most common form of expressing a human-readable string representation of a byte (group of 8 bits). Number SystemsSystemBaseSymbolsUsed by humans?Used in computers?Decimal100, 1, 9YesNoBinary20, 1NoYesOctal80, 1, 7NoNoHexa-decimal160, 1, 9,A, B, FNoNoConversion Among BasesThe possibilities:HexadecimalDecimalOctalBinaryBinary Base 2 = Base 10000 = 0001 = 1010 = 2011 = 3100 = 4101 = 5110 = 6111 = 7In Binary, there are only 0’s and 1’s. These numbers are called “Base-2” ( Example: 0102)Binary to DecimalWe count in “Base-10” (0 to 9)Binary number has base 2Each digit is one of two numbers: 0 and 1Each digit is called a bitEight binary bits make a byteAll 256 possible values of a byte can be represented using 2 digits in hexadecimal notation.Binary as a VoltageVoltages are used to represent logic values:A voltage present (called Vcc or Vdd) = 1Zero Volts or ground (called gnd or Vss) = 0A simple switch can provide a logic high or a logic low.A Simple SwitchHere is a simple switch used to provide a logic value:VccGnd, or 0VccVcc, or 1There are other ways to connect a switch.Binary digitsBit: single binary digitByte: 8 binary digits100101112BitByteRadixConverting to decimal from binary:Evaluate the power series Example1 0 1 1 1 125430210*241*25+1*23++1*22+1*21+1*20=4710Number systemsReview of Number systemsMemorize the first ten powers of twoReview of Number systemsNumber systemsConverting to binary from decimal:Divide the decimal number by 2 repeatedly.The remainder gives the digits of the binary number746222222222373 R 0186 R 1 93 R 0 46 R 1 23 R 0 11 R 1 5 R 12 2 R 1 1 R 010111010102Decimal 2 BinaryOctal Numbers: [Base 8],[ 0,1,3,4,5,6,7]Octal to Decimal Conversion:Example:- [2374]8 = [ ? ]10 =4×80+7×81+3×82+2×83 =[1276]10Number systems (Octal Numbers)Octal number has base 8Each digit is a number from 0 to 7Each digit represents 3 binary bitsWas used in early computing, but was replaced by hexadecimalDecimal to Octal Conversion:The Division:[359]10 = [ ? ]8By using the division system:745745ReminderNumber systems (Octal Numbers)QuotientBinary to Octal Conversion:Example:- [110101]2 = [ ? ]8 Here we will take 3 bits and convert it from binary to decimal by using the decimal to binary truth table: Binary Decimal110610151 1 0 1 0 1 = (65)8{65{Number systems (Octal Numbers) Octal to Binary Conversion:Example:- [13]8 = [ ? ]2 Here we will convert each decimal digit from decimal to binary (3 bits) using the decimal to binary truth table: Decimal Binary 10013011(13)8 = (001011)2Number systems (Octal Numbers)Radix Based Conversion (Example)Convert 1234 decimal into octal Radix 8Answer23228Divide by radix 881234 815428192 23OctalsConverting to decimal from octal:Evaluate the power seriesExample2 0 7 80210*812*82+7*80+=13510HexadecimalHexadecimal is used to simplify dealing with large binary values:Base-16, or Hexadecimal, has 16 characters: 0-9, A-FRepresent a 4-bit binary value: 00002 (0) to 11112 (F) Easier than using ones and zeros for large binary valuesCommonly used in computer applicationsExamples: 11002 = 1210 = C161010 0110 1100 00102 = A6 C216Hex values can be followed by an “H” to indicate base-16. Example: A6 C2 HHex Values in ComputersDecimal to HexadecimalDecimalHex0011223344556677889910A11B12C13D14E15FConversion Binary to Hexadecimal10101100000101101010 = 101100 = 120001 = 10110 = 6AC16Radix Based Conversion (Example)Convert 1234 decimal into hexadecimal Radix 16Answer4D216Divide by radix 16161234 16772 4DHexadecimals – Base 16Converting to decimal from hex:Evaluate the power seriesExample2 E A 1602114*1612*162+10*160+=74610Octal to Hex ConversionTo convert between the Octal and Hexadecimal numbering systemsConvert from one system to binary firstThen convert from binary to the new numbering systemHex to Octal ConversionEx : Convert E8A16 to octalFirst convert the hex to binary: 1110 1000 10102 111 010 001 010 and re-group by 3 bits (starting on the right)Then convert the binary to octal: 7 2 1 2 So E8A16 = 72128Octal to Hex ConversionEx : Convert 7528 to hexFirst convert the octal to binary: 111 101 0102 re-group by 4 bits 0001 1110 1010 (add leading zeros) Then convert the binary to hex: 1 E A So 7528 = 1EA16Octal to HexadecimalHexadecimalDecimalOctalBinaryOctal to HexadecimalTechniqueUse binary as an intermediaryExample10768 = ?16 1 0 7 6001 000 111 1102 3 E10768 = 23E16Hexadecimal to OctalHexadecimalDecimalOctalBinaryHexadecimal to OctalTechniqueUse binary as an intermediaryExample1F0C16 = ?8 1 F 0 C0001 1111 0000 11001 7 4 1 41F0C16 = 174148Example: Hex → OctalExample:Convert the hexadecimal number 5AH into its octal equivalent. 5AH = 13285A16116016180+10=9010Solution:First convert the hexadecimal number into its decimal equivalent, then convert the decimal number into its octal equivalent.Fractions (Example)Fractions (Example)Radix Based Conversion (Example)Convert 0.6875 decimal into binary Radix 2Answer0.10112FractionRadixTotal (Fraction x Radix)IntegerFraction0.687521.37510.3750.37520.7500.750.7521.510.50.52110Multiply by radix 2FractionRadixTotal (Fraction x Radix)IntegerFraction0.513168.20880.2080.208163.32830.3280.328165.24850.2480.248163.96830.968Radix Based Conversion (Example)Convert 0.51310 to base 16 (up to 4 fractional point) Radix 16Answer0.835316Multiply by radix 16Any base to decimal conversion(110.11)2 to decimal: (110.11)2 = 6.75.ComplementIt has already been studied that subtracting one number from another is the same as making one number negative and just adding them.We know how to create negative numbers in the binary number system.How to perform 2’s complement process.How the 2’s complement process can be use to add (and subtract) binary numbers.Digital electronics requires frequent addition and subtraction of numbers. You know how to design an adder, but what about a subtracter?A subtracter is not needed with the 2’s complement process. The 2’s complement process allows you to easily convert a positive number into its negative equivalent.Since subtracting one number from another is the same as making one number negative and adding, the need for a subtracter circuit has been eliminated.3-Digit DecimalA bicycle odometer with only three digits is an example of a fixed-length decimal number system.The problem is that without a negative sign, you cannot tell a +998 from a -2 (also a 998). Did you ride forward for 998 miles or backward for 2 miles?Note: Car odometers do not work this way.999998997001000999998002001forward (+)backward (-)Negative Decimal How do we represent negative numbers in this 3-digit decimal number system without using a sign?Cut the number system in half.Use 001 – 499 to indicate positive numbers.Use 500 – 999 to indicate negative numbers.Notice that 000 is not positive or negative.499498497001000999998501500pos(+)neg(-)+499+498+497+001000-001-002-499-5003-Digit Decimal (Examples) 3 + 2 5 003 + 002 005 (-5) + 2 (-3) 995 + 002 997 6 + (-3)3 (-2)+ (-3)(-5) 006 + 997 1003 DisregardOverflow 998 + 997 1995 DisregardOverflowIt Works!Complex ProblemThe previous examples demonstrate that this process works, but how do we easily convert a number into its negative equivalent?In the examples, converting the negative numbers into the 3-digit decimal number system was fairly easy. To convert the (-3), you simply counted backward from 1000 (i.e., 999, 998, 997).This process is not as easy for large numbers (e.g., -214 is 786). How did we determine this?To convert a large negative number, you can use the 10’s Complement Process. The 10’s Complement process uses base-10 (decimal) numbers. Later, when we’re working with base-2 (binary) numbers, you will see that the 2’s Complement process works in the same way.First, complement all of the digits in a number. A digit’s complement is the number you add to the digit to make it equal to the largest digit in the base (i.e., 9 for decimal). The complement of 0 is 9, 1 is 8, 2 is 7, etc.Second, add 1.Without this step, our number system would have two zeroes (+0 & -0), which no number system has.10’s Complement Examples -003+1 996997 -214+1 785Example #1Example #2Complement DigitsAdd 1Complement DigitsAdd 1786 8-Bit Binary Number SystemApply what you have learned to the binary number systems. How do you represent negative numbers in this 8-bit binary system?Cut the number system in half.Use 00000001 – 01111111 to indicate positive numbers.Use 10000000 – 11111111 to indicate negative numbers.Notice that 00000000 is not positive or negative.51011111110111111001111101000000010000000011111111111111101000000110000000+127+126+125+10-1-2-127-128Sign BitWhat did do you notice about the most significant bit of the binary numbers? The MSB is (0) for all positive numbers.The MSB is (1) for all negative numbers.The MSB is called the sign bit.In a signed number system, this allows you to instantly determine whether a number is positive or negative.011111110111111001111101000000010000000011111111111111101000000110000000pos(+)neg(-)+127+126+125+10-1-2-127-1282’S Complement Process The steps in the 2’s Complement process are similar to the 10’s Complement process. However, you will now use the base two. First, complement all of the digits in a number. A digit’s complement is the number you add to the digit to make it equal to the largest digit in the base (i.e., 1 for binary). In binary language, the complement of 0 is 1, and the complement of 1 is 0.Second, add 1.Without this step, our number system would have two zeroes (+0 & -0), which no number system has.2’s Complement ExamplesExample #1Example #2Complement DigitsAdd 1 5 = 00000101-5 = 11111011 11111010+1Complement DigitsAdd 1 -13 = 1111001113 = 0000110100001100+1Using The 2’s Compliment Process 9 + (-5)4 (-9) + 5 - 4 (-9)+ (-5)- 14 9 + 5 14 POS + POS POS  POS + NEG POS  NEG + POS NEG  NEG + NEG NEG Use the 2’s complement process to add together the following numbers. POS + POS → POS AnswerIf no 2’s complement is needed, use regular binary addition.00001001 9 + 5 14 0000111000000101+ POS + NEG → POS AnswerTake the 2’s complement of the negative number and use regular binary addition.00001001 9 + (-5) 4 11111011+ 0000010111111010+111111011 2’s ComplementProcess1]000001008th Bit = 0: Answer is PositiveDisregard 9th BitPOS + NEG → NEG AnswerTake the 2’s complement of the negative number and use regular binary addition. 11110111 (-9) + 5 -4 00000101+ 0000100111110110+111110111 2’s ComplementProcess111111008th Bit = 1: Answer is Negative 1111110000000011+100000100 To Check:Perform 2’s ComplementOn Answer NEG + NEG → NEG AnswerTake the 2’s complement of both negative numbers and use regular binary addition. 11110111 (-9) + (-5) -14 11111011+ 2’s ComplementNumbers, See Conversion ProcessIn Previous Slides1]111100108th Bit = 1: Answer is NegativeDisregard 9th Bit 1111001000001101+100001110 To Check:Perform 2’s ComplementOn Answer 1’s Complement2’s Complement1s complement with negative numbers shifted one position clockwiseOnly one representation for 0 One more negative number than positive numberHigh-order bit can act as sign bitOverflowOverflow conditionsAdd two positive numbers to get a negative numberAdd two negative numbers to get a positive number