Decomposition of threshold functions into bounded fan-in threshold functions
This paper obtains explicit decomposition of threshold functions into bounded fan-in threshold functions. A small fan-in is important to satisfy technology constraints for large scale integration. By employing the concept of error in the threshold function, we are able to decompose functions in LT1 into a network of size O(n(c)/M-2) and depth O(log(2)n/logM) where n is the number of inputs of the function and M is the fan-in bound. The proposed construction enables one to trade-off the size and depth of the decomposition with the fan-in bound. Combined with the work on small weight threshold functions, this implies polynomial size, log(2) depth bounded fan-in decompositions for arbitrary threshold functions in LTd. These results compare favorably with the classical decomposition which has a size O(2(n-M)) and depth O(n-M). We also show that the decomposition size and depth can be significantly reduced by exploiting the relationships between the input weights. As examples of this strategy, we demonstrate an O(n(2)/M) size decomposition of the majority function and, O(n/M) size decompositions of an error tolerant pattern matching function and the comparison function. In all these examples, except for the first level, all other levels use only majority functions. (C) 2013 Elsevier Inc. All rights reserved.
decomposition threshold functions bounded fan-in comparison function majority logic