Combinational Logic Word Problems

In this section, we will look at a few case studies that illustrate the "art" of mapping circuit specifications into gate-level realizations. Sometimes the problems may seem more like puzzles than anything having to do with digital design. The art is in understanding the problem and formulating the solution; the implementation might well be very simple.

4.3.1 Design Procedure

In tackling word problems, we recommend following a standard "procedure" for extracting the key points and constraints of the problem and formulating its solution. Our method consists of the following steps. First, try to understand the problem. Second, reformulate it in terms of a standard digital design representation. Third, decide on how you will implement your design. And last, follow an implementation algorithm suitable for your chosen implementation approach. It is not possible to give a precise algorithm for some of these steps; you will need to rely on practice and experience. Let's look at each of them in more detail.

Step 1: Understand the Problem The very first thing you must do is to understand the problem. There is no single approach for understanding a complex problem statement. Word problems are inherently difficult because they are presented in imprecise, wordy, ambiguous, and confusing statements. In the real world of design, the function being designed may not be particularly well understood or clearly defined. The place to start is with the input/output behavior of the object being designed. Can you identify the inputs, outputs, and control signals? How do the control signals operate on the inputs to generate the outputs? If the problem gives example output behaviors based on certain input streams, make sure you understand how those outputs are derived from the inputs. Sometimes it is helpful to draw a diagram, relating inputs, outputs, and control, to obtain a better understanding of the problem. Or perhaps the diagram can help you understand the different configurations of the inputs you are supposed to recognize.

For example, suppose you are asked to design a logic circuit to control a hall light, with light switches at either end of the hall. It should be possible to turn the light on from either end of the hall, then walk through the hall and turn it off at the other end.

You start by identifying the inputs and outputs. The inputs are the two light switches and the output is the light. Let's call the switches A and B. Sometimes you just need to make reasonable starting assumptions. We will assume that when the light switch is in the down position the input is 0, and when the switch is up the input is 1. The light is on when the logic function is 1. Otherwise it is off.

Let's assume that the system begins with both light switches in the down position. Clearly, the light should be off when both switches are down. When one switch goes up, the light should go on. At the other end of the hall, placing the second switch in the up position should turn the light off.

So if both switches are up, the light is off. What happens when you walk back through the hall? Putting one switch down, the light should go on. Putting the far switch down should turn the light off.

Step 2: Formulate in a Standard Representation Once we have a feeling for what the combinational logic circuit is supposed to do, we must describe it more formally. Digital design representations are the precise ways of representing a digital system. For combinational logic word problems the appropriate representations are almost always Boolean equations or truth tables. These representations capture the relationships among inputs, control, and output as algebraic statements or as tabulations of input/output behavior. The key challenge is to extract these relationships from the word statement of the problem.

For the hall light example, simply tabulate the input conditions. When both switches are in the same position, the light is off. When they are in different positions, the light is on.

Step 3: Choose an Implementation A Boolean equation or a truth table is an abstract representation of the digital system. The next step is to map this into something more concrete, like logic gates. Before you can implement the system, however, you must make a critical design decision: you must choose a technology for implementation. The kinds of choices available are two-level combinational networks of discrete gates or PALs/PLAs, multilevel networks, memories such as ROMs, transmission gate networks, or use of "complex gate logic" like AND-OR-Invert gates. The detailed choice is usually based on economics or performance, but it may be constrained by the kind of technology available to you. For example, if you only have TTL components, transmission gate networks are pretty much eliminated.

The hall light circuit is simple enough to implement with a small number of discrete gates.

Step 4: Apply the Design Procedure The last step is perhaps the most mechanical. You have formulated the solution in terms of Boolean equations or truth tables, you have chosen an implementation approach, and now you must follow the algorithm to map your digital representation into an actual implementation. For two-level networks, you will apply the techniques of Chapter 2 to derive a circuit with the fewest number of product terms. The approach is the same whether the implementation target is discrete gates or programmable logic. For a ROM-based design, only the truth table is needed; there is no need to minimize your logic description first. If you choose a multilevel implementation approach, your best bet is to use computer-aided design tools to factor the Boolean equations into their best form to minimize gate and literal counts.

The hall light circuit can be implemented with a single XOR gate.

Introduction to the Case Studies In the following sections, we will tackle four different word problems/case studies, applying the four-step approach we have just outlined. The first problem is a simple process control application. You must determine the particular Boolean conditions, as indicated by the condition of input light sensors, which characterize the condition of rods on an assembly line. When the right rod condition is detected, the logic must generate a signal to move a mechanical arm. The second case study is a decoder application: the combinational logic circuit must map encoded input signals to specified output signals for the desired effects. In this case, the circuit must illuminate certain segments of a seven-segment light display based on the inputs. The third problem describes a logical function unit that implements several different logic functions of its inputs. This kind of system could be of use in a simple microprocessor. The outputs are defined as combinational logic functions of the inputs and control signals. The last problem presents a digital subsystem that takes an 8-bit input and shifts it any number of positions. Follow along and try the design problems on your own. Then compare your solution with the ones presented. Yours may well be better than the solutions we show.

A Simple Process Line Control Problem

Rods of varying length (± 10%) travel one at a time in the direction of their longest axis on a conveyor belt. A mechanical arm pushes rods that are within specification (± 5%) off the belt to one side. A second arm pushes rods that are too long to the other side. Rods that are too short remain on the belt. Use three light barriers (light source + photocell) as sensors, and design the combinational circuits that activate the two arms.

Step 1: Understand the problem.

In a problem like this, it is important to make sure that you understand the problem specification. Suppose the perfect length is 100 inches. All rods will be within 10% of this specification, or from 90 to 110 inches in length. "Too long" rods are longer than the specified length by more than 5%-more than 105 inches but less than or equal to 110 inches. These rods are supposed to be pushed to one side of the conveyor belt. "Too short" rods are more than 5% shorter than the desired length-greater than or equal to 90 inches but less than 95 inches. These are destined to remain on the belt. Rods in the range 95 to 105 inches are "within spec" and will be pushed to the other side by a second arm. A picture should make this more obvious. (See Figure 4.64.)

Next, let's identify the inputs and outputs. The only inputs we have are the readings from the three light sensors. The outputs are the signals that actuate the two positioning arms. Since it is not explicitly stated in the problem, let's assume that the light barriers operate by reading out a 0 when the light beam is uninterrupted and a 1 when it is tripped by the passing rod. The inputs and outputs are fairly straightforward. The key design question becomes how to arrange the placement of the sensors so we can distinguish between the three different classes of rods.

We will call the light barriers A, B, and C and arrange them so that the sensor C is the first to be tripped by the passing rod, then B, and finally A. Let's make one critical assumption: we will fix the placement of barrier A and arrange barriers B and C so as to be able to decide on the rod length when the rod breaks the light barrier at A. A second assumption is that the rods are adequately spaced on the conveyor belt, at least a maximum rod length, so that it is never possible to interpret two rods accidentally as a single rod.

By redrawing Figure 4.64 slightly, this time incorporating the light barriers, it becomes a little clearer where to place B and C to distinguish the rod types. See Figure 4.65.

We will use barrier B to identify rods that are too short and barrier C to detect those that are too long. B should be placed just far enough from A so that a too-short rod will trip A but not B. Thus, A and B should be separated by the specified length minus 5%. For our hypothetical specification of 100 inches, this means that A and B should be placed 95 inches apart.

Now we must place barrier C to detect the rods that are too long. Let's place it a distance that is the specification plus 5% from A (105 inches in our example). The barriers now distinguish between the three cases. If A is tripped, but not B or C, then the rod is clearly too short (ABC = 100). If A, B, and C are tripped simultaneously, the rod is too long (ABC = 111). This condition activates the arm to move the rod to one side of the belt. The remaining case is handled by A and B being tripped but not C (ABC = 110). Then the rod is within the desired specification. This is the condition to move the rod to the other side of the belt.

This represents only three of the eight possible barrier configurations. Because of our first assumption, that we will make our decision as soon as barrier A is triggered, the rod must still be in transit if the barrier configuration is ABC = 0XX. Since we also assume that the rods are separated by a maximum rod length, the remaining input condition, ABC = 101, can never occur.

Step 2: Formulate the problem in terms of a truth table or other suitable design representation.

At this point, most of the hard work has been done. A summary truth table, derived from the discussion above, appears in Figure 4.66.

Step 3: Choose implementation technology.

The actual logic is really quite simple, so we can implement it as straightforward gate logic.

Step 4: Follow implementation procedure. The "too long" condition is represented by the function F = ABC. The "within spec" condition is represented by the function G = . These can be implemented via two 3-input AND gates.

BCD-to-Seven-Segment Display Controller

You are to design a combinational circuit that maps a 4-bit BCD digit to the signals that control a seven-segment display. The display element contains seven light-emitting diodes (LEDs). When the appropriate LED control line is asserted, the associated LED segment lights. We assume that the LED driver inputs are active high (most of the actual LED driver components are really active low). Otherwise, the LED segment is off. The seven segments are controlled independently; there is no limit to the number of segments that could be illuminated at the same time. Figure 4.67 shows the seven-segment display and its configurations displaying each of the 10 possible BCD digits.

Step 1: Understand the problem.

Begin by asking yourself what the circuit is supposed to do. What are the inputs and outputs? There are four input signals, representing the 4-bit BCD digit. There should be seven outputs, one for each of the LED segments that must be controlled. At this point, it might be helpful to draw a block diagram, with the inputs and outputs clearly identified. A high-level block diagram is given in Figure 4.68.

In more complex systems, you might apply a divide-and-conquer approach to break the high-level blocks into smaller, more primitive blocks that are easier to understand. In this case, the decomposition is reasonably straightforward: each LED segment control line is a Boolean function of the four inputs.

Step 2: Formulate the problem in terms of a truth table or other suitable design representation.

For a problem like this one, it is best to tabulate the input values with the desired outputs. For example, the BCD representation for the digit 0 should cause the LED segments 0, 1, 2, 3, 4, and 5 to be illuminated. Thus, associated with the input combination 0000 we would assert the control signals C0 through C5, leaving C6 unasserted. For the input combination 0001, segments 1 and 2 are turned on, while segments 0 and 3 through 6 are left off. In the table entry for 0001, C1 and C2 are asserted, while the remaining outputs are left unasserted. In this fashion we can fill in the whole truth table. Since BCD digits consist of the bit patterns 0000 through 1001, the outputs associated with the remaining input patterns can be left as don't cares. This should help reduce the complexity of our actual implementation. The complete truth table is shown in Figure 4.2.

Step 3: Implementation target

Now we must decide on our implementation technology. If we choose to implement the system with a read-only memory, we can stop now. All we need to do is to place the truth table of Figure 4.2 into a 16-word by 7-bit ROM (such a ROM is not likely to exist, but you should be able to find a 2n by 8-bit ROM).

Suppose your boss tells you that a programmable ROM is too expensive to be used in this subsystem. You may have noticed the 74LS48 component in the TTL catalog. This implements a BCD-to-seven-segment display controller in a single MSI package. In fact, the catalog contains several alternative single-package implementations for this function. Unfortunately, your boss doesn't like the way these decoders display the digit "6," so you will have to implement your own decoder from scratch. This function, with its seven outputs, is complex enough that a discrete gate implementation will probably require quite a few gates and packages to realize. Therefore, let's make the decision that the target is a PAL or PLA structure, and our goal is to realize the function in a single package. Obviously, we will need a minimized two-level network.

Step 4: Implementation procedure

Since the target is a two-level network, we can use either the K-map techniques of Chapter 2 or a CAD tool like espresso directly. Since this particular problem involves only four-variable maps, let's look at both approaches. It will turn out that even in a relatively simple problem such as this, espresso still does much better than our pencil-and-paper techniques!

K-Map Method The K-map method requires seven 4-variable K-maps, one for each truth table column. By this point, it should be second nature for you to fill in the K-map from the truth table. The maps are shown in Figure 4.70(a) through (g). We've gone ahead and boxed the prime implicants, taking advantage of don't cares wherever possible. Read out from Figure 4.70, the equations for the LED segment control outputs become:
We would need a four-input, seven-output PAL with at least four product terms per output to implement this function. A P16H8 PAL, for example, has sufficient resources to implement it: ten external inputs plus six feedback inputs (more on this in Chapter 7), eight outputs, and seven product terms per output. The simpler P14H8 PAL cannot do the job. It has 14 inputs and eight outputs, but only two of the outputs are computed as the OR of four product terms while the remaining six outputs have only two product terms each.

See Figures 4.72 and 4.73 for the PAL programming maps.

