Combinational logic circuit

1. About combinational logic circuits

If you design a logic circuit using the logic operations and logic gates you have seen before, and become familiar with the Karnaugh map as a tool to simplify it, you are ready for the logic circuit. From now on, we will look at combinational logic circuits that are frequently used as a module by combining logic circuits with specific functions.

 

2. Comparator

First, the comparator referred to here is a digital comparator. Therefore, the value used for the input corresponds only to digital ‘0’ or ‘1’, and it is a circuit that compares the two inputs. When comparing input A(comparandum) and input B(comparand), there are four possible outputs: ‘Equal’, ‘Not-equal’, (B is)’Greater’, and (B is)’Less’. Among them, ‘Equal’ and ‘Not-equal’ have an inverted relationship with each other, so ‘Not-equal’ can be obtained by adding NOT logic to ‘Equal’, so three are mainly used. By naming each output as E(Equal), G(Greater), and L(Less), a truth table can be constructed as shown below.

 

Input		Output
A	B	E	G	L
0	0	1	0	0
0	1	0	1	0
1	0	0	0	1
1	1	1	0	0

 

The truth table is the same as the description, output E is when A＝B＝0 and A＝B＝1, output G is when A＝0<B＝1, output L is when A＝1>B＝0 1 can be seen. This can be expressed as a logic gate as:

 

 

As shown in the figure, select one of NOT×2+AND×2+OR×1 or XNOR logic gate for output E=A’·B’＋A·B, and other outputs are G=A’·B, L=A·B’ to apply the NOT and AND logic gates. For reference, if necessary, it is also possible to make NE(Not-equal) using an XOR logic gate.
  In the case of more than two digits, the output E must be the same after comparing all digits, so the result of AND operation of the entire XNOR logic result for each digit can be expected. The outputs G and L are tricky. If they are different, the comparison ends immediately after comparing from the highest digit, and only in the same case, a chain comparison is needed to go down to the lower digit and compare again. In other words, the corresponding digits are different and all of the upper digits must be the same, and this is done for all digits. The comparator for two-digit numbers is:

 

Input				Output
A1	A0	B1	B0	E	G	L
0	0	0	0	1	0	0
0	0	0	1	0	1	0
0	0	1	0	0	1	0
0	0	1	1	0	1	0
0	1	0	0	0	0	1
0	1	0	1	1	0	0
0	1	1	0	0	1	0
0	1	1	1	0	1	0
1	0	0	0	0	0	1
1	0	0	1	0	0	1
1	0	1	0	1	0	0
1	0	1	1	0	1	0
1	1	0	0	0	0	1
1	1	0	1	0	0	1
1	1	1	0	0	0	1
1	1	1	1	1	0	0

 

(Transformation process omitted)

E＝A₁’·A₀’·B₁’·B₀’＋A₁’·A₀·B₁’·B₀＋A₁·A₀’·B₁·B₀’＋A₁·A₀·B₁·B₀＝(A₁’·B₁’＋A₁·B₁)·(A₀’·B₀’＋A₀·B₀)

G＝A₁’·A₀’·B₁’·B₀＋A₁’·A₀’·B₁·B₀’＋A₁’·A₀’·B₁·B₀＋A₁’·A₀·B₁·B₀’＋A₁’·A₀·B₁·B₀＋A₁·A₀’·B₁·B₀＝A₁’·B₁＋A₁’· A₀’·B₀＋A₀’·B₁·B₀

L＝A₁’·A₀·B₁’·B₀’＋A₁·A₀’·B₁’·B₀’＋A₁·A₀’·B₁’·B₀＋A₁·A₀·B₁’·B₀’＋A₁·A₀·B₁’·B₀＋A₁·A₀·B₁·B₀’＝A₁·B₁’＋A₀·B₁’·B₀’＋A₁·A₀·B₀’

 

 

The left side shows the result of simplification, and the right side shows the way people go down by comparing from the upper digit when comparing. In the case of the right side, an intermediate process is taken as an input, so some experience may be required for transformation. Although the two figures show the same results, it can be expected that the difficulty, size, and manufacturing cost will be different during actual manufacturing.
  In the circuit described above, comparison of many digits is possible by adding logic whenever a digit is added. Based on this combined logic circuit, it is possible to compare numbers.

 

3. Adders and Subtractors

It is a circuit that performs addition and subtraction, which will be the basic of the four arithmetic operations.
  First, consider an adder that can perform addition. Assume that we initially take two inputs that are single-digit numbers and calculate them. In the case of addition, if there is one number of ‘1’s in input A(augend) and input B(addend), the output is 1₁₀, and if there are two, rounding occurs to 2₁₀(=10₂). The sum of the two inputs is written as S(Sum), and the carry-up according to the number of digits exceeded is written as C(Carry), and summarized in the table as follows.

 

Input		Output
A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

 

