Shannon's expansion

In mathematics, Shannon's expansion or the Shannon decomposition is a method by which a Boolean function can be represented by the sum of two sub-functions of the original. While often credited to Claude Elwood Shannon, Boole proved this much earlier. Claude Shannon is credited with many other important aspects of Boolean algebra.

Expansion

The Shannon expansion develops the idea that Boolean functions can be reduced by means of the identity:

:$F = x cdot F_x + x\text{'} cdot F_\left\{x\text{'}\right\}$

where $F$ is any function and $F_x$and $F_\left\{x\text{'}\right\}$ are positive and negative Shannon cofactors of $F$, respectively. It is named for Claude Shannon.

A positive Shannon cofactor of function $F$ with respect to variable $x$ is defined as that function with all $x$’s set to $1$. A negative Shannon cofactor is the same, but sets all $x$’s to $0$.

The Shannon expansion theorem is an important idea in Boolean algebra. It paved the way for Binary decision diagrams, Satisfiability solvers, and many other techniques relevant for computer engineering and formal verification of digital circuits.

As presented in Jan.1948 paper, "The Synthesis of Two-Terminal Switching Circuits" [Bell System Technical Journal, vol.28, pp.59-98, original text.] . Simply stated as the expansion of a function as:

:$f\left(X_1, X_2, dots , X_n\right) = X_1 cdot f\left(1, X_2, dots , X_n\right) + X_1\text{'} cdot f\left(0, X_2, dots , X_n\right)$

followed by the expansion for two variables, and noting that expansion can be continued for any number of variables.

Example

Rather than explain it pedantically, here is an example:

Take this as our function:

: $f = xyz + xy\text{'}z + x\text{'}y\text{'}z + x\text{'}yz + x\text{'}y\text{'}z\text{'} ,$

Now, notice that you can re-write the function in terms of any two variables &mdash; namely, a variable and its complement. Observe:

:$f = x\text{'}g_x\text{'} + xg_x ,$

Now, to make the final expression equivalent to our composition of functions, simply apply the distributive theorem to the function about "x":

:$f = x\text{'}\left(y\text{'}z + yz + y\text{'}z\text{'}\right) + x\left(yz + y\text{'}z\right) ,$

Now have expanded the function "f" about the variable "x".

"x" Variables

In Shannon's expansion the term "x" is very significant but problems can arise in simple equations. What if there were no x variable in one or more of the terms? Problems here can lead to confusion. Dealing with no "x" variable in one or more of the terms can be simple. The solution is not always intuitive.

In Boolean algebra, you can "AND any literal or term with 1", and still achieve the same "truth value". With that in mind, let's look at this function:

:$f = yz + xyz\text{'} + x\text{'}y\text{'}z ,$

If we desire to expand around the variable x, we simply don't have enough information in the first term to accomplish this task. So, what do we do? Remember what was said above: AND the literal with 1, or, in this case $\left(x\text{'} + x\right)$.

:$f = yz\left(x\text{'} + x\right) + xyz\text{'} + x\text{'}y\text{'}z ,$

Expand:

:$f = x\text{'}yz + xyz + xyz\text{'} + x\text{'}y\text{'}z ,$

This function contains the variable about which we want to expand the expression, so now we should have no problem performing the expansion:

:$f = x\text{'} g_x\text{'} + x g_x ,$:$f = x\text{'}\left(yz + y\text{'}z\right) + x\left(yz + yz\text{'}\right) ,$

The expansion is complete.

Of course, you can perform Shannon's Expansion about any variable you desire, so long as you can provide for that variable in the expression without changing the truth value of the expression. Also, you can perform multiple expansions of a single function (e.g. about "x", then about "y") or, you can even perform the expansion about many variables at once (e.g. about "xy"). The result is a functionally equivalent expression for the variables involved.

Expanding and minimizing

*You can expand a function
*You can minimize a function

Why make an expression larger? Is Boolean algebra all about minimizing functions?

Consider a logic device called a multiplexer. Multiplexers take "n" select inputs, and 2n data inputs, and give one output. Once you expand any boolean function about any number of variables, you can use the variables that the function was expanded about as the select inputs, and their respective composed functions as the corresponding data inputs.

References

* [http://homepages.ius.edu/JFDOYLE/c421/html/Chapter6.htm Shannon’s Decomposition] Example with multiplexers.
* [http://www1.cs.columbia.edu/~sedwards/papers/soviani2007optimizing.pdf Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF)] Paper on application.

ee also

*Truth value
*Mathematics
*Boolean algebra (logic)
*Claude Elwood Shannon

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Shannon Johnson — Vereinigte Staaten Shannon Johnson …   Deutsch Wikipedia

• Shannon-Zerlegung — Die Shannon Zerlegung (Shannon Expansion) stellt eine Möglichkeit dar, Boolesche Funktionen mithilfe ihrer sogenannten Kofaktoren darzustellen. Eine beliebige Boolesche Funktion F(x1,x2,...,xn) kann damit folgendermaßen angeschrieben werden: ,… …   Deutsch Wikipedia

• Claude Shannon — Claude Elwood Shannon (1916 2001) Born April …   Wikipedia

• Nyquist–Shannon sampling theorem — Fig.1: Hypothetical spectrum of a bandlimited signal as a function of frequency The Nyquist–Shannon sampling theorem, after Harry Nyquist and Claude Shannon, is a fundamental result in the field of information theory, in particular… …   Wikipedia

• Entropie de Shannon — L entropie de Shannon, due à Claude Shannon, est une fonction mathématique qui, intuitivement, correspond à la quantité d information contenue ou délivrée par une source d information. Cette source peut être un texte écrit dans une langue donnée …   Wikipédia en Français

• Entropie De Shannon — L entropie de Shannon, due à Claude Shannon, est une fonction mathématique qui, intuitivement, correspond à la quantité d information contenue ou délivrée par une source d information. Cette source peut être un texte écrit dans une langue donnée …   Wikipédia en Français

• Darryl Shannon — Pour les articles homonymes, voir Shannon. Darryl Shannon Données clés Nationalité  Canada Né le …   Wikipédia en Français

• NHL Expansion Draft 1999 — Der NHL Expansion Draft 1999 fand am 25. Juni 1999 in Boston, Massachusetts, statt. Der Expansion Draft wurde ausgerichtet, da mit den Atlanta Thrashers ein neues Franchise in der Eishockeyliga NHL eröffnet wurde und der Kader des Teams mit… …   Deutsch Wikipedia

• Repêchage d'expansion LNH 1999 — Le repêchage d expansion de la LNH de 1999 fut celui des Thrashers d Atlanta, la 28e franchise de la Ligue nationale de hockey. Ce repêchage se tient en prémisse du repêchage d entrée qui se déroula à Boston dans l état américain du Massachusetts …   Wikipédia en Français

• Repechage d'expansion LNH 1999 — Repêchage d expansion LNH 1999 Le repêchage d expansion de la LNH de 1999 fut celui des Thrashers d Atlanta, la 28e franchise de la Ligue nationale de hockey. Les Thrashers choisirent 26 joueurs, soit un de chaque équipe de la ligue exluant les… …   Wikipédia en Français