next up previous
Next: Synchronous Logic Up: Logic Pipelines Previous: Logic Pipelines

Combinational Logic

A combinational logic network is one that is free of synchronous elements. This is not a particularly helpful definition -- we will use only the fact that a combinational circuit that is also free of directed cycles implements a pure function. The outputs depend only on the value of the inputs and not on their history.

The circuit is implemented using wires, transistors, etc. This obvious fact has two important consequences. First, to be useful the circuit is attached to a source of inputs and those inputs change over time. Secondly, the outputs do not instantaneously change in response to a change in the inputs; some finite delay is involved.

Quite sophisticated treatments of this delay have been studied. For our purposes it will suffice to consider just the gross maximum delay: the time between the inputs becoming stable and the outputs reliably taking on the function value corresponding to those inputs. To a very loose first approximation the lower bound on delay for realizations of a given function is proportional to the logarithm of the number of input bits.

Stephen W. Nuchia
Mon Dec 11 17:02:42 CST 2000