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
"notdata" value NULL (N) and the value
INTERMEDIATE (I), which expresses "notcomplete".
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 "notcomplete" 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
nonlogical 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 singleform complete
expression.
