Jump to content

Boolean minimization

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 24.218.108.33 (talk) at 14:51, 29 April 2009. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Introduction

Digital electronic equipment has deeply penetrated everyone's life. Electronic devices are embedded in all kinds of appliances from coffee makers to automobiles. All such devices are composed of numerous blocks of digital circuits, the combination of which performs the required task. As a result, the efficient implementation of logic functions in the form of logical gate circuits has become an economical key factor in the success of many contemporary industrial products.

Designing digital logic circuits

All digital systems are composed of two elementary functions: memory elements for storing information and combinational logic gate circuits for translating that information. State machines, like counters, are nothing but a combination of memory elements and combinational gate circuits. Since memory elements are standard components to be selected out of a limited set, in essence designing digital functions comes to implementing the combinational gate circuits for the basic building blocks as well as interconnecting all these building blocks.

In general the implementation of gate circuits is referred to as Logic Synthesis, which basically can be carried out by hand, but usually some formal method by computer is applied. In this article the design methods for combinational gate circuits are briefly summarized.

The starting point for the design of a logic gate circuit is its desired functionality, having derived from the analysis of the system as a whole, the gate circuit is to make part of. The description can be stated in some algorithmic form or by logic equations, but may be summarized in the form of a table as well. The below example shows a part of such a table for a 7-segment driver that translates the binary code for the values of a decimal digit into the signals that cause the respective segments of the display to light up.

  Digit  Code      Segments  A-G
    0    0000      1 1 1 1 1 1 0          -A-
    1    0001      0 1 1 0 0 0 0         F   B
    2    0010      1 1 0 1 1 0 1         |-G-|
    3    0011      1 1 1 1 0 0 1         E   C
    .    ....      . . . . . . .          -D-

The implementation process starts with a logic minimization phase, to be described below, in order to simplify the function table by combining the separate terms into larger ones containing fewer variables.

Next the minimized result may be split up in smaller parts by a factorization procedure and is eventually mapped onto the available basic logic cells of the target technology. This operation is commonly referred to as Logic Optimization.[1]

Classical minimization methods

Minimizing Boolean functions by hand using the classical Karnaugh maps is a laborious, tedious and error prone process. It isn't suited for more than 6 input variables and practical only for up to 4 variables, while product term sharing for multiple output functions is even harder to carry out.[2] Moreover, this method doesn't lend itself to be automated in the form of a computer program. However, since modern logic functions are generally not constrained to such a small number of variables, while the cost as well as the risk of making errors is prohibitive for manual implementation of logic functions, the use of computers became indispensable.

The first alternative method to become popular was the tabular method developed by Quine and McCluskey. Starting with the truth table for a set of logic functions, by combining the minterms for which the functions are active—the ON-cover—or for which the function value is irrelevant—the Don't-Care-cover or DC-cover—a set of prime implicants is composed. Finally a systematic procedure is followed to find the smallest set of prime implicants the output functions can be realised with.[3][4]

Although this Quine-McCluskey algorithm is very well suited to be implemented in a computer program, the result is still far from efficient in terms of processing time and memory usage. Adding a variable to the function will roughly double both of them, because the truth table length increases exponentially with the number of variables. A similar problem occurs when increasing the number of output functions of a combinational function block. As a result the Quine-McCluskey method is practical only for functions with a limited number of input variables and output functions.

Algorithms

  1. ^ De Micheli, Giovanni (1994), Synthesis and Optimization of Digital Circuits, McGraw-Hill Science Engineering, ISBN 0-07-016333-2
  2. ^ Lewin, Douglas (1985), Design of Logic Systems, Van Nostrand (UK), ISBN 0-442-30606-7
  3. ^ Katz, Randy H.; Borriello, Gaetano (1994), Contemporary Logic Design, The Benjamin/Cummings Publishing Company, ISBN 0-8053-2703-7
  4. ^ Lala, Parag K. (1996), Practical Digital Logic Design and Testing, Prentice Hall, ISBN 0-02-367171-8