Logic Simplification


	simplification

Logic Expression Simplification


	Often it is possible to simplify function expressions from, say, their minterm form.
	This may be done by using various identities, as we know. But more systematic methods will be shown.

Simplification Example

Notice Certain ÒAdjacenciesÓ

Any other Adjacencies?
(ok to use a row more than once)

Adjacencies can Overlap

Any More Adjacencies?

unsimplified majority

simplified majority

Simplified/Unsimplified Comparison for Majority


	Draw the diagrams
	Unsimplified: 4 and-gates, 3 inputs each, some with negation, 1 4-input or-gate
	Simplified: 3 and-gates, 2 inputs each, none with negation, 1 3-input or-gate

Implications for Simplified Functions


	If communicated by human, easier to understand, transfer
	If implemented as hardware, fewer gates, wires
	If implemented as software, fewer tests, execution steps

Visualizing Adjacencies


	Hypercube representation of truth table
	Karnaugh map representation

Hypercubes
(connected vertices = adjacent)

Hypercubes

Sub-cubes


	An n-dimensional hypercube, for n > 0, has embedded in it a set of m-dimensional hypercubes, for each m < n.
	These are call the sub-cubes of the original hypercube.

Sub-cubes

Which sets are subcubes?

Plotting Functions
on Hypercubes

Simplified Functions
on Hypercubes

Sub-Cube Dimensions


	The dimension of a sub-cube is n minus (number of variables in the corresponding product term)

	where n is the total number of variables.
	Examples: 3 variables total:
		dimension 0: 3 variables
		dimension 1: 2 variables
		dimension 2: 1 variables
		dimension 3: 0 variables (= constant 1)
	ÒMore is lessÓ (Greater dimension, fewer variables)

SOP Circuits


	An SOP will always correspond to
		a set of sub-cubes
		Collectively the vertices in the sub-cubes cover the ÒonÓ vertices.
		The vertices in the sub-cubes donÕt cover any ÒoffÓ vertices.
	Such a set is called a cover for the function.
	Each cover corresponds to a different gate implementation.

Simplified Covers


	In a fully-simplified SOP, each sub-cube will be maximal, in that it is not contained within another sub-cube.
	If instead it were properly contained in another sub-cube, then it could be replaced with that sub-cube.
	The replacement would have fewer variables, i.e. be simpler.

Maximality

More-is-Less Principle

EinsteinÕs Principle:


	Explanations should be made as simple as possible, but no simpler.

Non-Uniqueness of Simplest Cover

4-D Hypercube

Alternate 4-D hypercube representation
(= ÒshadowÓ of a Tesseract)

Plotting Function on 4-D Hypercube

Hypercube Function-Plotting Applet

Gray Code on a Hypercube

Other CS uses of Hypercubes


	Distributed parallel computer topologies
	High-speed sorting

Non-CS uses of Hypercubes

Hypercubes occur wherever independent attributes are found: e.g. genetics, ÒcomplexityÓ

More Hypercube Projections

Non-CS uses of Hypercubes: chemistry

Hypercube Game

RubickÕs Hypercube

Karnaugh Maps


	Invented by Maurice Karnaugh, 1953, at Bell Labs
	A way to visualize hypercubes of up to 4 (and stretching to 5 or 6) dimensions
	Approach by ÒflatteningÓ a hypercube
	A structured form of Venn Diagram

Ò3-DÓ Karnaugh Map

Covering on a Karnaugh Map

Try this one

Answer

Using a Karnaugh Map to Prove Equalities

4-D Karnaugh Map

Implied connections on
4-D Karnaugh Map

Minterm Numbering on
4-D Karnaugh Map

Assorted Sub-Cubes on
4-D Karnaugh Maps

Try this one

Exercises, etc.


	Project: Translate the hypercube game into a Karnaugh-map game.

	Exercise: Why is a Gray code sometimes called a Òsnake-in-the-boxÓ code?

Simplification with
ÒDonÕt CareÓ Combinations


	For certain problems, certain combinations (truth-table rows) never arise in actual operation.

	These are called ÒdonÕt careÓ combinations.

	Because their input combinations never occur, the function value can be either 0 or 1. This means we can elect which value to use at our discretion.

	Usually we elect whichever value achieves the best simplification of the result.

Example: mod 3 adder

Plot Function on a K-Map

Do the other half.

The other half.

Implementation using
NAND gates


	In some families of logic, and- and or- gates might not be available.
	Instead the only gate is nand (negated and).
	The question of sufficiency arises.

Sufficiency


	We know that functions and, or, and not are sufficient to realize any logic function.
	Two proofs:
		minterm expansion: a sum of minterms, and each minterm uses and and not only
		Boole-Shannon expansion (applied recursively)

Sufficiency


	To show that a given set of gate types is sufficient, it is enough to show that and, or, and not can be realized with those gate types.
	Actually it is sufficient to show just and and not can be realized, since or can be realized as: a + b = (aÕ bÕ)Õ by DeMorganÕs law. So if and and not are realizable, so is or.

nand alone is sufficient


	aÕ = nand(a, a)
	and(a, b) = nand(a, b)Õ
	or(a, b) = nand(aÕ, bÕ) = nand(nand(a, a), nand(b, b))

Exercises


	nor alone is sufficient.
	Is xor alone sufficient?

Bubble Logic

SOP form using nandÕs only

Logic Rebuses

Common Logic Packages


	mod-2 adder
	mod-2 adder with carry-in
	4-bit adder
	decoder (binary to one-hot)
	encoder (one-hot to binary)
	(MUX) multiplexor
	(DMUX) demultiplexor

mod-2 adder with carry-out

mod-2 adder with carry-in/out

4-bit ripple-carry adder

4-bit decoder

4-bit encoder

multiplexor

demultiplexor

Exercises


	How would you build a decoder out of a demultiplexor?
	How would you build a 16-way multiplexor out of 4-way multiplexors?
	How would you build a 16-way demultiplexor out of 4-way demultiplexors?
	How would you use a decoder to build a decoder ring?