Section 4.3 Switching Algebra
Functional Decomposition
Alfredo Benso Politecnico di Torino, Italy Alfredo.benso@polito.it

Why?
Goal: • Translate a large and complex circuit into a network of small and simple circuits • Express a switching function of n variables as a composition of switching functions of less than n variables Motivation: • Reduce the complexity of simplification • Reduce the size of a circuit by finding common circuit elements Theoretical background: • Shannon’s Expansion Theorem (SET): – Simple type of decomposition – f(x1, x 2, ..., xn) = x 1f(1, x 2, ..., xn) + x’1 f(0, x 2, ..., xn)

1

Residues
• The function that is obtained from setting one of the variables, say xi, equal to 1 is called xiresidue. If xi is set to 0, the resulting function is called xi’-residue. • The notation for the xi–residue function is fi(1); for the x’i–residue is fi(0).

Boolean Difference
• The “Boolean Difference” (or Boolean Derivative) indicates whether f is sensitive to changes in the value of xi and is defined as:

∂f = fi (0) ⊕ f i (1) ∂xi
Example • f(w,x,y,z) = wx + w′ z′ , find values of x and z to sensitize circuit to changes in w. fw = x , fw′ = z′

∂f = z′ ⊕ x = z′x′ + zx ∂w z=x=1 o r z=x=0 will sensitize circuit to changes in w

2

Simple Disjoint Decomposition
Definition: • A switching function f(x1, ..., xn) is functionally decomposable iff there exists switching functions G and H (simple)

x1 f xn

A

G B

H

where A ∪ B = {x 1, ..., x n} and A and B are mutually disjoint (they do not share inputs)

Example
F(w,x,y,z) = wx’yz + wxyz’ + w’x’y’z’ + w’xy’z = (x’z + xz’)wy + (x’z’ + xz)w’y’ = (x’z + xz’)wy + (x’z + xz’)’w’y’ = G(x,z)wy + G(x,z)’w’y’ (G(x,z) = x’z + xz’) = H(G(x, z), w, y) (H(k, w, y) = kwy + k’w’y’) Here A = {x, z}, B = {w, y}

3

How do I find a simple disjoint decomposition?
Theorem • A function f(X) has a simple disjoint decomposition F(g[Y ], Z) iff each residue fZ equals either 0, 1, g[Y ], or g’[Y]

How do I find a simple disjoint decomposition?
F(w,x,y,z) = wx’yz + wxyz’ + w’x’y’z’ + w’xy’z 1) Step 1: K-maps (if necessary for each residue of F)
A=xz 00 B=wy 00 01 10 11 1 0 0 0 01 0 0 0 1 10 0 0 0 1 11 1 0 0 0

4

How do I find a simple disjoint decomposition?
2) Look at the rows/columns
A=xz 00 B=wy 00 01 10 11 1 0 0 0 01 0 0 0 1 10 0 0 0 1 11 1 0 0 0

fw’y’ = G’ fw’y= 0 fwy’= 0 fwy = G fw’y’ = G fw’y= H fwy’= H fwy = G

OK!

NO!

How do I find a simple disjoint decomposition?
3) Write the decomposition
A=xz 00 B=wy 00 01 10 11 1 0 0 0 01 0 0 0 1 10 0 0 0 1 11 1 0 0 0

fw’y’ = G’ fw’y= 0 fwy’= 0 fwy = G G = x’z+xz’

F = w’y’ G’ + wy G

5

How do I find a simple disjoint decomposition?
3) Write the decomposition
A=xz 00 B=wy 00 01 10 11 1 0 0 0 01 0 0 0 1 10 0 0 0 1 11 1 0 0 0

No decomposition is possible fw’y’ = G fw’y= H fwy’= H fwy = G

6