Topic X – Topic Title Module Title

Module Title: Computer Systems

Topic: 9
Topic Title: Digital Logic

© NCC Education Limited

Digital Logic Topic 9 - 9.2

Scope and Coverage

This topic will cover:
 Executing instructions (fetch, decode execute)
 Logic gates
 From logic equations to logic circuits (some
examples)
 Realising digital circuits (some examples)
 Logic design and simulation tools

Digital Logic Topic 9 - 9.3

Learning Outcomes
By the end of this topic students will be able to:
• Understand and work with truth-tables and the
associated digital logic gates and circuits.
• Be able to develop logic equations from truth tables
• Be able to synthesise simple logic circuits from logic
equations
• Describe the basic steps in logic circuit design and
realisation
• Describe logic circuit design tools

V0.0 Visuals Handout – Page 1

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.4

Computer systems - roadmap

Computer hardware components are
covered in earlier topic as black-boxes. To
Advanced topics better understand these require
Computer networks understanding of digital logic circuits.
Embedded systems
Digital logic
It is the digital logic circuits that include
Computer systems software logic as gates with binary inputs and
Computer programs outputs that decide how hardware
Numbers and logic components should behave.
Operating systems 2
In this topic, therefore, we look at how the
Computer systems hardware
Computer systems
logical functions of simple circuits are
decided using truth tables and logic
equations from which circuits are realised.

Digital Logic Topic 9 - 9.5

Digital logic introduction

Digital logic is used to realise digital processors. What are
digital processors? Any hardware or software that can accept
input information as digital data, manipulate it digitally and
produce digital data as output.

So, digital logic is the main building-blocks of the digital

devices; just like the Lego bricks. Simple digital-logic
components are interconnected to construct complex devices
such as microprocessors.

This topic is about the very basics of digital logic that form the
backbone of computer architecture. Therefore, appreciation of
this subject is essential for understanding computer systems.

Digital Logic Topic 9 - 9.6

CPU operation
Consider a central processing unit (CPU) as a fundamental
digital data processor. What are its main functions? A
reminder: think of the main three CPU cycles!!!

• Fetch instruction from RAM

• Decode instruction
• Execute instruction
So, if we wish to construct a very basic CPU, all we need to do
is to use digital logic's basic building-blocks to realise all three
above functions! But how?

V0.0 Visuals Handout – Page 2

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.7

CPU operation
Here is a quick reminder

CPU

Decoder Parity RAM

checker
instruction
op code operands

EU
e.g. Adder
result

Digital Logic Topic 9 - 9.8

Digital logic
Let us build a (very) simple CPU!
What do we need? A means of fetching data from RAM and
checking it for any corruption; a decoder which separates the
instruction into operation and its operands; a means of
executing the decoded instruction… Simple!!!
We are going to carry out a small sub-set of the above tasks.
This is just to demonstrate digital logic and how it is used in its
most basic ways. So, what are we doing?
• A parity checker to validate data from RAM
• A decoder to identify operation and operands
• An adder to do the arithmetic operations

Digital Logic Topic 9 - 9.9

Digital logic
Digital logic building-blocks
Digital logic building-blocks are represented as black-boxes,
i.e. internal details are hidden, only external characteristics
are known. These include inputs, outputs and input-to-output
transformation functions.

Digital
Inputs (one or more) logic Outputs (one or more)
0s and 1s building 0s and 1s
block

Transformation functions are represented by the logic truth-

tables that define input/output relationships.

V0.0 Visuals Handout – Page 3

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.10

Truth-table of parity checker

Let us build a simple CPU! – the Parity Checker
What does a parity checker do? Where can it be used?
Inputs Output
A 2-input even
parity A B P
checker/ P 0 0 1
B generator 0 1 1
1 0 1
1 1 0
For this example, let’s assume 0 is odd! Truth table
Logic formula: A . B + A . B + A . B = P

Digital Logic Topic 9 - 9.11

Parity checker/generator example

The sender of data generates the parity bit. The data and
parity bit are sent to the receiver which in turn works out
the parity bit. Both data and parity bits must agree.
A B P1 A B P2
A Sender 2-input 1 1 0 1 1 0 P2=P1
even parity P1
B generator 1 0 0 1 0 1 P2≠P1

Receiver
A 3-input even P2
B parity checker

Digital Logic Topic 9 - 9.12

Truth-table of a decoder
Let us build a simple CPU! – the Decoder
What does a decoder do? Where can it be used?
Truth table
A B D0 D1 D2 D3
D0
A 2-line to 0 0 1 0 0 0
D1
4-line 0 1 0 1 0 0
decoder D2
B 1 0 0 0 1 0
D3
1 1 0 0 0 1

Logic formula: A . B = D0; A . B = D1; A . B = D2 ; A.B = D3

V0.0 Visuals Handout – Page 4

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.13

Decoder equivalent in VB
The decoder behaves like the case/switch/match statements
of high-level languages such as VB, C and Python. For
example, using VB ‘select case’ statement:
Select case AB
Case 0
D0=1, D1=0, D2=0, D3=0
Case 1
D0=0, D1=1, D2=0, D3=0
Case 2
D0=0, D1=0, D2=1, D3=0
Case 3
D0=0, D1=0, D2=0, D3=1
End select

Digital Logic Topic 9 - 9.14

Decoder example
Here is an example. A simple calculator with only four basic
maths operations add (ADD), subtract (SUB), divide (DIV) and
multiply (MUL). The decoder selects which maths operation
is executed by enabling corresponding maths logic.
CPU Instruction
2-bit OpCode Operands
(AB)

0 ADD
logic SUB
2-line to 1 logic DIV
4-line 2 logic MUL
decoder 3 logic

Digital Logic Topic 9 - 9.15

Truth table of a half-adder

Let us build a simple CPU! – the Adder
What does an adder do? Where can it be used?

Truth table
A S A B S C
Half-adder 0 0 0 0
B 0 1 1 0
C 1 0 1 0
1 1 0 1

Logic formula: A . B + A . B = S ; A . B = C

V0.0 Visuals Handout – Page 5

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.16

Basic logic gates

Digital logic is implemented as simple hardware logic gates.
Below are the gate symbols and their corresponding truth-tables.
A B R
A 0 0 0
R AND-gate 0 1 0
B R=A.B 1 0 0
1 1 1

A B R
A OR-gate 0 0 0
R R=A+B 0 1 1
B
1 0 1
A R 1 1 1
NOT-gate 0 1
A R 1 0
R=A

Digital Logic Topic 9 - 9.17

Digital logic realisation

Realisation of digital-logic
Digital logic circuits of arbitrary complexity can be realised
from one or more (usually many more) interconnected basic
AND-gates, OR-gates and NOT-gates. How do we do this?

• Define the truth-table – need to know inputs/outputs

• Write down the logic formula from the truth-table
• Derive the logic circuit from the logic formula
The logic designers use logic building-blocks of much more
complexity (as large-scale integrated circuits) which they can
purchase off-the-shelf; they don't have to re-invent every time.

Digital Logic Topic 9 - 9.18

Parity checker/generator
Logic realisation of parity checker/generator
Below is a realisation of a 2-input parity checker logic. In a more practical
and useful version, there will be more than 2 inputs. This will increase the
complexity of the circuit.
(even parity)

A B P
0 0 1
0 1 1
1 0 1
1 1 0
Truth table

Logic formula: A . B + A . B + A . B = P

V0.0 Visuals Handout – Page 6

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.19

Logic simplification
The logic equation of parity checker logic circuit is:
Logic formula: A . B + A . B + A . B = P

This equation is not optimal and can be simplified by

converting it to:

A (B + B) + A . B = P
but B + B = 1
therefore, the simplified equation is
A + A.B= P

Digital Logic Topic 9 - 9.20

Logic simplification
The simplified logic equation can be realised as the circuit
below, which is different than the one before:
• This circuit uses four gates
and less wiring as opposed
to six gates and more wiring
using the unoptimized logic
equation, a saving of over
60%!
• In a more complex circuit,
optimised logic will provide
much more significant
savings in cost and chip size.

Digital Logic Topic 9 - 9.21

Decoder
Logic realisation of decoder
Below is a realisation of a 2-input to 4-output decoder logic. In a more
practical and useful version, there will be more than 2 inputs and more than
4 outputs. This will increase the complexity of the circuit.

A B D0 D1 D2 D3

0 0 1 0 0 0

0 1 0 1 0 0

1 0 0 0 1 0

1 1 0 0 0 1

Logic formula: A . B = D0; A . B = D1; A . B = D2 ; A.B = D3

V0.0 Visuals Handout – Page 7

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.22

Half-adder
Logic realisation of half-adder
Below is a realisation of a 2-input adder logic. The outputs are the sum (S)
and the carry (C). In a more practical and useful version, there will be more
than 2 inputs. This will increase the complexity of the circuit. A full adder
can be constructed from several interconnected half-adders.

