Slide Number 1TopicsNumber SystemsNumber Systems: General RepresentationExamplesNumber System ConversionBinary Numbers: ComplementsSubtraction with 2’s Complement2’s Complement Subtraction ExampleSlide Number 10Electrical CharacteristicsSlide Number 12Slide Number 13Slide Number 14Slide Number 15Slide Number 16The Uniting TheoremMinterms and MaxtermsMapping Between FormsSOP and POSBoolean MinimizationK-MapsK-Map ExamplesK-Map Example: Don’t CaresCombinational CircuitsSlide Number 26Slide Number 27Slide Number 28Slide Number 29Slide Number 30Slide Number 31Slide Number 32Slide Number 33Slide Number 34Slide Number 35Memory ExamplePropagation DelayHazards and GlitchesTypes of HazardsStatic HazardsDynamic HazardsDealing with HazardsTechnology Mapping Technology MappingLogic SynthesisDepartment of Electrical and Computer EngineeringMississippi State UniversitySherif Abdelwahed Combinational Logic ReviewComputer Aided Digital Systems Design - EE 4743/6743Topics Numbering systems: binary, decimal, hexadecimal  Signed and unsigned number representations. Logic primitives NAND, NOR, XOR, NOT Boolean logic Basic theorems and properties Gate-level minimization K-maps, Boolean minimization Combinational building blocks Decoders, Multiplexers, Adders, etc. Propagation delay Delay Hazards Technology MappingNumber Systems A number system is totally defined by its base or radix. A digit in base 10 ranges from 0 to 9 A digit in base 2 ranges from 0 to 1 (binary numbers) A digit in Base 16 can range from 0 to 15 (0,1,2,3,4,5,5,6,7,8,9,A,B,C,D,E,F)  Use letters A-F to represent values 10 to 15.  Base 16 is also called Hexadecimal In general a digit in base R can range from 0 to R-1 Textbooks usually uses subscripts to represent different bases. For example: A2F16 , 953.7810 , 1011.112Number Systems: General Representation A rational number with radix r is represented by a string of digits:An - 1An - 2… A1A0 . A- 1 A- 2 … A- m + 1 A- min which 0 ≤ Ai< r and . is the radix point. The string of digits represents the power series:( ) ( )(Number)r= ∑∑+j = - mjjii = 0irArA(Integer Portion) +(Fraction Portion)i = n - 1j = - 1Examples953.78 = 9 * 102+ 5 * 101+ 3 * 100+ 7 * 10-1+ 8 * 10-2= 900 + 50 + 3 + .7 +.08 = 953.780b1011.11 = 1*23+ 0*22+ 1*21+ 1*20+ 1*2-1+ 1*2-2= 8 + 0 + 2 + 1 + 0.5 + 0.25 = 11.750xA2F = 10*162+ 2*161+ 15*160= 10 * 256 + 2 * 16 + 15 * 1 = 2560 + 32 + 15 = 2607Number System Conversion From any base to decimal: Multiplying each digit by its weight and summing. From decimal to any base: Divide Number N by base R until quotient is 0. Remainder at EACH step is a digit in base R, from Least Significant digit to Most significant digit. From Hex to Binary: Each Hex digit represents 4 bits. To convert a Hex number to Binary, simply convert each Hex digit to its four bit value. From Binary to Hex: Just the opposite, create groups of 4 bits starting with least significant bits. If last group does not have 4 bits, then pad with zeros for unsigned numbers.Quiz: Based on the above, how to translate from any base to any base?Binary Numbers: Complements Two main forms: Diminished Radix Complement of N (r - 1)’s complement for radix r 1’s complement for radix 2 Defined as (rn-1) - N In binary, the one's complement is obtained by complementing each individual bit (bitwise NOT). Radix Complement r’s complement for radix r 2’s complement in binary Defined as rn-N In binary, the two's complement is obtained by complementing each individual bit (bitwise NOT) and then adding one.Quiz: What are the advantages of each complement representation?Subtraction with 2’s ComplementFor n-digit, unsigned numbers M and N, find M − N in base 2 Add the 2's complement of the subtrahend N to the minuend M:M + (2n− N) = M − N + 2n If M > N, the sum produces end carry rnwhich is discarded. from above, M − N remains. If M < N, the sum does not produce an end carry and, from above, is equal to 2n− ( N − M ), the 2's complement of ( N − M ).  To obtain the result − (N – M) , take the 2's complement of the sum and place a “−” to its left.2’s Complement Subtraction Example Find 010101002– 01000011201010100 01010100– 01000011 + 1011110100010001 The carry of 1 indicates no correction of the result is needed12’s comp Find 010000112– 01010100201000011 01000011– 01010100 + 101011001110111100010001 The carry of 0 indicates a correction of the result is needed Result = – (00010001)2’s comp2’s compQuiz: How 1’s complement subtraction is performed?Basic Logic GatesElectrical Characteristics Fan in – max number of inputs to a gate Fan out – how many standard loads it can drive (load usually 1) Voltage – often 1.8v, 3.3v or 5v depending on the underlying technology . Noise margin – how much electrical noise it can tolerate Power dissipation – how much power chip needs TTL high Some CMOS low (but look at heat sink on a Pentium) Propagation delay – maximum delay between the input and its output response.Majority Gate (AND-OR form)Theorems of Boolean AlgebraQuiz: Explain the absorption law using Venn diagramTheorems of Boolean AlgebraDeMorgan’s Theorem: ImplementationMajority Gate (NAND-NAND form)The Uniting Theorem Key tool to simplification:  Essence of simplification of two-level logic¾ Find two element subsets of the ON-set where only one variable changes its value –this single varying variable can be eliminated and a single product term used to represent both elementsΑΒ)ΒΑ( =+Minterms and Maxterms Minterms: Product term in which all variables appear once For n variables, there will be 2n minterms Maxterms: Sum term in which all variables appear once Minterm and maxterm with same subscripts are complementsMjmj=33MZYXYZXm =++==Mapping Between FormsSOP and POSXYZZXYZYXZY XZ YXF ++++= Sum of minterms: OR all of the minterms of truth table for rows with a 1 output Simplifying sum-of-minterms can yield a sum of products (SOP) Similarly, simplifying product –of-maxtermscan yield a product of sums (POS)))()()(( ZYXZYXZYXZYXF ++++++++=Boolean MinimizationReduce a Boolean equation to fewer terms - hopefully, this will result in using less gates to implement the Boolean equation.A B C