B23ADT301 – DIGITAL LOGIC AND COMPUTER ORGANIZATION

B23ADT301 – DIGITAL LOGIC AND COMPUTER ORGANIZATION

References

S.
UNITS BOOKS WEBSITE
NO

1 Unit 1 M. Morris Mano, Michael D.

Ciletti, “Digital Design: With
an Introduction to the Verilog
HDL, VHDL, and System
Verilog”, Sixth Edition, [Link]
Pearson Education, 2018.
2 Unit 2
[Link]
John. F. Wakerly, "Digital
Design Principles and
Practices", Pearson Education,
4 th Edition, 2007.

3 Unit 3 David A. Patterson, John L.

Hennessy, “Computer
Organization and Design, The
Hardware/Software Interface”,
Sixth Edition, Morgan
Kaufmann/Elsevier, 2020. [Link]

4 Unit 4
Carl Hamacher, Zvonko [Link]
Vranesic, Safwat Zaky, Naraig
Manjikian, “Computer
Organization and Embedded
Systems”, Sixth Edition, Tata
McGraw-Hill, 2012.

William Stallings, “Computer

Organization and Architecture
– Designing for Performance”,
Tenth Edition, Pearson
5 Unit 5 [Link]
Education, 2016.3. M. Morris
Mano, “Digital Logic and
Computer Design”, Pearson
Education, 2016.
 B23ADT301 – DIGITAL LOGIC AND COMPUTER ORGANIZATION
LECTURE NOTES

UNIT- I DIGITAL SYSTEMS AND COMBINATIONAL LOGIC

Number Systems – Decimal, Binary, Octal, Hexadecimal, 1‘s and 2‘s complements
- Logic gates - Combinational Circuits – Karnaugh Map - Analysis and Design
Procedures – Binary Adder – Subtractor – Decimal Adder – Magnitude Comparator –
Decoder – Encoder – Multiplexers – Demultiplexers.

1. Number Systems
A digital number system is a positional number system that has some symbols called
digits. It provides a complete set of digits, operators, and rules to perform operations.
In a digital number system, the number of digits used determines the base of the number
system. For example, the binary number system has two digits (0 and 1), hence, the base
of the binary number system is 2.
Digital number systems form the foundation of the modern computing technologies and
digital electronics. They are used to represent, process, and manipulate the information
using a digital system.
In this chapter, we will discuss the fundamental concepts of different types of digital
number systems.
Types of Digital Number Systems
In digital electronics, the following four types of digital number systems are mainly used
−
• Binary Number System
• Decimal Number System
• Octal Number System
• Hexadecimal Number System
Lets discuss each of these number systems in detail.
Binary Number System
Binary number system is the fundamental building block behind the implementation and
working of all digital systems.
Binary number system has two symbols or digits, i.e., 0 and 1. Hence, these two digits are
used to represent information and perform all the digital operations. Each binary digit is
called a bit.
Since there are two digits are used in the binary number system, hence its base is 2.
Therefore, the value of a binary number is calculated as the sum of powers of 2.
Binary digits are used in digital system to represent their ON and OFF states. Where, 0 is
used to represent the OFF state of the digital system and 1 is used to represent the ON
state of the system.
Overall, the binary number system forms the foundation of computation, digital
communication, and digital information storage.
Example
Consider the binary number 1101.011. The integer part of this number is 1101 and the
fractional part of this number is 0.011. The digits 1, 0, 1 and 1 of the integer part have
weights of 20, 21, 22, 23 respectively. Similarly, the digits 0, 1 and 1 of fractional part have
weights of 2-1, 2-2, 2-3 respectively.
Mathematically, we can write it as,

After simplifying the right-hand side terms, we will get a decimal number, which is an
equivalent of binary number on left-hand side.
Decimal Number System
Decimal number system is not inherently a digital number system. But it is widely used
to represent the digital information in a human readable format.
Decimal number system is a base 10 number system having 10 unique digits i.e., 0, 1, 2,
3, 4, 5, 6, 7, 8, and 9. It is the standard number system used by human beings to represent
information in a natural way. However, a digital system cannot directly process the
information represented in decimal form, so it is converted into binary form and then
processed.
The base of the decimal number system is 10. So, the value of a decimal number is
calculated by the sum of powers of 10.
Example
Consider the decimal number 1358.246. The integer part of this number is 1358 and the
fractional part of this number is 0.246. The digits 8, 5, 3 and 1 have weights of (10) 0, (10)1,
(10)2 and (10)3 respectively. Similarly, the digits 2, 4 and 6 have weights of (10)-1, (10)-2 and
(10)-3 respectively.
Mathematically, we can write it as,

After simplifying the right-hand side terms, we will get the decimal number, which is on
the left-hand side.
Octal Number System
The octal number system is another type of digital number system used in the field of
digital electronics to represent information. It is a base 8 number system having eight
unique digits i.e., 0, 1, 2, 3, 4, 5, 6, and 7.
It is important note that the octal number system is equivalent to 3-bit binary number
system as 23 = 8. Hence, this number system can be used in computing and digital
electronic applications.
The value of an octal number is obtained by the sum of powers of 8, as 8 is the base of
the octal number system.
Octal number system is used in the field of digital electronics to represent binary
information in compact form, permissions in Linux or Unix systems, IPv6 address, binary
machine code instructions, in error detection algorithms, etc.
Example
Consider the octal number 1457.236. Integer part of this number is 1457 and fractional
part of this number is 0.236. The digits 7, 5, 4 and 1 have weights of (8) 0, (8)1, (8)2 and
(8)3 respectively. Similarly, the digits 2, 3 and 6 have weights of (8)-1, (8)-2, (8)-3 respectively.
Mathematically, we can write it as,

After simplifying the right-hand side terms, we will get a decimal number, which is an
equivalent of octal number on the left-hand side.
Hexadecimal Number System
The hexadecimal number system is a base 16 number system. It has 16 digits, 0 to 9 and
A to F. Where, A represents 10, B represents 11, C represents 12, D represents 13, E
represents 14, and F represents 15. The hexadecimal number system is equivalent to a
4-bit binary number system as 24 = 16. Thus, the value of a hexadecimal number can be
calculated by the sum of powers of 16.
In the field of digital electronics, the hexadecimal number system is used in memory
address representation, digital colors representation, low level computer programming,
encoding, assembly language programming, microcontrollers, keyboards, etc.
Hexadecimal number system creates a balance between digital representation and
human readability.
Example
Consider the hexadecimal number 1A05.2C4. The integer part of this number is 1A05 and
the fractional part of this number is 0.2C4. The digits 5, 0, A and 1 have weights of (16) 0,
(16)1, (16)2 and (16)3 respectively. Similarly, the digits 2, C and 4 have weights of (16)-1 ,
(16)-2 and (16)-3 respectively.
Mathematically, we can write it as,
After simplifying the right-hand side terms, we will get a decimal number, which is an
equivalent of the hexadecimal number on the left-hand side.
Advantages of Digital Number Systems
The following are some key advantages of digital number systems −
• Digital number systems provide a simple and consistent way of representing and
understanding information.
• Digital number systems allow to develop efficient methods for storage and
transmission of digital information.
• Digital number systems provide methods of representing different types of
information like text, numbers, images, etc.
• Digital number systems allow to convert information from one form to full fill the
needs of applications.
• Digital number systems create compatibility between hardware and software.
Applications of Digital Number Systems
Digital number systems are used in various digital electronic fields such as computing,
internet, communication, signal processing, and more. Here are a few examples of
applications of digital number systems −
• Information Representation
• Digital Communication
• Storage and Transmission of Digital Data and Information
• Algorithm Development
• System Programming, etc.
--------------------------------------------------------------------------------------------------------------
2. 1‘s and 2‘s complements

Complements are used in digital computers in order to simply the subtraction operation
and for the logical manipulations. For the Binary number (base-2) system, there are two
types of complements: 1’s complement and 2’s complement.
1’s Complement of a Binary Number
There is a simple algorithm to convert a binary number into 1’s complement. To get 1’s
complement of a binary number, simply invert the given number.
2’s Complement of a Binary Number
 There is a simple algorithm to convert a binary number into 2’s complement. To get 2’s
complement of a binary number, simply invert the given number and add 1 to the least
significant bit (LSB) of given result.
Differences between 1’s complement and 2’s complement
These differences are given as following below −

1’s complement 2’s complement

To get 2’s complement of a binary number,

To get 1’s complement of a binary number,
simply invert the given number and add 1 to
simply invert the given number.
the least significant bit (LSB) of given result.

1’s complement of binary number 110010 is 2’s complement of binary number 110010 is
001101 001110

Simple implementation which uses only NOT Uses NOT gate along with full adder for each
gates for each input bit. input bit.

Can be used for signed binary number Can be used for signed binary number
representation but not suitable as ambiguous representation and most suitable as
representation for number 0. unambiguous representation for all numbers.

0 has two different representation one is -0 0 has only one representation for -0 and +0
(e.g., 1 1111 in five bit register) and second is (e.g., 0 0000 in five bit register). Zero (0) is
+0 (e.g., 0 0000 in five bit register). considered as always positive (sign bit is 0)

For k bits register, positive largest number that For k bits register, positive largest number that
can be stored is (2(k-1)-1) and negative lowest can be stored is (2(k-1)-1) and negative lowest
number that can be stored is -(2(k-1)-1). number that can be stored is -(2(k-1)).

end-around-carry-bit addition occurs in 1’s end-around-carry-bit addition does not occur

complement arithmetic operations. It added in 2’s complement arithmetic operations. It is
to the LSB of result. ignored.

1’s complement arithmetic operations are not 2’s complement arithmetic operations are
easier than 2’s complement because much easier than 1’s complement because of
of addition of end-around-carry-bit. there is no addition of end-around-carry-bit.

Sign extension is used for converting a signed Sign extension is used for converting a signed
integer from one size to another. integer from one size to another.

--------------------------------------------------------------------------------------------------------------
3. Logic gates
A logic gates are an electronic circuit that are designed by using electrical components
like diodes, transistors, resistors, and more. It is used to perform logical operations based
on the inputs provided to it and gives a logical output that can be either high(1) or low(0).
The operation of logic gates is based on Boolean algebra or mathematics. Logic gates find
their uses in our day-to-day lives, such as in the architecture of our telephones, laptops,
tablets and memory devices.
Types of Logic Gates
AND GATE
An AND gate is used to perform logical Multiplication of binary input. The Output state of
the AND gate will be high (1) if both the input is high (1), else the output state will be low(0)
if any of the input is low (0).

OR GATE
OR GATE is most widely used digital logic circuit. The output state of OR gate will be high
i.e., (1) if any of the input state is high or 1, else output state will be low i.e., 0.

NOT GATE
In digital electronics, the NOT gate is one of the basic Logic Gate having only a single
input and a single output. It is also known as inverter or inverting buffer. When the input
signal is "low" the output signal is "high" and vice-versa.
NOR GATE
The NOR gate is the type of universal logic gate. It takes two or more inputs and gives
only one output. The output state of the NOR gate will be high (1) when all the inputs are
low (0). NOR gate returns the complement result of the OR gate. It is basically a
combination of two basic logic gates i.e., OR gate and NOT gate.

NAND GATE
The NAND Gate is another type of Universal logic gate. The NAND gate or "Not AND" is the
combination of two basic logic gates AND gate and the NOT gate connected in series. It
takes two or more inputs and gives only one output. The output of the NAND gate will give
result high (1) when either of its input is high (1) or both of its input are low (0). In simple,
it performs the inverted operation of AND gate.

XOR GATE

In digital electronics, there is a specially designed logic gate named, XOR gate, which is
used in digital circuits to perform modulo sum. It is also referred to as Exclusive OR gate
or Ex-OR gate. it is used extensively in arithmetic logic circuits., logic comparators and
error detection circuits. The XOR gate can take only two inputs at a time and give an
output. The output of the XOR gate is high (1) only when its two inputs are dissimilar i.e.,
if one of them is low (0) then other one will be high (1).

XNOR GATE
The XNOR is the combination of XOR gate and NOT gate. The output of the XNOR gate is
high(1) when both the inputs are high (1) or low(0). In other words, the output of the XNOR
gate is high(1) when both the inputs are the same. the XNOR gate can sometimes be
called as Equivalence gate. In simple words, The XNOR gate is the complement of the
XOR gate.
--------------------------------------------------------------------------------------------------------------
[Link]

INTRODUCTION:

.in
The digital system consists of two types of circuits, namely
(i) Combinational circuits
(ii) Sequential circuits

ee
Combinational circuit consists of logic gates whose output at any time is
determined from the present combination of inputs. The logic gate is the most basic
sfr
building block of combinational logic. The logical function performed by a
combinational circuit is fully defined by a set of Boolean expressions.
Sequential logic circuit comprises both logic gates and the state of storage
ote

elements such as flip-flops. As a consequence, the output of a sequential circuit

depends not only on present value of inputs but also on the past state of inputs.
In the previous chapter, we have discussed binary numbers, codes, Boolean
algebra and simplification of Boolean function and logic gates. In this chapter,
N

formulation and analysis of various systematic designs of combinational circuits will

be discussed.
w.

A combinational circuit consists of input variables, logic gates, and output

variables. The logic gates accept signals from inputs and output signals are
generated according to the logic circuits employed in it. Binary information from the
ww

given data transforms to desired output data in this process. Both input and output
are obviously the binary signals, i.e., both the input and output signals are of two
possible states, logic 1 and logic 0.

[Link]
[Link]

Block diagram of a combinational logic circuit

For n number of input variables to a combinational circuit, 2n possible

combinations of binary input states are possible. For each possible combination,
there is one and only one possible output combination. A combinational logic circuit
can be described by m Boolean functions and each output can be expressed in terms
of n input variables.

.in
DESIGN PROCEDURES:

ee
Any combinational circuit can be designed by the following steps of design
procedure.
1. The problem is stated.
sfr
2. Identify the input and output variables.
3. The input and output variables are assigned letter symbols.
4. Construction of a truth table to meet input -output requirements.
ote

5. Writing Boolean expressions for various output variables in terms of input

variables.
6. The simplified Boolean expression is obtained by any method of
N

minimization—algebraic method, Karnaugh map method, or tabulation

method.
7. A logic diagram is realized from the simplified Boolean expression using logic
w.

gates.
ww

The following guidelines should be followed while choosing the preferred

form for hardware implementation:
1. The implementation should have the minimum number of gates, with the
gates used having the minimum number of inputs.
2. There should be a minimum number of interconnections.
3. Limitation on the driving capability of the gates should not be ignored.

[Link]
[Link]

Problems:
1. Design a combinational circuit with three inputs and one output. The output is 1
when the binary value of the inputs is less than 3. The output is 0 otherwise.
Solution:
Truth Table:

.in
x y z F
0 0 0 1
0 0 1 1
0 1 0 1

ee
0 1 1 0
1 0 0 0
1 0 1 0
sfr
1 1 0 0
1 1 1 0
K-map Simplification:
N ote

Logic Diagram:
w.

The combinational circuit can be drawn as,

ww

2. Design a combinational circuit with three inputs, x, y and z, and the three
outputs, A, B, and C. when the binary input is 0, 1, 2, or 3, the binary output is

[Link]
[Link]

one greater than the input. When the binary input is 4, 5, 6, or 7, the binary
output is one less than the input.
Solution:
Truth Table:
Derive the truth table that defines the required relationship between inputs and
outputs.

x y z A B C
0 0 0 0 0 1

.in
0 0 1 0 1 0
0 1 0 0 1 1
0 1 1 1 0 0

ee
1 0 0 0 1 1
1 0 1 1 0 0
1 1 0 1 0 1
1 1 1 1 1 0
sfr
Obtain the simplified Boolean functions for each output as a function of the input
variables.
K-map for output A:
N ote

The simplified expression from the map is: A= xz+ xy+ yz

w.

Logic Diagram:
ww

K-map for output B:

[Link]
[Link]

The simplified expression from the map is: B= x’y’z+ x’yz’+ xy’z’+ xyz
Logic Diagram:

.in
ee
sfr
K-map for output C:
ote

The simplified expression from the map is: C=z’

Logic Diagram:
N
w.

3. A majority circuit is a combinational circuit whose output is equal to 1 if the

input variables have more 1’s than 0’s. The output is 0 otherwise. Design a 3-
ww

input majority circuit.

Solution:
Truth Table:

x y z F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
5

[Link]
[Link]

1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

K-map Simplification:

.in
The simplified expression from the map is: xz+ yz+ xy

ee
Logic Diagram:
sfr
ote

4. Design a combinational circuit that generates the 9's complement of a BCD digit.
N

Solution:
Truth Table:
w.

Inputs Outputs
A B C D w x y z
0 0 0 0 1 0 0 1
0 0 0 1 1 0 0 0
ww

0 0 1 0 0 1 1 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 0 1 1
0 1 1 1 0 0 1 0
1 0 0 0 0 0 0 1
1 0 0 1 0 0 0 0
6

[Link]
[Link]

K-map Simplification:

.in
ee
sfr
N ote
w.

Logic Diagram:
ww

[Link]
[Link]

ARITHMETIC CIRCUITS:
In this section, we will discuss those combinational logic building blocks that
can be used to perform addition and subtraction operations on binary numbers.
Addition and subtraction are the two most commonly used arithmetic operations, as

.in
the other two, namely multiplication and division, are respectively the processes of
repeated addition and repeated subtraction.
The basic building blocks that form the basis of all hardware used to perform

ee
the arithmetic operations on binary numbers are half-adder, full adder, half-
subtractor, full-subtractor.
sfr
Half-Adder:
A half-adder is a combinational circuit that can be used to add two binary bits.
It has two inputs that represent the two bits to be added and two outputs, with one
producing the SUM output and the other producing the CARRY.
N ote

Block schematic of half-adder

The truth table of a half-adder, showing all possible input combinations and
w.

the corresponding outputs are shown below.

Truth Table:

Inputs Outputs
ww

A B Sum (S) Carry (C)

0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
K-map simplification:

[Link]
[Link]

The Boolean expressions for the SUM and CARRY outputs are given by the
equations,

.in
Sum, S = A’B+ AB’= AB
Carry, C = A . B
The first one representing the SUM output is that of an EX-OR gate, the

ee
second one representing the CARRY output is that of an AND gate.
The logic diagram of the half adder is,
sfr
ote

Logic Implementation of Half-adder

N

Full-Adder:
A full adder is a combinational circuit that forms the arithmetic sum of three
w.

input bits. It consists of three inputs and two outputs.

Two of the input variables, represent the significant bits to be added. The
third input represents the carry from previous lower significant position. The block
ww

diagram of full adder is given by,

Block schematic of full-adder

[Link]
[Link]

The full adder circuit overcomes the limitation of the half-adder, which can be
used to add two bits only. As there are three input variables, eight different input
combinations are possible.

Truth Table:

.in
Inputs Outputs
A B Cin Sum (S) Carry (Cout)
0 0 0 0 0
0 0 1 1 0

ee
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1
sfr0 1 0 1
1 1 0 0 1
1 1 1 1 1
ote

K-map simplification:
N
w.

The Boolean expressions for the SUM and CARRY outputs are given by the eqns.,
ww

Carry, Cout= AB+ ACin + BCin .

Logic Diagram:

10

[Link]
[Link]

.in
The logic diagram of the full adder can also be implemented with two half-

ee
adders and one OR gate. The S output from the second half adder is the exclusive-
OR of Cin and the output of the first half-adder, giving
Sum = Cin  (A  B) [x  y = x’y+ xy’]
sfr
= Cin  (A’B+AB’)
= C’in (A’B+AB’) + Cin (A’B+AB’)’ [(x’y+xy’)’= (xy+x’y’)]
= C’in (A’B+AB’) + Cin (AB+A’B’)
ote

= A’BC’in + AB’C’in + ABCin + A’B’Cin .

and the carry output is,

Carry, Cout = AB+ Cin (A’B+AB’)
N

= AB+ A’BCin+ AB’Cin

= B (A+A’Cin) + AB’Cin
w.

= B (A+Cin) + AB’Cin
= AB + BCin + AB’Cin
= AB + Cin (B + AB’)
ww

= AB + Cin (A + B)
= AB+ ACin+ BCin.

11

[Link]
[Link]

Implementation of full adder with two half-adders and an OR gate

Half -Subtractor

.in
A half-subtractor is a combinational circuit that can be used to subtract one
binary digit from another to produce a DIFFERENCE output and a BORROW output.
The BORROW output here specifies whether a ‘1’ has been borrowed to perform the

ee
subtraction. sfr
Block schematic of half-subtractor
ote

The truth table of half-subtractor, showing all possible input combinations

and the corresponding outputs are shown below.

Inputs Outputs
A B Difference (D) Borrow (Bout)
N

0 0 0 0
0 1 1 1
1 0 1 0
w.

1 1 0 0

K-map simplification:
ww

The Boolean expressions for the DIFFERENCE and BORROW outputs are
given by the equations,
12

[Link]
[Link]

Difference, D = A’B+ AB’= A  B

Borrow, Bout = A’ . B
The first one representing the DIFFERENCE (D)output is that of an exclusive-
OR gate, the expression for the BORROW output (Bout) is that of an AND gate with
input A complemented before it is fed to the gate.
The logic diagram of the half adder is,

