4.3 Аналитический способ

Автомат по каждому выходу задается в виде алгебраического выражения получаемого путем применения логических операций к переменным – символам входов:

Пример. Пусть автомат имеет один выход и три входа. В этом случае возможно задание автомата, например, в виде:

4.4 Координатный способ (в виде карт Карно)

В этом случае автомат по каждому выходу задается в виде таблицы (карта Карно) с числом ячеек 2ⁿ по числу наборов значений переменных. Каждая ячейка (клетка) определяется координатами строки и столбца, соответствующими определенному набору значений логических переменных, которые разбиваются на две группы так, что одна группа определяет координаты строки, а другая – столбца. Значения логической переменной, равные 1, указываются чертой над символом логической переменной. Отсутствие черты или отсутствие символа логической переменной означает, что для всех клеток данной строки или столбца соответствующая логическая переменная имеет значение, равное 0. В клетках тех наборов значений логических переменных, для которых выход автомата равен единице, пишется 1; равен нулю, пишется 0. Если значение выхода не определено, то в соответствующей клетке ставиться знак тильда (~). Например, карта Карно для автомата с двумя входами x₁ и x₂ имеет вид:

Если автомат имеет один выход и три входа x₁, x₂, x₃, то карта Карно имеет вид:

Если автомат имеет один выход и четыре входа x₁, x₂, x₃, x₄, то карта Карно имеет вид:

Если автомат имеет один выход и пять входов x₁, x₂, x₃, x₄, x₅, то карта Карно имеет вид:

Если автомат имеет один выход и шесть входов x₁, x₂, x₃, x₄, x₅, x₆ то карта Карно имеет вид:

Возможно и другое обозначение карт Карно, когда на сторонах карты Карно непосредственно указываются двоичные значения соответствующих входов x₁, x₂, x₃.

Необходимо отметить свойство карт Карно, которое позволяет использовать их для минимизации структуры комбинационных автоматов. Это свойство заключается в том, что для любой клетки карты Карно существует соседняя по строке и столбцу такая, что координаты этой клетки отличаются от координат рассматриваемой клетки значением только одной переменной. Это свойство «соседства» позволяет производить по карте минимизацию функций, отображая процесс склеивания соседних конституентов, соответствующих клеткам карты Карно, путем построения различных объединений соседних клеток.

Примеры карт Карно с различными вариантами объединения клеток в соседние показаны на рисунке 5(а, б, в, г)

Рисунок 5 – Пример карты Карно и объединения соседних клеток

5 Способы задания дискретных автоматов с памятью

Для описания дискретного автомата с памятью, помимо состояний входа X (t) и выхода Z (t), необходимо также знать состояние памяти автомата или его внутреннее состояние S(t). Чтобы задать закон функционирования автомата, необходимо определить, каким образом в зависимости от его внутреннего состояния происходит переработка входной информации в выходную и каким образом происходит изменение его внутреннего состояния.

Поэтому в дискретном автомате с памятью необходимо оперировать с двумя разными функциями: φ и f. Функция φ, называемая функцией переходов, описывает смену внутренних состояний автомата, т. е. изменение содержимого памяти в зависимости от того, что в ней хранилось, и от того, какие изменения входных сигналов имели место. Функция f, называемая функцией выходов, описывает изменение выходных сигналов автомата под воздействием входных сигналов в зависимости от того, что было записано в памяти автомата.

Функциональная модель дискретного автомата с памятью получила название – конечный автомат. Конечный автомат определяется совокупностью пяти объектов: множеством состояний входа {X}, множеством состояний выхода {Z}, множеством внутренних состояний {Y}, функцией переходов φ и функцией выходов f. Принимают, что все множества {X}, {Z} и {Y} – конечны, т. е. число возможных значений для состояний входа, выхода и внутренних состояний конечны (рисунок 6)

Рисунок 6 – Дискретный автомат с памятью

Функционирование автомата, т. е. состояние его входа, выхода и памяти, рассматривается в дискретные моменты времени, определяющие такты работы автомата. Если эти моменты определяются сигналами, поступающими от некоторого независимого источника синхронизации сигналов, то говорят о синхронном автомате.

В асинхронном автомате дискретные моменты времени определяются моментами изменения состояния входа или состояния памяти автомата, а длительность тактов определяется интервалом времени, в течение которого состояние автомата не меняется.

Способ задания автомата зависит от состава объектов, которые его определяют. В случае автомата с памятью – это конечные множества {X},{Y},{Z}, которые задаются простым перечислением их элементов, и функции переходов и выходов, которые являются формализацией словесного описания алгоритма функционирования автомата.

При задании и синхронных, и асинхронных автоматов могут быть использованы одни и те же формы представления функций, описывающих работу автомата. При этом есть свои особенности, которые находят отражение и в способах их задания [2].