Logic Design Fundamental

Logic Design Fundamental : Logic Design Fundamental Nguyen Thanh Kien Department of Computer Engineering Faculty of Information Technology Hanoi University of Technology

Content : 2 Content 1. Introduction 2. Function Minimization Methods 3. Larger Combinational Systems 4. Sequential Systems 5. Hardware Design Languages

Reference textbooks : 3 Reference textbooks Introduction to Logic Design, 2nd Ed,, Alan B, Marcovitz, Mc. Graw Hill,2005 Foundation of Digital Logic Design, G.Langholz, A. Kandel, J. Mott, World Scientific, 1998

Grading policy : 4 Grading policy Homework: 20% Lab work: 20% Midterm: 30% Final Exam (multichoice and writing): 30%

1. Introduction : 5 1. Introduction 1.1. Review of Number Systems 1.2. Switching Algebra and Logic Circuits

1.1. Review of Number Systems : 6 1.1. Review of Number Systems 1.1.1 Number Representation 1.1.2 Binary Addition 1.1.3 Signed Numbers 1.1.4 Binary Subtraction 1.1.5 Binary Coded Decimal (BCD) 1.1.6 Other Codes

1.1. Review of Number Systems : 7 1.1. Review of Number Systems 1.1.1 Number Representation 1.1.2 Binary Addition 1.1.3 Signed Numbers 1.1.4 Binary Subtraction 1.1.5 Binary Coded Decimal (BCD) 1.1.6 Other Codes

1.1.1. Number Representation : 8 1.1.1. Number Representation Numbers are normally written using a positional number system: Base/radix: b (the number of digits) Digits: 0..(b-1) 0 = ai = (b-1) Binary: b=2, digits:0,1 Decimal: b=10, digits: 0,1,2,3,4,5,6,7,8,9 Octal: b=8, digits: 0,1,2,3,4,5,6,7 Hexadecimal: b=16, digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

1.1.1. Number Representation : 9 1.1.1. Number Representation 11101.11(2) = 1x24+1x23+1x22+0x21+1x20+1x2-1+1x2-2= 29.75(10)

1.1.1. Number Representation : 10 1.1.1. Number Representation Decimal: b=10 Digits: 0,1,2,3,4,5,6,7,8,9 Eg: 539.45(10) = 5x102+3x101+9x100+4x10-1+5x10-2 ai = 0..9

1.1.1. Number Representation : 11 1.1.1. Number Representation Binary: b=2 Digits: 0,1 Eg: 1011.011(2) = 1x23 + 0x22 + 1x21 + 1x20 + 0x2-1 + 1x2-2 + 1x2-3 ai = 0,1 bit – binary digit

1.1.1. Number Representation : 12 1.1.1. Number Representation Binary (cnt’) n-bit binary number can represent which range? an-1...a1a0 from 0 to 2n-1 MSB – Most Significant Bit LSB – Least Significant Bit 0001 = 1 1001 = 9 0010 = 2 1010 = 10 0011 = 3 1011 = 11 0100 = 4 1100 = 12 0101 = 5 1101 = 13 0110 = 6 1110 = 14 0111 = 7 1111 = 15 1000 = 8

1.1.1. Number Representation : 13 1.1.1. Number Representation Octal: b=8 Digits: 0,1,2,3,4,5,6,7 Eg: 503.071(8) = 5x82 + 0x81 + 3x80 + 0x8-1 + 7x8-2 + 1x8-3 ai = 0..7 Hexadecimal: b=16 Digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Eg: 503.071(16) = 5x162 + 0x161 + 3x160 + 0x16-1 + 7x16-2 + 1x16-3 ai = 0..F

Convert from base b to base 10 : 14 Convert from base b to base 10 Base b to base 10 conversion Eg: 1010.11(2)=? 1010.11(8)=? A12(16)=?

Convert from base 10 to base b : 15 Convert from base 10 to base b Base 10 to base b conversion For integer part: Divide integer part by b until the result is 0 Write remainders in reverse order to get the converted result. For the odd part after “.” Multiply by b until the result is 0

Convert from base 10 to base 2 : 16 Convert from base 10 to base 2 Eg1: 6.625(10) = ?(2) The integer part Eg2: 20.75(10) = ?(2) The odd part after “.” 0.625 x 2 = 1.25 0.25 x 2 = 0.5 0.5 x 2 = 1.0 6.625(10) = 110.101(2)

Convert from base 2 to base 2n : 17 Convert from base 2 to base 2n Group from right to left n-bit groups and replace the equivalent values in base 2n Eg: 101011(2) = ?(8) 1010.110(2)=12.6(8) 101011(2) = ?(16) 1010.110(2)=A.C(16)

Convert from base 2n to base 2 : 18 Convert from base 2n to base 2 Each digit in base 2n is replaced by n bit in base 2. Eg: 37A.B(16)=?(2)

Convert from base i to base j : 19 Convert from base i to base j If both i and j are powers of 2, use base 2 as an intermediate base: Eg: base 8 ? base 2 ? base 16 735.37(8)=?(16) Else, use base 10 as an intermediate base: Eg: base 5 ? base 10 ? base 2

1.1. Review of Number Systems : 20 1.1. Review of Number Systems 1.1.1 Number Representation 1.1.2 Binary Addition 1.1.3 Signed Numbers 1.1.4 Binary Subtraction 1.1.5 Binary Coded Decimal (BCD) 1.1.6 Other Codes

1.1.2 Binary Addition : 21 1.1.2 Binary Addition Binary long addition similar to decimal long addition. decimal binary carry 1100 11110 A 2565 10110 B 6754 11011 sum 9319 110001 Eg: 10101(2) + 11011(2) = ? (2)

1.1.2 Binary Addition : 22 1.1.2 Binary Addition Overflow: Occur when the result of addition is out of range of representation (the result can not be stored in the predefined number of bits) In 8-bit computer, the result of addition of two binary numbers 10101010 and 11010011 is 9-bit binary number which can not be stored in 8-bit => overflow

1.1.2 Binary Addition : 23 1.1.2 Binary Addition n-bit adder in computer:

1.1. Review of Number Systems : 24 1.1. Review of Number Systems 1.1.1 Number Representation 1.1.2 Binary Addition 1.1.3 Signed Numbers 1.1.4 Binary Subtraction 1.1.5 Binary Coded Decimal (BCD) 1.1.6 Other Codes

1.1.3 Signed Numbers : 25 1.1.3 Signed Numbers Represent sign and amplitude Use the most-left-bit to represent sign: 0: positive, 1: negative Eg: represent signed numbers using 4 bit: +5 = 0101, -5 = 1101, -3 = 1011 Using 3 right bits to represent amplitude, we can represent from -7 to +7. Drawbacks: +0 = 0000, -0 = 1000 => complex when calculating => need an other representation

2’s complement representation : 26 2’s complement representation Most left bit is still sign bit Positive and 0 numbers are expressed in usual binary format. The largest number can be represented is 2n-1-1 n=8 => largest signed number: 28-1-1 = 127 Negative number a is stored as the binary equivalent of 2n-a in a n-bit system. -3 is stored as 28-3=11111101 in a 8-bit system The most negative number can be stored is -2n-1

2’s complement representation : 27 2’s complement representation Procedure to find binary representation of negative number in 2’s complement: Find the binary equivalent of the magnitude Complement each bit (0=>1, 1=>0) Add 1 Eg: find representation of -13 in 8-bit signed number system using 2’s complement: Magnitude: 13 = 0000 1101 Complement: 1111 0010 Add 1: 1 -13 = 1111 0011 +

4 bit representation of unsigned and signed (2’s complement) : 28 4 bit representation of unsigned and signed (2’s complement)

2’s complement representation : 29 2’s complement representation To find the magnitude of a negative number: Complement each bit Add 1 Eg:

Addition of signed numbers : 30 Addition of signed numbers The reason that 2’s complement is so popular is the simplicity of addition. To add any two numbers, no matter what the sign of each is, we just do binary addition on their representation.

Addition of signed numbers : 31 Addition of signed numbers Overflow Occur when?

