Chapter 4: Boolean Expressions and Combinational Circuits

In this chapter, we learn how to express Boolean equation with combinational circuits, circuit schematics rules for combinational circuits, and one of the multiple-output circuits – priority circuit. By understanding the meanings of Contention X (don’t care) and floating Z, we can apply the rules of Karnaugh maps for simplifying Boolean equations.

Objectives

By the end of this chapter you should be able to:

• Express Boolean equation with combinational circuits.
• Recognize circuit schematics rules for combinational circuits.
• Recall multiple-output circuits – priority circuit.
• Demonstrate the meanings of Contention X (don’t care) and floating Z.
• Summarize the rules of Karnaugh maps.
• Apply Karnaugh maps for simplifying Boolean equations.

4.1 Circuit Schematics Rules

Digital systems are constructed by using logic gates which are abstract representations of real devices. We can represent the Boolean algebra with two-level logic, ANDs followed by Ors. For example, we have a Boolean equation: . This equation can be designed with logic gates, as shown in the following figure:

Fig. 4‑1. From Logic to Gates

In Fig. 4-1, There are three AND gates. These AND gates have the following inputs,

• AND_1: A complement, B complement, C complement
• AND_2: A, B complement, C complement
• AND_3: A, B, C complement

The outputs of the three AND gates feed into OR gate. The OR gate produces the output Y.

There are some rules for circuit schematics. Wires always connect at a T junction, as shown in Fig. 4-2. A dot where wires cross indicates a connection between the wires. Wires crossing without a dot make no connection.

Fig. 4‑2. Circuit Schematics Rules

The following figures show that there are T junctions between the wires. That means the wires are connected.

Fig. 4‑3. Some examples of Junction

The following figures show that there is no T junction between the wires. That means the wires are not connected.

Fig. 4‑4. Some examples of No Junction

The following figure, Fig. 4-5, designed a Boolean equation. There are five AND gates. These AND gates have the following inputs,

• AND_1: A complement, D
• AND_2: B, D
• AND_3: A, C complement, D
• AND_4: A, B complement, C
• AND_5: A, B, C, D

The outputs of four AND gates (AND_1, AND_3, AND_4, AND_5) feed into OR gate. The OR gate produces the output Y. We can express the corresponding Boolean equation as follows: .

Fig. 4‑5. Some examples of Boolean equation

Multiple-Output Circuits

Circuits that we have previously discussed have only one output. Here we will discuss how multiple output systems are analyzed. A priority encoder is a circuit or algorithm that compresses multiple binary inputs into a smaller number of outputs. The priority circuit produces an output asserted corresponding to the most significant TRUE input. The following figure shows the truth table and the hardware design of the priority circuit.

Fig. 4‑6. Truth Table and Hardware Design of Priority Circuit

The priority circuit has:

• Input A₃ directly connected to Y₃.
• AND_1 gate produces the output Y₂ with two inputs, i.e. A₃ complement and A₂.
• AND_2 gate produces the output Y₁ with three inputs, i.e. A₃ complement, A₂ complement, and A₁.
• AND_3 gate produces the output Y₀ with four inputs, i.e. A₃ complement, A₂ complement, A₁ complement and A₀.

Where the bubble symbol represents a complement. The above truth table can be simplified as the following table.

Table 4‑1. Truth Table of Priority Circuit with Don’t Cares (X)

Let’s look at the case when the output Y₁ is TRUE. A₃ and A₂ didn’t assert, meaning that both A₃ and A₂ are FALSE. In this case, A₁ has a priority among the input values. Once A₁ asserts TRUE, the input A₀ doesn’t matter whether it is TRUE or FALSE. Only Y₁ is TRUE and the other outputs are all FALSE.

Let’s look at the case when the output Y₂ is TRUE. A₃ didn’t assert, meaning that A₃ is FALSE. In this case, A₂ has a priority among the input values. Once A₂ asserts TRUE, the two inputs A₀ and A₁ don’t matter whether they are TRUE or FALSE. Only Y₂ is TRUE and the other outputs are all FALSE.

