Microsoft Word - Digital Logic Design v_4_6a

2.8. Methods of Function Minimization (reducing the number of literals in an expression)

It is important to minimize the function prior to implementation. Minimization of literals and operators
reduces the number of gates needed to implement the function therefore reducing the cost of
implementation. In this section Systematic Algebraic Reduction (SAR) minimization techniques will be
discussed. The SAR technique is effective for automation but tedious for human use. On the other hand,
Karnaugh Map (K-Map) that will be discussed later is a visual tool that is more effect for human use to
minimize functions.
.
.
 Systematic Algebraic Reduction (SAR) technique uses algebraic theorems and postulates. Although
you could start applying various algorithms until you find one that reduces the function, our goal is to
introduce systematic techniques that can be described in a step-by-step process (algorithm) and
consistently applied.

 Usage

Most Computer Aided Design (CAD) packages use the SAR technique for function minimization.

Although SAR is not guaranteed to reduce the function to a minimum, it is the most effective

algorithm available.

 Process

Here is the step-by-step algorithm for a Systematic Algebraic Reduction(SAR):

(1) Expand the function into its Standard sum of products (SOP) form

(Include all variables; writing variables in order in all terms makes it easier to recognize

patterns.)

(2) Compare all pairs of products for:

(a) Adjacency Theorem: “exp exp.1 2 +exp exp.1 2 =exp 1 ”

and

(b) Idempotency Theorem: “exp+exp =exp ”

**Note: The reduction process may have to be repeated a number of times.

(3) Once you have done all reductions possible in step 2, See if the Consensus Theorem

applies

exp exp.1 2 +exp exp.1 3 +exp exp.2 3 =exp exp.1 2 +exp exp.1 3

 Example: Using SAR, minimize the function F= (A+B+C).( A+C).(B+C)

Solution:

1) Use the truth table to derive the min-terms

A B C F

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 0

1 1 1 1

2) Write the function in compact Min-term form