Simplification

Purpose of simplification

Simpler expression leads to circuit with lesser logic gates, resulting in cheaper, low-power-requirement, and sometimes faster.

Techniques

Algebraic Simplification

Aims to minimise number of literals and number of terms.


Half-Adder

Half adder

A circuit that adds 2 single bits (X, Y) to produce a result of 2 bits (C, S).

Gray Code

• Unweighted (not an arithmetic code)
• Only a single bit change


K-Maps

Karnaugh-map

Abstract form of Venn diagram, organised as a matrix of squares, where each square represents a minterm, and two adjacent squares represent minterms that differ by exactly one literal.

Objective: Fewest possible product terms and literals. Advantage: Easy to use Disadvantage: Limited to 5 or 6 variables

Filling the K-map

Put a 1 to correspond to a minterm in the function, and otherwise.

Variable K-maps

Each cell in a variable K-map has adjacent neighbours. The K-map allows for this with a wrap-around.

As the number of variables increase, it is harder to draw out. For variable K-maps, where there will be an expected amount of squares, it can be organised as two variable K-maps, where, one K-map is on top of the other.

Using K-maps

The unifying theorem (complement law) allows us to use

• each valid grouping of adjacent cells to correspond to a simpler product term of

Assume that the green squares are the minterms with output 1 for function .

We currently have:

Since are adjacent, we can group them together, meaning we eliminate the variable from the product term.

To use effectively:

1. Group as many cells as possible

• The larger the group, the fewer the number of literals in product term.

2. Select as few groups as possible (the lesser the groups, the fewer the number of product terms)

Implicants

Implicants

A product term that could be used to cover minterms of a function

Prime implicants

A product term obtained by combining the maximum possible number of minterms from adjacent squares in the map.

Essential prime implicants

A prime implicant that includes at least one minterm that is not covered by any other prime implicant

Algorithm

1. Circle all prime-implicants
2. Identify and select all essential prime-implicants
3. Select a minimum subset

Simplified POS expression

The Simplified POS expression can be found using two methods:

• the K-map of the maxterms, and grouping 0s together
• complement of the SOP expression

Don’t Care conditions

Don't care conditions

In some cases, outputs are not specified or are invalid. These outputs can then be either 1 or 0. These conditions are denoted X or d.

This changes the eventual SOP/POS expressions.