DIGITAL LOGIC CIRCUITS

Name : R.Shanthi prabha, M.Sc., M.Phil.,

Designation : Assistant Professor
Department : Computer Science
College : Sri Adi Chunchanagiri
Women’s College, Cumbum
 Introduction

DIGITAL LOGIC CIRCUITS

Logic Gates

Boolean Algebra

Map Specification

Combinational Circuits

Flip-Flops

Sequential Circuits

Memory Components

Integrated Circuits
 Logic Gates

LOGIC GATES

Digital Computers

- Imply that the computer deals with digital information, i.e., it deals
with the information that is represented by binary digits
- Why BINARY ? instead of Decimal or other number system ?

* Consider electronic signal

1 7
6
5 signal
4
3 range
2
0 1
0
binary octal

0 1 2 3 4 5 6 7 8 9
* Consider the calculation cost - Add 0 0 1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9 10
0 1 2 2 3 4 5 6 7 8 9 1011
3 3 4 5 6 7 8 9 101112
0 0 1 4 4 5 6 7 8 9 10111213
1 1 10 5
6
5 6 7 8 9 1011121314
6 7 8 9 101112131415
7 7 8 9 10111213141516
8 8 9 1011121314151617
9 9 101112131415161718
 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
 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
 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
 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
 Boolean Algebra

BASIC IDENTITIES OF BOOLEAN ALGEBRA

[1] x + 0 = x [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
 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

C
 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'

 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
 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)
 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)
MAP SIMPLIFICATION - 2 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
MAP SIMPLIFICATION - MORE 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
 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
 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
 Map Simplification

IMPLEMENTATION OF K-MAPS - Product-of-Sums Form -

Logic function represented by a Karnaugh map

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

If we implement a Karnaugh map using 0-cells,

the complement of F, i.e., F’, can be obtained.
Thus, by complementing F’ using DeMorgan’s
theorem F can be obtained

F(x,y,z) = (0,2,6) y
F’ = xy’ + z
1 0 0 1 z
x 0 0 0 1 F = (xy’)z’
= (x’ + y)z’
x z
y’

x
y
F
z

I OR AND
 Map Simplification
IMPLEMENTATION OF K-MAPS
- Don’t-Care Conditions -
In some logic circuits, the output responses
for some input conditions are don’t care
whether they are 1 or 0.

In K-maps, don’t-care conditions are represented

by d’s in the corresponding cells.

Don’t-care conditions are useful in minimizing

the logic functions using K-map.
- Can be considered either 1 or 0
- Thus increases the chances of merging cells into the larger cells
--> Reduce the number of variables in the product terms
y x’
1 d d 1
x d 1
z yz’

x
F
y
z
 Combinational Logic Circuits

COMBINATIONAL LOGIC CIRCUITS

y y
Half Adder x y c s 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
Full Adder
y y
x y cn-1 cn s
0 0 0 0 0 0 0 0 1
0 0 1 0 1 0 1 c 1 0 cn-1
n-1
0 1 0 0 1 x 1 1 x 0 1
0 1 1 1 0 0 1 1 0
1 0 0 0 1 cn s
1 0 1 1 0
1 1 0 1 0 cn = xy + xcn-1+ ycn-1
1 1 1 1 1 = xy + (x  y)cn-1
s = x’y’cn-1+x’yc’n-1+xy’c’n-1+xycn-1
x = x  y  cn-1 = (x  y)  cn-1
y S
cn-1
cn
 Combinational Logic Circuits

COMBINATIONAL LOGIC CIRCUITS

Other Combinational Circuits

Multiplexer
Encoder
Decoder
Parity Checker
Parity Generator
etc
 Combinational Logic Circuits

MULTIPLEXER

4-to-1 Multiplexer
Select Output
S1 S 0 Y
0 0 I0
0 1 I1
1 0 I2
1 1 I3

I0

I1
Y
I2

I3

S0
S1
 Combinational Logic Circuits

ENCODER/DECODER

Octal-to-Binary Encoder
D1 A0
D2
D3 A1
D4
D5 A2
D6
D7

2-to-4 Decoder
D0

E A1 A0 D0 D1 D2 D3 A0 D1
0 0 0 0 1 1 1
0 0 1 1 0 1 1 D2
0 1 0 1 1 0 1
0 1 1 1 1 1 0
1 d d 1 1 1 1 A1 D3
E
 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)
 Flip Flops

CLOCKED FLIP FLOPS

In a large digital system with many flip flops, operations of individual flip flops
are required to be synchronized to a clock pulse. Otherwise,
the operations of the system may be unpredictable.
R
Q

c
(clock)
S Q’

Clock pulse allows the flip flop to change state only

when there is a clock pulse appearing at the c terminal.

We call above flip flop a Clocked RS Latch, and symbolically as

S Q S Q
c c
R Q’ R Q’
operates when operates when
clock is high clock is low
 Flip Flops

RS-LATCH WITH PRESET AND CLEAR INPUTS

P(preset)
R Q
c
(clock)
S Q’

clr(clear)

S P Q S P Q
c c
R clr Q’ R clr Q’

S P Q S P Q
c c
R clr Q’ R clr Q’
 Flip Flops

D-LATCH

D-Latch
Forbidden input values are forced not to occur
by using an inverter between the inputs

D Q
Q

E
(enable) E Q’

Q’ D Q
D(data)

D Q(t+1) E Q’
0 0
1 1
 Flip Flops

