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

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




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

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


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

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

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



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

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

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

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



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

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



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

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



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



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



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

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



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

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

    Средняя зарплата в IT

    120 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 9 172 анкет, за 1-ое пол. 2021 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 33

      0
      хорошо написано, доступно очень.
        0
        Молодец. Хорошая работа. Интересный пример.
          0
          Спасибо за статью мне будет полезно. В каком редакторе рисовали графы?
            +2
            1) взял в универе MS Office Visio по программе MSDN AA;
            2) воспользовался.
            Удачи :-)
              0
              Спасибо +)
                –2

                3) ??????
                4) PROFIT!

                fixed for teh great justice!
              +1
              Спасибо. Автор молодец, отлично описал. Продолжай в том же духе :)
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Не совсем так. Посмотрите первую таблицу.
                  Я планирую оформить это как игрушку. так вот, может это и не совсем логично, но состояние Сст это такое состояние из которого игра перейдёт в «стартовое», когда все звери окажуться на первом береге. то есть Сст это не начальное состояние игры, а начальное состояние игрушки.
                  Ну вот как-то так…
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      согласен. получается, что "(а2, а3, а4) придётся начать всё с начала" и все на втором берегу 1111. Странно это.
                        0
                        sorry, второй берег 0000
                  +6
                  Как-то не к добру картинка козы в статье о схемотехнике. Выражение «коза пришла» больно отзывается в памяти.
                  Капитан напоминает: коза = короткое замыкание
                    +1
                    я тоже когода прочитал заголовок статьи и посмотрел на картинку сразу подмал о коротком замыкании. И подумал:«каким образом конечные автоматы имею отношение к коротким замыканиям? может алгоритм вычесления КЗ в дочерной сети на конечных автоматах ?»
                      +2
                      Зато появился повод залезть в топик. Коза оправдала свою цель — привлекла ваше внимание.
                        0
                        Тогда туда надо поставить фото "Психолога". Все читали бы этот топик :)
                      0
                      а мне картинка понравилась, хорошенькое животное
                      0
                      Вместо козы лучше бы девушку) Хотя может быть когнитивный диссонанс рулит…
                        +5
                        Красную шапочку, пироги и волка? :)
                        +1
                        Забегая вперед на чем это написано будет в итоге VHDL?
                          0
                          Схему для моделирования собирать хотел ручками — не такая она уж и большая
                          А собирать есть 2 варианта:
                          1) Собирать на россыпи ИМС
                          2) Прошивать на ПЛИС
                          1) хорошо тем, что можно будет познакомиться с базой самих микросхем
                          2) будет просто выглядеть, но возникнут накладные расходы на сборку программатора
                          Непосредственно до реализации есть еще несколько недель…
                            0
                            ИМС это так сказать из деталей собрать?
                            ПЛИС же наверно VHDL-ем програмиться?
                              0
                              1) Да, собрать из деталей, отдельных микросхем.
                              2) Второй пункт — ПЛИС. Да его надо программировать VHDL или Verilog, обширными знаниями в которых я похвастаться не могу — должен это признать…
                              Поэтому как наиболее реальный для себя рассматривал первый вариант — про это я смогу рассказать. А вот с ПЛИС ковыряться надо.
                                +1
                                Вам не обязательно использовать язык высокого уровня для программирования ПЛИС. Любая среда разработки позволяет оформлять модуль в виде схемы. Те же регистры, счетчики, етц. Из плюсов — возможность прогона в эмуляторе и готовая схемотехника, если конечно демоплата имеется. А если нет, то паяется на коленке.
                          0
                          Спасибо, интересно. Только, как мне кажется, ввод Сст и кодирование единицей стартового берега а нулём — конечного только приносит путаницы.
                            0
                            Аж подумал — может вспомнить заново схемотехнику! :)
                              0
                              Ай маладца, как излагает.
                                +1
                                Ну вот почему на нашей теории автоматов нам не давали таких примеров)
                                  0
                                  Нам тоже не давали… Чуть-чуть фантазии и охохо! Честно говоря, самому понравилось. :-)
                                  0
                                  У меня в детстве — была такая

                                  Детская вычислительная машина ,
                                  которая как раз такое и позволяла делать и считать.
                                    +1
                                    статья красиво оформлена и приятная для чтения. но по-моему, незнающему человеку она будет непонятна, а знающему не интерестна. не сочтите за грубость, но надо решить на какой уровень вы хотите ориентироваться… в таком виде она не разьясняет природу задачи, для начинающих. статья действительно позезна но не наглядна. мозможно видео или пошаговые слайды для графов внесут ясность в основную часть статьи. спасибо
                                      0
                                      Спасибо за отзыв. :-)
                                      Ориентироваться хотел на всех — тех, кто знает, для закрепления и тех, кто хочет узнать. Поэтому получается то слишком разжёвано, то недостаточно полно.
                                      Скоро я соберусь и доделаю продолжение (понимаю, что обещал раньше, но ...). По Вашему пожеланию, добавлю туда слайд-шоу или видео с дополнительными комментариями.
                                        0
                                        отлично! теперь буду ждать продолжения ;)

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

                                    Самое читаемое