Module 5: Counters and State machines

SYLLABUS
Counters: Asynchronous and Synchronous counters, up, down, Mod-N counters, Ring counter,
Johnson counter, State Machines: Concept of state, state diagram, state transition tables, State
minimization, Moore and Mealy machines.
---------------------------------------------------------------------------------------------------------------------
COUNTERS:

Counters are the crucial hardware components, and are defined as “The digital circuit which is
used to count the number of pulses”. Counters are well known to us as “Timers”. Counter
circuits are the best example for the flip flop applications. Counters are designed by grouping of
flip flops and applying a single clock signal to them. In simple words, the counters are those,
which have the group of storage elements like flip flops to hold the count.

Need of Counters:
Counting means incrementing or decrementing the values of an operator, with respect to its
previous state value. So to perform the mathematical operation we use no devices other than
counters. We cannot perform this action (counting) with any other logic devices rather than
counters.

Types of counters:
There are two types of counters available for digital circuits, they are
1. Synchronous counters
2. Asynchronous counters

Differences between Synchronous and Asynchronous counters:

SYNCHRONOUS COUNTERS ASYNCHRONOUS COUNTERS

The propagation delay is very low. Propagation delay is higher than that of
synchronous counters.

Its operational frequency is very The maximum frequency of operation is very

high. low.

These are faster than that of ripple These are slow in operation.
counters.

Large number of logic gates are Less number of logic gates required.
required to design

High cost. Low cost.

Synchronous circuits are easy to Complex to design.

design.

Standard logic packages available for For asynchronous counters, Standard logic
synchronous. packages are not available.
 Module 5: Counters and State machines

Asynchronous counters:
Asynchronous counters are those whose output is free from the clock signal. Because the flip-
flops in asynchronous counters are supplied with different clock signals, there may be a delay in
producing output. The number of logic gates required to design asynchronous counters is very
small. So they are simple in design. Another name for Asynchronous counters is “Ripple
counters”.

Two-bit ripple up-counter using a negative-edge-triggered flip-flop:

A two-bit ripple counter uses two flip-flops. There are four possible states in 2–bit up–counting:
00, 01, 10, and 11. For the up-counter the output of first flip-flop is connected as clock to the
next flip-flop as shown in the figure.

Logic diagram

Truth Table
Clock Counter Output
(CLK) Q1 Q0
Initially 0 0
1st 0 1
2nd 1 0
3rd 1 1
4th 0 0

Timing Diagram:

The counter is initially assumed to be at a state 00 where the outputs of the tow flip-flops are
noted as Q1Q0. Where Q1 forms the MSB and Q0 forms the LSB.

For the negative edge of the first clock pulse, output of the first flip-flop FF1 toggles its state.
Thus Q1 remains at 0 and Q0 toggles to 1 and the counter state are now read as 01.
 Module 5: Counters and State machines
During the next negative edge of the input clock pulse FF1 toggles and Q 0 = 0. The output Q0
being a clock signal for the second flip-flop FF2 and the present transition acts as a negative
edge for FF2 thus toggles its state Q1 = 1. The counter state is now read as 10.

For the next negative edge of the input clock to FF1 output Q 0 toggles to 1. But this transition
from 0 to 1 being a positive edge for FF2 output Q 1 remains at 1. The counter state is now read
as 11.

For the next negative edge of the input clock, Q 0 toggles to 0. This transition from 1 to 0 acts as a
negative edge clock for FF2 and its output Q 1 toggles to 0. Thus the starting state 00 is attained.
Figure shown below

Two-bit ripple down-counter using negative-edge-triggered flip-flop:

Logic diagram
Truth Table:

Clock Counter Output

(CLK) Q1 Q0
Initially 0 0
1st 1 1
2nd 1 0
3rd 0 1
4th 0 0
Timing Diagram:

A two-bit ripple down counter uses two flip-flops. There are four possible states in 2–bit down–counting:
11, 10, 01, and 00. For the down-counter the complemented output of first flip-flop is connected as clock
to the next flip-flop as shown in the figure.
 Module 5: Counters and State machines

The counter is initially assumed to be at a state 00 where the outputs of the tow flip-flops are noted as
Q1Q0. Where Q1 forms the MSB and Q0 forms the LSB.

For the negative edge of the first clock pulse, output of the first flip-flop FF1 toggles its state. Thus Q 1
remains at 0 and Q0 toggles to 1 and the counter state are now read as 01.

During the next negative edge of the input clock pulse FF1 toggles and Q 0 = 0. The output Q0 being a
clock signal for the second flip-flop FF2 and the present transition acts as a negative edge for FF2 thus
toggles its state Q1 = 1. The counter state is now read as 10.

