Novel state minimization and state assignment in finite state machine design for low-power portable devices

Zvi Kohavi, Switching and Finite Automata Theory, nineteenth reprint, Tata Mcgraw-Hill, New Delhi, 1996, pp. 385-463. Hopcroft, 1971, An nlogn algorithm for minimizing states in a finite automaton, 189 Bennets, 1971, An improved method of prime C-class derivation in the state reduction of sequential networks, IEEE Trans. Comput., C-20, 229, 10.1109/T-C.1971.223221 Bennets, 1972, A computer algorithm for state-table reduction, Radio Electron. Eng., 42, 513, 10.1049/ree.1972.0088 Villa, 1990, NOVA, IEEE Trans. Comput. Aided Designs, 9, 905, 10.1109/43.59068 B. Lin, A.R. Newton, Synthesis of multiple level logic from symbolic high-level description languages, Proceedings of International Conference on VLSI, August 1989, pp. 187–196. Hennie, 1968 Benini, 1995, State encoding for low power dissipation, IEEE J. Solid-State Circuits, 30, 10.1109/4.364440 S. Mitra, L. Avra, E. McCluskey, An output encoding problem and a solution technique, IEEE/ACM International Conference on Computer-Aided Design, 1997. B. Iyer, M. Ciesielski, Reencoding for cycle-time minimization under fixed encoding length, International Conference on Computer-Aided Design, 1998. Wang, 1999, An activity-driven encoding scheme for power optimization in microprogrammed control unit, IEEE Trans. VLSI Systems, 7, 130, 10.1109/92.748210 I. Pomeranz, K. Cheng, State encoding using input/output functions, 29th ACM/IEEE Design Automation Conference, 1992, pp. 573–577. J. Monteiro, A. Oliveira, Finite state machine decomposition for low power, Proceedings of the 35th Annual Conference on Design Automation, June 15–19, 1998, pp. 758–763. A. Iranli, P. Rezvani, M. Pedram, Low power synthesis of state machines with mixed D and T flip flops, Asia South Pacific Design Automation Conference, January 2003. E. Pastor, J. Cortadella, An efficient unique state coding algorithm for signal transition graphs, IEEE International Conference on Computer Design: VLSI in Computers & Processors, Cambridge, October 1993, pp. 174–177. G. De Micheli, et al., Optimal state assignment for finite state machines, IEEE Trans. Comput. Aided Designs (1985) 269–285. S. Devadas, et al., MUSTANG: state assignment of finite state machines targeting multi-level logic implementations, IEEE Trans. Comput. Aided Designs (1988) 1290–1300. S. Chow, Y Ho, T. Hwang, C. Liu, Low power realization of finite state machines, Proceedings of the 35th Annual Conference on Design Automation, 1998, pp. 758–763. Tsui, 1998, Low power state assignment targeting two and multilevel logic implementations, IEEE Trans. Comput. Aided Designs, 17, 1281, 10.1109/43.736568 Benini, 1995, State encoding for low power dissipation, IEEE J. Solid-State Circuits, 30, 10.1109/4.364440 S. Devadas, A.R. Newton, Exact algorithms for output encoding, state assignment and four-level Boolean minimization, International Conference on System Sciences, January 1990, pp. 387–396. R. Brayton, F. Somenzi, Minimization of Boolean relations, International Symposium on Circuits and Systems, May 1989, pp. 738–743. Dolotta, 1964, The coding of internal states of sequential circuits, IRE Trans. Electron. Comput., 13, 549, 10.1109/PGEC.1964.263726 Corman, 2001 Thulasiraman, 1992 Micheli, 1994