Race-Free State Assignment

See race condition.

We can prevent races by performing state assignment such that the transitions from one stable state to another state require only one state variable to change at a time. However, this isn't always possible. To avoid this, we can create intermediate states to facilitate the transition.

Methods

Extra Unstable States Method

Let there be states in a flow table and .

Try to embed the symbolic states of the flow table into the coordinates of the or a higher dimensional "cube" such that the path from stable state to stable state fulfills one of the following:
- It is direct along a single edge of the cube, OR
- It goes through newly introduced unstable states along cube edges

New extra states area always unstable.

Example

Consider the following flow table:

We can draw our square:

Here we have $n = 2$ and we try a 2-dimensional "cube" (square). Notice that each diagonal represents a change in more than 1 variable at a time. This is bad, as it could cause race conditions. We could try other state assignments, but none of them will get rid of the diagonals.

The extra coordinates in the cube allow us to avoid diagonals by rearranging states closer to each other. We are also able to introduce additional, unstable states and use them as intermediate states during transitions.

Consider the node , which is adjacent to , This change only requires one variable to change.
The transition from to is via intermediate state
The transition from to is via

We need to assign our states, which we will do like so ():

A = 000
B = 001
C = 010
D = 100
E = 101
F = 110
G = 110

This state assignment will remove all race conditions.

Note that for each output variable of a transition state, if the desired state has a different value for that variable than the previous state, we we set that variable in the transition state to a don't care so it can transition. Otherwise, we set it to the same value. If multiple variables are different, we set the output to the destination.

If there is a "two way" state assignment in the double change row, you must write "01" OR "10".

Equivalent States Method

This method is useful for a flow table with less than 4 states. Each state of a given flow table is replaced with two or more equivalent states.

For example, a state A may be replaced with A1 and A2 which are both equivalent to A. These new states will have the following features:

The output for A1 and A2 should be the same as that of A
If the original state was stable for some input valuation, the new states should also be stable for those inputs
For an input valuation, the ultimate stable successors for A1 and A2 belong to the same equivalent pair

Embedding rule:
The states are embedded into a cube of dimension or higher such that:

Members (e.g states A1, A2) of an equivalent pair are adjacent to each other
Through members, each pair is adjacent to other pairs

Procedure

Check each state S of the given flow table, and check its next-state values
Consult the cube for each S1 and S2 and their next state. If you can make a direct path, proceed as usual. If not, find the shortest path to get to the next state, whether that be 1 or 2 (since same output, equivalent state)

Example

Consider the flow table (same as previous example):

Note that this is only one of many possible arrangements.

Now we have from our "coordinate system":

A1 = 000
A2 = 001
B1 = 100
B2 = 101
C1 = 010
C2 = 110
D1 = 011
D2 = 111

One Hot State Method

This method makes use of one-hot state assignment.

We assign each state with a "one hot" state, and then transition between two states by setting this transition state to a combination of the two states. In addition, we do not care if a state has a race condition or not. We use a transition for every unstable state.

Procedure

Scan each state S and next state N
If next state N is unstable and not already mapped to an intermediate state, map it to an intermediate state
- In addition, scan the destination of next state N, and if there is another next state that points to S, add that to the list for the intermediate state
Update the output accordingly
- If a digit stays the same, make it a dash (don't cares)
- Else set it to the result

Example

Consider the same flow table:

Let:

A = 0001
B = 0010
C = 0100
D = 1000

We arrive at our new table quite easily: