Information Theory and the Complexity of Switching Networks

Document Type

Conference Proceeding


Mathematics (HMC)

Publication Date



Our purpose in this paper is to establish some relationships between two areas pioneered by Shannon: information theory and the complexity of switching networks that realize Boolean functions. We investigate the following three questions.

1. How does the complexity of a function depend on the number of 1's and 0's in its truth table?

2. How does the complexity of an incompletely specified function depend on the number of unspecified entries in its truth table?

3. If we do not insist that a function be realized exactly, but allow a certain number of entries in its truth table to be changed, what reduction in complexity is possible?

These questions are answered by combinatorial arguments, but in each case the answer admits an information-theoretic interpretation that renders it more memorable. This interpretation has only heuristic significance, however, and does not provide an alternate means of deriving our results.

Rights Information

© 1975 IEEE