- •Введение
- •1. Постановка задачи
- •2. Формальное описание автомата
- •3. Минимизация числа состояний
- •4. Кодирование
- •4.1. Кодирование близкое к соседнему
- •4.2. Кодирование по критерию желательности соседства
- •4.3. Сравнительный анализ результатов кодирования
- •4.4. Кодирование систем канонических уравнений
- •5. Функциональная схема и расчет ее характеристик
- •6. Логическое моделирования на наборах функционального теста
- •В ходе выполнения моделирования работы схемы ошибок в работе автомата не обнаружено.
- •7. Проверка полноты теста и построение дополнительного набора
- •Заключение
- •Библиографический список
4.2. Кодирование по критерию желательности соседства
Для осуществления данного кодирования строится т. наз. матрицы желательности соседства по 3 критериям:
1. По входным переменным: если в таблице переходов соседние по входным наборам элементы содержат состояния Si и Sj, то элемент матрицы увеличивается на единицу.
2. По состоянию перехода: если в таблице переходов при одном входном наборе в состояниях Si и Sj следующее состояние одно и то же, то элемент матрицы увеличивается на единицу.
3. По выходным переменным: если выходные наборы в состояниях Si и Sj имеют r одинаковых компонент, то элемент увеличивается на r/k, где k - число внутренних переменных, k=,n- число состояний.
Кодирование состояний на основе матриц степени желательности соседства состоит в том, что состояния, имеющие наибольшее значение размещаются на соседних элементах булева пространства (кодируются соседними кодами). Затем к уже размещённым состояниям подбирается очередное новое, исходя из наибольшей суммарной степени желательности соседства.
Кодирование выполняется в два этапа:
Размещение на матричной форме n-переменных в соответствии с матрицей.
Вращение булева пространства с тем, чтобы наиболее часто встречающийся код был закодирован набором «000».
Построим матрицы желательности соседства для автомата:
А. По входным переменным:
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
|
|
|
|| |
||| |
|
| |
S0 |
|
| |
|
||| |
|
|
S1 |
|
|
| |
|| |
|
|
S2 |
|
|
|
| |
|
|
S3 |
|
|
|
|
||| |
|| |
S4 |
|
|
|
|
|
| |
S5 |
B. По состоянию перехода:
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
|
| |
| |
|
|| |
| |
| |
S0 |
|
| |
|
| |
| |
|| |
S1 |
|
|
|
| |
|| |
| |
S2 |
|
|
|
|
|
| |
S3 |
|
|
|
|
| |
| |
S4 |
|
|
|
|
|
| |
S5 |
C. По выходным переменным:
k = = 3, r = 2
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
|
2/3 |
2/3 |
1/3 |
1/3 |
1/3 |
1/3 |
S0 |
|
2/3 |
1/3 |
1/3 |
1/3 |
1/3 |
S1 |
|
|
1/3 |
1/3 |
1/3 |
1/3 |
S2 |
|
|
|
|
|
|
S3 |
|
|
|
|
2/3 |
2/3 |
S4 |
|
|
|
|
|
2/3 |
S5 |
D. Матрица критерия желательности соседства:
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
|
1⅔ |
1⅔ |
2⅓ |
5⅓ |
1⅓ |
2⅓ |
S0 |
|
2⅔ |
⅓ |
4⅓ |
1⅓ |
2⅓ |
S1 |
|
|
1⅓ |
3⅓ |
2⅓ |
1⅓ |
S2 |
|
|
|
1 |
|
1 |
S3 |
|
|
|
|
4⅔ |
3⅔ |
S4 |
|
|
|
|
|
2⅔ |
S5 |
Выбираем максимальный элемент в матрице D и в матрице кодирования состояний обеспечиваем соседство состояний, соответствующих данному элементу. Затем в ТПиВ автомата находим рассматриваемую пару состояний и также обеспечиваем соседство состояний. Найдя таковую пару, прибавляем единицу к соответствующему элементу суммарной матрицы требований.
В соответствии с полученной матрицей кодируем состояния по матрице критерия желательности соседства:
Таблица 4.2.1 – Таблица кодирования
|
y1 |
y2 |
y3 |
S0 |
1 |
0 |
0 |
S1 |
1 |
0 |
1 |
S2 |
1 |
1 |
0 |
S3 |
0 |
1 |
1 |
S4 |
0 |
0 |
0 |
S5 |
0 |
0 |
1 |
S6 |
0 |
1 |
0 |
S4 S0 S2 S6 S3 X S1 S5
Рисунок 4.2.2 – Кодированная таблица переходов и выходов
Рисунок 4.2.3 – Выходные функции y1, y2
Z3
Рисунок 4.2.4 – Матрицы представления функций z1, z2, z3
Z1 = входов
Z2 = входов
Z3 = входов
Y1 = входа
Y2 = входа
Суммарное число входов: 18 + 16 + 15 + 2 + 4 = 55.