Синтез конечных автоматов

Теперь давайте подытожим сказанное и определим общую последовательность создания представленной на рис. 4.11 синхронной схемы, в основу которой положена диаграмма состояний, показанная на рис. 4.8. Процесс можно разбить на следующие ключевые этапы.

1.Составление диаграммы или таблицы состояний.

2.Определение количества и выбор подходящего типа триггеров.

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

4.Составление таблицы состояний.

5.Составление таблицы истинности для блока комбинаторной логики.

6.Разработка схемы реализации блока комбинаторной логики.

Пример

В качестве еще одного примера конечного автомата со входами и выходами будет рассмотрен торговый автомат, принимающий монеты и выдающий некоторый товар. Для того чтобы упростить изложение, предположим, что этот автомат принимает только монеты достоинством 25 и 10 центов. Автомат принимает монеты до пор, пока не получится сумма в 30 или более центов, после чего выдает товар.

Причем, получив больше 30 центов, автомат сдачи не дает. Пусть опускаемые в автомат монеты представляют две двоичные переменные, x1 и х2. Монете достоинством в 25 центов соответствует значение х1 = 1 (х2 = 0), а монете достоинством в 10 центов — значение х2 = 1 (x1 = 0). Монеты опускаются по одной, так что комбинации x1х2 = 11 быть не может. Пусть двоичная выходная переменная z обозначает выдачу автоматом товара, то есть z = 0, когда товар не выдается, и z = 1 в противном случае При синтезе логической схемы такого автомата первым делом нужно построить диаграмму или составить таблицу состояний. Имеет смысл для каждого из состояний составить словесное описание, чтобы позднее легче было определить, сколько триггеров потребуется для представления нужного количества состояний. Состояния определяют общую сумму денег, опущенных в автомат на данный момент. Поскольку монеты могут опускаться в любом порядке до тех пор, пока их общая сумма не составит или не превысит 30 центов, нам потребуются следующие четыре состояния:

♦ S0 — ничего не опущено (начальное состояние);

♦ S1 — 10 центов;

♦ S2 - 20 центов;

♦ S3 - 25 центов.

Другие состояния не потребуются, поскольку по достижении состояния S2 или S3 любая следующая монета дополнит сумму до необходимого максимума, после чего будет сгенерировано выходное значение z = 1 и автомат вернется в состояние S0, то есть будет готов к следующей операции продажи. Диаграмма состояний, описывающая поведение нашего торгового автомата, приведена на рис. 4.12.

Обратите внимание, что в диаграмме отсутствует входная пара значений x1х2 =11, поскольку опустить в автомат обе монеты одновременно невозможно. Кроме того, как видите, из каждого узла-состояния исходит стрелка, указывающая на него же и обозначенная как 00/0. Эта стрелка говорит о том, что пока в автомат не опущена ни одна монета, он остается в прежнем состоянии.

x1 = 1 — опущена монета в 25 центов; х2 = 1 — опущена монета в 10 центов

z = 1 — выдача товара (получена сумма в 30 или более центов)

Рис. 4.12. Диаграмма состояний торгового автомата

Описанный автомат может иметь всего четыре состояния, для реализации которых достаточно двух триггеров. Обозначим их как у2 и y1 и назначим им следующие значения: S0 = 00, S1 = 01, S2 = 10 и S3 = 11. Результирующая таблица состояний приведена на рис. 4.3. Прочерки в таблице соответствуют комбинации x1х2 = 11, которая на практике невозможна. Эти элементы, являющиеся безразличными значениями, при разработке схемы будут нам очень полезны, о чем узнаете позднее.

Таблица 4.3

Таблица состояний для торгового автомата

Этим завершается первый этап процесса разработки автомата. Составленной нами таблице состояний соответствует таблица истинности (табл. 4.4) - она определяет функцию, которую нам предстоит реализовать в блоке комбинаторной логики. Из таблицы легко вывести следующие выражения:

Y2 = y2 + x2 y1 + x1

Y1 = y1 + (x1 + х2)

z = y2(x1 + х2) + x1y1

Таблица 4.4

Спецификация комбинаторной логики для торгового автомата

Как видите, термы и (x1 + х2) встречаются в приведенных выражениях более одного раза. Это удешевляет реализацию логического блока. Последовательные схемы удобнее всего реализовывать в виде ПМЛ, СПЛУ и программируемых вентильных матриц, поскольку все эти типы схем состоят из триггеров и логических вентилей. Современные средства автоматизированного проектирования позволяют синтезировать последовательные схемы непосредственно на основе спецификаций, составленных в терминах диаграммы состоянии.

В таблице 4.3 для состоянии S2, значения следующих состояний и выходной переменной одинаковы при всех входных комбинациях, в которых происходит изменение состояния. Это означает, что для представления итоговых сумм в 20 и 25 центов двух разных состояний не требуется. Для них достаточно одного общего состояния, поскольку, как только в автомате окажется одна из этих двух сумм, поступление любой следующей монеты приведет к выдаче товара (z = 1) и возврату в состояние S0. Таким образом, состояния S2 и S3 эквивалентны и могут быть заменены одним состоянием. Это означает, что для реализации нашего торгового автомата достаточно трех состояний. Однако для них по-прежнему требуется два триггера. В общем случае, с уменьшением количества состояний обычно уменьшается и количество триггеров, а вся схема упрощается.

Напоследок заметим, что для представления переменных состояния могут применяться и триггеры других типов. Мы использовали триггеры типа D, чтобы предельно упростить задачу. Более гибкие триггеры, и в частности JK, позволяют сократить объем необходимых логических схем. Рассказывая о последовательных схемах, мы опирались на схемы, управляемые тактовым сигналом. Но последовательную схему можно создать и без тактового входа. Такие схемы, называемые асинхронными последовательными схемами, разрабатывать несколько сложнее, чем синхронные последовательные.