UNIT IV(Part II)

Generation of A State Diagram from A Timing Chart
A common method in describing digital systems uses a timing chart. This chart indicates the operations must take place during particular time slots in order for the system to function properly. These operations are initiated by control signals and the timing chart indicates when each control signal must be asserted.
The state diagram is essential in the hardware design of the system and hence after the timing chart, the system design can proceed to the development of the state diagram. A trial-and- error procedure is often the most efficient method to be used.
Let us consider the following timing chart of a simple digital controller.

(Pending – waveform)

Here, X and Y are the system inputs and the clock signal is also shown. The system does not give the output as long as X & Y are simultaneously 0. We have to develop a state diagram to implement this timing chart with a minimum number of states and without usingcounters.

From this timing chart we can say that,

All state changes must take place on the positive-going transitions of the clock since the inputs change on the negative transition.

The output assertions begin at the positive transition of the clock

(Pending – circuit)

Equivalent state & redundant state

In state machine design, one of the first tools used is the state diagram. Some of these diagrams may contain extra or redundant states that could be eliminated to decrease the design complexity. In a state machine, two major tasks are completed during each stage:
Outputs are generated, if necessary
The signals producing the correct next state must be generated.

Equivalent states: If a state machine is started from either of two states and identical output sequences are generated from every possible set of input sequences, the two states are said to be identical.

Redundant states: A state that is equivalent to another state is called a redundant state.

The redundant states can be removed. Hence a reduced state diagram contains no equivalent states. There is an orderly method available to identify and eliminate redundant states. This method is a simplified version of a more complex method that is generally applied to asynchronous system.
For practical synchronous systems, the following method is often sufficient to create the reduced state diagram.

a) The next state table for the state diagram is constructed

b) Equivalent states are then identified

c) As equivalent states are identified, all but one are considered redundant and thus be considered single state.

Actually, the simplified method of reducing states does not guarantee a minimal no. of states. More complex method can be carried out by executing the following steps:

a) Reduce the state table as far as possible using the simple method.

b) Group states having equivalent outputs together.

c) Within each group, eliminate those states that are not potentially equivalent.

d) Within each group, assume the equivalence of every possible pair of states.

By following this procedure, final reduced state diagram can be obtained

General State Machine Architecture
Traditional State Machines

The general block diagram of the state machine along with 2 possible variations is shown below.

1. General state machine The general state machine architecture consists of input forming logic, memory and output forming logic. The next state and the outputs are generated according to the design.(Pending – diagram)
2. State machine with output-holding register The output holding register is added to latch the outputs into this register at the midpoint of the state machine or after the state flip-flops settle. This arrangement is used to filter out the glitches from the output decoder. (Pending – diagram)
3. State machine with input-synchronizing register A synchronizing register is used to convert asynchronous inputs to synchronous variables. The state machine is then controlled by synchronous variables. Although, no output holding register is used, it may be added to the system if needed. (Pending – diagram)

6.9.2 The “One-Hot” state machine

The methods of state machine design are based on the use of minimum number of state flipflops. If m states are required to implement a sequential controller, the no of state flip-flops required n, is found by selecting the minimum value of n to satisfy: 2n ≥ m
This approach minimizes hardware requirements but there are certain disadvantages in certain applications.
In sequential controllers for digital computers, there is often a need for the state machine to be in 2 states simultaneously. Since, conventional state machines always exist in a single unique state at any given time, only one series of operations can be controlled.
The “one-hot” state machine, which associates each state with the assertion of a specific state flip-flop, can solve this problem. In a sequential system that progresses through a series of unique states, only one flip-flop is asserted during each stage. However, if two states must exist simultaneously, two flip-flops can be asserted. The output signals produced by each state flipflop can then be used to control two operations simultaneously.
These types of system allow the implementation of the fork and join operations in digital controllers. The figure below shows the idea of forking and jerking in a state machine controller.
The state machine progresses from state a to b. at this point, depending on an input, the system creates two states, c and g, that exist during t3. Two states also exist during t4 (d and h) and during t5 (e and i). As t6 is entered, the system returns to a single state f. during time slots t3 , t4 & t5 , two separate processes can be controlled concurrently.

Advantages of “one-hot” state machine design:
a) State machine can enter in two states simultaneously.
b) Design methods are simpler
c) This type of controller is more preferable for computer-aided design techniques than is the conventional state machine.

d) This design leads to shorter development time

Problems of Asynchronous Circuits

Asynchronous state machines are not as widely used as synchronous machines since there are three problems such as hazards, oscillations and critical races.

1. Hazards

A glitch is when a signal temporary takes on the wrong value. Glitches caused by structure of circuit and propagation delays are called hazards.
There are two types of hazards;

a) Static Hazards

When signal is not supposed to change its value in response to a specific change in an input, but instead momentarily does change is known as static hazard.

b) Dynamic Hazards

This is when a signal is supposed to change value, but there is a small oscillation.

(Pending – diagram)

Fig. : Static and Dynamic hazard

A change to a primary input often has more than one path of propagation to an output. When one path has a longer propagation delay than the others, we may find a static hazard.
This can be eliminated by examining the K-map of the output. A potential hazard exists whenever two adjacent ones (or 0’s if we are doing a product-of-sum implementation) are not covered by a common product term (sum term for product-of-sum).
To guarantee no static hazards, obtain a cover such that each pair of adjacent one’s(zero’s) is covered by a common product term (sum term).
A dynamic hazard is caused by the structure of a circuit. It is caused by a circuit with more than two levels, in which changes to an input have more than one path to propagate. A circuit with a dynamic hazard must also contain a static hazard
To avoid dynamic hazards, design two-level circuits with no static hazards.

2. Oscillations

A second problem that can occur in a poorly designed circuit is that of oscillation. Consider the excitation map as shown below.

(Pending – excitation table)

Fig. : An excitation map

If the system is in state a, a change of input from B = 0 to B = 1 sends the system to state c. State c is the transient state, and thus the excitation variable X changes to1.
A short time later, x changes to 1, moving the system to state d. This state is also the transient state changing back X to 0, followed by change in x to0.
The system now oscillates between states c and d. this is known as oscillation and is unacceptable in most systems. Hence, the situation depicted by states c and d of the map must be avoided.

3. Critical races

A third problem in asynchronous design is that of critical races. This situation can occur only when two or more feedback variables are present in the system. The below figure demonstrates the critical race problem.
This system has two external inputs, A and B, and two excitation variables, X and Y, that are feedback to the input of the circuit.
Due to unequal propagation delays, one of the excitation variables will reach a value of 1, while the other has not changed from a value of 0. The final stable state reached from this condition depends on the relative switching speeds of variables X and Y. This situation is referred to as critical race.
In some cases, a final state is never reached. Such a situation is also called critical race. Critical races obviously must be avoided. Hence, in designing asynchronous circuits, hazards, oscillations and critical races must be avoided.

(Pending – circuit and k-map)

Fig. : An excitation map with critical races

(Pending – Post MCQ)

Leave a Comment Cancel Reply