Page 226 - Engineering Digital Design

CHAPTER 5

Function Minimization

by Using K-map XOR Patterns

and Reed-Muller

Transformation Forms

5.1 INTRODUCTION

In this chapter it will be shown how simple "pencil-and-paper" methods can be used to
extract gate-minimum multilevel logic designs not yet possible by any conventional method,
including the use of CAD techniques. The methods described here make possible multilevel
1C designs that occupy much less real estate than would be possible for an equivalent two-
level design, and often with little or no sacrifice in speed—an advantage for VLSI design.
There are a variety of approaches to logic function minimization, which can be divided
into two main categories: two-level and multilevel approaches. Chapter 4 was devoted
primarily to the two-level approach to minimization. Combining entered variable (EV) sub-
functions and the XOR patterns (described in the following section) in a K-map extraction
process is a special and powerful form of multilevel function minimization. Used with two-
level logic forms (AND and OR functions) this multilevel minimization approach leads
to XOR/SOP, EQV/POS, and hybrid forms that can represent a substantial reduction in
the hardware not possible otherwise. XOR/SOP and EQV/POS forms are those connecting
p-terms (product terms) with XOR operators or s-terms (sum-terms) with EQV operators,
respectively. Hybrid forms are those containing a mixture of these.
Another approach to multilevel logic minimization involves the use of Reed-Muller
transformation forms (discussed in Sections 5.5 through 5.12) that are partitioned (broken
up) into tractable parts with the assistance of entered variable Karnaugh maps (EV K-maps).
The process is called the contracted Reed-Muller transformation (CRMT) minimization
method and is expressly amenable to classroom (or pencil-and-paper) application. General
information covering the subjects associated with Reed-Muller minimized logic synthesis
are cited in Further Reading at the end of this chapter.
The word level (meaning level of a function) refers to the number of gate path delays
from input to output. In the past the XOR gate (or EQV gate) has been viewed as a two-level

197