Determination of sparse representations of multiple-valued logic functions by using covering codes

Abstract

The paper points out the relationships and similarities between some problems in the theory of covering codes and the determination of sparse functional expressions for logic functions. Based on these connections we propose a method to derive functional expressions that have an a priory specified number of product terms. The method can be applied to either binary or multiple-valued functions with different sets for values of variables or function values by selecting appropriately the underlying covering code. The number of product terms in the related functional expression is determined by the covering radius of the code. We present algorithms to determine the coefficients in these expressions, discuss their complexities, and provide a direct construction to extend the application of this approach to binary and multiple-valued functions for a large number of variables.