Design of Fundamental Mode Sequential Circuits

Design of Fundamental Mode Sequential Circuits

In the previous section we have seen the analysis of asynchronous sequential circuits. It gives us the information of how an existing sequential circuit works. The design process is an exactly reverse process. Here, we know the behaviour of the circuit and we have to develop the sequential circuit from scratch. Let us see the steps involved in designing of asynchronous sequential circuit.

1. Construction of a primitive flow table from the problem statement. An intermediate step may include the development of a state diagram.

2. Primitive flow table is reduced by eliminating redundant states by using state reduction techniques.

3. State assignment is made.

4. The primitive flow table is realized using appropriate logic elements.

 

1. Derivation of Primitive Flow Table

• The flow table in the asynchronous sequential circuit is same as that of state table in the synchronous sequential circuit. In asynchronous sequential circuits state table is known as flow table because of the behaviour of the asynchronous sequential circuit. The state changes occur independent of a clock, based on the logic propagation delay, and cause the states to "flow" from one to another.

• A primitive flow table is a special case of flow table. It is defined as a flow table which has exactly one stable state for each row in the table. The design process begins with the construction of primitive flow table. Let us see the following example to understand the process of construction of the primitive flow table from the problem statement.

 

Ex. 7.6.1 Develop the state diagram and primitive row flow table for a logic system that has two inputs S and R and a single output Q. The device is to be an edge triggered SR flip-flop but without a clock. The device changes state on the rising edges of the two inputs. Static input values are not to have any effect in changing the Q output.

AU : Dec.-06, Marks 16

Sol. : For SR flip-flop, initial state A is stable when no input changes have been detected. When SR input changes from 00 to 01 (Reset), the state transition occurs from A to C and when SR input changes from 00 to 10 (Set), the state transition occurs from A to B. This is illustrated in Fig. 7.6.1.

The state B is stable with a 10 static SR input and Q⁺ is a 1. The state C is stable with a 01 static SR input and Q⁺ remains a 0. A state transition from B to D occurs when the SR input changes from 10 to 00 with Q⁺ output remains a 1. State change from B to E occurs when SR changes from 10 to 11. Once state E is reached the Q⁺ output changes from a 1 to a 0. State change from D to C occurs when SR changes from 00 to 01. Once state C is reached the Q⁺ output changes from a 1 to a 0. An SR input sequence of 00 → 01 → 11 → causes an A → C → F → state transition. The Q⁺ remains a 0 unit the 01 → 11 SR change occurs. The 11 static input is allowed because only input rising edges cause Q changes. State transition F to B occurs when SR changes from 11 to 00.

The state change occurs from B to E when SR changes from 10 → 11, and the Q+ output is a 1 for the transition. A state transition from state E to state G occurs when SR changes from 11 to 10 and Q⁺ is 0. When SR input changes from 10 → 11 transition from G to E occurs. Once in state G, a 00 input on SR returns the state machine back to state A.

A state transition from state F to H occurs when SR changes from 11 to 01. For SR input 10 state transition F to B occurs.

Table 7.6.1 shows the primitive flow table constructed from the state diagram.

 

2. Reduction of Primitive Flow Table

The next step in the design process is to reduce the primitive flow table using state reduction techniques. Here, we are going to use merger graph technique to reduce primitive flow table.

Merger graphs is state reducing tool used to reduce states in the incompletely specified machine. The merger graph is defined as follows :

1. It contains the same number of vertices as the state table contains states. Refer Fig. 7.6.2.

2. Each compatible state pair is indicated by a line drawn between the two state vertices.

3. Every potentially compatible state pair, with outputs not in conflict but whose next states are different, is connected by a broken line. The implied states are drawn in the line break between the two potentially compatible states.

4. If two states are incompatible, no connecting line is drawn.

 

Ex. 7.6.2 Reduce the primitive flow table shown in Table 7.6.2 using merger graph method.

Sol. :

1. States A and B are compatible. Thus the line is drawn between A and B.

