Digital Logic Circuits 1 Introduction

DIGITAL LOGIC CIRCUITS

Logic Gates

Boolean Algebra

Map Specification

Combinational Circuits

Flip-Flops

Sequential Circuits

Computer Organization Computer Architectures Lab

Digital Logic Circuits 2 Logic Gates

BASIC LOGIC BLOCK - GATE -

Binary Binary
Digital Digital
. Gate Output
Input .
Signal . Signal

Types of Basic Logic Blocks

- Combinational Logic Block

Logic Blocks whose output logic value
depends only on the input logic values

- Sequential Logic Block

Logic Blocks whose output logic value
depends on the input values and the
state (stored information) of the blocks

Functions of Gates can be described by

- Truth Table
- Boolean Function
- Karnaugh Map
Computer Organization Computer Architectures Lab
Digital Logic Circuits 3 Logic Gates

COMBINATIONAL GATES
Name Symbol Function Truth Table
A B X
A X=A•B 0 0 0
AND B
X or
X = AB
0
1
1
0
0
0
1 1 1
A B X
A 0 0 0
OR X X=A+B 0 1 1
B 1 0 1
1 1 1
A X
I A X X = A’ 0
1
1
0
A X
Buffer A X X=A 0 0
1 1
A B X
A 0 0 1
NAND X X = (AB)’ 0
1
1
0
1
1
B 1 1 0
A B X
A 0 0 1
NOR X X = (A + B)’ 0 1 0
B 1 0 0
1 1 0
A X=AB A B X
XOR X or 0 0 0
Exclusive OR 0 1 1
B X = A’B + AB’ 1 0 1
1 1 0
A B X
A X = (A  B)’
XNOR X or
0
0
0
1
1
0
Exclusive NOR
or Equivalence B X = A’B’+ AB 1 0 0
1 1 1

Computer Organization Computer Architectures Lab

Digital Logic Circuits 4 Boolean Algebra

BOOLEAN ALGEBRA
Boolean Algebra

* Algebra with Binary(Boolean) Variable and Logic Operations

* Boolean Algebra is useful in Analysis and Synthesis of
Digital Logic Circuits

- Input and Output signals can be

represented by Boolean Variables, and
- Function of the Digital Logic Circuits can be represented by
Logic Operations, i.e., Boolean Function(s)
- From a Boolean function, a logic diagram
can be constructed using AND, OR, and I

Truth Table

* The most elementary specification of the function of a Digital Logic

Circuit is the Truth Table

- Table that describes the Output Values for all the combinations
of the Input Values, called MINTERMS
- n input variables → 2n minterms

Computer Organization Computer Architectures Lab

Digital Logic Circuits 5 Boolean Algebra

LOGIC CIRCUIT DESIGN

x y z F
0 0 0 0
Truth 0 0 1 1
Table 0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Boolean F = x + y’z
Function

x
F
Logic y
Diagram
z

Computer Organization Computer Architectures Lab

 BASIC IDENTITIES OF
Digital Logic Circuits 6 Boolean Algebra

BOOLEAN
[1] x+0=x ALGEBRA
[2] x • 0 = 0
[3] x + 1 = 1 [4] x • 1 = x
[5] x + x = x [6] x • x = x
[7] x + x’ = 1 [8] x • X’ = 0
[9] x + y = y + x [10] xy = yx
[11] x + (y + z) = (x + y) + z [12] x(yz) = (xy)z
[13] x(y + z) = xy +xz [14] x + yz = (x + y)(x + z)
[15] (x + y)’ = x’y’ [16] (xy)’ = x’ + y’
[17] (x’)’ = x
[15] and [16] : De Morgan’s Theorem
Usefulness of this Table
- Simplification of the Boolean function
- Derivation of equivalent Boolean functions
to obtain logic diagrams utilizing different logic gates
-- Ordinarily ANDs, ORs, and Inverters
-- But a certain different form of Boolean function may be convenient
to obtain circuits with NANDs or NORs
→ Applications of De Morgans Theorem

x’y’ = (x + y)’ x’+ y’= (xy)’

I, AND → NOR I, OR → NAND

Computer Organization Computer Architectures Lab

Digital Logic Circuits 7 Boolean Algebra

