4.5. Кодирование внутренних состояний автомата
4.5.1. Составление внешнего π-разбиения
Выполним кодирование по внешнему разбиению (приравняв значения переменных кодирования р1 и р2 к значениям Ув и Ун. Получим разбиение следующего вида.
Определим пересечение полученных разбиений.
(
)
∙ (
)=
.
4.5.2. Составление внутреннего π-разбиения на основе множеств порядка единица
Запишем множества порядка единица:
0 – 0,1,2,3,4,5,6,7,8,9
1 – 0,1
2 – 1,2
3 – 2,3
4 – 3,4
5 – 4,5,6
6 – 5,6
7 – 5,7
8 – 7,8
9 – 8,9
Запишем объединённые наборы:
0,5 – по 3 состояниям;
0,1 0,2 0,3 0,4 0,6 0,7 0,8 0,9 5,6 – по 2 состояниям;
Таблица 11
Коды состояний
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
|
2 |
1 |
0 |
0 |
0 |
|
3 |
0 |
0 |
1 |
0 |
|
4 |
0 |
1 |
1 |
0 |
|
5 |
0 |
0 |
1 |
1 |
|
6 |
1 |
0 |
1 |
1 |
|
7 |
0 |
1 |
1 |
1 |
|
8 |
1 |
0 |
0 |
1 |
|
9 |
0 |
0 |
0 |
1 |
4.5.4. Построение автоматного графа для проверки возможности возникновения и устранения критических состязаний элементов памяти
Из автоматного графа видно, что состояния элементов памяти возникают на следующих кодах:
|
Переход |
Переключение кода |
Наборы |
|
1 – 2 |
0100 – 1000 |
А5 |
|
2 – 3 |
1000 – 0010
|
А3 |
|
4 – 0 |
0110 – 0000 |
А11,А12,А13 |
|
4 – 5 |
0110 – 0011 |
А5 |
|
5 – 0 |
0011 – 0000 |
А8,А10 |
|
6 – 0 |
1011 – 0000 |
А9,А12,А13 |
|
7 – 0 |
0111 – 0000 |
А8,А11,А12,А13 |
|
7 – 8 |
0111 – 1001 |
А6 |
|
8 – 0 |
1001 – 0000 |
А7,А8,А13 |
Рисунок 9. Граф состояний и переходов
Устранение критических состязаний
Для исправления критических состязаний элементов памяти вместо заданного перехода через другое неустойчивое состояние с последовательной сменой кодов. Если такие переходы выполнить невозможно, то вводят дополнительные состояния с неиспользуемым кодом и выполняют переходы через них. Если все коды использованы, вводят дополнительную переменную кодирования.
|
Новые переходы |
Переключение кода |
|
1 – 0 – 2 |
0100 – 0000 – 1000 |
|
2 – 10 – 3 |
1000 – 01010 – 0010
|
|
4 – 1 – 0 |
0110 – 0100 – 0000 |
|
4 – 3 – 5 |
0110 – 0010 – 0011 |
|
5 – 9 – 0 |
0011 – 0001 – 0000 |
|
6 – 5 – 9 – 0 |
1011 – 0011 – 0001 – 0000 |
|
7 – 5 –9 – 0 |
0111 – 0011 – 0001 – 0000 |
|
7 – 5 – 9 – 8 |
0111 – 0011 – 0001 – 1001 |
|
8 – 9 – 0 |
1001 – 0001 – 0000 |
Строим исправленный автоматный граф (рис.10).
Рисунок 10. Исправленный граф состояний и переходов