2. State A and C are compatible. Thus the line is drawn between A and C.

3. State B and C are compatible. Thus, the line is drawn between B and C.

4. States A and D are compatible only if implied states C and E are compatible. This is indicated by drawing a broken line between A and D with CE written in between.

5. States A and E are incompatible since there outputs are different, so line is not drawn between A and E. For the same reason states B, C and D are also not compatible with E.

6. State B and D are compatible. Thus, the line is drawn between B and D.

7. States C and D are compatible only if implied states C and E are compatible. This is indicated by drawing a broken line between C and D with CE written in between.

8. It is found that states C and E are not compatible and hence states A and D, and states D and C are also not compatible. This is indicated by cross (X) marks.

The compatibility lines of merger graph form a geometrical pattern consisting of one triangle (A, B, C), a line (B, D) and a single state E that is not compatible with any others. Thus maximum compatibles are :

(A, B, C) (B, D) (E)

Here, we can notice that state B is common in two sets. However, it can be compatible with either states A and C or state D, but not both. If we consider the next don't care state of B as state C, it is compatible with stable A and C. If we consider the next don't care state of B as state E it is compatible with state D.

Considering state B compatible with states A and C, we have following set of maximum compatibilities for given primitive flow table

(A, B, C) (D) (E)

Considering state B compatible with state D, we have following set of maximum compatibilities for given primitive flow table.

(A, C) (B, D) (E)

So we can say that there may be more than one possible way of merging rows when reducing a primitive flow table

According to altemative-I we have

(A, B, C) → S₀

(D) → S₁

 (E) → S₂

and according to altemative-II we have

(A, C)         → S₀

(B, D)         → S₁

(E) → S₂

The Table 7.6.2 shows the reduced primitive flow table using both the alternatives.

 

Ex. 7.6.3 Reduce the primitive flow table derived in example 7.6.1.

Sol. : The derived primitive flow table is redrawn in Table 7.6.3.

The Fig. 7.6.3 shows the merger graph. Each compatible state pair is indicated by a line drawn between the two states vector.

Every potentially compatible state pair, with outputs not in conflict but whose next states are different, is connected by a broken line. The implied states are drawn in the line break between the two potentially compatible states. If two states are incompatible, no connecting line is drawn. 

Therefore, we have

(A, C) → S₀

(B, D) → S₁

(E, G) → S₂

(F, H) → S₃

The Table 7.6.5 shows the reduced primitive flow.

The Fig. 7.6.4 shows the reduced state diagram for primitive flow table.

 

3. Race Free State Assignment

• The state assignment step in asynchronous circuits is essentially the same as it is for synchronous circuits, except for one difference. In synchronous circuits, the state assignments are made with the objective of circuit reduction. In asynchronous circuits, the objective of state assignment is to avoid critical races.

a. Races and Cycles

• When two or more binary state variables change their value in response to a change in an input variable, race condition occurs in an asynchronous sequential circuit. In case of unequal delays, a race condition may cause the state variables to change in an unpredictable manner. For example, if there is a change in two state variables due to change in input variable such that both change from 00 to 11. In this situation, the difference in delays may cause the first variable to change faster than the second resulting the state variables to change in sequence from 00 to 10 and then to 11. On the other hand, if the second variable changes faster than the first, the state variables change from 00 to 01 and then to 11. If the final stable state that the circuit reaches does not depend on the order in which the state variable changes, the race condition is not harmful and it is called a noncritical race. But, if the final stable state depends on the order in which the state variable changes, the race condition is harmful and it is called a critical race. Such critical races must be avoided for proper operation. Let us see the examples of noncritical races and critical races. 

Noncritical Races

• Fig. 7.6.6 illustrates noncritical races. It shows transition tables in which X is a input variable and y₁ y₂ are the state variables. Consider a circuit is in a stable state y₁ y₂ x = 000 and there is a change in input from 0 to 1. With this change in the input there are three possibilities that the state variables may change. They can either change simultaneously from 00 to 11, or they may change in sequence from 00 to 01 and then to 11, or they may change in sequence from 00 to 10 and then to 11. In all cases, the final stable state is 11, which results in a noncritical race condition. In Fig. 7.6.6 (b) final stable state is y₁ y₂ x = 101