EQUIVALENT CIRCUITS
Many different logic diagrams are possible for a given Function
F = ABC + ABC’ + A’C .......…… (1)
= AB(C + C’) + A’C [13] ..…. (2)
= AB • 1 + A’C [7]
= AB + A’C [4] ...…. (3)
A
B
(1) C
F

(2) A
B

C F

(3) A
B
F

Computer Organization Computer Architectures Lab

Digital Logic Circuits 8 Boolean Algebra

COMPLEMENT OF FUNCTIONS
A Boolean function of a digital logic circuit is represented by only using
logical variables and AND, OR, and Invert operators.

→ Complement of a Boolean function

- Replace all the variables and subexpressions in the parentheses

appearing in the function expression with their respective complements

A,B,...,Z,a,b,...,z  A’,B’,...,Z’,a’,b’,...,z’
(p + q)  (p + q)’

- Replace all the operators with their respective

complementary operators

AND  OR
OR  AND

- Basically, extensive applications of the De Morgan’s theorem

(x1 + x2 + ... + xn )’  x1’x2’... xn’

(x1x2 ... xn)'  x1' + x2' +...+ xn'

Computer Organization Computer Architectures Lab

Digital Logic Circuits 9 Map Simplification

SIMPLIFICATION
Truth Boolean
Table Function
Unique Many different expressions exist
Simplification from Boolean function

- Finding an equivalent expression that is least expensive to implement

- For a simple function, it is possible to obtain
a simple expression for low cost implementation
- But, with complex functions, it is a very difficult task

Karnaugh Map (K-map) is a simple procedure for

simplifying Boolean expressions.

Truth
Table
Simplified
Karnaugh Boolean
Map Function
Boolean
function

Computer Organization Computer Architectures Lab

Digital Logic Circuits 10 Map Simplification

KARNAUGH MAP
Karnaugh Map for an n-input digital logic circuit (n-variable sum-of-products
form of Boolean Function, or Truth Table) is
- Rectangle divided into 2n cells
- Each cell is associated with a Minterm
- An output(function) value for each input value associated with a
mintern is written in the cell representing the minterm
→ 1-cell, 0-cell

Each Minterm is identified by a decimal number whose binary representation

is identical to the binary interpretation of the input values of the minterm.
Karnaugh Map
x Identification x value
x
0
F
1 0 0 of the cell 0 0 of F

1 0 1 1 1 1
F(x) = (1)
1-cell
x
x y F
y 0 1 x0 1
0 0 0 0 0 1 y
0 1 1 0 0 1
1 0 1 1 2 3
1 1 1 1 1 0
F(x,y) =  (1,2)
Computer Organization Computer Architectures Lab
Digital Logic Circuits 11 Map Simplification

KARNAUGH MAP
x y z F
0 0 0 0
yz y yz
0 0 1 1
0 1 0 1 x 00 01 11 10 x 00 01 11 10
0 1 1 0 0 0 1 3 2 0 0 1 0 1
1 0 0 1 x 1 4 5 7 6
1 0 1 0 1 1 0 0 0
1 1 0 0 z
1 1 1 0 F(x,y,z) =  (1,2,4)

wx w
uv 00 01 11 10
u v w x F
0 0 0 0 0
0 0 0 1 1 00 0 1 3 2 v
0 0 1 0 0
0 0 1 1 1 01 4 5 7 6
0 1 0 0 0
u 11
12 13 15 14
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0 10 8 9 11 10
1
1
0
0
0
0
0
1
1
1
x
1 0 1 0 0 wx
1 0 1 1 1 uv 00 01 11 10
1 1 0 0 0 00 0 1 1 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0 01 0 0 0 1
11 0 0 0 1
10 1 1 1 0
F(u,v,w,x) =  (1,3,6,8,9,11,14)
Computer Organization Computer Architectures Lab
 MAP SIMPLIFICATION - 2
Digital Logic Circuits 12 Map Simplification

ADJACENT CELLS -
Rule: xy’ +xy = x(y+y’) = x
Adjacent cells

- binary identifications are different in one bit

→ minterms associated with the adjacent
cells have one variable complemented each other

Cells (1,0) and (1,1) are adjacent

Minterms for (1,0) and (1,1) are
x • y’ --> x=1, y=0
x • y --> x=1, y=1

F = xy’+ xy can be reduced to F = x

From the map y
x 0 1
0 0 0 2 adjacent cells xy’ and xy
1 1 1 → merge them to a larger cell x

