ZeePedia

Moore Machine State Diagram, Mealy Machine State Diagram, Karnaugh Maps

<< D FLIP-FLOP BASED IMPLEMENTATION
SHIFT REGISTERS: Serial In/Shift Left,Right/Serial Out Operation >>
img
CS302 - Digital Logic & Design
Lesson No. 33
STATE ASSIGNMENT
Each state in a sequential circuit is identified by a unique combination of binary bits.
Unless the output of the sequential is directly taken form the flip-flop outputs such as counters,
the states can be selected to allow minimum bit changes when changing from one state to the
other. Keeping the bits changes to minimum when changing from one state to the next, results
in simpler combinational circuits that determine the next state. Consider the example
discussed earlier having states a, b, c, d and f. Since we are interested in only the input and
output sequence, therefore it is immaterial how states a, b, c, d and f are uniquely identified.
Three possible state assignments are shown. Table 33.1. The Next-State, flip-flop input tables
for the three state assignments are shown. Table 33.2, 33.3 and33.4.
State
State
State
State
Assignment 1
Assignment 2
Assignment 3
a
000
001
000
b
001
010
001
c
010
011
011
d
011
100
010
f
100
110
110
Table 33.1 Three possible state assignments for states a, b, c, d and f
Present
Next State
D flip-flop Inputs
Output
State
X=0
X=1
X=0
X=1
X=0
X=1
000
100
001
1000010
0
001
001
010
0010101
1
010
000
100
0001000
1
011
010
011
0100111
0
100
011
010
0110100
0
Table 33.2a  Next State flip-flop input table for first State Assignment
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
0
0
1
0
00
1
0
0
0
01
0
0
1
1
01
0
1
0
0
11
x
x
x
x
11
x
x
x
x
10
1
1
x
x
10
0
0
x
x
D  2 = Q  2 Q1 Q  0 x + Q1 Q  0 X
D1 = Q  2 + Q  0 X + Q1Q  0
Q2Q1/Q0X
00
01
11
10
00
0
1
0
1
01
0
0
1
0
11
x
x
x
x
10
1
0
x
x
D0 = Q  2 Q  0 X + Q1Q  0 X + Q1Q  0 X + Q  2 Q1 Q  0 X
Table 33.2b
Karnaugh Maps and D flip-flop input Boolean expressions for the first State
Assignment
335
img
CS302 - Digital Logic & Design
Present
Next State
D flip-flop Inputs
Output
State
X=0
X=1
X=0
X=1
X=0
X=1
001
110
010
11
0
01
0
0
0
010
010
011
01
0
01
1
1
1
011
001
110
00
1
11
0
0
1
100
011
100
01
1
10
0
1
0
110
100
011
10
0
01
1
0
0
Table 33.3a
Next State flip-flop input table for second State Assignment
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
x
x
1
1
00
x
x
0
1
01
1
1
1
0
01
0
0
1
0
11
0
1
x
x
11
1
0
x
x
10
1
0
x
x
10
0
1
x
x
D  2 = Q  2 Q1 x + Q1Q  0 X + Q  2Q1 X + Q  2 Q1 X
D1 = Q  2 Q  0 + Q1Q  0 + Q1 X + Q1 X
Q2Q1/Q0X
00
01
11
10
00
x
x
0
0
01
0
1
0
1
11
0
1
x
x
10
1
0
x
x
D0 = Q  2 Q1 X + Q1 Q  0 X + Q1Q  0 X
Table 33.3b
Karnaugh Maps and D flip-flop input Boolean expressions for the second State
Assignment
Present
Next State
D flip-flop Inputs
Output
State
X=0
X=1
X=0
X=1
X=0
X=1
000
110
001
11
0
00
1
0
0
001
001
011
00
1
01
1
1
1
011
000
110
00
0
11
0
0
1
010
011
010
01
1
01
0
1
0
110
010
011
01
0
01
1
0
0
Table 33.4a
Next State flip-flop input table for third State Assignment
336
img
CS302 - Digital Logic & Design
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
1
0
1
0
00
1
0
0
0
01
1
1
1
0
01
0
0
1
0
11
1
1
x
x
11
0
0
x
x
10
x
x
x
x
10
x
x
x
x
D  2 = Q1 Q  0 x + Q1Q  0 X
D1 = Q  0 x + Q  0 X + Q1 Q  0
Q2Q1/Q0X
00
01
11
10
00
0
1
1
1
01
1
0
0
0
11
0
1
x
x
10
x
x
x
x
D0 = Q  2Q1 Q  0 x + Q  2 X + Q1Q  0 + Q1 X
Table 33.4b
Karnaugh Maps and D flip-flop input Boolean expressions for the third State
Assignment
The third State Assignment is shown to have simpler input Boolean expressions
leading to a simpler combinational circuit. Generally, the selection of State Assignment is
based on the following guidelines.
·  Choose an initial coded state into which the state machine (sequential circuit) can easily be
forced to reset (000 or 111)
·  Minimize the State Variables that change on each transition
·  Maximize the number of state variables that don't change in a group of related states
·  If there are unused states, then choose the best state variable combinations to achieve the
first three goals.
Moore Machine
State Diagram
The state diagram of a Moore Machine is shown. Figure 33.1. The Clocked
Synchronous Sequential Circuit has six states. On each clock transition the machine
sequences through the states 011, 111, 001, 010, 100 and 110. The outputs of the flip-flops
represent the sequential circuit output.
337
img
CS302 - Digital Logic & Design
Figure 33.1
State diagram of a Moore Machine
Next-State Table
The Next-State table is derived from the State diagram. The present and the
corresponding next states to which the sequential circuit changes at each clock transition are
shown. Table 33.5
Karnaugh Maps
The flip-flop input table based on J-K flip-flops is shown. Table 33.6. J-K flip-flop
transition table is used to determine the J-K flip-flop inputs. The Karnaugh maps for each of
the three J and K inputs of the three J-K flip-flops are shown along with the Boolean
expressions. Table 33.7
Present State
Next State
Q2
Q1
Q0
Q2
Q1
Q0
0
1
1
1
1
1
1
1
1
0
0
1
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
0
0
1
1
Table 33.5
Next-State table of the Moore Machine
Present State
Next State
J-K flip-flop inputs
Q2
Q1
Q0
Q2
Q1
Q0
J2
K2
J1
K1
J0
K0
0
1
1
1
1
1
1
x
x
0
x
0
1
1
1
0
0
1
x
1
x
1
x
0
0
0
1
0
1
0
0
x
1
x
x
1
0
1
0
1
0
0
1
x
x
1
0
x
1
0
0
1
1
0
x
0
1
x
0
x
1
1
0
0
1
1
x
1
x
0
1
x
Table 33.6
J-K flip-flop input table for the Moore Machine
338
img
CS302 - Digital Logic & Design
Q2Q1/Q0
0
1
Q2Q1/Q0
0
1
00
x
0
00
x
x
01
1
1
01
x
x
11
x
x
11
1
1
10
x
x
10
0
x
J2 = Q1
K  2 = Q1
Table 33.7a
Karnaugh Map for J2 and K2 inputs
Q2Q1/Q0
0
1
Q2Q1/Q0
0
1
00
x
1
00
x
x
01
x
x
01
1
0
11
x
x
11
0
1
10
1
x
10
x
x
J1 = 1
K1 = Q  2 Q  0 + Q  2Q0
Table 33.7b
Karnaugh Map for J1 and K1 inputs
Q2Q1/Q0
0
1
Q2Q1/Q0
0
1
00
x
1
00
x
x
01
x
0
01
0
x
11
x
0
11
1
x
10
x
x
10
0
x
J0 = Q  2Q1
K  0 = Q1
Table 33.7c
Karnaugh Map for J0 and K0 inputs
Implementation
The circuit and timing diagram of the State Machine is shown. Figure 33.2. The
sequential circuit is assumed to be reset to state 011. At interval t1, J-K input of the first flip-flop
is set at 0 and 0 respectively; therefore at the clock transition the output of the first flip-flop
remains unchanged. The J input of the second flip-flop is permanently connected to logic 1,
the K input is set at logic 0, therefore the output of the second flip-flop is set to logic 1 at the
clock transition t1. The J-K input of the third flip-flop is set to logic 1, at clock transition t1 the
output of the flip-flop changes to logic 1. The operation of the sequential circuit can be similarly
verified for intervals t2 to t7.
339
img
CS302 - Digital Logic & Design
Figure 33.2a Implementation of the Moore Machine
Figure 33.2b Timing diagram of the Moore Machine
Mealy Machine
State Diagram
The sequential circuit represented earlier as a Moore Machine is described as a Mealy
Machine. Figure 33.3. The output of a Mealy machine depends upon the present state at the
inputs. The state diagram shows the six states. When the input is 1, the machine switches
from its present state to the next. If the input is 0, the machine remains in its present state. The
outputs of the machine when it switches to the next state or it remains the present state are
shown with the directed arrows. For, example at state `a', when the input is 1 the machine
changes to the next state and the output is set to 111. When the input is set at 0, the machine
remains in its current state with outputs 011.
340
img
CS302 - Digital Logic & Design
Figure 33.3
State diagram of a Mealy Machine
Next-State Table
The Next-State table for the Mealy Machine is shown. Table 33.8. The Next-State table
is directly derived from the State diagram. The present state, and the corresponding next state
when the input X=0 and X=1 are shown in separate columns respectively. Similarly, the Moore
Machine outputs are also shown for each present state when the inputs are X=0 and X=1
respectively.
Present
Next State
Output
State
X=0
X=1
X=0
X=1
a
a
b
011
111
b
b
c
111
001
c
c
d
001
010
d
d
e
010
100
e
e
f
100
110
f
f
a
110
011
Table 33.8
Next-State table of a Mealy Machine
State Assignments
Based on the guidelines for State Assignment, States are assigned keeping the bit
changes to minimum. The corresponding next states for input X=0 and X=1 are also shown.
Table 33.9.
Present
Next State
State
X=0
X=1
000
000
001
001
001
011
011
011
010
010
010
110
110
110
100
100
100
000
Table 33.9
State Assignments for the Mealy Machine
341
img
CS302 - Digital Logic & Design
Karnaugh Maps
The J-K flip-flop input tables for the Mealy Machine are shown. Table 33.10. The J-K
inputs for the three flip-flops are based on the J-K flip-flop transition tables.
Present
Next State
J-K flip-flop inputs
Output
State
X=0
X=0
X=0
Q2  Q1
Q0  Q2   Q1   Q0   J2
K2
J1
K1
J0
K0
O2
O1
O0
0
0
0
0
0
0
0
x
0
x
0
x
0
1
1
0
0
1
0
0
1
0
x
0
x
x
0
1
1
1
0
1
1
0
1
1
0
x
x
0
x
0
0
0
1
0
1
0
0
1
0
0
x
x
0
0
x
0
1
0
1
1
0
1
1
0
x
0
x
0
0
x
1
0
0
1
0
0
1
0
0
x
0
0
x
0
x
1
1
0
Table 33.10a J-K flip-flop input table for the Moore Machine (X=0)
Present
Next State
J-K flip-flop inputs
Output
State
X=1
X=1
X=1
Q2  Q1
Q0
Q2   Q1   Q0
J2
K2
J1
K1
J0
K0
O2
O1
O0
0
0
0
0
0
1
0
x
0
x
1
x
1
1
1
0
0
1
0
1
1
0
x
1
x
x
0
0
0
1
0
1
1
0
1
0
0
x
x
0
x
1
0
1
0
0
1
0
1
1
0
1
x
x
0
0
x
1
0
0
1
1
0
1
0
0
x
0
x
1
0
x
1
1
0
1
0
0
0
0
0
x
1
0
x
0
x
0
1
1
Table 33.10b J-K flip-flop input table for the Moore Machine (X=1)
The Karnaugh maps for the three sets of J-K inputs and the three outputs are shown.
The Boolean expressions are written along with the Karnuagh maps. Table 33.11
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
0
0
0
0
00
x
x
x
x
01
0
1
0
0
01
x
x
x
x
11
x
x
x
x
11
0
0
x
x
10
x
x
x
x
10
0
1
x
x
J2 = Q1 Q  0 X
K  2 = Q1 X
Table 33.11a Karnaugh Map for J2 and K2 inputs
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
0
0
1
0
00
x
x
x
x
01
x
x
x
x
01
0
0
0
0
11
x
x
x
x
11
0
1
x
x
10
0
0
x
x
10
x
x
x
x
K1 = Q  2 X
J1 = Q  0 X
Table 33.11b Karnaugh Map for J1 and K1 inputs
342
img
CS302 - Digital Logic & Design
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
0
1
x
x
00
x
x
0
0
01
0
0
x
x
01
x
x
1
0
11
0
0
x
x
11
x
x
x
x
10
0
0
x
x
10
x
x
x
x
J0 = Q  2 Q1 X
K  0 = Q1 X
Table 33.11c Karnaugh Map for J0 and K0 inputs
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
1
1
0
1
00
0
1
0
1
01
1
0
1
0
01
0
1
0
0
11
0
1
x
x
11
1
1
x
x
10
1
1
x
x
10
1
0
x
x
O  2 = Q  2 X + Q  2Q1 + Q  2 Q  0 X + Q1Q  0 X
O1 = Q1Q  0 X + Q  2 Q  0 X + Q  2 X + Q1 Q  0 + Q1 X
Q2Q1/Q0X
00
01
11
10
00
1
1
1
1
01
0
0
0
1
11
0
0
x
x
10
0
1
x
x
O  0 = Q1 X + Q  2 Q1 + Q  0 X
Table 33.11d Karnaugh Map for O2, O1 and O0 outputs
Implementation
The implementation of the Mealy Machine is shown. Figure 33.4. The circuit shows
only the part of the circuit that allows the Mealy Machine to switch from its current state to the
next state. The operation of the machine can be verified with the help of the timing diagram.
343
img
CS302 - Digital Logic & Design
X
Q0
Q1
Q2
SET
SET
SET
Q
Q
Q
flip-flop 1
flip-flop 2
flip-flop 3
Q
Q
Q
CLR
CLR
CLR
CLK
Figure 33.4a Implementation of the Mealy Machine
The machine is assumed to be reset to state `a' 000. At interval t1, J-K inputs of the first
flip-flop are set at logic 1 and 0 respectively, therefore at the clock transition the output of the
first flip-flop switches from 0 to 1. The J-K inputs of the second flip-flop are set at logic at logic
0 and 0 respectively, thus the output state of the second flip-flop remains unchanged at the
clock transition. The J-K inputs of the third flip-flop are set to logic 0 and 1 respectively, thus at
clock transition t1 the flip-flop is reset to logic 0. Transition at intervals t2 to t7 can similarly be
verified.
CLOCK
Input
Q0
Output
Q1
Output
Q2
Output
t2
t3
t4
t5
t6
t7
t8
t1
Figure 33.4b Timing diagram of the Mealy Machine
The circuit which implements the Mealy Machine outputs has not been shown. The
machine outputs are implemented through the three Boolean expressions for outputs O2, O1
and O0 respectively. At interval t1, before the clock transition, Q0, Q1 and Q2 outputs are set at
logic 0, 0 and 0 respectively. When the X input is logic 0, the output of Boolean expression for
344
img
CS302 - Digital Logic & Design
O2, O1 and O0 is 0, 1 and 1 respectively. At the clock transition t1 when the X input is set to 1,
the output O2, O1 and O0 is set to 1, 1 and 1. The outputs for all six states `a', `b', `c', `d', `e' and
`f' can similarly be verified.
345
Table of Contents:
  1. AN OVERVIEW & NUMBER SYSTEMS
  2. Binary to Decimal to Binary conversion, Binary Arithmetic, 1’s & 2’s complement
  3. Range of Numbers and Overflow, Floating-Point, Hexadecimal Numbers
  4. Octal Numbers, Octal to Binary Decimal to Octal Conversion
  5. LOGIC GATES: AND Gate, OR Gate, NOT Gate, NAND Gate
  6. AND OR NAND XOR XNOR Gate Implementation and Applications
  7. DC Supply Voltage, TTL Logic Levels, Noise Margin, Power Dissipation
  8. Boolean Addition, Multiplication, Commutative Law, Associative Law, Distributive Law, Demorgan’s Theorems
  9. Simplification of Boolean Expression, Standard POS form, Minterms and Maxterms
  10. KARNAUGH MAP, Mapping a non-standard SOP Expression
  11. Converting between POS and SOP using the K-map
  12. COMPARATOR: Quine-McCluskey Simplification Method
  13. ODD-PRIME NUMBER DETECTOR, Combinational Circuit Implementation
  14. IMPLEMENTATION OF AN ODD-PARITY GENERATOR CIRCUIT
  15. BCD ADDER: 2-digit BCD Adder, A 4-bit Adder Subtracter Unit
  16. 16-BIT ALU, MSI 4-bit Comparator, Decoders
  17. BCD to 7-Segment Decoder, Decimal-to-BCD Encoder
  18. 2-INPUT 4-BIT MULTIPLEXER, 8, 16-Input Multiplexer, Logic Function Generator
  19. Applications of Demultiplexer, PROM, PLA, PAL, GAL
  20. OLMC Combinational Mode, Tri-State Buffers, The GAL16V8, Introduction to ABEL
  21. OLMC for GAL16V8, Tri-state Buffer and OLMC output pin
  22. Implementation of Quad MUX, Latches and Flip-Flops
  23. APPLICATION OF S-R LATCH, Edge-Triggered D Flip-Flop, J-K Flip-flop
  24. Data Storage using D-flip-flop, Synchronizing Asynchronous inputs using D flip-flop
  25. Dual Positive-Edge triggered D flip-flop, J-K flip-flop, Master-Slave Flip-Flops
  26. THE 555 TIMER: Race Conditions, Asynchronous, Ripple Counters
  27. Down Counter with truncated sequence, 4-bit Synchronous Decade Counter
  28. Mod-n Synchronous Counter, Cascading Counters, Up-Down Counter
  29. Integrated Circuit Up Down Decade Counter Design and Applications
  30. DIGITAL CLOCK: Clocked Synchronous State Machines
  31. NEXT-STATE TABLE: Flip-flop Transition Table, Karnaugh Maps
  32. D FLIP-FLOP BASED IMPLEMENTATION
  33. Moore Machine State Diagram, Mealy Machine State Diagram, Karnaugh Maps
  34. SHIFT REGISTERS: Serial In/Shift Left,Right/Serial Out Operation
  35. APPLICATIONS OF SHIFT REGISTERS: Serial-to-Parallel Converter
  36. Elevator Control System: Elevator State Diagram, State Table, Input and Output Signals, Input Latches
  37. Traffic Signal Control System: Switching of Traffic Lights, Inputs and Outputs, State Machine
  38. Traffic Signal Control System: EQUATION DEFINITION
  39. Memory Organization, Capacity, Density, Signals and Basic Operations, Read, Write, Address, data Signals
  40. Memory Read, Write Cycle, Synchronous Burst SRAM, Dynamic RAM
  41. Burst, Distributed Refresh, Types of DRAMs, ROM Read-Only Memory, Mask ROM
  42. First In-First Out (FIFO) Memory
  43. LAST IN-FIRST OUT (LIFO) MEMORY
  44. THE LOGIC BLOCK: Analogue to Digital Conversion, Logic Element, Look-Up Table
  45. SUCCESSIVE –APPROXIMATION ANALOGUE TO DIGITAL CONVERTER