For the next negative edge of the input clock to FF1 output Q 0 toggles to 1. But this transition from 0 to 1
being a positive edge for FF2 output Q1 remains at 1. The counter state is now read as 11.

For the next negative edge of the input clock, Q 0 toggles to 0. This transition from 1 to 0 acts as a
negative edge clock for FF2 and its output Q 1 toggles to 0. Thus the starting state 00 is attained. Figure
shown below

Design of a Mod-6 asynchronous counter using T FFs:

A mod-6 counter has six stable states: 000, 001, 010, 011, 100, and 101. When the sixth clock
pulse is applied, the counter temporarily goes to the 110 state, but immediately resets to 000
because of the feedback provided. it is ―divide by-6-counter‖, in the sense that it divides the
input clock frequency by [Link] requires three FFs, because the smallest value of n satisfying the
condition N ≤2n is n=3; three FFs can have 8 possible states, out of which only six are utilised,
and the remaining two states 110and 111 are invalid. If initially the counter is in the 000 state,
then after the first clock pulse, it goes to 001, after the second clock pulse, it goes to 010, and so
on.

After the sixth clock pulse it goes to 000. For the design, write the truth table with present state
outputs Q3, Q2 and Q1 as the variables, and reset R as the output and obtain an expression for R in
terms of Q3, Q2, and Q1that decides the feedback into be provided. From the truth table, R=Q 3Q2.
For active-low Reset, R‘ is used. The reset pulse is of very short duration, of the order of
nanoseconds and it is equal to the propagation delay time of the NAND gate used. The
expression for R can also be determined as follows.

R=0 for 000 to 101, R=1 for 110, and R=X=for111

Therefore, R=Q3Q2Q1‘+Q3Q2Q1=Q3Q2

The logic diagram of the Mod-6 counter is shown in the above figure

The truth table is as shown below.

 Module 5: Counters and State machines

Timing Diagram:

Mod-10 Asynchronous counter using T-flip-flops:

A Mod-10 counter is a decade counter. It also called a BCD counter or a divide-by-10 counter. It
requires four flip-flops (condition 10 ≤2n is n=4). So, there are 16 possible states, out of which
ten are valid and remaining six are invalid. The counter has ten stable state, 0000 through 1001,
i.e., it counts from 0 to 9. The initial state is 0000 and after nine clock pulses it goes to 1001.
When the tenth clock pulse is applied, the counter goes to state 1010 temporarily, but because of
the feedback provided, it resets to initial state 0000. So, there will be a glitch in the waveform of
Q2. The state 1010 is a temporary state for which the reset signal R=1, R=0 for 0000 to 1001, and
R=C for 1011 to 1111.

The count table is shown in Figure. The feedback is provided from second and fourth FFs. For
active –HIGH reset, Q4 and Q2 outputs are connected to NAND gate and the output of NAND
gate is connected to reset (CLR).
 Module 5: Counters and State machines

Timing Diagram:

Synchronous counters:
Asynchronous counters are serial counters. They are slow because each FF can change state only
if all the preceding FFs have changed their state. if the clock frequency is very high, the
asynchronous counter may skip some of the states. This problem is overcome in synchronous
counters or parallel counters. Synchronous counters are counters in which all the flip flops are
triggered simultaneously by the clock pulses Synchronous counters have a common clock pulse
applied simultaneously to all flip flops.

Design of synchronous counters:

Step 1:State Diagram: draw the state diagram showing all the possible states state diagram which
also be called nth transition diagrams, is a graphical means of depicting the sequence of states
through which the counter progresses.

Step2: number of flip-flops: based on the description of the problem, determine the required
number n of the flip-flops- the smallest value of n is such that the number of states N≤2 n--- and
the desired counting sequence.

Step3: choice of flip-flops excitation table: select the type of flip-flop to be used and write the
excitation table. An excitation table is a table that lists the present state (ps) , the next state(ns)
and required excitations.
 Module 5: Counters and State machines

Step4: minimal expressions for excitations: obtain the minimal expressions for the excitations of
the FF using K-maps drawn for the excitation of the flip-flops in terms of the present states and
inputs.

Step5: logic diagram: draw a logic diagram based on the minimal expressions
Design of a synchronous modulo-6 counter:

Step 1: the number of flip-flops: we know that the counting sequence for a modulo-6 counter is
000, 001, 010, 011, 100, and 101. It requires n=3FFs (N≤2 n, i.e., 6≤2*3). 3 FFs can have 8 states.
So the remaining two states, 110 and 111, are invalid. The entries for excitation corresponding to
invalid states are don‘t cares.