F(x,y) =  (2,3)
= xy’+ xy
=x

Computer Organization Computer Architectures Lab

 MAP SIMPLIFICATION - MORE
Digital Logic Circuits 13 Map Simplification

THAN 2 CELLS - wx u’v’ wx u’x’

u’v’w’x’ + u’v’w’x + u’v’wx + u’v’wx’ w w
= u’v’w’(x’+x) + u’v’w(x+x’) uv uv
= u’v’w’ + u’v’w 1 1 1 1 1 1 1 1
= u’v’(w’+w) vw’ 1 1 1 1
v v
= u’v’ 1 1 1 1
u u
1 1 1 1
uw x
x v’x

u’v’w’x’+u’v’w’x+u’vw’x’+u’vw’x+uvw’x’+uvw’x+uv’w’x’+uv’w’x
= u’v’w’(x’+x) + u’vw’(x’+x) + uvw’(x’+x) + uv’w’(x’+x)
= u’(v’+v)w’ + u(v’+v)w’
= (u’+u)w’ = w’
wx
uv w uv w V’
1 1 1 1 1 1
w’
1 1
v v
1 1
u u 1 1 1 1 u
1 1 1 1 1 1
x x

Computer Organization Computer Architectures Lab

Digital Logic Circuits 14 Map Simplification

MAP SIMPLIFICATION
wx
uv 00 01 11 10 w
00 1 1 0 1 1 1 0 1
01 0 0 0 0 0 0 0 0
v
11 0 1 1 0 0 1 1 0
10 0 1 0 0 u
0 1 0 0
x
F(u,v,w,x) =  (0,1,2,9,13,15)
(0,1), (0,2), (0,4), (0,8) Merge (0,1) and (0,2)
Adjacent Cells of 1 --> u’v’w’ + u’v’x’
Adjacent Cells of 0 Merge (1,9)
(1,0), (1,3), (1,5), (1,9) --> v’w’x
... Merge (9,13)
... --> uw’x
Adjacent Cells of 15 Merge (13,15)
(15,7), (15,11), (15,13), (15,14) --> uvx

F = u’v’w’ + u’v’x’ + v’w’x + uw’x + uvx

But (9,13) is covered by (1,9) and (13,15)
F = u’v’w’ + u’v’x’ + v’w’x + uvx

Computer Organization Computer Architectures Lab

Digital Logic Circuits 15 Map Simplification

IMPLEMENTATION OF K-MAPS - Sum-of-Products Form -

Logic function represented by a Karnaugh map

can be implemented in the form of I-AND-OR

A cell or a collection of the adjacent 1-cells can

be realized by an AND gate, with some inversion of the input variables.
y
x’
1 1 y
x’ z’
y’ x’
z’ x 1  y
x z’ 1 1
z y z’
z’ 1
F(x,y,z) =  (0,2,6)

x’
y’ x
z’
x’  z
y F F
z’ y
x
y z
z’
I AND OR

Computer Organization Computer Architectures Lab

Digital Logic Circuits 16

 Implicant: An implicant is any product term

(AND combination) of input variables in a Boolean
function that covers one or more 1s (minterms) in the
truth table.

 Prime Implicant: A prime implicant is an implicant

that cannot be combined (or expanded) further
with another implicant to eliminate more literals
without covering any 0s.

 Essential Prime Implicant: An essential prime

implicant is a prime implicant that covers at
least one minterm that is not covered by any
other prime implicant.

Computer Organization Computer Architectures Lab

Digital Logic Circuits 17

Criteria to Determine
Minimum Cost Using K-map
Cost Function

Cost = Number of terms + Total number of literals

Example:
AB + C → 2 terms, 3 literals → Cost = 5
A + B + C → 3 terms, 3 literals → Cost = 6

Computer Organization Computer Architectures Lab

Digital Logic Circuits 18

Grouping Rules
 Form largest possible groups of 1s (or 0s in POS form)
 Group size must be powers of 2: 1, 2, 4, 8, 16...
 Larger groups → fewer literals → simpler expression

Expression Minimization

 Identify all prime implicants from the K-map

 Select essential prime implicants first (must be
included)
 Use additional prime implicants only if needed to
cover all minterms
 Goal → cover all 1s with minimum terms

Computer Organization Computer Architectures Lab

Digital Logic Circuits 19

