SIMPLIFICATION OF BOOLEAN FUNCTIONS

Algebraic simplification involves the application of the identities of Table 20.2 to reduce the Boolean expression to one with fewer elements. For example, consider again Equation (20.1). Some thought should convince the reader that an equivalent expression is

This expression can be implemented as shown in Figure 20.6. The simplification of Equation (20.1) was done essentially by observation. For more complex expressions, some more systematic approach is needed.

For purposes of simplification, the Karnaugh map is a convenient way of representing a Boolean function of a small number (up to four) of variables.

The map is an array of 2" squares, representing all possible combinations of values of n binary variables. Figure 20.7a shows the :nap of four squares for a function of two variables. It is essential for later purposes to list the combinations in the order 00, 01, Because the squares corresponding to the combinations are to be used for recording information, the combinations are customarily written above the squares. In the case of three variables, the representation is an arrangement of eight squares (Figure 20.7b), with the values for one of the variables to the left and for the other two variables above the squares. For four variables, 16 squares are needed, with the arrangement indicated in Figure 20.7c.

The map can be used to represent any Boolean function in the following way.

Each square corresponds to a unique product in the sum-of-products form, with a 1 value corresponding to the variable and a 0 value corresponding to the NOT of that

variable. Thus, the product AB corresponds to the fourth square in Figure 20.7a.

For each such product in the function, 1 is placed in the corresponding square.

Thus, for the two-variable example, the map corresponds to AB + WB. Given the truth table of a Boolean function, it is an easy matter to construct the map: for each combination of values of variables that produce a result of 1 in the truth table, fill in the corresponding square of the map with 1. Figure 20.7b shows the result for the truth table of Table 20.3. To convert from a Boolean expression to a map, it is first necessary to put the expression into what is referred to as canonical form:

each term in the expression must contain each variable. So, for example, if we have Equation (20.3), we must first expand it into the full form of Equation (20.1) and then convert this to a map.

The labeling used in Figure 20.7d emphasizes the relationship between variables and the rows and columns of the map. Here the two rows embraced by the symbol A are those in which the variable A has the value 1; the rows not embraced by the symbol A are those in which A is 0; similarly for B, C, and D.

Once the map of a function is created, we can often write a simple algebraic expression for it by noting the arrangement of the 1s on the map. The principle is

eliminating that variable. For_{_} example, in Figure 20.8a, the two adjacent squares correspond to the two terms ABCD and ABCD. Thus, the function expressed is

ABCD + ABCD = ABD

This process can be extended in several ways. First, the concept of adjacency can be extended to include wrapping around the edge of the map. Thus, the top square of a column is adjacent to the bottom square, and the leftmost square of a row is adjacent to the rightmost square. These conditions are illustrated in Figures 20.8b and c. Second, we can group not just 2 squares but 2'Z adjacent squares (that is, 2, 4, 8, etc.). The next three examples in Figure 20.8 show groupings of 4 squares. Note that in this case, two of the variables can be eliminated. The last three examples show groupings of 8 squares, which allow three variables to be eliminated.

We can summarize the rules for simplification as follows:

Among the marked squares (squares with a 1), find those that belong to a unique largest block of 1, 2, 4, or 8 and circle those blocks.

Select additional blocks of marked squares that are as large as possible and as few in number as possible, but include every marked square at least once. The results may not be unique in some cases. For example, if a marked square combines with exactly two other squares, and there is no fourth marked square to complete a larger group, then there is a choice to be made as two which of the two groupings to choose. When you are circling groups, you are allowed to use the same 1 value more than once.

Continue to draw loops around single marked squares, or pairs of adjacent marked squares, or groups of four, eight, and so on in such a way that every marked square belongs to at least one loop; then use as few of these blocks as possible to include all marked squares.

Figure 20.9x, based on Table 20.3, illustrates the simplification process. If any isolated 1s remain after the groupings, then each of these is circled as a group of 1s. Finally, before going from the map to a simplified Boolean expression, any group of 1s that is completely overlapped by other groups can be eliminated. This is shown in Figure 20.9b. In this case, the horizontal group is redundant and may be ignored in creating the Boolean expression.

One additional feature of Karnaugh maps needs to be mentioned. In some cases, certain combinations of values of variables never occur, and therefore the corresponding output never occurs. These are referred to as "don't care"

An example, presented in [HAYE98], illustrates the points we have been dis-cussing. We would like to develop the Boolean expressions for a circuit that adds 1 to a packed decimal digit. Recall from Section 9.2 that with packed decimal, each decimal digit is represented by a 4-bit code, in the obvious way. Thus, 0 = 0000, 1 = 0001, . . ., 8 = 1000, and 9 = 1001. The remaining 4-bit values, from 1010 to 1111, are not used. This code is also referred to as Binary Coded Decimal (BCD).

Table 20.4 shows the truth table for producing a 4-bit result that is one more

inputs. Figure 20.10 shows the resulting Karnaugh maps for each of the output vari-ables. The d squares are used to achieve the best possible groupings.

For more than four variables, the Karnaugh map method becomes increasingly cumbersome. With five variables, two 16 x 16 maps are needed, with one map considered to be on top of the other in three dimensions to achieve adjacency. Six variables require the use of four 16 x 16 tables in four dimensions! An alternative approach is a tabular technique, referred to as the Quine-McKluskey method. The method is suitable for programming on a computer to give an autoirmafic fool for producing minimized Boolem expregSiong.

The method is best explained by means of an example. Consider the following expression:

ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD

Let us assume that this expression was derived from a truth table. We would like to produce a minimal expression suitable for implementation with gates.

The first step is to con_ trLictt a table in which each row corresponds to one of the product terms of the expression. The terms are grouped according to the number of complemented variables. I =:at is; eve start with the term with no complements, if it exists, then all terms with one complement, and so on. Table 20.5 shows the list for our example expression, with horizontal fines used to indicate the grouping. For clarity,

each term is represented by a 1 for each uncomplemented variable and a 0 for each complemented variable. Thus, we group terms according to the number of is they contain.

The index column is simply the decimal equivalent and is useful in what follows.

The next step is to find all pairs of terms that differ in only one variable, that is, all pairs of terms that are the same except that one variable is 0 in one of the terms and 1 in the other. Because of the way in which we have grouped the terms, we can do this by starting with the first group and comparing each term of the first group with every term of the second group. Then compare each term of the second group with all of the terms of the third group, and so on. Whenever a match is found, place a check next to each term, combine the pair by eliminating the variable that differs in the two terms, and add that to. a new list.

Thus, for example, the terms ABCD and ABCD are combined to prodai&e ABC. This process continues until the entire original table has been examined. The result is a new table with the following entries:

A CD ABC ABD ~' BCD% ACD ABC BCD ABD_V

The new table is organized into groups, as indicated, in the same fashion as the first table. The second table is then processed in the same manner as the first. That is, terms that differ in only one variable are checked and a new term produced for a third table. In this example, the third table that is produced contains only one term: BD.

matrix, as illustrated in Table 20.6. Each row of the matrix corresponds to one of the terms that have not been eliminated (has no check) in any of the tables used so far. Each column corresponds to one of the terms in the original expression. An X is placed at each intersection of a row and a column such that the row element is "compatible" with the column element. That is, the variables present in the row element have the same value as the variables present in the column element. Next, circle each X

that is alone in a column. Then place a square around each X in any row in which there is a circled X. If every column now has either a squared or a circled X, then we are done, and those row elements whose Xs have been marked constitute the minimal expression. Thus, in our example, the final expression is

A B C ! + A C D + I B C + X U D

In cases in which some columns have neither a circle nor a square, additional processing is required. Essentially, we keep adding row elements until all columns are covered.

Let us summarize the twine-McKluskey method to try to justify intuitively why it works. The first phase of the operation is reasonably straightforward, The process eliminates unneeded variables in product terms. Thus, the expression ABC + ABC is equivalent to AB;

because

ABC + ABC = AB(C + C) = A

After the elimination of variables, we are left with an expression that is clearly

Another consideration in the implementation of Boolean functions concerns the types of gates used. It is sometimes desirable to implement a Boolean function solely with TeTAND gates or solely with NOR gates. Although this may not be the minimum-gate implementation, it has the advantage of regularity, which can simplify the manufacturing process. Consider again Equation (2(1.3):

Because the complement of the complement of a value is just the original value;

F=B(A+C)=(AB)+ Applying DeMorgan's theorem, F = (AB) ° (BC)

which has three NAND forms, as illustrated in Figure 2.11.

The multiplexer connects 1utinle inputs to a single output. At any time, one of the inputs is selected to to the output. A general block diagram representation is shown in Figure This represents a 4-to-1 multiplexer. There are four input lines, labeled D0. D'. D-, and D3. One of these lines is selected to provide the output signal F. To select one of the four possible inputs, a 2-bit selection code is needed, and this is impiti meneed as two select lines labeled S1 and S2.

An example 4-to--^- multiplexer is defined by the truth table in Table 20.7. This is a simplified form of a truth table. Instead of showing all possible combinations of input variables, it shows tt_e output as data from line D0, D1, D2, or D3. Figure 20.13 shows an implementation using AND, OR, and NOT gates. S1 and S2 are connected to the AND

equal the value of the selected input gate. Using this regular organization, it is easy to construct multiplexers of size 8-to-1,16-to-1, and so on.

Multiplexers are used in digital circuits to control signal and data routing. An example is the loading of the program counter (PC). The value to be loaded into the program counter may come from one of several different sources:

A binary counter, if the PC is to be incremented for the next instruction

• The instruction register, if a branch instruction using a direct address has just been executed

• The output of the AT U, if the branch instruction specifies the address using a displacement mode

These various inputs could be connected to the input lines of a mulltiplexer, with the PC

A decoder is a combinational circuit with a number of output lines, only one of which is asserted at any time, dependent on the pattern of input lines. In general, a

decoder has n inputs and 2" outputs. Figure 20.15 shows a decoder with three inputs and eight outputs.

Decoders find many uses in digital computers. One example is address decoding.

Suppose we wish to construct a 1K-byte memory using four 256 X 8-bit RAM chips. We want a single unified address space, which can be broken down as follows;

Address Chip

0000-00FF 0 0100-01FF 1 0200-02FF 2

Each chip requires 8 address lines, and these are supplied by the lower-order 8 bits of the address. The higher-order 2 bits of the 10-bit address are used to select one of the four RAM chips. For this purpose, a 2-to-4 decoder is used whose output enables one of the four chips, as shown in Figure 20.16.

line. Thus, the n inputs act as an address to select a particular output line, and the value on the data input line (0 or 1) is routed to that output line.

The configuration in Figure 20.17 can be viewed in another way. Change the label on the new line from Data Input to Enable. This allows for the control of the timing of the decoder. The decoded output appears only when the encoded input is present and the enable line has a value of 1.