Top-Down Digital VLSI Design

Appendix B

Finite State Machines

Abstract

The emphasis in this appendix is on a number of mathematical facts relevant to hardware design that are not normally found in textbooks on automata theory. The equivalence relations between the various types of finite state machines (Mealy, Moore, and Medvedev), for instance, are not quite the same from a circuit designer’s perspective as for a computer scientist. The discussion further extends to implementation issues such as parasitic states, state reduction, state encoding, through-paths, logic instability, and output hazards.

Keywords

Finite State Machine (FSM)

Mealy machine

Moore machine

Medvedev machine

FSM equivalence

Latency

Parasitic state

State reduction

State encoding

Logic instability ...