CHAPTER ONE

1 DIGITAL LOGIC AND DIGITAL SYSTEMS

The computer lies at the heart of computing. Without it most of the computing disciplines today
would be a branch of theoretical mathematics. To be a professional in any field of computing
today, one should acquire some understanding and appreciation of a computer system’s
functional components, their characteristics, their performance, and their interactions. We need
to understand computer architecture in order to structure a program so that it runs more
efficiently on a real machine. In selecting a system to use, they should be able to understand
the tradeoff among various components, such as CPU clock speed vs. memory size.

Suppose a graduate enters the industry and is asked the most cost-effective computer for use
throughout a large organization. An understating of the implications of spending more for
various alternatives, such as larger cache or a higher processor clock rate, is essential to making
the decision.

Digital computers use the binary number system, which has two digits; 0 and 1. Because of the
physical restriction of components., Inside the computer, there are integrated circuits with
thousands of transistors. These transistors are made to operate on two-state. By this design, all
the input and output voltages are either HIGH or LOW. Low voltage represents binary 0 and
high voltage represents binary 1.

A binary digit is called a bit. Information is represented in digital computers in groups of bits.
By using various coding techniques, groups of bits can be made to represent not only binary
numbers but also other discrete symbols, such as decimal digits or letters of the alphabet and
to develop complete sets of instructions for performing various types of computations.

A computer system is subdivided into two functional entities: Hardware and Software. The
hardware of the computer consists of all the electronic components and electromechanical
devices that comprise the physical entity of the device. Computer software consists of the
instructions and data that the computer manipulates to perform various data-processing tasks.
A sequence of instructions for the computer is called a Program.

The hardware of the computer is usually divided into three major parts.

The central processing unit (CPU) contains an arithmetic and logic unit for manipulating
data, a number of registers for storing data, and control circuits for fetching and executing
instructions. The memory of a computer contains storage for instructions and data. It is called
a Random-Access Memory (RAM) because the CPU can access any location in memory at
random and retrieve the binary information within a fixed interval of time. Input and output
processor (IOP) contain electronic circuits for communicating and controlling the transfer of
information between the computer and the outside world. The input and output devices
connected to the computer include keyboards, printers, terminals, and other communication
devices.

1
Computer Architecture

Those attributes of the system that is visible to a programmer. It is concerned with the structure
and behavior of the computer as seen by the user. Those attributes that have a direct impact on
the execution of a program.

• Instruction sets
• Data representation – number of bits used to represent data
• Input/output mechanisms
• Memory addressing techniques

Computer Organization

The operational units and their interconnections that realize the architectural specifications. It
is concerned with the way the hardware components operate and the way they are connected
together to form the computer system. Those hardware attributes that are transparent to the
programmer.

• Control signals
• Interfaces between the computer and peripherals
• Memory technology

Computer Design

It is concerned with hardware design of the computer. Once the computer specifications are
formulated, it is the task of the designer to develop hardware for the system. This is sometimes
referred to as computer implementation.

Computer Structure and Function

A computer is a complex system; contemporary computers contain millions of electronic

components. A hierarchical system is a set of interrelated subsystems where each subsystem is
a hierarchical structure. At each level, the system consists of a set of components and their
interrelationships. At each level, a designer is concerned with structure and function:

Function: The four basic functions of a computer are:

• Process data
• Store data
• Move data between the computer and the outside world
• Control the above functions

Structure: The way in which components relate to each other. The four main internal
structural components of a computer are:

• Central processing unit (CPU) – controls the operation of the computer and performs
its data processing functions. It is probably the most interesting and, in some ways, the

2
 most complex component of the computer. The CPUs major structural components are
as follows:
o Control unit – controls the operation of the CPU and hence the computer.
o Arithmetic and logic unit (ALU) – performs the computer’s data processing
functions.
o Registers – provides storage internal to the CPU.
o CPU interconnections – some mechanism that provides for communication
among the control unit, ALU, and registers.
• Main memory – stores data.
• Input/output (I/O) – moves data between the computer and its external environment.
• System interconnections – some mechanism that provides for communication among
CPU, main memory, and I/O.
1.1 LOGIC GATES

A logic gate is an elementary building block of a digital circuit. It is a circuit with one output
and one or more inputs. At any given moment, logic gate takes one of the two binary conditions
low (0) or high (1), represented by different voltage levels. A voltage level will represent each
of the two logic values. For example, +5V might represent a logic 1 and 0V might represent a
logic 0.

There are three fundamental logic gates namely, AND, OR and NOT. Also, we have other logic
gates like NAND, NOR, XOR and XNOR. Out of these NAND and NOR gates are called the
Universal Gates. The circuit symbol and the truth table of these logic gates are explained here.

