Delays of Schemes in a Model That Considers the Input Values of Functional Elements

摘要

A delay model for schemes of functional elements in arbitrary finite complete basis B is studied; in the model, delays of the basic element are given by random positive real numbers for each input and each input-set of variables entering other inputs. Asymptotic estimates in the form τ_Bn ± O(logn), where τ~B is a constant that depends only on basis B, are obtained for the delay of the multiplex function of order n. Based on these estimates, asymptotic estimates of the form τ_Bn ± O(logn) for the corresponding Shannon function, i.e., for the delay of the worst function of logic algebra that depends on given n variables, are established.