Critical Races

• Fig. 7.6.7 illustrates critical race. Consider a circuit is in a stable state y₁ y₂ x = 000 and there is a change in input from 0 to 1. If state variables change simultaneously, the final stable state is y₁ y₂ x = 111. If Y₂ changes to 1 before Y₁ because of unequal propagation delay, then the circuit goes to the stable state Oil and remain there. On the other hand, if Y₁ changes faster than Y₂, then the circuit goes to the stable state 101 and remain there. Hence, the race is critical because the circuit goes to different stable states depending on the order in which the state variables change. 

Cycles

• A cycle occurs when an asynchronous circuit makes a transition through a series of unstable states. When a state assignment is made so that it introduces cycles, care must be taken to ensure that each cycle terminates on a stable state. If a cycle does not contain a stable state, the circuit will go from one unstable state to another, until the inputs are changed. Obviously, such a situation must always be avoided when designing asynchronous circuits.

• Two techniques are commonly used for making a critical race free state assignment.

1. Shared row state assignment.

2. One hot state assignment.

a. Shared Row State Assignment

Races can be avoided by making a proper binary assignment to the state variables. Here, the state variables are assigned with binary numbers in such a way that only one state variable can change at any one time when a state transition occurs. To accomplish this, it is necessary that states between which transition occur be given adjacent assignments. Two binary values are said to be adjacent if they differ in only one variable. For example, 110 and 111 are adjacent because they differ only in the third bit.

• Fig. 7.6.8 shows the transition diagram. The transition diagram shows that there is transition from state a to state b and transition from state a to state c. The state a is assigned binary value 00 and state c is assigned binary value 11. This assignment will cause a critical race during the transition from a to c because there are two changes in the binary state variables. A race free assignment can be obtained by introducing addition binary state say d with binary value 10, which is adjacent to both a and c. Fig. 7.6.9 shows the modified transition diagram. As shown in the Fig. 7.6.9, the transition from a to c will go through d. This causes the binary variables to change from 00 → 10 → 11 which satisfy the condition that only one binary variable changes during each state transition, thus avoiding the critical race.

• This technique is called shared row state assignment because in this technique extra state, i.e. extra row is introduced in a flow table. This extra state is shared between two stable states.

c. One Hot State Assignment

The one hot state assignment is an another method for finding a race free state assignment. In this method, only one variable is active or 'hot' for each row in the original flow table, i.e. it requires one state variable for each row of the flow table. Additional rows are introduced to provide single variable changes between internal state transitions. This is illustrated in the following example.

• Consider a flow table given in Fig. 7.6.10 four state variables are used to represent the four rows in the table. Each row is represented by a case where only one of the four state variables is a 1. A transition from state A to state B requires two state variable changes; F from 1 to 0 and F₂ from 0 to 1. By directing the transition A to B through a new row E which contains Is where both states A and B have Is. We require only one state variable change from transition A to E and then from transition E to B. This permits the race free transition between A and B.

• In general, we can say that, in row i of the table, state variable F_i is 1 and all other state variables are 0. When a transition between row i and row j is required, first state variable F_j is set to 1 (so that both F_i and F_j are 1), and then F_i is set to 0. Thus each transition between two rows in the flow table goes through one     intermediate row. This permits the race free transition but requires two state Original transition times.    

• The Fig. 7.6.11 shows the complete one hot state assignment flow table. When        X₁X₂ = 01 the transition from A to B is passing through the dummy state E. Added Similarly, when X₁X₂ = 00 the transition from C to A is passing through the  dummy state F and so on. The original table thus gets modified and it is as shown in Fig. 7.6.11.

 

4. Realization of Flow Table

• To understand the process of realization of flow table we see the following example. The example illustrates all the steps of designing of asynchronous sequential circuit.