Suppose the target implementation is for a PLA structure rather than a PAL. The limiting factor in a PLA is the number of unique product terms to implement the outputs. These correspond to the number of horizontal "wires" in the PLA circuit array. We have fifteen unique product terms in the above set of equations. A typical PLA component can handle sixteen inputs, eight outputs, and forty-eight product terms (for example, see Figure 4.70 for the F100 PLA programming map).

Two-Level Logic Optimization Method The espresso input file is given in Figure 4.74. The espresso output is shown in Figure 4.75. This maps onto the following set of Boolean equations:

Remarkably, espresso appears to have come up with more complex expressions for the outputs than the K-map method. However, a closer inspection reveals that the number of unique product terms has been reduced from 15 to only 9. Although the individual expressions now have more product terms, there is greater sharing of terms among the outputs. Remember that the size of the PLA is determined primarily by the number of unique product terms, so the better design is the one with fewer terms.

Term sharing provides no assistance for a PAL-based implementation, since the topology of a PAL makes it impossible to share terms among the different output functions. (Note that this statement is not true for the more complex programmable logic structures we will cover in Chapter 7.) In fact, by increasing the number of terms per output, the espresso method may force us to use a more complicated PAL than is really needed (it is possible to ask espresso to perform its optimization on the basis of an individual output, and this approach should be followed if the implementation technology is going to be a PAL).

Figure 4.76 shows the programming map for a PLA implementation.

Multilevel Optimization Method How does this compare with a multilevel solution, such as one that could be produced using misII? Multilevel logic is not well suited to PAL or PLA implementation, so let's have a look at discrete gate implementations, to compare misII and espresso. First, let's examine the complexity of the solution derived by espresso in a little more detail. The number of literals is 63. The number of gates is 7 (an OR gate for each output) plus 8 (an AND gate for each unique product term except the simple term A) plus 3 (an inverter for the inputs B, C, D), for a total of 18 gates. Each output is at the second level of the network, experiencing two to three gate delays.

Running a standard misII script on the espresso input file yields the following set of equations (note that hand optimization may do better):

X and Y are intermediate terms inserted into the logic network by misII. This yields a total of 52 literals and 33 gates (one for each of outputs C0 through C6, X and Y, plus seven inverters including , , and , plus 17 other product terms). In terms of delay, the slowest output is C1, since it is a function of C6, which is a function of C5, which in turn is a function of C4. C4 already experiences three gate delays since it is a function of Y. Thus C1 experiences 9 or 10 gate delays! Although misII has done an admirable job of reducing the number of wires (as measured by the number of literals), it has not done so well on reducing the gate count, and its implementation will be quite a bit slower than the two-level realization derived by espresso. The primary reason is that this version of misII is not yet sophisticated enough to make use of don't-care conditions. The important lesson here is to understand the limitations of the computer-aided design tools you are using.

A Logic Function Unit

You are to design a logic network that has two data inputs, A and B, and three control inputs, C0, C1, and C2. The network should implement the logical function F specified in Figure 4.77.
Components of this type find wide application in microprocessor data paths, for computing a variety of bitwise logic functions of two operands.

Step 1: Understand the problem. The problem specification mentions three control inputs (C0, C1, C2), two data inputs (A, B), and a single output function (F). Thus, F is a combinational logic function of these five variables.

Step 2: Formulate the problem in terms of truth table or other suitable design representation. The natural thing to do next is to create a five-variable truth table, in preparation for solving a five-variable K-map. In terms of the truth table representation, there really is no distinction between control and data inputs. We begin by listing the 32 different combinations of five variables. Next, let's partition the truth table into eight groups of four rows each. Each group represents a unique setting of the three control inputs (000 through 111), and each row within the group represents a unique configuration of the data inputs A and B (00 through 11). Since the first truth table group (C0C1C2 = 000) represents the constant function 1, we fill in all four rows with a 1. The second group (C0C1C2 = 001) is the function OR. We fill in the first row (AB = 00) with a 0 and the remaining three rows (AB = 01, 10, 11) with a 1. Continuing in this fashion, we can complete the rest of the table. This is shown in Figure 4.78.

Step 3: Choose an implementation technology.

The basic choice is whether to implement the function with a gate-oriented approach or with memories. Note that using discrete (or even programmable) gates is not the only "gate-oriented" approach. An im-ple-mentation based on a multiplexer might be worth considering. See the block diagram in Figure 4.79.

We could have come up with this implementation without even deriving the truth table of step 2.

