:PROPERTIES: :ID: aad1ebe0-6ca0-43a5-82f5-a797f9af3dda :mtime: 20231027030438 :ctime: 20231027030429 :END: #+title: state machine reduction #+filetags: :public:project: * Definition of State machine reduction - Sometimes, when designing [[id:29d52285-bccb-40dd-90f5-ac2e828c498b][state machines]] it is possible that unnecessary states may be introduced - In general, reducing the number of states may reduce the number of [[id:2c4ec126-9394-40b4-82e0-209cd3501c4b][flip-flop]]s required and may also reduce the complexity of the next state logic owing to the presence of more unused states (don’t cares) * Example Problem - Consider the following State Table that corresponds with a Mealy Machine implementation - This is so, since the inputs and outputs from the machine are on the transitions (arcs) between states - The following state table is drawn in a compact form by incorporating the 2 possible input values as parallel columns within both the next state and output columns of the table * Row Matching If there are two duplicated in the [[id:4978b171-3ac9-4f0b-8a68-ae4e9d551efc][excitation table]], then those rows are redundant. The benefits of row matching are that row matching is easy to use. A downside of row matching is that row matching might not find all the redundant states. * State equivalence 2 states $p$ and $q$ can be considered to be equivalent if for any input bit sequence, the corresponding outputs $y_p$ and $y_q$, are identical, i.e., $y_p = y_q$, and the next states $S_p’$ and $S_q’$, are equivalent, i.e., $S_p’ = S_q’$ basically, 2 states are equal if they have equal outputs and equal next states. * Determining State equivalence using an implication table - The procedure will be described via an example - We need to perform a pairwise comparison between all possible pairs of states to see if we can discover equivalent state pairs. - The Implication Table facilitates this procedure - It has a cell for every possible pair of states - Note cells above the diagonal are omitted (since they already exist below the diagonal) - Diagonal cells are also omitted since they correspond to same state pairs