Борис Цирлин
Рассматриваются трехэлементные последовательные схемы, причем ограничиваются только теми из них, которые уникальны своими параметрами, дают представления о тех семействах, к которым их можно отнести, или имеют какое-то отношение к практической схемотехнике.
Введение
Обратимся к трехэлементным последовательным схемам, далее просто схемам. Для удобства повторим фрагмент последнего рисунка части 2, а именно рис.1.
Их общее количество не изоморфных (1474) не оставляет надежды даже упомянуть о каждой. Поэтому рассмотрим только те из них, которые уникальны своими параметрами, дают представления о тех семействах, к которым их можно отнести, или имеют какое-то отношение к практической схемотехнике.
Уникальные схемы.
Привлекают внимание схемы с параметром w равным 1, 3 и 4 соответственно. Они имеют всего по одному представителю в общем списке, что говорит об их уникальности. Первая из них № 0 была упомянута еще в части 1 и приведена на рис.2 из которого видно, что это композиция трех одноэлементных схем с таким же номером.
Система логических уравнений, описывающих эту схему, далее просто система, инвариантна как к перестановкам , так и инверсиям переменных.
Далее рассмотрим уникальное семейство изоморфных схем, содержащее всего 3 члена Все они приведены на рис.3. Как и предыдущая они является композицией трех одноэлементных схем одной № 3 и двух № 0.
Их системы, инвариантны к инверсиям переменных и трансформируются друг в друга только их перестановками. Правда из 6 возможных перестановок действенны не все, что и объясняет такое количество изоморфных схем.
Графы переходов этих схем, далее просто графы, представляют собой 4 двунаправленных дуги (переходы между соседними состояниями схемы), расположенных на четверке параллельных ребер координатного куба. Этих четверок можно выделить в кубе всего 3 (ребер у куба 12), откуда и получается такое же количество изоморфных схем для такого графа.
Этот пример показывает, в чем заключается изоморфное преобразование схемы с точки зрения трансформации ее графа. Последняя сводится к перемещению этого графа по поверхности координатного куба. Для представления такого перемещения удобно выделить характерный фрагмент графа и поочередно размещать его на соответствующих элементах куба (вершинах, ребрах, гранях, диагоналях, сечениях) или их совокупностях. При этом надо учитывать то, что другие фрагменты графа, занимая место характерного, могут повторить его конфигурацию.
Поясним это следующим примером: семейством изоморфных схем, состоящим из четырех членов (w = 4), приведенным на рис. 4 (№ 7140, № 20145, № 45390 и № 58395).
Графы этих схем представляют две тройки дуг переходов, направленных к состояниям, расположенным на вершинах куба, являющихся концами его главных диагоналей. Таких диагоналей в кубе всего 4, что и определяет число членов этого семейства.
Обратим внимание, что все 4 системы получаются друг из друга инвертированиями переменных. Первая из этих систем инвариантна к перестановкам переменных, а остальные 3 преобразуются ими друг в друга.
Схемы с параметром w = 16
Таких схем, каждая из которых имеет 16 изоморфных, как ни странно, всего две: № 312 и № 6648 и обе они приведены на рис. 5.
Что характерно, перестановки переменных для каждой из их систем порождает всего по одной изоморфной - соответственно № 540 и № 6876, которые тоже приведены на рис. 5. Зато инверсии переменных порождает для этих пар максимальное число изоморфных - по 8, что в результате и дает анонсированные w = 16.
На графах этих четырех схем характерным фрагментом является состояние, расположенное на вершине 7 координатного куба. Именно к нему направлены дуги всех обсуждаемых графов, правда, в схемах №312 и № 540 они до него не доходят. Перестановки переменных определяют один из двух возможных путей для дуг. А помещая этот характерный фрагмент поочередно во все вершины координатного куба получим графы изоморфных схем, порождаемых инверсиями переменных, т.е. те же 16 изоморфных.
Схемы с параметром w = 8
Эти приемы применим к трем схемам, каждая из которых имеет по 8 изоморфных - рис. 6.
Граф первой (№ 804) напоминает таковой у уже рассмотренный схемы № 7140 - только в последней, характерные фрагменты привязывались к обоим концам главной диагонали координатного куба, и повторяли конфигурацию друг друга), а здесь - только к одной вершине. Размещая этот фрагмент поочередно на всех восьми вершинах куба и получим заявленное число изоморфных схем.
Вторая схема на рис. 6 (№ 11640) имеет граф переходов в виде циклической траектории, проходящей через все вершины координатного куба, кроме 0 и 7. Вот последние-то и являются характерными фрагментами, а поскольку они расположены на концах одной из главных диагоналей, то размещая их поочередно на всех главных диагоналях получим всего 4 графа изоморфных схем. Удвоить это число позволяет замена направления обхода циклической траектории на противоположное.
Применение инверсий переменных к системе этой схемы порождает 4 изоморфных, а - перестановок - только 2, что делает очевидным влияние этих действий на графы.
Циклическая траектория на графе схемы № 11640 содержит 6 состояний и, оказавшись в любом из них, схема будет переходить только в состояния этой траектории. При этом выход каждого из трех элементов побывает как в нулевом, так и единичном состояниях поочередно, т. е. схема представляет собой генератор импульсов, параметры которых и другие технические аспекты будут рассмотрены ниже.
Граф последней схемы этой серии (№ 11868) схож с таковым рассмотренной ранее схемы № 312 (рис. 5), имеющей w = 16. Разница лишь в том, что в последнем дуги однонаправленные, а здесь - двунаправленные и меняя местами друг с другом характерные фрагменты графа, расположенные на обоих концах главных диагоналей координатного куба, получим одинаковые графы переходов, что и дает только 8 изоморфных схем, против шестнадцати в предыдущем случае.
Перестановки переменных в системе этой схемы порождает только две изоморфных,- как и в случае схемы № 312, а их инверсии - все 8 возможных для этой схемы изоморфных, в том числе и порожденные перестановками.
Схемы с параметром w = 6
Последнее множество схем, которое приведено полностью (в силу его немногочисленности на рис. 7, это те, что имеют по 6 изоморфных.
Каждая из этих схем содержит, как элемент композиции, одноэлементную схему № 0, а первые 3 из них (№ 255, №1360 и № 5185) - даже две таких схемы, что и объясняет величину параметра w = 6.
Действительно, инверсия переменных в системе каждой из этих схем порождает всего две изоморфных, а перестановки переменных для первых трех (№ 255, № 1360 и № 5185) - 3 изоморфных, что, с учетом инверсий, и дает анонсированное w = 6. Для остальных (№ 21930, № 26985 и № 27030) перестановки переменных в системах дают все 6 изоморфных, в число которых входят и те, что от инверсий.
Графы схем № 255, № 5185, № 26985 и № 27030 распадаются на 2 изолированных подграфа каждый, расположенных на паре параллельных граней координатного куба. Таких пар в кубе 3 и используя их поочередно для размещения этих подграфов получим 3 изоморфных схемы для каждой их этих исходных. Удвоить это количество изоморфных позволяет замена направления всех дуг в этих графах на противоположное.
Лаконичный граф схемы № 1360 (всего две дуги, правда, двунаправленные) можно привязать к диагональному сечению координатного куба. На меньших сторонах этого сечения (соответствующих ребрах куба) расположены обе дуги графа, а всего в кубе таких сечений 6 и поочередная привязка к ним графа переходов этой схемы дает анонсированные w = 6.
Граф схемы № 21930 тоже можно привязать к паре параллельных граней координатного куба, чтобы меняя эти пары получить три изоморфных схемы, но удвоение этого количества за счет смены направления дуг графа на противоположное здесь не проходит - дуги двунаправленные. Зато можно повернуть граф в плоскости грани куба, на которой он расположен, на 90 градусов и тем самым достигнуть анонсированного результата. Возможен и другой подход, когда в качестве характерного фрагмента графа выбраны две его параллельные двунаправленные дуги. Привязав этот фрагмент к грани координатного куба, можно "отправить его в путешествие" (а с ним и весь граф) по всем шести граням и получить таким образом w = 6.
Схемы с параметром w = 12, 24 и 48.
Все оставшиеся нерассмотренными схемы, имеющие 12, 24 или 48 изоморфных каждая, объединены в один раздел и поскольку их слишком много, представлены только схемы с минимальными и максимальными номерами, которые приведены на рис. 8.
Более простыми для рассмотрения являются, как ни странно, схемы с максимальным числом изоморфных (параметр w = 48). Для того чтобы обеспечить такое значение перестановки и инверсии переменных в системах должны давать максимально возможное количество изоморфных, т. е.6 и 8 соответственно.
Граф первой из таких схем (№ 6) содержит всего две дуги, которые образуют плоскую фигуру. Она и является характерным фрагментом, помещая который поочередно на все грани координатного куба, получим 6 изоморфных схем (по числу граней). Поворачивая на каждой этот фрагмент в плоскости грани на 90 градусов 3 раза - увеличим это количество до 24, а меняя каждый раз направление дуг на противоположное, удвоим это число, получив искомый параметр w = 48.
Все сказанное можно отнести и к схеме с максимальным номером (№ 27031), граф переходов которой, в отличие от предыдущего, имеет значительное количество дуг (свободны от них только 3 ребра координатного куба из 12) и 4 из них образуют замкнутый контур. Вот последний-то и есть характерный фрагмент этого графа, к которому можно применить те же манипуляции, что и в предыдущем случае, получая при этом тот же результат.
Схема № 1 имеет параметр w = 24, при этом перестановки переменных ее системы дают 3 изоморфных, а и инверсии - 8, что и определяет этот результат.
Ее граф представляет собой всего одну дугу, которую и можно считать характерным фрагментом. Располагая эту дугу на различных ребрах координатного куба (которых, как известно, 12), получим 12 изоморфных схем, а меняя каждый раз направление дуги на противоположное - удвоим это количество, получив искомый результат.
Характерный фрагмент графа можно определить и как состояние, из которого исходит эта единственная дуга. Помещая этот фрагмент поочередно в различные 8 вершин координатного куба, получим такое же количество изоморфных, а направляя эту дугу поочередно по одному из трех исходящих из вершины ребер, утроим это количества и опять придем к w =24. Это подход имеет аналогии с инверсиями и перестановками переменных в системе.
Вторая схема с таким же количеством изоморфных (№ 27581) имеет развитый граф (содержит 8 дуг). И перестановки и инверсии переменных в ее системе ее дают максимально возможный результат каждая - 6 и 8 соответственно изоморфных схем, но за счет пересечения полученных множеств последних, параметр w = 24.
Характерным фрагментом этого графа можно выбрать пару вершин, имеющих только исходящие дуги, расположенных на вершинах 2 и 3 координатного куба. Эти вершины принадлежат общему ребру последнего, что позволяет подставляя поочередно этот фрагмент на место всех 12 ребер получить соответственно столько же графов изоморфных схем. А удвоить это количество можно перестановкой выбранных вершин на одном и том же ребре, получив, в результате параметр w = 24.
Последний пример показателен тем, что в качестве характерного фрагмента может служить не только такой элемент, как ребро графа, но и его отсутствие.
Схема № 5, имеющая w = 12, аналогична уже рассмотренной схеме № 1, и отличается только тем, что единственная дуга ее графа - двунаправленная, точнее это две противоположно направленные дуги, соединяющие одну и ту же пару вершин графа. Перестановки и инверсии переменных в ее системе дают соответственно 3 и 4 изоморфных схем каждая, что и определяет общее их количество.
Выбрав, как и в случае схемы № 1, в качестве характерного фрагмента графа дугу и повторив с ним те же манипуляции (связанные с ребрами координатного куба), получим параметр w = 12. Заметим, что изменение направления дуги на противоположное в данном случае бессмысленно.
Последняя на рис. 7 схема № 27550, имеет, как и предыдущая (№5), w = 12. Ее граф представляет собой циклическую траекторию из восьми дуг, проходящую через все 8 вершин. Инверсии и перестановки переменных в ее системе дают соответственно 4 и 6 изоморфных, но, как и в случае схемы № 27581, имеет место пересечение полученных множеств, что и ограничивает параметр w =12.
На двух параллельных гранях координатного куба расположены участки графа этой схемы, имеющие только по две дуги, а на всех остальных четырех гранях - по 3 дуги. Вот эти первые
2 участка и выберем в качестве характерного фрагмента графа. Помещая этот фрагмент поочередно на каждой из трех пар параллельных граней, получим 3 изоморфных схемы, а поворачивая его в плоскости грани на 90 градусов - удвоим это количество. Поменяв направление дуг на этих участках на противоположное, получим еще одно удвоение, что в результате и даст искомое w = 12.
В соответствии с графом схема № 27550 переходит из состояния в состояние по циклической траектории, что приводит периодическому изменению значений выходов ее элементов (аналогично рассмотренной схеме № 11640), но при этом за время одного цикла значения у изменяться 4 раза, а x и z - только 2.
Некоторые технические аспекты последовательных схем.
Вернемся к схеме № 11640, которая, как уже было сказано может служить генератором импульсов, скважность которых равна двум, т.е. длительности импульса и паузы равны между собой и равны 3t, где t - задержка элемента. Период этих импульсов составляет 6t. Импульсы, одинаковые по форме, имеются на выходах всех трех элементов схемы, причем сдвиг по фазе между ними составляет 60 градусов. Недостатком схемы является наличие двух устойчивых состояний, расположенные на вершинах 0 и 7 координатного куба (назовем их критическими), оказавшись в них она ничего генерировать не будет. Альтернативой является схема № 28025, приведенная на рис. 9 (вместе с № 11640).
В ней из критических состояний есть 1 переход в одно из соседних состояний, принадлежащих циклической траектории, и в каком бы состоянии не находилась схема изначально - она на эту траекторию попадет. Выбранное направление этих новых переходов упрощает логическую функцию соответствующей переменной (в нашем случае х). А если допустить переходы из критических состояний, во все три соседних с ними состояния, то получится простая и достаточно известная схема генератора из трех инверторов, приведенная на рис. 10.
Последняя не является последовательной т.к. в критических состояниях возбуждены выходы более одного элемента, что делает возможным переход из критического состояний в любое другое, в том числе и другое критическое. В последнем случае схема также может генерировать импульсы с той же скважностью, но с периодом 2t.
Если в этом примере описанная ситуация хоть и нарушает правильность работы схемы, но, по крайней мере, сохраняет ее функционал (она остается генератором), то в следующем примере, связанным со схемой № 27550, становится возможным и нарушение функционала. У самой этой схемы описанных проблем нет, т. к. все 8 ее состояний принадлежат одной циклической траектории. На рис. 11 приведена реализация последней на логических элементах типа И-ИЛИ с инверсиями на входах, полученная в соответствии с ее системой.
Если разорвать связь, показанную на рисунке пунктиром, то образуется счетный вход и схема будет функционировать, как счетный триггер. При этом изменение значения на выходе элемента y будет индицировать окончание переходных процессов, вызванных очередным изменением значения на счетном входе.
На практике схемотехническая реализация элементов с прямыми и инверсными входами не встречается, а используются И-НЕ, ИЛИ-НЕ и аналогичные. На рис.12 приведен широко известный вариант схемы счетного триггера с индикатором окончания переходных процессов (для усиления подобия выход индикатора тоже соединен со счетным входом пунктиром).
В этой схеме 7 элементов И-НЕ, следовательно она имеет всего 2**7 = 128 состояний. Однако состояний, в которых она находится функционируя как счетный триггер, всего 12 и они образуют циклическую траекторию, аналогичную таковой у схемы № 27550, только длиннее (там было 8). В каждом из этих двенадцати состояний возбужден выход ровно одного элемента и можно сказать, что схема последовательная относительно этих состояний. Что делается в остальных ста шестнадцати состояниях проверять не будем, кроме двух критических, т.е. таких, в которых значения выходов все элементов равны 0 и 1. В каждом из них возбуждены выходы всех элементов схемы, поскольку значения на их входах совпадают со значениями выходов, что является условием возбуждения для логической функции И-НЕ. Значит кроме всех прочих переходов возможны переходы между этими состояниями, т.е. эта схема, будет в этом случае функционировать не как счетный триггер, а как генератор импульсов с периодом 2t, аналогично кольцу из трех инверторов.
К счастью в технике для предотвращения этого феномена используют начальную установку.