You get a bonus - 1 coin for daily activity. Now you have 1 coin

5: Structural Machine Synthesis

Lecture



Abstract: The structural automaton is considered. The method of canonical synthesis of structural automata is given.
Keywords: microprogram, automaton, graph, functional diagram, representation, vector, combined automaton, abstract automaton, input, canonical method of synthesis, combinational diagram, block diagram, automaton Mile, automaton Moore

5.1 Structural automaton

The process of abstract design consists in the transition from the source firmware (or a set of firmware) to one of the traditional forms of the automaton specification: matrix, table, or graphical (graph). The stage of transition to the task of the automaton is also necessary, since ensures the implementation of the structural design process by using a sufficiently efficient apparatus of the theory of finite automata.

Structural design is the process of transition from the above task forms to its functional scheme.

So, an abstract automaton at the input has a certain sequence of input signals, depending on which it goes from one state to another, producing a certain sequence of output signals (Fig. 5.1).

  5: Structural Machine Synthesis

Fig. 5.1.

The structure of the machine takes into account the structure of the input and output signals, that is, their specific representation in the form of binary vectors. The states of the automaton are also encoded by binary vectors.

Consider the combined automaton (Fig.5.2). Every state   5: Structural Machine Synthesis abstract automaton is encoded by a binary vector:

  5: Structural Machine Synthesis ,

  5: Structural Machine Synthesis ;

  5: Structural Machine Synthesis - the number of states of an abstract automaton;

  5: Structural Machine Synthesis - the number of memory elements.

  5: Structural Machine Synthesis

Fig. 5.2.

Input and output signals are also represented by binary vectors:

  •   5: Structural Machine Synthesis ,   5: Structural Machine Synthesis ,   5: Structural Machine Synthesis - the number of input signal abstract machine,   5: Structural Machine Synthesis - the number of inputs of the structural machine;
  •   5: Structural Machine Synthesis ,   5: Structural Machine Synthesis - the number of output signals of type 1,   5: Structural Machine Synthesis - the number of outputs of the 1st type of structural automaton;
  •   5: Structural Machine Synthesis ,   5: Structural Machine Synthesis - the number of output signals of type 2,   5: Structural Machine Synthesis - number of outputs 2 types of structural automaton

5.2 Canonical method of structural synthesis of automata

Structural diagram   5: Structural Machine Synthesis an automaton with the canonical method of synthesis appears to consist of three parts: two-combination schemes and the memory of the automaton (Fig. 5.3). Combination scheme 1 is designed to form the excitation functions   5: Structural Machine Synthesis arriving at the inputs of the memory elements, and output signals of type 1   5: Structural Machine Synthesis depending on input signals   5: Structural Machine Synthesis and signals from the outputs of the memory elements   5: Structural Machine Synthesis .

  5: Structural Machine Synthesis

Fig. 5.3.

Combination scheme 2 is designed to generate output signals of type 2   5: Structural Machine Synthesis as functions from the outputs of the memory elements   5: Structural Machine Synthesis .

Since the type 2 signals are absent in the Miles automatic machine, then, accordingly, there is no combinational circuit 2 in the structural diagram. The scheme of the Mile structural automaton is shown in Fig. 5.4.

  5: Structural Machine Synthesis

Fig. 5.4.

In Moore's automaton, type 1 signals are absent, therefore, in the block diagram in combinational circuit 1, there are no output signals of type 1   5: Structural Machine Synthesis . The scheme of the structural automaton of Moore is shown in Fig.5.5.

  5: Structural Machine Synthesis

Fig. 5.5.

Thus, in order to synthesize a structural automaton, it is necessary to synthesize two combinational circuits using a system of canonical equations. The system of canonical equations for   5: Structural Machine Synthesis -automat looks like this:

  •   5: Structural Machine Synthesis ;
  •   5: Structural Machine Synthesis ;
  • . . .
  •   5: Structural Machine Synthesis
  •   5: Structural Machine Synthesis
  •   5: Structural Machine Synthesis
  • . . .
  •   5: Structural Machine Synthesis
  •   5: Structural Machine Synthesis
  •   5: Structural Machine Synthesis
  • . . .
  •   5: Structural Machine Synthesis

5.4. Stages of synthesis

  1. Find the number of memory elements   5: Structural Machine Synthesis , (   5: Structural Machine Synthesis - the number of states of the abstract automaton) and we encode the states of the abstract automaton (Table 5.1).
    Table 5.1.
    a m \   5: Structural Machine Synthesis   5: Structural Machine Synthesis
    a 1
    a 2
    ...
    a M
  2. We encode the input and output signals, that is
    • find the number of inputs of the structural machine   5: Structural Machine Synthesis , (   5: Structural Machine Synthesis - the number of input signal abstract machine);
    • number of exits 1 type   5: Structural Machine Synthesis ; (   5: Structural Machine Synthesis - the number of output signals of type 1);
    • number of exits 2 types   5: Structural Machine Synthesis , (   5: Structural Machine Synthesis - the number of output signals of type 2) and encode the input (table 5.2) and output signals (table 5.3) and (table 5.4) of the abstract automaton.
      Table 5.2.
      z f / x 1 x L x 1 x 2 ... x 1
      z
      z
      ...
      z
      Table 5.3.
      w f / y 1 y 2 ... y N y 1 y 2 ... y N
      w 1
      w 2
      ...
      w G
      Table 5.4.
      u h / r 1 r 2 ... r D r 1 r 2 ... r D
      u 1
      u 2
      ...
      u H
  3. The structural automaton is represented by the generalized scheme (Fig.5.6).
      5: Structural Machine Synthesis

    Fig. 5.6.
  4. We compile a coded output table of the automaton and write the output equations using it.
    •   5: Structural Machine Synthesis ;
    •   5: Structural Machine Synthesis ;
    • . . .
    •   5: Structural Machine Synthesis ;
    •   5: Structural Machine Synthesis ;
    •   5: Structural Machine Synthesis ;
    • . . .
    •   5: Structural Machine Synthesis ;
    • . . .
  5. We compile a coded automaton transition table and write equations for the excitation functions using it, using the transition tables of the corresponding memory elements.
    •   5: Structural Machine Synthesis ;
    •   5: Structural Machine Synthesis ;
    • . . .
    •   5: Structural Machine Synthesis ;
  6. The equations of excitation functions and outputs are minimized (using Carnot cards, for example) and a circuit is constructed from them in a given functional-logical basis ({AND, OR, NOT}, {AND-NO}, {OR-NOT}).

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Theory of Automata

Terms: Theory of Automata