Lecture 5 Digital Logic (I)
Digital Logic
◆Operations in Computers are based on the processing of digital/binary data
Copyright By PowCoder代写 加微信 powcoder
binary data
digital circuits
(processing binary data)
All kinds of functionalities
Digital Logic
◆Digital Logic: analysis of discrete/binary data in computer system
– represent real-world signals as binary data
– logical operations over binary data
– the design and implement of digital circuit: logic gates, basic components (adder, decoder, etc.), circuits
An Introductory Example
◆A real-world problem: consider an elevator which has 0 to 9 floors, if you press a button (0- 9), you want to display the number
How to implement this real-world functionality?
Implementation Using Combinational Logic
Input (binary value)
Output (binary value)
𝑌! =𝐹!(𝑋!,𝑋”,⋯,𝑋$%”)
𝑌” =𝐹”(𝑋!,𝑋”,⋯,𝑋$%”)
𝑌&%” =𝐹&%”(𝑋!,𝑋”,⋯,𝑋$%”)
Combinational Logic
Combinational logic: a digital logic circuit in which logical decisions are made based only on combinations of the input 𝑋!, ⋯ , 𝑋”#$
How the decision are made? — Boolean Functions 𝑌! = 𝐹!(𝑋”, 𝑋#, ⋯ , 𝑋$%#)
An important feature of combinational logic: the outputs are updated “immediately” (there exists gate delay) after the inputs change
Implementation Using Combinational Logic
Input (binary value)
Output (binary value)
𝑌! =𝐹!(𝑋!,𝑋”,⋯,𝑋$%”)
𝑌” =𝐹”(𝑋!,𝑋”,⋯,𝑋$%”)
𝑌&%” =𝐹&%”(𝑋!,𝑋”,⋯,𝑋$%”)
Combinational Logic
Input: use 10 inputs 𝑋!, ⋯ , 𝑋”, one for each button. If the button 𝑖 is pressed, set 𝑋! = 1 Output:use7outputs𝑌”,⋯,𝑌&,oneforeachLEDlight.If𝑌! =1,thej-thLE BooleanFunctions𝐹!,⋯,𝐹% toimplementthefunction:givenacombination of inputs, the corresponding LED lights are on
The Overview
Input, Output, Boolean Functions
Combinational Logic
Design Implementation
The mathematical foundation of Design & Implementation: Boolean Algebra
Real-world Problem
Outline of Today’s Lecture ◆Boolean Algebra
– how to do logical operations – basic properties
◆Combinational Logic
– logic gates
– common components
Boolean Algebra
◆Boolean Algebra is useful from both aspects
– implementation (design of digital circuit): given a desired boolean function, Boolean algebra can be applied to develop a simplified implementation of that function
– analysis: Boolean algebra provides an efficient way to describe the function of a digital circuit
Variables and Logic Operations
◆A variable may take on the value 1 (True) or 0 (False)
◆Basic logical operations
– A AND B = 𝐴 ⋅ 𝐵, A OR B = 𝐴 + 𝐵, NOT A = 𝐴
– A NAND B = NOT (A AND B) = 𝐴 ⋅ 𝐵
– A NOR B = NOT (A OR B) = 𝐴 + 𝐵
– A XOR B = 𝐴 ⊕ 𝐵 (exclusive-or: 1 if only one of A and B is 1)
Boolean Operations Extended to Multiple Inputs
Note the condition for output = 1
Switching Functions
◆We can use all the logical operations to construct a
switching function Z = f (A,B, C, …)
– input takes value 0 or 1, output also takes value 0 or 1 — this is why it’s called “switch”
– switch function defines a mapping from a combination of input values to an output value
– example Z = f (A,B); there are four different combinations of input values (0,0), (0,1), (1,0), (1,1) — different way of mapping defines different switching functions
◆Consider switching functions defined over N variables,
how many possible switching functions could we have?
– truth table
– an example of two variables A and B
Truth Table
◆A truth table defines the mapping from the combination
of input values to output
A truth table defines a mapping from input (A,B) to output Z; that is, it defines a switching function f
How many switching functions do we have?
To determine a function f, we need to fill in the “Z column” How many cells do we need to fill — 4; because there are
four rows, meaning four combinations of the input values For each cell, we have two options for the output value (0/1)
So, 2′ = 2(!
Z = f(A,B)
◆Consider switching functions defined over N variables,
how many possible switching functions could we have? – that is, how many different truth tables can we construct?
– hint: first check how many rows in the truth table (= number of combinations of input values)
◆Consider switching functions defined over N variables,
how many possible switching functions could we have?
– we have 2! combinations of input values (rows in the truth table)
– for each row, we have 2 options for the output value – total number of switching functions 2$!
Properties of Boolean Algebra
◆Basic Postulates — stated without proof
– some other properties that could be proved from postulates
– in any case, you can check this properties by truth table
– note the difference from ordinary algebra: some are very similar; others are quite different
Basic Postulates
Commutative law implies that the order of the input does not matter (image two wires to a gate)
Distributive law: similar to algebra, multiplication (AND) has the distributive property over adding (OR); different to algebra, OR has the distributive property over AND — A +BC = (A+B)(A+C)
How to check A +BC = (A+B)(A+C)? — Truth table
In Class Exercise — Truth table
◆Build the truth tables for A+BC and (A+B)(A+C)
– how many rows are there in the table
– when the input combination is (0,1,0), what are the two outputs?
Duality of Boolean Algebra
◆If one expression is correct, its dual is also correct
– example, in the previous table, AB = BA and A+B = B+A ◆How to get the dual of an expression?
– replace AND with OR; replace OR with AND
– replace constant 1 with 0; replace constant 0 with 1 – check duality in the previous table
Other Properties
Note the duality in the first and second column (for NOT, there’s no dual operation, thus no duality)
What are These Properties for?
◆ Transform one expression to another form with specific features
– simplification (Absorption theorem and Consensus Theorem)
– contain only certain operations in the expression (DeMorgan’s theorem) – easy to implement
◆ Generally, we call this process as Algebraic Simplification
– different people may have different results
– depending on the purpose, we may need different results
◆Absorption Theorem
-A(A+B)=A; A+AB=A
– no B in the expression — simplified, less input
◆Consensus Theorem
– 𝐴𝐵 + 𝐴𝐶 + 𝐵𝐶 = 𝐴𝐵 + 𝐴𝐶; (𝐴 + 𝐵)(𝐴 + 𝐶)(𝐵 + 𝐶) =
(𝐴+𝐵)(𝐴+𝐶)
– simplified, less operations
◆DeMorgan’s Theorem
-𝐴𝐵=𝐴+𝐵; 𝐴+𝐵=𝐴𝐵
– in the first equation, no AND operation (change AND to OR)
– in the second equation, no OR operation (change OR to AND)
– reduce the types of operations — important for implementation
– completeness of functionality — a set of operations (gates) that can be used to implement all logical expressions
Completeness of Functionality ◆Functionally Complete Sets of Gates
– AND, OR, NOT: self evident
– AND, NOT: question, can OR be expressed by AND and NOT? – OR, NOT: same as above
similar to Lego block types
Prove (AND, NOT) is a Complete Set of Gates
◆Need to show that A+B can be expressed by AND and NOT operations on A and B
-DeMorgan’slaw:𝐴𝐵=𝐴+𝐵; 𝐴+𝐵=𝐴𝐵 – A+B = ?
𝐴 + 𝐵 = 𝐴 + 𝐵two negations (involution) 𝐴 + 𝐵 = 𝐴𝐵apply DeMorgan′s law
Prove (NAND) is a Complete Set of Gates
◆Need to show that AND and NOT can be expressed by NAND (recall, A NAND B = NOT (A AND B))
– [1] NOT A , that is A NAND A 𝐴 = 𝐴 + 𝐴 = 𝐴𝐴
– [2] A AND B: how? exercise: rewrite write A AND B using NAND hint: 𝐴𝐵 = 𝐴𝐵 ; now treat 𝐴𝐵 as “A” in the above equation
𝐴𝐵 = 𝐴𝐵 = 𝐴𝐵 ⋅ 𝐴𝐵(A NAND B) NAND (A NAND B)
Exercise after Class
◆Use NAND to express A OR B
◆Show NOR is a complete set of gates
Why do We Need NAND (NOR) as A Complete Set ◆There is an obvious shortcoming:
– we use 3 NAND gates to implement 1 AND gate
𝐴𝐵 = 𝐴𝐵 = 𝐴𝐵 ⋅ 𝐴𝐵(A NAND B) NAND (A NAND B)
– so why do we still need NAND
– reason related to the implementation of logical expressions on
Integrated Chips
– during manufacturing, it is preferred to use less types of gates
Two Rules of Thumbs
◆We can write the same logical expression in different forms (algebraic simplification)
◆There are two general rules
– less operations (gates)
– less types of operations (gates)
– there is a trade-off between these two rules
Outline of Today’s Lecture
◆Boolean Algebra
– how to do logical operations
– basic properties ◆Combinational Logic
– logical gates
– common components
Basic Logic Gates
Each gate is defined in three ways: graphical symbol, algebraic notation, and truth table
Each gate has two inputs (NOT has only one) and one single output; it can be easily extended to multiple inputs.
note the different shapes, the “little bubble” for NOT gate
XOR is also very useful
Basic Logic Gates
◆A gate is the fundamental building block of all digital logic circuits
– itself is a electronic circuit, producing an output signal that is a simple Boolean operation on its input signals
– Gate delay: when one input value changes, the correct output signal appears almost instantaneously, delayed only by the propagation time of signals through the gate
Interconnections of Gates — Circuit
use NAND gate to implement NOT, AND, and OR
Three Representations of A Circuit
◆A circuit is a “larger gate”: multiple inputs and a single output
– switching function (logical expression) Z = f(A, B, C,…)
– circuit (graphical/symbolic representation)
– truth table
– know how to translate among these three representations — useful for implementation
Example: A Small Circuit
Logical expression (sum of product form)
Truth table
The Fundamental Implementation Problem ◆How to obtain the circuit?
– a very convenient way is to use “Sum of Product” (SOP) form of a logical expression
– it’s a sum of terms, where term is the product of inputs (or negation of inputs)
– it’s easy to obtain the circuit from SOP
Example: SOP to Circuit
We can easily implement the SOP form using a 2-level AND-OR circuit
But, How to Get SOP?
◆A quick way to convert a truth table to SOP form
F is true when: A=0, B=1,C=1 A=1,B=0,C=1 A=1,B=1,C=0 A=1,B=1,C=1
F is true when:
A=0 AND B=1 AND C=1 OR A=1 AND B=0 AND C=1 OR A=1 AND B=1 AND C=0 OR A=1 AND B=1 AND C=1
But, How to Get SOP?
◆A quick way to convert a truth table to SOP form
principle: go through the table to check each row of F, find the rows where the value of F is 1
then, for each row, write the product as follows: for each individual input X, if it is 1, use X; if it is 0, use negation of X
Product of Sum (POS) Form
◆A product of terms, each term is a sum
(𝐴 + 𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶)
principle: go through the table to check each row of F, find the rows where the value of F is 0
then, for each row, write the sum as follows: for each individual input X, if it is 0, use X; if it is 1, use negation of X
Example: POS to Circuit
(𝐴 + 𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶)
We can easily implement the POS form using a 2-level OR-AND circuit
Which Type of 2-level Circuit Should We Choose ◆Intuition — for shorter expression
– less 1’s in F — use SOP
– less 0’s in F — use POS
– shorter expression means less gates
– however, shorter expression is not the only consideration when designing circuits
– also consider the types of gates available
Digital Components
◆A digital component is a collection of gates that has a specific function
– think about function or method in high-level programming language
◆The design of digital circuits is often at the component level
– digital component is also called Integrated Circuit/IC component – important to know some commonly used digital component
Multiplexer (MUX)
◆N input to 1 output unit (N-to-1) MUX: choose one of the N inputs as the output depending on control signal
(also known as data selector) – 𝐷% is the input data
– 𝑆 is called the selection
4-to-1 MUX
2n number of input requires n number of selection controls
Multiplexer (MUX)
Component Symbol
Truth Table
Note: the output value in the truth table is not 0/1, instead it is D
How can we implement this 4-to-1 MUX?
idea is similar to that of transforming a Truth table to SOP form
if the “coefficient” of the term is 1, that term is selected
Multiplexer (MUX) Implementation
Implementation: 2-level circuit
if the “coefficient” of the term is 1, that term is selected
Applications of Multiplexer (MUX) ◆Main advantage
– reduce the usage of wires — multiple input wires vs. control wires and one single output wire
◆Example of application
– remember Bus? (different data can travel over the same bus)
Applications of Multiplexer (MUX) ◆Access Registers using MUX
Use S to control which register to access
pay attention to the line connection:
4 output lines of register A are connected to position “0” of each MUX
4 output lines of register B are connected to position “1” of each MUX
when S = 00, select position “0” -> register A when S = 01, select position “1” -> register B when S = 10, select position “2” -> register C when S = 11, select position “3” -> register D
Demultiplexer (DEMUX) ◆A Decoder with an Enabler
– less input (A,B); more output (F)
– an Enabler D
– when D = 0, all output = 0
– when D = 1, A,B control which output wire is “on”
why it is called decoder: we use two bits A and B to encode four states (which output wire is on); this digital component will try to decode the input AB
when there is no Enabler D, DEMUX is a Decoder (n inputs, 2^n outputs)
Demultiplexer (DEMUX)
Focus on the case Enable = 1 first, use one AND gate for each output
Then add an Enable wire for each gate
Demultiplexer (DEMUX) ◆Application of DEMUX
– connect the source signal to multiple destinations, where each output wire is connected to one destination
– the source signal (AB) decides which destination is “on”
– simple example: the output line can act as an Enabler for the destination machine
Binary Adder ◆One-bit Adder
– input: A, B; output: S (sum), C (carry forward)
1-Bit Adder Truth Table
note: arithmetic operation is implemented by logical operations
Binary Adder
◆One-bit Adder with Carry Input: the carry forward bit from the previous bit position
practice: derive the SOP form for S and 𝐶)*+
N-bit Binary Adder
A1 B1 A0 B0
Cn-1 -2 Cin
A + B, where A and B both have N bits The Gate delay issue
Simplification
◆Example: the simplification of 𝐶!”#
𝐶/01 =𝐴𝐵𝐶+𝐴𝐵𝐶+𝐴𝐵𝐶+𝐴𝐵𝐶
= 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶
= (𝐴𝐵𝐶 + 𝐴𝐵𝐶) + (𝐴𝐵𝐶 + 𝐴𝐵𝐶) + (𝐴𝐵𝐶 + 𝐴𝐵𝐶)
= (𝐴 + 𝐴)𝐵𝐶 + 𝐴(𝐵 + 𝐵)𝐶 + 𝐴𝐵(𝐶 + 𝐶)reverse Distribution
= 𝐵𝐶 + 𝐴𝐶 + 𝐴𝐵
Complement
Idempotence Association
Simplification in Circuit Design
◆Given a Boolean expression, we may have two qustions
– can it be simplified?
– if you found simplification, is it the simplest form? – a systematical way — Karnaugh map (K-map)
◆Boolean Algebra – the mathematic foundation of
digital logic
– logical operations, truth tables, switching functions
– basic properties — algebraic simplification ◆Combinational Logic
– logica gates, SOP/POS form, implementation – common components
◆Reading: Chapter 20 in textbook (pdf)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com