.in
ee
Logic Implementation of Half-Subtractor

Comparing a half-subtractor with a half-adder, we find that the expressions

for the SUM and DIFFERENCE outputs are just the same. The expression for
sfr
BORROW in the case of the half-subtractor is also similar to what we have for
CARRY in the case of the half-adder. If the input A, ie., the minuend is
complemented, an AND gate can be used to implement the BORROW output.
ote

Full Subtractor:
A full subtractor performs subtraction operation on two bits, a minuend and
a subtrahend, and also takes into consideration whether a ‘1’ has already been
N

borrowed by the previous adjacent lower minuend bit or not.

As a result, there are three bits to be handled at the input of a full subtractor,
w.

namely the two bits to be subtracted and a borrow bit designated as B in. There are
two outputs, namely the DIFFERENCE output D and the BORROW output Bo. The
BORROW output bit tells whether the minuend bit needs to borrow a ‘1’ from the
next possible higher minuend bit.
ww

Block schematic of full- subtractor

The truth table for full-subtractor is,
Inputs Outputs
13

[Link]
[Link]

A B Bin Difference(D) Borrow(Bout)

0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1

.in
K-map simplification:

ee
sfr
ote

The Boolean expressions for the DIFFERENCE and BORROW outputs are
given by the equations,
N
w.

Borrow, Bout = A’B+ A’Bin + BBin .

ww

The logic diagram for the above functions is shown as,

14

[Link]
[Link]

.in
Implementation of full- subtractor

The logic diagram of the full-subtractor can also be implemented with two
half-subtractors and one OR gate. The difference,D output from the second half

ee
subtractor is the exclusive-OR of Bin and the output of the first half-subtractor, giving
Difference,D= Bin  (A  B) [x  y = x’y+ xy’]
= Bin  (A’B+AB’)
sfr
= B’in (A’B+AB’) + Bin (A’B+AB’)’ [(x’y+xy’)’= (xy+x’y’)]
= B’in (A’B+AB’) + Bin (AB+A’B’)
= A’BB’in + AB’B’in + ABBin + A’B’Bin .
ote

and the borrow output is,

Borrow, Bout = A’B+ Bin (A’B+AB’)’ [(x’y+xy’)’= (xy+x’y’)]
= A’B+ Bin (AB+A’B’)
N

= A’B+ ABBin+ A’B’Bin

= B (A’+ABin) + A’B’Bin
= B (A’+Bin) + A’B’Bin
w.

= A’B + BBin + A’B’Bin

= A’B + Bin( B + A’B’)
ww

= A’B + Bin (B+ A’)

= A’B+ BBin+ A’Bin.
Therefore,
We can implement full-subtractor using two half-subtractors and OR gate as,

15

[Link]
[Link]

Implementation of full-subtractor with two half-subtractors and an OR gate

.in
Binary Adder (Parallel Adder)
The 4-bit binary adder using full adder circuits is capable of adding two 4-bit

ee
numbers resulting in a 4-bit sum and a carry output as shown in figure below.
sfr
ote

4-bit binary parallel Adder

Since all the bits of augend and addend are fed into the adder circuits
simultaneously and the additions in each position are taking place at the same time,
N

this circuit is known as parallel adder.

Let the 4-bit words to be added be represented by,

w.

A3 A2 A1 A0= 1 1 1 1 and B3 B2 B1 B0= 1 0 1 1.

ww

The bits are added with full adders, starting from the least significant position,
to form the sum it and carry bit. The input carry C0 in the least significant position
must be 0. The carry output of the lower order stage is connected to the carry input
of the next higher order stage. Hence this type of adder is called ripple-carry adder.
16

[Link]
[Link]

In the least significant stage, A0, B0 and C0 (which is 0) are added resulting in
sum S0 and carry C1. This carry C1 becomes the carry input to the second stage.
Similarly in the second stage, A1, B1 and C1 are added resulting in sum S1 and carry
C2, in the third stage, A2, B2 and C2 are added resulting in sum S2 and carry C3, in the
third stage, A3, B3 and C3 are added resulting in sum S3 and C4, which is the output
carry. Thus the circuit results in a sum (S3 S2 S1 S0) and a carry output (Cout).

Though the parallel binary adder is said to generate its output immediately

.in
after the inputs are applied, its speed of operation is limited by the carry
propagation delay through all stages. However, there are several methods to reduce
this delay.

ee
One of the methods of speeding up this process is look-ahead carry addition
which eliminates the ripple-carry delay.
sfr
ote

Carry Look Ahead Adder:

In Parallel adder, all the bits of the augend and the addend are available for
N

computation at the same time. The carry output of each full-adder stage is connected
to the carry input of the next high-order stage. Since each bit of the sum output
w.

depends on the value of the input carry, time delay occurs in the addition process.
This time delay is called as carry propagation delay.
For example, addition of two numbers (1111+ 1011) gives the result as 1010.
ww

Addition of the LSB position produces a carry into the second position. This carry
when added to the bits of the second position, produces a carry into the third
position. This carry when added to bits of the third position, produces a carry into
the last position. The sum bit generated in the last position (MSB) depends on the
carry that was generated by the addition in the previous position. i.e., the adder will
not produce correct result until LSB carry has propagated through the intermediate
full-adders. This represents a time delay that depends on the propagation delay
17

[Link]
[Link]

produced in an each full-adder. For example, if each full adder is considered to have
a propagation delay of 8nsec, then S3 will not react its correct value until 24 nsec
after LSB is generated. Therefore total time required to perform addition is 24+ 8 =
32nsec.

.in
ee
The method of speeding up this process by eliminating inter stage carry delay
sfr
is called look ahead-carry addition. This method utilizes logic gates to look at the
lower order bits of the augend and addend to see if a higher-order carry is to be
generated. It uses two functions: carry generate and carry propagate.
N ote
w.

Full-Adder circuit

Consider the circuit of the full-adder shown above. Here we define two
functions: carry generate (Gi) and carry propagate (Pi) as,
ww

Carry propagate, Pi = Ai  Bi
Carry generate, Gi = Ai . Bi
the output sum and carry can be expressed as,
Si = Pi  Ci
Ci+1 = Gi + [Link]

18

[Link]
[Link]

Gi (carry generate), it produces a carry 1 when both Ai and Bi are 1, regardless of the
input carry Ci. Pi (carry propagate), is the term associated with the propagation of
the carry from Ci to Ci+1.
The Boolean functions for the carry outputs of each stage and substitute for
each Ci its value from the previous equation:
C0= input carry
C1= G0 + P0C0
C2= G1 + P1C1 = G1 + P1 (G0 + P0C0)

.in
= G1 + P1G0 + P1P0C0
C3= G2 + P2C2 = G2 + P2 (G1 + P1G0 + P1P0C0)
= G2 + P2G1 + P2P1G0 + P2P1P0C0

ee
Since the Boolean function for each output carry is expressed in sum of
products, each function can be implemented with one level of AND gates followed
by an OR gate. The three Boolean functions for C1, C2 and C3 are implemented in the
sfr
carry look-ahead generator as shown below.
N ote
w.
ww

Logic diagram of Carry Look-ahead Generator

19

[Link]
[Link]

Note that C3 does not have to wait for C2 and C1 to propagate; in fact C3 is
propagated at the same time as C1 and C2.
Using a Look-ahead Generator we can easily construct a 4-bit parallel adder
with a Look-ahead carry scheme. Each sum output requires two exclusive-OR gates.
The output of the first exclusive-OR gate generates the Pi variable, and the AND gate
generates the Gi variable. The carries are propagated through the carry look-ahead
generator and applied as inputs to the second exclusive-OR gate. All output carries
are generated after a delay through two levels of gates. Thus, outputs S 1 through S3

.in
have equal propagation delay times.

ee
sfr
N ote
w.
ww

4-Bit Adder with Carry Look-ahead

Binary Subtractor (Parallel Subtractor)

20

[Link]
[Link]

The subtraction of unsigned binary numbers can be done most conveniently

by means of complements. The subtraction (A – B) can be done by taking the 2’s
complement of B and adding it to A. The 2’s complement can be obtained by taking
the 1’s complement and adding 1 to the least significant pair of bits. The 1’s
complement can be implemented with inverters and a 1 can be added to the sum
through the input carry.

The circuit for subtracting (A – B) consists of an adder with inverters placed

between each data input B and the corresponding input of the full adder. The input

.in
carry C0 must be equal to 1 when performing subtraction. The operation thus
performed becomes A, plus the 1’s complement of B, plus1. This is equal to A plus
the 2’s complement of B.
Let the 4-bit words to be subtracted be represented by,

ee
A3 A2 A1 A0= 1 1 1 1 and B3 B2 B1 B0= 1 0 1 1.
sfr
N ote
w.
ww

4-bit Parallel Subtractor

Parallel Adder/ Subtractor

21

[Link]
[Link]

The addition and subtraction operation can be combined into one circuit with
one common binary adder. This is done by including an exclusive-OR gate with each
full adder. A 4-bit adder Subtractor circuit is shown below.

.in
ee
4-Bit Adder Subtractor

The mode input M controls the operation. When M= 0, the circuit is an adder
sfr
and when M=1, the circuit becomes a Subtractor. Each exclusive-OR gate receives
input M and one of the inputs of B. When M=0, we have B 0= B. The full adders
receive the value of B, the input carry is 0, and the circuit performs A plus B. When
ote

M=1, we have B 1= B’ and C0=1. The B inputs are all complemented and a 1 is
added through the input carry. The circuit performs the operation A plus the 2’s
complement of B. The exclusive-OR with output V is for detecting an overflow.
N

Decimal Adder (BCD Adder)

The digital system handles the decimal number in the form of binary coded
w.

decimal numbers (BCD). A BCD adder is a circuit that adds two BCD bits and
produces a sum digit also in BCD.
Consider the arithmetic addition of two decimal digits in BCD, together with
ww

an input carry from a previous stage. Since each input digit does not exceed 9, the
output sum cannot be greater than 9+ 9+1 = 19; the 1 is the sum being an input carry.
The adder will form the sum in binary and produce a result that ranges from 0
through 19.
These binary numbers are labeled by symbols C, S3, S2, S1, S0, C is the carry.
The columns under the binary sum list the binary values that appear in the outputs

22

[Link]
[Link]

of the 4-bit binary adder. The output sum of the two decimal digits must be
represented in BCD.
To implement BCD adder:
• For initial addition , a 4-bit binary adder is required,
• Combinational circuit to detect whether the sum is greater than 9 and
• One more 4-bit adder to add 6 (0110)2 with the sum of the first 4-bit adder, if
the sum is greater than 9 or carry is 1.

.in
The logic circuit to detect sum greater than 9 can be determined by
simplifying the Boolean expression of the given truth table.

ee
sfr
N ote
w.

The two decimal digits, together with the input carry, are first added in the
top4-bit binary adder to provide the binary sum. When the output carry is equal to
zero, nothing is added to the binary sum. When it is equal to one, binary (0110)2 is
ww

added to the binary sum through the bottom 4-bit adder.

23

[Link]
[Link]

.in
ee
The output carry generated from the bottom adder can be ignored, since it
sfr
supplies information already available at the output carry terminal. The output carry
from one stage must be connected to the input carry of the next higher-order stage.

MULTIPLEXER: (Data Selector)

ote

A Multiplexer or MUX, is a combinational circuit with more than one input

line, one output line and more than one selection line. A multiplexer selects binary
information present from one of many input lines, depending upon the logic status
of the selection inputs, and routes it to the output line. Normally, there are 2 n input
N

lines and n selection lines whose bit combinations determine which input is selected.
The multiplexer is often labeled as MUX in block diagrams.
w.

A multiplexer is also called a data selector, since it selects one of many inputs
and steers the binary information to the output line.
ww

Block diagram of Multiplexer

24

[Link]
[Link]

2-to-1- line Multiplexer:

The circuit has two data input lines, one output line and one selection line, S.
When S= 0, the upper AND gate is enabled and I0 has a path to the output.
When S=1, the lower AND gate is enabled and I1 has a path to the output.

.in
Logic diagram

ee
The multiplexer acts like an electronic switch that selects one of the two sources.
Truth table:

S Y
sfr
0 I0
1 I1

4-to-1-line Multiplexer
ote

A 4-to-1-line multiplexer has four (2n) input lines, two (n) select lines and one
output line. It is the multiplexer consisting of four input channels and information of
one of the channels can be selected and transmitted to an output line according to
the select inputs combinations. Selection of one of the four input channel is possible
N

by two selection inputs.

Each of the four inputs I0 through I3, is applied to one input of AND gate.
w.

Selection lines S1 and S0 are decoded to select a particular AND gate. The outputs of
the AND gate are applied to a single OR gate that provides the 1-line output.
ww

25

[Link]
[Link]

.in
ee
4-to-1-Line Multiplexer
Function table:

S1 S0 Y
sfr 0 0 I0
0 1 I1
1 0 I2
1 1 I3
ote

To demonstrate the circuit operation, consider the case when S 1S0= 10. The
AND gate associated with input I2 has two of its inputs equal to 1 and the third input
connected to I2. The other three AND gates have atleast one input equal to 0, which
makes their outputs equal to 0. The OR output is now equal to the value of I 2,
N

providing a path from the selected input to the output.

The data output is equal to I0 only if S1= 0 and S0= 0; Y= I0S1’S0’.
The data output is equal to I1 only if S1= 0 and S0= 1; Y= I1S1’S0.
w.

The data output is equal to I2 only if S1= 1 and S0= 0; Y= I2S1S0’.

The data output is equal to I3 only if S1= 1 and S0= 1; Y= I3S1S0.
When these terms are ORed, the total expression for the data output is,
ww

Y= I0S1’S0’+ I1S1’S0 +I2S1S0’+ I3S1S0.

As in decoder, multiplexers may have an enable input to control the operation
of the unit. When the enable input is in the inactive state, the outputs are disabled,
and when it is in the active state, the circuit functions as a normal multiplexer.

Quadruple 2-to-1 Line Multiplexer

26

[Link]
[Link]

.in
ee
sfr
N ote

This circuit has four multiplexers, each capable of selecting one of two input
lines. Output Y0 can be selected to come from either A0 or B0. Similarly, output Y1
w.

may have the value of A1 or B1, and so on. Input selection line, S selects one of the
lines in each of the four multiplexers. The enable input E must be active for normal
operation.
ww

Although the circuit contains four 2-to-1-Line multiplexers, it is viewed as a

circuit that selects one of two 4-bit sets of data lines. The unit is enabled when E= 0.
Then if S= 0, the four A inputs have a path to the four outputs. On the other hand, if
S=1, the four B inputs are applied to the outputs. The outputs have all 0’s when E= 1,
regardless of the value of S.

Application:

27

[Link]
[Link]

1. They are used as a data selector to select out of many data inputs.
2. They can be used to implement combinational logic circuit.
3. They are used in time multiplexing systems.
4. They are used in frequency multiplexing systems.
5. They are used in A/D and D/A converter.
6. They are used in data acquisition systems.

Implementation of Boolean Function using MUX:

.in
1. Implement the following boolean function using 4: 1 multiplexer,
F (A, B, C) = ∑m (1, 3, 5, 6).
Solution:

ee
Variables, n= 3 (A, B, C)
Select lines= n-1 = 2 (S1, S0)
2n-1 to MUX i.e., 22 to 1 = 4 to 1 MUX
sfr
Input lines= 2n-1 = 22 = 4 (D0, D1, D2, D3)
Implementation table:
Apply variables A and B to the select lines. The procedures for implementing the
ote

function are:
i. List the input of the multiplexer
ii. List under them all the minterms in two rows as shown below.
The first half of the minterms is associated with A’ and the second half
N

with A. The given function is implemented by circling the minterms of the

function and applying the following rules to find the values for the inputs of the
w.

multiplexer.
1. If both the minterms in the column are not circled, apply 0 to the corresponding
input.
ww

2. If both the minterms in the column are circled, apply 1 to the corresponding
input.
3. If the bottom minterm is circled and the top is not circled, apply C to the input.
4. If the top minterm is circled and the bottom is not circled, apply C’ to the input.

28

[Link]
[Link]

Multiplexer Implementation:

.in
ee
sfr
ote

2. F (x, y, z) = ∑m (1, 2, 6, 7)
Implementation table:
N
w.
ww

Multiplexer Implementation:

29

[Link]
[Link]

.in
3. F ( A, B, C) = ∑m (1, 2, 4, 5)

ee
Solution:
Variables, n= 3 (A, B, C)
Select lines= n-1 = 2 (S1, S0)
sfr
2n-1 to MUX i.e., 22 to 1 = 4 to 1 MUX
Input lines= 2n-1 = 22 = 4 (D0, D1, D2, D3)
Implementation table:
N ote

Multiplexer Implementation
w.
ww

4. F( A, B, C, D)= ∑m (0, 1, 3, 4, 8, 9, 15)

30

[Link]
[Link]

Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:

.in
ee
Multiplexer Implementation:
sfr
N ote
w.

5. Implement the Boolean function using 8: 1 and also using 4:1 multiplexer
F (A, B, C, D) = ∑m (0, 1, 2, 4, 6, 9, 12, 14)
ww

Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:

31

[Link]
[Link]

Multiplexer Implementation (Using 8: 1 MUX)

.in
ee
sfr
ote

Using 4: 1 MUX:
N
w.
ww

6. F (A, B, C, D) = ∑m (1, 3, 4, 11, 12, 13, 14, 15)

32

[Link]
[Link]

Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:

.in
ee
Multiplexer Implementation:
sfr
N ote
w.
ww

7. Implement the Boolean function using 8: 1 multiplexer.

F (A, B, C, D) = A’BD’ + ACD + B’CD + A’C’D.
Solution:
Convert into standard SOP form,
= A’BD’ (C’+C) + ACD (B’+B) + B’CD (A’+A) + A’C’D (B’+B)
= A’BC’D’ + A’BCD’+ AB’CD + ABCD +A’B’CD + AB’CD +A’B’C’D+ A’BC’D
33

[Link]
[Link]

= A’BC’D’ + A’BCD’+ AB’CD + ABCD +A’B’CD +A’B’C’D+ A’BC’D

= m4+ m6+ m11+ m15+ m3+ m1+ m5
= ∑m (1, 3, 4, 5, 6, 11, 15)
Implementation table:

.in
Multiplexer Implementation:

ee
sfr
N ote
w.

8. Implement the Boolean function using 8: 1 multiplexer.

F (A, B, C, D) = AB’D + A’C’D + B’CD’ + AC’D.
Solution:
ww

= AB’D (C’+C) + A’C’D (B’+B) + B’CD’ (A’+A) + AC’D (B’+B)

= AB’C’D + AB’CD+ A’B’C’D + A’BC’D +A’B’CD’ + AB’CD’ +AB’C’D+
ABC’D
= AB’C’D + AB’CD+ A’B’C’D + A’BC’D +A’B’CD’ + AB’CD’+ ABC’D
= m9+ m11+ m1+ m5+ m2+ m10+ m13
= ∑m (1, 2, 5, 9, 10, 11, 13).
Implementation Table:
34

[Link]
[Link]

Multiplexer Implementation:

.in
ee
sfr
ote

9. Implement the Boolean function using 8: 1 and also using 4:1 multiplexer
F (w, x, y, z) = ∑m (1, 2, 3, 6, 7, 8, 11, 12, 14)
N

Solution:
Variables, n= 4 (w, x, y, z)
w.

Select lines= n-1 = 3 (S2, S1, S0)

2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
ww

Implementation table:

Multiplexer Implementation (Using 8:1 MUX):

35

[Link]
[Link]

.in
ee
sfr
(Using 4:1 MUX)
N ote
w.
ww

10. Implement the Boolean function using 8: 1 multiplexer

36

[Link]
[Link]

F (A, B, C, D) = ∏m (0, 3, 5, 8, 9, 10, 12, 14)

Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation table:

.in
ee
Multiplexer Implementation:
sfr
N ote
w.

11. Implement the Boolean function using 8: 1 multiplexer

ww

F (A, B, C, D) = ∑m (0, 2, 6, 10, 11, 12, 13) + d (3, 8, 14)

Solution:
Variables, n= 4 (A, B, C, D)
Select lines= n-1 = 3 (S2, S1, S0)
2n-1 to MUX i.e., 23 to 1 = 8 to 1 MUX
Input lines= 2n-1 = 23 = 8 (D0, D1, D2, D3, D4, D5, D6, D7)
Implementation Table:
37

[Link]
[Link]

Multiplexer Implementation:

.in
ee
sfr
ote

DEMULTIPLEXER

Demultiplex means one into many. Demultiplexing is the process of taking

N

information from one input and transmitting the same over one of several outputs.
A demultiplexer is a combinational logic circuit that receives information on a
w.

single input and transmits the same information over one of several (2n) output lines.
ww

Block diagram of demultiplexer

38

[Link]
[Link]

The block diagram of a demultiplexer which is opposite to a multiplexer in its

operation is shown above. The circuit has one input signal, ‘n’ select signals and 2 n
output signals. The select inputs determine to which output the data input will be
connected. As the serial data is changed to parallel data, i.e., the input caused to
appear on one of the n output lines, the demultiplexer is also called a “data
distributer” or a “serial-to-parallel converter”.