Questions
Find the Prime Implicants and Essential Prime Implicants
from the following:

F(A,B,C,D) = Σ(0, 4, 5 ,7, 8, 9, 13,

15)
F(A,B,C,D) = Σ(3, 4, 5, 7, 9, 13,
14, 15)
F(A,B,C,D) = Σ(0, 2, 3, 4, 8, 9, 10,
14)
F(A,B,C,D) = Σ(0, 4, 5, 8,
Computer Organization 10,
Computer 11, Lab
Architectures
Digital Logic Circuits 20

Example- BCD to Excess-3

Code Converter
 BCD (Binary Coded Decimal): 4-bit code for decimal
digits (0000–1001)
 Excess-3 Code: A decimal digit represented in binary,
offset by +3
 Formula: Excess-3 = BCD + 0011 (3)

Computer Organization Computer Architectures Lab

Digital Logic Circuits 21

Conversion Table
Inputs: (a, b, c, d)
Ouptuts: (w, x, y, z)
 0 → 0000 → 0011
 1 → 0001 → 0100
 2 → 0010 → 0101
 3 → 0011 → 0110
 4 → 0100 → 0111
 5 → 0101 → 1000
 6 → 0110 → 1001
 7 → 0111 → 1010
 8 → 1000 → 1011
 9 → 1001 → 1100
 10–15 (1010–1111) → Don’t Care

Computer Organization Computer Architectures Lab

Digital Logic Circuits 22

Outputs with Don’t Care

 W(A,B,C,D) = Σ(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14,
15)
 X(A,B,C,D) = Σ(1, 2, 3, 4, 9) + d(10, 11, 12, 13, 14,
15)
 Y(A,B,C,D) = Σ(0, 3, 4, 7, 8) + d(10, 11, 12, 13, 14,
15)
 Z(A,B,C,D) = Σ(0, 2, 4, 6, 8) + d(10, 11, 12, 13, 14,
15)

Computer Organization Computer Architectures Lab

Digital Logic Circuits 23

Examples of Don’t Care

F(A,B,C,D) = Σ(6, 7, 12, 13, 14, 15) +
d(1, 5, 9)
F(A,B,C,D) = Σ(5, 6, 9, 15) + d(1, 4, 7,
8,13, 14)
F(A,B,C,D) = Σ(5, 6, 9, 15) + d(1, 4, 7,
8, 13, 14)

Computer Organization Computer Architectures Lab

 COMBINATIONAL LOGIC
Digital Logic Circuits 24 Combinational Logic Circuits

CIRCUITS
Half Adder x y c s
y y
x
0 0 0 0 0 0 0 1 c
y
0 1 0 1 x 0 1 x 1 0
1 0 0 1 c = xy s = xy’ + x’y s
1 1 1 0 =x  y

Computer Organization Computer Architectures Lab

Digital Logic Circuits 25

Sequential Circuits
 Sequential circuits are digital circuits whose
outputs depend not only on the current inputs
but also on the past history (state) of inputs.

Computer Organization Computer Architectures Lab

Digital Logic Circuits 26 Flip Flops

FLIP FLOPS
Characteristics
- 2 stable states
- Memory capability
- Operation is specified by a Characteristic Table
1 0 0 1

0 1 1 0
0-state 1-state
In order to be used in the computer circuits, state of the flip flop should
have input terminals and output terminals so that it can be set to a certain
state, and its state can be read externally.

R S R Q(t+1)
Q 0 0 Q(t)
0 1 0
1 0 1
S Q’ 1 1 indeterminate
(forbidden)

Computer Organization Computer Architectures Lab

Digital Logic Circuits 27

Characteristic Table for T Flip

Flop
 T | Q(t) | Q(t+1)
 0| 0 | 0
 0| 1 | 1
 1| 0 | 1
 1| 1 | 0

Computer Organization Computer Architectures Lab

Digital Logic Circuits 28 Memory Components

INTEGRATED CIRCUITS
Classification by the Circuit Density
SSI - several (less than 10) independent gates
MSI - 10 to 200 gates; Perform elementary digital functions;
Decoder, adder, register, parity checker, etc
LSI - 200 to few thousand gates; Digital subsystem
Processor, memory, etc
VLSI - Thousands of gates; Digital system
Microprocessor, memory module

Computer Organization Computer Architectures Lab