In the last case where the output Y₃ is TRUE, A₃ has a priority among the input values. Once A₃ asserts TRUE, the other inputs A₀, A₁ and A₂ don’t matter whether they are TRUE or FALSE. Only Y₃ is TRUE and the other outputs are all FALSE. Here, a don’t-care term (X) for a function is an input-sequence (a series of bits) for which the function output does not matter.

With the contention X, circuit tries to drive an output to 1 and 0. The actual value of the contention could be 0, 1, or in forbidden zone. That might change with voltage, temperature, time and noise. The contention often causes excessive power dissipation. However, the contention usually indicates a bug. The symbol, X, is used for “don’t care” and contention. With this don’t care, we can find out some way to simplify the Boolean equation when we design the digital circuits.

The floating Z, high impedance, is driven neither HIGH nor LOW. The floating Z might be 0, 1 or somewhere in between. The tristate buffer is one of example of this floating Z which has three possible output states: HIGH (1), LOW (0) and floating (Z).

The output Y determined by both the input A and the enable E.

• If enable E = 0, then the tristate buffer outputs floating Z regardless of the value of input A.
• If enable E = 1, then the tristate buffer outputs the same as the value of input A.

Fig. 4‑7. Tristate Buffer

The floating nodes are used in tristate busses, where many different drivers use the shared bus with processor, video, Ethernet, memory, etc.

4.2 Karnaugh Maps (K-Maps)

The Karnaugh map (K-map) is a graphical method of simplifying Boolean algebra expressions, where the Boolean expressions can be minimized by combining terms.

Let’s look at a truth table, where the output Y is TRUE if only if the two inputs are A = 0 and B = 1, or A = 1 and B = 1.

The above table can be expressed in the K-map as the following figure, where each value of the squares is corresponding to the value of Y:

• If A = 0 and B = 0, Y = 0 (i.e., ).
• If A = 0 and B = 1, Y = 1 (i.e., ).
• If A = 1 and B = 0, Y = 0 (i.e., ).
• If A = 1 and B = 1, Y = 0 (i.e., ).

Fig. 4‑8. K-Map Representation

In order to simplify the Boolean expression with K-map, we can circle 1’s in adjacent squares, where the most left column and the first row represent the input variables, inputs A and B.

In the following figure, the circle is located in the rightest column, whose literal corresponds to the input B. Let’s look closely at the circle to draw the corresponding literal. The circle takes two rows (, ), i.e. one for the input and another for the input . These two literals, and , are cancelled each. We can only write the literal B, that simplify the Boolean equation.

Fig. 4‑9. K-Map Representation with a Circle

The following figure shows that the circles must span a power of 2.

Fig. 4‑10. K-Map Representation with a Circle

Fig. 4-10 has two red circles, one located at the rightest column and another located at the last row. The first circle takes a single column () and two rows (, ), where and are cancelled each other. We can draw only the literal from this circle. The latter circle takes a single row () and two columns (, ), where and are cancelled each other. We can draw only the literal from the circle. These two literals are Ored, so we can draw the corresponding Boolean equation: from Fig. 4-10.

The 3-input K-Map can be drawn in the following figure:

Fig. 4‑11. 3-Input K-Map Representation

In this K-map, the first row and the most left column represent the input variables.

• First row: inputs A and B
• Most-left column: input C

In the first row, we can identify four different combinations of two inputs; AB=00, AB=01, AB=11, and AB=10, where only one-bit change in value from one adjacent column to the next column is allowed.

Let’s see how to use this 3-input K-Map to simplify the Boolean equation. The following truth table can be mapped to K-map, as shown in Fig. 4-12.

Fig. 4‑12. 3-Input K-Map Representation with Circles

