Определение числа элементов памяти и кодирование состояний автомата

Число элементов памяти N автомата Мили определяем по выражению N? ]log₂ M [, где M — число состояний автомата. Отсюда N=]log₂ 10[= 4.

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

1. По графу или таблице переходов автомата составляем матрицу Т, строки которой образуют пары состояний, между которыми возможен переход. Каждой паре состояний автомата ставится в соответствие вес перехода, определяемый в соответствии с выражением.

P (i, j) = q (i, j) + q (j, i),.

где q (i, j) — количество дуг, идущих от iго состояния к jму на графе состояний автомата;

q (j, i) — количество дуг, идущих от jго состояния к iму на графе состояний автомата.

Критерием сложности синтезированной комбинационной схемы автомата будет являться величина.

W = P (i, j)* d (i, j),.

где d (i, j) — кодовое расстояние по Хеммингу, то есть количество символов, которыми отличаются коды состояний i и j.

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

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

3. Состояния первой строки матрицы М кодируем начальными кодовыми комбинациями.

.

4. Для незакодированного состояния второй строки составляем дополнительную матрицу, где обозначено незакодированное состояние второй строки, равное его номеру. В матрицу введём все строчки, содержащие .

.

Множество уже закодированных состояний, содержащихся в матрице, равно .

5. Составляем множество кодовых комбинаций для состояния () с учётом условий соседнего кодирования. Для подбора кодов можно использовать карту Карно.

Составим карту Карно для трёх переменных и запишем закодированные состояния и в соответствии с их кодами в клетки карты Карно.

Так как в переходах, состояния, незакодированны, то для нахождения кода для состояния используется только переход. Отметим звёздочками соседние к уже закодированному состоянию клетки карты Карно, получим:

для к (b₁₀) = 0000 — множество соседних клеток (кодов) .

Для каждой кодовой комбинации из вычисляем .

Таблица 3.

Расчет функции W при выборе кода для состояния b₆

Функция W имеет одинаковое значение для всех кодов, поэтому можно выбрать любой, возьмём по порядку написания код 0010, то есть .

Повторяем пункты 4,5 для того, чтобы закодировать все незакодированные состояния автомата.

Для третьей строки в переходе незакодированно состояние .

.

Множество уже закодированных состояний, содержащихся в матрице, равно .

Таблица 4.

Расчет функции W при выборе кода для состояния b₅

Функция W имеет одинаковое значение для всех кодов, поэтому можно выбрать любой, возьмём по порядку написания код 0011, то есть .

Для четвертой строки в переходе незакодированно состояние .

.

Множество уже закодированных состояний, содержащихся в матрице, равно .

Таблица 5.

Расчет функции W при выборе кода для состояния b₈

Функция W имеет одинаковое значение для всех кодов, поэтому можно выбрать любой, возьмём по порядку написания код 0100, то есть .

Для пятой строки в переходе незакодированно состояние .

.

Множество уже закодированных состояний, содержащихся в матрице, равно .

Таблица 6.

Расчет функции W при выборе кода для состояния b₉

Функция W имеет одинаковое значение для всех кодов, поэтому можно выбрать любой, возьмём по порядку написания код 0110, то есть .

Для шестой строки в переходе незакодированно состояние .

.

Множество уже закодированных состояний, содержащихся в матрице, равно .

Таблица 7.

Расчет функции W при выборе кода для состояния b₇

Функция W имеет минимальное значение W=3 для трех кодов, получим код .

Для двенадцатой строки в переходе незакодированно состояние .

.

Множество уже закодированных состояний, содержащихся в матрице, равно .

Здесь всего одна соседняя клетка, получаем код .

Для тринадцатой строки в переходе незакодированно состояние .

.

Множество уже закодированных состояний, содержащихся в матрице, равно .

Таблица 8.

Расчет функции W при выборе кода для состояния b₄

Функция W имеет минимальное значение W=2, получаем код .

Для пятнадцатой строки в переходе незакодированно состояние .

.

Множество уже закодированных состояний, содержащихся в матрице, равно .

Таблица 9.

Расчет функции W при выборе кода для состояния b₃

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

Таким образом состояния автомата получили следующие коды: