Transcript CS1104: Computer Organisation

CT455: Computer Organization
Logic gate
Lecture 4:
Logic Gates and Circuits
 Logic Gates







The Inverter
The AND Gate
The OR Gate
The NAND Gate
The NOR Gate
The XOR Gate
The XNOR Gate
 Drawing Logic Circuit
 Analysing Logic Circuit
 Propagation Delay
Lecture 4:
Logic Gates and Circuits
 Universal Gates: NAND and NOR
 NAND Gate
 NOR Gate






Implementation using NAND Gates
Implementation using NOR Gates
Implementation of SOP Expressions
Implementation of POS Expressions
Positive and Negative Logic
Integrated Circuit Logic Families
Digital (logic) Elements: Gates
Digital devices or gates have one or more inputs and
produce an output that is a function of the current input
value(s).
All inputs and outputs are binary and can only take the
values 0 or 1
A gate is called a combinational circuit because the
output only depends on the current input combination.
Digital circuits are created by using a number of
connected gates such as the output of a gate is
connected to to the input of one or more gates in such a
way to achieve specific outputs for input values.
Digital or logic design is concerned with the design of
such circuits.
Introduction
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
CS1103
Chapter 1: Introduction
Logic Gates
 Gate Symbols
AND
OR
a
b
a
b
NOT
a
a
NAND
NOR
EXCLUSIVE OR
Symbol set 2
Symbol set 1
b
a
b
a
b
a.b
a+b
a'
(a.b)'
(a+b)'
ab
(ANSI/IEEE Standard 91-1984)
a
&
a.b
b
a
b
a
a
b
a
b
a
b
1
a+b
1
a'
&
(a.b)'
1
(a+b)'
=1
ab
Truth Tables
Provides a listing of every possible
combination of values of binary inputs to a
digital circuit and the corresponding
outputs.
INPUTS
…
…
OUTPUTS
…
…
Example (2 inputs, 2
outputs):
inputs Truth table outputs
x
0
0
1
1
y
0
1
0
1
x.y
0
0
0
1
x+y
0
1
1
1
inputs
x
y
outputs
Digital
circuit
x.y
x+y
Basic Concepts
Simple gates
 AND
 OR
 NOT
Functionality can be
expressed by a truth
table
 A truth table lists
output for each
possible input
combination
Other methods
 Logic expressions
 Logic diagrams
CS1103
Chapter 1: Introduction
Basic Concepts (cont’d)
Additional useful
gates
 NAND
 NOR
 XOR
NAND = AND + NOT
NOR = OR + NOT
XOR implements
exclusive-OR
function
NAND and NOR gates
require only 2
transistors
 AND and OR need
CS1103 3 transistors!
Chapter 1: Introduction
Realizing Logic in Hardware
Boolean Algebra and truth tables are essential
important tools to express logical relationships.
To use these tools in the real world , we must have
some physical way to represent TRUE and FALSE (T
and F).
In, digital electronic circuits, T and F are represented
by voltage levels:

The transistor-transistor logic (TTL) 74LS family of digital
integrated circuits produces two voltage levels:
< .5V which represents low voltage L (0)
and,
> 2.7V which represents high voltage H (1)
for the digital device.
Electronic Logic Gates
Electrical Signals and Logic Values
Electric Signal
High Voltage (H)
Low Voltage (L)



CS1103
Logic Value
Positive Logic
Negative Logic
1
0
0
1
A signal that is set to logic 1 is said to be asserted,
active, or true.
An active-high signal is asserted when it is high
(positive logic).
An active-low signal is asserted when it is low
(negative logic).
Chapter 1: Introduction
Logic Gates: The Inverter
 The Inverter
A A'
A
A'
A
0
1
A'
 Application of the inverter: complement.
Binary number
1
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
1’s Complement
1
0
Logic Gates: The AND Gate
 The AND Gate
A
A.B
B
A
0
0
1
1
B
0
1
0
1
A.B
0
0
0
1
A
B
&
A.B
Logic Gates: The AND Gate
 Application of the AND Gate
1 sec
A
A
Enable
Counter
Enable
1 sec
Reset to zero
between
Enable pulses
Register,
decode
and
frequency
display
Logic Gates: The OR Gate
 The OR Gate
A
A+B
B
A
0
0
1
1
B
0
1
0
1
A+B
0
1
1
1
A
B
1
A+B
Logic Gates: The NAND Gate
 The NAND Gate
A
(A.B)'
B
A
0
0
1
1
B
0
1
0
1

(A.B)'
1
1
1
0
A
(A.B)'
B
A
&
(A.B)'
B

NAND
Negative-OR
Logic Gates: The NOR Gate
 The NOR Gate
A
(A+B)'
B
A
0
0
1
1
B
0
1
0
1

(A+B)'
1
0
0
0
A
(A+B)'
B
A
1
(A+B)'
B

NOR
Negative-AND
Logic Gates: The XOR Gate
 The XOR Gate
A
AB
B
A
0
0
1
1
B
0
1
0
1
AB
0
1
1
0
A
B
=1
AB
Logic Gates: The XNOR Gate
 The XNOR Gate
A
(A  B)'
B
A
0
0
1
1
B (A  B) '
0
1
1
0
0
0
1
1
A
B
=1
(A  B)'
Basic Concepts (cont’d)
Proving NAND gate is universal
CS1103
Chapter 1: Introduction
Basic Concepts (cont’d)
Proving NOR gate is universal
CS1103
Chapter 1: Introduction
Drawing Logic Circuit
 When a Boolean expression is provided, we can
easily draw the logic circuit.
 Examples:
(i) F1 = xyz' (note the use of a 3-input AND gate)
x
y
z
F1
z'
Drawing Logic Circuit
(ii) F2 = x + y'z (can assume that variables and their
complements are available)
x
F2
y'
z
(iii) F3 = xy' + x'z
y'z
x
y'
xy'
F3
x'
z
x'z
Analysing Logic Circuit
 When a logic circuit is provided, we can analyse the
circuit to obtain the logic expression.
 Example: What is the Boolean expression of F4?
A'
B'
A'B'
A'B'+C
C
F4 = (A'B'+C)' = (A+B).C'
(A'B'+C)'
F4
Logic Functions (cont’d)
3-input majority function
A
B
C
F
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
0
1
0
1
1
1
CS1103
Logical expression
form
F=AB+BC+AC
Chapter 1: Introduction
Propagation Delay
 Every logic gate experiences some delay (though
very small) in propagating signals forward.
 This delay is called Gate (Propagation) Delay.
 Formally, it is the average transition time taken for the
output signal of the gate to change in response to
changes in the input signals.
 Three different propagation delay times associated
with a logic gate:
 tPHL: output changing from the High level to Low level
 tPLH: output changing from the Low level to High level
 tPD=(tPLH + tPHL)/2
(average propagation delay)
Propagation Delay
Input
Output
H
Input
L
Output
H
L
tPHL
tPLH
Propagation Delay
A
B
 In reality, output signals
 Ideally, no
normally lag behind
input signals:
delay:
1
0
1
Signal for A
1
0
1
C
0
Signal for A
1
Signal for B
Signal for C
0
0
1
Signal for B
Signal for C
0
time
time
Calculation of Circuit Delays
 Amount of propagation delay per gate depends on:
 (i) gate type (AND, OR, NOT, etc)
 (ii) transistor technology used (TTL,ECL,CMOS etc),
 (iii) miniaturisation (SSI, MSI, LSI, VLSI)
 To simplify matters, one can assume
 (i) an average delay time per gate, or
 (ii) an average delay time per gate-type.
 Propagation delay of logic circuit
= longest time it takes for the input signal(s) to propagate to the
output(s).
= earliest time for output signal(s) to stabilise, given that input
signals are stable at time 0.
Calculation of Circuit Delays
 In general, given a logic gate with delay, t.
