Asynchronous logic (algebra)

Asynchronous logic is a sort of symbiosis (mixture) of combinational logic and sequential logic. In digital circuit theory asynchronous logic differs from synchronous one because its propositional variables act asynchronously without common clocked regulation and control. It means that every input of digital circuit follows its own time, own clock.

Characteristics

Asynchronous logic is part of discrete mathematics, and it is also considered an applied discipline of mathematical logic. Mathematical apparatus of asynchronous logic is served by Boolean algebra as well as by algebraic INSTRUMENTS of sequential logic – venjunction and sequention. The corresponding mathematical apparatus in the form of logical relationships is assigned for digital circuit representation, analysis and synthesis.

Mathematical instruments

1. Venjunction is a logic-dynamic operation (sign ∠) with two propositional variables.

x ∠ y = 1,  if  x = 0/1  on the background  y = 1;

x ∠ y = 0, if  x = 0 or  y = 0, or y ∠ x = 1.

2. Sequention is a sequence (inside angle brackets ⟨⟩) of propositional variables, which being binary function takes logical unity value at the following order of switchings: ⟨x₁ x₂ … x_n⟩ = ⟨(−/1) (0/1) … (0/1)⟩.

In all other cases sequential function is equal to zero.

Asynchronous logic formulas

Formulas in asynchronous logic are represented as analytical expressions, whose propositional variables are connected by means of Boolean operations – conjunction, disjunction and negation, which are combined with additional logic-dynamic operation – venjunction. Alongside with binary variables, sequentions are also forming components of the formulas. Transformations of asynchronous logic formulas obey certain rules.

Venjunction laws

1. Negation of venjunction:

$\quad \overline {\left ( x\, \angle\, y \right )} = \bar{x} \lor \bar{y} \lor \left ( y\, \angle\, x \right ), \quad \overline {\overline {\left ( x\, \angle\, y \right )}} = \left ( x\, \angle\, y \right ).$

2. Combination of venjunction and conjunction:

$\backslash left\; (\; x\backslash ,\; \backslash angle\backslash ,\; y\; \backslash right\; )\; \backslash land\; \backslash left\; (\; y\backslash ,\; \backslash angle\backslash ,\; x\; \backslash right\; )\; =\; 0,\; \backslash quad$

x \land \left ( x\, \angle\, y \right ) = \left ( x\, \angle\, y \right ), \quad y \land \left ( x\, \angle\, y \right ) = \left ( x\, \angle\, y \right ).

3. Combination of venjunction and disjunction:

$\backslash left\; (\; x\backslash ,\; \backslash angle\backslash ,\; y\; \backslash right\; )\; \backslash lor\; \backslash left\; (\; y\backslash ,\; \backslash angle\backslash ,\; x\; \backslash right\; )\; =\; \backslash left\; (\; x\; \backslash land\; y\; \backslash right\; ),\; \backslash quad$

x \lor \left ( x\, \angle\, y \right ) = x, \quad y \lor \left ( x\, \angle\, y \right ) = y.

4. Connection of venjunction and sequention:

x ∠ y  = ⟨y x⟩.

Transformation of sequentions

1. Associativity:

$\backslash left\; \backslash langle\; x\backslash ,y\; \backslash right\; \backslash rangle\; =\; \backslash left\; \backslash langle\; \backslash left\; \backslash langle\; x\; \backslash right\; \backslash rangle\; y\; \backslash right\; \backslash rangle,\backslash quad$

\left \langle \left \langle x \right \rangle \left \langle y \right \rangle \right \rangle = \left \langle x \left \langle y \right \rangle \right \rangle .

2. Zeroing:

$\backslash left\; \backslash langle\; \backslash left\; \backslash langle\; x\backslash ,y\; \backslash right\; \backslash rangle\; \backslash left\; \backslash langle\; x\; \backslash right\; \backslash rangle\; \backslash right\; \backslash rangle\; =\; 0,\; \backslash quad$

\left \langle \left \langle x\,y \right \rangle x \right \rangle = 0, \quad \left \langle x\,y \left \langle x \right \rangle \right \rangle = 0.

3. Absorption:

$\backslash left\; \backslash langle\; \backslash left\; \backslash langle\; x\; \backslash right\; \backslash rangle\; \backslash left\; \backslash langle\; x\backslash ,y\; \backslash right\; \backslash rangle\; \backslash right\; \backslash rangle\; =\; \backslash left\; \backslash langle\; x\backslash ,y\; \backslash right\; \backslash rangle,\; \backslash quad$

\left \langle x \left \langle x\,y \right \rangle \right \rangle = \left \langle x\,y \right \rangle.

4. Splitting:

⟨x y z⟩ = ⟨⟨x y⟩⟨y z⟩⟩.

5. Splicing (under condition ⟨x⟩ ⊇ ⟨u⟩):

⟨⟨x y⟩⟨u y z⟩⟩ = ⟨x y z⟩.

6. Decomposition:

$\backslash left\; \backslash langle\; x\backslash ,y\backslash ,z\backslash ,u\backslash ,v\; \backslash right\; \backslash rangle\; =\; \backslash left\; \backslash langle\; \backslash left\; \backslash langle\; x\backslash ,y\; \backslash right\; \backslash rangle\; \backslash left\; \backslash langle\; y\backslash ,z\; \backslash right\; \backslash rangle\; \backslash left\; \backslash langle\; z\backslash ,u\; \backslash right\; \backslash rangle\; \backslash left\; \backslash langle\; u\backslash ,v\; \backslash right\; \backslash rangle\; \backslash right\; \backslash rangle,\; \backslash quad$

\left \langle x\,y\,z\,u\,v \right \rangle = \left \langle \left \langle \left \langle \left \langle \left \langle x\ \right \rangle y \right \rangle z \right \rangle u \right \rangle v \right \rangle.

7. Association with conjunction (conjunctive decomposition of sequention):

$\backslash left\backslash langle\; x\_1\backslash ,x\_2\backslash ,x\_3\backslash ldots\backslash ,\; x\_\backslash mathrm\; \{n-1\}\backslash ,\; x\_\backslash mathrm\; n\backslash right\backslash rangle\; =\; \backslash left\backslash langle\; x\_1\backslash ,x\_2\; \backslash right\backslash rangle\; \backslash land\; \backslash left\backslash langle\; x\_2\backslash ,x\_3\; \backslash right\backslash rangle\; \backslash land\; \backslash ldots$

\left\langle x_\mathrm {n-1}\, x_\mathrm n\right\rangle.

8. Association with venjunction (venjunctive decomposition of sequention):

⟨x₁ x₂ x₃… x_n − 1 x_n⟩ = x_n ∠ (x_n − 1 ∠ (…(x₃ ∠ (x₂ ∠ x₁))…)).

Trigger function

Trigger function is an asynchronous logic function which serves as a template for constructing trigger (flip-flop) type circuits with paraphase outputs. It is a sequential function of two variables, represented by two equations:

$Z\_X=X\; \backslash lor\; \backslash overline\{X\}\; \backslash angle\backslash ,\; \backslash overline\{Y\},\; \backslash quad$

Z_Y=Y \lor \overline{Y} \angle\, \overline{X}.

Input arguments X and Y must satisfy the following relations:

$X\; \backslash land\; Y=0,\; \backslash ,(X\; \backslash not=0,\; \backslash ,Y\; \backslash not=0,\; \backslash ,X\; \backslash not=\backslash overline\{Y\});\; \backslash quad$

\overline{X} \angle\, \overline{Y} \not=0; \quad\overline{Y} \angle\, \overline{X} \not=0.

See also

• Sequential logic
• Combinational logic
• Asynchronous circuit

References

• V. O. Vasyukevich. (2009). Asynchronous logic elements. Venjunction and sequention — 118 p.
• V. O.Vasyukevich. "Whenjunction as a logic/dynamic operation. Definition, implementation and applications". Automatic Control and Computer Sciences, 1984, Vol.18, No.6, pp. 68-74.
• V. O. Vasyukevich. "Analytics of trigger functions". Automatic Control and Computer Sciences. 2009, Vol.43, No.4, 184–189.

External links

• http://asynlog.balticom.lv/Content/EN/about.html (Asynchronous logic and new algebra for digital circuits).
• An introduction to asynchronous circuit design by A. Davis, S. Nowick .

fr:Processeur asynchrone ru:Асинхронная логика zh:非同步電路