To a large extent, the implementation decision depends on two factors: design time versus component cost. ROM-based designs usually require less time for design and implementation. For one thing, a ROM-based design starts with the same truth table as a discrete gate design, plus it has the advantage that we need not minimize the function. However, a ROM package is about five times as expensive as a discrete gate package (of course, this depends on the number of bits in the ROM). On the positive side, the function can be implemented in a single ROM but it will take several packages to implement it using discrete gates.

For example, the multiplexer-based design of Figure 4.79 requires four TTL packages: four 2-input NAND, four 2-input NOR, two 2-input XOR, and an 8:1 multiplexer (inverters can be formed from leftover NAND, NOR, or XOR gates). If the cost differential is a factor of 5, the multiplexer-based design is still less expensive than ROM. Yet the multiplexer-based design takes up more circuit area than the ROM-based one, with more opportunities for wiring errors and component failures. If cost is the overriding criterion, we will choose packaged logic. But which requires fewer packages, the discrete gate design or the multiplexer design? The minimized gate-level design cannot be evaluated without performing the K-map minimization, which we do next.

Step 4: Follow the implementation procedure.

To continue the analysis, we will minimize the function's K-map. This is shown in Figure 4.79, and the function for F turns out to be a rather simple equation:

In packaged logic like TTL, this requires five gates (four 3-input, one 4-input), plus five inverters. This can be implemented in three TTL packages (one package of three 3-input gates, one package of two 4-input gates, and one package of six inverters), so there is a slight advantage for the gate approach.

Note that the function can be simplified further, assuming that XOR gates are available: We still need five inverters and five more gates: three 3-input, one 2-input, and one 2-input XOR. This time we need four packages: one package of three 3-input gates, one package of four 2-input gates, one package of two 2-input XOR gates, and one package of six inverters. This simplification actually increases the implementation costs unless the leftover gates can be used for other purposes.

If the criterion is circuit area rather than cost, the clear winner is the ROM-based implementation, since it requires a single package. In a gate array design style, the 10-gate version probably has the area advantage. This is because it would be difficult to implement a 32-word ROM in an equivalent area using the primitive gate structures available in a typical gate array.

An Eight-Input Barrel Shifter

A barrel shifter is a digital subsystem that can shift any number of bit positions at once. In a single pass through the shifter, the input can rotate from 0 to 7 positions. Barrel shifters are useful for implementing bit extraction operations supported in many computer instruction sets.

To be more precise, you are to design a digital subsystem that implements the following function. The subsystem has eight data inputs, D7, D6, , D0, eight data outputs, O7, O6, , O0, and three control inputs, S2, S1, S0. The control inputs specify the number of positions to shift the input to the left. Inputs that "fall off the end" are rotated around to the low-order bits of the output.

For example, when S2 = S1 = S0 = 0, the inputs are simply gated straight through to the outputs: O7 = D7, O6 = D6, , O1 = D1, O0 = D0. When S2 = S1 = 0, S0 = 1, the input bits are shifted one place toward the left: O7 = D6, O6 = D5, , O1 = D0, O0 = D7. Note that D7 is rotated around to the 0th output position. When S2 = S1 = S0 = 1, the input is shifted seven positions to the left, with the high-order bits wrapping around to the low-order output positions: O7 = D0, O6 = D7, , O1 = D2, O0 = D1. This is the same as shifting one position to the right, with the inputs wrapping from the low-order to the high-order positions.

Step 1: Understand the problem.

The subsystem consists of eight output functions, each depending on 11 inputs: S2, S1, S0, D7, D6, , D0. Probably the easiest way to understand the subsystem's behavior is to tabulate the values of the outputs as a function of the control settings. This is shown in Figure 4.81.

The inputs shift to the left by an increasing number of positions as the binary index of the control inputs increases. The inputs wrap around from the left to the right of the table.

Step 2: Formulate the problem in terms of a truth table or other suitable design representation.

At this point, it is best to describe each of the outputs in terms of the 11 inputs:

Step 3: Choose implementation technology.

Step 4: Follow implementation procedure.

