Digital Logic Design Lecture 7 Overview
Explore topics covered in Digital Logic Design Lecture 7, including exam details, synthesis procedures, gate properties, and simplification of Boolean expressions. Get ready for the upcoming midterm and review session. Homework 3 due soon!
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ENEE244-02xx Digital Logic Design Lecture 7
Announcements Homework 3 due on Thursday. Review session will be held by Shang during class on Thursday. Midterm on Tuesday, Sept. 30.
First Exam 8 questions, some with multiple parts Will cover material from Lectures 1-7 Including (list on course webpage): Positional number systems: basic arithmetic, polynomial and iterative methods of number conversion, special conversion procedures. Signed numbers and complements: r's complement, (r-1)'s complement, addition and subtraction using r's complement, (r-1)'s complement. Codes: Error detection, error correction, parity check code, Hamming code. Boolean Algebra: definition, postulates, theorems, principle of duality. Boolean formulas and functions: canonical formulas, minterm canonical formulas, maxterm canonical formulas, m-Notation, M-notation, manipulation and simplification of Boolean formulas Gates and combinational networks: various types of gates, universal gates, synthesis procedure, Nand and Nor gate realizations. Incomplete Boolean functions and don't care conditions: truth table representation, satisfiability don't cares, observability don't cares. Gate properties: noise margins, fan-out, propagation delays, power dissipation.
Agenda Last time: Universal Gates (3.9.3) NAND/NOR/XOR Gate Realizations (3.9.4-3.9.6) Gate Properties (3.10) This time: Some examples of Synthesis Procedure The simplification problem (4.1) Prime Implicants (4.2) Prime Implicates (4.3)
Synthesis Procedure High-level description: A function with finite domain and range. Binary-level: All input-output variables are binary.
Formulation of the Simplification Problem What evaluation factors for a logic network should be considered? Cost (of components, design, construction, maintenance) Reliability (highly reliable components, redundancy) Time it takes for network to respond to changes at its inputs.
Minimal Response Time Achieved by minimizing the number of levels of logic that a signal must pass through. Always possible to construct any logic network with at most two levels under the double-rail logic assumption. Why?
Minimal Component Cost Assume this is the only other factor influencing the merit evaluation of a logic network. In general, there are many two-level realizations. Determine the normal formula with minimal component cost. Number of gates is one greater than the number of terms with more than one literal in the expression. Number of gate inputs is equal to the number of literals in the expression plus the number of terms containing more than one literal. Using these criteria can obtain a measure of a Boolean expression s complexity called the cost of the expression.
The Simplification Problem The determination of Boolean expressions that satisfy some criterion of minimality is the simplification or minimization problem. We will assume cost is determined by number of gate inputs.
Fundamental Terms A product or sum of literals in which no variable appears more than once. Can obtain a fundamental term by noting: ? + ? = 1 ? ? = 0 ? + ? = ? ? ? = 1
Prime Implicants ?1implies ?2(?1 ?2) There is no assignment of values to the n variables that makes ?1equal to 1 and ?2equal to 0. Whenever ?1equals 1, then ?2must also equal 1. Whenever ?2equals 0, then ?1must also equal 0. Concept can be applied to terms and formulas.
Examples ?1?,?,? = ?? + ??, ?2?,?,? = ?? + ?? + ?z ?3?,?,? = ? + ? ? + ? ? + ? , ?4(? + ?)(? + ?)
Examples Case of Disjunctive Normal Formula Sum-of-products form Each of the product terms implies the function being described by the formula Whenever product term has value 1, function must also have value 1. Case of Conjunctive Normal Formula Product-of-sums form Each sum term is implied by the function Whenever the sum term has value 0, the function must also have value 0.
Subsumes A term ?1is said to subsume a term ?2iff all the literals of the term ?2are also literals of the term ?1. Example: ?? ?,?? ? + ? + ?,? + ? If a product term ?1subsumes a product term ?2, then ?1implies ?2. Why? If a sum term ?3subsumes a sum term ?4, then ?4 implies ?1. Why?
Subsumes Theorem: If one term subsumes another in an expression, then the subsuming term can always be deleted from the expression without changing the function being described. CNF: (? + ?)(? + ? + ?) DNF: ?? + ???
