Самостоятельное Изучение Схемотехники. Синтез Автоматов На Триггерах. Часть 1

Привет. Продолжая тему самостоятельного изучения схемотехники, предлагаю вашему вниманию статью, связанную с синтезом автоматов на триггерах.

И начинается все так:

«Крестьянину нужно перевезти через реку волка, козу и капусту.

Но лодка такова, что в нее поместится только мужик, а с ним или один волк, или одна коза, или одна капуста.

Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту.

Как мужик перевез свой грузЭ» Давайте немного отвлечемся от задачи и вспомним то, что мы уже знаем:

Так.

Есть 2 пути решения этой проблемы:

Нам придется начать с козла.
Крестьянин, перевезя козу, возвращается и забирает волка, которого переправляет на другой берег, где и оставляет, но он берет и козу и отвозит ее обратно на первый берег.
Здесь он оставляет ее и переносит капусту волку.
Затем, вернувшись, он перевозит козу, и переправа благополучно завершается.
Сначала мужик снова перевозит козу.
Тогда можно взять капусту, отвезти ее на другой берег, оставить там и вернуть козу на первый берег.
Затем перенесите волка на другую сторону, вернитесь за козой и снова отведите ее на другую сторону.
При этом количество пролетов (7) точно такое же, как и в первом варианте.

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

Каждый ранг отвечает за то, какие существа находятся на какой стороне реки.

Если в этой категории хранится 1, то существо находится на первом (исходном) банке, если 0 — на втором.

Для наглядности я продемонстрирую это на следующем рисунке:

Из условий задачи становится ясно, что они не могут быть вместе без присмотра мужика:

Коза и капуста;
Коза и волк.

Это значит, что следующие четыре комбинации проигрышны:

Самостоятельное изучение схемотехники.
</p><p>
Синтез автоматов на триггерах.
</p><p>
Часть 1

Теперь, как мы все помним, нам необходимо перейти от словесного описания к графическому описанию – графику.

Это не должно быть сложно.

Отметим начальное состояние Cst — с него наша игра начнется и закончится.

Считается, что некая кнопка «СТАРТ» переводит машину из состояния «0000» в состояние «1111».

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

Это означает, что нам придется ввести комбинационную схему, которая будет генерировать выходные слова.

Для управления крестьянином и другими сущностями вам понадобятся четыре входных слова:

Так.

Входным и выходным словам присвоены имена, указаны состояния.

Граф автомата Мура.

Начнем рисовать:

Из нулевого состояния игра переводится в исходное положение при поступлении любого слова.
Очевидно, что только тогда, когда мужик первым возьмет козу (а1), игра может продолжаться, иначе (а2, а3, а4) ему придется начинать все сначала.

Отразим эти два факта на графике:

Давайте обсудим дальше:

Если мы теперь введем слова а2 или а3, то ясно, что крестьянин не сможет перевезти волка или капусту, поэтому состояние игры не изменится.
Однако он может забрать козла обратно и игра вернется в исходное состояние.
Это значит, что единственным действием, не заходящим в тупик, будет возвращение мужика в первый берег.

Давайте добавим это к нашему рисунку:

Пока все в порядке.

Теперь нам нужно выбрать, кого взять на второй берег: капусту или волка.

Было бы неплохо рассмотреть оба варианта (приведу частичную картинку, чтобы было легче понять):

То есть понятно, что после этого движения на первом берегу останется либо капуста, либо волк.

Ну вот! Я же говорил тебе, что это не сложно! Если продолжить наши рассуждения в том же духе, то можно прийти к такой простой схеме:

Обратите внимание: когда крестьянин пытается перейти на другую сторону в состояниях 3, 4, 5 и 8, козел остается без присмотра рядом с волком или капустой, что чревато и приводит к концу игры.

Или просто посмотрите таблицу неприемлемых состояний выше.

Если вы попытаетесь подойти к ним, игра закончится.

Теперь давайте вспомним, как строятся таблицы переходов/выходов.

советую открыть здесь этот статью и посмотрите, вдруг вы забыли, а я просто приведу таблицу:

Ну вот. Теперь почти всё готово для синтеза автомата с помощью триггеров.