.in
1-to-4 line Demultiplexer
A 1-to-4 demultiplexer has a single input, Din, four outputs (Y0 to Y3) and two
select inputs (S1 and S0).

ee
sfr
ote

Logic Symbol

The input variable Din has a path to all four outputs, but the input information
is directed to only one of the output lines. The truth table of the 1-to-4 demultiplexer
N

is shown below.

Enable S1 S0 Din Y0 Y1 Y2 Y3
w.

0 x x x 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 1 0 0 0 0 0
ww

1 0 1 1 0 1 0 0
1 1 0 0 0 0 0 0
1 1 0 1 0 0 1 0
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 1
Truth table of 1-to-4 demultiplexer

39

[Link]
[Link]

From the truth table, it is clear that the data input, Din is connected to the
output Y0, when S1= 0 and S0= 0 and the data input is connected to output Y1 when
S1= 0 and S0= 1. Similarly, the data input is connected to output Y2 and Y3 when S1= 1
and S0= 0 and when S1= 1 and S0= 1, respectively. Also, from the truth table, the
expression for outputs can be written as follows,
Y0= S1’S0’Din
Y1= S1’S0Din
Y2= S1S0’Din

.in
Y3= S1S0Din

ee
sfr
N ote

Logic diagram of 1-to-4 demultiplexer

w.

Now, using the above expressions, a 1-to-4 demultiplexer can be implemented

using four 3-input AND gates and two NOT gates. Here, the input data line Din, is
connected to all the AND gates. The two select lines S1, S0 enable only one gate at a
time and the data that appears on the input line passes through the selected gate to
ww

the associated output line.

40

[Link]
[Link]

1-to-8 Demultiplexer
A 1-to-8 demultiplexer has a single input, Din, eight outputs (Y0 to Y7) and
three select inputs (S2, S1 and S0). It distributes one input line to eight output lines
based on the select inputs. The truth table of 1-to-8 demultiplexer is shown below.
Din S2 S1 S0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0
0 x x x 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 1 0

.in
1 0 1 0 0 0 0 0 0 1 0 0
1 0 1 1 0 0 0 0 1 0 0 0
1 1 0 0 0 0 0 1 0 0 0 0
1 1 0 1 0 0 1 0 0 0 0 0

ee
1 1 1 0 0 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0
Truth table of 1-to-8 demultiplexer
sfr
From the above truth table, it is clear that the data input is connected with one
of the eight outputs based on the select inputs. Now from this truth table, the
expression for eight outputs can be written as follows:
ote

Y0= S2’S1’S0’Din Y4= S2 S1’S0’Din

Y1= S2’S1’S0Din Y5= S2 S1’S0Din
Y2= S2’S1S0’Din Y6= S2 S1S0’Din
Y3= S2’S1S0Din Y7= S2S1S0Din
N

Now using the above expressions, the logic diagram of a 1-to-8 demultiplexer
w.

can be drawn as shown below. Here, the single data line, Din is connected to all the
eight AND gates, but only one of the eight AND gates will be enabled by the select
input lines. For example, if S2S1S0= 000, then only AND gate-0 will be enabled and
ww

thereby the data input, Din will appear at Y0. Similarly, the different combinations of
the select inputs, the input Din will appear at the respective output.

41

[Link]
[Link]

.in
ee
sfr
ote

Logic diagram of 1-to-8 demultiplexer

N

1. Design 1:8 demultiplexer using two 1:4 DEMUX.

w.
ww

42

[Link]
[Link]

2. Implement full subtractor using demultiplexer.

Inputs Outputs
A B Bin Difference(D) Borrow(Bout)
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0

.in
1 1 0 0 0
1 1 1 1 1

ee
sfr
N ote

Applications:
w.

1. It can be used as a decoder

2. It can be used as a data distributer
3. It is used in time division multiplexing at the receiving end as a data separator.
4. It can be used to implement Boolean expressions.
ww

43

[Link]
[Link]

DECODERS
A decoder is a combinational circuit that converts binary information from ‘n’
input lines to a maximum of ‘2n’ unique output lines. The general structure of
decoder circuit is

.in
General structure of decoder

ee
The encoded information is presented as ‘n’ inputs producing ‘2n’ possible
outputs. The 2n output values are from 0 through 2n-1. A decoder is provided with
enable inputs to activate decoded output based on data inputs. When any one enable
sfr
input is unasserted, all outputs of decoder are disabled.

Binary Decoder (2 to 4 decoder)

ote

A binary decoder has ‘n’ bit binary input and a one activated output out of 2n
outputs. A binary decoder is used when it is necessary to activate exactly one of 2 n
outputs based on an n-bit input value.
N
w.
ww

2-to-4 Line decoder

44

[Link]
[Link]

Here the 2 inputs are decoded into 4 outputs, each output representing one of
the minterms of the two input variables.

Inputs Outputs
Enable A B Y3 Y2 Y1 Y0
0 x x 0 0 0 0
1 0 0 0 0 0 1
1 0 1 0 0 1 0
1 1 0 0 1 0 0

.in
1 1 1 1 0 0 0
As shown in the truth table, if enable input is 1 (EN= 1) only one of the
outputs (Y0 – Y3), is active for a given input.
The output Y0 is active, ie., Y0= 1 when inputs A= B= 0,

ee
Y1 is active when inputs, A= 0 and B= 1,
Y2 is active, when input A= 1 and B= 0,
sfr
Y3 is active, when inputs A= B= 1.
3-to-8 Line Decoder
A 3-to-8 line decoder has three inputs (A, B, C) and eight outputs (Y0- Y7).
ote

Based on the 3 inputs one of the eight outputs is selected.

The three inputs are decoded into eight outputs, each output representing one
of the minterms of the 3-input variables. This decoder is used for binary-to-octal
conversion. The input variables may represent a binary number and the outputs will
represent the eight digits in the octal number system. The output variables are
N

mutually exclusive because only one output can be equal to 1 at any one time. The
output line whose value is equal to 1 represents the minterm equivalent of the binary
w.

number presently available in the input lines.

Inputs Outputs
A B C Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7
ww

0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1

45

[Link]
[Link]

.in
ee
sfr
ote

3-to-8 line decoder

N

BCD to 7-Segment Display Decoder

A seven-segment display is normally used for displaying any one of the
w.

decimal digits, 0 through 9. A BCD-to-seven segment decoder accepts a decimal digit

in BCD and generates the corresponding seven-segment code.
ww

Each segment is made up of a material that emits light when current is passed
through it. The segments activated during each digit display are tabulated as

46

[Link]
[Link]

Digit Display Segments Activated

0 a, b, c, d, e, f

1 b, c

.in
2 a, b, d, e, g

ee
3 sfr a, b, c, d, g

4 b, c, f, g
ote

5 a, c, d, f, g
N

6 a, c, d, e, f, g
w.

7 a, b, c
ww

8 a, b, c, d, e, f, g

9 a, b, c, d, f, g

47

[Link]
[Link]

Truth table:
BCD code 7-Segment code
Digit
A B C D a b c d e f g
0 0 0 0 0 1 1 1 1 1 1 0
1 0 0 0 1 0 1 1 0 0 0 0
2 0 0 1 0 1 1 0 1 1 0 1
3 0 0 1 1 1 1 1 1 0 0 1
4 0 1 0 0 0 1 1 0 0 1 1
5 0 1 0 1 1 0 1 1 0 1 1

.in
6 0 1 1 0 1 0 1 1 1 1 1
7 0 1 1 1 1 1 1 0 0 0 0
8 1 0 0 0 1 1 1 1 1 1 1

ee
9 1 0 0 1 1 1 1 1 0 1 1

K-map Simplification:
sfr
N ote
w.
ww

48

[Link]
[Link]

.in
ee
sfr
N ote
w.
ww

49

[Link]
[Link]

Logic Diagram

.in
ee
sfr
N ote
w.

BCD to 7-segment display decoder

Applications of decoders:
ww

1. Decoders are used in counter system.

2. They are used in analog to digital converter.
3. Decoder outputs can be used to drive a display system.
4. Address decoding
5. Implementation of combinational circuits.
6. Code converters.

50

[Link]
[Link]

ENCODERS
An encoder is a digital circuit that performs the inverse operation of a
decoder. Hence, the opposite of the decoding process is called encoding. An encoder
is a combinational circuit that converts binary information from 2 n input lines to a
maximum of ‘n’ unique output lines.
The general structure of encoder circuit is

.in
ee General structure of Encoder

It has 2n input lines, only one which 1 is active at any time and ‘n’ output lines.
sfr
It encodes one of the active inputs to a coded binary output with ‘n’ bits. In an
encoder, the number of outputs is less than the number of inputs.
ote

Octal-to-Binary Encoder

It has eight inputs (one for each of the octal digits) and the three outputs that
generate the corresponding binary number. It is assumed that only one input has a
N

value of 1 at any given time.

The encoder can be implemented with OR gates whose inputs are determined
directly from the truth table. Output z is equal to 1, when the input octal digit is 1 or
w.

3 or 5 or 7. Output y is 1 for octal digits 2, 3, 6, or 7 and the output is 1 for digits 4, 5,

6 or 7.
ww

Inputs Outputs
D0 D1 D2 D3 D4 D5 D6 D7 A B C
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 1 1
51

[Link]
[Link]

These conditions can be expressed by the following output Boolean functions:

z= D1+ D3+ D5+ D7
y= D2+ D3+ D6+ D7
x= D4+ D5+ D6+ D7
The encoder can be implemented with three OR gates. The encoder defined in
the below table, has the limitation that only one input can be active at any given time.
If two inputs are active simultaneously, output produces an undefined combination.

.in
For eg., if D3 and D6 are 1 simultaneously, the output of the encoder may be
111. This does not represent either D6 or D3. To resolve this problem, encoder circuits
must establish an input priority to ensure that only one input is encoded. If we
establish a higher priority for inputs with higher subscript numbers and if D3 and D6

ee
are 1 at the same time, the output will be 110 because D6 has higher priority than D3.
sfr
ote

Octal-to-Binary Encoder
N

Another problem in the octal-to-binary encoder is that an output with all 0’s is
generated when all the inputs are 0; this output is same as when D0 is equal to 1. The
w.

discrepancy can be resolved by providing one more output to indicate that atleast
one input is equal to 1.
ww

Priority Encoder
A priority encoder is an encoder circuit that includes the priority function. In
priority encoder, if two or more inputs are equal to 1 at the same time, the input
having the highest priority will take precedence.

In addition to the two outputs x and y, the circuit has a third output, V (valid
bit indicator). It is set to 1 when one or more inputs are equal to 1. If all inputs are 0,
there is no valid input and V is equal to 0.

52

[Link]
[Link]

The higher the subscript number, higher the priority of the input. Input D 3,
has the highest priority. So, regardless of the values of the other inputs, when D3 is 1,
the output for xy is 11.
D2 has the next priority level. The output is 10, if D2= 1 provided D3= 0. The
output for D1 is generated only if higher priority inputs are 0, and so on down the
priority levels.

Truth table:
Inputs Outputs

.in
D0 D1 D2 D3 x y V
0 0 0 0 x x 0
1 0 0 0 0 0 1
x 1 0 0 0 1 1

ee
x x 1 0 1 0 1
x x x 1 1 1 1

Although the above table has only five rows, when each don’t care condition
sfr
is replaced first by 0 and then by 1, we obtain all 16 possible input combinations. For
example, the third row in the table with X100 represents minterms 0100 and 1100.
The don’t care condition is replaced by 0 and 1 as shown in the table below.
ote

Modified Truth table:

Inputs Outputs
D0 D1 D2 D3 x y V
0 0 0 0 x x 0
N

1 0 0 0 0 0 1
0 1 0 0
0 1 1
1 1 0 0
w.

0 0 1 0
0 1 1 0
1 0 1
1 0 1 0
1 1 1 0
ww

0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

53

[Link]
[Link]

K-map Simplification:

.in
ee
sfr
ote

The priority encoder is implemented according to the above Boolean functions.

N
w.
ww

4-Input Priority Encoder

54

[Link]
[Link]

MAGNITUDE COMPARATOR
A magnitude comparator is a combinational circuit that compares two given
numbers (A and B) and determines whether one is equal to, less than or greater than
the other. The output is in the form of three binary variables representing the
conditions A = B, A>B and A<B, if A and B are the two numbers being compared.

.in
Block diagram of magnitude comparator

For comparison of two n-bit numbers, the classical method to achieve the

ee
Boolean expressions requires a truth table of 22n entries and becomes too lengthy and
cumbersome. sfr
2.8.1 2-bit Magnitude Comparator
The truth table of 2-bit comparator is given in table below
Truth table:
ote

Inputs Outputs
A1 A0 B1 B0 A>B A=B A<B
0 0 0 0 0 1 0
0 0 0 1 0 0 1
N

0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 0 1 0 0
w.

0 1 0 1 0 1 0
0 1 1 0 0 0 1
0 1 1 1 0 0 1
ww

1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 0 1 0
1 0 1 1 0 0 1
1 1 0 0 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 1 0

55

[Link]
[Link]

K-map Simplification:

.in
ee
sfr
N ote
w.
ww

56

[Link]
[Link]

Logic Diagram:

.in
ee
sfr
N ote

2-bit Magnitude Comparator

w.

4-bit Magnitude Comparator:

Let us consider the two binary numbers A and B with four digits each. Write
the coefficient of the numbers in descending order as,
ww

A = A3A2A1A0
B = B3 B2 B1 B0,
Each subscripted letter represents one of the digits in the number. It is
observed from the bit contents of two numbers that A = B when A 3 = B3, A2 = B2, A1
= B1 and A0 = B0. When the numbers are binary they possess the value of either 1 or 0,
the equality relation of each pair can be expressed logically by the equivalence
function as,

57

[Link]
[Link]

Xi = AiBi + Ai′Bi′ for i = 1, 2, 3, 4.

Or, Xi = (A  B)′. or, Xi ′ = A  B
Or, Xi = (AiBi′ + Ai′Bi)′.
where, Xi =1 only if the pair of bits in position i are equal (ie., if both are 1 or both
are 0).
To satisfy the equality condition of two numbers A and B, it is necessary that
all Xi must be equal to logic 1. This indicates the AND operation of all Xi variables.

.in
In other words, we can write the Boolean expression for two equal 4-bit numbers.
(A = B) = X3X2X1 X0.
The binary variable (A=B) is equal to 1 only if all pairs of digits of the two numbers

ee
are equal.
To determine if A is greater than or less than B, we inspect the relative
magnitudes of pairs of significant bits starting from the most significant bit. If the
sfr
two digits of the most significant position are equal, the next significant pair of digits
is compared. The comparison process is continued until a pair of unequal digits is
found. It may be concluded that A>B, if the corresponding digit of A is 1 and B is 0.
ote

If the corresponding digit of A is 0 and B is 1, we conclude that A<B. Therefore, we

can derive the logical expression of such sequential comparison by the following two
Boolean functions,

(A>B) = A3B3′ +X3A2B2′ +X3X2A1B1′ +X3X2X1A0B0′

N

(A<B) = A3′B3 +X3A2′B2 +X3X2A1′B1 +X3X2X1A0′B0

The symbols (A>B) and (A<B) are binary output variables that are equal to 1
w.

when A>B or A<B, respectively.

The gate implementation of the three output variables just derived is simpler
than it seems because it involves a certain amount of repetition. The unequal outputs
ww

can use the same gates that are needed to generate the equal output. The logic
diagram of the 4-bit magnitude comparator is shown below,

58

[Link]
[Link]

.in
ee
sfr
ote

4-bit Magnitude Comparator

The four x outputs are generated with exclusive-NOR circuits and applied to
N

an AND gate to give the binary output variable (A=B). The other two outputs use
the x variables to generate the Boolean functions listed above. This is a multilevel
w.

implementation and has a regular pattern.

ww

59

[Link]
[Link]

INTRODUCTION

e
In combinational logic circuits, the outputs at any instant of time depend
fre
only on the input signals present at that time. For any change in input, the output
occurs immediately.
tes
No

Combinational Circuit- Block Diagram

In sequential logic circuits, it consists of combinational circuits to which

storage elements are connected to form a feedback path. The storage elements are
devices capable of storing binary information either 1 or 0.
w.

The information stored in the memory elements at any given time defines the
present state of the sequential circuit. The present state and the external circuit
ww

determine the output and the next state of sequential circuits.

Sequential Circuit- Block Diagram

Thus in sequential circuits, the output variables depend not only on the
1

[Link]
[Link]

The rotary channel selected knob on an old-fashioned TV is like a

combinational. Its output selects a channel based only on its current input – the
position of the knob. The channel-up and channel-down push buttons on a TV is like
a sequential circuit. The channel selection depends on the past sequence of up/down
pushes.
The comparison between combinational and sequential circuits is given in
table below.

n
[Link] Combinational logic Sequential logic
The output variable, at all times The output variable depends not only

e.i
1 depends on the combination of on the present input but also depend
input variables. upon the past history of inputs.
Memory unit is required to store the
2

3
fre
Memory unit is not required.

Faster in speed.
past history of input variables.
Slower than combinational circuits.
4 Easy to design. Comparatively harder to design.
tes
Eg. Adder, subtractor, Decoder,
5 Eg. Shift registers, Counters
Encoders, Magnitude comparator
No

CLASSIFICATION OF LOGIC CIRCUITS

w.
ww

The sequential circuits can be classified depending on the timing of their

signals:
 Synchronous sequential circuits
 Asynchronous sequential circuits.
3

[Link]
[Link]

[Link] Synchronous sequential circuits Asynchronous sequential circuits

Memory elements are either unclocked
1 Memory elements are clocked
flip-flops (Latches) or time delay
Flip-Flops.
elements.
The change in input signals can The change in input signals can affect
2 affect memory element upon memory element at any instant of
activation of clock signal. time.
The maximum operating speed of Because of the absence of clock, it can
3 clock depends on time delays operate faster than synchronous

n
involved. circuits.
4 Easier to design More difficult to design

e.i
TRIGGERING OF FLIP-FLOPS

fre
The state of a Flip-Flop is switched by a momentary change in the input signal.
This momentary change is called a trigger and the transition it causes is said to
trigger the Flip-Flop. Clocked Flip-Flops are triggered by pulses. A clock pulse starts
tes
from an initial value of 0, goes momentarily to 1and after a short time, returns to its
initial 0 value.
Latches are controlled by enable signal, and they are level triggered, either
positive level triggered or negative level triggered. The output is free to change
No

according to the S and R input values, when active level is maintained at the enable
input.
w.
ww

[Link]
[Link]

EDGE TRIGGERED FLIP-FLOPS

Flip-Flops are synchronous bistable devices (has two outputs Q and Q’). In
this case, the term synchronous means that the output changes state only at a
specified point on the triggering input called the clock (CLK), i.e., changes in the
output occur in synchronization with the clock.
An edge-triggered Flip-Flop changes state either at the positive edge (rising
edge) or at the negative edge (falling edge) of the clock pulse and is sensitive to its

n
inputs only at this transition of the clock. The different types of edge-triggered Flip-

e.i
Flops are—
S-R Flip-Flop (Set – Reset)
J-K Flip-Flop (Jack Kilby)
fre
D Flip-Flop
T Flip-Flop
(Delay)
(Toggle)
Although the S-R Flip-Flop is not available in IC form, it is the basis for the D
tes
and J-K Flip-Flops. Each type can be either positive edge-triggered (no bubble at C
input) or negative edge-triggered (bubble at C input).
The key to identifying an edge- triggered Flip-Flop by its logic symbol is the
small triangle inside the block at the clock (C) input. This triangle is called the
No

dynamic input indicator.

S-R Flip-Flop
w.

The S and R inputs of the S-R Flip-Flop are called synchronous inputs because
data on these inputs are transferred to the Flip-Flop's output only on the triggering
edge of the clock pulse. The circuit is similar to SR latch except enable signal is
ww

replaced by clock pulse (CLK). On the positive edge of the clock pulse, the circuit
responds to the S and R inputs.

[Link]
[Link]

SR Flip-Flop

When S is HIGH and R is LOW, the Q output goes HIGH on the triggering

n
edge of the clock pulse, and the Flip-Flop is SET. When S is LOW and R is HIGH, the

e.i
Q output goes LOW on the triggering edge of the clock pulse, and the Flip-Flop is
RESET. When both S and R are LOW, the output does not change from its prior state.
An invalid condition exists when both S and R are HIGH.
fre
CLK
1
S
0
R
0
Qn
0
Qn+1
0
State

No Change (NC)
1 0 0 1 1
tes
1 0 1 0 0
Reset
1 0 1 1 0
1 1 0 0 1
Set
1 1 0 1 1
No

1 1 1 0 x Indeterminate
1 1 1 1 x *

Truth table for SR Flip-Flop

w.

The timing diagram of positive edge triggered SR flip-flop is shown below.

ww

Input and output waveforms of SR Flip-Flop

[Link]
[Link]

Characteristic table and Characteristic equation:

The characteristic table for JK Flip-Flop is shown in the table below. From the
table, K-map for the next state transition (Qn+1) can be drawn and the simplified logic
expression which represents the characteristic equation of JK Flip-Flop can be found.

S R Qn Qn+1
0 0 0 0
0 0 1 1
0 1 0 0

