STATE ASSIGNMENT IN ASYNCHRONOUS MACHINES AVOIDING CRITICAL RACES

Consider a machine with the reduced flow table shown below. State Stabes are shown in UPPER CASE letters and transit states in lower case.

	INPUT COMBINATIONS
STATES	00	01	11	10
A	A	e	-	c
B	a	B	B	d
C	a	-	b	C
D	a	D	D	D
E	a	E	d	-
-	-	-	-	-
-	-	-	-	-
-	-	-	-	-

Where do we begin? Note that the 00 column has only one stable state (A). There can be no critical race here (why not?). The 11 and 10 columns have two stable states each. There may be potential problems here. The 01 state has three stable states - this is the most critical column of all. Therefore, we should concentrate on the 01 column in making state assignments.

	INPUT COMBINATIONS
STATES	00	01	11	10
A=000	A=000	e=001	-	c
B	a	B	B	d
C	a	-	b	C
D	a	D	D	D
E=001	a=000	E=001	d	-
-	-	-	-	-
-	-	-	-	-
-	-	-	-	-

With A and E as assigned above, there is no race in the 01 column. The next most critical column is the 11 column. We assign states based on it next.

	INPUT COMBINATIONS
STATES	00	01	11	10
A=000	A=000	e=001	-	c
B=010	a=000	B=010	B=010	d=011
C	a	-	b	C
D=011	a=000	D=011	D=011	D=011
E=001	a=000	E=001	d=011	-
-	-	-	-	-
-	-	-	-	-
-	-	-	-	-

We had to assign state D as 011 to make it a unit-distance step from E (001). Then, since B goes to D, it must be a unit-distance from 011. We chose 010 since it is the lowest numbered state not yet used (an arbitrary decision). We have only state C to assign.

	INPUT COMBINATIONS
STATES	00	01	11	10
A=000	A=000	e=001	-	c=100
B=010	a=000	B=010	B=010	d=011
C=100	a=000	-	b=???	C=100
D=011	a=000	D=011	D=011	D=011
E=001	a=000	E=001	d=011	-
-	-	-	-	-
-	-	-	-	-
-	-	-	-	-

To go from C=100 to B=010 requires two state variables to change. We have a race condition, is it critical (It can not be eliminated!)

The possible transitions are 100 to 000 to 010; 100 to 110 to 010; and (not likely) 100 to 010.

Now 000 is state A, 110 has not been used. Both have don't cares in the 11 column. We have three possible solutions.

Change the "b" in the C row to "a" and change the don't care in a to 010. Thus the 100-000-010 sequence is assured
Change to "b" in the C row to 110 (an undefined state) and change the don't care to 010. Thus the sequence 100-110-010 is assured.
Leave the "b" alone and change both don't cares so either sequence will eventually lead to the correct state (B).

Does it make any difference? As far as races are concerned, no! But there is something we have not yet considered.

	INPUT COMBINATIONS				OUT
STATES	00	01	11	10	Z
A=000	A=000	e=001	-	c=100	0
B=010	a=000	B=010	B=010	d=011	1
C=100	a=000	-	b=???	C=100	1
D=011	a=000	D=011	D=011	D=011	0
E=001	a=000	E=001	d=011	-	0
-	-	-	-	-
-	-	-	-	-
-	-	-	-	-

	INPUT COMBINATIONS				OUT
STATES	00	01	11	10	Z
A=000	A=000	e=001	-	c=100	0
B=010	a=000	B=010	B=010	d=011	1
C=100	a=000	-	b=110	C=100	1
D=011	a=000	D=011	D=011	D=011	0
E=001	a=000	E=001	d=011	-	0
- = 110	-	-	-=010	-	1
-	-	-	-	-
-	-	-	-	-

The moral is to (a) attempt an all unit-distance assignment when possible, (b) if not possible, start with the most critical columns first and (c) don't forget to check what the output(s) will do. Note that, in many cases, the remainder of the don't cares in the table should be change so as to direct the machine to some specific state if the machine ever gets into that unused state.