State splitting for level reduction

Abstract

A method of state splitting in a state machine includes determining a number N of logic levels, i.e. CLB levels, for each state in a state machine. Number N is equal to N.sub.i-1 +log.sub.k f.sub.i wherein 'k' is the number of input lines to a CLB, 'i' is a particular node in a particular hierarchial level in the Boolean logic, and 'f' is the number of fanin transitions to the particular node. An average number N(AV) as well as a maximum number N(MAX) of CLBs to implement the states in the state machine are also determined. Then, predetermined exit criteria are checked. One exit criterion includes determining that the maximum number N(MAX) is not associated with a state register, but is instead associated with an output, for example. Another exit criterion includes providing a ratio by dividing the maximum number N(MAX) by the average number N(AV). If the ratio is less than or equal to a split-factor, then this exit criterion is met. In one embodiment, the split factor is between 1.5 and 2.0. Yet another exit criterion includes determining that the state being analyzed has one or two fanin transitions. If none of the exit criteria are met, then the state associated with the maximum number N(MAX) is split into at least two states. The method is further optimized by repeating all steps until at least one exit criterion is met. State splitting in accordance with the present invention typically reduces the levels of CLBs by approximately 20%, thereby significantly reducing delay in the state machine.