n
0 1 1 0
1 0 0 1

e.i
1 0 1 1
1 1 0 x
1 1 1 x
Characteristic table

fre
K-map Simplification:
tes
Characteristic equation:
Qn+1= S+ R’Qn
No

J-K Flip-Flop:
JK means Jack Kilby, Texas Instrument (TI) Engineer, who invented IC in 1958.
JK Flip-Flop has two inputs J(set) and K(reset). A JK Flip-Flop can be obtained from
w.

the clocked SR Flip-Flop by augmenting two AND gates as shown below.

ww

JK Flip Flop

[Link]
[Link]

The data input J and the output Q’ are applied o the first AND gate and its
output (JQ’) is applied to the S input of SR Flip-Flop. Similarly, the data input K and
the output Q are applied to the second AND gate and its output (KQ) is applied to
the R input of SR Flip-Flop.

n
e.i
J= K= 0
When J=K= 0, both AND gates are disabled. Therefore clock pulse have no

J= 0, K= 1
fre
effect, hence the Flip-Flop output is same as the previous output.

When J= 0 and K= 1, AND gate 1 is disabled i.e., S= 0 and R= 1. This condition

will reset the Flip-Flop to 0.
tes
J= 1, K= 0
When J= 1 and K= 0, AND gate 2 is disabled i.e., S= 1 and R= 0. Therefore the
Flip-Flop will set on the application of a clock pulse.
No

J= K= 0
When J=K= 1, it is possible to set or reset the Flip-Flop. If Q is High, AND
gate 2 passes on a reset pulse to the next clock. When Q is low, AND gate 1 passes on
a set pulse to the next clock. Eitherway, Q changes to the complement of the last
w.

state i.e., toggle. Toggle means to switch to the opposite state.

Truth table:
ww

Inputs Output
CLK State
J K Qn+1
1 0 0 Qn No Change
1 0 1 0 Reset
1 1 0 1 Set
1 1 1 Q n’ Toggle

[Link]
[Link]

The timing diagram of negative edge triggered JK flip-flop is shown below.

n
Input and output waveforms of JK Flip-Flop

e.i
Characteristic table and Characteristic equation:
The characteristic table for JK Flip-Flop is shown in the table below. From the
fre
table, K-map for the next state transition (Qn+1) can be drawn and the simplified logic
expression which represents the characteristic equation of JK Flip-Flop can be found.
Qn J K Qn+1
tes
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 1
No

1 0 1 0
1 1 0 1
1 1 1 0
Characteristic table
w.

K-map Simplification:
ww

Characteristic equation:
Qn+1= JQ’+ K’Q

[Link]
[Link]

D Flip-Flop:
Like in D latch, in D Flip-Flop the basic SR Flip-Flop is used with
complemented inputs. The D Flip-Flop is similar to D-latch except clock pulse is
used instead of enable input.

n
e.i
D Flip-Flop

fre
To eliminate the undesirable condition of the indeterminate state in the RS Flip-
Flop is to ensure that inputs S and R are never equal to 1 at the same time. This is
done by D Flip-Flop. The D (delay) Flip-Flop has one input called delay input and clock
pulse input.
tes
The D Flip-Flop using SR Flip-Flop is shown below.
No

Truth Table:
w.

The truth table of D Flip-Flop is given below.

Clock D Qn+1 State
ww

1 0 0 Reset
1 1 1 Set
0 x Qn No Change

Truth table for D Flip-Flop

[Link]
[Link]

The timing diagram of positive edge triggered D flip-flop is shown below.

Input and output waveforms of clocked D Flip-Flop

Looking at the truth table for D Flip-Flop we can realize that Qn+1 function

n
follows the D input at the positive going edges of the clock pulses.

e.i
Characteristic table and Characteristic equation:
The characteristic table for D Flip-Flop shows that the next state of the Flip-

fre
Flop is independent of the present state since Qn+1 is equal to D. This means that an
input pulse will transfer the value of input D into the output of the Flip-Flop
independent of the value of the output before the pulse was applied.
The characteristic equation is derived from K-map.
tes
Qn D Qn+1
0 0 0
0 1 1
No

1 0 0
1 1 1
Characteristic table
K-map Simplification:
w.
ww

Characteristic equation:
Qn+1= D.

10

[Link]
[Link]

T Flip-Flop
The T (Toggle) Flip-Flop is a modification of the JK Flip-Flop. It is obtained
from JK Flip-Flop by connecting both inputs J and K together, i.e., single input.
Regardless of the present state, the Flip-Flop complements its output when the clock
pulse occurs while input T= 1.

n
e.i
fre T Flip-Flop

When T= 0, Qn+1= Qn, ie., the next state is the same as the present state and no
change occurs.
tes
When T= 1, Qn+1= Qn’,ie., the next state is the complement of the present state.
No
w.

Truth Table:
The truth table of T Flip-Flop is given below.
T Qn+1 State
ww

0 Qn No Change
1 Q n’ Toggle

Truth table for T Flip-Flop

Characteristic table and Characteristic equation:

The characteristic table for T Flip-Flop is shown below and characteristic
equation is derived using K-map.

11

[Link]
[Link]

Qn T Qn+1
0 0 0
0 1 1
1 0 1
1 1 0
K-map Simplification:

n
e.i
Characteristic equation:
Qn+1= TQn’+ T’Qn

fre
Master-Slave JK Flip-Flop
A master-slave Flip-Flop consists of clocked JK flip-flop as a master and
clocked SR flip-flop as a slave. The output of the master flip-flop is fed as an input to
tes
the slave flip-flop. Clock signal is connected directly to the master flip-flop, but is
connected through inverter to the slave flip-flop. Therefore, the information present
at the J and K inputs is transmitted to the output of master flip-flop on the positive
No

clock pulse and it is held there until the negative clock pulse occurs, after which it is
allowed to pass through to the output of slave flip-flop. The output of the slave flip-
flop is connected as a third input of the master JK flip-flop.
w.
ww

Logic diagram

When J= 1 and K= 0, the master sets on the positive clock. The high Y
output of the master drives the S input of the slave, so at negative clock, slave sets,
copying the action of the master.

12

[Link]
[Link]

When J= 0 and K= 1, the master resets on the positive clock. The high Y’
output of the master goes to the R input of the slave. Therefore, at the negative clock
slave resets, again copying the action of the master.
When J= 1 and K= 1, master toggles on the positive clock and the output of
master is copied by the slave on the negative clock. At this instant, feedback inputs
to the master flip-flop are complemented, but as it is negative half of the clock pulse,
master flip-flop is inactive. This prevents race around condition.

n
The clocked master-slave J-K Flip-Flop using NAND gate is shown below.

e.i
fre
tes

Master-Slave JK Flip-Flop
No

The input and output waveforms of master-slave JK flip-flop is shown below.

w.
ww

Input and output waveform of master-slave flip-flop

13

[Link]
[Link]

APPLICATION TABLE (OR) EXCITATION TABLE:

The characteristic table is useful for analysis and for defining the operation
of the Flip-Flop. It specifies the next state (Qn+1) when the inputs and present state
are known.
The excitation or application table is useful for design process. It is used to
find the Flip-Flop input conditions that will cause the required transition, when the
present state (Qn) and the next state (Qn+1) are known.

n
SR Flip- Flop:

e.i
Present
Inputs Next State Present Next
State Inputs Inputs
State State
Qn S R Qn+1
0
0
fre
0
0
0
1
0
0
Qn
0
Qn+1
0
S
0
R
0
S

0
R

x
0 0 0 1
0 1 0 1
tes
0 1 1 0 1 0
0 1 1 x
1 0 0 1 0 1
1 0 0 1
1 1 0 0
1 0 1 0 x 0
No

1 1 1 0
1 1 0 1
1 1 1 x Modified Table

Characteristic Table
w.

Present Next
Inputs
State State
Qn Qn+1 S R
ww

0 0 0 x
0 1 1 0
1 0 0 1
1 1 x 0
Excitation Table

14

[Link]
[Link]

The above table presents the excitation table for SR Flip-Flop. It consists of
present state (Qn), next state (Qn+1) and a column for each input to show how the
required transition is achieved.
There are 4 possible transitions from present state to next state. The required
Input conditions for each of the four transitions are derived from the information
available in the characteristic table. The symbol ‘x’ denotes the don’t care condition;
it does not matter whether the input is 0 or 1.

n
JK Flip-Flop:

e.i
Present Next Present Next
Inputs Inputs Inputs
State State State State
Qn J K Qn+1 Qn Qn+1 J K J K
0
0
fre0
0
0
1
0
0
0
0
0
0
0
0
0
1
0 x

0 1 0 1 0 1 1 0
tes
1 x
0 1 1 1 0 1 1 1
1 0 0 1 1 0 0 1
x 1
1 0 1 0 1 0 1 1
No

1 1 0 1 1 1 0 0
x 0
1 1 1 0 1 1 1 0

Characteristic Table Modified Table

w.

Present Next
Inputs
State State
Qn Qn+1 J K
ww

0 0 0 x
0 1 1 x
1 0 x 1
1 1 x 0

Excitation Table

15

[Link]
[Link]

D Flip-Flop:

Present Next Present Next

Input Input
State State State State
Qn D Qn+1 Qn Qn+1 D
0 0 0 0 0 0
0 1 1 0 1 1
1 0 0

n
1 0 0
1 1 1 1 1 1

e.i
Characteristic Table Excitation Table

T Flip-Flop:
Present Next
Present Next

Qn
fre
State
Input

T
State
Qn+1
State
Qn
State
Qn+1
Input

0 0 0 0 0 0
tes
0 1 1 0 1 1

1 0 1 1 0 1

1 1 0 1 1 0
No

Characteristic Table Excitation Table

REALIZATION OF ONE FLIP-FLOP USING OTHER FLIP-FLOPS

It is possible to convert one Flip-Flop into another Flip-Flop with some
w.

additional gates or simply doing some extra connection. The realization of one Flip-
Flop using other Flip-Flops is implemented by the use of characteristic tables and
excitation tables. Let us see few conversions among Flip-Flops.
ww

SR Flip-Flop to D Flip-Flop
SR Flip-Flop to JK Flip-Flop
SR Flip-Flop to T Flip-Flop
JK Flip-Flop to T Flip-Flop
JK Flip-Flop to D Flip-Flop
D Flip-Flop to T Flip-Flop
T Flip-Flop to D Flip-Flop
16

[Link]
[Link]

SR Flip-Flop to D Flip-Flop:
 Write the characteristic table for required Flip-Flop (D Flip-Flop).
 Write the excitation table for given Flip-Flop (SR Flip-Flop).
 Determine the expression for given Flip-Flop inputs (S & R) by using K- map.
 Draw the Flip-Flop conversion logic diagram to obtain the required flip- flop
(D Flip-Flop) by using the above obtained expression.

The excitation table for the above conversion is

n
Required Flip-Flop Given Flip-Flop
(D) (SR)

e.i
Input Present state Next state Flip-Flop Inputs
D Qn Qn+1 S R
0 0 0 0 x
0 1 0 0 1
fre
1
1
0
1
1
1
1
x
0
0
tes
No

SR to D Flip-Flop
w.

SR Flip-Flop to JK Flip-Flop
The excitation table for the above conversion is, Qn

Inputs Present state Next state Flip-Flop Inputs

ww

J K Qn Qn+1 S R
0 0 0 0 0 x
0 0 1 1 x 0
0 1 0 0 0 x
0 1 1 0 0 1
1 0 0 1 1 0
1 0 1 1 x 0
1 1 0 1 1 0
1 1 1 0 0 1

17
[Link]
[Link]

n
e.i
fre SR to JK Flip-Flop

SR Flip-Flop to T Flip-Flop
tes
The excitation table for the above conversion is
Flip-Flop
Input Present state Next state
Inputs
T Qn Qn+1 S R
No

0 0 0 0 x
0 1 1 x 0
1 0 1 1 0
1 1 0 0 1
w.
ww

SR to T Flip-Flop

18
[Link]
[Link]

JK Flip-Flop to T Flip-Flop
The excitation table for the above conversion is

Input Present state Next state Flip-Flop Inputs

T Qn Qn+1 J K
0 0 0 0 x
0 1 1 x 0
1 0 1 1 x
1 1 0 x 1

n
e.i
fre
JK to T Flip-Flop
tes
JK Flip-Flop to D Flip-Flop
The excitation table for the above conversion is
No

Input Present state Next state Flip-Flop Inputs

D Qn Qn+1 J K
0 0 0 0 x
0 1 0 x 1
w.

1 0 1 1 x
1 1 1 x 0
ww

JK to D Flip-Flop

19
[Link]
[Link]

D Flip-Flop to T Flip-Flop
The excitation table for the above conversion is

Input Present state Next state Flip-Flop Input

T Qn Qn+1 D
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 0

n
e.i
fre D to T Flip-Flop
tes
T Flip-Flop to D Flip-Flop
The excitation table for the above conversion is
Flip-Flop
Input Present state Next state
No

Input
D Qn Qn+1 T
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0
w.
ww

T to D Flip-Flop

20
[Link]
[Link]

CLASSIFICATION OF SYNCHRONOUS SEQUENTIAL CIRCUIT:

In synchronous or clocked sequential circuits, clocked Flip-Flops are used as
memory elements, which change their individual states in synchronism with the
periodic clock signal. Therefore, the change in states of Flip-Flop and change in state
of the entire circuits occur at the transition of the clock signal.
The synchronous or clocked sequential networks are represented by two models.
Moore model: The output depends only on the present state of the Flip-Flops.

n
Mealy model: The output depends on both the present state of the Flip-Flops
and on the inputs.

e.i
Moore model:

fre
In the Moore model, the outputs are a function of the present state of the Flip-
Flops only. The output depends only on present state of Flip-Flops, it appears only
after the clock pulse is applied, i.e., it varies in synchronism with the clock input.
tes
No

Moore model

Mealy model:
In the Mealy model, the outputs are functions of both the present state of the
w.

Flip-Flops and inputs.

ww

Mealy model

21
[Link]
[Link]

Difference between Moore and Mealy model

[Link] Moore model Mealy model
1 Its output is a function of present Its output is a function of present state
state only. as well as present input.
2 An input change does not affect the Input changes may affect the output of
output. the circuit.
3 It requires more number of states It requires less number of states for

n
for implementing same function. implementing same function.

e.i
ANALYSIS OF SYNCHRONOUS SEQUENTIAL CIRCUIT:

fre
ANALYSIS PROCEDURE:
The synchronous sequential circuit analysis is summarizes as given below:
1. Assign a state variable to each Flip-Flop in the synchronous sequential circuit.
tes
2. Write the excitation input functions for each Flip-Flop and also write the
Moore/ Mealy output equations.
3. Substitute the excitation input functions into the bistable equations for the
Flip-Flops to obtain the next state output equations.
No

4. Obtain the state table and reduced form of the state table.
5. Draw the state diagram by using the second form of the state table.
w.

ANALYSIS OF MEALY MODEL:

1. A sequential circuit has two JK Flip-Flops A and B, one input (x) and one output
(y). the Flip-Flop input functions are,
ww

JA= B+ x JB= A’+ x’

KA= 1 KB= 1
and the circuit output function, Y= xA’B.
a) Draw the logic diagram of the Mealy circuit,
b) Tabulate the state table,
c) Draw the state diagram.

22
[Link]
[Link]

Logic Diagram:

n
e.i
State table:

Present state
freInput Flip-Flop Inputs Next state Output

A B x JA= B+ x KA= 1 JB= A’+ x’ KB= 1 A(t+1) B(t+1) Y= xA’B

tes
0 0 0 0 1 1 1 0 1 0
0 0 1 1 1 1 1 1 1 0
0 1 0 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 0 1
No

1 0 0 0 1 1 1 0 1 0
1 0 1 1 1 0 1 0 0 0
1 1 0 1 1 1 1 0 0 0
1 1 1 1 1 0 1 0 0 0

Reduced State Table:

w.

Next state Output

Present state
x= 0 x= 1 x= 0 x= 1

A B A B A B y y
ww

0 0 0 1 1 1 0 0
0 1 1 0 1 0 0 1
1 0 0 1 0 0 0 0
1 1 0 0 0 0 0 0

23
[Link]
[Link]

State Diagram:

n
State Diagram

e.i
2. A sequential circuit with two ‘D’ Flip-Flops A and B, one input (x) and one
output (y). The Flip-Flop input functions are:
fre
DA= Ax+ Bx
DB= A’x
and the circuit output function is, Y= (A+ B) x’.
tes
(a) Draw the logic diagram of the circuit,
(b) Tabulate the state table,
(c) Draw the state diagram.
No

Soln:
w.
ww

24
[Link]
[Link]

State Table:

Present state Input Flip-Flop Inputs Next state Output

DA=
A B x DB= A’x A(t+1) B(t+1) Y= (A+B)x’
Ax+Bx
0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
0 1 0 0 0 0 0 1
0 1 1 1 1 1 1 0
1 0 0 0 0 0 0 1
1 0 1 1 0 1 0 0

n
1 1 0 0 0 0 0 1
1 1 1 1 0 1 0 0

e.i
Next state Output
Present state
x= 0 x= 1 x= 0 x= 1

A
0
0
1
fre B
0
1
0
A
0
0
0
B
0
0
0
A
0
1
1
B
1
1
0
Y
0
1
1
Y
0
0
0
1 1 0 0 1 0 1 0
tes
Second form of state table

State Diagram:
No
w.
ww

3. A sequential circuit has two JK Flip-Flop A and B. the Flip-Flop input functions
are: JA= B JB= x’
KA= Bx’ KB= A x.
(a) Draw the logic diagram of the circuit,
(b) Tabulate the state table,
(c) Draw the state diagram.
Soln:

25
[Link]
[Link]

Logic diagram:

n
e.i
The output function is not given in the problem. The output of the Flip-Flops
may be considered as the output of the circuit.

State table:
fre
Prese
Input Flip-Flop Inputs Next state
nt state
tes
A B x JA= B KA= Bx’ JB= x’ KB= Ax A(t+1) B(t+1)
0 0 0 0 0 1 0 0 1
0 0 1 0 0 0 1 0 0
0 1 0 1 1 1 0 1 1
No

0 1 1 1 0 0 1 1 0
1 0 0 0 0 1 1 1 1
1 0 1 0 0 0 0 1 0
1 1 0 1 1 1 1 0 0
1 1 1 1 0 0 0 1 1
w.

Next state
Present state
X= 0 X= 1

A B A B A B
ww

0 0 0 1 0 0
0 1 1 1 1 0
1 0 1 1 1 0
1 1 0 0 1 1

26
[Link]
[Link]

State Diagram:

n
4. A sequential circuit has two JK Flop-Flops A and B, two inputs x and y and

e.i
one output z. The Flip-Flop input equation and circuit output equations are
JA = Bx + B' y' KA = B' xy'
JB = A' x KB = A+ xy'

(a)
fre
z = Ax' y' + Bx' y'
Draw the logic diagram of the circuit
(b) Tabulate the state table.
tes
(c) Derive the state equation.
Soln:
Logic diagram:
No
w.
ww

27
[Link]
[Link]

State table:
To obtain the next-state values of a sequential circuit with JK Flip-Flop, use
the JK Flip-Flop characteristic table,

Present state Input Flip-Flop Inputs Next state Output

JA= KA= JB = KB=
A B x y A(t+1) B(t+1) z
Bx+B’y’ B’xy’ A’x A+xy’
0 0 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 1 1 1 1 1 0

n
0 0 1 1 0 0 1 0 0 1 0
0 1 0 0 0 0 0 0 0 0 1

e.i
0 1 0 1 0 0 0 0 0 0 0
0 1 1 0 1 0 1 1 1 1 0
0 1 1 1 1 0 1 0 1 1 0
1 0 0 0 1 0 0 1 1 0 1
1
1
1
1
0
0
0
1
fre
0
1
1
0
1
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
0
0
0
1
1 1 0 1 0 0 0 1 1 0 0
tes
1 1 1 0 1 0 0 1 1 0 0
1 1 1 1 1 0 0 1 1 0 0
State Equation:
No
w.
ww

28
[Link]
[Link]

5. Analyze the synchronous Mealy machine and obtain its state diagram.

n
e.i
Soln:
fre
The given synchronous Mealy machine consists of two D Flip-Flops, one inputs and
one output. The Flip-Flop input functions are,
DA= Y1’Y2X’
tes
DB= X+ Y1’Y2
The circuit output function is, Z= Y1Y2X.

State Table:
No

Present state Input Flip-Flop Inputs Next state Output

Y1 Y2 X DA= Y1’Y2X’ DB= X+ Y1’Y2 Y1 (t+1) Y2 (t+1) Z= Y1Y2X

0 0 0 0 0 0 0 0
w.

0 0 1 0 1 0 1 0
0 1 0 1 1 1 1 0
0 1 1 0 1 0 1 0
1 0 0 0 0 0 0 0
ww

1 0 1 0 1 0 1 0
1 1 0 0 0 0 0 0
1 1 1 0 1 0 1 1

29
[Link]
[Link]

Reduced State Table:

Next state Output

Present state
X= 0 X= 1 X= 0 X= 1