1.1. Review of Number Systems : 32 1.1. Review of Number Systems 1.1.1 Number Representation 1.1.2 Binary Addition 1.1.3 Signed Numbers 1.1.4 Binary Subtraction 1.1.5 Binary Coded Decimal (BCD) 1.1.6 Other Codes

1.1.4 Binary Subtraction : 33 1.1.4 Binary Subtraction Find the 2’s complement of the second operand, then add. a – b = a + (-b) Eg: 7 – 5 = ?

1.1. Review of Number Systems : 34 1.1. Review of Number Systems 1.1.1 Number Representation 1.1.2 Binary Addition 1.1.3 Signed Numbers 1.1.4 Binary Subtraction 1.1.5 Binary Coded Decimal (BCD) 1.1.6 Other Codes

Binary-Coded Decimal - BCD : 35 Binary-Coded Decimal - BCD BCD: Use four bits (a nibble) to represent each of the decimal digits 0 through 9. Eg: 375 = 0011 0111 0101(BCD)

1.1. Review of Number Systems : 36 1.1. Review of Number Systems 1.1.1 Number Representation 1.1.2 Binary Addition 1.1.3 Signed Numbers 1.1.4 Binary Subtraction 1.1.5 Binary Coded Decimal (BCD) 1.1.6 Other Codes

ASCII : 37 ASCII American Standard Code for Information Interchange - ASCII Use seven bits to represent various characters on the standard keyboard as well as a number of control signal

Slide 38 : 38

Problems : 39 Problems 1. Convert the following unsigned numbers: 98.625(10)=?(2) 11011.011(2)=?(10) 6A1.1E(16)=?(8) 2. Represent the following signed numbers: a. -74 in 8-bit signed 2’s complement. b. -74 in 16-bit signed 2’s complement.

1. Introduction : 40 1. Introduction 1.1. Review of Number Systems 1.2. Switching Algebra and Logic Circuits

1.2. Switching Algebra and Logic Circuits : 41 1.2. Switching Algebra and Logic Circuits 1.2.1 Definition of Switching Algebra 1.2.2 Basic Properties of Switching Algebra 1.2.3 Manipulation of Algebraic Functions 1.2.3 Representations of Algebraic Functions 1.2.4 Implementation of Functions with AND, OR, NOT, NAND, NOR, XOR Gates

1.2. Switching Algebra and Logic Circuits : 42 1.2. Switching Algebra and Logic Circuits 1.2.1 Definition of Switching Algebra 1.2.2 Basic Properties of Switching Algebra 1.2.3 Manipulation of Algebraic Functions 1.2.3 Representations of Algebraic Functions 1.2.4 Implementation of Functions with AND, OR, NOT, NAND, NOR, XOR Gates

1.2.1 Definition of Switching Algebra : 43 1.2.1 Definition of Switching Algebra Switching algebra is binary: All variables and constant take on 0 or 1. Light on/off, switch: up/down, voltage: low/high... Quantities which are not naturally binary must be coded into binary format. Three operators: OR: a+b AND: a.b NOT: a’

1.2. Switching Algebra and Logic Circuits : 44 1.2. Switching Algebra and Logic Circuits 1.2.1 Definition of Switching Algebra 1.2.2 Basic Properties of Switching Algebra 1.2.3 Manipulation of Algebraic Functions 1.2.3 Representations of Algebraic Functions 1.2.4 Implementation of Functions with AND, OR, NOT, NAND, NOR, XOR Gates

Basic Properties of Switching Algebra : 45 Basic Properties of Switching Algebra P1: Commutative: a + b = b + a a.b = b.a P2: Associative: a + (b + c) = (a + b) + c a.(b.c) = (a.b).c P3: a + 0 = a a . 1 = a P4: a + 1 = 1 a . 0 = 0

Basic Properties of Switching Algebra : 46 Basic Properties of Switching Algebra P5: a + a’ = 1 a . a’ = 0 P6: no coefficient and no exponent a + a = a a . a = a n.a=a (a)n=a P7: complement (a’)’ = a P8: distributive: a.(b+c) = a.b + a.c a + b.c = (a+b).(a+c)

Basic Properties of Switching Algebra : 47 P9: adjacency ab + ab’ = a (a+b)(a+b’)=a P10: a + a’b = a +b a(a’+b) = a P11: De Morgan (a + b)’ = a’b’ (ab)’ = a’ + b’ Basic Properties of Switching Algebra

Problems : 48 Problems 1. Prove the following equalities: a. xy’+y=x+y b. xy+xz’+yz=xy+x’z c. x’y’z+yz+xz=z d. (x+y)[x’(y’+z’)]’+x’y’+x’z’ = 1

1.2. Switching Algebra and Logic Circuits : 49 1.2. Switching Algebra and Logic Circuits 1.2.1 Definition of Switching Algebra 1.2.2 Basic Properties of Switching Algebra 1.2.3 Manipulation of Algebraic Functions 1.2.3 Representations of Algebraic Functions 1.2.4 Implementation of Functions with AND, OR, NOT, NAND, NOR, XOR Gates

Manipulation of Algebraic Functions : 50 Manipulation of Algebraic Functions A literal: Is the appearance of a variable or its complement Eg: x and x’ are two different literals Expression ab’+bc’d+a’d+e’ has 8 literals A product term: Is one or more literal connected by AND operators Expression ab’+bc’d+a’d+e’has 4 product terms Note: A single literal is also a product term

Manipulation of Algebraic Functions : 51 A standard product term - minterm: Is a product term which includes each variable of the problem, either uncomplemented or complemented. Eg: for a function of four variables a,b,c,d: the product term a’bc’d is a standard product term the product term a’bd’ is not Manipulation of Algebraic Functions

Slide 52 : 52 A sum of product - SOP: Is one or more product terms connected by OR operators Eg: ab’c+abc’+a’c+a’ d A canonical sum – sum of standard product term Is a sum of products expression where all terms are standard product terms. Eg: A function of three variables a,b,c: ab’c + abc’ + abc is a canonical sum ab’c + abc’ + a is not Manipulation of Algebraic Functions

Slide 53 : 53 A minimum sum of products: Is one of those SOP expression for a function that has the fewest number of product terms. If there is more than one expression with fewest number of terms, then minimum is defined as one or more of those expressions with the fewest number of literals. Eg: F1(x,y,z) = x’yz’+x’yz+ xy’z’+xy’z+xyz F2(x,y,z) = x’y+xy’+xyz F3(x,y,z) = x’y+xy’+xz F4(x,y,z) = x’y+xy’+yz Manipulation of Algebraic Functions F3,F4 are minimum SOP of F1

Slide 54 : 54 A sum term: Is one or more literals connected by OR operators Eg: a + b’ + c’ b’ A standard sum term - maxterm: Is a sum term that includes each variable of the problem, either uncomplemented or complemented Eg: For a function of four variables x,y,z,t x+y+z’+t’ is a maxterm x+y+t’ is not Manipulation of Algebraic Functions

Slide 55 : 55 A product of sum – POS: Is one or more sum terms connected by AND Eg: (w+x’+y’)(w+y+z’)(w+x+z) w A canonical product – product of standard sum terms: Is a product of sum term where all sum terms are standard Manipulation of Algebraic Functions

Slide 56 : 56 A minimum POS is defined the same way as SOP: fewest number of terms the same number of terms => fewest number of literals Manipulation of Algebraic Functions

Canonical forms : 57 Canonical forms Three-variable minterm and Maxterm

Canonical forms : 58 Canonical forms Properties of minterm/Maxterm: mimj=0 if i?j =mi if i=j Mi+Mj=1 if i?j = Mi if i=j mi=Mi’ and Mi=mi’ for every i

Canonical forms : 59 Canonical forms An algebraic expression of a Boolean function can be derived from a given true table in two ways: By summing (ORing) those minterm for which the function takes a value 1. By multiplying (ANDing) those maxterm for which the function takes a value 0.

Canonical forms : 60 Canonical forms f(x2,x1,x0)=m1+m4+m5+m6+m7 =S(1,4,5,6,7) f(x2,x1,x0)=M0M2M3 = ?(0,2,3) Canonical sum-of-products (SOP) Canonical product-of-sums (POS)