For this case study, we will combine the discussion of implementation choice and procedures for yielding the implementation. The basic implementation choices are discrete gates, MSI components, programmable logic, or switching networks. Let's start with a discrete gate implementation. A close examination of the Boolean equations should tell us that there is little chance of simplifying the functions. All of the combinations of the Si inputs are needed for each function, and each Dj appears in exactly one product term. There is just no way to exploit the uniting theorem. This means that a discrete gate implementation will require eight 4-input gates and one 8-input gate per function, for a total gate count of sixty-four 4-input gates and eight 8-input gates. This requires 40 packages: 32 for the 4-input gates and 8 for the 8-input gates. An approach based on discrete gates does not look too promising.

One alternative is to use MSI components such as multiplexers or decoders. It is not too hard to see that each output can be implemented by an 8:1 multiplexer. Simply use the control inputs to select one of the eight data inputs. All we have to do is to wire up the data inputs as specified by the table in Figure 4.81. This implementation requires only eight packages, a considerable savings over the discrete gate approach.

We can implement the subsystem with a single package if we use either a ROM or a PAL/PLA with sufficient programmable resources. Since the functions have 11 inputs, the ROM requires 2048 (211) by 8-bit words. To use a PAL, we need a component with 11 inputs, 8 outputs, and 8 product terms per OR gate output. A quick look at the output functions should convince you that they share no product terms. So there is no particular advantage to using a PLA.

The final implementation alternative is to develop some form of switching network. This should be a reasonable approach, since the shifter is a natural application of steering logic. Depending on the control signal settings, the inputs will be steered to the appropriate outputs.

Figure 4.83 shows a switching structure constructed from orthogonal sets of wires connected by nMOS transistors. The "cross-points" are implemented as shown by the cutaway at the right of the figure. The structure has the ability to connect any input to any output depending on which transistor gates are turned on. It is often called a crosspoint switch.

For example, if the diagonal crosspoints are enabled by the signal S000, then Di is connected to Oi. To implement the barrel shifter behavior, we need a strategy for distributing the right control signals to the appropriate switches in the array.

Within the crosspoint switch, we will use the fully decoded signals S000 through S111 derived from the eight possible configurations of the control inputs S2, S1, and S0. It's not too hard to see how to implement the remaining control connections. The diagonal switches implement the barrel shifter function when S2 = S1 = S0 = 0. The switches immediately below the diagonal connect D6 to O7, D5 to O6, , D0 to O1. This is almost the correct functionality for S2 = S1 = 0, S0 = 1. All we need in addition is to be able to connect D7 to O0. This is made possible by the switch in the upper right corner of the array, as shown in the figure. The set of switches is controlled by the decoded signal S001.

Figure 4.83 shows the crosspoint connection scheme with the complete set of control signals distributed through the structure. To shift 0 bits, the signal S000 controls the transistors along the main diagonal. S001, the signal to shift 1 bit, is split across two diagonals, one below the main diagonal and one above. We use this strategy for each of the remaining control signals. With each increase in shift distance, the next control signal is routed to the diagonal immediately below and to the left of those controlled by the previous signal. For example, the switches controlled by S010 are immediately below and to the left of the switches controlled by S001. Clearly, the switch implementation is most efficient. It requires only 64 transistors (plus a decoder), although the signal routing is fairly complex. If you cannot implement the subsystem directly at the level of transistor switches, the best alternative is to use a ROM or PAL to complete implementation in a single integrated circuit package.

Case Study Summary In this section, you have followed a four-step design procedure for mapping a word specification of a combinational logic cir-cuit into an actual implementation. First, you understand the problem specification by identifying inputs, outputs, and their relationships. A picture or diagram is often an indispensable aid to the process of understanding the problem. Second, you map your understanding of the problem onto a truth table or collection of Boolean equations. Without placing the design into one of these forms, you will be hard pressed to use the techniques learned in Chapter 2 and this chapter to derive an implementation. Third, you choose your implementation technology: discrete or programmable gates, memory-based designs, or perhaps alternative approaches based on multiplexers or other steering logic. The choice depends on many things: cost, availability of CAD tools or hardware programmers, circuit area. Memory-based designs require a truth table. The gate-oriented designs can start with either truth tables or Boolean equations, but they demand a minimization procedure to obtain an efficient implementation. With the availability of the appropriate computer-aided design tools, this should not represent too much of a problem, however. The fourth and final step is to apply the appropriate procedure to obtain the implementation: the K-map method or a CAD tool like espresso for a two-level logic network, Boolean factoring, or a tool like misII for a multilevel network.