EDGE-TRIGGERED FLIP FLOPS

Characteristics
- State transition occurs at the rising edge or
falling edge of the clock pulse

Latches

respond to the input only during these periods

Edge-triggered Flip Flops (positive)

respond to the input only at this time

 Flip Flops

POSITIVE EDGE-TRIGGERED

D-Flip Flop
D S1 Q1 S2 Q2 Q D Q
SR1 SR2
C1 C2 D-FF
R1 Q1' R2 Q2' Q' C Q'
C

SR1 inactive
SR2 active
SR2 inactive SR2 inactive
SR1 active SR1 active
JK-Flip Flop

J S1 Q1 S2 Q2 Q J Q
SR1 SR2
C1 C2 C
K R1 Q1' R2 Q2' Q' K Q'
C

T-Flip Flop: JK-Flip Flop whose J and K inputs are tied together to make
T input. Toggles whenever there is a pulse on T input.
 Flip Flops

CLOCK PERIOD

Clock period determines how fast the digital circuit operates.

How can we determine the clock period ?

Usually, digital circuits are sequential circuits which has some flip flops

FF FF ... FF
C
Combinational .
.
. Logic .
. Circuit .

Combinational
FF Logic FF
Circuit
FF Setup Time
FF Delay Combinational logic Delay FF Hold Time
td
ts,th
clock period T = td + ts + th
 Sequential Circuits

DESIGN EXAMPLE
Design Procedure:
Specification  State Diagram  State Table 
Excitation Table  Karnaugh Map  Circuit Diagram
Example: 2-bit Counter -> 2 FF's
x=0 current next
state input state FF inputs
00 A B x A B Ja Ka Jb Kb
x=1 x=1 0 0 0 0 0 0 d 0 d
0 0 1 0 1 0 d 1 d
x=0 01 11 x=0 0 1 0 0 1 0 d d 0
0 1 1 1 0 1 d d 1
x=1 1 0 0 1 0 d 0 0 d
x=1 1 0 1 1 1 d 0 1 d
10 1 1 0 1 1 d 0 d 0
x=0 1 1 1 0 0 d 1 d 1

B B B B
d d d d
1 x d d x 1 d x d 1 x
d d 1 1 d x A B
A A A d 1 J Q J Q
A
d d d d C C
Ja Ka Jb Kb K Q' K Q'
clock
Ja = Bx Ka = Bx Jb = x Kb = x
 Sequential Circuits

SEQUENTIAL CIRCUITS - Registers

A0 A1 A2 A3
Q Q Q Q
D C D C D C D C

Clock
I0 I1 I2 I3
Shift Registers
Serial Serial
D Q D Q D Q D Q Output
Input C C C C
Clock

Bidirectional Shift Register with Parallel Load

A0 A1 A2 A3

Q Q Q Q
D C D C D C D C

4x1 4x1 4x1 4x1

MUX MUX MUX MUX

Clock S0S1 SeriaI I0 I1 I2 Serial I

3
Input Input
 Sequential Circuits

SEQUENTIUAL CIRCUITS - Counters

A0 A1 A2 A3

Q Q Q Q
J K J K J K J K
Clock

Counter
Enable

Output
Carry
 Memory Components

MEMORY COMPONENTS
0
Logical Organization

words
(byte, or n bytes)

N-1
Random Access Memory

- Each word has a unique address

- Access to a word requires the same time
independent of the location of the word
- Organization
n data input lines

k address lines
2k Words
Read (n bits/word)

Write

n data output lines

 Memory Components

READ ONLY MEMORY(ROM)

Characteristics
- Perform read operation only, write operation is not possible
- Information stored in a ROM is made permanent
during production, and cannot be changed
- Organization k address input lines

m x n ROM
(m=2k)

n data output lines

Information on the data output line depends only
on the information on the address input lines.
--> Combinational Logic Circuit address Output
X0=A’B’ + B’C ABC X 0 X1 X 2 X 3 X 4
X1=A’B’C + A’BC’ 000 1 0 0 0 0
X2=BC + AB’C’ 001 1 1 0 0 0
X3=A’BC’ + AB’ 010 0 1 0 1 0
X4=AB 011 0 0 1 0 0
100 0 0 1 1 0
X0=A’B’C’ + A’B’C + AB’C 101 1 0 0 1 0
X1=A’B’C + A’BC’ 110 0 0 0 0 1
Canonical minterms X2=A’BC + AB’C’ + ABC 111 0 0 1 0 1
X3=A’BC’ + AB’C’ + AB’C
X4=ABC’ + ABC
 Memory Components

TYPES OF ROM

ROM
- Store information (function) during production
- Mask is used in the production process
- Unalterable
- Low cost for large quantity production --> used in the final products

PROM (Programmable ROM)

- Store info electrically using PROM programmer at the user’s site
- Unalterable
- Higher cost than ROM -> used in the system development phase
-> Can be used in small quantity system

EPROM (Erasable PROM)

- Store info electrically using PROM programmer at the user’s site
- Stored info is erasable (alterable) using UV light (electrically in
some devices) and rewriteable
- Higher cost than PROM but reusable --> used in the system
development phase. Not used in the system production
due to eras ability
 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
Classification by Technology
TTL - Transistor-Transistor Logic
Bipolar transistors
NAND
ECL - Emitter-coupled Logic
Bipolar transistor
NOR
MOS - Metal-Oxide Semiconductor
Unipolar transistor
High density
CMOS - Complementary MOS
Low power consumption