The implementation of finite sequential machines by using a programmable array logic to synthesise their combinational part is considered. A critical view of the efficiency of existing methods to carry out the state assignment of these machines is given, and it is shown that we can derive a bound on the number of state variables beyond which even an arbitrary coding usually leads to better results in terms of area occupation. It is suggested in the paper that this bound can still be found when more refined area estimates are used.
Inspec keywords: logic CAD; sequential circuits; logic arrays
Other keywords:
Subjects: Logic and switching circuits; Computer-aided logic design; Logic circuits
References
-
-
1)
- C.J. Tan . State assignments for asynchronous sequential machines. IEEE Trans. Comput. , 4 , 382 - 391
-
2)
- H.A. Curtiss . Tan-like state assignments for synchronous sequential machines. IEEE Trans. Comput. , 181 - 187
-
3)
- De Micheli, G., Brayton, R.K., Sangiovanni-Vincentelli, A.: `Kiss: A program for optimal state assignment of finite state machines', Proc. 1984 Int. Conf. on CAD, p. 209–211.
-
4)
- Brown, D.W.: `A state-machine synthesis-SMS', Proc. 18th Design Automation Conference, TN Nashville, p. 301–305.
-
5)
- G. De Micheli , A.L. Sangiovanni-Vincentelli . Multiple constrained folding of programmable logic arrays: theory and applications. IEEE Trans. Comput.-Aided Des. , 3 , 151 - 167
-
6)
- D.B. Armstrong . A programmed algorithm for assigning internal codes to sequential machines. IRE Trans. Elect. Comput. , 611 - 622
-
7)
- Quintana-Toledo, J.M.: `Una contribución al diseño automático de circuitos digitales usando PLAs', 1987, PhD dissertation, Sevilla University, (in spanish).
-
8)
- R. Sobol . (1983) The universal syncronous machine, VLSI Design.
-
9)
- G. De Micheli . Symbolic design of combinational and sequential logic circuits implemented by two-level logic macros. IEEE Trans., Comput.-Aided Des. , 4 , 597 - 615
-
10)
- Meyer, M.J., Agrawal, P., Pfister, R.G.: `A VLSI FSM design system', Proc. 21st Design Automation Conference, NM Albuquerque.
-
11)
- G.D. Hachtel , A.R. Newton , A.L. Sangiovanni-Vincentelli . An algorithm for optimal PLA folding. IEEE Trans. Comput.-Aided Des. , 2 , 63 - 76
-
12)
- G. De Micheli , R.K. Brayton , A. Sangiovanni-Vincentelli . Optimal state assignment for finite state machines. IEEE Trans., Comput.-Aided Des. , 269 - 284
-
13)
- De Micheli, G.: `Computer-aided synthesis of PLA-based systems', 1984, PhD dissertation, Berkeley University.
-
14)
- De Micheli, G., Sangiovanni-Vincentelli, A., Villa, T.: `Computer-aided synthesis of PLA-based finite state machines', Proc. 1983 Int. Conf. on CAD, p. 154–157.
-
15)
- C.N. Liu . A state variable assignment method for asynchronous sequential machines. J. ACM , 209 - 216
-
16)
- Y. Kambayasi . Logic design of programmable logic arrays. IEEE Trans. Comput. , 9 , 609 - 617
-
17)
- C.A. Papachristou , D. Sarma . An approach to sequential circuit construction in LSI programmable logic arrays. IEE Proc. E, Comput. & Digital Tech. , 5
-
18)
- S.H. Unger . (1969) , Theory of asynchronous sequential machines.
-
19)
- J.I. Acha , J. Calvo . On the implementation of sequential cricuits with PLA modules. IEE Proc. E, Comput. & Digital Tech. , 5 , 518 - 522
-
20)
- Kang, S.: `Automated synthesis of PLA based systems', 1981, PhD dissertation, Stanford University.
-
21)
- P. Agrawal , M.J. Meyer . (1984) Automation in the design of finite state machines, VLSI Design.
-
1)
Related content