Y1 Y2 Y1 Y2 Y1 Y2 Z Z
0 0 0 0 0 1 0 0
0 1 1 1 0 1 0 0
1 0 0 0 0 1 0 0
1 1 0 0 0 1 0 1

n
Second form of state table

State Diagram:

e.i
fre
tes
No

ANALYSIS OF MOORE MODEL:

6. Analyze the synchronous Moore circuit and obtain its state diagram.
w.
ww

30
[Link]
[Link]

Soln:
Using the assigned variable Y1 and Y2 for the two JK Flip-Flops, we can write
the four excitation input equations and the Moore output equation as follows:
JA= Y2X ; KA= Y2’
JB= X ; KB= X’ and output function, Z= Y1Y2’
State table:
Present state Input Flip-Flop Inputs Next state Output
Y1 Y2 X JA= Y2X KA= Y2’ JB= X KB= X’ Y1 (t+1) Y2 (t+1) Z= Y1Y2’

n
0 0 0 0 1 0 1 0 0 0
0 0 1 0 1 1 0 0 1 0

e.i
0 1 0 0 0 0 1 0 0 0
0 1 1 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 1
1 0 1 0 1 1 0 0 1 1
1
1
1
1
fre 0
1
0
1
0
0
0
1

Next state
1
0
1
1

Output
0
1
0
0

Present state
X= 0 X= 1
tes
Y
Y1 Y2 Y1 Y2 Y1 Y2
0 0 0 0 0 1 0
0 1 0 0 1 1 0
1 0 0 0 0 1 1
No

1 1 1 0 1 1 0
State Diagram:
Here the output depends on the present state only and is independent of the
input. The two values inside each circle separated by a slash are for the present state
w.

and output.
ww

31
[Link]
[Link]

7. A sequential circuit has two T Flip-Flop A and B. The Flip-Flop input functions
are:
TA= Bx TB = x
y= AB
(a) Draw the logic diagram of the circuit,
(b) Tabulate the state table,
(c) Draw the state diagram.

n
Soln:
Logic diagram:

e.i
fre
tes
No

State table:

Present state Input Flip-Flop Inputs Next state Output

A B x TA= Bx TB = x A (t+1) B (t+1) y= AB

w.

0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
0 1 0 0 0 0 1 0
0 1 1 1 1 1 0 0
ww

1 0 0 0 0 1 0 0
1 0 1 0 1 1 1 0
1 1 0 0 0 1 1 1
1 1 1 1 1 0 0 1

32
[Link]
[Link]

Reduced State Table:

Next state Output

Present state
x= 0 x= 1 x= 0 x= 1

A B A B A B y y
0 0 0 0 0 1 0 0
0 1 0 1 1 0 0 0
1 0 1 0 1 1 0 0
1 1 1 1 0 0 1 1

n
Second form of state table

e.i
State Diagram:

fre
tes
No

STATE REDUCTION/ MINIMIZATION

The state reduction is used to avoid the redundant states in the sequential
circuits. The reduction in redundant states reduces the number of required Flip-
w.

Flops and logic gates, reducing the cost of the final circuit.
The two states are said to be redundant or equivalent, if every possible set of
inputs generate exactly same output and same next state. When two states are
ww

equivalent, one of them can be removed without altering the input-output

relationship.
Since ‘n’ Flip-Flops produced 2n state, a reduction in the number of states may
result in a reduction in the number of Flip-Flops.
The need for state reduction or state minimization is explained with one
example.

33
[Link]
[Link]

Examples:
1. Reduce the number of states in the following state diagram and draw the
reduced state diagram.

n
e.i
State diagram
Step 1: Determine the state table for given state diagram
Next state Output
fre Present state

a
X= 0
b
X= 1
c
X= 0
0
X= 1
0
b d e 1 0
tes
c c d 0 1
d a d 0 0
e c d 0 1
No

State table

Step 2: Find equivalent states

From the above state table c and e generate exactly same next state and same
output for every possible set of inputs. The state c and e go to next states c and d and
w.

have outputs 0 and 1 for x=0 and x=1 respectively. Therefore state e can be removed
and replaced by c. The final reduced state table is shown below.
ww

Next state Output

Present state
X= 0 X= 1 X= 0 X= 1
a b c 0 0
b d c 1 0
c c d 0 1
d a d 0 0
Reduced state table

34
[Link]
[Link]

Step 3: Draw state diagram

n
Reduced state diagram

e.i
2. Reduce the number of states in the following state table and tabulate the reduced
state table.
fre
Present state

a
Next state
X= 0
a
X= 1
b
Output
X= 0
0
X= 1
0
b c d 0 0
tes
c a d 0 0
d e f 0 1
e a f 0 1
f g f 0 1
No

g a f 0 1
Soln:
From the above state table e and g generate exactly same next state and same
output for every possible set of inputs. The state e and g go to next states a and f and
w.

have outputs 0 and 1 for x=0 and x=1 respectively. Therefore state g can be removed
and replaced by e.
The reduced state table-1 is shown below.
ww

Next state Output

Present state
X= 0 X= 1 X= 0 X= 1
a a b 0 0
b c d 0 0
c a d 0 0
d e f 0 1
e a f 0 1
f e f 0 1

35
[Link]
[Link]

Now states d and f are equivalent. Both states go to the same next state (e, f) and
have same output (0, 1). Therefore one state can be removed; f is replaced by d.
The final reduced state table-2 is shown below.

Next state Output

Present state
X= 0 X= 1 X= 0 X= 1
a a b 0 0
b c d 0 0
c a d 0 0
d e d 0 1

n
e a d 0 1

e.i
Reduced state table-2

Thus 7 states are reduced into 5 states.

3. Determine a minimal state table equivalent furnished below

fre Present state

1
Next state
X= 0
1, 0
X= 1
1, 0
2 1, 1 6, 1
tes
3 4, 0 5, 0
4 1, 1 7, 0
5 2, 0 3, 0
6 4, 0 5, 0
7 2, 0 3, 0
No

Soln:
Next state Output
Present state
X= 0 X= 1 X= 0 X= 1
w.

1 1 1 0 0
2 1 6 1 1
3 4 5 0 0
4 1 7 1 0
ww

5 2 3 0 0
6 4 5 0 0
7 2 3 0 0
From the above state table, 5 and 7 generate exactly same next state and same
output for every possible set of inputs. The state 5 and 7 go to next states 2 and 3 and
have outputs 0 and 0 for x=0 and x=1 respectively. Therefore state 7 can be removed
and replaced by 5.

36
[Link]
[Link]

Similarly, 3 and 6 generate exactly same next state and same output for every
possible set of inputs. The state 3 and 6 go to next states 4 and 5 and have outputs 0
and 0 for x=0 and x=1 respectively. Therefore state 6 can be removed and replaced
by 3. The final reduced state table is shown below.

Next state Output

Present state
X= 0 X= 1 X= 0 X= 1
1 1 1 0 0
2 1 3 1 1

n
3 4 5 0 0
4 1 5 1 0

e.i
5 2 3 0 0
Reduced state table

Thus 7 states are reduced into 5 states.

fre
4. Minimize the following state table.
Next state
Present state
tes
X= 0 X= 1
A D, 0 C, 1
B E, 1 A, 1
C H, 1 D, 1
D D, 0 C, 1
No

E B, 0 G, 1
F H, 1 D, 1
G A, 0 F, 1
H C, 0 A, 1
I G, 1 H,1
w.

Soln:
Next state Output
Present state
X= 0 X= 1 X= 0 X= 1
ww

A D C 0 1
B E A 1 1
C H D 1 1
D D C 0 1
E B G 0 1
F H D 1 1
G A F 0 1
H C A 0 1
I G H 1 1

37
[Link]
[Link]

From the above state table, A and D generate exactly same next state and
same output for every possible set of inputs. The state A and D go to next states D
and C and have outputs 0 and 1 for x=0 and x=1 respectively. Therefore state D can
be removed and replaced by A. Similarly, C and F generate exactly same next state
and same output for every possible set of inputs. The state C and F go to next states
H and D and have outputs 1 and 1 for x=0 and x=1 respectively. Therefore state F
can be removed and replaced by C.
Next state Output
Present state

n
X= 0 X= 1 X= 0 X= 1
A A C 0 1

e.i
B E A 1 1
C H A 1 1
E B G 0 1
G A C 0 1
fre H
I
C
G
A
H
Reduced state table-1
0
1
1
1

From the above reduced state table-1, A and G generate exactly same next
state and same output for every possible set of inputs. The state A and G go to next
tes
states A and C and have outputs 0 and 1 for x=0 and x=1 respectively. Therefore
state G can be removed and replaced by A.
The final reduced state table-2 is shown below.
No

Next state Output

Present state
X= 0 X= 1 X= 0 X= 1
A A C 0 1
B E A 1 1
w.

C H A 1 1
E B A 0 1
H C A 0 1
I A H 1 1
Reduced state table-2
ww

Thus 9 states are reduced into 6 states.

38
[Link]
[Link]

5. Reduce the following state diagram.

n
e.i
Soln:
Next state Output
frePresent state
a
b
X= 0
a
c
X= 1
b
d
X= 0
0
0
X= 1
0
0
c a d 0 0
tes
d e f 0 1
e a f 0 1
f g f 0 1
g a f 0 1
State table
No

From the above state table e and g generate exactly same next state and same
output for every possible set of inputs. The state e and g go to next states a and f and
have outputs 0 and 1 for x=0 and x=1 respectively. Therefore state g can be removed
w.

and replaced by e. The reduced state table-1 is shown below.

Present state Next state Output

X= 0 X= 1 X= 0 X= 1
ww

a a b 0 0
b c d 0 0
c a d 0 0
d e f 0 1
e a f 0 1
f e f 0 1
Reduced state table-1

Now states d and f are equivalent. Both states go to the same next state (e, f)
and have same output (0, 1). Therefore one state can be removed; f is replaced by d.

39
[Link]
[Link]

The final reduced state table-2 is shown below.

Present state Next state Output

X= 0 X= 1 X= 0 X= 1
a a b 0 0
b c d 0 0
c a d 0 0
d e d 0 1
e a d 0 1
Reduced state table-2

n
Thus 7 states are reduced into 5 states.
The state diagram for the reduced state table-2 is,

e.i
fre
tes
No

Reduced state diagram

DESIGN OF SYNCHRONOUS SEQUENTIAL CIRCUITS:

w.

A synchronous sequential circuit is made up of number of Flip-Flops and

combinational gates. The design of circuit consists of choosing the Flip-Flops and
then finding a combinational gate structure together with the Flip-Flops. The
ww

number of Flip-Flops is determined from the number of states needed in the circuit.
The combinational circuit is derived from the state table.

Design procedure:
1. The given problem is determined with a state diagram.
2. From the state diagram, obtain the state table.
3. The number of states may be reduced by state reduction methods (if applicable).

40
[Link]
[Link]

4. Assign binary values to each state (Binary Assignment) if the state table
contains letter symbols.
5. Determine the number of Flip-Flops and assign a letter symbol (A, B, C,…) to
each.
6. Choose the type of Flip-Flop (SR, JK, D, T) to be used.
7. From the state table, circuit excitation and output tables.
8. Using K-map or any other simplification method, derive the circuit output

n
functions and the Flip-Flop input functions.
9. Draw the logic diagram.

e.i
fre
tes
No

The type of Flip-Flop to be used may be included in the design specifications

or may depend what is available to the designer. Many digital systems are
constructed with JK Flip-Flops because they are the most versatile available. The
selection of inputs is given as follows.
w.

Flip-Flop Application
JK General Applications
ww

D Applications requiring transfer of data

(Ex: Shift Registers)
Application involving complementation
T (Ex: Binary Counters)

41
[Link]
[Link]

3.10.2 Excitation Tables:

Before going to the design examples for the clocked synchronous sequential
circuits we revise Flip-Flop excitation tables.
Present Next
Inputs
State State
Qn Qn+1 S R
0 0 0 x
0 1 1 0
1 0 0 1
1 1 x 0

n
Excitation table for SR Flip-Flop

e.i
Present Next
Inputs
State State
Qn Qn+1 J K
0
0
1
1
fre
0
1
0
1
0
1
x
x
x
x
1
0
Excitation table for JK Flip-Flop
tes
Present Next
Input
State State
Qn Qn+1 T
No

0 0 0
0 1 1
1 0 1
1 1 0
Excitation table for T Flip-Flop
w.

Present Next
Input
State State
Qn Qn+1 D
ww

0 0 0
0 1 1
1 0 0
1 1 1
Excitation table for D Flip-Flop

42
[Link]
[Link]

Problems
1. Design a clocked sequential machine using JK Flip-Flops for the state diagram
shown in the figure. Use state reduction if possible. Make proper state
assignment.

n
e.i
Soln:
State Table:

Next state Output

frePresent state

a
b
X= 0
a
c
X= 1
b
b
X= 0
0
0
X= 1
0
0
c a b 0 1
tes
d a b 0 0
Reduced State Table:

Next state Output

Present state
No

X= 0 X= 1 X= 0 X= 1
a a b 0 0
b c b 0 0
c a b 0 1
w.

Binary Assignment:
Now each state is assigned with binary values. Since there are three states,
ww

number of Flip-Flops required is two and 2 binary numbers are assigned to the states.
a= 00; b= 0; and c= 10.

Reduced State Diagram

43

[Link]
[Link]

Excitation Table:

Present State Next State Inputs

Qn Qn+1 J K
0 0 0 x
0 1 1 x
1 0 x 1
1 1 x 0
Excitation table for JK Flip-Flop

n
Present
Input Next state Flip-Flop Inputs Output
state

e.i
X A B A B JA KA JB KB Y
0 0 0 0 0 0 x 0 x 0
1 0 0 0 1 0 x 1 x 0
0 0 1 1 0 1 x x 1 0
1
0
1
0
0
1
1
1
fre 1
0
0
1
0
0
0
x
1
0
1
x
0
x
x
x
x
1
1
x
x
0
1
x
0
x
x
x
0
0
1
x
1 1 1 x x x x x x x
tes
K-map Simplification:
No
w.
ww

With these Flip-Flop input functions and circuit output function we can draw
the logic diagram as follows.

44

[Link]
[Link]

n
e.i
2. Design a clocked sequential machine using T Flip-Flops for the following state

fre
diagram. Use state reduction if possible. Also use straight binary state
assignment.
tes
No

Soln:
w.

State Table:

Next state Output

Present state
X= 0 X= 1 X= 0 X= 1
ww

a a b 0 0
b d c 0 0
c a b 1 0
d b a 1 1

Even though a and c are having same next states for input X=0 and X=1, as
the outputs are not same state reduction is not possible.

45

[Link]
[Link]

State Assignment:
Use straight binary assignments as a= 00, b= 01, c= 10 and d= 11, the
transition table is,
Flip-Flop
Input Present state Next state Output
Inputs
X A B A B TA TB Y
0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0
0 1 0 0 0 1 0 1

n
0 1 1 0 1 1 0 1
1 0 0 0 1 0 1 0

e.i
1 0 1 1 0 1 1 0
1 1 0 0 1 1 1 0
1 1 1 0 0 1 1 1

fre
K-map simplification:
tes

With these Flip-Flop input functions and circuit output function we can draw
No

the logic diagram as follows.

Logic Diagram:
w.
ww

46

[Link]
[Link]

SHIFT REGISTERS:

A register is simply a group of Flip-Flops that can be used to store a binary

number. There must be one Flip-Flop for each bit in the binary number. For instance,
a register used to store an 8-bit binary number must have 8 Flip-Flops.
The Flip-Flops must be connected such that the binary number can be entered
(shifted) into the register and possibly shifted out. A group of Flip-Flops connected
to provide either or both of these functions is called a shift register.

n
The bits in a binary number (data) can be removed from one place to another

e.i
in either of two ways. The first method involves shifting the data one bit at a time in
a serial fashion, beginning with either the most significant bit (MSB) or the least
significant bit (LSB). This technique is referred to as serial shifting. The second

shifting.
fre
method involves shifting all the data bits simultaneously and is referred to as parallel

There are two ways to shift into a register (serial or parallel) and similarly two
ways to shift the data out of the register. This leads to the construction of four basic
tes
register types—
i. Serial in- serial out,
ii. Serial in- parallel out,
No

iii. Parallel in- serial out,

iv. Parallel in- parallel out.
w.

(i) Serial in- serial out (iii) Parallel in- serial out
ww

(iii) Serial in- parallel out (iv) Parallel in- parallel out

47

[Link]
[Link]

Serial-In Serial-Out Shift Register:

The serial in/serial out shift register accepts data serially, i.e., one bit at a time
on a single line. It produces the stored information on its output also in serial form.

n
Serial-In Serial-Out Shift Register

e.i
The entry of the four bits 1010 into the register is illustrated below, beginning
with the right-most bit. The register is initially clear. The 0 is put onto the data input

fre
line, making D=0 for FF0. When the first clock pulse is applied, FF0 is reset, thus
storing the 0.
Next the second bit, which is a 1, is applied to the data input, making D=1 for
tes
FF0 and D=0 for FF1 because the D input of FF1 is connected to the Q0 output. When
the second clock pulse occurs, the 1 on the data input is shifted into FF0, causing FF0
to set; and the 0 that was in FF0 is shifted into FFl.
The third bit, a 0, is now put onto the data-input line, and a clock pulse is
No

applied. The 0 is entered into FF0, the 1 stored in FF0 is shifted into FFl, and the 0
stored in FF1 is shifted into FF2.
The last bit, a 1, is now applied to the data input, and a clock pulse is applied.
w.

This time the 1 is entered into FF0, the 0 stored in FF0 is shifted into FFl, the 1 stored
in FF1 is shifted into FF2, and the 0 stored in FF2 is shifted into FF3. This completes
the serial entry of the four bits into the shift register, where they can be stored for
ww

any length of time as long as the Flip-Flops have dc power.

To get the data out of the register, the bits must be shifted out serially and
taken off the Q3 output. After CLK4, the right-most bit, 0, appears on the Q3 output.
When clock pulse CLK5 is applied, the second bit appears on the Q3 output.
Clock pulse CLK6 shifts the third bit to the output, and CLK7 shifts the fourth bit to
the output. While the original four bits are being shifted out, more bits can be shifted
in. All zeros are shown being shifted out, more bits can be shifted in.

48

[Link]
[Link]

Serial-In Parallel-Out Shift Register:

In this shift register, data bits are entered into the register in the same as
serial-in serial-out shift register. But the output is taken in parallel. Once the data are
stored, each bit appears on its respective output line and all bits are available
simultaneously instead of on a bit-by-bit.

n
e.i
Serial-In parallel-Out Shift Register
fre
Parallel-In Serial-Out Shift Register:
In this type, the bits are entered in parallel i.e., simultaneously into their
tes
respective stages on parallel lines.
A 4-bit parallel-in serial-out shift register is illustrated below. There are four
data input lines, X0, X1, X2 and X3 for entering data in parallel into the register.
No

SHIFT/ LOAD input is the control input, which allows four bits of data to load in
parallel into the register.
w.
ww

Parallel-In Serial-Out Shift Register

49

[Link]
[Link]

When SHIFT/LOAD is LOW, gates G1, G2, G3 and G4 are enabled, allowing
each data bit to be applied to the D input of its respective Flip-Flop. When a clock
pulse is applied, the Flip-Flops with D = 1 will set and those with D = 0 will reset,
thereby storing all four bits simultaneously.
When SHIFT/LOAD is HIGH, gates G1, G2, G3 and G4 are disabled and gates
G5, G6 and G7 are enabled, allowing the data bits to shift right from one stage to the
next. The OR gates allow either the normal shifting operation or the parallel data-

n
entry operation, depending on which AND gates are enabled by the level on the
SHIFT/LOAD input.

e.i
Parallel-In Parallel-Out Shift Register:
In this type, there is simultaneous entry of all data bits and the bits appear on
fre
parallel outputs simultaneously.
tes
No
w.

Parallel-In Parallel-Out Shift Register

ww

UNIVERSAL SHIFT REGISTERS:

If the register has shift and parallel load capabilities, then it is called a shift
register with parallel load or universal shift register. Shift register can be used for
converting serial data to parallel data, and vice-versa. If a parallel load capability is
added to a shift register, the data entered in parallel can be taken out in serial fashion
by shifting the data stored in the register.

50

[Link]
[Link]

The functions of universal shift register are:

1. A clear control to clear the register to 0.
2. A clock input to synchronize the operations.
3. A shift-right control to enable the shift right operation and the serial input
and output lines associated with the shift right.
4. A shift-left control to enable the shift left operation and the serial input and
output lines associated with the shift left.

n
5. A parallel-load control to enable a parallel transfer and the n input lines
associated with the parallel transfer.

e.i
6. ‘n’ parallel output lines.
7. A control line that leaves the information in the register unchanged even
though the clock pulses re continuously applied.
fre
tes
No
w.
ww

4-Bit Universal Shift Register

It consists of four D-Flip-Flops and four 4 input multiplexers (MUX). S0 and S1
are the two selection inputs connected to all the four multiplexers. These two
selection inputs are used to select one of the four inputs of each multiplexer.

51

[Link]
[Link]