In the K-map of Fig. 4-12, we can identify only 3 squares filled with ‘1’ bit; mapping to , , and . We can circle 1’s in adjacent squares, and have two red circles; one located at the second column of the squares and another located at the last row of the squares. The first circle takes a single column () and two rows (, ), where and are cancelled each other. We can draw the literal from the circle. The latter circle takes a single row () and two columns (, ), where and are cancelled each other, leaving only the literal . We can draw the literals from the circle. These two implicants (product of literals) are Ored, so we can draw the corresponding Boolean equation: from Fig. 4-12.

When we draw a circle in the K-map, we need to draw a circle as big as possible so that the corresponding implicant can be minimized. We called a prime implicant whose implicant corresponding to the largest circle in a K-map.

There are some rules when we draw a circle in a K-map:

• Every 1 must be circled at least once.
• Each circle must span a power of 2 (i.e. 1, 2, 4) squares in each direction.
• Each circle must be as large as possible.
• A circle may wrap around the edges.
• A “don’t care” (X) is circled only if it helps minimize the equation.

Let’s look at another example of 3-input K-map in Fig. 4-13.

Fig. 4‑13. 3-Input K-Map Representation with wrap around edges

In Fig. 4-13, we have the two circles, one for the column and another for the bottom edges of the squares. The first circle takes a single column () and two rows (, ), where and are cancelled each other. We can draw the literals from the circle. The latter circle takes a single row () and two columns (, ), where and are cancelled each other, leaving only the literal . We can draw the literals from the circle. These two implicants (product of literals) are Ored, so we can draw the corresponding Boolean equation: from Fig. 4-13.

The following table shows a 4-input truth table. From the truth table, we can fill out K-map. In the K-map, the first row and the most left column represent the input variables.

• First row: inputs A and B have four different combinations AB=00, AB=01, AB=11, and AB=10, where only one-bit change in value from one adjacent column to the next column is allowed.
• Most-left column: inputs C and D have four different combinations CD=00, CD=01, CD=11, and CD=10, where only one-bit change in value from one adjacent column to the next column is allowed.

Fig. 4‑14. 4-Input K-Map Representation

Let’s see how to use this 4-input K-Map to simplify the Boolean equation. We can draw four circles in the above figure using the rules. The first circle^① takes two columns (, ) and two rows (, ), where and are cancelled each other, and and are cancelled in the same manner. We can draw the literals from the circle. The second circle^② takes a single column () and two rows (, ), where and are cancelled each other. We can draw the literals from the circle. The third circle^③ takes a single column () and two rows (, ), where and are cancelled each other. We can draw the literals from the circle. The last circle^④ is located around the corner of edges and takes two columns (, ) and two rows (, ), where and are cancelled each other, and and are cancelled in the same manner. We can draw the literals from the circle. These four implicants (product of literals) are Ored, so we can draw the corresponding Boolean equation: from Fig. 4-14.

Fig. 4-15 shows an example of 4-input K-map with “don’t cares (X)”. We need to circle every ‘1’ bit at least once. We can also circle “don’t cares (X)” if they help minimize the equation by making the circle as large as possible. If the don’t care (X) doesn’t help to maximize the circle, it can be considered as a ‘0’ bit. The first circle^① takes two columns (, ) and four rows (, , , ), where all the literals are cancelled each other ( and , and , and and ) except the literal . We can draw the literal from the circle. The second circle^② takes four columns (, , , ), two rows (, ), where all the literals are cancelled each other ( and , and , and and ) except the literal . We can draw the literal from the second. The last circle^③ is located around the corner of edges and takes two columns (, ) and two rows (, ), where and are cancelled each other, and and are cancelled in the same manner. We can draw the literals from the circle. These three implicants (product of literals) are Ored, so we can draw the corresponding Boolean equation: from Fig. 4-15.

Fig. 4‑15. 4-Input K-Map Representation with Don’t Cares

Exercise

Simply the Boolean equation with K-map:

Answer: You can get the following equation:

4.3 Combinational Circuits