AND Gate

The AND Gate has two or more input signals but only one output signal. All the inputs must
be high to get a high output. If we have two inputs to this AND gate and both the inputs are
high then the output will be high otherwise the output will be low. All the possible inputs and
outputs are shown in the following table.
Table 1: Truth table of AND gate
A B Z
0 0 0
0 1 0
1 0 0
1 1 1
Figure 1: Circuit symbol representation of
AND gate

OR Gate

The OR gates has two or more input signals but only one output signal. If any input signal is
high, the output signal is high. If we have two inputs to this OR gate and any of the two inputs
is high then the output will be high. This can be shown in a table below with all the possible
inputs and corresponding outputs.

3
 Table 2: Truth table of OR gate
A B Z
0 0 0
0 1 1
1 0 1
1 1 1
Figure 2: Circuit symbol representation of
OR gate

NOT or Inverter

A Low input produces a high output, and a high input produces low output. In binary format if
the input is 0 the output will be 1 and if the input is 1 then the output will be 0. The table shows
the input and output possibilities.
Table 3: Truth table of NOT gate
A Z
0 1
1 0
Figure 3: Circuit symbol representation of
NOT gate

NAND Gate

NAND Gate is a combination of an AND gate with an inverter. An AND Gate followed by an
inverter (see Figure 5). Whatever the output of the AND gate, it will be inverted by the inverter.
This is the formation of NAND gate. The circuit sign and the table are shown below.
Table 4: Truth table of AND gate
A B Z
0 0 1
0 1 1
1 0 1
1 1 0
Figure 4:Circuit symbol representation of
NAND gate

Figure 5: A NAND gate composed of AND and NOT gate

NOR Gate

4
NOR Gate, one of the universal gate family, is a combination of an OR gate followed by an
inverter. The following table and figure describe the function and the circuit symbol of the gate.
Table 5: Truth table of NOR gate
A B Z
0 0 1
0 1 0
1 0 0
1 1 0

Figure 6:Circuit symbol representation of

NOR gate

Exclusive OR Gate

An OR Gate recognizes with one or more 1s as inputs and gives output as 1. The Exclusive-
OR is different; it recognizes only that have odd number of 1s, it counts the occurrence of 1’s
from the input and produce 1 if the number of 1’s is odd. In other words, it performs the value
mod 2 operation. The following table shows the XOR gate operation for size of two binary
value.
Table 6: Truth table of XOR gate
A B Y
0 0 0
0 1 1
1 0 1
1 1 0
Figure 7: Circuit symbol representation of
XOR gate

The XOR gate can be expressed in terms of NOT, AND and OR gates as shown in the figure
below.

̅B + AB
A B = A ̅

Figure 8: XOR in terms of NOT, AND, OR gates

5
Exclusive NOR Gate or XNOR: Exclusive NOR Gate is abbreviated as XNOR. This is
logically equivalent to and XOR gate followed by an inverter.
1.2 BOOLEAN ALGEBRA

Boolean Algebra is mathematical system for formulating logical statements with symbols so
that problems can be solved in a manner to ordinary algebra. A basic knowledge in the Boolean
algebra required to study and analysis of logic circuits. It is a convenient and systematic way
of expressing and analyzing the operations of logic circuits. In boolean algebra, the logic gates
that we have seen in above were expressed by circuit symbols but they can also express as
shown the following table (Table 7: Basic logical operations), the gate and their symbol
together with operands A and B:
Table 7: Basic logical operations
Gate Symbol Pronunciation
AND AB A and B
OR A+B A or B
NOT ̅
A Not A

These logical operators have properties, that can be described by the following equality
equations:
• A+0=A • A. A ̅=0
• A+1=1 • A.A = A
• A0 = 0 • A ̅=A
• A1 = A • A + AB = A
• A+A ̅=1 • A. A ̅B = A + B
• A+A = A • (A + B) (A + C) = A + BC
Table 8: Other identities

AB = BA A+B=B+A Commutative Law

A +(BC) = (A+B). (A+C) A(B+C) = AB + AC Distributive law

A(BC) = (AB)C A+(B+C) = (A+B) + C Associative Law

̅̅̅̅ ̅+𝐁
𝐀𝐁 = 𝐀 ̅ ̅̅̅̅̅̅̅̅
𝐀+𝐁 = 𝐀 ̅. 𝐁
̅ De Morgan’s Theorems

NB: You are invited to verify the expressions listed in above by substituting actual values (1s
and 0s) for the variables A, B, and C.
1.3 COMBINATIONAL CIRCUITS

