Delay in networks of functional elements in a model with an arbitrary distribution of basis element input delays

摘要

The article investigates a model of delays in a network of functional elements (a gate network) in an arbitrary finite complete basis B, where basis elements may have different input delays. Asymptotic bounds of the form τ _Bn ± O(1), where τ _B is a constant that depends only on the basis B, are obtained for the delay of a multiplexer function of order n, i. e., a function with n address inputs and 2 ~n data inputs whose value equals the data input with index formed by the binary values of the address inputs. These bounds are used in the given model to obtain high-accuracy asymptotic bounds of the form τ _B(n - log log n) ~± O(1) for the corresponding Shannon function, i. e., for the delay of the "worst" Boolean function of the given n variables.