x010100100 z011110110SolutionADifferent sequences of past in

x=010100100

z=011110110

Solution

A)Different sequences of past inputs will constitute different states or conditions of the circuit. • Specific outputs result only following a specified input sequence. The general description does not specify whether the output will depend just on the past inputs or on the latest input as well. These two possibilities lead to different structures, first explored in the mid-1950s by two people named Mealy and Moore. As mentioned in Chapter 5, in Mealy machines the outputs depend both on the present state (resulting from past inputs) and on the current input. The outputs in Moore machines depend only on the present state (resulting from past inputs). Attention will be devoted to both types.

sequential machines were given in Chapter 5, Figure 1. Somewhat refined versions are shown in Figure 1 here. The open arrowheads imply multiple variables. For example, input x stands for the set of variables {x1, x2, ... , xn}. The combinational part of the circuit is broken down into two separate parts: the state decoder and the output decoder. The state decoders in both models accept as inputs both primary (external) inputs and the present state. In the Moore machine, however, the output decoder accepts only the present state to yield outputs. In the simplest case, there is no output decoder at all; the states themselves are the outputs. In a given machine, there may be some outputs that are Moore-type outputs and others that aren’t. Such a machine must be classified as a Mealy machine, since at least some of its outputs depend not only on the state, but also on the inputs. Thus, the Mealy machine is the more general (and more common) type. The behavior of synchronous sequential logic circuits can be described in a number of ways. At any given clock pulse, the state of the circuit is the present state. Signals present at the input terminals at that time are the inputs. Thiscombination of present state and input results in two things: a transition to the next state and an output. At the next clock pulse, the process is repeated, except that the present state is now what the next state was at the preceding clock pulse. It is possible to conceive of this process as never ending; that is, the “next state” is never a state that had been previously encountered. In this case, the machine would be infinite—a peculiar machine indeed. Barring such an unlikely event, somewhere along the line the next state will be a previously encountered state. After this, the machine will retrace its steps over and over; no new states will be encountered. Several means are available for illustrating the following sequence: present state/input clock pulse next state/output One of these means is graphical/diagrammatic; another is tabular. A third approach utilizes a chart not unlike a flow chart describing an algorithm.

The graphical/diagrammatic tool for describing sequential circuit behavior is known as a linear graph.2 For each state of the circuit, there is a corresponding node in the graph. (The circle representing the node is made large enough that the symbol for the state can be written inside.) With the machine in any one state (node in the graph), at the occurrence of a clock pulse, there will be a state transition to the next state and there will be an output, both in accordance with the problem statement. For a single-input machine, two lines emanate from each node, one each for a 0 and for a 1 input. For two input variables, four lines emanate from each node, one for each input combination: 00, 01, and so on. (How many lines will emanate from each node if the number of input variables is n?) Along each line we write the input value and the corresponding output separated by a slash. The resulting graph is called a state diagram. For some state machines it is known from the statement of the problem just how many distinct states the machine has. However, in general, the number of possible states is initially unknown. To establish the state diagram, we arbitrarily choose an initial state and label it, say, A. (State names can be anything convenient.) A state is identified by unambiguously specifying how it is reached. To say, for example, that “state S is reached when the input is 1” is inadequate,3 because the statement does not unambiguously identify it: Does this 1 follow another 1? Is it the first 1 after a string of 0’s? Does this 1 follow a string of two or more preceding 1’s? One unambiguous specification would be: “State S is reached by the second of two input 1’s after one or more 0’s.” Because it is difficult to describe, in the abstract, both the state diagram and the tabular tool to be discussed next, we will continue this discussion in conjunction