t1
t2
:
tn
:
Logic
Gate
max (t1, t2, ..., tn ) + t
If inputs are stable at times t1,t2,..,tn, respectively; then the
earliest time in which the output will be stable is:
max(t1, t2, .., tn) + t
 To calculate the delays of all outputs of a
combinational circuit, repeat above rule for all gates.
Calculation of Circuit Delays
 As a simple example, consider the full adder circuit
where all inputs are available at time 0. (Assume
each gate has delay t.)
X 0
Y 0
max(0,0)+t = t
max(t,0)+t = 2t
S
t
2t
max(t,2t)+t = 3t
C
Z
0
where outputs S and C, experience delays
of 2t and 3t, respectively.
Universal Gates: NAND and NOR
 AND/OR/NOT gates are sufficient for building any
Boolean functions.
 We call the set {AND, OR, NOT} a complete set of
logic.
 However, other gates are also used because:
(i) usefulness
(ii) economical on transistors
(iii) self-sufficient
NAND/NOR: economical, self-sufficient
XOR: useful (e.g. parity bit generation)
NAND Gate
 NAND gate is self-sufficient (can build any logic
circuit with it).
Therefore, {NAND} is also a complete set of logic.

 Can be used to implement AND/OR/NOT.
 Implementing an inverter using NAND gate:
x
(x.x)' = x'
x'
(T1: idempotency)
NAND Gate
 Implementing AND using NAND gates:
x
y
(x.y)'
x.y
((xy)'(xy)')' = ((xy)')' idempotency
= (xy)
involution
 Implementing OR using NAND gates:
x
y
x'
((xx)'(yy)')' = (x'y')' idempotency
= x''+y'' DeMorgan
x+y
= x+y
involution
y'
NOR Gate




NOR gate is also self-sufficient.
Therefore, {NOR} is also a complete set of logic
Can be used to implement AND/OR/NOT.
Implementing an inverter using NOR gate:
x
(x+x)' = x'
x'
(T1: idempotency)
NOR Gate
 Implementing AND using NOR gates:
x'
x
y
y'
x.y
((x+x)'+(y+y)')'=(x'+y')'
= x''.y''
= x.y
idempotency
DeMorgan
involution
 Implementing OR using NOR gates:
x
y
(x+y)'
x+y
((x+y)'+(x+y)')' = ((x+y)')' idempotency
= (x+y)
involution
Implementation using NAND
gates
 Possible to implement any Boolean expression using