A connected arrangement of logic gates with a set of inputs and outputs is known as
combinatorial circuit. The combinational circuits are those logic circuits whose operations can
be completely described by a truth table or Boolean expression. A combinational circuit can be
realized by using AND, OR, NOT gates (or NAND OR NOR gates).

6
Examples of combinational circuits are: adder, subtractors, code converters, decoders,
encoders, digital multiplexers, demultiplexers, programmable logic arrays, ROMs etc.,

In general terms, a combinational circuit consists of n binary inputs and m binary outputs. As
with a gate, a combinational circuit can be defined in three ways:

• Truth table: For each of the 2n possible combinations of input signals, the binary value
of each of the m output signals is listed.
• Graphical symbols: The interconnected layout of gates is depicted.
• Boolean equations: Each output signal is expressed as a Boolean function of its input
signals.
1.4 SOP vs. POS

Any Boolean function can be implemented in electronic form as a network of gates. For any
given function, there are a number of alternative realizations.

Consider the Boolean function that represented by the truth table in Table 9.
Table 9: A Boolean function of three variables
A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

We can express this function by simply itemizing the combinations of values of A, B, and C
that cause F to be 1:

𝐹 = 𝐴̅𝐵 𝐶̅ + 𝐴̅𝐵𝐶 + 𝐴𝐵𝐶̅

There are three combinations of input values that cause F to be 1, and if any one of these
combinations occurs, the result is 1. This form of expression, for self-evident reasons, is known
as the sum of products (SOP) form.

In alternative to the SOP form logical expressions can also be derived from the truth table
known as the product of sum (POS). Unlike, SOP form expresses that the output is 1 if any of
the input combinations that produce 1 is true. In POS the output is 1 if none of the input
combinations that produce 0 is true. Thus,

̅̅̅̅̅̅
𝐹 = (𝐴 ̅̅̅̅̅̅
̅𝐵̅ 𝐶̅ ) ∙ (𝐴 ̅̅̅̅̅̅
̅𝐵̅ 𝐶 ) ∙ (𝐴𝐵 ̅̅̅̅̅̅
̅ 𝐶̅ ) ∙ (𝐴𝐵 ̅ 𝐶 ) ∙ (𝐴𝐵𝐶
̅̅̅̅̅̅ )

NB: please draw the digital circuit of the above equations.

7
 1.5 KARNAUGH MAP (K-MAP)

The Karnaugh map (k-map) method is a graphical technique for simplifying Boolean functions.
It is a two-dimensional of a Truth Table. It provides a simpler method for minimizing logic
expressions. The map method is ideally suited for four or less variables. A Karnaugh map for
n variables is made up of 2n squares. Each square designates a product term of a Boolean
expression. For product terms which are present in the expression, 1s are written in the
corresponding squares; 0s are written in those squares which correspond to product terms not
present in the expression, take a look at the following figure.

Figure 9:The Use of Karnaugh Maps to Represent Boolean

Once the map of a function is created, we can often write a simple algebraic expression for it
by noting the arrangement of the 1s on the map. The principle is as follows. Any two squares
that are adjacent differ in only one of the variables. If two adjacent squares both have an entry
of one, then the corresponding product terms differ in only one variable. In such a case, the two
terms can be merged by eliminating that variable. For example, in Figure 10a, the two adjacent
squares correspond to the two terms 𝐴̅𝐵𝐶̅ 𝐷and 𝐴̅𝐵𝐶𝐷. Thus, the function expressed is

𝐴̅𝐵𝐶̅ 𝐷 + 𝐴̅𝐵𝐶𝐷 = 𝐴̅𝐵𝐷

8
 Figure 10:The Use of Karnaugh Maps

This process can be extended in several ways. First, the concept of adjacency can be extended to
include wrapping around the edge of the map. Thus, the top square of a column is adjacent to the
bottom square, and the leftmost square of a row is adjacent to the rightmost square. These
conditions are illustrated in Figure 10 b and c. Second, we can group not just 2 squares but 2n
adjacent squares (that is, 2, 4, 8, etc.). The next three examples in Figure 10 show groupings of 4
squares. Note that in this case, two of the variables can be eliminated. The last three examples
show groupings of 8 squares, which allow three variables to be eliminated.

Exercise: Draw a circuit that can add two 3-binary digits (use Full adder circuit).
9
 1.6 SEQUENTIAL CIRCUITS

Recall that a ROM is a memory unit that performs only the read operation. This implies that the
binary information stored in a ROM is permanent and was created during the fabrication process.
Thus, a given input to the ROM (address lines) always produces the same output (data lines).
Because the outputs are a function only of the present inputs, the ROM is in fact a combinational
circuit.