Step 2: the state diagram: the state diagram of the mod-6 counter is drawn as shown in figure.

Step3: type of flip-flop and the excitation table: JK flip-flops are selected and the excitation table
of the mod-6 counter using JK-flip-flops is shown in below.
 Module 5: Counters and State machines

Timing diagram:
 Module 5: Counters and State machines
Design of a synchronous modulo-6 counter:

Step 1: the number of flip-flops: we know that the counting sequence for a modulo-6 counter is
000, 001, 010, 011, 100, and 101. It requires n=3FFs (N≤2 n, i.e., 6≤2*3). 3 FFs can have 8 states.
So the remaining two states, 110 and 111, are invalid. The entries for excitation corresponding to
invalid states are don‘t cares.

Step 2: the state diagram: the state diagram of the mod-6 counter is drawn as shown in figure.

Step3: type of flip-flop and the excitation table: T flip-flops are selected and the excitation table of the
mod-6 counter using T-flip-flops is shown in below.

Step4: The minimal expressions: the K-maps for excitations of FFs T3,T2,and T1 in terms of outputs of
FFs Q3,Q2, and Q1, their minimization and the minimal expressions for excitations obtained from them
are shown below

[To be done by student]

Step5: The logic diagram based on those minimal expressions is drawn as shown in fig.

[To be done by student]

4 bit Ring Counter:

The ring counter is a cascaded connection of flip flops, in which the output of last flip flop is
connected to input of first flip flop. In ring counter if the output of any stage is 1, then its
reminder is 0. The Ring counters transfers the same output throughout the circuit.
That means if the output of the first flip flop is 1, then this is transferred to its next stage i.e. 2nd
flip flop. By transferring the output to its next stage, the output of first flip flop becomes 0. And
this process continues for all the stages of a ring counter. If we use n flip flops in the ring
counter, the ‘1’ is circulated for every n clock cycles.
 Module 5: Counters and State machines

The circuit diagram of the ring counter is shown below

Here we design the ring counter by using D flip flop. This is a Mod 4 ring counter which has 4 D
flip flops connected in series. The clock signal is applied to clock input of each flip flop,
simultaneously and the RESET pulse is applied to the CLR inputs of all the flip flops.

Operation of Ring Counter:

Initially, all the flip flops in ring counter are reset to 0 by applying CLEAR signal. Before
applying the clock pulse, we apply the PRESET pulse to the flip flops which assigns the value
‘1’ to the ring counter circuit. For each clock signal, the data circulates among all the 4 flip flop
stages of ring counter.
This 4 staged ring counter is called Mod 4 ring counter or 4 bit ring counter. To circulate the data
correctly in the ring counter, we must load the counter with required values like all 0’s or all 1’s.
Circulation of data in Ring counters

Truth table of ring counter:

The truth table of the 4 bit ring counter is explained below.

When CLEAR input CLR = 0, then all flip flops are set to 1. When CLEAR input CLR = 1, the
ring counter starts its operation. For one clock signal, the counter starts its operation. On next
clock signal, the counter again resets to 0000. Ring counter has 4 sequences: 0001, 0010, 0100,
1000, 000.
Timing Diagram:
 Module 5: Counters and State machines

State diagram of ring counter:

The state diagram of the 4 bit ring counter is shown in above picture. It denotes that the position
of the preset digit (in this case preset digit is 1) is changing its position from LSB to MSB, for
one clock signal.

Johnson Counter:
The Johnson counter is a modification of ring counter. In this the inverted output of the last stage
flip flop is connected to the input of first flip flop. If we use n flip flops to design the Johnson
counter, it is known as 2n bit Johnson counter or Mod 2n Johnson counter.
This is an advantage of the Johnson counter that it requires only half number of flip flops that of
a ring counter uses, to design the same Mod.
The main difference between the 4 bit ring counter and the Johnson counter is that, in ring
counter, we connect the output of last flip flop directly to the input of first flip flop. But in
Johnson counter, we connect the inverted output of last stage to the first stage input.
The Johnson counter is also known as Twisted Ring Counter, with a feedback. In Johnson
counter the input of the first flip flop is connected from the inverted output of the last flip flop.
The Johnson counter or switch trail ring counter is designed in such a way that it overcomes the
limitations of ring counter. Mainly it reduces the number of flip flops required for designing the
circuit.

