Information theoretical approach to minimization of AND/EXOR expressions of switching functions

Abstract

In modern circuit design, the Shannon decomposition of switching functions is widely used. On the other hand, in information theory of telecommunication, the Shannon entropy used as a measure to represent the information in numerical values, is a key notion. In this paper, we relate these two concepts, belonging to different areas, into an approach to the minimisation of exclusive-or sum-of-products (AND/EXOR) expressions for switching functions. The Shannon decomposition, and the closely related Davio decomposition for AND/EXOR expressions are interpreted in terms of basic concepts in the information theory. Thanks to that, we have proposed an entropy based strategy for minimization of AND/EXOR expressions. We have provided a comparison and an experimental verification of this strategy with some known heuristic minimization strategies using benchmarks. In some cases, our program Info-EXOR produces extremely better results. Moreover, the information theory interpretation of classical decomposition of switching functions offers a new point of view to the existing design styles.