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.


Year:
Jan 17 2020
Keywords:
Laboratories:


Note: The status of this file is: Anyone


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

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)