О мостиковых схемах и асинхронной логике

Александр Кушнеров
10.01.2025

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

1. Введение

Замыкание выхода комбинационной схемы на один или несколько её входов может дать новую комбинационную схему. Поскольку данные обрабатываются от входов к выходам, обратную связь можно представить как направленную петлю на графе. С другой стороны, графы, которые задают контактные мостиковые схемы, содержат не направленные петли (циклы). Именно из-за петель такие схемы часто являются минимальными. Преобразование графа мостиковой схемы в последовательно-параллельный соответствует схеме на логических элементах. Это преобразование размыкает все петли и называется декомпозиция в базисе И/ИЛИ. Мы будем рассматривать декомпозицию, которая даёт минимальное количество логических элементов. Чтобы корректно замкнуть полученные схемы нужно выполнить определённые условия. В качестве этих условий мы используем известную замкнутую схему.
В инженерной практике релейно-контактные мостиковые схемы начали использоваться по крайней мере со второй половины 1890-х годов [1]. Однако, привлечение булевой алгебры для их анализа и синтеза состоялось лишь во второй половине 1930-х годов [2]. Рассмотрим простейшую мостиковую схему из пяти замыкающих ключей (контактов), назовём её K5. Каждый ключ в этой схеме управляется своей переменной. Присвоить переменные можно например так, как показано в Табл. 1. Последовательное соединение ключей записывается как произведение переменных, а параллельное – как сумма. Таким образом, чтобы записать булеву функцию схемы в дизъюнктивной нормальной форме (ДНФ), нужно найти все возможные пути от входа к выходу.

Табл. 1: Схема K5 и её минимальные формы.

Чтобы найти функцию двойственную данной (dual), нужно инвертировать все переменные, а затем инвертировать саму функцию. Минимизация полученного выражения даст ДНФ без инверсий. Другой способ – это заменить в исходной ДНФ все произведения на суммы и наоборот. Для некоторых функций переменных мостиковые схемы содержат минимальное число контактов [3]. Например, схема в Табл. 1 является минимальной также для функции четырёх переменных , где .

2. Декомпозиция и ложные пути

В составе ДНФ могут быть произведения с большим количеством переменных, при этом количество слагаемых также может быть большим. Для внутренней (контактной) схемы логического элемента это означает большое количество транзисторов в ряд. Такие элементы работают медленно, поэтому на практике количество входов элемента редко превышает четыре. Таким образом, в ДНФ нужно выносить общие множители за скобки. В общем случае, это называется декомпозиция в базисе И/ИЛИ, которая даёт каскадную (multilevel) схему.
Чтобы понять сколько элементов позволяет сэкономить декомпозиция, нужно обозначить каждую переменную отдельным символом и сосчитать их число. Для функции из Табл. 1 минимальная декомпозиция показана на Рис. 1. Заметим, что она является суммой двух бесповторных (read-once или fanout-free) формул и . Такие формулы мы будем использовать в дальнейшем.

Рис. 1: Минимальная декомпозиция функции из Табл. 1.

Рассмотрим некоторую идеализированную комбинационную схему, где задержка любого элемента Δt=1 , а задержка любого провода равна нулю. Самая длинная цепочка элементов от какого-либо входа до выхода схемы называется критическим путём, а число элементов в ней – глубиной. В схеме без ветвлений максимальная задержка (или просто задержка) равна произведению глубины на Δt=1 , т.е. равна глубине. Однако, схема с ветвлениями может иметь ложный критический путь (или просто ложный путь), который по-прежнему определяет глубину. Однако, задержка вычисляется по какому-то другому пути, поскольку сигнал по ложному пути никогда не проходит. Таким образом, задержка может быть меньше глубины. Насколько? Впервые на этот вопрос попытался ответить Храпченко [4]. В его конструкции, с увеличением количества входов, количество элементов и глубина увеличиваются одинаково, а задержка стремится к половине глубины.
Добавим в схему на Рис. 1 ветвление после . Для этого в формуле для из Табл. 1 обозначим , , и , тогда . Схема для этой формулы показана на Рис. 2. Убедимся, что в этой схеме самый длинный путь через является ложным. Пусть , тогда не пропустит на свой выход переключение в 0. Аналогично, для элемент не пропустит переключение в 1.

Рис. 2: Добавление ложного пути в схему на Рис. 1.

3. Обратные связи

По всей видимости, первой замкнутой комбинационной схемой был многоразрядный сумматор [5], где выход переноса старшего разряда подаётся на вход переноса младшего разряда. Эта схема построена из одноразрядных сумматоров, где элемент XOR3 даёт сумму , а элемент MAJ3 – перенос . Как показано в [6], при некоторых условиях схема превращается в запоминающую.
Преимущество замкнутых схем по сравнению с обычными, состоит в экономии количества элементов и/или уменьшение задержки. В этой статье мы рассматриваем только первый аспект. Более того, мы ограничимся лишь замкнутыми монотонными (positive unate) схемами. Это связано с предположением, что они будут реагировать на смену входных наборов так же, как обычные, не замкнутые. Варшавский с коллегами [7] доказал, что только переходы по так называемым сравнимым наборам не вызывают состязаний (hazards) в монотонных схемах. Такие переходы составляют лишь малую часть всех переходов от одного произвольного набора к другому. Для не монотонных схем подмножество разрешённых переходов ещё меньше. Насколько известно автору, то, как замкнутые монотонные схемы реагируют на переходы по сравнимым наборам, не изучал никто. Краткий обзор разработанных ранее замкнутых схем из не монотонных (binate) и антимонотонных (negative unate) элементов приведён в следующем разделе.
Rivest [8] предложил минимальную замкнутую монотонную схему, которая имеет три входа и представляет собой чередование элементов 2И и 2ИЛИ, как показано на Рис. 3(а). В общем случае, такая схема состоит из элементов, где – это количество входов, которое должно быть нечётным. Каждый элемент реализует функцию входных переменных. Rivest доказал, что не замкнутая схема, которая реализует те же самые функции, будет состоять как минимум из элементов. Таким образом, для большого можно сэкономить около трети элементов.
Найдём функции выходов

Рис. 3: Минимальная замкнутая схема (a) и соответствующий элемент (б).

Найдём функции выходов . Для этого, начиная с , будем подставлять функцию предыдущего выхода в функцию следующего. Можно ожидать, что функция , окажется зависимой от самой себя, поэтому обозначим . Каждый результат минимизируется с помощью законов поглощения конъюнкций и дизъюнкций. Как показано в Табл. 2, прямая и обратная подстановки дают функции, которые зависят только от .

Табл. 2: Получение функций выходов в схеме на Рис. 3(а).

Для избыточного КМОП элемента на Рис. 3(б), функция задаёт последовательно-параллельную схему из семи n-MOS транзисторов. Чтобы получить дополняющую часть из семи p-MOS транзисторов, нужно найти функцию двойственную . Как это сделать говорится во Введении. Если n-MOS схему представить графом, то из-за поглощаемой конъюнкции соответствующий цикл будет ложным.
Значения на выходах комбинационной схемы, в том числе и замкнутой, можно считать правильными лишь через какое-то время, необходимое для завершения всех переходных процессов. Переходы между некоторыми входными наборами вызывают самый длинный переходной процесс. Это называется худший случай, исходя из которого выбирается период тактового сигнала в синхронных комбинационных схемах. В асинхронных комбинационных схемах используется индикатор завершения переходных процессов. На Рис. 4 показано как добавить такой индикатор в схему на Рис. 3(а).

Рис. 4: Добавление индикатора в схему на Рис. 3(а).

Чтобы понять как работает схема с индикатором, достаточно рассмотреть одновременное переключение из 0 в 1 и наоборот. Пусть $\{x_1,x_2,x_3\}=111$ , а начальные состояния всех остальных элементов 0. Элементы готовы переключиться и переключатся в 1, что вызовет переключения в 1, поскольку на втором входе каждого из них есть 1. Это называется «в фазе установки (set), переключения входов и элементов ИЛИ индицируются переключениями элементов И». Аналогично, для $\{x_1,x_2,x_3\}=000$ и начальных состояний 1, переключения в 0 вызовут переключения в 0. То есть в фазе сброса (reset), переключения входов и элементов И индицируются переключениями элементов ИЛИ. Рис. 5 демонстрирует вышесказанное с помощью фрагментов графа сигнальных переходов (STG).

Рис. 5: Фрагменты STG для фазы установки (а) и сброса (б) в схеме на Рис. 4.

Таким образом, переключения индицируются в обоих фазах, – только в фазе установки, а – только в фазе сброса. Однако, чтобы схема работала правильно, переключения всеx сигналов должны индицироваться в обеих фазах. Чтобы индицировать переключения в 0, нужно собрать эти сигналы по ИЛИ. Соответственно, нужно собрать по И. Полученные сигналы подаются на C-элемент, который представляет собой триггер и задаётся уравнением . В общем случае, инверторы имеют разную задержку, поэтому их переключения в каждой фазе могут происходить в любом порядке. Все варианты этих переключений показаны на Рис. 6 с помощью (дистрибутивной) диаграммы переходов. Схема на Рис. 4 была построена и верифицирована в Workcraft [9].

Рис. 6: Диаграмма переходов для схемы на Рис. 4.

Теперь, когда мы знаем, что после добавления индикатора в минимальную схему Rivest-а, она будет работать как асинхронная, можно поискать подобные структуры среди мостиковых схем. Как выглядят мостиковые схемы для количества переменных больше пяти? На этот вопрос ответил Кузнецов. В приложении к статье [10] он приводит графы мостиковых схем с десятью и менее рёбрами. Для каждого числа рёбер (переменных) есть одна или несколько пар графов, которые реализуют одну или несколько пар двойственных функций. Для семи рёбер такая пара одна, назовём её K7. Соответствующие мостиковые схемы показаны в Табл. 3.

Табл. 3: Схемы K7 и их минимальные формы.

Как и в предыдущем случае (Табл. 1), минимальная декомпозиция функции из Табл. 3 является суммой двух бесповторных формул. Эта декомпозиция показана на Рис. 7.

Рис. 7: Минимальная декомпозиция функции из Табл. 3.

Чтобы получить схему Rivest-а из верхней или из нижней половины схемы на Рис. 7, нужно объединить некоторые входы как показано в Табл. 4.

Табл. 4: Объединение входов для схемы на Рис. 7.

Пусть для верхней половины , , $x_7= g_{11}$ . Тогда, аналогично тому, как это было сделано в Табл. 2, мы получим 11 функций, которые приведены в Табл. 5. Семь из них зависят только от , а четыре – ещё и от выхода $g_{11}$ .

Табл. 5: Функции выходов в схеме на Рис. 7.

Если вместо мы возьмём и $x_2 = g_{11}$ , то функций, не зависимых от выхода будет только шесть. Для нижней половины схемы вторая строка в Табл. 4 даст аналогичные семь функций в одном случае и шесть в другом. Теперь, добавим в схему ложный путь тем же способом, как это было сделано для схемы на Рис. 1. Это даёт схему, показанную на Рис. 8.

Рис. 8: Добавление ложного пути в схему на Рис. 7.

Пусть, как и прежде, , , но $x_7 = g_{12}$ . В результате мы получим 12 функций, которые приведены в Табл. 6. По сравнению с Табл. 5, здесь появилась дополнительная, восьмая функция $g_{10}$ , которая не зависит от выхода.

Табл. 6: Функции выходов в схеме на Рис. 8.

4. Схемы в других базисах

Хронологически первыми были замкнутые не монотонные (binate) контактные схемы на переключателях. В современных терминах такой переключатель называется мультиплексор MUX 2:1. Не монотонная мостиковая схема и её не минимальная декомпозиция показаны в Табл. 7. Минимизация превращает не монотонную функцию y в монотонную MAJ3. Для такой квази-монотонной реализации MAJ3, приведённая мостиковая схема является минимальной.

Табл. 7: Не монотонная мостиковая схема и её не минимальная декомпозиция.

Short [11] с помощью перебора построил немонотонную схему на основе двоичного дерева из семи MUX 2:1. В современных терминах такое дерево называется LUT3, восемь портов которого подключены к константам. Поскольку Short использовал переключатели, порты в его схеме могут быть либо входами, либо выходами. Четыре из этих восьми портов подключены в обратную связь [12]. Новые замкнутые схемы на MUX 2:1 под названием cyclic BDD появились спустя более, чем 40 лет [13], [14]. Другая немонотонная функция – это XOR. Она используется в полиноме Жегалкина, который также известен как алгебраическая нормальная форма (АНФ). Riedel [13], [15] предложил две конструкции АНФ схем, которые на данный момент являются лучшими. Для числа n элементов в обычной схеме, первая конструкция даёт схемы из не более, чем элементов, а вторая – из и не менее, чем $\sqrt{n}$ элементов. Куликов с коллегами [16] предложил записывать систему уравнений для схем из элементов XOR2 в специальной матричной форме. Если такая система имеет единственное решение, то функции всех выходов зависят только от входных переменных.
McCaw [17] среди прочего, преобразовал немонотонную контактную схему Short-а в схему из 16-ти монотонных элементов И и ИЛИ. Kautz [12] построил схему из антимонотонных элементов 2ИЛИ-НЕ. Однако, в зависимости от числа элементов (чётного или не чётного), эта схема может запоминать или осциллировать. Анализ этой схемы с помощью решения булевых уравнений приводит в качестве примера Cerny [18]. В рамках задачи о минимальном числе инверторов, Huffman [19] предложил не осциллирующие схемы из монотонных элементов с двумя выходными инверторами. Метод синтеза замкнутых схем на основе преобразования булевых уравнений предложил Pratt [20]. Современные методы синтеза замкнутых схем основаны на определённой модели задержки элементов. Классификация моделей задержек, а также примеры схем, которые работают правильно для одной модели и не правильно для другой, приведены в [21].

5. Выводы и обсуждение

В статье показано соответствие между ложными циклами в графе контактной схемы и минимизацией функций, реализуемых замкнутой комбинационной схемой. Ложный цикл появляется, если число рёбер графа больше, чем количество переменных. Однако, это лишь необходимое условие. Достаточное условие – формула, которая задаёт соответствующую контактную схему, должна содержать поглощаемые конъюнкции или дизъюнкции.
В статье также показано как сделать замкнутую бесповторную схему асинхронной. Такие схемы работают правильно, даже если элементы в них имеют произвольную задержку. Платой за это свойство является специальная дисциплина смены входных наборов. Обычные, не замкнутые асинхронные бесповторные схемы рассматривал Кишиневский [22].
Некоторые из упомянутых в статье схем могут переходить в режим запоминания, если на их входы подан «запрещённый» набор. Здесь возникает вопрос – можно ли придумать схемы, где запрещённый набор – это «все единицы»? Дело в том, что этот набор никогда не возникает в dual-rail асинхронных комбинационных схемах, где рабочая фаза чередуется со спейсером.

Благодарности

Автор благодарен Сергею Быстрову за идею разделить индикацию на фазу установки и фазу сброса, а также Игорю Сергееву за ответы на вопросы по дискретной математике.

Литература

[1] M. Boda, «Stromlauf-Formeln und ihre Anwendung zur Schaltung Siemenscher Blockwerke,» Zeits. des Oesterr. Ingenieur und Architekten-Vereines, vol. XVIX, pp. 620, 634, 647, 664, Taf. 33, 1897.
[2] В. И. Левин, «История открытия логического моделирования технических устройств,» Вестник российских университетов. Математика, т. 9, № 4, pp. 458-463, 2004.
[3] A. Kushnerov and S. Bystrov, «On minimal realization and behavior of NCL gates,» Preprint, 2022, DOI: 10.13140/RG.2.2.31525.47847.
[4] В. М. Храпченко, «Различие и сходство между задержкой и глубиной,» Проблемы кибернетики, № 35, pp. 141-168, 1979.
[5] Annals of the Computation Laboratory of Harvard University, Vol. I. A Manual of Operation for the Automatic Sequence Controlled Calculator, Harvard University Press, 1946.
[6] J. J. Shedletsky, «Comment on the sequential and indeterminate behavior of an end-around-carry adder,» IEEE Transactions on Computers, Vols. C-26, no. 3, pp. 271-272, 1977.
[7] В. И. Варшавский (ред.), Апериодические автоматы, Наука, 1976.
[8] R. L. Rivest, «The necessity of feedback in minimal monotone combinational circuits,» IEEE Transactions on Computers, Vols. C-26, no. 6, pp. 606-607, 1977.
[9] https://workcraft.org.
[10] А. В. Кузнецов, «О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики,» Труды математического института АН СССР, т. 51, pp. 186-225, 1958.
[11] R. A. Short, A theory of relations between sequential and combinational realizations of switching functions. Technical Report No. 098-1, Stanford Electronics Labs, 1960.
[12] W. H. Kautz, «The necessity of closed circuit loops in minimal combinational circuits,» IEEE Transactions on Computers, Vols. C-19, no. 2, pp. 162-166, 1970.
[13] M. D. Riedel, Cyclic combinational circuits. PhD thesis, California Institute of Technology, 2004.
[14] S. N. Yanushkevich, G. Tangim, S. Kasai, S. E. Lyshevski and V. P. Shmerko, «Design of nanoelectronic ICs: Noise-tolerant logic based on cyclic BDD,» in IEEE Int. Conference on Nanotechnology, 2012.
[15] M. D. Riedel and J. Bruck, «Cyclic Boolean circuits,» Discrete Applied Mathematics, vol. 160, no. 13-14, pp. 1877-1900, 2012.
[16] M. G. Find, A. Golovnev, E. A. Hirsch and A. S. Kulikov, «A better-than-3n lower bound for the circuit complexity of an explicit function,» in IEEE Symposium on Foundations of Computer Science (FOCS), 2016.
[17] C. R. McCaw, Loops in directed combinational switching circuits. Technical Report No. 6208-1, Stanford Electronics Labs, 1963.
[18] E. Cerny, An approach to unified methodology of combinational switching circuits. PhD thesis, McGill University, 1975.
[19] D. A. Huffman, «Combinational circuits with feedback,» in Recent Developments in Switching Theory, A. Mukhopadhyay, Ed., Academic Press, 1971, pp. 27-55.
[20] W. C. Pratt, Transformation of Boolean equations for the design of multiple-output networks. PhD thesis, University of Illinois at Urbana-Champaign, 1976.
[21] M. Mendler, T. R. Shiple and G. Berry, «Constructive Boolean circuits and the exactness of timed ternary simulation,» Formal Methods in System Design, vol. 40, no. 3, pp. 283-329, 2012.
[22] М. А. Кишиневский, Реализация и анализ апериодических схем. Дис. канд. техн. наук, Ленинградский электротехнический институт, 1982.

ссылка на оригинал статьи https://habr.com/ru/articles/872874/