Асинхронная логика

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Асинхронная логика представляет собой своего рода симбиоз комбинационной логики и асинхронной секвенциальной логики. В теории цифровых устройств асинхронная логика отличается от синхронной тем, что её пропозициональные элементы действуют асинхронно во времени, не подчиняясь общему регулятору, или датчику времени. Это означает, что каждый вход моделируемого цифрового устройства руководствуется своим собственным временем, своими часами.

Характеристика[править | править вики-текст]

Асинхронная логика представляет собой своего рода симбиоз комбинационной логики и асинхронной секвенциальной логики. В теории цифровых устройств асинхронная логика отличается от синхронной тем, что её пропозициональные элементы действуют асинхронно во времени, не подчиняясь общему регулятору, или датчику времени. Это означает, что каждый вход моделируемого цифрового устройства руководствуется своим собственным временем, своим генератором тактовых импульсов.

Асинхронная логика является разделом дискретной математики, и может рассматриваться как прикладная дисциплина математической логики. Математическим аппаратом асинхронной логики служит булева алгебра, которая дополняется алгебраическими инструментами асинхронной секвенциальной логики — венъюнкцией и секвенцией.

Математические инструменты[править | править вики-текст]

1. Венъюнкция — это логико-динамическая операция (знак \angle) над двумя пропозициональными переменными:

x\,\angle\,y=1,  если \,x=0/1  на фоне \,y=1;
x\,\angle\,y=0, если \,x=0 или \,y=0, или y\,\angle\,x=1.

2. Секвенция — это последовательность пропозициональных переменных (обрамление \left\langle \right \rangle ), которая, будучи двоичной функцией, принимает единичное значение при следующей очерёдности переключений: \left\langle x_1\,x_2\,\ldots\, x_\mathrm n \right \rangle = \left \langle \left (-/1 \right ) \,\left(0/1 \right )\,\ldots\, \left (0/1 \right ) \right \rangle .

В других случаях секвенциальная функция равно нулю.

Формулы асинхронной логики[править | править вики-текст]

Формулы асинхронной логики — это аналитические выражения, в которых пропозициональные переменные соединены булевыми операциями конъюнкции, дизъюнкции и отрицания с участием логико-динамической операции венъюнкция. Кроме того, наряду с двоичными переменными, в формулах могут присутствовать секвенции. Преобразования формул асинхронной логики подчинены определённым правилам.

Законы венъюнкции[править | править вики-текст]

1. Отрицание венъюнкции:

\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. Сочетание венъюнкции с конъюнкцией:

\left ( x\, \angle\, y \right ) \land \left ( y\, \angle\, x \right ) = 0, \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. Сочетание венъюнкции с дизъюнкцией:

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

4. Связь венъюнкции с секвенцией:

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

Преобразование секвенций[править | править вики-текст]

1. Ассоциативность:

 \left \langle x\,y \right \rangle = \left \langle \left \langle x \right \rangle y \right \rangle,\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. Обнуление:

\left \langle \left \langle x\,y \right \rangle \left \langle x \right \rangle \right \rangle = 0, \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. Поглощение:

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

4. Расщепление:

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

5. Склеивание (при условии \left \langle x \right \rangle \supseteq \left \langle u \right \rangle):

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

6. Декомпозиция:

\left \langle x\,y\,z\,u\,v \right \rangle = \left \langle \left \langle x\,y \right \rangle \left \langle y\,z \right \rangle \left \langle z\,u \right \rangle \left \langle u\,v \right \rangle \right \rangle, \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. Связь с конъюнкцией (конъюнктивное разложение секвенции):

\left\langle x_1\,x_2\,x_3\ldots\, x_\mathrm {n-1}\, x_\mathrm n\right\rangle = \left\langle x_1\,x_2 \right\rangle \land \left\langle x_2\,x_3 \right\rangle \land \ldots
\left\langle x_\mathrm {n-1}\, x_\mathrm n\right\rangle.

8. Связь с венъюнкцией (венъюнктивное разложение секвенции):

\left\langle x_1\,x_2\,x_3\ldots\, x_\mathrm {n-1}\, x_\mathrm n\right\rangle = x_\mathrm n\, \angle\, \left (x_\mathrm {n-1}\, \angle\, \left ( \ldots \left (x_3\, \angle\, \left (x_2\, \angle\, x_1 \right ) \right ) \ldots \right )\right ).

Триггерная функция[править | править вики-текст]

Триггерной называется функция-шаблон, в соответствии с которой реализуются асинхронные парафазные устройства триггерного типа. Это секвенциальная функция двух переменных, представляемая в виде двух уравнений:

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

Аргументы X и Y должны удовлетворять следующим соотношениям:

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • В. И .Варшавский, В. Б. Мараховский, Л. Я. Розенблюм и А. В. Яковлев, § 4.3 Апериодическая схемотехника, в кн. Искусственный интеллект, т.3: Программные и аппаратные средства. Под ред. В. Н. Захарова и В. Ф. Хорошевского. М.: Радио и связь, 1990.
  • J. B. Dennis, "Modular asynchronous control structures for a high performance processor," Project MAC conference on concurrent systems and parallel computation, 1970, pp. 55-80.
  • M. Rem, "Mathematical aspects of VLSI design," Caltech conference on VLSI, 1979, pp. 55-63.
  • G .V. Bochman, "Hardware specification with temporal logic: an example," IEEE Trans. on Computers, 1982, Vol. C-31, №43, pp. 223-231.
  • Y. Malachi and S. S. Owicki, "Temporal specification of self-timed systems," CMU conference on VLSI Systems and Computations, 1981, pp. 203-212.
  • Васюкевич В. О. Венъюнкция — логико-динамическая операция. Определение, реализация, приложения. // Автоматика и вычислительная техника, 1984, №6, стр. 73-78.
  • Васюкевич В. О. Элементы асинхронной логики. Венъюнкция и секвенция. — 2009. — 123 с. — URL: http://asynlog.balticom.lv/Content/Files/ru.pdf.
  • Васюкевич В. О. Аналитика триггерных функций // Автоматика и вычислительная техника, 2009, №4, стр. 21-29, ISSN 0132-4160.
  • Плеханов Л. П. Основы самосинхронных электронных схем. — Москва: БИНОМ. Лаборатория знаний, 2013. — 208 с. — ISBN 978-5-9963-2191-9.

Ссылки[править | править вики-текст]