Synthesis of combinational devices on the example of the converter from direct code to additional

All the electronics around us consists of individual microcircuits, more complex electronics - of functional blocks built on their basis.

At this stage, computers literally create themselves; it has become impossible to synthesize even the simplest microprocessor without using a computing device.
')
But what all the same underlies the microcircuit? How to create a simple digital device with the required output function?

Under the cut - an example of the synthesis of the device with all the necessary theory.

Some theory

All elementary digital devices (DD) are divided into combinational and sequential ones. In a combinated digital output, the output signals are uniquely determined by the combination of input signals that are currently active. The output signals (functions) of sequential DDs are determined by the sequence of changes in the input signals (coordinates).

The basis of almost all digital circuits are the simplest logical elements AND , OR , NOT . Naturally, there may be a lot of options for the implementation of the DD, depending on the combinations of composite elementary logic elements. Therefore, we will make a reservation in advance that we will produce the synthesis in the AND-NOT basis, i.e. we use only this element in the course of building the CO.

I think that the audience Habra knows the basics of the algebra of logic. I will give only a couple of formulas:

Formulation of the problem

In this article, we consider an example of the synthesis of sequential DD. As an example, take a converter from a direct code to an additional one (for a three-digit code).

An additional number code is formed by adding 1 to the lower-order digit of the inverted number. For example, we have the number A = 10110 (most significant digit to the left). Then the reverse code for A is 01001, and the supplementary code is 01010.

Device synthesis

To begin with we will make the truth table.
Legend: x - input signals, y - output. Index "1" - at the low bit.



Now it is necessary to express the output signals depending on the input with the help of the simplest logical functions (according to the condition of the task, we will use the basis NAND).

Most often, two recording forms are used - a perfect disjunctive normal form (CDNF) and a perfect conjunctive normal form (SKNF).

In the first case, each set of variables from the truth table is assigned to the minterm - the logical product of all variables that are included in the direct form, if the variable value is 1, or in the inverse form, if the variable value is 0. Any logical function can be represented as the logical sum of the minterms corresponding to the single sets of variables (sets where the logical function takes the value 1). Such a presentation is called PDNF. For the implementation of the CU in the AND-NOT basis, it is advisable to represent the output function in the form of the SDNF.

In the case of SKNF, everything is exactly the opposite. The function is represented as a logical product of maxtherm. Maksterm is the logical sum of all variables that are included directly, if the value of the variable is 0, or in the inverse form, if the value of the variable is 1.

We will write the output function y1 as SDNF:

Carnot maps

It is seen that the expression turned out quite long. It can be simplified by applying the rules of absorption and bonding. In order not to do unnecessary actions, you can immediately get a minimized function. For this, you can use the Carnot map method.

A map is a table, each cell of which corresponds to one of the sets of the truth table. For the logical function of three variables, the Carnot map consists of two horizontal rows of four cells. The meaning of the use of Carnot maps is determined by a specially chosen order of cell numbering, in which any adjacent pair of cells with ones or zeros horizontally or vertically correspond to glued-together terms or factors of the formula. If the structural formula is obtained on the basis of PDNF, then only the cells of the map defining individual sets are taken into account. (In the case of SKNF - zero).

Neighboring cells of a card with ones or zeros are combined into a group. When combining use the following rules:
1) adjacent are not only the cells located near horizontally and vertically, but also the cells on the opposite edges of the map;
2) cells can be combined 2, 4, 8, etc .;
3) the same cell can belong to several groups;
4) the minimized structural formula is written based on the smallest aggregate of groups that captures (covers) all either single (if CDNF is used) or zero (SKNF) cells.

In the first case, the structural formula presents a logical sum, each of the addends of which corresponds to one of the map groups. At the same time, each term includes only those variables that do not change their value in the sets corresponding to the combined cells. In the second case, zero cells are combined into groups, the minimized structural formula is a logical product, each factor of which is recorded on the basis of a map group.

Further we will indicate in our maps only single sets. “Zero” cells will be left empty.

It's time to start ...

So, we proceed to the synthesis of our device, guided by the above theory.

To begin with, we draw up Carnot maps for all output functions (we have three of them, as well as input functions). The circle labeled cells are combined into one group. Please note, we sum up the products of unchanging (in this group) input signals with the corresponding logic level. The number of terms is equal to the number of groups of associations. The first map combines the 2nd and 3rd cells, as well as the 3rd and 4th cells. In the second - the 2nd and 6th, as well as the 4th and 8th. In the third map, 2, 3, 6, 7th cells are combined into one group.

Next, write to the right in accordance with the rules of combining cells minimized output functions. Since we need to get them in a certain basis, use the algebra of logic, namely, formulas (1) and (2), and express functions through input variables.



Now we can synthesize our DD based on the functions obtained:


We received a ready-made digital device — a three-digit code converter from direct to additional.

I do not know how relevant the above method of synthesis. I tried to state everything at the level on which I understand this topic myself. Waiting for comments from competent habrovchan.

Literature:
Digital and analog-digital devices / A. V. Loginov, An. V. Loginov. LMI, 1989