Finite State Machines and Algorithmic State Machines: Fast and Simple Design of Complex Finite State Machines

This book is about Algorithmic State Machines (ASMs) and Finite State Machines (FSMs). It provides techniques for the design of very complex control units of digital systems with hardly any constrains on their size – namely the number of inputs, outputs and states. The models, method and algorithms described in the book can be applied to a broad class of digital system design problems including design of complex controllers, robots, microprocessors, communication devices and for designing CAD systems of digital systems with ASIC and FPGA technologies. The book contains six chapters. The following is a brief description of the subjects that are covered in each chapter. The First Chapter deals with models for description of sequential circuits whose behavior depends not only on their present inputs, but generally on a prehistory, including past inputs. In the first part of this chapter, Samary Baranov discusses the main automaton models – Mealy, Moore and their combined model and the methods for their representation – automaton graphs and transition and output tables. He then presents the transformations between Mealy and Moore models and their minimization. In the First Chapter, the author considers an abstract automaton as a 'black box' with one input and one output which transforms input sequences into output sequences. In Chapter 2, he concentrates on the interior of a black box and examine how to realize the behavior, described at the level of abstract automaton, by means of hardware components. Baranov describes how structure automaton works, introduces the automaton structure table and explains how to encode output signals and states for minimization of logic circuits. This chapter is concluded with detailed examples of logic synthesis of different automaton models – Mealy, Moore and their combined model. In Chapter 3, author defines Algorithmic State Machines, gives examples of ASMs and describes how to present sequential processes with ASMs. Then he discusses various representations of ASMs, ASM minimization and combining several ASMs into one combined ASM. The fourth Chapter is the main chapter in this book. It builds the bridge between Algorithmic State Machines and Final State Machines. In this Chapter, Baranov uses ASMs to design FSMs with hardly any constrains on their size – namely the number of inputs, outputs and states. The author considers techniques for synthesis Mealy and Moore FSMs and their combined model, and a method for logic synthesis of such FSMs. Finally, he presents methods for decomposition of FSM with large numbers of inputs and outputs. In the fifth Chapter, the author concentrates on the multilevel minimization of logic circuits that is especially important for complex circuits with large numbers of inputs and outputs. Several simple and straightforward methods for obtaining circuit structure with more than two levels are considered. At the end of Chapter, he presents very simple algorithms for transformation of any multilevel circuit into the circuit with NOR gates, NAND gates and NOR and NAND gates together without using Boolean expressions. As a rule, the control unit of a digital system is a small but a more complicated part of a design. It is a regular circuit with rather long connections between gates. The delay of such connections is generally more than the delay of the gates themselves. The solution is to implement control units in the form of matrices with closely spaced elements. The sixth Chapter presents techniques for several possible realizations of FSMs, minimizing the chip area. These techniques are based on the circuit representation as a composition of four or six matrices, the input variables replacement, and special methods for state assignment and microinstruction encoding. This book is useful for undergraduate and graduate students of Computer engineering and Computer science departments, their teachers and hardware designers and hardware engineers.