Shannon expansion

This MedLibrary.org supplementary page on Shannon expansion is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:

Related Sponsors

BM Pharmacy Generic pharmaceuticals at unbeatable prices. Insomnia, men's health, hair health, pain control. bmpharmacy.com

Online Pharmacy Carisoprodol, tadalafil, sildenafil, vardenafil and more... xlpharmacy.com

MedBasket.com Discreet. Inexpensive. Fast shipping. Great selection. What more can we say? medbasket.com

Frugalmed 2000 reasons to shop with us first. frugalmed.com

Ads by Tiva

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.

1 Expansion
- 1.1 Example
- 1.2 x Variables
2 Expanding and minimizing
3 References
4 External links
5 See also

Expansion

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

$F = x \cdot F_x + x' \cdot F_{x'}$

where $F$ is any function and $F x$ and $F x'$ 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" ^[1]. Simply stated as the expansion of a function as:

$f(X_1, X_2, \dots , X_n) = X_1 \cdot f(1, X_2, \dots , X_n) + X_1' \cdot f(0, X_2, \dots , X_n)$

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'z + x'y'z + x'yz + x'y'z' \,$

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

$f = x'g_x' + 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'(y'z + yz + y'z') + x(yz + y'z) \,$

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' + x'y'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 $(x' + x)$ .

$f = yz(x' + x) + xyz' + x'y'z \,$

Expand:

$f = x'yz + xyz + xyz' + x'y'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' g_x' + x g_x \,$

$f = x'(yz + y'z) + x(yz + yz') \,$

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 2ⁿ 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

^ Bell System Technical Journal, vol.28, pp.59-98, original text.

External links

Shannon’s Decomposition Example with multiplexers.
Optimizing Sequential Cycles Through Shannon Decomposition and Retiming (PDF) Paper on application.

Welcome to the MedLibrary.org Wikipedia Supplement on Shannon expansion -- Please Click to Return to Front Page