The input 0 in each MUX is selected when S1S0= 00 and input 1 is selected
when S1S0= 01. Similarly inputs 2 and 3 are selected when S1S0= 10 and S1S0= 11
respectively. The inputs S1 and S0 control the mode of the operation of the register.
When S1S0= 00, the present value of the register is applied to the D-inputs of
the Flip-Flops. This is done by connecting the output of each Flip-Flop to the 0 input
of the respective multiplexer. The next clock pulse transfers into each Flip-Flop, the
binary value is held previously, and hence no change of state occurs.

n
When S1S0= 01, terminal 1 of the multiplexer inputs has a path to the D inputs
of the Flip-Flops. This causes a shift-right operation with the lefter serial input

e.i
transferred into Flip-Flop FF3.
When S1S0= 10, a shift-left operation results with the right serial input going
into Flip-Flop FF1.
fre
Finally when S1S0= 11, the binary information on the parallel input lines (I1, I2,
I3 and I4) are transferred into the register simultaneously during the next clock pulse.
The function table of bi-directional shift register with parallel inputs and
tes
parallel outputs is shown below.
Mode Control
Operation
S1 S0
0 0 No change
No

0 1 Shift-right
1 0 Shift-left
1 1 Parallel load
w.

BI-DIRECTION SHIFT REGISTERS:

A bidirectional shift register is one in which the data can be shifted either left
or right. It can be implemented by using gating logic that enables the transfer of a
ww

data bit from one stage to the next stage to the right or to the left depending on the
level of a control line.
A 4-bit bidirectional shift register is shown below. A HIGH on the
RIGHT/LEFT control input allows data bits inside the register to be shifted to the
right, and a LOW enables data bits inside the register to be shifted to the left.

52

[Link]
[Link]

When the RIGHT/LEFT control input is HIGH, gates G1, G2, G3 and G4 are
enabled, and the state of the Q output of each Flip-Flop is passed through to the D
input of the following Flip-Flop. When a clock pulse occurs, the data bits are shifted
one place to the right.
When the RIGHT/LEFT control input is LOW, gates G5, G6, G7 and G8 are
enabled, and the Q output of each Flip-Flop is passed through to the D input of the
preceding Flip-Flop. When a clock pulse occurs, the data bits are then shifted one

n
place to the left.

e.i
fre
tes
No

4-bit bi-directional shift register

w.

SYNCHRONOUS COUNTERS:

Flip-Flops can be connected together to perform counting operations. Such a

ww

group of Flip- Flops is a counter. The number of Flip-Flops used and the way in
which they are connected determine the number of states (called the modulus) and
also the specific sequence of states that the counter goes through during each
complete cycle.

53

[Link]
[Link]

Counters are classified into two broad categories according to the way they
are clocked:
Asynchronous counters,
Synchronous counters.
In asynchronous (ripple) counters, the first Flip-Flop is clocked by the external
clock pulse and then each successive Flip-Flop is clocked by the output of the
preceding Flip-Flop.

n
In synchronous counters, the clock input is connected to all of the Flip-Flops
so that they are clocked simultaneously. Within each of these two categories,

e.i
counters are classified primarily by the type of sequence, the number of states, or the
number of Flip-Flops in the counter.
The term ‘synchronous’ refers to events that have a fixed time relationship
fre
with each other. In synchronous counter, the clock pulses are applied to all Flip-
Flops simultaneously. Hence there is minimum propagation delay.

[Link] Asynchronous (ripple) counter Synchronous counter

tes
1 All the Flip-Flops are not clocked All the Flip-Flops are clocked
simultaneously. simultaneously.
2 The delay times of all Flip-Flops There is minimum propagation delay.
are added. Therefore there is
No

considerable propagation delay.

3 Speed of operation is low Speed of operation is high.

4 Logic circuit is very simple even Design involves complex logic circuit
w.

for more number of states. as number of state increases.

5 Minimum numbers of logic The number of logic devices is more
devices are needed. than ripple counters.
6 Cheaper than synchronous Costlier than ripple counters.
ww

counters.

2-Bit Synchronous Binary Counter

In this counter the clock signal is connected in parallel to clock inputs of both
the Flip-Flops (FF0 and FF1). The output of FF0 is connected to J1 and K1 inputs of the
second Flip-Flop (FF1).
54

[Link]
[Link]

2-Bit Synchronous Binary Counter

n
Assume that the counter is initially in the binary 0 state: i.e., both Flip-Flops

e.i
are RESET. When the positive edge of the first clock pulse is applied, FF 0 will toggle
because J0= k0= 1, whereas FF1 output will remain 0 because J1= k1= 0. After the first
clock pulse Q0=1 and Q1=0.

fre
When the leading edge of CLK2 occurs, FF 0 will toggle and Q0 will go LOW.
Since FF1 has a HIGH (Q0 = 1) on its J1 and K1 inputs at the triggering edge of this
clock pulse, the Flip-Flop toggles and Q1 goes HIGH. Thus, after CLK2,
Q0 = 0 and Q1 = 1.
tes
When the leading edge of CLK3 occurs, FF0 again toggles to the SET state (Q0
= 1), and FF1 remains SET (Q1 = 1) because its J1 and K1 inputs are both LOW (Q0 = 0).
After this triggering edge, Q0 = 1 and Q1 = 1.
No

Finally, at the leading edge of CLK4, Q0 and Q1 go LOW because they both
have a toggle condition on their J1 and K1 inputs. The counter has now recycled to its
original state, Q0 = Q1 = 0.
w.
ww

Timing diagram

55

[Link]
 [Link]

3-Bit Synchronous Binary Counter

A 3 bit synchronous binary counter is constructed with three JK Flip-Flops
and an AND gate. The output of FF0 (Q0) changes on each clock pulse as the counter
progresses from its original state to its final state and then back to its original state.
To produce this operation, FF0 must be held in the toggle mode by constant HIGH,
on its J0 and K0 inputs.

n
e.i
3-
fre Bit Synchronous Binary Counter

The output of FF1 (Q1) goes to the opposite state following each time Q0= 1.
This change occurs at CLK2, CLK4, CLK6, and CLK8. The CLK8 pulse causes the
counter to recycle. To produce this operation, Q 0 is connected to the J1 and K1 inputs
tes
of FF1. When Q0= 1 and a clock pulse occurs, FF1 is in the toggle mode and therefore
changes state. When Q0= 0, FF1 is in the no-change mode and remains in its present
state.
The output of FF2 (Q2) changes state both times; it is preceded by the unique
No

condition in which both Q0 and Q1 are HIGH. This condition is detected by the AND
gate and applied to the J2 and K2 inputs of FF2. Whenever both outputs Q0= Q1= 1,
the output of the AND gate makes the J2= K2= 1 and FF2 toggles on the following
clock pulse. Otherwise, the J2 and K2 inputs of FF2 are held LOW by the AND gate
w.

output, FF2 does not change state.

CLOCK Pulse Q2 Q1 Q0
Initially 0 0 0
ww

1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1
8 (recycles) 0 0 0

56

[Link]
 [Link]

n
Timing diagram

4-Bit Synchronous Binary Counter

e.i
This particular counter is implemented with negative edge-triggered Flip-
Flops. The reasoning behind the J and K input control for the first three Flip- Flops is
the same as previously discussed for the 3-bit counter. For the fourth stage, the Flip-
fre
Flop has to change the state when Q 0= Q1= Q2= 1. This condition is decoded by AND
gate G2.
tes
No

4- Bit Synchronous Binary Counter

Therefore, when Q0= Q1= Q2= 1, Flip-Flop FF3 toggles and for all other times it
w.

is in a no-change condition. Points where the AND gate outputs are HIGH are
indicated by the shaded areas.

4-Bit Synchronous Decade Counter: (BCD Counter):

ww

BCD decade counter has a sequence from 0000 to 1001 (9). After 1001 state it
must recycle back to 0000 state. This counter requires four Flip-Flops and AND/OR
logic as shown below.

57

[Link]
[Link]

n
4-Bit Synchronous Decade Counter

 First, notice that FF0 (Q0) toggles on each clock pulse, so the logic equation for

e.i
its J0 and K0 inputs is
J0= K0= 1
This equation is implemented by connecting J0 and K0 to a constant HIGH level.
 fre
Next, notice from table, that FF1 (Q1) changes on the next clock pulse each
time Q0 = 1 and Q3 = 0, so the logic equation for the J1 and K1 inputs is
J1= K1= Q0Q3’
tes
 Flip-Flop 2 (Q2) changes on the next clock pulse each time both Q 0 = Q1 = 1.
This requires an input logic equation as follows:
J2= K2= Q0Q1
This equation is implemented by ANDing Q0 and Q1 and connecting the gate output
No

to the J2 and K2 inputs of FF2.

 Finally, FF3 (Q3) changes to the opposite state on the next clock pulse each
time Q0 = 1, Q1 = 1, and Q2 = 1 (state 7), or when Q0 = 1 and Q1 = 1 (state 9).
w.

The equation for this is as follows:

J3= K3= Q0Q1Q2+ Q0Q3
This function is implemented with the AND/OR logic connected to the J3 and K3
ww

inputs of FF3.

58

[Link]
[Link]

CLOCK Pulse Q3 Q2 Q1 Q0
Initially 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0

n
9 1 0 0 1
10(recycles) 0 0 0 0

e.i
The timing diagram for the decade counter is shown below.

fre
tes

Timing diagram
No

Synchronous UP/DOWN Counter

An up/down counter is a bidirectional counter, capable of progressing in
either direction through a certain sequence. A 3-bit binary counter that advances
w.

upward through its sequence (0, 1, 2, 3, 4, 5, 6, 7) and then can be reversed so that it
goes through the sequence in the opposite direction (7, 6, 5, 4, 3, 2, 1,0) is an
illustration of up/down sequential operation.
ww

The complete up/down sequence for a 3-bit binary counter is shown in table
below. The arrows indicate the state-to-state movement of the counter for both its UP
and its DOWN modes of operation. An examination of Q0 for both the up and down
sequences shows that FF0 toggles on each clock pulse. Thus, the J0 and K0 inputs of
FF0 are,
J0= K0= 1

59

[Link]
[Link]

n
To form a synchronous UP/DOWN counter, the control input (UP/DOWN)

e.i
is used to allow either the normal output or the inverted output of one Flip-Flop to
the J and K inputs of the next Flip-Flop. When UP/DOWN= 1, the MOD 8 counter

fre
will count from 000 to 111 and UP/DOWN= 0, it will count from 111 to 000.

When UP/DOWN= 1, it will enable AND gates 1 and 3 and disable AND
gates 2 and 4. This allows the Q0 and Q1 outputs through the AND gates to the J and
tes
K inputs of the following Flip-Flops, so the counter counts up as pulses are applied.
When UP/DOWN= 0, the reverse action takes place.

J1= K1= ([Link])+ (Q0’.DOWN)

No

J2= K2= (Q0. [Link])+ (Q0’.Q1’.DOWN)

w.
ww

3-bit UP/DOWN Synchronous Counter

60

[Link]
[Link]

MODULUS-N-COUNTERS:
The counter with ‘n’ Flip-Flops has maximum MOD number 2n. Find the
number of Flip-Flops (n) required for the desired MOD number (N) using the
equation,
2n ≥ N
(i) For example, a 3 bit binary counter is a MOD 8 counter. The basic counter can
be modified to produce MOD numbers less than 2n by allowing the counter to

n
skin those are normally part of counting sequence.
n= 3

e.i
N= 8
2n = 23= 8= N

(ii) fre
MOD 5 Counter:
2n= N
2n= 5
22= 4 less than N.
tes
23= 8 > N(5)
Therefore, 3 Flip-Flops are required.
No

(iii) MOD 10 Counter:

2n= N= 10
23= 8 less than N.
24= 16 > N(10).
w.

To construct any MOD-N counter, the following methods can be used.

1. Find the number of Flip-Flops (n) required for the desired MOD number (N)
using the equation,
ww

2n ≥ N.
2. Connect all the Flip-Flops as a required counter.
3. Find the binary number for N.
4. Connect all Flip-Flop outputs for which Q= 1 when the count is N, as inputs to
NAND gate.
5. Connect the NAND gate output to the CLR input of each Flip-Flop.

61

[Link]
[Link]

When the counter reaches Nth state, the output of the NAND gate goes LOW,
resetting all Flip-Flops to 0. Therefore the counter counts from 0 through N-1.

For example, MOD-10 counter reaches state 10 (1010). i.e., Q3Q2Q1Q0= 1 0 1 0.

The outputs Q3 and Q1 are connected to the NAND gate and the output of the
NAND gate goes LOW and resetting all Flip-Flops to zero. Therefore MOD-10
counter counts from 0000 to 1001. And then recycles to the zero value.
The MOD-10 counter circuit is shown below.

n
e.i
fre
MOD-10 (Decade) Counter
tes
2.1 SHIFT REGISTER COUNTERS:
A shift register counter is basically a shift register with the serial output
connected back to the serial input to produce special sequences. Two of the most
No

common types of shift register counters are:

Johnson counter (Shift Counter),
Ring counter,
w.

3.16.1 Johnson counter (Shift Counter):

In a Johnson counter the complement of the output of the last Flip-Flop is
connected back to the D input of the first Flip-Flop. This feedback arrangement
ww

produces a characteristic sequence of states as shown in table below. The 4-bit

sequence has a total of eight states, and that the 5-bit sequence has a total of ten
states. In general, a Johnson counter will produce a modulus of 2n, where ‘n’ is the
number of stages in the counter.

62

[Link]
[Link]

4-Bit Johnson Counter

The Q output of each stage is connected to the D input of the next stage
(assuming that D Flip-Flops are used). The complement output of the last stage is

n
connected back to the D input of the first stage.

e.i
fre
tes
Time sequence for a 4-bit Johnson counter
No

3.16.2 Ring Counters:

The ring counter utilizes one Flip-Flop for each state in its sequence. It has the
advantage that decoding gates are not required. In the case of a l0-bit ring counter,
there is a unique output for each decimal digit.
w.
ww

Ring counter

The output Q0 sets D1 input, Q1 sets D2, Q2 sets D3 and Q3 is fed back to D0.
Because of these conditions, bits are shifted left one position per positive clock edge

63

[Link]
[Link]

and fed back to the input. All the Flip-Flops are clocked together. When CLR goes
low then back to high, the output is 0000.

n
e.i
Time sequence for a Ring counter

fre
The first positive clock edge shifts MSB to LSB position and other bits to one
position left so that the output becomes Q= 0010. This process continues on second
and third clock edge so that successive outputs are 0100 and 1000. The fourth
tes
positive clock edge starts the cycle all over again and the output is 0001. Thus the
stored 1 bit follows a circular path (i.e., the stored 1 bits move left through all Flip-
Flops and the final Flip-Flop sends it back to the first Flip-Flop). This action has
given the name of ring counter.
No

2.2 DESIGN OF COUNTERS:

The procedure for design of counters as follows:
w.

1. Specify the counter sequence and draw a state diagram.

2. Derive a next-state table from the state diagram.
3. Make the state assignment and develop a transition table showing the flip-
ww

flop inputs required.

4. Draw the K-maps for each input of each Flip-Flop.
5. Derive the logic expression for each Flip-Flop input from the K-maps.
6. Implement the expressions with combinational logic and combine with the
Flip-Flops to form the counter.

64

[Link]
[Link]

Examples:
1. Using JK Flip-Flops, design a synchronous counter which counts in the
sequence, 000, 001, 010, 011, 100, 101, 110, 111, 000.
Step 1: State Diagram

n
e.i
Step 2: Excitation Table :
Excitation Table for JK Flip-Flop:
fre Present State
Qn
0
Next State
Qn+1
0
J
0
Inputs
K
x
0 1 1 x
1 0 x 1
tes
1 1 x 0
Excitation Table for Counter:

Present State Next State Flip-Flop Inputs

No

Q2 Q1 Q0 q2 q1 q0 J2 K2 J1 K1 J0 K0
0 0 0 0 0 1 0 x 0 x 1 x
0 0 1 0 1 0 0 x 1 x x 1
0 1 0 0 1 1 0 x x 0 1 x
0 1 1 1 0 0 1 x x 1 x 1
w.

1 0 0 1 0 1 x 0 0 x 1 x
1 0 1 1 1 0 x 0 1 x x 1
1 1 0 1 1 1 x 0 x 0 1 x
1 1 0 0 0 1 1
ww

1 x x x 1

Step 3: K-map Simplification

65

[Link]
[Link]

n
e.i
Step 4: Logic Diagram

fre
tes
No

2. Design and explain the working of a synchronous MOD-3 counter.

Soln:
2n ≥ N= 3
22 > 3.
w.

Therefore, 2 Flip-Flops are required.

State Diagram:
ww

66

[Link]
[Link]

Excitation Table:
Excitation Table for JK Flip-Flop:

Present State Next State Inputs

Qn Qn+1 J K
0 0 0 x
0 1 1 x
1 0 x 1
1 1 x 0
Excitation Table for Counter:

n
Present State Next State Flip-Flop Inputs

e.i
QB QA QB+1 QA+1 JB KB JA KA
0 0 0 1 0 x 1 x
0 1 1 0 1 x x 1
1 0 0 0 x 1 0 x
fre
K-map Simplification:
tes
No
w.

Logic Diagram:
ww

67

[Link]
[Link]

3. Design a synchronous counter with states 0, 1, 2, 3, 0, 1, ………using JK Flip-

Flops.
Soln:
State Diagram:

n
e.i
Excitation Table for Counter:
fre
Present State
QB
0
QA
0
Next State
QB+1
0
QA+1
1
JB
0
Flip-Flop Inputs
KB
x
JA
1
KA
x
0 1 1 0 1 x x 1
tes
1 0 1 1 x 0 1 x
1 1 0 0 x 1 x 1

K-map Simplification:
No
w.

Logic Diagram:
ww

68

[Link]
[Link]

4. Design a MOD-7 synchronous counter using JK Flip-Flops. Write excitation table

and state table.
Soln:
2n ≥ N= 7
23 > 8.
Therefore, 3 Flip-Flops are required.
State Diagram:

n
e.i
fre
Excitation Table:
tes
Excitation Table for JK Flip-Flop:

Present State Next State Inputs

Qn Qn+1 J K
0 0 0 x
No

0 1 1 x
1 0 x 1
1 1 x 0
Excitation Table for Counter:
w.

Present State Next State Flip-Flop Inputs

QC QB QA QC+1 QB+1 QA+1 JC KC JB KB JA KA
0 0 0 0 0 1 0 x 0 x 1 x
ww

0 0 1 0 1 0 0 x 1 x x 1
0 1 0 0 1 1 0 x x 0 1 x
0 1 1 1 0 0 1 x x 1 x 1
1 0 0 1 0 1 x 0 0 x 1 x
1 0 1 1 1 0 x 0 1 x x 1
1 1 0 0 0 0 x 1 x 1 0 x

69

[Link]
[Link]

K-map Simplification:

n
e.i
fre
tes

Logic Diagram:
No
w.
ww

5. Design a MOD-10 synchronous counter using JK Flip-Flops. Write excitation

table and state table.
Soln:
2n ≥ N= 10
24 > 10.

70

[Link]
[Link]

Therefore, 4 Flip-Flops are required.

State Table:

n
e.i
Excitation Table:
Excitation Table for JK Flip-Flop:
fre Present State
Qn
0
Next State
Qn+1
0
J
0
Inputs
K
x
0 1 1 x
tes
1 0 x 1
1 1 x 0

Excitation Table for Counter:

No

Present State Next State Flip-Flop Inputs

Q D QC QB QA QD+1 QC+1 QB+1 QA+1 JD KD JC KC JB KB JA KA
0 0 0 0 0 0 0 1 0 x 0 x 0 x 1 x
0 0 0 1 0 0 1 0 0 x 0 x 1 x x 1
0 0 1 0 0 0 1 1 0 x 0 x x 0 1 x
w.

0 0 1 1 0 1 0 0 0 x 1 x x 1 x 1
0 1 0 0 0 1 0 1 0 x x 0 0 x 1 x
0 1 0 1 0 1 1 0 0 x x 0 1 x x 1
ww

0 1 1 0 0 1 1 1 0 x x 0 x 0 1 x
0 1 1 1 1 0 0 0 1 x x 1 x 1 x 1
1 0 0 0 1 0 0 1 x 0 0 x 0 x 1 x
1 0 0 1 0 0 0 0 x 1 0 x 0 x x 1

71

[Link]
[Link]

K-map Simplification:

n
e.i
fre
tes
No
w.
ww

72

[Link]
[Link]

Logic Diagram:

n
e.i
6. Design a synchronous 3-bit gray code up counter with the help of excitation table.
Soln: fre
Gray code sequence: 000, 001, 011, 010, 110, 111, 101, 100.
State Diagram:
tes
No
w.

Excitation Table:

Present State Next State Flip-Flop Inputs

QC QB QA QC+1 QB+1 QA+1 JC KC JB KB JA KA
ww

0 0 0 0 0 1 0 x 0 x 1 x
0 0 1 0 1 1 0 x 1 x x 0
0 1 1 0 1 0 0 x x 0 x 1
0 1 0 1 1 0 1 x x 0 0 x
1 1 0 1 1 1 x 0 x 0 1 x
1 1 1 1 0 1 x 0 x 1 x 0
1 0 1 1 0 0 x 0 0 x x 1
1 0 0 0 0 0 x 1 0 x 0 x