Similar to the ring counter, the clock signal in Johnson counter is connected to the clock input of
each flip flop simultaneously.
Operation of Johnson counter
The Johnson counter designed with D flip flop is shown below. It has four stages i.e. four flip
flops connected in series type or cascaded. Initially zero / Null is fed to the Johnson counter and
on applying the clock signal, outputs will change to “1000”, “1100”, “1110”, “1111”, “0111”,
“0011”, “0001”, “0000” in a sequence and the sequence will repeat for next clock signal.
 Module 5: Counters and State machines
The Johnson counter produces a special pattern by passing four 0’s and then four 1’s and thus it
produces a special pattern by counting up down.
Truth table of Johnson counter
The truth table of the 4 bit ring counter is explained below.

Timing Diagram:

State diagram:

The state diagram indicates that how the data transfers from one flip flop to another for every
clock pulse. The4 stage Johnson ring counters are used as frequency dividers, by varying their
feedback connections. So they can be used as frequency divider circuits also.

Finite State Machines:

Finite State Machines are the fundamental building blocks of various digital and computing
systems. They provide a systematic approach to model the behavior of sequential circuits. They
also help to control various processes in digital systems.
 Module 5: Counters and State machines

What is a Finite State Machine?

A Finite State Machine (FSM) is a mathematical model that is used to explain and understand
the behavior of a digital system. More specifically, it is a structured and systematic model that
helps to understand the behavior of a sequential circuit that exists in a finite number of states at a
given point of time.

In simpler words, a synchronous sequential circuit is also called a Finite State Machine (FSM) if
it has a finite number of states.

The transition of these finite states takes place based on the internal or external inputs that result
in the predictable and systematic changes in the behavior of the system.

Components of a Finite State Machine:

A typical finite state machine consists of the following main components −
Finite States
The finite states are nothing but the distinct modes or conditions in the given system. Each of
these finite states represents a specific behavior. In digital system representation, these finite
states are generally represented through symbols or labels.
(or)
A state machine is composed of two or more states. A state stores information about the past and
reflects changes from the start of the system to the present state. The current state is determined
by past states of the system.

State Transitions
In terms of finite state machines, the state transition can be defined as the change from one state
to another. This change in state or state transition takes place based on some specific inputs or
conditions. These state transitions are generally triggered by events that are associated with some
rules or conditions and determine the next state of the system.

Inputs
The inputs to the finite state machines are the external signals that trigger the state transitions in
the system. These inputs are to be entered into the finite state machine by using sensors, user
input devices like mic, keyboard, etc.
Outputs
The results produced by the system as per the inputs and current states, are known as outputs.
These outputs of the system can be used to trigger events, control actuators, or to provide
feedback to the external environment.
 Module 5: Counters and State machines
State Diagram
The state transition and the behavior of a finite state machine can be represented in a graphical
form that is known as the state diagram of the finite state machine.
(or)
It is a pictorial representation of the relationship among the present, the external input, the next
state and the output of the state machine.

State table:
The state table representation of a sequential circuit consists of three sections labelled present
state, next state and output. The present state designates the state of flip-flops before the
occurrence of a clock pulse. The next state shows the states of flip-flops after the clock pulse,
and the output section lists the value of the output variables during the present state. The state
table for the above state diagram is shown below.

State Table

State minimization (reduction):

If next state & output of two present states are same (identical) then we can eliminate one state.
This process is called as state minimization.
The state reduction technique basically avoids the introduction of redundant states. The reduction
in redundant states reduce the number of required flip-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 equivalent, one of
them can be removed without altering the input-output relationship.

Example: Consider a sequential circuit whose specification is given in the state diagram of
Figure below. As shown in the diagram, the states are denoted by letter symbols instead of their
binary values, because in state reduction technique internal states are not important; but only
input-output sequences are important.
 Module 5: Counters and State machines

Step 1 : Determine the state table for the given state diagram. The table below shows the state
table for given state diagram

Step 2 : Find equivalent states

As mentioned earlier, in equivalent states every possible set of inputs generate exactly same output and
same next state. In the given circuit there are two input combinations : X = 0 and X = 1. Looking at the
state table for two present states that go to the same next state and have the same output for both input
combinations, we can easily find that states c and e are equivalent. This is because, c and e both states go
to states c and d and have outputs of 0 and 1 for X = 0 and X = 1, respectively. Therefore, state e can be
removed and replaced by c. The final reduced table is shown in Table below. The state diagram for the
reduced table consists of only four states and is shown in Figure below

Types of Finite State Machine

There are two types of finite state machines namely,
 Mealy State Machine
 Moore State Machine
.
Mealy State Machine:
A Finite State Machine is said to be a Mealy state machine, if its outputs depend on both present
inputs & present states. The block diagram of the Mealy state machine is shown in the following
figure −
 Module 5: Counters and State machines