Combinational Circuits are circuits made up of different types of logic gates and produce outputs by combining the values of the inputs at any given time. The circuits do not make use of any memory or storage device.

Fig. 4‑16. Combinational Circuit Description

For n input variables, there are 2ⁿ possible binary input combinations, and for each binary combination of the input variables, there is one possible output.

The combinational circuit is like a black box but it can be described with the truth table, which gives one possible output for each binary combination of the input variables. We will take a look at some popular combinational circuits throughout this section.

1-Bit Half Adders

A 1-bit half adder is used for adding together the two least significant digits in a binary sum. It has two inputs A and B, and two outputs, the sum S and the carryout C_out. The following table describe the 1-bit half adder. The sum is the output of exclusive OR gate, which has . The C_out (carryout) is the output of AND gate, which has two inputs, A and B, i.e. .

Table 4‑2. Truth Table of 1-bit Half Adder

For the above truth table, we can fill the box of Fig. 4-16 with a combinational circuit of 1-bit half adder in the following figure:

Fig. 4‑17. Combinational Circuit of 1-bit Half Adder

Multiplexer

A multiplexer (or Mux), also known as a data selector, is a device that selects one of N analog or digital inputs and forwards the selected input to a single output line. If the mux has the two inputs, it needs a control input. If the mux has N inputs, it needs control inputs. The following figure shows a 2-to-1 multiplexer which has two inputs (D₀ and D₁), one output (Y), and a control input (S).

Fig. 4‑18. 2-to-1 Multiplexer

If the control input S is 0, the input D₀ is forwarded to the output Y. If the control input S is 1, the input D₁ is forwarded to the output Y. The following table describes the 2-to-1 multiplexer.

Table 4‑3. Truth Table of 2-to-1 Multiplexer

We can simply draw the truth table as follows:

The multiplexer can have more than two inputs. The 4-to-1 multiplexer has four inputs (D₀, D₁, D₂, and D₃), one output (Y), and two select inputs (S₀ and S₁), as shown in the following figure:

Fig. 4‑19. 4-to-1 Multiplexer

The multiplexer operates as follows:

• If the select inputs S₁ S₀ is 00, the input D₀ is forwarded to the output Y. In this case, the other inputs D₃, D₂, and D₁ don’t matter. Only the input D₀ determines the output Y.
• If the select inputs S₁ S₀ is 01, the input D₁ is forwarded to the output Y. In this case, the other inputs D₃, D₂, and D₀ don’t matter. Only the input D₁ determines the output Y.
• If the select inputs S₁ S₀ is 10, the input D₂ is forwarded to the output Y. In this case, the other inputs D₃, D₁, and D₀ don’t matter. Only the input D₂ determines the output Y.
• If the select inputs S₁ S₀ is 11, the input D₃ is forwarded to the output Y. In this case, the other inputs D₂, D₁, and D₀ don’t matter. Only the input D₃ determines the output Y.

Accordingly, we can draw the truth table of 4-to-1 multiplexer as follows:

Table 4‑4. Truth Table of 4-to-1 Multiplexer

where ‘X’ represents the don’t care term.

Fig. 4-20 shows how the 4-to-1 multiplexer operates when the two select inputs S₁S₀ = 00. The input sequence D₀ = 11111111 is forwarded to the output Y. The other inputs don’t affect the sequence of the output Y.

Fig. 4‑20. 4-to-1 Multiplexer with S₁S₀ = 00

Fig. 4-21 shows how the 4-to-1 multiplexer operates when the two select inputs S₁S₀ = 01. The input sequence D₁ = 00001111 is forwarded to the output Y. The other inputs don’t affect the sequence of the output Y.

Fig. 4‑21. 4-to-1 Multiplexer with S₁S₀ = 01

Fig. 4-22 shows how the 4-to-1 multiplexer operates when the two select inputs S₁S₀ = 10. The input sequence D₂ = 11110000 is forwarded to the output Y. The other inputs don’t affect the sequence of the output Y.

Fig. 4‑22. 4-to-1 Multiplexer with S₁S₀ = 10

Fig. 4-23 shows how the 4-to-1 multiplexer operates when the two select inputs S₁S₀ = 11. The input sequence D₃ = 10101010 is forwarded to the output Y. The other inputs don’t affect the sequence of the output Y.

Fig. 4‑23. 4-to-1 Multiplexer with S₁S₀ = 11

The following figure shows the 8-to-1 multiplexer which has eight inputs, D₀ through D₇. Since it has 8 inputs, select bits (select inputs) required.

Fig. 4‑24. 8-to-1 Multiplexer

The output Y is determined by the three select inputs, i.e. S₂, S₁, and S₀. The following table describes the operation of the 8-to-1 multiplexer.

Table 4‑5. Truth Table of 8-to-1 Multiplexer

Encoder

In general, encoders convert motion to an electrical signal that can be read by some type of control devices. One of very popular encoders you know is a keyboard. When you press a button of the keyboard, the keyboard coverts this motion to an 8-bit digital signal. Your computer can read the value you pressed. The encoder is an inverse operation of a decoder. If you have 2^N inputs, the encoder produces a total of N outputs so that it generates the binary code corresponding to the input value.

The following figure shows a 4-to-2 encoder, where there are four inputs, i.e. D₃, D₂, D₁, D₀, and two outputs (binary code), i.e. B₁ and B₀. In the encoder, only one input is high or “1” and the other inputs are low or “0”.

Fig. 4‑25. 4-to-2 Encoder

The encoder generates the binary code corresponding to the input value. For example, if the input D₀ is high and the other inputs are low, the encoder generates the binary code B₁ B₀ = 00. If the input D₃ is high and the other inputs are low, the encoder generates the binary code B₁ B₀ = 11. The following table describe the operation of the 4-to-2 encoder.

Table 4‑6. Truth Table of 4-to-2 Encoder

The following figure shows a 8-to-3 encoder, where there are eight inputs, i.e. D₇ through D₀, and three outputs (binary code), i.e. B₂, B₁ and B₀. This encoder operates in a similar manner. Only one input is high or “1” and the other inputs are low or “0”.

Fig. 4‑26. 8-to-3 Encoder

The encoder generates the binary code corresponding to the input value. For example, if the input D₇ is high and the other inputs are low, the encoder generates the binary code B₂ B₁ B₀ = 111. If the input D₄ is high and the other inputs are low, the encoder generates the binary code B₂ B₁ B₀ = 100.

Table 4‑7. Truth Table of 8-to-3 Encoder

Binary Decoder

The binary decoder translates the binary value into the decimal value. Fig. 4-27 shows a block diagram of 2-bit binary decoder.

Fig. 4‑27. Block Diagram of 2-bit Binary Decoder

The 2-bit binary decoder has the two inputs, A and B, and four output, Y₀, Y₁, Y₂, and Y₃. The following table shows the truth table of the decoder.

Table 4‑8. Truth Table of 2-bit Binary Decoder

The following figure shows 3-to-8 binary decoder, where there are three inputs (binary code), i.e. A₂, A₁, and A₀, and eight outputs, i.e. Y₇ through Y₀.

Fig. 4‑28. 3-to-8 Decoder

The decoder converts the binary code into a decimal value (outputs), where only one output is high or “1” and the other outputs are low or “0”. The decoder generates a decimal value corresponding to the input binary code. For example, if the binary inputs are A₂ A₁ A₀ = 110, only the output Y₆ is HIGH, and the other outputs are all LOW. The following table describes the operation of the decoder.

Table 4‑9. Truth Table of 3-to-8 Decoder

Priority Circuit

This chapter introduced the priority circuit in Section 4.1. This section describes the priority circuit in detail. Fig. 4-6 shows the truth table of the priority circuit. We will show how to design the circuit hardware from the truth table using K-map.

