Кодирование состояний синхронного автомата

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

Сложность схемы оценивается числом логических элементов или суммарным числом входов ее логических элементов.

Задача кодирования состоит в присвоение каждому состоянию уникального двоичного кода. Число разрядов этого кода q зависит от числа состояний автомата k и находится в интервале:

┐log₂k┌ ≤ q ≤ k, где ┐p┌ - ближайшее целое не меньшее p.

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

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

Два состояния автомата s’ и s” называются “соседями I рода ”, если под воздействием хотя бы одного и того же входного символа из них осуществляется переход в одно и то же состояние.

Два состояния автомата s_i и s_j называются “соседями II рода”, если в эти состояния осуществляется переход под воздействием хотя бы одного и того же входного символов из состояний, которые являются “соседями I рода”.

Суть способа кодирования состоит в том, что состояния являющиеся соседями I рода и II рода кодируются соседними кодами.

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

Фрагмент графа с состояниями, являющиеся соседями I рода и II рода представлен на рис. 4.18.

s’

si

sk

s”

sj

x

x

соседи II рода

соседи II рода

I рода

соседи I рода

соседи I рода

0 0 0   y1y2y3 1 0 0

0 1 0

0 0 1

0 1 1 состояниям, являющихся соседями I рода

Рис. 4.18.

 

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

Пусть во фрагменте графа (рис. 4.18) состояния s ^’ и s ^”, являющиеся соседями I рода закодированы следующими соседними кодами:
s ^’ - 000 и s ^” – 100, а состояние s_k – 001, тогда если в качестве элемента памяти задан D-триггер, функция возбуждения третьего триггера для перехода из состояний s ^’. и s ^” в состояние s_k:

y ^’ _D3 = x _{1 2 3} V x y_{1 2 3} = x _{2 3}.

Первая конъюнкция определяет переход из состояния s ^’ в состояние s_k, а вторая из состояния s ^” в состояние s_k, устанавливая третий триггер в единицу.

Из этого примера видно, что кодирование соседними кодами состояний, являющихся соседями I рода, позволяет получить в функциях возбуждения, склеивающиеся между собой конъюнкций и за счет этого упростить комбинационную схему.

В этом же фрагменте состояния s_i и s_j, являющиеся соседями II рода закодированы следующими соседними кодами: s_i - 010 и s_j – 011, тогда функции возбуждения второго и третьего триггера:

y ^’ _D2 = _{1 2 3} V y_{1 2 3} = _{2 3};

y ^’ _D3 = x _{2 3} V y_{1 2 3}

Первая конъюнкция функции y ^’ _D2 определяет переход из состояния s ^’ в состояние s_i, а вторая из состояния s ^” в состояние s_j, устанавливая второй триггер в единицу. Вторая конъюнкция функции y ^’ _D3 определяет переход из состояния s ^” в состояние s_j, устанавливая третий триггер в единицу.

Таким образом, кодирование соседними кодами состояний, являющихся соседями II рода, позволяет получить в функциях возбуждения, склеивающиеся между собой конъюнкции, в б льшем числе функций, чем при друг м кодировании.

Обычно не хватает соседних кодов при назначении их соседям I и II рода и поэтому соседние коды надо в первую очередь назначать состояниям, являющихся соседями I рода, а затем назначать соседние коды состояниям, являющихся соседями II рода. Если соседних кодов не хватает уже для соседей I рода, то в первую очередь их надо назначать состояниям, у которых “степень соседства” больше. Под “степенью соседства” понимается количество одинаковых входных символов, по которым осуществляется переход в одно и то же состояние.

Пример кодирования состояний с учетом соседства состояний.

Пусть задана таблица переходов автомата (табл. 4.15).

Определение состояний, являющихся соседями I и II рода кодов удобно осуществлять по инверсной таблице переходов. Эта таблица отличается от известной (прямой) таблицы переходов тем, что в ее клетках указываются состояния, из которых осуществляется переход по входному символу p_j в состояние s_i, которым отмечена строка (табл. 4.16).

Таблица 4.15

 

pi sj
s0	s1	s2
s1	s3	s2
s2	s4	s0
s3	s2	s1
s4	s4	s0

 

Таблица 4.16

 

		pi sj
---	s2, s4	s0
s0	s3	s1
s3	s0, s1	s2
s1	---	s3
s2, s4	---	s4

 

