An analysis of root functions-A subclass of the Impossible Class of Faulty Functions (ICFF)

The class of Boolean functions, which can never occur as output of a faulty combinational circuit, is known as Impossible Class of Faulty Functions (ICFF). Despite years of research, the characterization of ICFF for a complex logic network is yet a significantly open problem. In a recent work (Das et al., 2014), a partial characterization of ICFF was done by completely enumerating a subclass of ICFFs, also called the root functions. For 2-level AND-OR logic networks for up to 6-variable the root functions were completely enumerated. This paper significantly extends this line of research by providing a more general framework for handling this class of functions. Both the upper and lower bounds are derived and the maximum cardinality of the weight of non-affine root functions is established. A constructive method for obtaining non-affine root functions of maximum possible weight is provided and it is shown that there are no other such functions than those obtained by our method. The direct correspondence of these functions to the independent dominating sets in the n-dimensional hypercube Gn is used for establishing new results concerning the minimum weight of these functions. In particular, we give the exact value of the minimum cardinality of independent dominating set in Gn for any n=2r−1, where r≥2. Since our approach is also constructive, we essentially efficiently solve this problem for any n=2r−1, where r≥2, and our results conform to the observation of Harary and Livingston (2010). Finally, the problem of classifying and enumerating root functions is addressed leading to some non-trivial lower bounds on their number, though the problem appears to be hard and further research in this direction is needed.