Truth table
A B S C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Logic formula: A . B + A . B = S ; A . B = C

Digital Logic Topic 9 - 9.23

Logic design tools

Logic realisation – design tools
Logic designers often use software tools to capture logic circuits and
verify their designs by simulation methods. This is done by providing
inputs to the logic and checking the output(s) against truth-tables.

One such easy-to-use software tool is “Digital Works” written by

David John Barker from University of Teesside in UK. A free version
is/was available for non-commercial use. This tool allows logic
capture and simulation. We’ll use this tool during the tutorial session.

There are many, much sophisticated and powerful, software and

hardware tools for the logic designers of large-scale integrated
circuits (ICs). These tools are often very expensive and are mainly
used by large electronics companies and research centres.

Digital Logic Topic 9 - 9.24

Hardware design languages

In the same way that high-level programming languages
are used to design and code software, hardware design
languages (HDLs) are used to design and code digital
hardware.
Two leading HDLs are:
• Verilog – developed in 1984, became IEEE
standard in 1995
• VHDL – developed in 1981, became IEEE
standard in 1987

V0.0 Visuals Handout – Page 8

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.25

Hardware design languages

The process of logic circuit design, testing and
synthesising follows three steps:
• HDL definition (capturing the circuit)
o Capture of logic gates and interconnections (wires)
o Definition of how logic behaves (e.g. timings, delays)
• Simulation (debugging the circuit)
o Input values are applied to the circuit
o Outputs and timings are verified for correctness
• Synthesis (realising the circuit)
o Transforms HDL code into a list of gates and wires from
which chips and printed circuits can be manufactured.

Digital Logic Topic 9 - 9.26

HDL example
Here is the HDL definition of half-adder using Verilog:
module half-adder(A, B, S, C) module and(a, b, y) module or(a, b, y)
input a, b; input a, b;
input A, B; output y; output y;
output S, C;
assign y = a & b assign y = a | b
not (A, p); endmodule endmodule
and (p, A, x);
not (B, q); module not(a, y)
and (q, B, y); input a;
Uses C like syntax:
or (x, y, S); output y:
and (A, B, C); | is OR operator
assign y = ~a & is AND operator
endmodule endmodule ~ is NOT operator

Digital Logic Topic 9 - 9.27

Did you know?

Carver Mead
During the 1960s, his studies at the California
Institute of Technology led him to research in
physics and technology of electronic devices.
His deep awareness of the limitations of
standard computer circuitry led to his
pioneering solid-state electronics and the
design of large-scale integrated circuits,
complex silicon chips, that have contributed to
today’s advanced semiconductor and computer
Professor Carver Mead technologies. Professor Mead co-authored the
classic text-book ‘Introduction to VLSI Systems’
that laid down the VLSI automation principles.

V0.0 Visuals Handout – Page 9

Topic X – Topic Title Module Title

Digital Logic Topic 9 - 9.28

VLSI
• Very Large Scale Integration (VLSI) is a process used in the
design and fabrication of integrated logic circuits made up of
densely packed transistors in a single chip, e.g. memory and
CPU chips.
• Hardware description languages (HDLs), e.g. Verilog and
VHDL, are used to describe and code the behaviour and
functionality of digital VLSI circuits.
• Simulation and emulation tools test the functionality of VLSI
designs to ensure they will work properly when fabricated,
saving considerable time and cost.

Digital Logic Topic 9 - 9.29

Quiz time!
1. What are the main three functions of a CPU?
2. Explain the purpose of a truth-table
3. What are the most basic logic gates?
4. What is the result of True AND False?
5. Describe how a parity checker/generator works
6. How many output bits a 3-to-8 decoder has?
7. What are the inputs and the outputs of a half-adder?
8. State the advantages of simplifying the logic equations
9. Hardware design language (HDL) is used to .................
10. What tools are used in a VLSI process?

Digital Logic Topic 9 - 9.30

References
 Null, L. and Lobur, J. (2014) The Essentials of
Computer Organization and Architecture. Fourth
edition. Jones and Bartlett Publishers, Inc.
 Englander, I. (2014) The Architecture of Computer
Hardware and Systems Software. 5th Edition. John
Wiley.
 Comer, D. (2017) Essentials of Computer
Architecture. 2nd edition. CRC Press.
 Bindal, A. (2017) Fundamentals of Computer
Architecture and Design. Springer.

V0.0 Visuals Handout – Page 10

Topic X – Topic Title Module Title

Topic 9 – Digital Logic

Any Questions?

V0.0 Visuals Handout – Page 11