According to the truth table, an XOR logic gate is applied to S＝A·B’＋A’·B(NOT×2＋AND×2＋OR×1 is also possible), and an AND logic gate is applied to C＝A·B. Expressed in a picture, it is as follows.

 

 

This logic circuit is the most basic circuit for addition in a computer and is separately named Half adder(HA). This is enough for the least significant digit, but the higher digits need to take as input the rounding that occurred in the lower digit and add them additionally. That is, since the sum of A and B and the received carry-up can be from a minimum of 0₁₀ to a maximum of 3₁₀(=11₂), carry-up may occur naturally. It is the input C_I that has been carry-up from the lower digit, and the carry-up that occurred at the corresponding digit is classified as the output C_O, and summarized in the table as follows.

 

Input			Output
A	B	CI	S	CO
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

 

According to the truth table, expressed as S＝A’·B’·C_I＋A’·B·C_I’＋A·B’·C_I’＋A·B·C_I＝(A·B’＋A’·B)·C_I’＋(A·B’＋A’·B)’·C_I, C_O＝A’·B·C_I＋A·B’·C_I＋A·B·C_I’＋A·B·C_I＝A·B＋(A·B’＋A’·B)·C_I, and expressed as a circuit, it is as follows.

 

 

Looking at the configuration, you can see that it is a Half adder×2+OR logic gate, and this configuration is collectively called a Full adder(FA). In this way, it is possible to add numbers using a half adder or a full adder.

 

Next, consider a subtractor capable of subtraction. Again, it is assumed that the first two inputs are taken and calculated. In the case of subtraction, if B is less than A among input A(subtrahend) and input B(minuend), the output is 1₁₀, and if it is larger, －1₁₀(= 11₂), a negative number occurs, so borrowing is necessary. Write the difference between the two inputs as D(Difference), and the borrowing due to lack of digits as Br(Borrowed), summarized in the table below.

 

Input		Output
A	B	D	Br
0	0	0	0
0	1	1	1
1	0	1	0
1	1	0	0

 

According to the truth table, an XOR logic gate is applied to S＝A·B’＋A’·B(NOT×2＋AND×2＋OR×1 is also possible), and a NOT＋AND logic gate is applied to Br＝A’·B. Expressed in a picture, it is as follows.

 

 

This logic circuit is the most basic circuit for subtraction and is named Half subtractor (HS). This is enough for the lowest digit, but the higher digits need to take as input the borrow from the lower digit and subtract it further. That is, if A is subtracted from B and borrowed down, it can be from a minimum of －2₁₀(＝10₂) to a maximum of 1₁₀, so borrowing may occur again. The borrowing request in the lower digit is classified as input Br_I, and the borrowing generated in the corresponding digit is classified as output Br_O, and the table summarizes them as follows.

 

Input			Output
A	B	BrI	D	BrO
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	1
1	0	0	1	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

 

According to the truth table, It becomes D＝A’·B’·Br_I＋A’·B·Br_I’＋A·B’· Br_I’＋A·B·Br_I＝(A·B’＋A’·B)·Br_I’＋(A·B’＋A’·B)’· Br_I, Br_O＝A’·B’·Br_I＋A’·B·Br_I’＋A’·B·Br_I＋A·B·Br_I＝A’·B＋(A·B’＋A’·B)’·Br_I, and when expressed as a circuit, it is as follows.

 

 

Looking at the configuration, it can be seen that it is a Half subtracter×2+OR logic gate, and this configuration is collectively called a Full subtractor(FS). In this way, it is possible to subtract numbers using a Half subtractor or a Full subtractor. However, since subtraction of binary numbers can be replaced with addition using 2’s complement, adders are relatively more used.
  In addition, a multiplier that repeats addition as many times as the multiplier and a divider that repeats subtraction as many times as the quotient can be expected to be designed, but it is omitted.

 

4. Encoder and Decoder

It is a circuit that performs an encoding function to reduce the number of lines and a decoding function to restore it back to its original state.

First, in the case of an encoder, it is a circuit that changes the sequence number of a signal to a binary format(encoding), and the number of inputs is greater than that of outputs. In general, when the number of inputs is 2ⁿ, there is a relationship in which the number of outputs is n. For example, if the number of inputs is 8, the number of outputs is 3 (8×3 encoder), and if there are 16 inputs, there are 4 outputs (16×4 encoder). If the input I is 4 in order, the output O becomes 2(4×2 encoder). The relationship is summarized as follows.

 

Input				Output
I3	I2	I1	I0	O1	O0
0	0	0	1	0	0
0	0	1	0	0	1
0	1	0	0	1	0
1	0	0	0	1	1

 

If arranged according to the truth table, it can be arranged as O₀＝I₃’·I₁＋I₃·I₁’ and O₁＝I₃’·I₂＋I₃·I₂’. And as shown in the table, it can be seen that the binary representation of the output increases with each increase from sequence number 0. The peculiar thing is that, on the premise that only one of the inputs is input, only 4, the number of all cases for 2 outputs, are checked. The above table is expressed as a figure as follows.

 

 

