Electronic digital logic circuitry – Multifunctional or programmable – Array
Patent
1994-05-23
1997-04-01
Harvey, Jack B.
Electronic digital logic circuitry
Multifunctional or programmable
Array
326 46, 326 17, G11C 1300
Patent
active
056175736
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.
REFERENCES:
patent: Re34363 (1993-08-01), Freeman
patent: T943001 (1974-06-01), Mennone
patent: 4706216 (1987-11-01), Carter
Roy L. Adler et al., Algorithms for Sliding Block Codes, IEEE Trans. on Info. Theory, vol. IT-29, Jan. '83 pp. 5-16.
Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Trans. on Comp., Aug. '86 pp. 677-691.
Preas, Bryan and Lorenzetti, Michael, Physical Design Automation of VLSI Systems, The Benjamin/Cummings Publishing Company, Inc., Menlo Park, Ca., pp. 74-75. Copyright 1988.
Huang Alan Y.
Knapp Steven K.
Kwatra Sanjeev
Harms Jeanette S.
Harvey Jack B.
Seto Jeffrey K.
Xilinx , Inc.
LandOfFree
State splitting for level reduction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with State splitting for level reduction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and State splitting for level reduction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-548132