1
\$\begingroup\$

I have a very basic question. In what ways an algorithmic state machine (ASM) is different from a state transition graph (STG). Can someone take a very basic example (such as a binary counter) to explain what problems in a state diagram does an ASM solve. For example, somewhere on the internet I read that ASMs can describe finite state machines (FSM) with very large number of inputs, but I am unable to construct an example of this situation. Can anyone highlight the problems in STGs that ASMs solves by giving an example of an FSM?

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

State Transition Graph (or Diagram)

  • Low level circuit behavior description, only used for sequential logic
  • Only meaningful for sequential logic (see classic T-Bird tail light example)
  • Includes very detailed information about exact bit patterns for both inputs and outputs - even "don't care" inputs
  • Transitions are assumed to occur on clock signal transitions
  • Doesn't scale well - complex behaviors and designs result in unmanageably complex STGs

Algorithmic State Machine

  • Structured similarly to flowcharts, with a few symbol differences
  • Are a higher-level description of behavior using more abstract language than STGs (for example, an 8-bit accumulation register may just be referred to as "SUM" in an ASM instead of printing an 8-bit pattern in the equivalent STG)
  • There is implicit timing information - state box actions and the following decision and conditional box actions occur in one clock cycle of sequential design descriptions
  • Unlike STGs, ASMs can been used to describe combinational logic such as multipliers - in that case, the implicit timing information is meaningless and they must contain start operation and end operation boxes
  • "Don't care" inputs are not listed - only inputs required to make a decision
  • Scales well to describe multiple levels of the design

There are also obvious syntactic differences between how they represent inputs or outputs, as well as the symbols they use.

To address your specific question about using an ASM to describe a larger design, the reason it may be "easier" to use an ASM for larger designs is because the ASM charts have slightly less detailed information. Inputs and outputs can be described in English words instead of bit patterns, and they generally appear less cluttered than STGs.

By the way, I strongly disagree with the first paragraph in Wikipedia's ASM description. ASM charts are not "less formal" than STGs. Every symbol still has a specific meaning and intended use. Replacing an STG with an ASM is not an excuse to get sloppy.

This slide show (PDF Link) has several comparisons of the two side by side along with pretty detailed explanations. This one (PDF Link) goes into more detail about the timing requirements of ASM charts.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.