73

[Link]
[Link]

K-map Simplification:

n
e.i
fre
tes
No

Logic Diagram:
w.
ww

74

[Link]
[Link]

7. Design a 3 bit (MOD 8) Synchronous UP/DOWN counter.

Soln:
When UP/DOWN= 1, UP mode,
UP/DOWN= 0, DOWN mode.
State Diagram:

n
e.i
Excitation Table:
fre
Input Present State Next State A B C
tes
Up/Down Q A Q B QC QA+1 QB+1 QC+1 JA KA JB KB JC KC
0 0 0 0 1 1 1 1 x 1 x 1 x
0 1 1 1 1 1 0 x 0 x 0 x 1
0 1 1 0 1 0 1 x 0 x 1 1 x
No

0 1 0 1 1 0 0 x 0 0 x x 1
0 1 0 0 0 1 1 x 1 1 x 1 x
0 0 1 1 0 1 0 0 x x 0 x 1
0 0 1 0 0 0 1 0 x x 1 1 x
w.

0 0 0 1 0 0 0 0 x 0 x x 1
1 0 0 0 0 0 1 0 x 0 x 1 x
1 0 0 1 0 1 0 0 x 1 x x 1
ww

1 0 1 0 0 1 1 0 x x 0 1 x
1 0 1 1 1 0 0 1 x x 1 x 1
1 1 0 0 1 0 1 x 0 0 x 1 x
1 1 0 1 1 1 0 x 0 1 x x 1
1 1 1 0 1 1 1 x 0 x 0 1 x
1 1 1 1 0 0 0 x 1 x 1 x 1

75

[Link]
[Link]

K-map Simplification:

n
e.i
fre
tes
No
w.

Logic Diagram:
ww

76

[Link]
[Link]

4.20 LOCKOUT CONDITION:

In a counter if the next state of some unused state is again a used state and if
by chance the counter happens to find itself in the unused states and never arrived at
a used state then the counter is said to be in the lockout condition.

n
e.i
Desired Sequence

The circuit that goes in lockout condition is called bushless circuit. To make
fre
sure that the counter will come to the initial state from any unused state, the
additional logic circuit is necessary. To ensure that the lockout does not occur, the
counter should be designed by forcing the next state to be the initial state from the
tes
unused states as shown below.
No

State diagram for removing lockout

w.

8. Design a synchronous counter for

Avoid lockout condition. Use JK type design.

ww

Soln:
State diagram:

77

[Link]
[Link]

Here, states 5, 2 and 0 are forced are forced to go into 6, 3 and 1state,
respectively to avoid lockout condition.
Excitation table:
Excitation Table for JK Flip-Flop:

Present State Next State Inputs

Qn Qn+1 J K
0 0 0 x
0 1 1 x

n
1 0 x 1
1 1 x 0

e.i
Excitation Table for counter:

Present State Next State Flip-Flop Inputs

QA QB QC QA+1 QB+1 QC+1 JA KA JB KB JC KC
0
0
0
fre
0
0
1
0
1
0
0
1
0
0
0
1
1
0
1
0
1
0
x
x
x
0
0
x
x
x
0
1
x
1
x
1
x
0 1 1 0 0 1 0 x x 1 x 0
tes
1 0 0 1 1 0 x 0 1 x 0 x
1 0 1 1 1 0 x 0 1 x x 1
1 1 0 1 1 1 x 0 x 0 1 x
1 1 1 0 1 1 x 1 x 0 x 0
No

K-map Simplification:
w.
ww

78

[Link]
[Link]

Logic Diagram:

n
e.i
fre
tes
No
w.
ww

79

[Link]
 e
3.1 Functional Units of Digital Computer
o
fre
A computer organization describes the functions and design of the various units of a digital
system.
tes
o A general-purpose computer system is the best-known example of a digital system. Other
examples include telephone switching exchanges, digital voltmeters, digital counters,
electronic calculators and digital displays.
o Computer architecture deals with the specification of the instruction set and the hardware
No

units that implement the instructions.

o Computer hardware consists of electronic circuits, displays, magnetic and optic storage
media and also the communication facilities.
o Functional units are a part of a CPU that performs the operations and calculations called for
w.

by the computer program.

o Functional units of a computer system are parts of the CPU (Central Processing Unit) that
performs the operations and calculations called for by the computer program. A computer
ww

consists of five main components namely, Input unit, Central Processing Unit, Memory unit
Arithmetic & logical unit, Control unit and an Output unit.
 n
e.i
fre
Input unit
tes
o Input units are used by the computer to read the data. The most commonly used input devices
are keyboards, mouse, joysticks, trackballs, microphones, etc.
o However, the most well-known input device is a keyboard. Whenever a key is pressed, the
No

corresponding letter or digit is automatically translated into its corresponding binary code
and transmitted over a cable to either the memory or the processor.

Central processing unit

w.

o Central processing unit commonly known as CPU can be referred as an electronic circuitry
within a computer that carries out the instructions given by a computer program by
performing the basic arithmetic, logical, control and input/output (I/O) operations specified
ww

by the instructions.

Memory unit
o The Memory unit can be referred to as the storage area in which programs are kept which are
running, and that contains data needed by the running programs.
o The Memory unit can be categorized in two ways namely, primary memory and secondary
memory.
o It enables a processor to access running execution applications and services that are
temporarily stored in a specific memory location.
 o Primary storage is the fastest memory that operates at electronic speeds. Primary memory
contains a large number of semiconductor storage cells, capable of storing a bit of
information. The word length of a computer is between 16-64 bits.
o It is also known as the volatile form of memory, means when the computer is shut down,
anything contained in RAM is lost.
o Cache memory is also a kind of memory which is used to fetch the data very soon. They are
highly coupled with the processor.

n
o The most common examples of primary memory are RAM and ROM.
o Secondary memory is used when a large amount of data and programs have to be stored for a

e.i
long-term basis.
o It is also known as the Non-volatile memory form of memory, means the data is stored
permanently irrespective of shut down.
o fre
The most common examples of secondary memory are magnetic disks, magnetic tapes, and
optical disks.

Arithmetic & logical unit

tes
o Most of all the arithmetic and logical operations of a computer are executed in the ALU
(Arithmetic and Logical Unit) of the processor. It performs arithmetic operations like
addition, subtraction, multiplication, division and also the logical operations like AND, OR,
No

NOT operations.

Control unit
o The control unit is a component of a computer's central processing unit that coordinates the
w.

operation of the processor. It tells the computer's memory, arithmetic/logic unit and input and
output devices how to respond to a program's instructions.
o The control unit is also known as the nerve center of a computer system.
ww

o Let's us consider an example of addition of two operands by the instruction given as Add
LOCA, RO. This instruction adds the memory location LOCA to the operand in the register
RO and places the sum in the register RO. This instruction internally performs several steps.

Output Unit
o The primary function of the output unit is to send the processed results to the user. Output
devices display information in a way that the user can understand.
o Output devices are pieces of equipment that are used to generate information or any other
response processed by the computer. These devices display information that has been held or
generated within a computer.
 o The most common example of an output device is a monitor.

3.2 Von-Neumann Model

Von-Neumann proposed his computer architecture design in 1945 which was later known as Von-
Neumann Architecture. It consisted of a Control Unit, Arithmetic, and Logical Memory Unit (ALU),
Registers and Inputs/Outputs.

Von Neumann architecture is based on the stored-program computer concept, where instruction data
and program data are stored in the same memory. This design is still used in most computers

n
produced today.

e.i
A Von Neumann-based computer:
o Uses a single processor
o Uses one memory for both instructions and data.
o fre
Executes programs following the fetch-decode-execute cycle
tes
No
w.
ww

Components of Von-Neumann Model:

o Central Processing Unit
o Buses
o Memory Unit

Central Processing Unit

 The part of the Computer that performs the bulk of data processing operations is called the Central
Processing Unit and is referred to as the CPU.

The Central Processing Unit can also be defined as an electric circuit responsible for executing the
instructions of a computer [Link] Video

The CPU performs a variety of functions dictated by the type of instructions that are incorporated in
the computer.

The major components of CPU are Arithmetic and Logic Unit (ALU), Control Unit (CU) and a
variety of registers.

n
Arithmetic and Logic Unit (ALU)

e.i
The Arithmetic and Logic Unit (ALU) performs the required micro-operations for executing the
instructions. In simple words, ALU allows arithmetic (add, subtract, etc.) and logic (AND, OR,
NOT, etc.) operations to be carried out.

Control Unit fre

The Control Unit of a computer system controls the operations of components like ALU, memory
and input/output devices.
tes
The Control Unit consists of a program counter that contains the address of the instructions to be
fetched and an instruction register into which instructions are fetched from memory for execution.

Registers
No

Registers refer to high-speed storage areas in the CPU. The data processed by the CPU are fetched
from the registers.

Following is the list of registers that plays a crucial role in data processing.
w.

Registers Description

MAR (Memory Address Register) This register holds the memory location of the data that needs to be accessed.
ww

MDR (Memory Data Register) This register holds the data that is being transferred to or from memory.

AC (Accumulator) This register holds the intermediate arithmetic and logic results.

PC (Program Counter) This register contains the address of the next instruction to be executed.

CIR (Current Instruction Register) This register contains the current instruction during processing.
 Buses are the means by which information is shared between the registers in a multiple-register
configuration system.

A bus structure consists of a set of common lines, one for each bit of a register, through which binary
information is transferred one at a time. Control signals determine which register is selected by the
bus during each particular register transfer.

Von-Neumann Architecture comprised of three major bus systems for data transfer.

Bus Description

n
Address Bus Address Bus carries the address of data (but not the data) between the processor and the memory.

e.i
Data Bus Data Bus carries data between the processor, the memory unit and the input/output devices.

Control Bus Control Bus carries signals/commands from the CPU.

Memory Unit fre

A memory unit is a collection of storage cells together with associated circuits needed to transfer
information in and out of the storage. The memory stores binary information in groups of bits called
tes
words. The internal structure of a memory unit is specified by the number of words it contains and
the number of bits in each word.

Two major types of memories are used in computer systems:

No

1. RAM (Random Access Memory)

2. ROM (Read-Only Memory)

3.3 Operation and Operands of Computer Hardware

Instruction
w.

Computer instruction is a binary code that determines the micro-operations in a sequence for a computer.
They are saved in the memory along with the information. Each computer has its specific group of
instructions. They can be categorized into two elements as Operation codes (Opcodes) and Address. Opcodes
ww

specify the operation for specific instructions, and an address determines the registers or the areas used for
that operation.

Operands are definite elements of computer instruction that show what information is to be operated
on. The most important general categories of data are

1. Addresses
2. Numbers
3. Characters
4. Logical data

In many cases, some calculation must be performed on the operand reference to determine the main
or virtual memory address.
In this context, addresses can be considered to be unsigned integers. Other common data types are numbers,
characters, and logical data, and each of these is briefly described below. Some machines define specialized
data types or data structures. For example, machine operations may operate directly on a list or a string of
characters.

Addresses

Addresses are nothing but a form of data. Here some calculations must be performed on the operand
reference in an instruction, which is to determine the physical address of an instruction.

Numbers

n
All machine languages include numeric data types. Even in non-numeric data processing, numbers

e.i
are needed to act as counters, field widths, etc. An important difference between numbers used in
ordinary mathematics and numbers stored in a computer is that the latter is limited. Thus, the
programmer is faced with understanding the consequences of rounding, overflow and underflow.

Here are the three types of numerical data in computers, such as:
fre
1. Integer or fixed point: Fixed point representation is used to store integers, the positive and
negative whole numbers (… -3, -2, -1, 0, 1, 2, 3, …). However, the programmer assigns a radix point
tes
location to each number and tracks the radix point through every operation. High-level programs,
such as C and BASIC usually allocate 16 bits to store each integer. Each fixed point binary number
has three important parameters that describe it:

 Whether the number is signed or unsigned,

 The position of the radix point to the right side of the sign bit (for signed numbers), or the position of
No

the radix point to the most significant bit (for unsigned numbers).
 And the number of fractional bits stored.

2. Floating point: A Floating Point number usually has a decimal point, which means 0, 3.14, 6.5,
and-125.5 are Floating Point
w.

The term floating point is derived from the fact that there is no fixed number of digits before and
after the decimal point, which means the decimal point can float. There are also representations in
which the number of digits before and after the decimal point is set, called fixed-point
representations. In general, floating-point representations are slower and less accurate than fixed-
ww

point representations, but they can handle a larger range of numbers.

3. Decimal number: The decimals are an extension of our number system. We also know that
decimals can be considered fractions with 10, 100, 1000, etc. The numbers expressed in the decimal
form are called decimal numbersor decimals. For example:1, 4.09, 13.83, etc. A decimal number has
two parts, and a dot separates these parts (.) called the decimal point.

 Whole number part: The digits lying to the left of the decimal point form the whole number part.
The places begin with ones, tens, hundreds, thousands and so on.
 Decimal part: The decimal point and the digits laying on the right of the decimal point form the
decimal part. The places begin with tenths, hundredths, thousandths and so on.

Characters

A common form of data is text or character strings. While textual data are most convenie
humans. But computers work in binary. So, all characters, whether letters, punctuation or
stored as binary numbers. All of the characters that a computer can use are called character sets.
Here are the two common standards, such as:

1. American Standard Code for Information Interchange (ASCII)

2. Unicode

ASCII uses seven bits, giving a character set of 128 characters. The characters are represented in a
table called the ASCII table. The 128 characters include:

 32 control codes (mainly to do with printing)

 32 punctuation codes, symbols, and space

n
 26 upper-case letters
 26 lower-case letters
 numeric digits 0-9

e.i
We can say that the letter 'A' is the first letter of the alphabet; 'B' is the second, and so on, all the way
up to 'Z', which is the 26th letter. In ASCII, each character has its own assigned number. Denary,
binary and hexadecimal representations of ASCII characters are shown in the below table.

Character Denary Binary Hexadecimal

A 65 1000001
fre
41
tes
Z 90 1011010 5A

a 97 1100001 61

z 122 1111010 7A
No

0 48 0110000 30

9 57 0111001 39
w.

Space 32 0100000 20

! 33 0100001 21
ww

A is represented by the denary number 65 (binary 1000001, hexadecimal 41), B by 66 (binary

1000010, hexadecimal 42) and so on up to Z, which is represented by the denary number 90 (binary
1011010, hexadecimal 5A).

Similarly, lower-case letters start at denary 97 (binary 1100001, hexadecimal 61) and end at denary
122 (binary 1111010, hexadecimal 7A). When data is stored or transmitted, its ASCII or Unicode
number is used, not the character itself.

For example, the word "Computer" would be represented as:

1000011 1101111 1101101 1110000 1110101 1110100 1100101 1110010

On the other hand, IRA is also widely used outside the United States. A unique 7-bit p
represents each character in this code. Thus, 128 different characters can be represent
www
than necessary to represent printable characters, and some of the patterns represent co
characters. Some control characters control the printing of characters on a page, and others are
concerned with communications procedures.

IRA-encoded characters are always stored and transmitted using 8 bits per character. The 8 bit may
be set to 0 or used as a parity bit for error detection. In the latter case, the bit is set such that the total
number of binary 1s in each octet is always odd (odd parity) or always even (even parity).

Logical data

Normally, each word or other addressable unit (byte, half-word, and so on) is treated as a single unit
of data. Sometimes, it is useful to consider an n-bit unit consisting of 1-bit items of data, each item

n
having the value 0 or 1. When data are viewed this way, they are considered to be logical data.

e.i
The Boolean data can only represent two values: true or false. Although only two values are
possible, they are rarely implemented as a single binary digit for efficiency reasons. Many
programming languages do not have an explicit Boolean type, instead of interpreting 0 as false and
other values as true. Boolean data refers to the logical structure of how the language is interpreted to
the machine language. In this case, a Boolean 0 refers to the logic False, and true is always a non
zero, especially one known as Boolean 1.

There are two advantages to the bit-oriented view:

fre
 We may want to store an array of Boolean or binary data items, in which each item can take on only
tes
the values 0 and 1. With logical data, memory can be used most efficiently for this storage.
 There are occasions when we want to manipulate the bits of a data item.

3.4 Instruction set Architecture(ISA):

No

An Instruction Set Architecture (ISA) is part of the abstract model of a computer that defines how the
CPU is controlled by the software. The ISA acts as an interface between the hardware and the software,
specifying both what the processor is capable of doing as well as how it gets done

Two types of instruction set architectures are

w.

The two main categories of instruction set architectures, CISC (such as Intel's x86 series) and RISC (such
as ARM and MIPS),

The ISA of a processor can be described using 5 catagories:

ww

Operand Storage in the CPU

Number of explicit named operands
Operand location
Operations
Type and size of operands

The 3 most common types of ISAs are:

1. Stack - The operands are implicitly on top of the stack.

2. Accumulator - One operand is implicitly the accumulator.
3. General Purpose Register (GPR) - All operands are explicitely mentioned, they are either
registers or memory locations
 Stack Accumulator GPR

PUSH A LOAD A LOAD R1,A

PUSH B ADD B ADD R1,B

ADD STORE C STORE R1,C

POP C - -

n
e.i
The i8086 has many instructions that use implicit operands although it has a general register set. The
i8051 is another example, it has 4 banks of GPRs but most instructions must have the A register as
one of its operands.

Stack
fre
Advantages: Simple Model of expression evaluation (reverse polish). Short instructions.
Disadvantages: A stack can't be randomly accessed This makes it hard to generate eficient code.
tes
The stack itself is accessed every operation and becomes a bottleneck.

Accumulator

Advantages: Short instructions.

No

Disadvantages: The accumulator is only temporary storage so memory traffic is the highest for this
approach.

GPR

Advantages: Makes code generation easy. Data can be stored for long periods in registers.
w.

Disadvantages: All operands must be named leading to longer instructions.

Reduced Instruction Set Computer (RISC):

ww

RISC stands for Reduced Instruction Set Computer. The ISA is composed of instructions that all
have exactly the same size, usualy 32 bits. Thus they can be pre-fetched and pipelined succesfuly.
All ALU instructions have 3 operands which are only registers. The only memory access is through
explicit LOAD/STORE instructions.
Thus C = A + B will be assembled as:

LOAD R1,A
LOAD R2,B
ADD R3,R1,R2
STORE C,R3

Although it takes 4 instructions we can reuse the values in the registers.

Complex Instruction Set Architecture (CISC) :
The main idea is that a single instruction will do all loading, evaluating, and storing
operations just like a multiplication command will do stuff like loading data, evaluating,
and storing it, hence it’s complex

Memory Locations and Addresses

n
The memory consists of many millions of storage cells, each of which can store a bit of information having the
value 0 or 1. Because a single bit represents a very small amount of information, bits are seldom handled
individually.

e.i
The usual approach is to deal with them in groups of fixed size. For this purpose, the memory is organized so that a
group of n bits can be stored or retrieved in a single, basic operation. Each group of n bits is referred to as a word
of information, and n is called the word length. The memory of a computer can be schematically represented as a
collection of words.
fre
tes
No
w.
ww

Modern computers have word lengths that typically range from 16 to 64 bits. If the word length of a computer
is 32 bits, a single word can store a 32-bit signed number or four ASCII-encoded characters, each occupying 8
bits, as shown in Figure
 n
e.i
A unit of 8 bits is called a byte. Machine instructions may require one or more words for their representation.
fre
After we have described instructions at the assembly-language level. Accessing the memory to store or
retrieve a single item of information, either a word or a byte, requires distinct names or addresses for each
location. It is customary to use numbers from 0 to 2k − 1, for some suitable value of k, as the addresses of
successive locations in the memory. Thus, the memory can have up to 2k addressable locations. The 2k
tes
addresses constitute the address space of the computer. For example, a 24-bit address generates an address
space of 224 (16,777,216) locations. This number is usually written as 16M (16 mega), where 1M is the
number 220 (1,048,576). A 32-bit address creates an address space of 232 or 4G (4 giga) locations, where 1G
is 230. Other notational conventions that are commonly used are K (kilo) for the number 210 (1,024), and T
(tera) for the number 240
No

Byte Addressability :

A byte is always 8 bits, but the word length typically ranges from 16 to 64 bits. It is impractical to assign
distinct addresses to individual bit locations in the memory. The most practical assignment is to have
w.

successive addresses refer to successive byte locations in the memory. This is the assignment used in most
modern computers. The term byte-addressable memory is used for this assignment. Byte locations have
addresses 0, 1, 2,.... Thus, if the word length of the machine is 32 bits, successive words are located at
addresses 0, 4, 8,..., with each word consisting of four bytes.
ww

There are two ways that byte addresses can be assigned across words big-endian and Little endian
 n
e.i
fre
The name big-endian is used when lower byte addresses are used for the more significant bytes (the leftmost
bytes) of the word.

The name little-endian is used for the opposite ordering, where the lower byte addresses are used for the less
tes
significant bytes (the rightmost bytes) of the word. The words “more significant” and “less significant” are
used in relation to the weights (powers of 2) assigned to bits when the word represents a number. Both little-
endian and big-endian assignments are used in commercial machines. In both cases, byte addresses 0, 4, 8,...,
are taken as the addresses of successive words in the memory of a computer with a 32-bit word length. These
are the addresses used when accessing the memory to store or retrieve a word.
No

