Home Analysis and system design Self-synchronous circuits. Calculation of logic functions directly from the event graph. Part 3. Decomposition

# Self-synchronous circuits. Calculation of logic functions directly from the event graph. Part 3. Decomposition

Let me remind you of an important conclusion from the previous parts. For cyclic sequential behavior that does not contain multiple signals (switching more than twice per cycle), the minimum logic function of each signal can be represented in the following form (naturally, if there are no CSC conflicts)
1) where a*b*…*c is an implicant consisting of one or more variables. g+h+…+i is a possibly empty set of implicants consisting of one variable. x*f is an implicant of 2 variables, the presence of which in minimal form is optional. All variables except x can enter the formula either directly or inversely, depending on the sign arrangement of the corresponding events. All variables enter the formula as arguments strictly once each time.
Before we go any further, let’s take a closer look at such a phenomenon as decomposition. First of all, we are interested in decomposition that preserves self-synchrony. In the decomposition of a NOT-OR logic function, a new element can be distinguished :
(a) One or more implicants,
b) several signals (variables) of one implicant,
c) one input inverter.
First, let us consider a special case of the NOT-OR function OR. The behavior of such a logic function (x=a+b+c+d) for the model under consideration : It can have several signals as a separate element.
In essence, selecting a new element in decomposition is adding a new signal (f). To maintain correct behavior, semi-modularity, and self-synchrony, the switches of the newly added signal f must have an event-sequence. Since decomposition affects only one circuit element (in this case x) and does not affect the rest of the circuit elements, the switching of signal f can only be the cause of the switching of signal x. Otherwise, the logic function of the other signal would become dependent on the signal f. Given this conclusion, let us try to distinguish as a new element f any number of variables other than the variable a. Take the variables b and c as examples. They form a logical element f=b+c. As can be seen, for an event f+ it is impossible to define an event-sequence without violating the correctness of the behavior. Any group of signals that does not contain variable a cannot be singled out as a separate element with preservation of self-synchrony.
A signal like a in this example will be called an include signal. In the general case, the switching signal for the OR (AND) function is the signal whose switching to 1 (0), changes the value of the function from 0 to 1 (from 1 to 0). To maintain self-synchrony when decomposing the OR (AND) logic function, it is necessary to use an enable signal when a new element is selected. It is also necessary to use only signals that form a connected chain (in the example below a+b) when selecting a new element. x=f+c+d, f=a+b. When using a+b+d signals, self-synchrony is not preserved. Thus, for sequential behaviors without multiples when decomposing an OR (AND) logic function, isolating as a new element the first few signals in the process deployment, starting with the turning on signal, ensures that the self-synchrony of the circuit is maintained.
Let us now consider the function NOT-OR (x=!a+!b). Only the input inverter which corresponds to the switching signal (x=f+!b, f=!a) can be singled out as a separate element (f) with preservation of self-synchrony. The isolation of the other input inverters as a separate element will lead to a violation of the self-synchrony. Let us now proceed to consider the AND-ILI function. Similarly, as an enabling signal for the OR function, let us define an enabling implicant for the AND-ILI function. This is the implicant whose value changes from 0 to 1. Similarly, as was found for the OR function, for consecutive behaviors without multiples when decomposing an AND-ILI logic function, the selection of several first-order implicants, starting with the including implicant, as a new element in the process deployment ensures that the circuit is self-synchronous. Otherwise the self-synchrony will be broken. In the example below, before decomposition x=a*b+c. After decomposition x=f+c, f=a*b. Now for the AND-OR function, consider the allocation as a new element of several variables that are part of the same implicant. Only minimal functions are considered. All possible variants are given below on the example of the function x=a*b*c+d (for variant 4 – x=a*b*c+d+e, for variant 6 – x=a*b*c*d+e). The selected element f=a*b. In variant 1 switching of one of the allocated signals (a+) is the cause of event x+. In variant 2 switching of one of the allocated signals (a-) is the cause of event x-. In variants 3 and 4 switching of one of the allocated signals (a+ and a-, respectively) is located between events x+ and x-, and is not the cause of event x-. Variant 5 is a special case of variant 4, where the implicant, in which the signals are distinguished, is an inclusive implicant. The remaining variant 6 is all switches of allocated signals are located between events x- and x+, and are not causes of event x+.
As you can see, in variants 1 and 6, the f- event cannot be positioned correctly. Such transformations are not decomposition with preservation of self-synchrony. In variants 2, 3, and 4, self-synchrony is preserved. But the value of function x in this case turns out different from f*c+d (f*c+d+e for variant 4). For variant 2, x=f*(d+c), for variant 3 x=c*x+d*!f+x*!f, for variant 4 x=(f+d)*(e+c). Such transformations are not decomposition.
Only variant 5 is decomposition with preservation of self-synchrony (x=f*c+d). In this case the first few signals, starting with the including implicant, are singled out as a separate element in the including implicant (the signal including implicant AND is the same as the signal including function AND). But, as shown above, this result is achieved in two steps. First, the enabling implicant is selected. In the second step, the first few signals, starting with the including signal, are singled out in the new element.
Let us now look at the NOT-OR function. We isolate the input inverter as a separate element. The signal a corresponds to the input of the element x to which the allocated input inverter is connected (f=!a). Variants 1 and 2 – switching of signal a is the cause of event x+ (1 – x=!a+b*c, 2 – x=b*!a+c). Variants 3 and 4 – switching of signal a is the cause of event x- (3 – x=!a+b*c, 4 – x=!a*b+c). Variants 5 and 6 – switching of signal a is located between events x+ and x-, and is not the cause of event x- (5 – x=b*!a+c, 6 – x=!a*b+d+c). Variant 7 is a special case of variant 6, where the signal a is the including signal of the including implicant (x=!a*b+c). The remaining variant 8 is that all switching signals a are located between events x- and x+, and are not causes of event x+ (x=c*!a*b+d).
As you can see variants 2, 3, and 8 are not decomposition with preservation of self-synchrony, because it is impossible to correctly place the switching signal f. For variant 4 after transformation x=f*(c+b). For variant 5 after transformation x=c*!f+!f*x+b*x. For variant 6 after transformation x=(f+c)*(d+b). These transformations (variants 4, 5, and 6) are not decomposition. For option 7, after transforming x=f*b+c. Variant 7 is a decomposition with preservation of self-synchrony. In this case the inverter corresponding to the turning on signal of the turning on implicant is singled out as a separate element. This result is achieved in two steps with the help of the above mentioned transformations. First the switching implicant is singled out, and then the input inverter of the switching signal is singled out from it. For variant 1 after the transformation x=f+b*c. Variant 1 is also a decomposition with preservation of self-synchrony. It is a special case of variant 7, when the including implicant consists of a single signal.
Let us systematize the obtained results. For the considered model at decomposition of logic function NOT-OR for preservation of self-synchrony the following transformations are possible only – allocation as a separate element :
1 – one or more overlapping implicants (a special case is for a NOT-OR function to select several overlapping signals, starting with the one that includes it);
2 – in the enabling implicant of several, starting from the enabling one, overlapping signals;
3 – the input inverter corresponding to the switching signal of the switching implicant (a special case is for the NOT-OR function to allocate the input inverter corresponding to the switching signal).
These conversions cannot make the implicant include if it was not so before the conversion. Hence the conclusion: if a logic function contains an implicant which consists of more than one signal and is not including, such a function cannot be split with a self-synchronous decomposition up to two-input elements. Any logical function NOT AND OR with more than one variable containing only an including implicant can be broken down to two input elements (2I-NE, 2ILI-NE) with a decomposition that preserves self-synchrony.
Step 1 – if the logical element contains only one implicant (or all implicants consist of one variable) go to step 3, otherwise go to step 2.
Step 2 – Separate all but one implicant, starting with the one that includes it. Next, work with the newly obtained element. Go to step 1.
Step 3 – if the element consists of two variables, go to step 5, otherwise go to step 4.
Step 4 – Select as a separate element all the variables except one, starting with the one that includes it. Next, work with the newly obtained element. Go to step 3.
Step 5 applies to all two-input elements obtained.
Step 5.1 – If input inverters are on both inputs, convert the element to dual.
Step 5.2 – if the input inverter is the same and corresponds to a signal that is not an enable signal, convert the element to dual.
Step 5.3 – if there is an input inverter, isolate it as a separate element. The split is done.
Now let’s go back to formula 1 at the beginning of the text. If the implicant x*f is missing in the logical expression, then the function looks like this : x=a*b*c+g+h+i. Its behavior is : As we see, the only implicant consisting of more than one variable (a*b*c) is including. And this function can be decomposed into minimal components while maintaining self-synchrony.
If the implicant x*f is present in a logical expression, the function looks like this : x=a*b*c+x*f+g+h+i. Its behavior is : The implicant x*f, which is not including, consists of more than one variable. Such a function cannot be split with self-synchrony. But we apply a self-synchrony-preserving transformation: we add signal y, which is dual to signal x. Adding signal y changes the function of only signal x and the signal whose switching was a consequence of event x- (the variable x is replaced by the variable y). Now x=(f+i+h+g)*y, y=c*b*a+x. The implicants f+i+h+g and c*b*a including and respectively functions x and y can be split to minimal components while maintaining self-synchrony.
A simplified model of behavior (without parallelism, selection and multiples) allows to reveal properties naturally inherent to binary processes. Synthesis of self-synchronous circuits in a minimal basis is a natural phenomenon that does not require any design.