Partitioning minimization procedure

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