Sequential logic

Sequential logic is the logic of the memory of digital devices . The name "sequential" goes back to English. sequential . The corresponding logic can also be referred to as sequential , although the latter term is mainly used in connection with logical automata.

Sequential logic differs from combinational logic in that it simulates digital devices taking into account the history of their operation (that is, it assumes the presence of memory , which is not provided for in combinational logic).

Feature

Sequential logic is a section of discrete mathematics . It develops within the framework of the theory of digital circuits in close connection with combinational logic , Boolean algebra and finite automata . Depending on the rules of operation of digital devices are divided into synchronous and asynchronous. Accordingly, their behavior is subject to either synchronous or asynchronous logic.

Synchronous Sequential Logic

In logical modeling of devices with memory, a special role is assigned to the time factor, which in synchronous circuits is naturally taken into account by the tacts of the finite automaton. Tacts determine the moments of change of states of the automaton, that is, synchronize the corresponding function.

The mathematical apparatus of synchronous logic is set by Mile and Moore’s automaton models . ^[one]

Asynchronous Sequential Logic

Asynchronous sequential logic for expressing the effect of memorization uses the moments of state transitions that are not specified in an explicit form, but based on the comparison of logical quantities according to the principle of “earlier-later”. For asynchronous logic, it is enough to set the order of state changes, regardless of any bindings to real or virtual time. The theoretical apparatus of sequential logic is made up of mathematical tools of sequencing and venjection, as well as logical-algebraic equations based on them.

Sequence

Sequence ( lat. Sequentia - sequence ) is a sequence of propositional elements represented by

ordered set for example $\left\langle x\right\rangle =\left\langle x_{1}\,x_{2}\,\ldots \,x_{\mathrm {n} }\right\rangle$ ${\ displaystyle \ left \ langle x \ right \ rangle = \ left \ langle x_ {1} \, x_ {2} \, \ ldots \, x _ {\ mathrm {n}} \ right \ rangle}$ where $x_{i}\in \left\{0,1\right\}.$ ${\ displaystyle x_ {i} \ in \ left \ {0,1 \ right \}.}$

A binary function is implemented through a sequence. $z=\varphi \left(\left\langle x\right\rangle \right)$ ${\ displaystyle z = \ varphi \ left (\ left \ langle x \ right \ rangle \ right)}$ such that $z=1$ ${\ displaystyle z = 1}$ only takes place

$\left(x_{1}\land x_{2}\land \,\ldots \,x_{\mathrm {n} }\right)=1$ ${\ displaystyle \ left (x_ {1} \ land x_ {2} \ land \, \ ldots \, x _ {\ mathrm {n}} \ right) = 1}$ provided that $\left(x_{i}=1\right)\prec \left(x_{j}=1\right)$ ${\ displaystyle \ left (x_ {i} = 1 \ right) \ prec \ left (x_ {j} = 1 \ right)}$ for all $\mathrm {\,i<j} .$ ${\ displaystyle \ mathrm {\, i <j}.}$ (Symbol $\prec$ ${\ displaystyle \ prec}$ sets the lead relation).

The sequential function is set to one for single values of the arguments, which are set in turn,

beginning with $x_{1}$ ${\ displaystyle x_ {1}}$ and ending $x_{\mathrm {n} }$ ${\ displaystyle x _ {\ mathrm {n}}}$ . In all other cases - $z=0$ ${\ displaystyle z = 0}$ .

Venjunction

Venjunction is an asymmetric logical-dynamic operation. $\angle \,,$ ${\ displaystyle \ angle \ ,,}$ according to which a bunch $x\,\angle \,y$ ${\ displaystyle x \, \ angle \, y}$ takes a single value only in case $x\,\land \,y=1$ ${\ displaystyle x \, \ land \, y = 1}$ provided that at the time of establishment $x=1$ ${\ displaystyle x = 1}$ equality $y=1$ ${\ displaystyle y = 1}$ already had a place.

The truth of the venjection is due to the switching $x=0/1$ ${\ displaystyle x = 0/1}$ on the background $y=1.$ ${\ displaystyle y = 1.}$

Logical uncertainty is expressed through venjection: $1\,\angle \,1.$ ${\ displaystyle 1 \, \ angle \, 1.}$

Venjunction and minimal (two-element) sequence are functionally identical: $x\,\angle \,y\ =\left\langle y\,x\right\rangle .$ ${\ displaystyle x \, \ angle \, y \ = \ left \ langle y \, x \ right \ rangle.}$

Implementation

The venjunctor is the main operational element of the memory of sequential logic. It is implemented on the basis of equality

$x\land \left({\bar {x}}\lor x\,\angle \,y\right)=x\,\angle \,y,$ ${\ displaystyle x \ land \ left ({\ bar {x}} \ lor x \, \ angle \, y \ right) = x \, \ angle \, y,}$ where is the formula $\left({\bar {x}}\lor x\,\angle \,y\right)$ ${\ displaystyle \ left ({\ bar {x}} \ lor x \, \ angle \, y \ right)}$ represents the SR trigger function.

The sequencer is built on the basis of a composition of venjunctors connected in a certain way. For example, to implement

sequencer $\left\langle x\,y\,z\,u\,v\right\rangle$ ${\ displaystyle \ left \ langle x \, y \, z \, u \, v \ right \ rangle}$ the following formulas are suitable: $v\,\angle \,\left(u\,\angle \,\left(z\,\angle \,\left(y\,\angle \,x\right)\right)\right),\,\left\langle x\,y\right\rangle \land \left\langle y\,z\right\rangle \land \left\langle z\,u\right\rangle \land \left\langle u\,v\right\rangle .$ ${\ displaystyle v \, \ angle \, \ left (u \, \ angle \, \ left (z \, \ angle \, \ left (y \, \ angle \, x \ right) \ right) \ right) , \, \ left \ langle x \, y \ right \ rangle \ land \ left \ langle y \, z \ right \ rangle \ land \ left \ langle z \, u \ right \ rangle \ land \ left \ langle u \, v \ right \ rangle.}$

Notes

↑ Classification of abstract automata

Literature

A. Friedman, P. Menon. Theory of switching circuits. - M.: Mir, 1978. - 580s.
Vasiukevich V. O. Venjunction - logical-dynamic operation. Definition, implementation, applications. // Automation and computing. - 1984. - №6. - pp. 73-78.
Vasyukevich V. O. Elements of asynchronous logic. Vension and sequence. - 2009. - 123s. - URL: http://asynlog.balticom.lv/Content/Files/en.pdf (inaccessible link) .

Links

ASYNCHRONOUS LOGIC AND NEW ALGEBRA FOR DIGITAL CIRCUITS
Automaton Theory // mathnet.ru

[1] Classification of abstract automata