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

All electronics surrounding us consists of separate microcircuits, more complex electronics - from functional blocks constructed on their basis.

At this stage, computers literally create themselves, it became impossible to synthesize even the simplest microprocessor without using a computing device.

But what is still the basis of the chip itself? How to create a simple digital device with the required output function?

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

Bit of theory

All elementary digital devices (DU) are divided into combinational and serial. In combinational control units, the output signals are uniquely determined by the combination of current input signals. The output signals (functions) of sequential control units are determined by the sequence of changes in the input signals (coordinates).

At the heart of almost all digital circuits are the simplest logical elements AND , OR , NOT . Naturally, there can be a lot of options for the implementation of the control center, depending on combinations of composite elementary logic elements. Therefore, we make a reservation in advance that we will produce synthesis in the basis of NAND, i.e. we use only this element during the construction of the control center.

I think that the Habr audience 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 a sequential CPU. As an example, take a converter from direct to additional code (for three-digit code).

An additional number code is formed by adding 1 to the least significant bit of the inverted number. For example, we have the number A = 10110 (the most significant digit on the left). Then the return code for A is 01001, and the additional code is 01010.

Device synthesis

To begin with we will make the truth table.
Designations: x - input signals, y - output. Index "1" - in the least significant bit.



Now it is necessary to express the output signals depending on the input using the simplest logical functions (according to the terms of the assignment, we will use the AND-NOT basis).

Most often, two forms of recording are used - the perfect disjunctive normal form (SDNF) and the perfect conjunctive normal form (SKNF).

In the first case, each set of variables from the truth table is assigned a minterm- the logical product of all variables that are in direct form if the value of the variable is 1, or in the inverse form if the value of the variable is 0. Any logical function can be represented as a logical sum of minterms corresponding to unit sets of variables (sets in which the logical the function takes the value 1). This view is called SDNF. To implement the TS in the AND NOT basis, it is advisable to represent the output function in the form of SDNF.

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

We write the output function y1 in the form of SDNF:

Carnot Maps

It can be seen that the expression turned out to be 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. To do this, you can apply 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 using Carnot maps is determined by a specially selected order of cell numbering, in which any adjacent pair of cells with units or zeros horizontally or vertically corresponds to gluing terms or factors of the formula. If the structural formula is obtained on the basis of SDNF, then only the cells of the map that determine the individual sets are taken into account. (In the case of SKNF - zero).

Adjacent cells of the card with units or zeros are combined into a group. When combining, they use the following rules:
1) neighboring are not only cells located horizontally and vertically next to each other, but also cells on opposite borders of the map;
2) cells can combine in 2, 4, 8, etc .;
3) the same cell can belong to several groups;
4) the minimized structural formula is written on the basis of the smallest set of groups that captures (covers) all either single (if SDNF is used) or zero (SKNF) cells.

In the first case, the structural formula is a logical sum, each of the terms of which corresponds to one of the card groups. Moreover, each term includes only those variables that do not change their meaning 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 written on the basis of the map group.

Next, we will indicate in our maps only single sets. We will leave the “zero” cells empty.

It's time to start ...

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

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

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



Now we can synthesize our


control center according to the received functions: We have received a ready-made digital device — a three-digit code converter from direct to additional.

I do not know how relevant the above synthesis method is. I tried to explain everything at the level at which I myself understand this topic. I look forward to comments from competent Habrovsk.

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