A diagrammatic way to simplify functions by eliminating terms.

The columns are set as the most significant variables
The rows are set as the least significant variable

This creates a layout such that adjacent cell values only differ by one bit - This helps us identify common terms which can be taken out - "grey encoding"

The left-most and right-most columns are also considered to be adjacent - "torus"

Find columns/rows which share a 1 bit
- Can extract that 'same' variable

two-variable

three-variable

four-variable

Minimisation Strategies

Terminology

Implicant - A product term that indicates a set of valuations that give a function result of 1
Prime Implicant - Cannot be combined into another implicant that has fewer literals
- Expanded by square/rectangular powers of 2 to for prime implicants
Cover - collection of implicants that account for all valuations
- A cover consisting of only prime implicants will lead to a minimal cost implementation
Cost - #gates + #inputs
- Input inverters are not counted!
Essential prime implicant
- A prime implicant that is not included in any other prime implicant

POS minimisation

It may be cheaper to implement a POS (Product of Sums) implementation over a SOP (Sum of Products) implementation.

A: SOP (6) vs POS (9)

POS (15)

Incomplete Functions

Often functions are not completely specified, we can treat these input conditions as "don't care", allowing them to be used as 0s or 1s.

Multiple-output Synthesis

If there are several similar function circuits, we may be able to reuse components to serve several functions.

Input Refactoring

Gates have a (physical) limit to the number of inputs they can have. It may be necessary to refactor the layout by having several layers of lesser-input gates.

Decreases the complexity of each gate
Increases the number of gates
As gates are physical, there is an electrical delay
- Chaining gates adds more propagation delay

Karnaugh Maps

Contents