Applied Theory of Digital Automata

The topic covers the fundamentals of analysis and synthesis of simple and finite automata with memory.

Forms of representing automata in different bases using switching functions are given, along with their minimization using the Quine method, the implicant matrix, the Veitch diagram, etc.

A methodology for constructing logic circuits is given.

Attention is given to finite automata with memory, various forms of their representation, the methodology for constructing coded tables, and structural synthesis.

Switching functions and their basic properties.

• 1.1. Basic concepts
• 1.2.Elementary switching functions
• 1.3. Expressing some switching functions in terms of others
• 1.4. Basic classes of switching functions
• 1.5. Functionally complete systems
• 1.6. Forms of representing switching functions

2. Minimization of switching functions.

• 2.1. Basic concepts
• 2.2. Methods for obtaining a reduced disjunctive normal form
• 2.3. Methods for obtaining irredundant and minimal forms

3. Analysis and synthesis of combinational circuits.

• 3.1. Logic networks
• 3.2. Analysis of logic circuits
• 3.3. Synthesis of a logic circuit
• 3.4. Synthesis of a logic circuit with one output
• 3.5. Synthesis of logic circuits with multiple outputs
• 3.6. Synthesis of circuits for incompletely specified functions of their own

4. Analysis and synthesis of finite automata with memory.

• 4.1. Basic definitions
• 4.2. Structural synthesis of an automaton

The main purpose of a computer's functional units is the conversion of information. An information converter is a device with a finite number of inputs, to which information is supplied, and a finite number of outputs, from which the converted information is taken. In physical systems, the nature of the information conversion process is determined by the operating law of that system. In particular, a converter that transforms information from direct code into one's complement code converts the source information into one's complement code, an adder converts the addends into a sum, a shift circuit converts information into information shifted relative to the original, and so on. When considering the conversion process, it is convenient to encode information as a sequence of symbols (letters) from some finite alphabet. Any such sequence is called a word in that alphabet. Formally, the process of converting information in some device can be reduced to converting an input alphabet into an output alphabet. Thus, an information conversion device puts into correspondence any word of the input alphabet with some word of the output alphabet. Consider some device (fig.1) with n inputs and m outputs. Any symbol from the finite alphabet X=(x1,x2,…xn) can be applied to each input. A given sequence of symbols applied to the inputs forms the input word Fi in the alphabet X. As a result of the conversion, the output of the device will produce the word Gj , formed in the output alphabet- Y=(y1,y2,…yl ). Because the alphabet X, Y and the lengths of the input and output words are finite (the length of the input word is always n, and that of the output word – m), the total number of input and output

words is finite. Thus, when the input word Fi appears at the output of the device, the device produces at its output a combination of output symbols forming the output word Gj . The operation of such a device is completely defined if a table is given for each admissible word Fi :

A device whose operation is described by the table given above is a finite automaton without memory, or a combinational circuit.

Besides the devices mentioned above, which from a functional standpoint are simple devices, there exist more complex devices, on in – a new state of the automaton. -nated finite automata with to the word uniquely corresponds out tom. This is caused above all by the fact that in computers, in ba e of a pulse, etc. In de a. Suppose, them To each -tion a decimal digit from 0 to 3. The table given above will take the form: -tputs of which the information is determined not only by the input information, but also by the state in which this device was. Such a converter is a finite automaton with memory. The state of such an automaton is determined by the state of the memory. To define the state of the automaton, let us introduce a finite alphabet A=(a0 ,a1 ,….aq). The symbol ai reflects the internal state of the automaton. The pair Fi , ai fully determines the output word and the new state of the automaton into which it will transition after the word Fi is applied to the inputs. The operating rule of such an automaton can be represented by means of a table: (Fi,at) → (Gj ,ar), where Gj – is the output word, ar the structure of the automaton under consideration is given in fig.2

the present course con-siders determi- automata with memory and without memory, in which to each input e out-put signal corresponds. In computers, input and output information is encoded with a two-letter binary alphab – in general, a binary number system or number systems with another base with binary encoding of symbols are used. In addition, in a computer, two-position elements are used to store information, for which binary encoding of the state is natural. A physical analog of the binary alphabet in computer circuits can be a high or low potential, the presence or absen -termining the operation of the circuit, these quantities can be expressed by any pair of symbols. Usually such symbols are 1 and 0. In accordance with this, the operation of any computer circuit is defined as follows: a certain set of zeros and ones is applied to the input of the circuit, which causes a certain set of zeros and ones to appear at the output of the circuit. Let us consider an example of such encoding . Suppose that the alphabet X=(x1,x2 ,x3) contains three symbols, the alphabet Y=(y1 ,y2 ,y3 ,y4 ) – four symbols. We ha-ve a finite automaton without memory that converts a word consisting of two symbols of the alphabet X into a word of one symbol of the alphabet Y. Let us represent the operating rule of the automaton by means of the following table:

To each -tion a decimal digit from 0 to 3. The table given above will take the form:

in the present course, questions related to the analysis of finite automata are con-sidered. Of simple circuits or elements, in which the assembled circuit implements the specified rule -re. Methods for synthesizing computer circuits in modern literature are developed mainly on the basis of mathematical logic and the theory of discrete automata. To solve the synthesis problem, first of all, on the basis of which the converter circuit must be built. One and the same law of information conversion can be implemented by means of various circuits. To evaluate the technical implementation, criteria are introduced: the complexity of the circuit, its speed, and its reliability. Methods are de-termined on the basis of the chosen criteria, since in one case preference in evaluating a circuit may be given to speed, in other cases – to its complexity or reliability. The task of circuit analysis consists in representing them in analytical form, for the purpose of their evaluation or further conversion.