# Partitioning minimization procedure

- 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- EC**D**G ** 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

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Metaheuristic** — In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the… … Wikipedia

**statistics** — /steuh tis tiks/, n. 1. (used with a sing. v.) the science that deals with the collection, classification, analysis, and interpretation of numerical facts or data, and that, by use of mathematical theories of probability, imposes order and… … Universalium

**Genetic algorithm** — A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of… … Wikipedia

**List of statistics topics** — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… … Wikipedia