1.2. Switching Algebra and Logic Circuits : 61 1.2. Switching Algebra and Logic Circuits 1.2.1 Definition of Switching Algebra 1.2.2 Basic Properties of Switching Algebra 1.2.3 Manipulation of Algebraic Functions 1.2.3 Representations of Algebraic Functions 1.2.4 Implementation of Functions with AND, OR, NOT, NAND, NOR, XOR Gates

Truth table : 62 Truth table List all the possible binary combinations of the independent variables and display the corresponding binary values of dependant variables.

Truth table : 63 Truth table n independent variables and m dependant variables: 2n rows n+m columns 3 independent variables 2 dependent variables 23 rows

Venn diagram : 64 Venn diagram Venn diagram using ‘space’ to present logic F(A,B)=A.B F(A,B)=C.not(B)

Venn diagram : 65 Venn diagram A A A+B A.B A.B A+B

Karnaugh map : 66 Karnaugh map A Karnaugh map is a graphical method for representing the true table of a Boolean function. K-map may be used for any variables number, but often at most six.

Karnaugh map (K-map) : 67 Karnaugh map (K-map) If variables number is n => 2n cells in K-map. 2n cells are arranged in logical pattern for minimization purpose.

Two-variable K-map : 68 Two-variable K-map F(A,B) A B 0 1 0 1 B A 0 1 0 1

Three-variable K-map : 69 Three-variable K-map F(A,B,C)

Four-variable K-map : 70 Four-variable K-map F(A,B,C,D)

Five-variable K-map : 71 Five-variable K-map 1 1 1 1 1 1 00 01 11 10 AB CD 00 01 11 10 1 1 1 1 1 1 00 01 11 10 AB CD 00 01 11 10 E 0 1 5 variables Karnaugh Map consists of two 4 variables Karnaugh Map connected up/down.

Six-variable K-map : 72 Six-variable K-map 1 1 1 1 1 1 00 01 11 10 AB CD 00 01 11 10 1 1 1 1 1 1 00 01 11 10 AB CD 00 01 11 10 E 0 1 1 1 1 1 1 1 00 01 11 10 AB CD 00 01 11 10 1 1 1 1 1 1 00 01 11 10 AB CD 00 01 11 10 F 0 1

Karnaugh map with don’t care : 73 Karnaugh map with don’t care don’tcare ~ input conditions that not occur

1.2. Switching Algebra and Logic Circuits : 74 1.2. Switching Algebra and Logic Circuits 1.2.1 Definition of Switching Algebra 1.2.2 Basic Properties of Switching Algebra 1.2.3 Manipulation of Algebraic Functions 1.2.3 Representations of Algebraic Functions 1.2.4 Implementation of Functions with AND, OR, NOT, NAND, NOR, XOR Gates

Basic logic gates : 75 Basic logic gates AND OR NOT

Basic logic gates : 76 Basic logic gates NAND NOR XOR

Implementation of Functions with AND, OR : 77 Implementation of Functions with AND, OR Assume all inputs are available in uncomplemented and complemented F1 = x’yz’+x’yz+xy’z’+xy’z+xyz F2 = x’y+xy’+xz

Implementation of Functions with AND, OR, NOT : 78 Implementation of Functions with AND, OR, NOT Complemented inputs can be produced using inverters NOT: X Y Z F

Multilevel circuits : 79 Multilevel circuits A circuit is called n-level circuit if the maximum number of gates through which one signal must pass from input to output two-level circuit three-level circuit

Implementation of Functions with NAND : 80 Implementation of Functions with NAND Using equivalent change steps, every expression can be represented using only NAND gates. NOT AND OR

Implementation of Functions with NAND : 81 Implementation of Functions with NAND Represent the following expression using only NAND: F(a,b,c) = ab + bc’ + b’

Implementation of Functions with NOR : 82 Implementation of Functions with NOR Using equivalent change steps, every expression can be represented using only NOR gates.

Implementation of Functions with NOR : 83 Implementation of Functions with NOR Represent the following expression using only NAND: F(a,b,c) = ab + bc’ + b’