Electronic digital circuit can formally be divided into 2 class:

Combinational Circuit (The COP) – have no memory. The output signal is formed depending on combinations of the input data in a fixed moment of time (given the delay for signal conversion).Combinational circuit, their types and principles of construction can be a topic for another article, as examples: Managed bus, multiplexers and demultiplexers, decoders and encoders, code converters, matching counters and adders, and the t. d.

Circuits with memory – the algorithm depends on the input status and memory (in, in previous times). These schemes are described using the theory of finite automata. It's about them and will continue.

In other words first grade — logic devices, processing the input signal. Second elements having a memory and responsive to the signal depending on the entered data.

 Abstract machine

The machine will have to implement some functions, are specified by the developer. It may be a simple adder, can implement any microcomedo CPU, choose words from memory or to deal with parsing expression.

In General, without going into details, the abstract machine can be represented as follows:

Or, if you go from illustration to mathematical description:

A = <A, B, C, δ, λ>

Designation:

Many {A} – is a set of values at the physical inputs of the machine. The input in our case we have a sequence of high and low voltage levels, which will encode logical ones and zeros.

Many {B} – is a set of values at the physical outputs of the machine.

Many {C} – and many, which represents the internal state of the machine memory. Future C0 we denote the initial state of the automaton.

δ = X × Z → Z is the transition function of the machine, they uniquely determine the state ai in which the machine moves from state aj.

λ = X × Z → Y – output functionality, they define what is at the output of the machine depending on the inputs and internal state.

δ and λ are not shown for visual simplification.

Such an automaton operates in discrete time, the values of the inputs, outputs and internal state of the automaton changes in discrete moments of time.

So we in General terms describe what is an Abstract machine. An example of such a machine can be a trigger, register the computer or the adder.

Allocate 2 type machines:

Machines Miles. Described by a system of equations:

c(t) = δ( a(t), c(t-1) );

b(t) = λ( a(t), c(t-1) ).

Moore Machines. Described by the equations:

c(t) = δ( a(t), c(t-1) );

b(t) = λ( a(t), c(t) ).

As you can see the condition of the machine c(t) in the current time is a function of its state at the previous time and the input signal.

Machines differ by the form of the output function. In the combinational output signal is determined by input signal a(t) and the state in the previous time c(t-1). The output of Moore machine is defined by a pair of input signal a(t) and the status at the moment c(t).

You can also note, that one type, you can proceed to the second and Vice versa, moreover, in the transition from combinational to the Moore machine, the number of internal States of the automaton will remain the same, and if you switch back the number of internal States may increase. To stop in detail will not, considering, what synthesized(drew Earl) machine type, want.

So, the materiel is over. Let's try to describe the machines.

Ie. machine type Miles provides an output signal when the input changes, depending on its previous state. The duration of the output signal does not depend on the duration of the input, but only from his presence. In machines of type Moore the output signal depends on the state of the machine at the current time ie. the machine will produce a specific output signal until it changes its state.

Methods of setting machines

As we explained in the first part — the machine is a set of input and output alphabets, the many internal States and functions, defining transitions and outputs. However, usually the functions δ and λ not specified, and the behavior of the machine have to be described differently.

There are two main ways of specifying the machine:

1. With the help of graphs.
2. With the help of tables of transitions and outputs.

Graphs

A graph automaton is a directed connected graph, vertices which represent the internal state of the machine, as the arc transitions from one state to another.

To count the Miles on the arcs indicate similar and output letters. Weekend letters are written on the arcs, symbolizing the, because the output state depends on the state of the machine in the previous time.

For Moore machine graph on the arcs are written only input letters, weekend indicated near the vertices.

An important point: If each vertex goes so much Doug, how many there is an input of letters, the machine is called a full. In other words, if each vertex is defined a transition for each input letter. In our examples, the Miles machine is full, a Moore machine – fractional.

And: If one vertex is out the arcs more, than the input letters (that is 2 or more arcs with the same input letters), such a machine is called nondeterministic. This can happen when building a formal description and then it will be necessary to make the transition to a deterministic machine, but it is not always possible to perform. The description of this process I also miss, immediately drawing a deterministic automaton.

At the same time on all graphs.

The table of transitions and outputs.

The graphs are clearer to humans, a table for the machine. Any machine can be represented as a table of transitions and outputs (TPV). In TPV lines are internal States, and columns – input the letters.

We will construct our graphs TPV for Miles and Moore. If you have not defined any input or output letter, instead, put a dash. If not defined, the status, there is a simple rule.

TPV Earl Miles

 

In TPV Miles in each cell of the recorded transitions and outputs. For example, if the machine is in state C0 and the input letter a1 comes, he goes into a state of C1 and the output appears b3.

TPV Earl Moore

For count Moore noted build the jump table. Allocated an additional column for the output letters.

In the cell under the input letter is written in what state the machine transitions, in the rightmost cell which returns the output alphabet.

An example of the synthesis machine

Using abstract machines to describe almost anything. It is possible to describe the operation of digital circuits, a syntactic or a lexical analyzer. Let's try to describe the trigger – nothing machine?

To set the count need a verbal description of algorithm of operation of the trigger. Read:

Encode the input and output alphabets:

A = {a0, a1}, where a0 is a logical 1 the input R, a1 is a logical one at input S.

B = {b0, b1}, where b0 is the logical 0 the output Q, b1 – a logical one at the output Q.

Build a graph of combinational:

That's such a funny Cheburashka turned out :-). You can now build a table of transitions and outputs:

If to paint this table converting the symbols in the actual, we get a table which is a table of transitions of the trigger. Then you can simplify:

Inflict function on this map Veitch and minimize:

Let us write, what happened:

Build function diagram:

A bit unusual to see a trigger in the Boolean basis, so let's translate function in basis AND-NOT and draw a diagram in it:

 

And the diagram of the asynchronous RS trigger is indicated here:

Now if you make a little effort, it is possible to independently synthesize simple Christmas garland.