Transcript PPT - Electrical and Computer Engineering

EE2174: Digital Logic and
Lab
Professor Shiyan Hu
Department of Electrical and Computer Engineering
Michigan Technological University
CHAPTER 4
Technology Mapping
Overview


More Logic Gates
NAND and NOR Gates
NAND and NOR circuits
 Two-level Implementations
 Multilevel Implementations


Exclusive-OR (XOR) Gates
Odd Function
 Parity Generation and Checking

8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 2
More Logic Gates


We can construct any combinational circuit
with AND, OR, and NOT gates
Additional logic gates are used for practical
reasons
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 3
BUFFER, NAND and NOR
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 4
XOR and XNOR
XOR: “not-equal” gate
X
Y
F
XNOR: “equal” gate
X
Y
8-Apr-15
F
X
Y
F = XY
0
0
0
0
1
1
1
0
1
1
1
0
X
Y
F = XY
0
0
1
0
1
0
1
0
0
1
1
1
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 5
NAND Gate


Known as a “universal” gate because
ANY digital circuit can be implemented
with NAND gates alone.
To prove the above, it suffices to show
that AND, OR, and NOT can be
implemented using NAND gates only.
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 6
NAND Gate Emulation
X
X
Y
F = (X•X)’
= X’+X’
= X’
X
F = ((X•Y)’)’
= (X’+Y’)’
= X’’•Y’’
= X•Y
8-Apr-15
F X•Y
X
X
Y
X
Y
F = X’
F = (X’•Y’)’
= X’’+Y’’
= X+Y
F = X+Y
Y
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 7
NAND Circuits

To easily derive a NAND implementation of a
boolean function:




8-Apr-15
Find a simplified SOP
SOP is an AND-OR circuit
Change AND-OR circuit to a NAND circuit
Use the alternative symbols below
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 8
AND-OR (SOP) Emulation
Using NANDs
Two-level implementations
a)
b)
8-Apr-15
Original SOP
Implementation with NANDs
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 9
AND-OR (SOP) Emulation
Using NANDs (cont.)
Verify:
(a) G = WXY + YZ
(b) G = ( (WXY)’ • (YZ)’ )’
= (WXY)’’ + (YZ)’’ = WXY + YZ
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 10
SOP with NAND (again!)
(a)
(b)
(c)
8-Apr-15
Original SOP
Double inversion and grouping
Replacement with NANDs
AND-NOT
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
NOT-OR
PJF - 11
Two-Level NAND Gate
Implementation - Example
F (X,Y,Z) = m(0,6)
1. Express F in SOP form:
F = X’Y’Z’ + XYZ’
2. Obtain the AND-OR implementation
for F.
3. Add bubbles and inverters to
transform AND-OR to NAND-NAND
gates.
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 12
Example (cont.)
Two-level implementation with NANDs
F = X’Y’Z’ + XYZ’
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 13
Multilevel NAND Circuits
Starting from a multilevel circuit:
1. Convert all AND gates to NAND gates
with AND-NOT graphic symbols.
2. Convert all OR gates to NAND gates
with NOT-OR graphic symbols.
3. Check all the bubbles in the diagram.
For every bubble that is not
counteracted by another bubble along
the same line, insert a NOT gate or
complement the input literal from its
original appearance.
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 14
Example
Use NAND gates
and NOT gates to
implement
Z=E’F(AB+C’+D’)+GH
AB
AB+C’+D’
E’F(AB+C’+D’)
E’F(AB+C’+D’)+GH
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 15
Yet Another Example!
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 16
NOR Gate


Also a “universal” gate because ANY
digital circuit can be implemented with
NOR gates alone.
This can be similarly proven as with the
NAND gate
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 17
NOR Circuits

To easily derive a NOR implementation of a
boolean function:




8-Apr-15
Find a simplified POS
POS is an OR-AND circuit
Change OR-AND circuit to a NOR circuit
Use the alternative symbols below
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 18
Two-Level NOR Gate
Implementation - Example
F(X,Y,Z) = m(0,6)
1. Express F’ in SOP form:
1.
2.
2.
3.
4.
F’ = m(1,2,3,4,5,7)
= X’Y’Z + X’YZ’ + X’YZ + XY’Z’ + XY’Z + XYZ
F’ = XY’ + X’Y + Z
Take the complement of F’ to get F in the
POS form: F = (F’)' = (X'+Y)(X+Y')Z'
Obtain the OR-AND implementation for F.
Add bubbles and inverters to transform ORAND implementation to NOR-NOR
implementation.
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 19
Example (cont.)
Two-level implementation with NORs
F = (F’)' = (X'+Y)(X+Y')Z'
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 20
Multilevel NOR Circuits
Starting from a multilevel circuit:
1. Convert all OR gates to NOR gates
with OR-NOT graphic symbols.
2. Convert all OR gates to NOR gates
with NOT-AND graphic symbols.
3. Check all the bubbles in the diagram.
For every bubble that is not
counteracted by another bubble along
the same line, insert a NOT gate or
complement the input literal from its
original appearance.
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 21
Exclusive-OR (XOR) Function



XOR (also ) : the “not-equal” function
XOR(X,Y) = X  Y = X’Y + XY’
Identities:





Properties:


8-Apr-15
X0=X
X  1 = X’
XX=0
X  X’ = 1
XY=YX
(X  Y)  W = X  ( Y  W)
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 22
XOR function implementation


XOR(a,b) = ab’ + a’b
Straightforward: 5 gates
2 inverters, two 2-input ANDs, one 2input OR
 2 inverters & 3 2-input NANDs


Nonstraightforward:

8-Apr-15
4 NAND gates
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 23
XOR circuit with 4 NANDs
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 24
Exclusive-NOR (XNOR) Function



XNOR: the “equality” function
XNOR(a,b) = ab + a’b’
Observe that XNOR(a,b) = ( XOR(a,b) )’


( a  b )’ = ( a’b + ab’)’
= (a’b)’ (ab’)’
= (a + b’) (a’ +b)
= ab + a’b’
a  b’ = ( a  b )’ = a’  b
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 25
Odd Function






xy = x’y + xy’
xyz = xy’z’ + x’yz’ + x’y’z +xyz
xyzw = x’yzw + xy’zw + xyz’w + xyzw’ +
x’y’z’w + x’yz’w’ + x’y’zw’ +xy’z’w’
… Observe a pattern here?
An n-input XOR function is implied (=1) by
all the minterms that have an odd # of 1s
Thus, XOR is also know as the odd function
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 26
Odd Function (cont.)
Minterms are ALWAYS distance two from each other
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 27
Odd Function (cont.)
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 28
Even Function

How would you implement an even
function?
The complement of XOR  XNOR
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 29
Parity Generation and Checking




Odd and even functions can be used to
implement parity checking circuits used
for error detection and correction.
Use even parity as example.
Parity generator: the circuit that
generates the parity bit before
transmitting.
Parity checker: the circuit that checks
the parity in the receiver.
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 30
Even Parity Generation


P(X,Y,Z) must produce a 1 for all the input
combinations that contain an odd number of 1s
Thus, it is a 3-input odd function P = XYZ
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 31
Even Parity Checking
How would you implement a parity
checker for the previous example?
Use a 4-input XOR circuit (odd function)
C = XYZP  1 indicates an error
OR
A 4-input XNOR circuit (even function)
C = (XYZP)’  1 indicates a pass
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 32
Transmission Gates

The transmission gate is one of the
designs for an electronic switch for
connecting and disconnecting two points
in a circuit:
X
C
X
TG
C
(a)
Y
Y
C=1 and C=0
(b)
X
X
C=0
Y
and C=1
(c)
TG
Y
C
(d)
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 33
Transmission Gates (continued)


In many cases, X can be regarded as a data input and Y as an
output. C and C, with complementary values applied, is a control
input.
With these definitions, the transmission gate, provides a 3state output:



C = 1, Y = X (X = 0 or 1)
C = 0, Y = Hi-Z
Care needs to be taken when using the TG in design, however,
since X and Y as input and output are interchangeable, and
signals can pass in both directions.
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 34
Circuit Example Using TG

Exclusive OR F = A + C
A
TG0
A C TG1
C
F
TG0
F
0 0 No path Path
0
0 1 Path
TG1
No path 1
1 0 No path Path
1 1 Path
(a)

1
No path 0
(b)
The basis for the function implementation is TG
controlled paths to the output
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 35
More Complex Gates


The remaining complex gates are SOP or POS
structures with and without an output
inverter.
The names are derived using:




8-Apr-15
A - AND
O - OR
I - Inverter
Numbers of inputs on first-level “gates” or
directly to second-level “gates”
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 36
More Complex Gates
(continued)


Example: AOI - AND-OR-Invert consists of a single
gate with AND functions driving an OR function which
is inverted (page 95 in the textbook).
These gate types are used because:


8-Apr-15
The number of transistors needed is fewer than required by
connecting together primitive gates
Potentially, the circuit delay is smaller, increasing the circuit
operating speed
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 37
Terms of Use






© 2004 by Pearson Education,Inc. All rights reserved.
The following terms of use apply in addition to the standard Pearson
Education Legal Notice.
Permission is given to incorporate these materials into classroom
presentations and handouts only to instructors adopting Logic and
Computer Design Fundamentals as the course text.
Permission is granted to the instructors adopting the book to post
these materials on a protected website or protected ftp site in
original or modified form. All other website or ftp postings,
including those offering the materials for a fee, are prohibited.
You may not remove or in any way alter this Terms of Use notice
or any trademark, copyright, or other proprietary notice, including
the copyright watermark on each slide.
Return to Title Page
8-Apr-15
Chapter 2-i: Combinational Logic Circuits (2.1-- 2.5)
PJF - 38