On the Depth of a Multiplexer Function with a Small Number of Select Lines.

This paper continues the research on the circuit synthesis problem for a multiplexer function of logic algebra, which is a component of many integrated circuits and is also used in theoretical study. The exact value of the depth of a multiplexer with select lines in the standard basis is found under the assumption that the conjunction and disjunction gates are of depth 1 and the negation gate is of depth 0; the depth equals if . Thus, it follows from previous results that the exact depth value equals for all positive integers such that either or . Moreover, for , this value equals 2, and for , it equals either or . Similar results are also obtained for a basis consisting of all elementary conjunctions and elementary disjunctions of two variables. [ABSTRACT FROM AUTHOR]