In the earlier part of this chapter we explored combinational logic units (CLU), in which the
outputs are completely determined by functions of the inputs. A sequential logic unit (SLU), a.k.a.
finite state machine (FSM), takes an input and a current state and produces an output and a new
state. SLU is distinguished from a CLU in that the past history of the inputs to the SLU influences
its state and output. This is important for implementing memory circuits as well as control units in
a computer.

The classical model of a finite state machine is shown in Figure 11. A CLU takes inputs from lines
i0 – ik which are external to the FSM, and also takes inputs from state bits s0 – sn which are internal
to the FSM. The CLU produces output bits f0 – fm and new state bits. Delay elements maintain the
current state of the FSM, until a synchronization signal causes the Di values to be loaded into the
si, which appear at Qi as the new state bits.

Figure 11: Classical model of a finite state machine

10
1.6.1 Flip-Flops

The simplest form of sequential circuit is the flip-flop. A flip-flop can be used to store a single bit
of information, and serves as a building block for computer memory. There are a variety of
flipflops, all of which share two properties:

• The flip-flop is a bistable device. It exists in one of two states and, in the absence of input,
remains in that state. Thus, the flip-flop can function as a 1-bit memory.
• The flip-flop has two outputs, which are always the complements of each other. These are
generally labeled Q and Q ̅.

The flip-flop maintains a binary state until directed by a clock pulse to switch states. The difference
among various types of flip-flops is in the number of inputs they possess and in the manner in
which the inputs affect the binary state. The most common types of flip-flops are presented below:

SR Flip-Flop

The SR flip-flop has three inputs, labeled S (for set), R (for reset), and C, EN or Ck (for clock). It
has an output Q and a complemented output. There is an arrowhead-shaped symbol in front of in
the input of clock to designate a dynamic input. The symbol used to represent SR flip-flop is shown
in Figure 12.

The operation of the SR flip-flop is as follows. If there is no signal at the clock input Ck, the output
of the circuit cannot change irrespective of the values at inputs S and R. Only when the clock signal
changes from 0 to 1 can the output be affected according to the values in inputs S and R.

The truth table is also shown in the third column of Figure 12. The S and R columns give the binary
values of the two inputs. Qn+1 is the binary state of the Q output after the occurrence of a clock
transition (referred to as next state). If S =1 and R = 0 when Ck changes from 0 to 1 the output is
set to 1. If S = 0 and R = 1, the output Q is cleared to 0. If both S and R are 0 during the clock
transition, the output does not change. When both S and R equal to 1, the output is unpredictable
and may go either 0 or 1, depending on the internal timing delays that occur within the circuit.
This property makes the SR flip-flop difficult to manage and therefore it is seldom used in practice.

D Flip-Flop

The D (data) flip-flop is a slight modification of the SR flip-flop. If D =1, the output of the flip-
flop goes to the 1 state, but if D = 0, the output of the flip-flop goes to the 0 state. Note that no
input condition is exist that will leave the state of the D flip-flop unchanged. The “no change”
condition can be accomplished either by disabling the clock signal or by feeding the output back
into the input. The symbol and the truth table of the D flip-flop is shown in Figure 12.

11
 Figure 12: Basic Flip-Flops

JK Flip-Flop

A JK flip-flop is a refinement of the SR flip-flop in that the indeterminate condition of the SR type
is deafened in the JK type. When inputs J and K are both equal to 1, a clock transition switches the
outputs of the flip-flop to their complement state.

T Flip-Flop

Another common flip-flop is the T (toggle) flip-flop. This flip-flop is obtained from a JK type
when inputs J and K are connected to provide a single input designated by T. It has only two
conditions. When T = 0 a clock transition does not change the state of the flip-flop. When T =1 a
clock transition complements the state of the flip-flop.
12
Excitation Tables

The characteristic tables of flip-flops specify the next state when the inputs and the present state
are known. During the design of sequential circuits, we usually know the required transition from
present state to the next state and which to find the flip-flop input conditions that will cause the
required transition. For this reason, we need a table that lists the required input combinations for a
given change of state. Such a table is called a flip-flop excitation table.

The following figure (Figure 13) shows the excitation tables for the four types of flip-flops. Each
table consists of two columns, Q(t) and Q(t+1), and a column for each input to show how the
required transition is achieved. There are four possible transitions from present state Q(t) to next
state Q(t+1). The required input conditions for each of these transitions are derived from the
information available in the truth tables. The symbol  in the tables represents a don’t-care
condition; that is, it does not matter whether the input to the flip-flop is 0 or 1.

Figure 13: Excitation Table for Four Flip-Flops

Exercise: Construct a 4-bit binary counter using flip-flop (use T flip-flop).

13