Борис Цирлин

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

Введение

Эта статья, если честно, инициирована полемикой, открытой в комментариях к моим статьям: Полумодулярные, Изоморфные и Дистрибутивные схемы ч. 1 и ч. 2. Автора укоряли тем, что свойства схемы рассматривались применительно ко всем ее состояниям, тогда как общепринятым является учет только, так называемых, "рабочих" состояний, т.е. такое их множество, которое схема не может покинуть в процессе функционирования. Ее поведение в остальных (нерабочих) состояниях безразлично (don't care) и логические функции элементов схемы для этих состояний считаются неопределенными. Естественно, при физической реализации их доопределяют, причем на практике используют такое их определение, чтобы реализация была минимальной. В упомянутых статьях автор предпочитает определить нерабочие состояния так, чтобы они не нарушали принадлежность схемы тому же классу, что и рабочие. Можно, конечно, оправдывать такой выбор тем, что это "улучшает" качество реализации, но на самом деле этот способ открывает возможность подсчета схем того или иного класса. Собственно этому процессу и были посвящены упомянутые статьи.

Как бы то ни было, в схеме реально построенной из n элементов, их логические функции
определены для всех G = 2**n состояний схемы.

На примере простейшего трехэлементного генератора покажем как то или иное определение нерабочих состояний порождает функционально равнозначные схемы с различными структурными свойствами.

Постановка задачи

Взяв за основу известную схему генератора на трех инверторах рис. 1, обсудим ее изоморфизмы, а затем применив все возможные переопределения нерабочих состояний этой схемы определим мощности семейств изоморфных и для них. Таким образом будет определен ее вклад в общий счет схем, полученный в упомянутых статьях. Как и в последних поведение схемы задается вектором Q возбуждения - последовательностью из G чисел, в которой каждая компонента Q[i] может иметь одно из G возможных значений (0=<Q[i]<G), соответствующих номерам элементов с возбуждёнными выходами или их суммам, если возбуждений несколько. Как и раньше, будем обозначать номера элементов схемы степенями двойки - от 1=2**0, до 2**(n-1), а нулем - отсутствие возбуждения в данном состоянии.

Напомним, что элемент считается возбужденным, если значение его выхода не равно значению логической функции для элемента в этом состоянии схемы. Имеется однозначное соответствие между номером I схемы и ее вектором Q возбуждения в соответствии с формулой:

I = sum(Q[i]*(G**i))

Кроме того, поведение схемы иллюстрируется графом переходов. На рис.1 граф переходов приведенной схемы для наглядности (как в известном анекдоте) натянут на координатный куб.

Структурный анализ простейшего генератора

Используя методы, описанные в одной из упомянутых статей, для схемы рис.1 получили ее
семейство изоморфных: мощность которого V = 8. При этом три инвертора содержит, кроме
исходной (№ 15770727), еще только одна схема № 15340311. Для этих двух характерны
противоположные направления обхода цикла рабочих состояний - далее просто цикла.

Остальные схемы этого семейства содержат инвертор и пару задержек, как показано на рис.2.

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

Достоинством этих схем является их минимализм, а "недостатком" - можно считать нарушение полумодулярности в нерабочих состояниях. Конечно, что в процессе работы в нерабочих состояниях схема оказаться не может, но вот при включении питания в начале работы это не исключено. В результате теоретически схема может поддерживать колебания между двумя нерабочими минуя рабочие.

Переопределения нерабочих состояний генератора

Для простоты будем считать, что нерабочими являются состояниями № 0 и № 7 - остальные варианты учитываются автоматически при программном поиске семейства изоморфных схем. Значение компонент Q[0] и Q[7] вектора возбуждений и определяет поведение генератора в нерабочих состояниях. Для n = 3 имеются 8 возможных значений этой компоненты от 0 до 7, т.е. возможно 64 варианта. На самом деле такие определения схемы путем подстановок различных значений Q[0] и Q[7] дают всего 14 семейств изоморфных, одно из которых для

Q[0] = Q[7] = 7

уже было описано. Для рассмотрения остальных разделим их на группы, обладающие общими свойствами, что облегчит понимание и позволит ничего не упустить.

Тупиковые нерабочие состояния

Как было справедливо указано в комментарии к одной из предыдущих статей, определение,
превращающее нерабочие состояния в тупиковые, приносит скорее не пользу, а вред: попав в них эта схема не имеет шансов из него выбраться!

Первым выберем "антипод" традиционного генератора рис.1, а именно схему, в которой
оба нерабочих состояния тупиковые, т.е.

Q[0] = Q[7] = 0

Схем генератора, удовлетворяющих этому условию 2 (соответственно направлениям обхода цикла) - № 1090656 и № 660240, а семейство изоморфных имеет, как и в предыдущем случае,
мощность V = 8. Эти схемы последовательные, но указанный недостаток сводит на нет это
"достоинство".

Следующее определение - компромисс между двумя рассмотренными:

Q[0] = 0, Q[7] = 7

Номера таких схем № 15770720 и № 15340304, и они (схемы), кстати, не полумодулярны, а их семейство изоморфных имеет мощность V = 16.

То же можно сказать и о схемах, полученные определением Q[0] и Q[7] вида:

Q[0] = 0, Q[7] = 3.

Номер одной из таких схем № 7382112, а семейство изоморфных, максимально возможное для n =3, имеет мощность V = 48. Заметим, что схемы полученные при Q[7] = 5 или 6 содержаться в этом семействе.

И последняя в этой группе определение:

Q[0] = 0, Q[7] = 1

Соответствующие схемы № 3187808 и № 2757392 образуют семейство изоморфных:
мощностью V = 48, включающие схемы с Q[7] = 2 и 4. Заметим, что последний вариант дает
последовательные схемы, но в данном случае это сомнительное достоинство.

Последовательные генераторы без тупиков

Обратимся к таким определениям нерабочих состояний, которое не делает их тупиковыми и при этом схема будет последовательной относительно всех своих состояний. Во-первых это

Q[0] = Q[7] = 1,

дающее схему № 3187809 (или № 2757392 при другом направлении обхода цикла) и семейство изоморфных мощностью V = 24, в которое входят схемы полученные и при Q[0] = Q[7] = 2 или 4. А во вторых:

Q[0] = 1, Q[7] = 2,

что дает схему № 5284961 ( или № 4854545 при обратном обходе цикла) и семейство изоморфных мощностью V = 48, куда входят и все другие схемы имеющие по одному возбужденному элементу в нерабочих состояниях такие, что Q[0] != Q[7].

Не полумодулярные генераторы без тупиков

Закрепив значение

Q[7] = 7

будем варьировать Q[0], получив для

Q[0] = 1

схему № 15770721 (№ 15340305) и семейство изоморфных мощностью V = 48, а для

Q[0] = 3

схему № 15770723 (№ 15340307) и семейство изоморфных той же мощности V = 48.Теперь, зафиксировав

Q[0] = 3,

положим

Q[7] = 3,

получив схему № 7382113 (№ 6951699) с семейством изоморфных мощностью V = 48, куда
входят и схемы со значениями Q[0] = 5, Q[7] = 7, а затем:

Q[7] = 5

со схемой № 11576419 (№ 11146003) и семейством изоморфных мощностью V = 48, куда входят схемы со значениями Q[0] = 3, Q[7] = 6 и Q[0]=5, Q[7] = 6.

Из нерассмотренных остались два варианта:

Q[0] = 1, Q[7] = 3,

дающий схему № 7382113 (№ 6951697) с семейством изоморфных мощностью V = 48
(куда входит и вариант Q[0] = 1, Q[7] = 5) и

Q[0] = 1, Q[7] = 6

со схемой № 13673569 (№ 13243153) и семейством изоморфных мощностью V = 48.

Если посчитать сумму мощностей всех упомянутых семейств изоморфных, то получим, что все варианты переопределения всего лишь двух нерабочих состояний охватывают 488 схем. При этом надо понимать, что в каждом таком семействе учитываются не только те значения Q[0] и Q[7], что обозначены, как образующие, но и аналогичные им. Например, в семействе
порождённом

Q[0] = Q[7] = 1,

имеются схемы, где значение для этой пары 2 или 4. Но следует подчеркнуть, что все это не вновь созданные схемы, а только те, подсчетом которых занимались в упомянутых статьях /

Целью этих определений схем генератора был поиск такой (из ранее подсчитанных!) поведение которой в нерабочих состояниях не может нарушить принцип ее функционирования.

Вот почему отвергаются схемы с тупиковыми нерабочими состояниями и подвергается сомнению традиционная реализация рис.1 или 2, в которой в принципе возможно колебание между двумя нерабочими состояниями, без захода в цикл.

Заключение

Собственно из-за двух вариантов последовательных схем и ломались все копья - получилась, как бы, схема с автоматической начальной установкой. Системы логических уравнений для этих генераторов имеют вид:

№ 3187809
x = ~z
y = Or(And(~x, y), And(~x, z), And(y, z))
z = Or(And(~y, z), And(x, z), And(x, ~y))

№ 5284961
x = Or(~z, And(x, y))
y = Or(And(~x, z), And(~x, y))
z = Or(And(~y, z), And(x, z), And(x, ~y))

Графы переходов для этих схем приведены на рис 3.

А надо ли за такую роскошь платить некоторой схемной избыточностью по сравнению с минимальным вариантом (рис.1 или 2) решать разработчику, помня при этом, что бесплатный сыр бывает только в мышеловке.

С другой стороны, если отказаться от универсального свойства полумодулярности (что автору всю жизнь разрабатывавшему только такие схемы было не легко), то получим ту же автоматическую начальную установку, за гораздо более скромную цену:

№ 15770723
x = ~z
y = ~x
z = Or(And(~y, z), And(x, ~y))

А его изоморфная схема кажется еще проще:

№ 8889740
x = Or(And(y, z), And(x, y))
y = z
z = ~x

Графы переходов для этих схем приведены на рис 4.

Вся особенность их функционирования заключается лишь в том, что переход из нерабочего состояния в цикл может произойти не в один шаг, как в предыдущем случае, а в два и при этом состояние одного из возбужденных элементов может стать устойчивым не поменяв своего значения. Но, как показывает опыт, ничего необратимо страшного это нарушение полумодулярности не вызовет и далее схема будет функционировать, как и прототип рис.1. после начальной установки. Вот и подумаешь, а везде ли нужна эта полумодулярность (дистрибутивность, последовательность)?