NAND gates.
Procedure:
(i) Obtain sum-of-products Boolean expression:
e.g. F3 = xy'+x'z
(ii) Use DeMorgan theorem to obtain expression
using 2-level NAND gates
e.g. F3 = xy'+x'z
= (xy'+x'z)' '
involution
= ((xy')' . (x'z)')' DeMorgan
Implementation using NAND gates
x
y'
(xy')'
F3
x'
z
(x'z)'
F3 = ((xy')'.(x'z)') ' = xy' + x'z
Implementation using NOR gates
 Possible to implement any Boolean expression using
NOR gates.
Procedure:
(i) Obtain product-of-sums Boolean expression:
e.g. F6 = (x+y').(x'+z)
(ii) Use DeMorgan theorem to obtain expression
using 2-level NOR gates.
e.g. F6 = (x+y').(x'+z)
= ((x+y').(x'+z))' ' involution
= ((x+y')'+(x'+z)')' DeMorgan
Implementation using NOR gates
x
y'
(x+y')'
F6
x'
z
(x'+z)'
F6 = ((x+y')'+(x'+z)')'
= (x+y').(x'+z)
Logical Equivalence
All three circuits implement F = A B
function
CS1103
Chapter 1: Introduction
Logical Equivalence (cont’d)
Derivation of logical expression from a
circuit
 Trace from the input to output
Write down intermediate logical
expressions along the path
CS1103
Chapter 1: Introduction
Logical Equivalence (cont’d)
Proving logical equivalence: Truth table method
A
0
0
1
1
CS1103
B
0
1
0
1
F1 = A B
0
0
0
1
F3 = (A + B) (A + B) (A + B)
0
0
0
1
Chapter 1: Introduction
Implementation of SOP Expressions
 Sum-of-Products expressions can be implemented
using:
 2-level AND-OR logic circuits
 2-level NAND logic circuits
 AND-OR logic circuit
A
B
C
D
E
F = AB + CD + E
F
Implementation of SOP Expressions
 NAND-NAND circuit (by
A
circuit transformation)
B
a) add double bubbles
b) change OR-withinverted-inputs to NAND
& bubbles at inputs to
their complements
C
D
F
E
A
B
C
D
E'
F
Deriving Logical Expressions (cont’d)
3-input majority function
A
B
C
F
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
0
1
0
1
1
1
CS1103
SOP logical expression
Four product terms

Because there are 4 rows with a
1 output
F = A B C + A B C +A B C + A B C
Sigma notation
S(3, 5, 6, 7)
Chapter 1: Introduction
Brute Force Method of Implementation
3-input even-parity
function
SOP implementation
A
B
C
F
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
1
CS1103
Chapter 1: Introduction
Implementation of POS Expressions
 Product-of-Sums expressions can be implemented
using:
 2-level OR-AND logic circuits
 2-level NOR logic circuits
 OR-AND logic circuit
A
B
G = (A+B).(C+D).E
C
D
E
G
Implementation of POS Expressions
 NOR-NOR circuit (by
circuit transformation):
a) add double bubbles
b) changed AND-withinverted-inputs to NOR
& bubbles at inputs to
their complements
A
B
C
D
G
E
A
B
C
D
E'
G
Deriving Logical Expressions (cont’d)
3-input majority
function
A
B
C
F
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
0
1
0
1
1
1
CS1103
POS logical expression
Four sum terms
 Because there are 4
rows with a 0 output
F = (A + B + C) (A + B + C)
(A + B + C) (A + B + C)
Pi notation
 (0, 1, 2, 4 )
Chapter 1: Introduction
Brute Force Method of
Implementation
3-input even-parity
function
POS implementation
A
B
C
F
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
1
CS1103
Chapter 1: Introduction
Positive & Negative Logic
 In logic gates, usually:
 H (high voltage, 5V) = 1
 L (low voltage, 0V) = 0
 This convention – positive logic.
 However, the reverse convention, negative logic
possible:
 H (high voltage) = 0
 L (low voltage) = 1
 Depending on convention, same gate may denote
different Boolean function.
Positive & Negative Logic
 A signal that is set to logic 1 is said to be asserted, or
active, or true.
 A signal that is set to logic 0 is said to be deasserted,
or negated, or false.
 Active-high signal names are usually written in
uncomplemented form.
 Active-low signal names are usually written in
complemented form.
Positive & Negative Logic
Positive logic:
Enable
Active High:
0: Disabled
1: Enabled
Enable
Active Low:
0: Enabled
1: Disabled
Negative logic:
Integrated Circuit Logic Families
 Some digital integrated circuit families: TTL, CMOS,
ECL.
 TTL: Transistor-Transistor Logic.
 Uses bipolar junction transistors
 Consists of a series of logic circuits: standard TTL, low-
power TTL, Schottky TTL, low-power Schottky TTL,
advanced Schottky TTL, etc.
Integrated Circuit Logic Families
TTL Series
Prefix Designation Example of Device
Standard TTL
54 or 74
7400 (quad NAND gates)
Low-power TTL
54L or 74L
74L00 (quad NAND gates)
Schottky TTL
54S or 74S
74S00 (quad NAND gates)
Low-power
Schottky TTL
54LS or 74LS
74LS00 (quad NAND gates)
Integrated Circuit Logic Families
 CMOS: Complementary Metal-Oxide Semiconductor.
 Uses field-effect transistors
 ECL: Emitter Coupled Logic.
 Uses bipolar circuit technology.
 Has fastest switching speed but high power consumption.
Integrated Circuit Logic Families
 Performance characteristics
 Propagation delay time.
 Power dissipation.
 Fan-out: Fan-out of a gate is the maximum number of
inputs that the gate can drive.
 Speed-power product (SPP): product of the propagation
delay time and the power dissipation.
Drawing Logic Circuits
When a Boolean expression is provided,
we can easily draw the logic circuit.
Examples:
F1 = xyz'
(note the use of a 3-input AND gate)
x
y
z
F1
z'
Analysing Logic Circuits
When a logic circuit is provided, we can
analyse the circuit to obtain the logic
expression.
Example: What is the Boolean expression
of F4?
A'
B'
C
A'B'
A'B'+C
(A'B'+C)'
F4
F4 = (A'B'+C)'
Analysing Logic Circuit
Example: What is Boolean expression of F5?
x
F5
y
z
F5 =
Simple Circuit Design: Two-input
Multiplexer
Multiplexer with two input bits, A, B and a control input
bit S and output Z. Depending on the value of S, the
circuit is to transfer either the the value of A or B to the
output Z
A
Truth table from
Z
circuit description
S
0
0
0
0
1
1
1
1
A
0
0
1
1
0
0
1
1
B
0
1
0
1
0
1
0
1
Z
0
0
1
1
0
1
0
1
B
Using logic design methods
(to be studied later) we get the
optimal logic function for Z
Z = S’. A + S . B
A
S
S’. A
S
B
Z
S’. A + S . B
S.B
Analysis of Combinational Circuits (1)
Digital Circuit Design:

Word description of a function
 a set of switching equations
 hardware realization (gates, programmable logic
devices, etc.)
Digital Circuit Analysis:

Hardware realization
 switching expressions, truth tables, timing diagrams, etc.
Analysis is used

To determine the behavior of the circuit

To verify the correctness of the circuit

To assist in converting the circuit to a different form.
CS1103
Chapter 1: Introduction
Analysis of Combinational Circuits (2)
Algebraic Method: Use switching algebra to derive a desired
form.
Example 2.33: Find a simplified switching expressions and logic
network for the following logic circuit (Fig. 2.21a).
a
b
a
c
b
c
P1
P4
f (a, b, c)
P2
P3
(a)
CS1103
Chapter 1: Introduction
Analysis of Combinational Circuits (3)
Write switching expression for each gate output:
P1  ab, P2  a  c, P3  b  c , P4  P1  P2  ab  (a  c)
The output is:f (a, b, c)  P3  P4  (b  c )  ab  (a  c)

Simplify the output function using switching algebra:
f (a, b, c)  (b  c )  ab  a  c
 bc  b c  ab  a  c
 bc  b c  (a  b )ac
 bc  b c  ab c
 bc  b c
f (a, b, c)
=b c
Therefore, f (a,b,c) = (b
b
c
CS1103
bc
c)' =
f (a, b, c)
Chapter 1: Introduction
[Eq. 2.24]
[T8]
[T5(b)]
[T4(a)]
[Eq. 2.32]
Analysis of Combinational Circuits (4)
Example 2.34: Find a simplified switching expressions and logic
network for the following logic circuit (Fig. 2.22).
a
b
b
c
a
b
a
c
a
b
(a
b
b)(b
c)
c
f (a, b, c)
a +b
a +b +a +c
a +c
Given circuit
CS1103
Chapter 1: Introduction
Analysis of Combinational Circuits (5)
Derive the output expression:
f(a,b,c)
= (a  b)(b  c)  (a  b  a  c)
= (a  b)(b  c)  a  b  a  c)
= (a  b)(b  c)  (a  b )(a  c)
(ab  a b)(bc  b c)  (a  b )(a  c)
=
ab bc  ab b c  a bbc  a bb c  a a  a c  ab  b c
=
ab c  a bc  a c  ab  b c
= a bc  a c  ab  b c
= a bc  a c  ab
= a b  a c  ab
a
= ac  a  b
c
f (a, b, c)
=
a
b
Simplified circuit
CS1103
Chapter 1: Introduction
[T8(b)]
[T8(a)]
[Eq. 2.24]
[P5(b)]
[P6(b), T4(a)]
[T4(a)]
[T9(a)]
[T7(a)]
[Eq. 2.24]
Analysis of Combinational Circuits (6)
Truth Table Method: Derive the truth table one gate at a time.
The truth table for Example 2.34:
abc
000
001
010
011
100
101
110
111
CS1103
ac
0
1
0
1
0
0
0
0
a b
0
0
1
1
1
1
0
0
Chapter 1: Introduction
f(a,b,c)
0
1
1
1
1
1
0
0
Analysis of Combinational Circuits (7)
Analysis of Timing Diagrams
 Timing diagram is a graphical representation of
input and output signal relationships over the time
dimension.
 Timing diagrams may show intermediate signals
and propagation delays.
CS1103
Chapter 1: Introduction
Analysis of Combinational Circuits (8)
Example 2.35: Derivation of truth table from a timing
diagram
A
A
B
B
Y = fa (A, B, C)
C
Inputs
Outputs
Z = fb (A, B, C) Y = fa (A, B, C)
Z = fb (A, B, C)
C
t0
(a)
t2
(b)
Inputs
Time
ABC
Outputs
fa(A, B, C)
fb(A, B, C)
t0
000
0
0
t1
001
1
1
t2
010
1
0
t3
011
0
1
t4
100
0
0
t5
101
0
1
t6
110
1
1
t7
111
1
0
(c)
CS1103
t1
Chapter 1: Introduction
t3
t4
t5
t6
t7
CS1103
Chapter 1: Introduction
Integrated Circuits
An Integrated circuit (IC) is a number of
logic gated fabricated on a single silicon
chip.
ICs can be classified according to how
many gates they contain as follows:




Small-Scale Integration (SSI): Contain 1 to 20 gates.
Medium-Scale Integration (MSI): Contain 20 to 200 gates.
Examples: Registers, decoders, counters.
Large-Scale Integration (LSI): Contain 200 to 200,000 gates.
Include small memories, some microprocessors, programmable
logic devices.
Very Large-Scale Integration (VLSI): Usually stated in terms
of number of transistors contained usually over 1,000,000.
Includes most microprocessors and memories.
Computer Hardware Generations
The First Generation, 1946-59: Vacuum Tubes, Relays,
Mercury Delay Lines:
ENIAC (Electronic Numerical Integrator and Computer):
First electronic computer, 18000 vacuum tubes, 1500 relays,
5000 additions/sec.

First stored program computer: EDSAC (Electronic Delay
Storage Automatic Calculator).
The Second Generation, 1959-64: Discrete Transistors.

(e.g IBM 7000 series,
DEC PDP-1)
The Third Generation, 1964-75: Small and MediumScale Integrated (SSI, MSI) Circuits. (e.g. IBM 360
mainframe)
The Fourth Generation, 1975-Present: The
Microcomputer. VLSI-based Microprocessors.
Hierarchy of Computer Architecture
High-Level Language Programs
Software
Assembly Language
Programs
Application
Operating
System
Machine Language
Program
Compiler
Software/Hardware
Boundary
Firmware
Instr. Set Proc. I/O system
Instruction Set
Architecture
Datapath & Control
Hardware
Digital Design
Circuit Design
Microprogram
Layout
Logic Diagrams
Circuit Diagrams
Register Transfer
Notation (RTN)
Summary
Logic Gates
AND,
OR,
NOT
NAND
NOR
Implementation of a
Boolean expression
using these
Universal gates.
Drawing Logic
Circuit
Analysing
Logic Circuit
Given a Boolean
expression, draw the
circuit.
Given a circuit, find
the function.
Implementation
of SOP and POS
Expressions
Concept of Minterm
and Maxterm
Positive and
Negative Logic
End of file