Совмещенная таблица переходов и выходов
|
|
а0 |
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
а9 |
а10 |
а11 |
а12 |
а13 |
а14 |
а15 |
а16 |
|
U0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Полученная таблица переходов и выходов позволяет построить схему автомата Мили, который будет работать согласно заданной таблицы соответствия. Основным недостатком этого автомата является наличие в нем семнадцати внутренних состояний. Для того, чтобы создать семнадцать внутренних состояний необходимо в схеме автомата иметь пять элементов памяти, т.к. число внутренних состояний всегда равно 2n, где n – число элементов памяти.
Для сокращения числа элементов памяти в автомате необходимо выполнять минимизацию числа внутренних состояний в таблице 5.1.
Минимизация таблицы переходов и выходов сводится к сокращению числа столбцов путем наложения их друг на друга. Для этого существует два условия: необходимое и достаточное.
Необходимое условие заключается в том, что два столбца могут накладываться друг на друга, если клетки каждой строки будут или пустые, или одна заполнена, а другая пустая, или если обе заполнены, но имеют одинаковые выходные сигналы. Согласно этого условия друг на друга могут накладываться несколько столбцов. Единого варианта объединения столбцов не существует. Важно сократить число столбцов таблицы до минимума и чтобы при этом выполнялись необходимое и достаточное условие.
Достаточное условие заключается в том, чтобы в объединяемых клетках, если они обе заполнены были одинаковые внутренние состояния после их переобозначения.
По необходимому условию произведем объединение столбцов таблицы, переобозначив их буквой в:
Таким образом, число внутренних состояний проектируемого автомата по необходимому условию сократилось с 17-ти до 3-х. Для того чтобы проверить выполнение достаточного условия надо построить таблицу аналогичную первой, только внутренние состояния в ней обозначить буквами в0, в1, в2.
Из таблицы 5.2. следует, что все столбцы, намеченные к объединению по необходимому условию, объединяются и по достаточному условию, т.к. все заполненные клетки, которые объединяются между собой, заполнены одинаковыми внутренними состояниями. В результате объединения столбцов получим минимальную таблицу переходов и выходов (табл. 5.3).
Таблица 5.2.
Таблица переходов и выходов с переобозначенными
внутренними состояниями
|
|
в0 |
в0 |
в0 |
в0 |
в0 |
в1 |
в1 |
в1 |
в1 |
в1 |
в2 |
в2 |
в2 |
в2 |
в2 |
в0 |
в0 |
|
|
а0 |
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
а9 |
а10 |
а11 |
а12 |
а13 |
а14 |
а15 |
а16 |
|
U0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если бы какая-либо группа столбцов, намеченная к объединению по необходимому условию, по достаточному условию не объединилась, то необходимо выполнить новое переобозначение столбцов для их объединения по необходимому условию и вновь проверить выполнение достаточного условия. Таким образом, объединять столбцы можно только после выполнения обоих условий.
Таблица 1.3