В инверсной таблице переходов состояния, являющиеся соседями I рода, расположены в одной клетке это: s₀, s₁ и s_2, s₄. Состояния, являющиеся соседями II рода, это те состояния в которые существуют переход из состояний, являющиеся соседями I рода, расположенных в одном столбце. В примере это состояния s₁ и s₃, потому что в s₁ существует переход по 0 из состояния s₀, а в s₃ существует переход по 0 из состояния s₁, являющиеся соседями I рода.

Для назначения соседних кодов найденным соседям I рода: s₀, s₁ и
s_2, s₄, а также соседям II рода: s₁ и s₃ удобно использовать таблицу клетки которой закодированы зеркальным кодом Грея, как в карте Карно, но в клетках указываются символы состояний. Состояния, являющихся соседями I и II рода, записываются в соседних клетках этой таблицы (табл. 4.17).

Таблица 4.17

y3

	s2	s4	s0	s1
y1					s3

y2

 

Таблица 4.18

 

si	y1	y2	y3
s0
s1
s2
s3
s4

 

Результат кодирования представлен в кодовой таблице (табл. 4.18).

 

 

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

Этот способ кодирования использует минимальное число элементов памяти и направлен на уменьшение числа переключений элементов памяти при каждом переходе, так как каждое изменения триггера требует включение конъюнкции в функцию возбуждения этого триггера

Расстояние между кодами k_i и k_J по Хэмминингу – это число разрядов, в которых значения соответствующих разрядов не совпадают. Для вычисления этого расстояния используется операция суммирования по модулю два. Пусть k_i = 11001, k_J = 01100 тогда:

ki 11001 kJ 01100

+

 

 

Число единиц в результате сложения по модулю два: d_ij = 3.

Чтобы определить общее число изменения значений элементов памяти надо вычислить сумму расстояний по всем переходам.

Алгоритм кодирования:

1. Определятся множество пар состояний M, между которыми существует переход;

2. Произвольно выбирается из M любая пара состояний s_i и s_j, одно из них s_i кодируется всеми нулями, а другое s_j нулями и одной единицей в самом правом разряде (00…01)

3. закодированные пары состояний удаляются из множества M и если все пары закодированы, то процесс кодирования завершается.

4. Из множества M произвольно выбирается пара, в которой одно состояние уже закодировано, а другое нет. Незакодированное состояние, обозначается s_q.

5. Из множества M выбираются пары, в которые входит состояние s_q. Подмножество таких пар обозначается M_q. Множество уже закодированные состояний из M_q, обозначается B_q;

6. Если B_q = , то переход пункту 4;

7. Для любого состояния из B_q строится множество кодов C^d_q, находящихся на расстоянии d от кода состояния S_q, где вначале d = 1. Если таких, то d увеличивается на 1 и так до тех пор, пока не будет найдено множество кодов находящихся на минимальном расстоянии;

8. Для каждого кода множества C^d_q определяется сумма расстояний по Хеммингу с каждым кодом из B_q Выбирается код, имеющий минимальную сумму и этот код приписывается S_q. Далее переход к пункту 3.

 

Пример кодирования состояний автомата (рис. 4.19):

 

s1

s2

s3

s4

s5

 

Рис. 4.19

 

1) Пары состояний M = {(1,2),(2,5),(2,4),(3,2),(4,3),(4,5),(5,1)}

2) Выбираем {1,2} s₁ = 000, s₂ = 001.

3) M = {(2,4),(2,5), (3,2) (4,3),(4,5),(5,1)}.

4) Выбираем {2,4} s₄, q=4.

5) M₄ = {(2,4),(4,3),(4,5)}, B₄ = {2}.

7) Для кода 001 - C¹₄ = {101,011}.

8) 101 + 001 = 100 d₁₀₁ = 1,

011 + 001 = 010 d₀₁₁ = 1, s₄ = 101.

3) M = { (2,5), (3,2), (4,3),(4,5),(5,1}.

4) Выбираем {2,5} s₅, q=5.

5) M₅ = {(2,5), (4,5), (5,1)}, B₅ = {2,4,1}.

7) Для кода 001 - C¹₅ = {011}.

Для кода 101 - C¹₅ = {(111),(100)}.

Для кода 000 - C¹₅ = {(100),(010)}.

8) 011 + 001 = 010, 011 + 101 = 110, 011 + 000 = 110 d₀₁₁ = 5.

111 + 001 = 110, 111 + 101 = 010, 111 + 000 = 111 d₁₁₁ = 6.

100 + 001 = 101, 100 + 101 = 001, 100 + 000 = 100 d₁₀₀ =4.

010 + 001 = 011, 010 + 101 = 111, 010 + 000 = 010 d₀₁₀ = 6.

Минимум d₁₀₀=4. s₅ = 100.

3) M = {(3,2),(4,3) }.

4) Выбираем {3,2} s₃, q=3.

5) M₃ = {(3,2),(4,3}, B₃ = {2,4}.

Для кода 001 - C¹₃ = {011}.

Для кода 101 - C¹₃ = {111}

8) 011 + 001 = 010, 011 + 101 = 110 d₀₁₁ = 3.

111 + 001 = 110, 111 + 101 = 010 d₁₁₁ = 3, s₃ = 011

3) M = – конец цикла.

Результат: s₁ = 000, s₂ = 001, s₃ = 011, s₄ = 101, s₅ = 100.

 

Универсальный способ кодирования состояний синхронного автомата.

При данном способе кодирования используется унитарный код. Унитарным называется код, который содержит только одну единицу, а остальные нули. Это способ кодирования с максимальным числом разрядов. Число разрядов кода равно числу состояний автомата, т.е. состояние s_i кодируется кодом, содержащим единицу в i – том разряде.

Пусть задан фрагмент графа (рис. 4.20), в котором состояние s₁ кодируется кодом 100, а s₂ – кодом 010. Если в качестве элемента памяти задан D-триггер, то для реализации этого перехода функция возбуждения второго триггера: y ’ _D2 = y_{1 2 3}.

s1

s2

x

y1y2y3

Рис. 4.20

В конъюнкции обеспечивающей этот переход переменные y₂ и y₃ являются несущественными, так как признаком того, что автомат находится в состоянии s₁, является единица в первом разряде, поэтому эту конъюнкцию можно упростить: y ’ _D2 = y₁. Это является достоинством этого способа кодирования, так как позволяет сразу по графу автомата строить функция возбуждения, которые обычно не требуется минимизировать, но иногда можно упростить.

Пример универсального способа кодирования (pис. 4.21):

s1

s2

s4

s3

s5

x

0 1 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 0 0 1

y1y2y3y4y5 1 0 0 0 0

Рис. 4.21

Если в качестве элемента памяти задан D-триггер, то при построении его функций возбуждения необходимо обеспечить его переходы: 0 1 и 1 1, которые могут быть реализованы поступлением единицы на его вход. Например, для реализации первого перехода (pис. 4.21) из состояния: s₁ в состояние s₂, необходимо второй триггер установить в единицу, для этого в функцию возбуждения второго триггера надо включить конъюнкцию, которая имеет значение единицы, когда автомат находится в состояние s₁ и x = 0. Признаком того, что автомат находится в состоянии s₁, является то, что y₁ = 1, поэтому эта конъюнкция имеет вид: y₁. Последовательно просматривая все переходы в графе (pис. 4.21), формируются конъюнкции, которые включаются в соответствующие функции возбуждения:

y ’ _D1 = x y₅ V x y₃;

y ’ _D2 = y₁;

y ’ _D3 = x y₁ V x y₂ V x y₄;

y ’ _D4 = y₂ V y₄;

 

y ’ _D5 = y_3.

 

Под каждой конъюнкцией указан номер перехода в графе (pис. 4.21), который она обеспечивает.

Если в качестве элемента памяти задан RS-триггер, то при построении его функций возбуждения необходимо обеспечить его переходы: 0 1 и 1 0. Переход 0 1 реализуется поступлением единицы на его вход S. Переход 1 0 реализуется поступлением единицы на его вход R. Например, для реализации первого перехода (pис. 4.21) из состояния: s₁ в состояние s₂, необходимо второй триггер установить в единицу, для этого в функцию возбуждения входа S второго триггера надо включить конъюнкцию, которая имеет значение единицы, когда автомат находится в состояние s₁ и x = 0, одновременно необходимо первый триггер сбросить в ноль, для этого в функцию возбуждения входа R первого триггера надо включить ту же самую конъюнкцию. Признаком того, что автомат находится в состоянии s₁, является то, что y₁ = 1, поэтому эта конъюнкция имеет вид: y₁. Последовательно просматривая все переходы в графе (pис. 4.21), формируются конъюнкции, которые включаются в соответствующие функции возбуждения:

 

y ’ _S1 = x y₅ V x y₃;

y ’ _S2 = y₁;

y ’ _S3 = x y₁ V x y₂ V x y₄;

y ’ _S4 = y₂;

y ’ _S5 = y₃;

 

y ’ _R1 = y₁ V x y₁ = y₁;

y ’ _R2 = y₂ V x y₂ = y₂;

y ’ _R3 = x y₃ V y₃;

y ’ _R4 = x y₄;

 

y ’ _R5 = x y₅.