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 LTˆ1 into a network of size O(nc/M2)O(nc/M2) and depth O(log2n/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, log2log2 depth bounded fan-in decompositions for arbitrary threshold functions in LTdLTd. These results compare favorably with the classical decomposition which has a size O(2n−M)O(2n−M) and depth O(n−M)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(n2/M)O(n2/M) size decomposition of the majority function and, O(n/M)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.