Automaton State Coding

Consider the heuristic coding method in this example.

For the Moore automaton, we construct a matrix M consisting of the numbers of states for which there are transitions in the transition table. Moreover, it is built in such a way that one of the elements of this line is contained in the previous one.

Encode the states from the first row of the matrix

a 0 =000, a 1 =001.

On the Karnot map, we mark the encoded states:

Table 4.11 – Encoded states on the Karnot map.

Q 1 Q 2 Q 3

From the matrix M we delete rows consisting of encoded states. We get the matrix M’.

Let us choose an unencoded element 2 from the first row of the matrix M’. Construct the matrix , consisting of the rows of the matrix M’, including the element 2. In this matrix, we select the already encoded elements. We get the set B 2 ={1}. For each element B 2 we find a set of codes adjacent to the code of the state under consideration and still unoccupied for encoding. . To select a code, we find the value of the weight function W, which characterizes the distance between state codes, equal to the number of memory elements that change their state during the transition.

We choose the code for which the weight function is minimal. In this case, for both codes of the set we got equal values of the weight function, so we take any code. For example, a 2 =101.

We mark a new state a 2 on the Carnot map.

Table 4.12 – Encoded states on the Karnot map.

Next, we cross out the lines containing the already encoded states, and perform the actions described above.


a3 =100

Table 4.13 – Encoded states on the Karnot map.

Similarly, we get a 4 =011.

Obtaining Memory Block Excitation Functions and Output Functions

Table 4.14 – Encoded jump table.

Let us choose the JK flip-flop as the memory elements.

Table 4.15 – Truth table for excitation functions of memory elements.

0- 0- one – 0- 0- 0-
one – 0- – 0 0- 0- – one
– 0 0- – 0 – 0 0- – one
– one 0- one – – one one – one –
0- – one – 0 0- – one – one
Q 1 Q 2 Q 3 J 1 K 1 J 2 K 2 J 3 K 3 J 1 K 1 J 2 K 2 J 3 K 3

After minimization, we get:

, ,

, ,


After minimizing the output function, we get .

Examples of combinational circuits of synchronous automata

Figure 4.1 – Diagram of the Moore automaton.

When developing the combinational circuit, JK flip-flops controlled by the edge of the clock signal were used, which are located in ComponentsDigital PrimitivesEdge Triggered Flip-FlopsJKFF. To set the triggers to the initial state, a single signal is applied to the PREB input, and to the CLRB input – at the initial moment 0 , and after a short time interval 1 of the generator U3.

Figure 4.2 – Diagram of the operation of the Moore machine.

For the Mealy machine, the encoded transition table has the following form:

Table 4.16 – Encoded transition table of the Mealy machine.

Table 4.17 – Truth table for trigger excitation functions.

0- one – 0- 0-
one – – one 0- – one
– 0 0- – 0 one –
– one – 0 – one – one
Q 1 Q 2 J 1 K 1 J 2 K 2 J 1 K 1 J 2 K 2



Figure 4.3 – Combination scheme of the Mealy automaton.

Figure 4.4 – Diagrams for the circuit in Figure 4.3.


General information

Unlike synchronous automata, where the signals are determined by a clock pulse, in asynchronous automata, transitions between automaton states are caused by a direct change in input signals. Thus, the new state of the automaton is a function of the current state and the previous input signal. Designing asynchronous automata includes the same development steps as synchronous automata. The first step is to build an automaton graph by analyzing the response of the automaton to input actions. In this case, it should be taken into account that the simultaneous change of several input signals is impossible, therefore, transitions with such input signals are not considered. The next steps are building a jump and output table and minimizing the jump table. Then the states are coded. Asynchronous automata can be executed without allocating a memory block, using the dependence of the new state of the automaton on the state before the change in the input signal and on the input signal. When designing asynchronous automata with the allocation of a memory block, synchronous triggers controlled by the level of the clock signal can be used as memory elements. To construct a combinational circuit, it will be necessary to determine the excitation functions of the memory block and the functions of the output signal.

Consider an example of constructing a Moore and Mealy automaton with and without allocation of a memory block.

Abstract synthesis.

Let’s design an automaton that detects the sequence 10,00,10,11. When this sequence appears at the input of the automaton, the output is one, in all other cases 0.

Let’s define the input alphabet X={ 00, 01, 11, 10 }. At the output of the automaton, a binary signal is issued, therefore, the output alphabet is Y={ 0, 1 }.

To determine the alphabet of states and the transition graph, we analyze the operation of the automaton.

At the first moment, the automaton is in the initial state a 0 . When the signal 10 arrives, the machine switches to a new state a 1 . On all other signals (00, 01, 11), the automaton will remain in the initial state a 0 , waiting for the start of the specified sequence. The automaton will be in the state a 0 with the input signal 10 unchanged, therefore, the state a 0 is stable or stable. From state a 1 when the signal changes to 00, the automaton, noting the arrival of the correct sequence, will move to the next state a 2 , at signal 11, the automaton should return to its initial state. Signal 01 is not considered at all, since in order to receive such a signal at the input, when the automaton is in state a 1 with input signal 10, two digits must change simultaneously, which is impossible. From the state a 2 under the influence of a change in the signal by 10, we provide a transition to the state a 3 , 01 – to the initial state, 11 – is not considered. If the automaton is in state a 3 and signal 11 is applied to the input of the automaton, this means that the sequence of signals specified in the condition has arrived, so the automaton will go to state a 4 , which corresponds to a single output signal. When the signal changes to 00 in state a 3, the automaton will go to the initial state, since an incorrect sequence of signals has arrived. From state a 4 , in which the automaton will be at a constant signal at input 11, the automaton will go to the initial state under the influence of input signal 01, when signal 00 is applied, the automaton will go to state a 1 , since signal 00 is the beginning of a given sequence.

Figure 5.1 – Automaton graph.

Table 5.1 – Primary transition table of the automaton:

a 0 a 0 a 0 a 0 a 1
a 1 a 2 a 0 a 1
a 2 a 2 a 0 a 3
a 3 a 0 a 4 a 3
a 4 a 0 a 4 a 1

Table 5.2 – Table of outputs of the Moore machine.

It is possible that the transition table obtained by analyzing the response of the automaton to input signals will contain an excessive number of states. Minimization is performed to exclude such states.

Be First to Comment

Leave a Reply

Your email address will not be published.