Page 155 - Bebop to The Boolean Boogie An Unconventional Guide to Electronics Fundamentals, Components, and Processes

136 Chapter Twelve

State Assignment

A key consideration in the design of a state machine is that of state
assignment, which refers to the process by which the states are assigned to
the binary patterns of Os and 1s that are to be stored in the state variables.
A common form of state assignment requiring the minimum number of
registers is known as binary encoding. Each register can only contain a single
binary digit, so it can only be assigned a value of 0 or 1. Two registers can be
assigned four binary values (00,01, 10, and ll), three registers can be assigned
eight binary values (000,001,010,011, 100, 101, 110, and lll), and so forth.
The controller used in our coin-operated machine consists of five unique states,
and therefore requires a minimum of three state variable registers.
The actual process of binary encoded state assignment is a nontrivial
problem. In the case of our controller function, there are 6,720 possible
combinations" by which five states can be assigned to the eight binary values
provided by three registers. Each of these solutions may require a different
arrangement of primitive gates to construct the input and output logic, which
in turn affects the maximum frequency that can be used to drive the system
clock. Additionally, the type of registers used to implement the state variables
also affects the supporting logic; the following discussions are based on the use
of D-type flip-flops.
Assuming that full use is made of don't care states, an analysis of the various
binary encoded solutions for our controller yields the following. . .

138 solutions requiring 7 product terms
852 solutions requiring 8 product terms
1,876 solutions requiring 9 product terms
3,094 solutions requiring 10 product terms
570 solutions requiring 11 product terms
190 solutions requiring 12 product terms
. . . where a product term is a group of literals linked by & (AND) operators-
for example, (a & b & c)-and a literal is any true or inverted variable. Thus,
the product term (a & b & c) contains three literals (a, b, and c).

4 This number would be somewhat reduced if all the mirror-image combinations were taken
into account, but that would not significantly lessen the complexity problem of determining
the optimal combination.