Memory Operations

Both program instructions and data operands are stored in the memory. To execute an instruction, the
processor control circuits must cause the word (or words) containing the instruction to be transferred from the
memory to the processor. Operands and results must also be moved between the memory and the processor.
w.

Thus, two basic operations involving the memory are needed, , namely Read and Write.

Read Operation:

The Read operation transfers a copy of the contents of a specific memory location to the processor. The
ww

memory contents remain unchanged. To start a Read operation, the processor sends the address of the desired
location to the memory and requests that its contents be read. The memory reads the data stored at that
address and sends them to the processor.

Write Operation:

The Write operation transfers an item of information from the processor to a specific memory location,
overwriting the former contents of that location. To initiate a Write operation, the processor sends the address
of the desired location to the memory, together with the data to be written into that location. The memory then
uses the address and data to perform the write.

3.5 Instructions and Instruction Sequencing

The tasks carried out by a computer program consist of a sequence of small steps, such as adding two
numbers, testing for a particular condition, reading a character from the keyboard, or sending a character to be
displayed on a display screen.

A computer must have instructions capable of performing four types of operations:

• Data transfers between the memory and the processor registers

• Arithmetic and logic operations on data

• Program sequencing and control

n
• I/O transfers

We begin by discussing instructions for the first two types of operations. To facilitate the discussion, we first

e.i
need some notation

Register Transfer Notation

We need to describe the transfer of information from one location in a computer to another. Possible locations

subsystem.

Example 1:
fre
that may be involved in such transfers are memory locations, processor registers, or registers in the I/O
tes
R2 ← [LOC]

This expressionmeans that the contents of memory location LOC are transferred into processor register R2

Example 2:
No

As another example, consider the operation that adds the contents of registers R2 and R3, and places their sum
into register R4. This action is indicated as

R4 ← [R2]+[R3]

This type of notation is known as Register Transfer Notation (RTN). Note that the righthand side of an RTN
w.

expression always denotes a value, and the left-hand side is the name of a location where the value is to be
placed, overwriting the old contents of that location
ww

Assembly-Language Notation:

to represent machine instructions and programs we use assembly –Language notation

Example 1:

Load R2, LOC

a generic instruction that causes the transfer described above, from memory location LOC to processor
register R2, The contents of LOC are unchanged by the execution of this instruction, but the old contents of
register R2 are overwritten. The name Load is appropriate for this instruction, because the contents read from
a memory location are loaded into a processor register

Example 2:

Add R4, R2, R3

adding two numbers contained in processor registers R2 and R3 and placing their sum in R4 can be specified
by the assembly-language statement, registers R2 and R3 hold the source operands, while R4 is the
destination

RISC and CISC Instruction Sets

One of the most important characteristics that distinguish different computers is the nature of their
instructions. There are two fundamentally different approaches in the design of instruction sets for modern
computers. One popular approach is based on the premise that higher performance can be achieved if each
instruction occupies exactly one word in memory, and all operands needed to execute a given arithmetic or
logic operation specified by an instruction are already in processor registers. This approach is conducive to an

n
implementation of the processing unit in which the various operations needed to process a sequence of
instructions are performed in “pipelined” fashion to overlap activity and reduce total execution time of a

e.i
program. The restriction that each instruction must fit into a single word reduces the complexity and the
number of different types of instructions that may be included in the instruction set of a computer. Such
computers are called Reduced Instruction Set Computers (RISC).

An alternative to the RISC approach is to make use of more complex instructions which may span more than
fre
one word of memory, and which may specify more complicated operations. This approach was prevalent prior
to the introduction of the RISC approach in the 1970s. Although the use of complex instructions was not
originally identified by any particular label, computers based on this idea have been subsequently called
Complex Instruction Set Computers (CISC).
tes
Introduction to RISC Instruction Sets:

Two key characteristics of RISC instruction sets are: • Each instruction fits in a single word. • A load/store
architecture is used, in which – Memory operands are accessed only using Load and Store instructions. – All
operands involved in an arithmetic or logic operation must either be in processor registers, or one of the
operands may be given explicitly within the instruction word.
No

At the start of execution of a program, all instructions and data used in the program are stored in the memory
of a computer. Processor registers do not contain valid operands at that time . If operands are expected to be in
processor registers before they can be used by an instruction, then it is necessary to first bring these operands
into the registers. This task is done by Load instructions which copy the contents of a memory location into a
processor register. Load instructions are of the form
w.

Load destination, source

Or more specifically
ww

Load processor_register, memory_location

Example:

The operation of adding two numbers is a fundamental capability in any computer.

The statement C = A + B

The required action can be accomplished by a sequence of simple machine instructions. We choose to use
registers R2, R3, and R4 to perform the task with four instructions:

Load R2, A

Load R3, B

Add R4, R2, R3

Store R4, C

Instruction Execution and Straight-Line Sequencing:

we used the task C = A + B

implemented as C ← [A] + [B]

n
e.i
fre
tes
No
w.

We assume that the word length is 32 bits and the memory is byte-addressable. The four instructions of the
program are in successive word locations, starting at location i. Since each instruction is 4 bytes long, the
second, third, and fourth instructions are at addresses i + 4, i + 8, and i + 12. For simplicity, we assume that a
desired memory address can be directly specified in Load and Store instructions, although this is not possible
if a full 32-bit address is involved.
ww

Let us consider how this program is executed. The processor contains a register called the program counter
(PC), which holds the address of the next instruction to be executed. To begin executing a program, the
address of its first instruction (i in our example) must be placed into the PC. Then, the processor control
circuits use the information in the PC to fetch and execute instructions, one at a time, in the order of
increasing addresses. This is called straight-line sequencing. During the execution of each instruction, the PC
is incremented by 4 to point to the next instruction. Thus, after the Store instruction at location i + 12 is
executed, the PC contains the value i + 16, which is the address of the first instruction of the next program
segment. Executing a given instruction is a two-phase procedure. In the first phase, called instruction fetch,
the instruction is fetched from the memory location whose address is in the PC. This instruction is placed in
the instruction register (IR) in the processor. At the start of the second phase, called instruction execute, the
instruction in IR is examined to determine which operation is to be performed. The specified operation is then
performed by the processor. This involves a small number of steps such as fetching operands from the
memory or from processor registers, performing an arithmetic or logic operation, and storing the res
destination location. At some point during this two-phase procedure, the contents of the PC are
point to the next instruction. When the execute phase of an instruction is completed, the PC contains the
address of the next instruction, and a new instruction fetch phase can begin.

Branching:

Consider the task of adding a list of n number

The addresses of the memory locations containing the n numbers are symbolically given as NUM1, NUM2,...,
NUMn, and separate Load and Add instructions are used to add each number to the contents of register R2.
After all the numbers have been added, the result is placed in memory location SUM.

n
e.i
fre
tes
No
w.
ww

Instead of using a long list of Load and Add instructions,

it is possible to implement a program loop in which the instructions read the next number in the list and add it
to the current sum. To add all numbers, the loop has to be executed as many times as there are numbers in the
list. The body of the loop is a straight-line sequence of instructions executed repeatedly. It starts at location
LOOP and ends at the instruction Branch_if_[R2]>0. During each pass through this loop, the address of the
next list entry is determined, and that entry is loaded into R5 and added to R3. The address of an operand can
be specified in various ways, as will be described in Section 2.4. For now, we concentrate on how to create
and control a program loop. Assume that the number of entries in the list, n, is stored in memory location N,
as shown. Register R2 is used as a counter to determine the number of times the loop is executed. Hence, the
contents of location N are loaded into register R2 at the beginning of the program. Then, within the body of
the loop, the instruction.
 n
e.i
fre
tes

Subtract R2, R2, #1

No

reduces the contents of R2 by 1 each time through the loop. Execution of the loop is repeated as long as the
contents of R2 are greater than zero. We now introduce branch instructions. This type of instruction loads a
new address into the program counter. As a result, the processor fetches and executes the instruction at this
new address, called the branch target, instead of the instruction at the location that follows the branch
instruction in sequential address order. A conditional branch instruction causes a branch only if a specified
w.

condition is satisfied. If the condition is not satisfied, the PC is incremented in the normal way, and the next
instruction in sequential address order is fetched and executed.

Branch_if_[R2]>0 LOOP
ww

is a conditional branch instruction that causes a branch to location LOOP if the contents of register R2 are
greater than zero. This means that the loop is repeated as long as there are entries in the list that are yet to be
added to R3. At the end of the nth pass through the loop, the Subtract instruction produces a value of zero in
R2, and, hence, branching does not occur. Instead, the Store instruction is fetched and executed. It moves the
final result from R3 into memory location SUM.

Encoding of Machine Instructions:

we have introduced a variety of useful instructions and addressing modes. We have used a generic form of
assembly language to emphasize basic concepts without relying on processor-specific acronyms or
mnemonics. Assembly-language instructions symbolically express the actions that must be performed by the
processor circuitry.
To be executed in a processor, assembly-language instructions must be converted by the assembler program,
into machine instructions that are encoded in a compact binary pattern.

Let us now examine how machine instructions may be formed.

The Add instruction

Add Rdst, Rsrc1, Rsrc2

The above instruction representative of a class of three-operand instructions that use operands in processor
registers. Registers Rdst, Rsrc1, and Rsrc2 hold the destination and two source operands. If a processor has
32 registers, then it is necessary to use five bits to specify each of the three registers in such instructions. If

n
each instruction is implemented in a 32-bit word, the remaining 17 bits can be used to specify the OP code
that indicates the operation to be performed

e.i
fre
tes
No

Now consider instructions in which one operand is given using the Immediate addressing mode, such as Add
w.

Rdst, Rsrc, #Value

Of the 32 bits available, ten bits are needed to specify the two registers. The remaining 22 bits must give the
OP code and the value of the immediate operand. The most useful sizes of immediate operands are 32, 16, and
ww

8 bits. Since 32 bits are not available, a good choice is to allocate 16 bits for the immediate operand. This
leaves six bits for specifying the OP code.

This format can also be used for Load and Store instructions, where the Index addressing mode uses the 16-bit
field to specify the offset that is added to the contents of the index register.

The format in Figure b can also be used to encode the Branch instructions. The Branch-greater-than
instruction at memory address 128.

BGT R2, R0, LOOP

if the contents of register R0 are zero. The registers R2 and R0 can be specified in the two register fields in
Figure b. The six-bit OP code has to identify the BGT operation. The 16-bit immediate field can be used to
provide the information needed to determine the branch target address, which is the location of the instruction
with the label LOOP. The target address generally comprises 32 bits. Since there is no space for 32 bits, the
BGT instruction makes use of the immediate field to give an offset from the location of this instruction in the
(address) of data is need to be specified, and in computer, there are various ways of
specifying the address of data. These various ways of specifying the address of data are
known as “Addressing Modes”

So Addressing Modes can be defined as “The technique for specifying the address of the
operands “ And in computer the address of operand i.e., the address where operand is actually
found is known as “Effective Address”. Now, in addition to this, the two most prominent

n
reason of why addressing modes are so important are:

e.i
First, the way the operand data are chosen during program execution is dependent on
theaddressing mode of the instruction.

Second, the address field(or fields) in a typical instruction format are relatively small and
fre
sometimes we would like to be able to reference a large range of locations, so here to achieve
this objective i.e., to fit this large range of location in address field, a variety of addressing
techniques has been employed. As they reduce the number of field in the addressing field of
tes
the instruction.

Thus, Addressing Modes are very vital in Instruction Set

Architecture(ISA).some notations are
No

A= Contents of an address field in the instruction

R= Contents of an address field in the instruction that refers to a register

EA= Effective Address(Actual address) of location containing the referenced

w.

operand.(X)= Contents of memory location x or register X.

ww
Types Of Addressing Modes
Various types of addressing modes are:

1. Implied and Immediate Addressing Modes

2. Direct or Indirect Addressing Modes
3. Register Addressing Modes

n
4. Register Indirect Addressing Mode
5. Auto-Increment and Auto-Decrement Addressing Modes

e.i
6. Displacement Based Addressing Modes

1. Implied and Immediate Addressing Modes:

Implied Addressing Mode: fre
tes
Implied Addressing Mode also known as "Implicit" or "Inherent“ addressing mode is the
addressing mode in which, no operand(register or memory location or data) is specified in the
instruction. As in this mode the operand are specified implicit in the definition of instruction.
No

“Complement Accumulator” is an Implied Mode instruction because the operand in the

accumulator register is implied in the definition of instruction. In assembly language it is written
as:

CMA: Take complement of content of AC Similarly, the instruction,

w.

RLC: Rotate the content of Accumulator is an implied mode instruction.

All Register-Reference instruction that use an accumulator and Zero-Address instruction in a

ww

Stack Organised Computer are implied mode instructions, because in Register reference operand
implied in accumulator and in Zero-Address instruction, the operand implied on the Top of
Stack.
Immediate Addressing Mode:
In Immediate Addressing Mode operand is specified in the instruction itself. In other words, an
immediate mode instruction has an operand field rather than an address field, which contain
actual operand to be used in conjunction with the operand specified in the instruction. That is, in
this mode, the format of instruction is:

n
As an example: The Instruction:

e.i
MVI 06 Move 06 to the accumulator

ADD 05 ADD 05 to the content of accumulator

fre
tes
 One of the operand is mentioned directly.
 Data is available as a part of instruction.
 Data is 8 0r 16 bit long.
 No memory reference is needed to fetch data
o
.N

Immediate Mode :Eg.

Example 1 :
w

MOV CL, 03H

ww

03 – 8 bit immediate source operand

CL – 8 bit register destination operand

Example 2:

ADD AX, 0525H

0525 – 16 bit immediate source operand

AX – 16 bit register destination operand.

2. Direct and Indirect Addressing Modes
The instruction format for direct and indirect addressing mode is shown below:

It consists of 3-bit opcode, 12-bit address and a mode bit designated as( I).The mode bit (I) is
zero for Direct Address and 1 for Indirect Address. Now we will discuss about each in detail
one by one.

.in
ee
Direct Addressing Mode
sfr
Direct Addressing Mode is also known as “Absolute Addressing Mode”. In this mode the
ote
address of data(operand) is specified in the instruction itself. That is, in this type of mode, the
operand resides in memory and its address is given directly by the address field of the
instruction. Means, in other words, in this mode, the address field contain the Effective Address
N

of operand i.e., EA=A

As an example: Consider the instruction:

w.

ADD A Means add contents of cell A to accumulator .

It Would look like as shown below:

ww

Here, we see that in it Memory Address=Operand.

Indirect Addressing Mode:
In this mode, the address field of instruction gives the memory address where on, the operand is
stored in memory. That is, in this mode, the address field of the instruction gives the address
where the “Effective Address” is stored in memory. i.e., EA=(A)

.in
Means, here, Control fetches the instruction from memory and then uses its address part to
access memory again to read Effective Address.

As an example: Consider the instruction:

e
ADD (A) Means adds the content of cell pointed to contents of A to Accumulator. It look
like as shown in figure below:

fre
tes
No

Thus in it, AC <-- M[M[A]]

w.

[M=Memory]

i.e., (A)=1350=EA
ww

[Link]
Addressing
Mode:
In Register Addressing Mode, the operands are in registers that reside within the CPU. That is, in
this mode, instruction specifies a register in CPU, which contain the operand. It is like Direct
Addressing Mode, the only difference is that the address field refers to a register instead of
memory location.
 i.e., EA=R

It look like as:

Example of such instructions are:

.in
MOV AX, BX Move contents of Register BX to AX

ADD AX, BX Add the contents of register BX to AX

e
Here, AX, BX are used as register names which is of 16-bit register.

fre
Thus, for a Register Addressing Mode, there is no need to compute the actual address as the
operand is in a register and to get operand there is no memory access involved
tes
No
w.

4. Register Indirect Addressing Mode:

ww

In Register Indirect Addressing Mode, the instruction specifies a register in CPU whose contents
give the operand in memory. In other words, the selected register contain the address of operand
rather than the operand itself. That is,

i.e., EA=(R)

Means, control fetches instruction from memory and then uses its address to access Register and
looks in Register(R) for effective address of operand in memory.

It look like as:

Here, the parentheses are to be interpreted as
meaning contents of.

Example of such instructions are:

MOV AL, [BX]

Code example in Register:

n
MOV BX, 1000H

e.i
MOV 1000H, operand

From above example, it is clear that, the instruction(MOV AL, [BX]) specifies a register[BX],

fre
and in coding of register, we see that, when we move register [BX], the register contain the
address of operand(1000H) rather than address itself.

5. Auto-increment and Auto-decrement

tes
Addressing Modes
These are similar to Register indirect Addressing Mode except that the register is incremented or
decremented after(or before) its value is used to access memory. These modes are required
No

because when the address stored in register refers to a table of data in memory, then it is
necessary to increment or decrement the register after every access to table so that next value is
accessed from memory.
w.

Thus, these addressing modes are common requirements in computer.

Auto-increment Addressing Mode:

ww

Auto-increment Addressing Mode are similar to Register Indirect Addressing Mode except that
the register is incremented after its value is loaded (or accessed) at another location like
accumulator(AC).

That is, in this case also, the Effective Address is equal to

EA=(R)

But, after accessing operand, register is incremented by 1.

As an example:

It look like as shown below:

Here, we see that effective address is (R )=400 and operand in AC is 7. And after loading R1 is
incremented by [Link] becomes 401.

Means, here we see that, in the Auto-increment mode, the R1 register is increment to 401 after

.in
execution of instruction.

e
fre
tes
No

Auto-decrement Addressing Mode:

w.

Auto-decrement Addressing Mode is reverse of auto-increment , as in it the register is

decrement before the execution of the instruction. That is, in this case, effective address is equal
ww

to

EA=(R) - 1
As an example:
It look like as shown below:
 n
e.i
Here, we see that, in the Auto-decrement mode, the register R1 is decremented to 399 prior to

fre
execution of the instruction, means the operand is loaded to accumulator, is of address 1099H in
memory, instead of [Link], in this case effective address is 1099H and contents loaded into
accumulator is 700.
tes
6. Displacement Based Addressing Modes:
No

Displacement Based Addressing Modes is a powerful addressing mode as it is a combination of

direct addressing or register indirect addressing mode. i.e., EA=A+(R)
w.

Means, Displacement Addressing Modes requires that the instruction have two address fields, at
least one of which is explicit means, one is address field indicate direct address and other
ww

indicate indirect address.

That is, value contained in one addressing field is A, which is used directly and the value in other
address field is R, which refers to a register whose contents are to be added to produce effective
address.
There are three areas where Displacement Addressing modes are used. In other words,
Displacement Based Addressing Modes are of three types. These are:

1. Relative Addressing Mode

2. Base Register Addressing Mode
3. Indexing Addressing Mode

n
Now we will explore to each one by one.

e.i
fre
tes
No

1. Relative Addressing Mode:

w.

In Relative Addressing Mode , the contents of program counter is added to the address part of
instruction to obtain the Effective Address.
ww

That is, in Relative Addressing Mode, the address field of the instruction is added to implicitly
reference register Program Counter to obtain effective address.

i.e., EA=A+PC

It becomes clear with an example:

Assume that PC contains the no.- 825 and the address part of instruction contain the no.- 24, then
the instruction at location 825 is read from memory during fetch phase and the Program Counter
is then incremented by one to 826.

The effective address computation for relative address mode is 26+24=850

Thus, Effective Address is displacement relative to the address of instruction. Relative

Addressing is often used with branch type instruction

.in
ee
sfr
ote

2. Index Register Addressing Mode

.N

In indexed addressing mode, the content of Index Register is added to direct address part(or
field) of instruction to obtain the effective address. Means, in it, the register indirect addressing
w

field of instruction point to Index Register, which is a special CPU register that contain an
Indexed value, and direct addressing field contain base address.
ww

As, indexed type instruction make sense that data array is in memory and each operand in the
array is stored in memory relative to base address. And the distance between the beginning
address and the address of operand is the indexed value stored in indexed register.
Any operand in the array can be accessed with the same instruction, which provided that the
index register contains the correct index value i.e., the index register can be incremented to
facilitate access to consecutive operands.

Thus, in index addressing mode

EA=A+Index

n
e.i
fre
tes
3. Base Register Addressing Mode:
No

In this mode, the content of the Base Register is added to the direct address part of the
instruction to obtain the effective address.
w.

Means, in it the register indirect address field point to the Base Register and to obtain EA, the
contents of Instruction Register, is added to direct address part of the instruction.
ww

This is similar to indexed addressing mode except that the register is now called as Base Register
instead of Index Register.
 That is, the EA=A+Base

n
e.i
fre
Thus, the difference between Base and Index mode is in the way they are used rather than
the way they are computed. An Index Register is assumed to hold an index number that is
relative to the address part of the instruction. And a Base Register is assumed to hold a
base address and thedirect address field of instruction gives a displacement relative to this
tes
base address.

Thus, the Base register addressing mode is used in computer to facilitate the relocation of
No

programs in memory. Means, when programs and data are moved from one segment of
memory to another, then Base address is changed, the displacement value of instruction
do not change.
w.

So, only the value of Base Register requires updation to reflect the beginning of new
memory segment.
ww