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 .

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:

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

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: