This document provides an introduction to digital logic design basics from a course taught by Dr. Hesham El Zouka. It discusses how logic gates are implemented using transistors and how basic logic gates like AND, OR and NOT work. It also covers logic families like NAND and NOR gates. The document discusses concepts like truth tables, logic functions, logical equivalence, Boolean algebra, and the process of deriving logical expressions from truth tables. It provides examples of analyzing and proving the logical equivalence of different logic circuits.
This document provides an introduction to digital logic design basics from a course taught by Dr. Hesham El Zouka. It discusses how logic gates are implemented using transistors and how basic logic gates like AND, OR and NOT work. It also covers logic families like NAND and NOR gates. The document discusses concepts like truth tables, logic functions, logical equivalence, Boolean algebra, and the process of deriving logical expressions from truth tables. It provides examples of analyzing and proving the logical equivalence of different logic circuits.
This document provides an introduction to digital logic design basics from a course taught by Dr. Hesham El Zouka. It discusses how logic gates are implemented using transistors and how basic logic gates like AND, OR and NOT work. It also covers logic families like NAND and NOR gates. The document discusses concepts like truth tables, logic functions, logical equivalence, Boolean algebra, and the process of deriving logical expressions from truth tables. It provides examples of analyzing and proving the logical equivalence of different logic circuits.
This document provides an introduction to digital logic design basics from a course taught by Dr. Hesham El Zouka. It discusses how logic gates are implemented using transistors and how basic logic gates like AND, OR and NOT work. It also covers logic families like NAND and NOR gates. The document discusses concepts like truth tables, logic functions, logical equivalence, Boolean algebra, and the process of deriving logical expressions from truth tables. It provides examples of analyzing and proving the logical equivalence of different logic circuits.
Lecturer: Dr. Hesham El Zouka Introduction to Digital Logic Basics 2009 Dr. Hesham EL Zouka
Hardware consists of a few simple building blocks
These are called logic gates AND, OR, NOT, … NAND, NOR, XOR, … Logic gates are built using transistors NOT gate can be implemented by a single transistor AND gate requires 3 transistors Transistors are the fundamental devices Pentium consists of 3 million transistors Compaq Alpha consists of 9 million transistors Now we can build chips with more than 100 million transistors Basic Concepts 2009 Dr. Hesham EL Zouka
Simple gates AND OR NOT Functionality can be expressed by a truth table A truth table lists output for each possible input combination Precedence NOT > AND > OR F=AB+AB = (A (B)) + ((A) B) Basic Concepts (cont.) 2009 Dr. Hesham EL Zouka
Additional useful gates
NAND NOR XOR NAND = AND + NOT NOR = OR + NOT XOR implements exclusive--OR function exclusive NAND and NOR gates require only 2 transistors AND and OR need 3 transistors! Basic Concepts (cont.) 2009 Dr. Hesham EL Zouka
Number of functions With N logical variables, we can define N 22 functions Some of them are useful AND, NAND, NOR, XOR, … Some are not useful: Output is always 1 Output is always 0 “Number of functions” definition is useful in proving completeness property Basic Concepts (cont.) 2009 Dr. Hesham EL Zouka
Complete sets A set of gates is complete If we can implement any logical function using only the type of gates in the set You can uses as many gates as you want Some example complete sets {AND, OR, NOT} Not a minimal complete set {AND, NOT} {OR, NOT} {NAND} {NOR} Minimal complete set A complete set with no redundant elements. Basic Concepts (cont.) 2009 Dr. Hesham EL Zouka
Proving NAND gate is universal
Basic Concepts (cont.) 2009 Dr. Hesham EL Zouka
Proving NOR gate is universal
Logic Chips (cont.) 2009 Dr. Hesham EL Zouka Logic Chips (cont.) 2009 Dr. Hesham EL Zouka
Integration levels SSI (small scale integration) Introduced in late 1960s 1-10 gates (previous examples) MSI (medium scale integration) Introduced in late 1960s 10-100 gates LSI (large scale integration) Introduced in early 1970s 100-10,000 gates VLSI (very large scale integration) Introduced in late 1970s More than 10,000 gates Logic Functions 2009 Dr. Hesham EL Zouka
Logical functions can be expressed in several ways:
Truth table Logical expressions Graphical form Example: Majority function Output is one whenever majority of inputs is 1 We use 3-input majority function Logic Functions (cont.) 2009 Dr. Hesham EL Zouka
3-input majority function Logical expression form
F=AB+BC+AC A B C F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Logical Equivalence 2009 Dr. Hesham EL Zouka
All three circuits implement F = A B function
Logical Equivalence (cont.) 2009 Dr. Hesham EL Zouka
Proving logical equivalence of two circuits
Derive the logical expression for the output of each circuit Show that these two expressions are equivalent Two ways: You can use the truth table method For every combination of inputs, if both expressions yield the same output, they are equivalent Good for logical expressions with small number of variables You can also use algebraic manipulation Need Boolean identities Logical Equivalence (cont.) 2009 Dr. Hesham EL Zouka
Derivation of logical expression from a circuit
Trace from the input to output Write down intermediate logical expressions along the path Logical Equivalence (cont.) 2009 Dr. Hesham EL Zouka
Proving logical equivalence: Truth table method
A B F1 = A B F3 = (A + B) (A + B) (A + B) 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 Boolean Algebra 2009 Dr. Hesham EL Zouka Boolean Algebra (cont.) 2009 Dr. Hesham EL Zouka Boolean Algebra (cont.) 2009 Dr. Hesham EL Zouka
To prove that two logical functions F1 and F2 are equivalent Start with one function and apply Boolean laws to derive the other function Needs intuition as to which laws should be applied and when Practice helps Sometimes it may be convenient to reduce both functions to the same expression Example: F1= A B and F3 are equivalent Logic Circuit Design Process 2009 Dr. Hesham EL Zouka
A simple logic design process involves
Problem specification Truth table derivation Derivation of logical expression Simplification of logical expression Implementation Deriving Logical Expressions 2009 Dr. Hesham EL Zouka
Derivation of logical expressions from truth tables
sum-of-products (SOP) form product-of-sums (POS) form SOP form Write an AND term for each input combination that produces a 1 output Write the variable if its value is 1; complement otherwise OR the AND terms to get the final expression POS form Dual of the SOP form Deriving Logical Expressions (cont.) 2009 Dr. Hesham EL Zouka
3-input majority function SOP logical expression
Four product terms A B C F Because there are 4 rows with a 1 output 0 0 0 0 0 0 1 0 0 1 0 0 F=ABC+ABC+ 0 1 1 1 ABC+ABC 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Deriving Logical Expressions (cont.) 2009 Dr. Hesham EL Zouka
3-input majority function POS logical expression
Four sum terms A B C F Because there are 4 rows with a 0 output 0 0 0 0 0 0 1 0 0 1 0 0 F = (A + B + C) (A + B + C) 0 1 1 1 (A + B + C) (A + B + C) 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Logical Expression Simplification 2009 Dr. Hesham EL Zouka
Two basic methods
Algebraic manipulation Use Boolean laws to simplify the expression Difficult to use Don’t know if you have the simplified form Karnaugh map (K-map) method Graphical method Easy to use Can be used to simplify logical expressions with a few variables Algebraic Manipulation 2009 Dr. Hesham EL Zouka Karnaugh Map Method 2009 Dr. Hesham EL Zouka
Note the order
Karnaugh Map Method (cont.) 2009 Dr. Hesham EL Zouka
Simplification examples Karnaugh Map Method (cont.) 2009 Dr. Hesham EL Zouka
First and last columns/rows are adjacent
Karnaugh Map Method (cont.) 2009 Dr. Hesham EL Zouka
Minimal expression depends on groupings
Karnaugh Map Method (cont.) 2009 Dr. Hesham EL Zouka
