M. Sekine and T. Villa and K. Goto and Robert K. Brayton

EECS Department, University of California, Berkeley

Technical Report No. UCB/ERL M93/59

, 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/ERL-93-59.pdf

This paper proposes a new approach based on loop construct for the derivation of finite state machines (FSM's) from high level models (HLM's), and also for state codes by using weights of eigenvectors of state transition matrices. As loops are closed and defined locally, they are primitive and robust under the transformation from HLM to FSM. The loops in control flow-graphs (CFG's) have been transformed to similar loops in FSM's in traditional approaches, but these approaches are valid only as far as control in CFG's is suitable to FSM's. Loops having complex control constructs over macro-sequences in CFG's is suitable to FSM's. Loops having complex control constructs over macro-sequences in CFG's must be reformed in order to control micro-sequences in FSM's. The loop body decomposition by Shannon expansion is proposed to obtain suitable micro-loops for FSM's. It generates recursive loop equations and micro-loop pieces from upper-level loop bodies. Since upper-level loops are designed to control global paths of data-flow parts, some lower level loops control global paths. These loops are desirable for global optimization. The global data-flow parts selected by such loops are ordered and optimized incrementally according to the weight order of the loops. Scheduling for each loop generates new control variables for the state transitions in it instead of variables occurring in control-flow parts of the HLM. A mathematical basis is build to relate loops in the state diagrams and eigenvectors or poles in pulse transform functions. The relations between linear systems and Boolean circuits are derived by combining a vector space and logic operations. The new approach based on loop body decomposition provides no heuristic algorithm, but a deductive algorithm. It is shown that the weights of the states are obtained in a general form if the state transition is a linear group.

---

BibTeX citation:

@techreport{Sekine:M93/59,
    Author= {Sekine, M. and Villa, T. and Goto, K. and Brayton, Robert K.},
    Title= {A New Approach for the Synthesis of FSM's from Control-Flow Graphs},
    Year= {1993},
    Month= {Jul},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2408.html},
    Number= {UCB/ERL M93/59},
    Abstract= {This paper proposes a new approach based on loop construct for the derivation of finite state machines (FSM's) from high level models (HLM's), and also for state codes by using weights of eigenvectors of state transition matrices.  As loops are closed and defined locally, they are primitive and robust under the transformation from HLM to FSM.  The loops in control flow-graphs (CFG's) have been transformed to similar loops in FSM's in traditional approaches, but these approaches are valid only as far as control in CFG's is suitable to FSM's.  Loops having complex control constructs over macro-sequences in CFG's is suitable to FSM's.  Loops having complex control constructs over macro-sequences in CFG's must be reformed in order to control micro-sequences in FSM's.  The loop body decomposition by Shannon expansion is proposed to obtain suitable micro-loops for FSM's.  It generates recursive loop equations and micro-loop pieces from upper-level loop bodies. Since upper-level loops are designed to control global paths of data-flow parts, some lower level loops control global paths.  These loops are desirable for global optimization.  The global data-flow parts selected by such loops are ordered and optimized incrementally according to the weight order of the loops.  Scheduling for each loop generates new control variables for the state transitions in it instead of variables occurring in control-flow parts of the HLM.  A mathematical basis is build to relate loops in the state diagrams and eigenvectors or poles in pulse transform functions.  The relations between linear systems and Boolean circuits are derived by combining a vector space and logic operations.  The new approach based on loop body decomposition provides no heuristic algorithm, but a deductive algorithm.  It is shown that the weights of the states are obtained in a general form if the state transition is a linear group.},
}

EndNote citation:

%0 Report
%A Sekine, M. 
%A Villa, T. 
%A Goto, K. 
%A Brayton, Robert K. 
%T A New Approach for the Synthesis of FSM's from Control-Flow Graphs
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/ERL M93/59
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2408.html
%F Sekine:M93/59