Нашел замечательную статью “Самостоятельное изучение схемотехники. Синтез автоматов на триггерах. Часть 1” на Хабре. В статье рассматривался интересный пример создания игры «Волк-Коза-Капуста».
Попробую объяснить суть дела.

Задача: На одном берегу реки находятся крестьянин, волк, коза и капуста. У крестьянина есть лодка, но видимо не очень хорошая  Он может взять с собой в плавание только один «предмет», в смысле только козу или только капусту или только волка. Проблема в том, что кое-кого нельзя оставлять наедине с желанной пищей. Например, нельзя уплыть оставив волка и козу на одном берегу – волк съест козу. Или нельзя уплыть с волком, оставив козу и капусту – ведь коза съест капусту. Но крестьянину нужно непременно попасть на другой берег. Вот такой он упертый. И хочет он довезти всех в сохранности.

Вообще-то это довольно известная детская головоломка.

Автор той статьи предлагает использовать «граф автомата Мура» для описания этой системы из волка-козы-капусты и крестьянина. Ну что же – в этом наверное есть какая-то здравая мысль.

Для хранения состояния системы используется четырех-битное слово. По одному биту на каждого: на козу (бит 3), на волка (бит 2), капусту (бит1) и крестьянина (бит 0). Если бит равен единице, то сущность на первом берегу, а если нулю, то на втором.

Кроме этого, в той статье автор определяет четыре «события» по которым система переходит из одного состояния в  другое:
1)    событие А1 – крестьянин везет козу
2)    событие А2 – крестьянин везет волка
3)    событие А3 – крестьянин везет капусту
4)    событие А4 – крестьянин перебирается сам на другой берег

После всех этих определений автором статьи был автором нарисован следующих граф:


Вообще прочитав статью и внимательно изучив этот граф мне немедленно захотелось попробовать реализовать эту игру «в железе». Тем более, что делать мне по большому счету почти ничего не надо – ведь у меня есть плата Марсоход и она очень подходит для этой игры.

Порылся в интернете и нашел несколько картинок коз, капуст, волков и крестьян. Выбрав более подходящие собрал их на одной картинке и напечатал на принтере вот так:

Потом наклеил эту картинку на картонку вырезал по контуру и двумя коротенькими шурупами привинтил плату Марсоход к картонке. Получилось вот так:

Идея в следующем. На плате Марсоход есть 8 светодиодов. Мысленно делим их на две группы. Первые четыре светодиода отображают присутствие сущностей на левом берегу, а правые четыре светодиода отображают присутствие сущностей на правом берегу. Понятно, что правые светодиоды это просто инверсия левых. Так нагляднее будет игра.

Опять же удобство – на плате Марсоход как раз четыре кнопочки – к ним привязываем «события» - перемещения сущностей. Под кнопочкой нарисована картинка обозначающая кого «перевозит» эта кнопка. Ну вот и все! Собственно аппаратура готова! Паять ничего не нужно. У нас есть ПЛИС на плате Марсоход. Осталось все это запрограммировать. Поскольку граф уже был любезно составлен автором той замечательной статьи, то казалось, что запрограмировать будет легко. Вроде бы думать уже не надо.

Вот тут и началось самое интересное. На самом деле есть большая разнича между теоретическими изысканиями и практическая реализацией. Попробую объяснить мои проблемы и проблемки с существующим графом:

• В существующем графе исходное состояние это 0000, что в принятой терминологии обозначает, что все сущности изначально находятся на том правом берегу. Как-то это странно.

• Любое событие А1-А4 перевозит всех сразу на левый берег с правого из состояния 0000 в состояние 1111. Тоже странно.

• Нет явного состояния «выиграл» или «проиграл». На графе проигрыш переводит всех сущностей сразу на правый берег в состояние 0000, что как бы обозначает «выиграл». Ну и как это?

• В статье говорится о четырех проигрышных ситуациях 0011\1100, 1010\0101, на само же деле их шесть. Есть еще две проигрышные ситуации 1110\0001 – это когда крестьянин оставляет все свое хозяйство и плывет сам. Коза съедает капусту, а потом волк козу.

