Traditionally in computer science the expression of data transformation and the expression of control have been viewed as inherently independent aspects of process expression which must, of necessity, be carefully coordinated. In programming languages this manifests as explicit sequence control of assignment statements. In traditional Boolean logic circuits, the gates and their interconnections are the data transformation aspect and the timing relationships expressed by careful engineering and the clock are the control aspect (which expresses the validity and invalidity of data values). But the data transformation aspect and the control aspect of process expression are not inherently independent. The expression of both aspects can be integrated into a single expression purely in terms of symbolic-value-dependent relationships with no external control expression at all. This is what is meant by a symbolically complete expression. It is completely expressed and completely determined solely in terms of symbolic-value-dependent relationships. A symbolically complete logic circuit would have no time relationships at all, and would be completely insensitive to the propagation delays among its component elements.

There have been attempts to eliminate time dependencies in digital logic circuits since D. E. Muller pioneered the pursuit in the late 1950s [1, 2]. These attempts (in order of increasing independence from time issues) are referred to as fundamental mode circuits, speed-independent circuits, and delay insensitive circuits. Only the delay insensitive circuits are completely free of delay issues of all circuit components including gates and wires. Delay insensitive circuits are generally considered the most difficult, expensive and elusive circuits to design. Only a few truly delay insensitive circuit designs are known. Fundamental mode circuits typically use matched delay lines to provide a local time reference for each circuit [4] and speed independent circuits must make assumptions about the insignificant propagation delay of the wires in the circuit.

These attempts to eliminate time dependencies are nearly always expressed within the traditional context of Boolean logic. They focus on designing Boolean logic circuits with appropriate switching behavior and surrounding them with Muller C-elements to express the control, then transmitting data between circuits with dual-rail encoding. These structures of Boolean logic circuits and C-elements can become very subtle, very large and very expensive [3].

There has been much recent work on asynchronous design [5, 6] but, while the pursuit of asynchronous circuits has produced many interesting results, it has not delivered a theoretically complete and economically feasible solution. The current approaches still require some assumptions about local transmission delay and the extra circuitry needed to achieve asynchronous control is considerably more than is required by a functionally equivalent clocked Boolean logic circuit.

NULL Convention Logic is a theoretically complete and economically feasible approach to delay insensitive circuits. In this paper, we first introduce the NULL Convention in the context of Boolean logic, showing how to make Boolean logic symbolically complete as a four value logic. Then, we show how the NULL Convention can be implemented as a two value logic, which will prove to be the most practical form. We conclude with a discussion of the properties of NULL Convention Logic.