Sequential Networks:Malfunctions of Asynchronous Sequential Networks.

Malfunctions of Asynchronous Sequential Networks

An asynchronous sequential network does not work reliably unless appropriate binary numbers are assigned to internal variables for each input change.

Racing Problem of Sequential Networks

A difference in time delays of signal propagation along different paths may cause a malfunction of an asynchronous sequential network that is called a race. This is caused by a difference in the delay times of gates.

Let us consider the transition-output table of a certain asynchronous sequential network shown in Table 31.2.

Suppose that the network is in the stable state (x1, x2, y1, y2) = (1110). If the inputs change from (x1, x2) = (11) to (10), the network changes into the unstable state (x1, x2, y1, y2) = (1010), marked with ∗ in Table 31.2. Because of y1 = 1, y2 = 0, Y1 = 0 and Y2 = 1, two logic gates whose outputs represent y1 and y2 in the network must change their output values simultaneously. However, it is extremely difficult for the two gates to finish their changes at exactly the same time, because no two paths that reach these gates have identical time delays. Actually, one of these two logic gates finishes its change before the other does. In other words, we have one of the following two cases:

occurs. State (01) is the destination stable state (i.e., desired stable state), but (11) is not. Thus, depending on which path of gates works faster, the network may malfunction. This situation is called a race. The network may or may not malfunction, depending on which case actually occurs.

Next, suppose that the network is in the stable state (x1, x2, y1, y2) = (0100) and that inputs (x1, x2) = (01) change to (11). The cell labeled with ∗∗ in Table 31.2 has (Y1 Y2 ) = (11). Thus, y1 and y2 must have simultaneous changes. Depending on which one of the two logic gates whose outputs represent y1 and y2 changes its output faster, there are two possible transitions. But in this case, both end up in the same stable state, (y1, y2) = (10). This is another race, but the network does not have a malfunction depending on the order of change of internal variables. Hence, this is called a noncritical race, whereas the previous race for cases 1 and 2 is termed a critical race because the performance is unpredictable (it is hard to predict which path of gates will have the signal change faster), possibly causing the network to malfunction. We may have more complex critical racing. In other words, if we have a network such that the output of the gate whose output represents y1 feeds back to the input of a gate on a path that reaches the gate whose output represents y1, the y1 may continue to change its value from 0 to 1 (or from 1 to 0), then change back to 0 by feedback of new value 1, and so on. This oscillatory race may continue for a long time.

Remedies for the Racing Problem

Whenever a network has critical races, we must eliminate them for reliable operation. One approach is to make the paths of gates have definitely different time delays. This approach, however, may not be most desirable for the following reasons. First, the speed may be sacrificed by adding gates for delay. Second, there are cases where this approach is impossible if a network contains more than one critical race. By eliminating a critical race in one column in the transition table by using a path of different time delay, a critical race in another column may occur or may be aggravated.

A better approach is to choose some entries in the transition table so that no critical races occur. Then, on the basis of this new table, we synthesize a network with the desired performance, according to the synthesis method to be described later. A change of entries in some unstable states without changing destination stable states, such that only one internal variable changes its value at a time, is one method for eliminating critical races. The critical race discussed above can be eliminated from Table 31.2 by replacing the entry marked with ∗ by (00), as shown in Table 31.3, where only Y1 and Y2 are shown without the network output z. If every entry that causes the network to malfunction can be changed in this manner, a reliable network with the performance desired in the original is produced, because every destination stable state to which the network should go is not changed, and the output value for the destination stable state is also not changed. (We need not worry about noncritical races, since they cause no malfunctions.) However, sometimes, there are entries for some unstable states that cannot be changed

in this manner. For example, consider Table 31.4 (some states are not shown, for the sake of simplicity). The entry (01) for (x1, x2, y1, y2) = (0010) is such an entry and causes a critical race. [State (x1, x2, y1, y2) = (0010) in Table 31.2 may have the same property, but actually, the network never enters this state because of the assumption that inputs x1 and x2 do not change simultaneously.] Since this entry requires simultaneous transitions of two internal variables, y1 and y2, we need to change it to (00) or (11). Both lead the network to stable states different from the destination stable state (01).

When a change of entries in unstable states does not work, we need to redesign the network completely by adding more states (e.g., 8 states with 3 internal variables, y1, y2, and y3, instead of 4 states with 2 internal variables, y1 and y2, for Table 31.4) without changing transitions among stable states, as we will see later in this chapter. This redesign may include the reassignment of binary numbers to states, or the addition of intermediate unstable states through which the network goes from one stable state to another. The addition of more states, reassignment of binary numbers to states, and addition of intermediate unstable states for this redesign, however, is usually cumbersome. So, designers usually prefer the use of synchronous sequential networks because design procedures are simpler and the racing problem, including oscillatory races due to the existence of feedback loops in a sequential network, is completely eliminated.