Transcript Lecture Notes on ``Combinational Logic Circuits`` (PPT Slides)

ENG241
Digital Design
Week #3 Part (a)
Cont ..
Combinational Logic Circuits
Resources

Chapter #2, Mano Sections




2.6
2.7
2.8
2.9
Multi-Level Circuit Optimization
Other Gate Types
Exclusive-OR Operator and Gates
High Impedance Outputs
2
Week #3 Topics








NAND, NOR Universal Gates
AND-OR to NAND Implementations
XOR Gates, XNOR Gates
Odd/Even Parity
Logic Families
Electrical Characteristics3
Multiple Level Circuits
High Impedance Outputs
3
NAND is Universal


Any digital circuit can be designed and realized using
AND, OR, NOT gates
If we can prove that NAND gate can emulate AND,
OR, NOT, then we prove that it is Universal
4
NAND is Universal
5
NAND = AND-NOT = NOT-OR

Also reverse inverter diagram for clarity
6
NOR also Universal

Dual of
NAND
7
NAND and NOR Implementations


Digital circuits are frequently constructed with only
NAND and NOR implementations:
 Both are universal gates
 they are easier to make (CMOS Technology)
Because of their use, rules have been developed
that allow us to convert Boolean functions using
AND, OR and NOT into the equivalent NAND and
NOR logic diagrams.
8
Multilevel NAND Circuits

The general procedure for converting a multi-level
AND-OR diagram into an all-NAND diagram is as
follows:
 Convert all AND gates to NAND gates with ANDNOT graphic symbols
 Convert all OR gates to NAND gates with NOT-OR
graphic symbols
 Check all the bubbles in the diagram
 Every bubble that is not compensated by
another along the same line will require the
insertion of an inverter or complement the
input literal
9
Sum of Products with NAND
Easy to think of bubbles as canceling
10
AND-OR Circuit Easy to Convert
11
Exclusive-OR Function

Exclusive-OR (XOR) performs the
following function



x  y = xy’ + x’y
This function is equal to one only if
either x or y is equal to one but not
both.
Another name for the XOR is the
ODD FUNCTION!!
12
Exclusive OR


Exclusive OR
Symbol is 

Plus in a circle
13
XOR Implementations
14
XOR Postulates and Theorems



Exclusive NOR (XNOR) can be generated by taking
the complement of an XOR operation
 (x  y)’ = xy + x’y’
The following identities apply to XOR (IMP!)
 x  0 = x
 x  1 = x’
 x  x = 0
 x  x’ = 1
 x  y’ = x’  y = (x  y)’
XOR is also commutative and associative
15
XOR = Odd Function



The XOR operation with three or more variables can be
converted into an ordinary Boolean function by
replacing the  with its equivalent Boolean expression
 A  B  C = (AB’ + A’B)C’ + (AB + A’B’)C

AB’C’ + A’BC’ + ABC + A’B’C

∑(1, 2, 4, 7)
This function is equal to 1 only if one variable is equal to
1 or if all three variables are equal to 1.
 This implies that an odd number of variables must be
one. This is defined as an odd function.
The complement of an odd function is an even
function (XNOR)
16
Recall .. Error Detecting Codes
 Parity
One bit added to a group of bits to make the total number
of ‘1’s (including the parity bit) even or odd
4-bit Example
7-bit Example
● Even
1
0 1 1 1
0
1 0 0 0 0 0 1
● Odd
0
0 1 1 1
1
1 0 0 0 0 0 1
 Good for checking single-bit errors
17
Parity Generation and Checking

XOR functions are very
useful in systems
requiring errordetection and
correction codes.
 A circuit that
generates a parity
bit is called a
parity generator.
 The circuit that
checks the parity is
called a parity
checker.
18
Parity Generator

Design even parity generator for 3-bit
signal



Perhaps make truth table and K-Map
Draw with XOR, then sum-of-products w/
NAND gates
How do you design a detector?
19
Parity Bit Implementation
X
Y
P
Z
20
Buffer



No inversion
No change, except
in power or voltage
Used to enable
driving more inputs
21
Binary Signaling (Noise Margin)

Zero volts


FALSE or 0
5 volts

A
Y
TRUE or 1
Noise
A
Y
A
Y
22
Tri-State

Output w/ 3 states: H, L, and Hi-Z



High impedance
Behaves like no output connection if in
Hi-Z state
Allows connecting multiple outputs
23
Multiplexed with Hi-Z

Normal operation is blue area
Smoke
24
Electrical Characteristics





Fan in – max number of inputs to a gate
Fan out – how many standard loads it
can drive (load usually 1)
Voltage – often 1.8v, 3.3v or 5v
Noise margin – how much electrical
noise it can tolerate
Power dissipation – how much power
chip needs



TTL high
Some CMOS low (but look at heat sink on a
Pentium)
Propagation delay – next
25
Propagation Delay


Max of high-to-low and low-to-high
Maximum and typical given
26
ENG241
Digital Design
Week #3 Part (b)
Combinational Logic Design
Resources

Chapter #3, Mano Sections



3.1 Design Concepts and Automation
3.2 The Design Space
3.3 Design Procedure
28
Week #3 Topics





Combinational Circuits
Analysis versus Design
Design Hierarchy
CAD Tools
Design Procedure
29
Combinational Circuits

A combinational logic circuit has:
 A set of m Boolean inputs,
 A set of n Boolean outputs, and

The output depends
only on the current input values
No Feedback, no cycles
A block diagram:


Combinatorial
Logic
Circuit
m Boolean Inputs
n Boolean Outputs
30
Sequential Circuits
A sequential circuit consists of combinational circuits to which
storage elements are connected to form a feedback path.
Storage elements store binary information.
Outputs of a sequential circuit are a function of the inputs
and the internal state of the storage elements.
31
Analysis vs. Design


Design of a circuit starts with specification and
ends up with a logic diagram.
Analysis for a combinational circuit consists of
determining the function that the circuit
implements with:



o
A set of Boolean functions or
A truth table, together with a possible explanation of the
operation of the circuit.
We can perform the analysis by manually finding the
Boolean equations or truth table.
The first step in the analysis is to make sure that
the given circuit is combinational and not
sequential (i.e. no feedback or storage elements).
32
Derivation of Func. Or Table
Label gate outputs of input variables
1.

Label outputs of gates fed by previously
labeled gates
2.

3.
Determine Boolean functions or values
Determine Boolean function or values
Repeat 2 until done
33
Let’s do this Example
T 3  AT 1  AB C
T 1  BC
34
Cont .. Analysis Example
T1  BC
T 2  AB
T 3  AT 1  AB C
T 4  T 2  D  ( A B)  D  A BD  AD  B D
T 5  T 2 D A B D
F 2  T 5  A B D
F1 
T3T 4 
A B C  A BD  AD  B D
35
Derivation of Truth Table




Make table with 2n rows, where n is
number of inputs
Label some gate outputs
Put those labels and the final outputs
on columns of truth table
Work your way across
36
Derivation of Truth Table
T1  BC
A
B
C
D
T1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
0
T2
T3
T4
F1
F2
37
Design Procedure
1.
2.
3.
4.
Specification

Write a specification for the circuit if one is not
already available
Formulation

Derive a truth table or initial Boolean equations
that define the required relationships between
the inputs and outputs, if not in the
specification
Optimization

Use K-Maps to simplify Boolean Expression.
Draw a logic diagram or provide a netlist for the
resulting circuit using ANDs, ORs, and inverters
38
Design Procedure
4.
5.

Technology Mapping

Map the logic diagram or netlist to the
implementation technology selected (FPGA, PCB)
Verification

Verify the correctness of the final design
HOW TO DEAL WITH A LARGE DESIGN?
39
Design Hierarchy

Just similar to large software
development:
1.

Divide and Conquer


To design a large chip we need hierarchy
To create and also to understand
Block is equivalent to object
40
Example



9-input odd function (parity for byte)
Basically checks for even parity!
Block for schematic is box with labels
Without hierarchy how
would you start your
design?
41
Design Broken Into Modules
Use 3-input odd functions
42
Each Module uses XOR
43
Use NAND to Implement XOR

In case there’s no XOR, for example
44
Components in Design

RHS shows what must be designed
45
Example – 4-bit Comparator

Specifications:


o
Input: 2 vectors A(3:0) and B(3:0)
Output: One bit, E, which is 1 if A and B
are bitwise equal, 0 otherwise
Straight forward implementation??
46
Formulation

Since the circuit has eight inputs, use of
truth table for formulation is impractical!



We need to create a truth table with 256
entries!!
In order for A[3:0] and B[3:0] to be
equal, the bit values in each of the
respective positions, 3 down-to 0, of A
and B must be equal.
Use intuition to immediately develop a
multiple level circuit. How?
47
Design
Use Hierarchical Design:
Decompose the problem into:




Four 1-bit comparison circuits
(i.e., One Module/bit)
An additional circuit that
combines the four comparison
circuit outputs to obtain E (i.e.,
Final Module for E)
48
Design for MX module
Define the output of the circuit to be:
• `0’ if both inputs are similar and
• `1’ if they are different?

Logic function is

Can implement as
Ai
Bi
Ei
0
0
0
0
1
1
1
0
1
1
1
0
Ei  Ai Bi  Ai Bi
49
4-bit comparison??
E
50
Design for ME module



Final E is 1 only if all intermediate
values are 0
Design for MX module
So
A
B
E
E  E0  E1  E2  E3
0
0
0
i
And a design is
i
i
0
1
1
1
0
1
1
1
0
51
Overall Design
E  E0  E1  E2  E3
52
53
CMOS Technology
54
Semiconductor Materials
Electronic materials generally can be
divided into three categories:




The primary parameter used to
distinguish among these materials is
the resistivity (rho)





Insulators
Semiconductors
Conductors
Insulator
105 < rho
Semiconductors 10-3 < rho < 105
Conductors
rho < 10-3
Silicon and germanium are the most
important semiconductor materials
55
P-type and N-type
The real advantage of semiconductors
emerge when impurities are added to the
material in minute amounts (Doping)

Impurity doping enables us to change the
resistivity over a very wide range and
determine whether the electron or hole
population controls the resistivity of the
material.



Donor Impurities: have five valence electrons in the
outer shell (phosphorus and arsenic). Semiconductors
doped with donor impurities are called n-type.
Acceptor Impurities: have one less electron than silicon
in the outer shell (boron). Semiconductors doped with
acceptor impurities are known as p-type.
56
The MOS Transistor
Polysilicon
Aluminum
57
Transistor as a Switch
A Switch!
An MOS Transistor
VGS  V T
|VGS|
Ron
S
58
D
Implementing Logic using:
nMOS vs. pMOS Devices
59
Static Complementary MOS (CMOS)
VDD
In1
In2
PUN and PDN are dual logic networks
PMOS only
PUN
InN
In1
In2
InN
F(In1,In2,…InN)
PDN
NMOS only
VSS
 At every point in time (except during the switching transients)
each gate output is connected to either VDD or VSS via a low
resistive path
60
CMOS Inverter
Pull-up
Network
A
Y
VDD
0
1
A
A
Y
Y
GND
Pull-down
Network
61
CMOS Inverter
A
Y
VDD
0
1
OFF
0
A=1
Y=0
ON
A
Y
GND
62
CMOS Inverter
A
Y
0
1
1
0
VDD
ON
A=0
Y=1
OFF
A
Y
GND
63
CMOS Tri-State Inverter
E
0
1
1
A
X
0
1
A
Y
Z
1
0
A
E
Y
Y
E
64
Example Gate: NAND
65
Example Gate: NOR
66
Top-Down versus Bottom-Up



A top-down design proceeds from an abstract,
high-level specification to a more and more detailed
design by decomposition and successive refinement
A bottom-up design starts with detailed primitive
blocks and combines them into larger and more
complex functional blocks
Designs usually proceed from both directions
simultaneously
 Top-down design answers: What are we building?


Top-down controls complexity
Bottom-up design answers: How do we build it?

Bottom-up focuses on the details
67
Others
68
NAND Gates

Very common for discrete logic
69
NOR Gates


NOT OR
Also common
F  X Y
X Y
Z
0
0
1
0
1
0
1
1
0
1
0
0
70
Negative Logic

Assign 0 to H
71
AND Gate Specification
72
Positive vs. Negative Logic
73
Bottom Line


Not much real change
Negative logic functions are just
duals of positive logic ones


OR -> AND
AND -> OR
74
Simulation Delays


A simulator can model timing
phenomena in two ways
Transport delay


Output after a specified time
Inertial delay

No effect if input occurs for time that is
too short (can’t overcome inertia) –
smaller than transport delay time
75
Effect of Transport Delay (blue)

Delay just shifts signal in time
76
Effect of Inertial Delay
Blue – Propagation delay time
Black – Rejection time
77
Design
Hierarchy
78
Hierarchical Design


No need to ever draw full schematic
with every gate
Abstract at the appropriate level
79
Design Example
1.
Specification

BCD to Excess-3 code converter

Transforms BCD code for the decimal digits to
Excess-3 code for the decimal digits

BCD code words for digits 0 through 9: 4-bit
patterns 0000 to 1001, respectively

Excess-3 code words for digits 0 through 9: 4-bit
patterns consisting of 3 (binary 0011) added to
each BCD code word

Implementation:
 multiple-level circuit
 NAND gates (including inverters)
80
Design Example (continued)
2.




Formulation
Conversion of 4-bit codes can be most easily
formulated by a truth table
Variables
Input BCD
Output Excess-3
- BCD:
ABCD
WXYZ
A,B,C,D
0000
0011
Variables
0001
0100
- Excess-3
W,X,Y,Z
0010
0101
0011
0110
Don’t Cares
- BCD 1010
0100
0111
to 1111
0101
1000
0110
0111
1000
1001
1001
1010
1011
1011
81
Design Example (continued)
z
3.
Optimization
a.
2-level using
K-maps
W = A + BC + BD
C
1
1
0
1
3
4
5
7
1
X
X
12
13
8
9
1
B
1
4
5
A
X
X
13
8
9
1
1
0
4
5
7
6
4
1
1
X
13
1
10
3
1
8
X
C
2
A
B
14
11
w
3
12
X
X
1
X
6
15
1
0
X
7
X
12
10
C
1
2
D
x
Z = D
3
1
X
14
11
0
D
X = BC + BD + B C D
Y = CD + C D
X
X
1
1
6
15
1
C
2
1
X
A
y
X
15
X
9
11
D
B
X
14
10
X
1
7
X
13
1
8
1
5
12
A
X
1
2
6
X
15
X
9
11
D
14
X
10
82
B
Levels of Integration

SSI Small Scale Integrated


MSI Medium Scale Integrated




Individual gates
Things like counters, single-block
adders, etc.
Like stuff we’ll be doing next
LSI
VLSI Very Large Scale Integrated

Larger circuits, like the FPGA, Pentium,
etc.
83
Logic Families


RTL, DTL earliest
TTL was used 70s, 80s



CMOS



Still available and used occasionally
7400 series logic, refined over
generations
Was low speed, low noise
Now fast and is most common
BiCMOS and GaAs

Speed
84