Complexity in Electronic Switching Circuits

Abstract

The complexity of an electronic switching circuit is defined in a sufficiently general way so that most definitions which are presently used may be included. If ø(p, q) is the complexity of a p input q output circuit which has been minimized then we may define E(p, q) as the maximum of ø(p, q) over all p input, q output circuits. In spite of the generality of the definition of complexity one may obtain the following inequality which gives upper and lower bounds on this maximum complexity: C ₁ 2 ^r /r≦E(p, q)≦C ₂ 2 ^r /r where r = p+log ₂ q. In this expression C ₁ and C ₂ are constants independent of p and q which depend upon the definition of complexity. These theoretical bounds are compared with those obtained from a few known circuiit designs.