Digital Design with Implicit State Machines

Claude Shannon, in his famous thesis (1938), revolutionized circuit design by showing that *Boolean algebra* subsumes all ad-hoc methods that are used in designing switching circuits, or combinational circuits as they are commonly known today. But what is the calculus for sequential circuits? Finite-state machines (FSM) are close, but not quite, as they do not support arbitrary parallel and hierarchical composition like that of Boolean expressions. We propose an abstraction called *implicit state machine* (ISM) that supports parallel and hierarchical composition. We formalize the concept and show that any system of parallel and hierarchical ISMs can be flattened into a single flat FSM without exponential blowup. As one concrete application of implicit state machines, we show that they serve as an attractive abstraction for digital design and logical synthesis.

Jan 17 2020

Note: The status of this file is: Anyone

 Record created 2020-01-17, last modified 2020-04-20

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)