MIT School of Computing
Department of Computer Science & Engineering
First Year Engineering
23CSE1105-Digital Electronics & Logic Design
Class - F.Y (SEM-II),
UnitPLD
- IV
Programmable Logic Devices and Algorithmic State
Machines
Prof.Tushar Mote
Subject Teacher
AY 2024-2025 SEM-II
Digital Electronics & Logic Design 1
MIT School of Computing
Department of Computer Science & Engineering
Unit-IV Syllabus
● ROM as PLD, Programmable Logic Array (PLA), Programmable Array
Logic (PAL), Designing combinational circuits using PLDs.
● Algorithmic State Machines: Finite State Machines (FSM) and ASM,
ASM charts, notations, construction of ASM chart and realization for
PLD
sequential circuits, Sequence Generator
Digital Electronics & Logic Design 2
MIT School of Computing
Department of Computer Science & Engineering
PROGRAMMABLE LOGIC DEVICES (PLD):
• A programmable logic device (PLD) is an electronic component used to build
reconfigurable digital circuits.
• Unlike digital logic constructed using discrete logic gates with fixed functions, a PLD
has an undefined function at the time of manufacture.
PLD
• Before the PLD can be used in a circuit it must be programmed to implement the
desired function.
• Compared to fixed logic devices, programmable logic devices simplify the design of
complex logic and may offer superior performance.
• Unlike for microprocessors, programming a PLD changes the connections made
between the gates in the device.
Digital Electronics & Logic Design 3
MIT School of Computing
Department of Computer Science & Engineering
Problems by Using Basic Gates:
Many components on PCB:
▪ As number of components PLD rises, nodes interconnection
complexity grows exponentially
▪ Growth in interconnection will cause an increase in
interference, PCB size, PCB design cost, and manufacturing
time
Digital Electronics & Logic Design 4
MIT School of Computing
Department of Computer Science & Engineering
Types of PLD :
• The purpose of a PLD device is to permit elaborate digital logic
designs to be implemented by the user in a single device.
• Can be erased electrically PLD
and reprogrammed with a new
design, making them very well-suited for academic and
prototyping
• Types of Programmable Logic Devices
ROM (Read Only Memory)
PAL (Programmable Array Logic)
PLA (Programmable Logic Array)
Digital Electronics & Logic Design 5
MIT School of Computing
Department of Computer Science & Engineering
PLD Configuration :
-They all have an input connection matrix, which
connects the inputs of the device to an array of AND
gates. PLD
-They all have an output connection matrix, which
connects the outputs of the AND-gates to the inputs of
OR gates, which drive the device's outputs.
Digital Electronics & Logic Design 6
MIT School of Computing
Department of Computer Science & Engineering
Read Only Memory or ROM
● a memory device, which collects binary information
permanently.
● That implies we cannot change that saved information by any
means later.
● If in case the ROM has a programmable
PLD feature, then it is
named Programmable ROM (PROM).
● This gives the user the flexibility to program the binary data
electrically once by applying for the PROM program.
Digital Electronics & Logic Design 7
MIT School of Computing
Department of Computer Science & Engineering
Read Only Memory or ROM
PLD
PROM is a programmable logic device that has a fixed AND array & a Programmable OR array.
Digital Electronics & Logic Design 8
MIT School of Computing
Department of Computer Science & Engineering
Difference Between PLD :
The differences between the first three categories are
these:
PLD
1. In a ROM, the input connection matrix is hardwired. The user
can modify the output connection matrix.
2. In a PAL the output connection matrix is hardwired. The user
can modify the input connection matrix.
3. In a PLA the user can modify both the input connection matrix
and the output connection matrix.
Digital Electronics & Logic Design 9
MIT School of Computing
Department of Computer Science & Engineering
Difference Between PLD :
Device AND-Array OR-Array
PLD
PROM FIXED Programmable
PAL Programmable FIXED
PLA Programmable Programmable
Digital Electronics & Logic Design 10
MIT School of Computing
Department of Computer Science & Engineering
The general structure of PLDs:
PLD
Digital Electronics & Logic Design 11
MIT School of Computing
Department of Computer Science & Engineering
Buffer/inverter:
PLD
(a) Symbol. (b) Logic equivalent.
Digital Electronics & Logic Design 12
MIT School of Computing
Department of Computer Science & Engineering
Rules to Design PLD’s:
Identify the total number of unique variables.
1. Calculate the total number of the input buffer Total no. of I/P
buffer=Total no. of unique variables.
PLD
2. Calculate the total number of AND Gate(AND Array) Total
no. of AND array=Total number of unique min terms.
3. Calculate the total number of OR Gate (OR Array) Total no.
of OR array=Total no. of output functions.
4. Dot (.) represents Fixed connection whereas cross(X)
represents Programmable Connection.
Digital Electronics & Logic Design 13
MIT School of Computing
Department of Computer Science & Engineering
Using a PROM for logic design:
F1= ∑m ( 0, 1, 2, 5, 7)
F2= ∑m( 1, 2, 4,6 )
Total No of I/p Buffer= 3
Total No of AND Array =8
Total No of OR Array=2
14
MIT School of Computing
Department of Computer Science & Engineering
Using a PROM for logic design: Full Adder using
Decoder IC
15
MIT School of Computing
Department of Computer Science & Engineering
Using a PAL for logic design:
F1= ∑m ( 0, 1, 2, 5, 7)
F2= ∑m( 1, 2, 4,6 )
Total No of I/p Buffer= 3
Total No of AND Array = 8
Total No of OR Array = 2
16
MIT School of Computing
Department of Computer Science & Engineering
Using a PLA for logic design:
F1= ∑m ( 0, 1, 2, 5, 7)
F2= ∑m( 1, 2, 4,6 )
Total No of I/p Buffer= 3
Total No of AND Array =8
Total No of OR Array=2
17
MIT School of Computing
Department of Computer Science & Engineering
Comparison between PROM, PLA and PAL
18
MIT School of Computing
Department of Computer Science & Engineering
Advantages of Programmable Logic Devices:
• Design Flexibility: PLDs offer customers much more flexibility
during the design cycle because design iterations are simply a
matter of changing the programming file, and the results of design
changes can be seen immediatelyPLD
in working parts.
• Improved Reliability: Lower power plus fewer interconnections
and packages translate into greatly improved system reliability.
• Lower Power: CMOS and fewer packages combine to reduce
power consumption.
Digital Electronics & Logic Design 19
MIT School of Computing
Department of Computer Science & Engineering
Advantages of Programmable Logic Devices:
• Reduced complexity: Since PLDs consume lower power
requirements less board space simpler testing procedures.
• PLDs are field-programmable PLDi. e. can be programmed outside
of the manufacturing environment
• PLDs are erasable and reprogrammable i.e allowing updating
a device or correction of errors and allowing to reuse of the device
for a different design – the ultimate in reusability!
Connection.
Digital Electronics & Logic Design 20
MIT School of Computing
Department of Computer Science & Engineering
Finite Sate Machin (FSM) and Algorithmic State Machines (ASM)
• The state diagrams and tables use are convenient for describing the behaviour of
FSMs that have only a few inputs and outputs.
• For larger machines the designers often use a different form of representation, called
the algorithmic state machine (ASM) chart.
Finite Sate Machin (FSM)
A Finite State Machine (FSM) is a computational model used to design both computer programs and
PLD
sequential logic circuits. It operates by transitioning between different states based on inputs, making it an
essential tool in digital system design and software development. Finite State Machines are necessary
because they offer a structured approach to designing systems with a predictable sequence of operations.
FSM Consists of
▪ States: Represent different conditions or modes of the system.
▪ Transitions: The movement from one state to another based on specific conditions.
▪ Input symbols: Events that trigger state transitions.
▪ Initial state: The starting state of the FSM.
▪ Final state: A state where the machine halts or finishes its process.
Digital Electronics & Logic Design 21
MIT School of Computing
Department of Computer Science & Engineering
State Diagram
A state diagram describes a state machine using a graphical representation.
1
0 1
S0 S1
State Table
PLDmachine in a tabular format.
A state transition table (or state table) describes a state
Present State Next State
x=0 x=1
S0 S0 S1
S1 S0 S1
(where x is the input)
Digital Electronics & Logic Design 22
MIT School of Computing
Department of Computer Science & Engineering
Types of Finite State Machine
Melay Machine:
The Mealy Machine is a type of FSM where the output depends on both the
current state and the current input. This makes the system more responsive to immediate
inputs, providing real time feedback.
Characteristics:
• Output depends on the current input and state.
• Useful in systems where outputs need to respond directly to inputs.
PLD
Moore Machine:
In contrast to the Mealy Machine, the Moore Machine produces an output
solely based on the current state, ignoring the input. The output changes only when the
state changes.
Characteristics:
• Output depends only on the current state.
• More predictable, as it doesn't react immediately to inputs.
Digital Electronics & Logic Design 23
MIT School of Computing
Department of Computer Science & Engineering
Mealy Machine
• The advantage of a Mealy machine is in its implementation.
• A Mealy machine often results in a reduced number of states.
• The output of a Mealy machine depends on the input and the current state.
• Therefore, the output will be coupled with the input and depicted on the transition
between states as shown in Figure PLD
Next State
Logic Output Logic
Input(s) (Combinational Memory Output(s)
Circuit) (Combinational
circuit)
Figure - block diagram of Mealy machine
Digital Electronics & Logic Design 24
MIT School of Computing
Department of Computer Science & Engineering
Mealy Machine Example
Sate diagram implementation of {1 0 1} sequence detector with a Mealy
machine.
1/0
0 1/0
S
S̀0 1 Present State Next State Output
x=0 x=1 x=0 x=1
1/1 PLD S0 S0 S1 0 0
S1 S2 S1 0 0
S2 S0 S1 0 1
0/0
(where x is the input)
0/0
S2
Digital Electronics & Logic Design 25
MIT School of Computing
Department of Computer Science & Engineering
Moore Machine
• The advantage of a Moore machine is a simplification of behaviour.
• The output of a Moore machine depends only on the current state.
• Therefore, the output is coupled with a state and which is solely depend on present
state only .
PLD
Input(s) Output(s)
Figure - block diagram of Moore machine
Digital Electronics & Logic Design 26
MIT School of Computing
Department of Computer Science & Engineering
Moore Machine Example
Sate diagram implementation of {1 0 1} sequence detector with a Moore
machine.
1
0 1
S0 S1
0 Present State Next State Output
0 0 x=0 x=1
S0 S0 S1
PLD S1 S2 S1
0
0
S2 S0 S3 0
0 S3 S2 S0 1
(where x is the input)
S3 S2
1 0
Digital Electronics & Logic Design 27
MIT School of Computing
Department of Computer Science & Engineering
Parameters Mealy Machine Moore Machine
Output Dependency Output depends on both the current state Output depends only on the current state.
and the input.
Response Time Faster response as output can change Slight delay in output change as it only
immediately when the input changes. depends on state change.
Number of States Typically requires fewer states because Requires more states because each output
different outputs can be produced from the must have its own state, leading to an
PLD
same state based on the input. increase in state count.
Hardware Requirements Requires fewer states, thus generally needs Requires more states, thus generally
less hardware needs more hardware
Complexity Slightly more complex to design and Simpler design and analysis since the
analyze due to the interaction between output depends solely on the state,
state and input for determining output. making the system more natural.
Example Used in systems requiring fast response to Common in systems where output
inputs like traffic light control or stability is crucial, like elevator control
communication protocols. or finite state machines for counters.
Digital Electronics & Logic Design 28
MIT School of Computing
Department of Computer Science & Engineering
Sequential circuit design procedure
Step 1: Make a state table based on the problem statement. The table should
show the present states, inputs, next states and outputs. (It may be easier to
find a state diagram first, and then convert that to a table.)
Step 2: Assign binary codes to the states in the state table, if you haven’t
already. If you have n states, your binary codes will have at least
log2 n digits, and your circuit will
PLD have at least log2 n flip-flops.
Step 3: For each flip-flop and each row of your state table, find the flip-flop
input values that are needed to generate the next state from the present state.
You can use flip-flop excitation tables here.
Step 4: Find simplified equations for the flip-flop inputs and the outputs.
Step 5: Build the circuit.
Digital Electronics & Logic Design 29
MIT School of Computing
Department of Computer Science & Engineering
Example: Design “11” Sequence detector using FSM
Step1 : Drawing state diagram
The state diagram is drawn by considering Melay FSM design approach. ‘w’ is input and ‘z’ is
output
PLD
Step 2 : Generation of State Table
By referring state diagram state table prepared which provides information of state change
with respect to input.
Digital Electronics & Logic Design 30
MIT School of Computing
Department of Computer Science & Engineering
Step 3: State excitation table
In this step from state table state excitation table is prepared . The state encoding is carried out
Present State (y) Next State (Y)
Input (w) D FF I/P Output (z)
Q Q+
0 0 0 0 0
0 1 0 0 0
1
PLD 0 1 1 0
1 1 1 1 1
Step 4 : K map implementation
Using excitation table K map drawn for logical circuit diagram connection. K map
for D FF and ‘z’ output
Digital Electronics & Logic Design 31
MIT School of Computing
Department of Computer Science & Engineering
Step 5 : Logic circuit diagram
From the k-map we can design the logical circuit connection diagram.
PLD
Digital Electronics & Logic Design 32
MIT School of Computing
Department of Computer Science & Engineering
Algorithmic State Machines (ASM)
ASM stands for 'Algorithm State Machine 'or simply state machine is another
name given to sequential network is used to control a digital system which
carries out a step by a step –by step procedure .It should be noted that ASM
charts represent physical hardware and offers several advantages.
1. Operation of a digital system can be easily understood by inspection of
PLD
the SM chart .
2. ASM charts represent physical hardware.
3. The ASM chart are equivalent to a state graph, and it leads directly to a
hardware realization .
4. ASM charts can be described the operation of both combinational and
sequential circuits .
5. ASM charts are easier to understand and can be converted several
equivalent form.
6. The ASM chart may be equivalently expressed as a state and output table .
Digital Electronics & Logic Design 33
MIT School of Computing
Department of Computer Science & Engineering
ASM (algorithmic state machine)
– Three basic elements: state box, decision box and conditional
box
• State and decision boxes used in conventional flowcharts
• Conditional box characteristicPLD
to ASM
State box
• Used to indicate states in control sequence
Register operations and output signals used to control generation
of next state written
Digital Electronics & Logic Design 34
MIT School of Computing
Department of Computer Science & Engineering
Elements of ASM Chart:
State box – A rectangle represents a state of the FSM. It is equivalent to a node in the
state diagram or a row in the state table. The name of the state is indicated outside the
box in the top-left corner.
Decision box –A diamond indicates that the stated
condition expression is to be tested and the exit path is
to be chosen accordingly. The condition expression
PLD
consists of one or more inputs to the FSM.
Conditional output box – An oval denotes the
output signals that are of Mealy type. These outputs
depend on the values of the state variables and the
inputs of the FSM; we will refer to these outputs
simply as Mealy outputs. The condition that
determines whether such outputs are generated is
specified in a decision box.
Digital Electronics & Logic Design 35
MIT School of Computing
Department of Computer Science & Engineering
State box
• Represents one state in the ASM.
• May have an optional state output list.
PLD
• Single entry.
• Single exit to state or decision boxes.
Digital Electronics & Logic Design 36
MIT School of Computing
Department of Computer Science & Engineering
State box
PLD
Digital Electronics & Logic Design 37
MIT School of Computing
Department of Computer Science & Engineering
The DecisionBox
•Indicated with a diamond shape
•Used for a condition expression that must be tested
•The exit path is chosen based on the outcome of the test
•Two or more outputs represent PLD exit paths dependant on
value of condition in decision box
•Two paths for binary based conditions
•The condition is on one or more inputs to the FSM
Digital Electronics & Logic Design 38
MIT School of Computing
Department of Computer Science & Engineering
The DecisionBox
PLD
Symbol Alternate Symbol
Digital Electronics & Logic Design 39
MIT School of Computing
Department of Computer Science & Engineering
The Conditional OutputBox
• Indicated with an oval shape
• Used for a Mealy-type output signals
• Not used for a Moore-type output signals
• The outputs depend on PLD the state variables and
inputs
• The condition that determines when such outputs
are generated is placed in a separate decision box
• It is mostly use for high (1) output state.
Digital Electronics & Logic Design 40
MIT School of Computing
Department of Computer Science & Engineering
The Conditional OutputBox
PLD
Digital Electronics & Logic Design 41
MIT School of Computing
Department of Computer Science & Engineering
ASM Example: Conversion of state diagram into ASM chart
PLD
Figure: State diagram
The output, z, is equal to 1 when the machine is in state B and w = 1.
This is indicated using the conditional output box. In all other cases
the value of z is 0, which is implied by not specifying z as an output
of state B for w = 0 and state A for w equal to 0 or 1.
Figure: ASM chart
Digital Electronics & Logic Design 42
MIT School of Computing
Department of Computer Science & Engineering
Asm Chart for JK Flipflop
State table and diagram
Present Qn Qn+1 J K
Inputs Output
state
0 0 0 x
Q+
J K Q 0 1 1 x
(Output)
0 0 0 0 1 0 x 1
0 0 1 1 1 1 x 0
PLD
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
Digital Electronics & Logic Design 43
MIT School of Computing
Department of Computer Science & Engineering
Asm Chart for D Flipflop
PLD
Digital Electronics & Logic Design 44
MIT School of Computing
Department of Computer Science & Engineering
ASM Chart for 2 Bit UP Counter
Present Input Next State
State (t) (t+1)
A B X(CLK A B
) (X= 1)
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1 PLD
0 1 1 1 0
1 0 0 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 0
Digital Electronics & Logic Design 45
MIT School of Computing
Department of Computer Science & Engineering
111 Sequence Detector-Mealy machine
PLD
Digital Electronics & Logic Design 46
MIT School of Computing
Department of Computer Science & Engineering
Draw ASM Chart for Below state Diagram
PLD
Digital Electronics & Logic Design 47
MIT School of Computing
Department of Computer Science & Engineering
Summary
❑ A state machine is a model used to describe the behaviour of a real-world system. State machines are used to
solve a large number of problems. They are used to model the behaviour of various types of devices such as
electronic control devices, parsing of communications protocols and programs that perform text or pattern
searches.
❑ State machines may be described using a state diagram and a state table. A state diagram is composed of
states, inputs, outputs and transitions between states.PLD
A state table describes a state machine with the present
state and input on the left and the next state and output on the right.
❑ State machines may be implemented using either a hardware architecture or a software architecture. The
advantage of a hardware implementation is that it operates very fast, but it is difficult to modify and usually
requires more circuit board space. The advantage of a software implementation is that it is easier to design
and modify, but can be slower than the hardware equivalent.
Digital Electronics & Logic Design 48
Thank You
Digital Electronics & Logic Design 49