Next, in the case of a decoder, it is a circuit that changes binary numbers according to the signal sequence(decoding), and the number of inputs is smaller than that of outputs. In general, when the number of inputs is n, there is a relationship in which the number of outputs is 2ⁿ. For example, if the number of inputs is 3, the number of outputs is 8(3×8 decoder), and if there are 4 inputs, 16 outputs(4×16 decoder). If the input I is 2, the output O is 4(2×4 decoder), and this relationship is summarized as follows.

 

Input		Output
I1	I0	O3	O2	O1	O0
0	0	0	0	0	1
0	1	0	0	1	0
1	0	0	1	0	0
1	1	1	0	0	0

 

If arranged according to the truth table, it can be arranged as O₀＝I₁’·I₀’, O₁＝I₁’·I₀, O₂＝I₁·I₀’, O₃＝I₁·I₀. As shown in the table, every time the input binary number increases It can be seen that the sequence number of the output increases. A pictorial representation of this table is as follows.

 

 

As mentioned once, the general purpose of an encoder is to receive an external input from a computer, etc. and change it to an internally used code(binary number), and a decoder to reconvert the internally used code when outputting it to the outside. When designing a logic circuit, it is often used as a circuit for controlling other circuits with fewer signals than being used alone.

As an aside, the encoder that encodes and the encoder that measures the rotation angle of the motor have the same English notation, so be careful not to misunderstand when looking for it for the first time.

 

5. Multiplexer and Demultiplexer

It is a circuit that selects to output only one of several lines or distributes one line to several lines.

First, if you look at the multiplexer(MUX), when the number of inputs is 2ⁿ(=N) and the number of outputs is 1, a circuit that receives additional n inputs S to select only one of them (N：1 multiplexer). For example, when there are 4 inputs I, 2 inputs S (4：1 multiplexer) are summarized in the table below.

 

Input						Output
(I3)	(I2)	(I1)	(I0)	S1	S0	O
X	X	X	X	0	0	I0
X	X	X	X	0	1	I1
X	X	X	X	1	0	I2
X	X	X	X	1	1	I3

 

As indicated in the table, the nth input I and the output O are equal to the input S. Since '1' occurs at output O only when input I_n selected in this way is '1', O＝(S₁’·S₀’)·I₀＋(S₁’·S₀)·I₁＋(S₁·S₀’)·I₂＋(S₁·S₀)·I₃ can be written. For reference, since the input I_n is meaningless, it is generally omitted, and the output is always one due to the characteristics of the circuit. These tables are represented graphically as follows.

 

 

It is a circuit that is often used when the number of input lines is insufficient, and it can be seen that the shape of the decoder for line selection remains on the logic circuit. However, note that what is described here is a digital multiplexer, and the characteristics of the analog multiplexer and input/output are different. In addition, the concept of selecting a line is often expressed as a symbol of a switch for convenience.

 

If you look at the following demultiplexer(DEMUX), when the number of inputs is 1 and the number of outputs is 2ⁿ(=N), it is a circuit that additionally receives n inputs S to be distributed to only one output(1:N demultiplexer). For example, when there are 4 outputs O, the relationship in which the input S becomes 2 (1:4 demultiplexer) is summarized in the table below.

 

Input			Output
I	S1	S0	O3	O2	O1	O0
X	0	0	0	0	0	I
X	0	1	0	0	I	0
X	1	0	0	I	0	0
X	1	1	I	0	0	0

 

As indicated in the table, the input S makes the input I and the nth output O equal. In this way, when input I is ‘1’, ‘1’ occurs only at the selected output O_n, so O₀＝(S₁’·S₀’)·I, O₁＝(S₁’·S₀)·I, O₂＝(S₁·S₀’)·I, O₃＝(S₁·S₀)·I can be written. For reference, in the case of input I, since it is meaningless, it is generally omitted, and this input is always one due to the characteristics of the circuit. These tables are represented graphically as follows.

 

 

The demultiplexer is not used relatively well compared to the multiplexer, but it is useful for parallel testing of various circuits with the same input. And it can be seen that the shape of the decoder remains on the logic circuit like the demultiplexer. For reference, in the case of digital, there is an input/output direction to distinguish the multiplexer and the demultiplexer, but in an analog environment, there is no concept of input/output, so the multiplexer and the demultiplexer are generally used identically.

 

6. Conclusion

In addition to the above, there are various types of combinational logic circuits such as parity generators(or checkers), binary-to-gray code converters, and BCD-to-decimal converters. When a specific function is needed in a logic circuit, if there is a function of logic circuit that corresponds to it, find and apply it in a combinational logic circuit rather than designing it yourself.