As shown in the figure, there are two main parts presents in the Mealy state machine. Those are
combinational logic circuit and memory element. The memory element is useful to provide some
part of previous outputs and present states as inputs to the combinational logic circuit.
Based on the present inputs and present states, the Mealy state machine produces outputs.
Therefore, the outputs will be valid only at positive or negative transition of the clock signal.
State Diagram of Mealy State Machine
The state diagram of Mealy state machine is shown in the following figure.

In the above figure, there are three states, namely A, B and C. These states are labelled inside the
circles and each circle corresponds to one state. State transitions between these states are
represented with directed lines. Here, 0 / 0, 1 / 0 and 1 / 1 denote the input / output. In the above
figure, there are two state transitions from each state based on the value of input.
In general, the number of states required in Mealy state machine is less than or equal to the
number of states required in Moore state machine. There is an equivalent Moore state machine
for each Mealy state machine.

Moore State Machine:

A Finite State Machine is said to be a Moore state machine, if its outputs depend only on the
present states.
The block diagram of the Moore state machine is shown in the following figure −

As shown in above figure, there are two parts presents in a Moore state machine. Those are
combinational logic and memory. In this case, the present inputs and present states determine the
next states. So, based on next states, Moore state machine produces the outputs. Therefore, the
outputs will be valid only after transition of the state.
State Diagram of Moore State Machine
The state diagram of Moore state machine is shown in the following figure −
 Module 5: Counters and State machines

In the above figure, there are four states, namely A, B, C, and D. These states and the respective
outputs are labelled inside the circles. Here, only the input value is labeled on each transition. In
the above figure, there are two transitions from each state based on the value of input.
In general, the number of states required in Moore state machine is more than or equal to the
number of states required in Mealy state machine. There is an equivalent Mealy state machine
for each Moore state machine. So, based on the requirement we can use one of them.

Advantages of Finite State Machine:

The Finite State Machines have several advantages in the field of digital electronics. All these
advantages make them a crucial tool for modeling and implementing various digital systems.
Some key advantages of Finite State Machines are listed below −
 Finite state machines provide a simple and systematic way to model and understand the
behavior of digital systems with discrete finite states and transitions between them.
 Finite state machines support modular designs that help to breakdown the complex digital
systems into smaller components. Each component of the finite state machine can
represent a specific task of the entire system. This allows for easier design, testing, and
maintenance.
 Finite state machines provide ease in terms of scalability that allows for addition of new
states and transitions, and logics to the existing system without altering its fundamental
structure or operation. This becomes essential when the system requirement evolve or
expand.
 Fundamentally, finite state machines have a deterministic or predictable behavior. That
means, we can easily determine the next state of the system from its current state and the
inputs. This predictable behavior helps us to ensure the reliable and consistent operation
of the system. It also makes the finite state machines best suited for real-time and safety-
critical applications.
 Finite state machines are considered highly efficient in terms of both hardware and
software implementations, as they require minimal hardware and software resources such
as logic gates, memory, and other processing resources.
 Finite state machines support parallelism. This technology allows the occurrence of
multiple states and state transitions simultaneously within the system. It also optimizes
the performance and improves the responsiveness of the system.
 Finite state machines are versatile tools in the field of digital electronics and computer
science, as they find their applications in various fields such as digital system design,
control system design, software development, development of artificial intelligence, etc.

Applications of Finite State Machine:

In the field of digital electronics and computer science, the finite state machines are used in
various applications due to their ability to model sequential logic systems effectively. Here are
some examples of applications of finite state machines −
 Finite state machines are commonly used in designing and implementation of different
types of sequential logic circuits, such as digital counters, timers, control units, etc.
 Module 5: Counters and State machines
 Finite state machines are used in digital control systems to control and regulate the
behavior of complex automated systems, like robots, industrial control and automation
systems, etc.
 Finite state machines are used in the implementation of communication protocols like
network protocols and state-based digital systems like data transmission and protocol
converters.
 Finite state machines are also used in the field of software development to model and
define the behavior of state-based systems in applications, to create user interfaces, to
implement game mechanics, and to develop workflow management systems.

Assignment Questions:
1. Draw 2 bit binary asynchronous counter using T Flip Flops.
2. What is meant by a state table?
3. Draw the circuit diagram of 4-bit Johnson counter using D-flip flop and explain its
operation.
4. Design a MOD-10 (decade) counter and explain its operation.
5. Design a 4-bit ring counter using D-flip-flops and explain its operation.
6. Design a 3-bit asynchronous counter and explain it.
7. List out all the differences between Melay and Moore models
8. With suitable example explain the Mealy and Moore models?