A Bound on the Run Measure of Switching Functions

The run measure of a switching function has arisen in several contexts as an indication of the complexity, or cost, of a realization of the function. The run measure of a function can be defined in terms of its conventional truth-table representation. The output column of the truth table is an ordered sequence of zeros and ones that are disposed in runs; i.e., groups of like digits, of various lengths. The run measure of the function is simply the number of runs in this output sequence. It is often convenient to consider two functions to be equivalent if one can be obtained from the other by some permutation or complementation of the input variables. In this context, the cost of a function can be taken as the minimum value of the run measure over the equivalence class that contains the function. This paper derives a firm upper bound on the run measure for arbitrary n-variable switching functions when arbitrary permutations and complementations of the input variables are permitted. It is also shown that this bound is attained only in the case of the parity functions and that, hence in this sense, all other functions are less complex.