State machines

From: John Conover <>
Subject: State machines
Date: Thu, 22 Feb 1996 05:52:38 -0800

Hi Rick. It is late, (almost 6'ish in the AM,) and I just got home
from a design review on a new microprocessor-you know, the latest and
greatest ...

I sat in this review, and things degenerated, (and egos got involved,
etc., like things do in design reviews where tens of millions of
dollars are being committed to a concept.)

One of the predominate issues was to have some confidence that the
many state machines in the design were, indeed, correct. If I could
"wave a magic wand" and state, unequivocally, that the state machines
would inter-operate in a robust fashion, the industry could save a lot
of money-not only in design reviews, but in reworks (and the enormous
costs involved of potential recalls, and associated litigation, etc.,)
to fix the state machines.

The industry is pushing the limits (managerially, organizationally,
and technically,) of what can be done in CPU engineering, and the
limiting issue is "correctness" of the state machines in a large

While I was listening to the diatribe of the review, (mostly shin
kicking and sand throwing between the various teams that designed the
various state machines that inter-relate in the design,) it occurred
to me that really what was necessary was a YACC(1) (ie., some kind of
a BNF grammar,) for state machines that is in some sense hierarchal,
so that many (most certainly thousands, probably more,) of state
machine operations could be specified, and verified. (Perhaps this
grammar could be used to "drive" some kind of "guaranteed by
construction" synthesis tool suite.) Note that the problem is entirely
different, (almost the antithesis,) of using HDL and simulation
methodology for verification. (For example, HDL/simulation will
certainly tell me what a multitude of state machines will do in
response to a given input stimulus, but it will not tell me that there
is an un-protected fault when a state machine hits a terminal state
with no operation-which I could deduce from a YACC(1) type of BNF
design methodology. There are many design faults-legally, they are
called "errors and omissions, AKA, E&O's," of which this is only one

I am not at liberty to disclose the name of the company, but it is a
company that has invested a lot of bucks in CAE/CAD/CAM (both in
internal and vendor software,) methodologies, and has an excellent
reputation in deploying/exploiting them. (Funny that I sat there and
remembered that these were the issues in the 6800, the F8, 3870




John Conover,,

Copyright © 1996 John Conover, All Rights Reserved.
Last modified: Fri Mar 26 18:56:53 PST 1999 $Id: 960222055256.6037.html,v 1.0 2001/11/17 23:05:50 conover Exp $
Valid HTML 4.0!