40.

---

O purblind race of miserable men,
How many among us at this very hour
Do forge a lifelong trouble for ourselves,
By taking true for false, and false for true!

-Alfred, Lord Tennyson

Introduction

This chapter begins our detailed examination of the implementation of digital systems. We start with combinational logic design, the design and implementation of logic functions whose outputs depend solely on their inputs. The full adder introduced in Chapter 1 is just such a circuit.

We start with the representation of a function as a Boolean equation or a truth table. We will introduce a "canonical," or standard, representation of Boolean equations, called the sum of products two-level form. We can think of this as a unique way to represent a Boolean function, like a fingerprint. The form expresses the function as ANDed terms (first level of gates) that are then ORed together (second level of gates). An alternative canonical form, the product of sums form, has ORs at the first level and ANDs at the second level.

You can implement a Boolean function as logic gates in more than one way. It is highly desirable to find the simplest implementation-that is, the one with the smallest number of gates or wires. The process of reducing a Boolean function to its simplest two-level form is called Boolean minimization or reduction. We will introduce the detailed algorithm for minimization, as well as a simple method suitable for pencil and paper. We emphasize methods that will help you to visualize what is going on during reduction.

This chapter builds on the themes introduced in Chapter 1, within the framework of combinational logic design. Namely, we emphasize:

• Multiple representations, including Boolean equations, truth tables, waveforms, and interconnected gate descriptions of a Boolean function. In particular, we introduce the standard canonical representations that form the basis of the various simplification and implementation methods.
  
  
• Rapid prototyping technology involving the use of computer-based software for reducing Boolean equations and truth tables to their simplest two-level form.

Table of Contents

2.1. Logic Functions and Switches
2.2. Gate Logic
2.3. Two-Level Simplification
2.4. CAD Tools for Simplification
2.5. Practical Matters
Exercises

---

[Table of Contents] [Next] [Prev]

This file last updated on 06/23/96 at 19:47:39.
[e-mail];