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

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




“Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин?”

Немного отвлечёмся от задачи и вспомним то, что мы уже знаем:

• Основные понятия
• Минимизация
• Что такое абстрактный автомат

Итак. Есть 2 способа решить эту задачу:

1. Приходится начать с козы. Крестьянин, перевезши козу, возвращается и берет волка, которого перевозит на другой берег, где его и оставляет, но зато берет и везет обратно на первый берег козу. Здесь он оставляет ее и перевозит к волку капусту. Вслед затем, возвратившись, он перевозит козу, и переправа оканчивается благополучно.
2. Вначале крестьянин опять-таки перевозит козу. Потом можно взять капусту, отвезти ее на другой берег, оставить там и вернуть на первый берег козу. Затем перевезти на другой берег волка, вернуться за козой и снова отвести ее на другой берег. В этом случае количество рейсов (7) точно такое же, как и в первом варианте.

Чтобы перейти от словесных описаний к таблицам, графам и схемам я предлагаю закодировать состояния игры следующим образом:
Выделим четыре двоичных разряда. Каждый разряд отвечает за то какие существа на каком береге реки находятся. Если в этом разряде хранится 1, то существо на первом (исходном) берегу, если 0 – на втором. Для наглядности продемонстрирую это на следующем рисунке:



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

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

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

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

Отметим начальное состояние Сст – с него наша игра будет начинаться и им же оканчиваться. Задумывается, что некая кнопка «СТАРТ» переводит автомат из состояния «0000» в состояние «1111». Обратите внимание на то, что так я кодирую выходные слова, а вот состояния придётся закодировать другим образом. Значит, придётся ввести комбинационную схему, которая будет заниматься формированием выходных слов.
Для управления крестьянином и остальными сущностями понадобятся четыре входных слова:



Итак. Входные и выходные слова названы, состояния обозначены. Граф автомата Мура. Приступим к рисованию:

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

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



Рассуждаем дальше:

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

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



Пока всё нормально.
Теперь надо выбрать, кого везти на второй берег: капусту или волка. Неплохо было бы рассмотреть оба варианта (приведу рисунок частично, чтобы легче воспринималось):



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



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

Теперь вспомним, как строятся таблицы переходов/выходов. Рекомендую открыть вот эту статью и посмотреть, если Вы вдруг забыли, а я просто приведу таблицу:



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

Вторую часть статьи намереваюсь опубликовать 14-15 июня.