Composing Cycles into Pipelines and Systems

Logically determined pipeline structures can be composed by combining the regulator (R) and the watcher (W) to interlink successive protocol cycles as shown in Figure 3. [references: 3, 6] Completeness of each wavefront is determined after it has passed through a regulator and is maintained by that regulator. Each regulator will maintain a wavefront until a wavefront is allowed through the succeeding regulator and maintained by that regulator. Then it will allow the next wavefront through and maintain that wavefront until accepted by the succeeding regulator. This provides logically determined wavefront flow from regulator to regulator through the pipeline. Each individual cycle, striving to oscillate, engenders the spontaneous activity of the pipeline as a whole. Pipelines can be composed into more complex structures to form spontaneously active, logically determined systems that manage complex data flows.

Figure 3. Interlinked cycles forming a pipeline.

Logically Determined Combinational Expression

The combinational expression must express the completeness criterion. For each wavefront, either data or NULL, transition of the combinational output to completeness must logically imply that the input wavefront is complete, that the wavefront has propagated through the expression and that the asserted output wavefront is the correct resolution of the presented input. To support this implication, the propagation of the wavefront through the combinational expression must be strictly monotonic. During a data wavefront there must only be transitions from NULL to data. During a NULL wavefront there must only be transitions from data to NULL. There can be no glitches and no incorrect transitions or opposite sense transitions within the expression during the propagation of a wavefront [reference 4]. Any incorrect or spurious transition will compromise the monotonic integrity of the propagation and the completeness of the wavefront will not be logically determinable and hence the behavior of the combinational expression will not be logically determined.

Logically Sufficient Gates

For a combinational expression as a whole to express the completeness criterion, the completeness criterion must be expressed by each gate as well as by any combination of gates. Sufficiently expressive gates can be defined with 4 logical values. The "data" values TRUE (T), FALSE (F), the "not-data" value NULL (N) and the value INTERMEDIATE (I), which expresses "not-complete". The truth tables of Figure 4 show the basic gate functions of this 4 value logic. A logic which uses the NULL value to express "not data" is referred to as a NULL Convention Logic (NCL) [reference 2] and this four value logic as 4NCL.

Figure 4. 4NCL logic gate truth tables.

Each gate outputs a data value only when there is "complete data present" at the input. It outputs a NULL value only when there is complete NULL ("no data present") at the input. Otherwise the input is "not-complete" and the gate outputs an INTERMEDIATE value. Each gate expresses the completeness criterion for both data and NULL.

Consider the combinational expression shown in Figure 5. Circles are gates and they are acyclically connected from input to output. Divide any such combinational expression arbitrarily into N ranks of gates ordered progressively from input to output, with all inputs before the first rank and all outputs after the last rank. The rank boundaries are shown with vertical lines labeled alphabetically in rank order from input to output.

Figure 5. The completeness criterion for a combinational expression as a whole.

For the values crossing E to be all data all of the values crossing D must be data.

For the values crossing D to be all data all of the values crossing C must be data.

For the values crossing C to be all data all of the values crossing B must be data.

For the values crossing B to be all data all of the values crossing A must be data.

These considerations are also true for the NULL wavefront presented when the expression is in an all data state. Simply substitute NULL for data in the above text.

During a data wavefront value transitions progress monotonically from NULL to data through the expression from input to output. If any value crossing a boundary is NULL or INTERMEDIATE then there will be at least one NULL or INTERMEDIATE value crossing all boundaries to the right of that boundary. There can only be a complete set of output data values when there is a complete set of input data values and the data values have propagated through the expression. There can only be a complete set of output NULL values when there is a complete set of input NULL values and the NULL values have propagated through the expression. The combinational expression as a whole expresses the completeness criterion.

The propagation of a wavefront through the expression is completely logically determined. Consider gate 7 in Figure 5. It does not matter how long the data values (NULL values) take to propagate through other gates and over signal paths to the input of gate 7, it will not output data (NULL) until all values are data (NULL) at the input of the gate. No gate transitions its output to data or NULL until all the values present at the input of the gate have transitioned. Each gate is a logically determined completeness boundary that regulates the orderly propagation of monotonic transitions to correct result values through the combinational expression until the output of the expression as a whole is complete. Each gate in the expression switches its output exactly once to a correct result value. There are no races, no hazards and no spurious result values during the propagation of a wavefront.

No expression of any time relationship or any other non-logical relationship is necessary to fully characterize the behavior of the combinational expression. The behavior of the combinational expression is expressed entirely in terms of logical relationships and it is a single-form complete expression.