Несмотря на то, что первую версию игры по существующему графу я сделал довольно быстро, как оказалось, пользоваться этим практически нельзя. Игра получилась совсем непонятная.

После некоторых раздумий я пришел к выводу, что нужно изменить граф, сделать его более внятным и четким. Сказать по правде нарисовать новый граф стоило мне ну просто очень больших усилий. Должен признаться, что тут я впервые пожалел, что выбрал этот путь – реализация игры в виде «автомата». Мне все время казалось, что есть другой гораздо более легкий путь сделать эту же игру, но об этом чуть позже.

Теперь про мой "новый" граф автомата Мура. Исходное состояние игры 0000 и это обозначает, что все сущности на первом левом берегу. Единица в бите состояния обозначает, что соответствующая сущность находится на правом берегу. Имеем одно выигрышное состояние 1111 и шесть проигрышных. И сущностей и события именуем в одинаковой последовательности, а не так как было раньше. Тоесть в слове состояния Коза – бит ноль. Событие по перевозке Козы – тоже бит ноль в слове событий (то есть кнопочка ноль).
Вообще, в нашем проекте, который я пишу на языке Verilog примем следующие обозначения битов в слове состояния и в слове событий:

parameter GOAT = 0;
parameter CABBAGE = 1;
parameter WOLF = 2;
parameter MEN = 3;

Вот так выглядит мой граф:


Теперь уже по новому графу пишем на языке Verilog описание логики работы нашего автомата. Полный текст получившейся «программы» можно взять здесь.

Несмотря на то, что проект заработал правильно (с моей точки зрения), все равно осталось какое-то чувство неудовлетворенности. Я еще когда писал весь этот код на Verilog видел, что получается как-то «тяжеловесно».

На самом деле вся логика может быть гораздо проще. Попробую объяснить свою мысль. В данном конкретном примере не нужно ломать голову всеми этими «автоматами». Составление такого графа подразумевает четкое представление какие вообще состояния есть и их трансформации. А собственно говоря зачем все это?

Понятно, что любое событие по перевозке, во-первых, обязательно приводит к перемещению крестьянина на противоположный берег. Тоесть, каждое событие всегда «инвертирует» бит состояния крестьянина. Во-вторых, сущности Коза, Капуста и Волк могут перемещаться только если перед событием они с крестьянином находятся на одном берегу.  Перемещение всех сущностей – это инвертирование их бита состояния. Распознавание «аварийных ситуаций», тоесть проигрышей, это отдельная песня. Проигрыши распознаются отдельной комбинаторной функцией. Вот и все! Как просто!

Вот уже этот новый код я действительно легко написал на Verilog и проверил за 10 минут. Посмотреть его можно здесь - как говорится "почувствуйте разницу".

Конечно нужно показать как работает моя игра . Вот небольшое демонстрационное видео:

Таким образом, мною была 2 раза реализована игра «Волк-Коза-Капуста» в плате Марсоход. Оба проекта Quartus II Вы можете взять здесь на нашем сайте:

1. После компиляции игры с «автоматом» я вижу, что вся логика уместилась в 80-ти логических элементах ПЛИС платы Марсоход.
2. После компиляции игры «без автомата»  - вся логика занимает 49 логических элементов ПЛИС платы Марсоход (тоесть почти в 2 раза меньше, чем в первом случае!)

Кроме того, среда разработки QuartusII может автоматически извлекать из текста «программ» Verilog или VHDL описания state machines, тоесть «автоматов». После компиляции проекта в среде QuartusII заходим в меню Tools\Netlist Viewers\State machine Viewer. Так вот в первом случае Quartus II показывает граф «автомата», примерно вот такой:

Во втором случае QuartusII говорит: «Design has no State Machine». Вот такое чудо – оказывается нет «автомата» в нашем проекте. Ну что же, оставим это на совести среды QuartusII.

Таким образом, сделаем странный вывод – не все «автоматы» одинаково полезны. Иногда бывает гораздо проще и легче сделать проект «в лоб», не ломая голову над графами и состояниями всей системы.