 | This article provides insufficient context for those unfamiliar with the subject. |
 |
A fairly simple procedure to reduce the number of states in a state machine transition table.
A partition denoted p1...p2...p3..etc. consists of one or more blocks where each block contains that may be equivalent but the states in a given block are definitely not equivalent to another block.
This is done by partitioning.
The first block, p1, will always be every state on the table FIG. 1
p1: [ABCDEFG]
The second block is achieved by grouping states with the same output p2: [ABD][CEFG]
as you can see A, B and D all have 1 as an output p3: [ABD][CEG][F]
and C, E, F and G all have 0. p4: [AD][B][CEG][F]
The third block looks at the next state 0s then 1s. All the states in
each given block are to have the next state 0s contained in the
same block in the partition above it. This sounds confusing but
is simple.
-Look at A, B and D the next states with input 0 are BD and B respectively
BDB are all in block 1 of p2
-Now look at the next states with input 1 = CF and G respectively
CFG are all in block 2 of p2
-Do the same for block 2 of p2 CEFG
0s- FFEF --all in block 2
1s- ECDG ** not all in block 2
-The next state input 1 for F is different so it comes out of block 2 into
its own block in p3
The fourth partition acts the same as the third, by checking the next state for 0s then 1s
to see if they are in same blocks
-In this case ABD 0s-BDB 1s-CFG which are different for B so B comes out
CEG remain the same as 0s-FFF 1s-ECG
F of course will remain in its own block.
NOTE-- once moved out of a block the state may not join into another.
The fifth partition acts the same as the fourth and third, by checking the next states.
As you check you will see that p5 is the same as p4 so p5 is not needed.
You will continue to create new partitions until a new partition is the same as the previous one.
State Table Minimized State Table
Present Next State Output Present Next State Output
State w=0 w=1 z State w=0 w=1 z
A -- B - C - 1 A -- B - C - 1
B -- D - F - 1 B -- D - F - 1
C -- F - E - 0 C -- F - E - 0
D -- B - G - 1 F -- E - D - 0
E -- F - C - 0 ------------------------------
F -- E - D - 0 FIG.2
G -- F - G - 0
------------------------------
FIG.1
You are now done minimizing the states and can make a minimized state table using
the first letter of each block and its next states and outputs from the original table.
seen in FIG.2