Reklama

Граф Мили

Электронные цифровые схемы формально можно разделить на 2 класса:

Комбинационные Схемы (КС)не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.

Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.

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

 Абстрактный автомат

Автомат должен будет реализовывать некоторые функции, которые заданы разработчиком. Он может быть простым сумматором, может реализовывать какую-либо микрокоманду процессора, выбирать слова из оперативной памяти или заниматься синтаксическим анализом выражения.

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

8af18afaeb1e39dd043e057fec2c3858

Или, если перейти от иллюстрации к математическому описанию:

A = <A, B, C, δ, λ>

Обозначения:

Множество {A} – представляет собой множество значений на физических входах автомата. На входе в нашем случае будет какая-то последовательность высоких и низких уровней напряжения, которые будут кодировать логические нули и единицы.

Множество {B} – представляет собой множество значений на физических выходах автомата.

Множество {C} – а множество, которое представляет внутреннее состояние автомата – память. На будущее C0 будем обозначать начальное состояние автомата.

δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.

λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.

δ и λ не показаны на схеме для визуального упрощения.

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

Итак мы в общем виде описали что есть Абстрактный автомат. Примером такого автомата может быть триггер, регистр ЭВМ или сумматор.

Выделяют 2 типа автоматов:

Автоматы Мили. Описывается системой уравнений:

c(t) = δ( a(t), c(t-1) );

b(t) = λ( a(t), c(t-1) ).

Автоматы Мура. Описывается уравнениями:

c(t) = δ( a(t), c(t-1) );

b(t) = λ( a(t), c(t) ).

Как видно состояние автомата c(t) в текущий момент времени является функцией его состояния в предыдущий момент времени и входного сигнала.

Отличаются автоматы видом функции выхода. В автомате Мили выходной сигнал определяется входным сигналом a(t) и состоянием автомата в предыдущий момент времени c(t-1). Выходной сигнал автомата Мура определяется парой входного сигнала a(t) и состояния в данный момент c(t).

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

Итак, на этом с матчастью окончено. Попробуем описать автоматы.

Т.е. автомат типа Мили вырабатывает выходной сигнал когда у него меняется входной, в зависимости от его предыдущего состояния. При этом длительность выходного сигнала не зависит от длительности входного, а только от его присутствия. В автоматах типа Мура выходной сигнал зависит от состояния автомата в текущий момент времени т.е. автомат будет вырабатывать определенный выходной сигнал пока не изменит свое состояние.

Способы задания автоматов

Как мы выяснили в первой части — автомат представляет собой совокупность входного и выходного алфавитов, множества внутренних состояний и функций, определяющих переходы и выходы. Однако, обычно функции δ и λ не заданы, и поведение автомата приходится описывать по-другому.

Есть два основных способа задания автомата:

  1. При помощи графов.
  2. При помощи таблиц переходов и выходов.

Графы

Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.

0b55ea44876b4e5e9e6b6d6d47a397b7

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

66b8c4bf26c20d0bb9882ac0c5dd8cd2

Для графа автомата Мура на дугах записываются только входные буквы, выходные же указываются около вершин.

Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным. Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат Мили является полным, а автомат Мура – частичным.

И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным. Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат.

На этом о графах всё.

Таблицы переходов и выходов.

Графы нагляднее для человека, а таблицы — для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.

Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.

ТПВ графа Мили

 59b9496f0bf8d52002355654c8e5d677

В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3.

ТПВ графа Мура

a1a55ff3083c16a84b60b515462774ca

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

В клетке под входной буквой пишется в какое состояние автомат переходит, в крайней правой клетке — какую выходную букву возвращает.

Пример синтеза автомата

При помощи абстрактных автоматов можно описать практически что угодно. Можно описать работу цифровой схемы, а можно – синтаксический или лексический анализатор. Попробуем описать триггер – чем не автомат?

Чтобы задать граф нужно словесное описание алгоритма работы триггера. Читаем:

Кодируем входной и выходной алфавиты:

A = {a0, a1}, где a0 – логическая 1 на входе R, a1 – логическая единица на входе S.

B = {b0, b1}, где b0 – логический 0 на выходе Q, b1 – логическая единица на выходе Q.

Строим граф автомата Мили:

868d610816eb300b45c08ea6c3fc86fc

Вот такая забавная чебурашка получилась :-). Теперь можно построить таблицу переходов и выходов:

66e4c76b97f8ad799d88dbb83062f8f5

Если расписать эту таблицу преобразовав условные обозначения в фактические, то получим таблицу которая представляет из себя таблицу переходов триггера. Затем её можно упростить:

ec083ca188ce021c0767bc9d15301808

Нанесём полученную функцию на карту Вейча и минимизируем:

fc8dd7c579e7c262fb6d03ce641a2be1

Выпишем, что получилось:

a5038d0813ae458793f442e79f3998b9

Строим по функции схему:

4b37f27aa734f4877fcf199fcaa8dab5

Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём:

2afa36b9cc864c24a35ad3269a93e801

 

3f535178a04733c56a7e4478dff34928

А на схеме асинхронный RS триггер обозначается вот так:

82b8afa14e9aad213f64ceb9fd3e6e9e

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

Reklama