Theseus Research : Technical Papers : Considerations of Completeness Page 3 of 11

The Logically Determined Cycle

While a Boolean logic combinational expression characterizes data transformation. A Boolean expression continually asserts valid data values and for any resolution zero or more output values may transition. It is not possible by watching the output data values to logically determine when a resolution begins or ends. Completion can only be determined by marking a time interval relative to the implementation of the logic expression that allows sufficient time for a resolution to begin and end. The complete Boolean logic expression includes a logic expression and a temporal expression.

For a combinational expression To logically determine the beginning of a resolution there must be a logically discriminable transition of the input from "no data present" to "complete data present". To logically determine the ending of a resolution there must be a logically discriminable transition of the output from the absence a result which can be represented as "no data present" to the presence of a result which can be represented as "complete data present". This will be called the completeness criterion.

The logical value NULL, disjoint from all data values, is introduced to represent "no data present" and will be referred to as the NULL convention. The input presented to a combinational expression will be defined to monotonically transition between two disjoint and logically discriminable state domains: "complete data present" and "no data present" or all NULL. These logical transitions shown in Figure 1 will be referred to as wavefronts. The monotonic transition from "no data present" (all NULL) to "complete data present" is a data wavefront and the transition from "complete data present" to "no data present" (all NULL) is a NULL wavefront.

Figure 1. Successive wavefronts monotonically transitioning between disjoint state domains.

Wavefront flow can be logically managed through a combinational expression with a completeness watcher at the output of the expression communicating via a request/acknowledge signal to a regulator at the input of the expression that passes and maintains wavefronts in response to the acknowledge signal as shown in Figure 2. This structure will be called a protocol cycle or simply a cycle.

Figure 2. A protocol cycle managing wavefront flow through a transmission path.

The conversation between the watcher and the regulator is a four phase handshake control protocol. [references: 1, 3]

Step 1 - Watcher detects NULL completeness and requests data wavefront
Step 2 - Regulator allows data wavefront to pass
Step 3 - Watcher detects data completeness and requests NULL wavefront
Step 4 - Regulator allows NULL wavefront to pass

Step 1 - Watcher detects NULL completeness and requests data wavefront
Step 2 - Regulator allows data wavefront to pas
Step 3 - Watcher detects data completeness and requests NULL wavefront
Step 4 - Regulator allows NULL wavefront to pass

Step 1 - And so on ...

The domain inversion in the request/acknowledge signal makes the protocol cycle a logically determined oscillator. When requesting a data wavefront the cycle will wait indefinitely for a data wavefront to arrive. When the data wavefront arrives it will be passed, resolved, completion of resolution detected and a NULL wavefront will be requested. When a NULL wavefront arrives it will be passed, resolved, completion of resolution detected and a data wavefront will be requested. If a wavefront arrives early it will be obliged by the regulator to wait on its enabling request/acknowledge signal. The monotonic alternation of wavefronts propagating through the cycle is completely logically determined [reference 7]. As long as there is a succession of wavefronts presented to the regulator they will be spontaneously resolved in turn through the combinational expression.