Information Theoretic Approach to Logic Functions Minimization

Abstract

Information theory methods are of wide use in contemporary logic design, but their proper application to Computer Aided Design (CAD) is rather impossible without strong theoretical and practical justification. Our research is focused on logic function minimization which is an essential component of any system for digital circuit design. The well-known information theory methods to minimize logic functions should be improved and developed towards new problems appeared while increasing the number of CAD applications. We report new results on logic functions minimization by information theory standpoint. We have developed an information theoretic model of recursive decomposition of logic functions. Based on this model, a novel technique for efficient Decision Tree design of various types (AND/OR, Reed-Muller, Kronecker Decision Trees, etc.) is presented. We develop the algorithms that employ information theoretic measures to minimization of the logic functions represented by Decision Trees. We investigate the effect of information theory appliance to minimization of multiple-valued, incompletely specified functions, and to symmetry detection as well. We give the extended experimental study to validate the approach. The presented results can be treated as a significant step towards better understanding of the behavior of digital circuits from the information theory point of view. This achievement creates the prospect of solving the wide circle of logic design problems, including low-power and high-testable circuits synthesis.