The following figure shows the block of the priority circuit. If the inputs A₃ A₂ A₁ A₀ are “0000”, the circuit produces the outputs Y₃ Y₂ Y₁ Y₀ = 0000.

Fig. 4‑29. Priority Circuit with inputs: A₃ A₂ A₁ A₀ = 0000

In the following figure, the inputs A₃ A₂ A₁ A₀ are “0001”. Only A₀ asserts TRUE and the other input values are all FALSE. The circuit produces the outputs Y₃ Y₂ Y₁ Y₀ = 0001.

Fig. 4‑30. Priority Circuit with inputs: A₃ A₂ A₁ A₀ = 0001

In the following figure, the inputs A₃ A₂ A₁ A₀ are “001X”, where the term ‘X’ represents ‘don’t care’. The higher priority inputs A₃ and A₂ didn’t assert. Since only A₁ asserts TRUE, the lower priority input A₀ doesn’t matter whether it is TRUE or FALSE. Only the output Y₁ is TRUE and the other outputs are all FALSE.

Fig. 4‑31. Priority Circuit with inputs: A₃ A₂ A₁ A₀ = 001X

In the following figure, the inputs A₃ A₂ A₁ A₀ are “01XX”, where the term ‘X’ represents ‘don’t care’. The higher priority input A₃ didn’t assert. Since the next higher priority A₂ asserts TRUE, the lower priority inputs A₁ and A₀ don’t matter whether they are TRUE or FALSE. Only the output Y₂ is TRUE and the other outputs are all FALSE.

Fig. 4‑32. Priority Circuit with inputs: A₃ A₂ A₁ A₀ = 01XX

In the following figure, the inputs A₃ A₂ A₁ A₀ are “1XXX”, where the term ‘X’ represents ‘don’t care’. The highest priority input A₃ asserts TRUE. The lower priority inputs A₂, A₁ and A₀ don’t matter whether they are TRUE or FALSE. Only the output Y₃ is TRUE and the other outputs are all FALSE.

Fig. 4‑33. Priority Circuit with inputs: A₃ A₂ A₁ A₀ = 1XXX

We can summarize the operation of the priority circuit in the following table:

Table 4‑10. Summary of Priority Circuit Operation

where the symbol ‘X’ represents ‘don’t care”.

Let’s design the hardware from the truth table. The following figures show how to simplify the output Y₃ with the input variables, A₃, A₂, A₁, and A₀. With the red circuit, we can simplify the Boolean equation and draw the corresponding equation: .

Fig. 4‑34. Priority Circuit Design of Y₃ using K-map

The following figures show how to simplify the output Y₂ with the input variables, A₃, A₂, A₁, and A₀. With the red circuit, we can simplify the Boolean equation and draw the corresponding equation: .

Fig. 4‑35. Priority Circuit Design of Y₂ using K-map

The following figures show how to simplify the output Y₁ with the input variables, A₃, A₂, A₁, and A₀. With the red circuit, we can simplify the Boolean equation and draw the corresponding equation: .

Fig. 4‑36. Priority Circuit Design of Y₁ using K-map

The following figures show how to simplify the output Y₀ with the input variables, A₃, A₂, A₁, and A₀. With the red circuit, we can simplify the Boolean equation and draw the corresponding equation: .

Y₀

A₃A₂

A₁A₀

Fig. 4‑37. Priority Circuit Design of Y₀ using K-map

With the above figures, from Fig. 4-34 to Fig. 4-37, we can design the priority circuit as follows:

• Input A₃ directly connected to Y₃
• AND₁ gate produces the output Y₂ with two inputs, A₃ complement and A₂
• AND₂ gate produces the output Y₁ with three inputs, i.e. A₃ complement, A₂ complement, and A₁
• AND₃ gate produces the output Y₀ with four inputs, i.e. A₃ complement, A₂ complement, A₁ complement and A₀

The following figure shows the priority circuit with logic gates.

Fig. 4‑38. Priority Circuit with Logic Gates

where the bubble symbol at the input side of AND gates represents a complement.