Минимизация числа состояний выполняется в два этапа. На этапе первичной минимизации необходимо найти и объединить в одно все состояния, имеющие одинаковые выходные символы и при переходе вырабатывающие одинаковые состояния. Второй этап минимизации проводится с помощью треугольной таблицы.
ПЕРВИЧНАЯ МИНИМИЗАЦИЯ
Как видно из таблицы 1.3.1 состояния а31, а32, а50, а57 под воздействием α переходят в а0 и вырабатывают 0, следовательно, их можно объединить в одну группу. Рассуждения аналогичны и для остальных состояний.
Обозначим получившиеся состояния буквой "в" и перепишем таблицу переходов-выходов.
в0 = а0
в12 = а12
в24 = а24
в36 = а37
в1 = а1
в13 = а13
в25 = а25
в37 = а38
в2 = а2
в14 = а14
в26 = а26
в38 = а39
в3 = а3
в15 = а15
в27 = а27
в39 = а40
в4 = а4
в16 = а16
в28 = а28
в40 = а41
в5 = а5
в17 = а17
в29 = а29
в41 = а42
в6 = а6
в18 = а18
в30 = а30
в42 = (а43, а44, а47 – а49, а51 – а56, а58)
в7 = а7
в19 = а19
в31 = (а31, а32, а50, а57)
в43 = а45
в8 = а8
в20 = а20
в32 = а33
в44 = а46
в9 = а9
в21 = а21
в33 = а34
в10 = а10
в22 = а22
в34 = а35
в11 = а11
в23 = а23
в35 = а36
Таблица 1.4.1 – Таблица переходов-выходов
α
в0
в1/β
в2/β
–
в1
в3/β
в4/β
–
в2
в5/β
в6/β
–
в3
в7/0
в8/β
–
в4
в9/β
в10/β
–
в5
в11/β
в12/β
–
в6
в13/0
в14/β
–
в7
в15/0
в16/0
–
в8
в17/0
в18/1
–
в9
в19/1
в20/0
–
в10
в21/1
в22/0
–
в11
в23/1
в24/0
–
в12
в25/1
в26/0
–
в13
в27/0
в282/1
–
в14
в29/1
в30/0
–
в15
–
–
в31/0
в16
–
–
в31/0
в17
–
–
в32/0
в18
–
–
в33/1
в19
–
–
в34/1
в20
–
–
в35/0
Таблица 1.4.1 – Продолжение
в21
–
–
в36/1
в22
–
–
в37/1
в23
–
–
в38/1
в24
–
–
в39/0
в25
–
–
в40/1
в26
–
–
в41/1
в27
–
–
в42/0
в28
–
–
в42/1
в29
–
–
в43/0
в30
–
–
в44/1
в31
–
–
в0/0
в32
–
–
в42/0
в33
–
–
в42/1
в34
–
–
в42/1
в35
–
–
в31/1
в36
–
–
в42/1
в37
–
–
в42/0
в38
–
–
в42/1
в39
–
–
в42/1
в40
–
–
в42/0
в41
–
–
в42/1
в42
–
–
в0/1
в43
–
–
в31/0
в44
–
–
в42/0
Как видно таблица 1.4.1 не является окончательной, и минимизацию можно продолжить. Обозначим получившиеся состояния буквой "с" и перепишем таблицу переходов-выходов.
с0 = в0
с12 = в12
с24 = в25
с1 = в1
с13 = в13
с25 = в26
с2 = в2
с14 = в14
с26 = (в27, в32, в36, в37, в40, в44)
с3 = в3
с15 = в15, в16, в43
с27 = (в28, в33, в34, в38, в39, в41)
с4 = в4
с16 = в17
с28 = в29
с5 = в5
с17 = в18
с29 = в30
с6 = в6
с18 = в19
с30 = в31
с7 = в7
с19 = в20
с31 = в35
с8 = в8
с20 = в21
с32 = в42
с9 = в9
с21 = в22
с10 = в10
с22 = в23
с11 = в11
с23 = в24
Таблица 1.4.2 – Таблица переходов-выходов
α
с0
с1/β
с2/β
–
с1
с3/β
с4/β
–
с2
с5/β
с6/β
–
с3
с7/0
с8/β
–
Таблица 1.4.2 – Продолжение
с4
с9/β
с10/β
–
с5
с11/β
с12/β
–
с6
с13/0
с14/β
–
с7
с15/0
с15/0
–
с8
с16/0
с17/1
–
с9
с18/1
с19/0
–
с10
с20/1
с21/0
–
с11
с22/1
с23/0
–
с12
с24/1
с25/0
–
с13
с26/0
с27/1
–
с14
с28/1
с29/0
–
с15
–
–
с30/0
с16
–
–
с26/0
с17
–
–
с27/1
с18
–
–
с27/1
с19
–
–
с31/0
с20
–
–
с26/1
с21
–
–
с26/1
с22
–
–
с27/1
с23
–
–
с27/0
с24
–
–
с26/1
с25
–
–
с27/1
с26
–
–
с32/0
с27
–
–
с32/1
с28
–
–
с15/0
с29
–
–
с26/1
с30
–
–
с0/0
с31
–
–
с30/1
с32
–
–
с0/1
Как видно таблица 1.4.2 не является окончательной, и минимизацию можно продолжить. Обозначим получившиеся состояния буквой "d" и перепишем таблицу переходов-выходов.
d0 = с0
d12 = с12
d24 = с30
d1 = с1
d13 = с13
d25 = с31
d2 = с2
d14 = с14
d26 = с32
d3 = с3
d15 = с15
d4 = с4
d16 = с16
d5 = с5
d17 = с17, с18, с22, с25
d6 = с6
d18 = с19
d7 = с7
d19 = с20, с21, с24, с29
d8 = с8
d20 = с23
d9 = с9
d21 = с26
d10 = с10
d22 = с27
d11 = с11
d23 = с28
Таблица 1.4.3 – Таблица переходов-выходов
α
d0
d1/β
d2/β
–
d1
d3/β
d4/β
–
d2
d5/β
d6/β
–
d3
d7/0
d8/β
–
d4
d9/β
d10/β
–
d5
d11/β
d12/β
–
d6
d13/0
d14/β
–
d7
d15/0
d15/0
–
d8
d16/0
d17/1
–
d9
d17/1
d18/0
–
d10
d19/1
d19/0
–
d11
d17/1
d20/0
–
d12
d19/1
d17/0
–
d13
d21/0
d22/1
–
d14
d23/1
d19/0
–
d15
–
–
d24/0
d16
–
–
d21/0
d17
–
–
d22/1
d18
–
–
d25/0
d19
–
–
d21/1
d20
–
–
d22/0
d21
–
–
d26/0
d22
–
–
d26/1
d23
–
–
d15/0
d24
–
–
d0/0
d25
–
–
d24/1
d26
–
–
d0/1
Как видно таблица 1.4.3 является окончательной на данном этапе минимизации. Теперь можно перйти к следующему этапу – минимизации с помощью треугольной таблицы.
1) строки таблицы обзначаются состояниями d1, d2, …, dn-1, а столбцы d0, d1, …, dn-2, где n – число состояний абстрактного автомата;
2) на пересечении i-той строки и j-того столбца записываются условия, при которых возможно объединение состояний di и dj; если состояния нельзя объединить ни при каких условиях, ставится знак "х"; если они объединяются безусловно, то ставится знак "v"; окончательное объединение состояний определяется на основе непротиворечивости условий.
Выпишем из таблицы пары эквивалентных состояний:
(0, 15)
(1, 15)
(2, 15)
(3, 15)
(4, 15)
(5, 15)
(6, 15)
(7, 15)
(8, 15)
(9, 15)
(0, 16)
(1, 16)
(2, 16)
(3, 16)
(4, 16)
(5, 16)
(6, 16)
(7, 16)
(8, 16)
(9, 16)
(0, 17)
(1, 17)
(2, 17)
(3, 17)
(4, 17)
(5, 17)
(6, 17)
(7, 17)
(8, 17)
(9, 17)
(0, 18)
(1, 18)
(2, 18)
(3, 18)
(4, 18)
(5, 18)
(6, 18)
(7, 18)
(8, 18)
(9, 18)
(0, 19)
(1, 19)
(2, 19)
(3, 19)
(4, 19)
(5, 19)
(6, 19)
(7, 19)
(8, 19)
(9, 19)
(0, 20)
(1, 20)
(2, 20)
(3, 20)
(4, 20)
(5, 20)
(6, 20)
(7, 20)
(8, 20)
(9, 20)
(0, 21)
(1, 21)
(2, 21)
(3, 21)
(4, 21)
(5, 21)
(6, 21)
(7, 21)
(8, 21)
(9, 21)
(0, 22)
(1, 22)
(2, 22)
(3, 22)
(4, 22)
(5, 22)
(6, 22)
(7, 22)
(8, 22)
(9, 22)
(0, 23)
(1, 23)
(2, 23)
(3, 23)
(4, 23)
(5, 23)
(6, 23)
(7, 23)
(8, 23)
(9, 23)
(0, 24)
(1, 24)
(2, 24)
(3, 24)
(4, 24)
(5, 24)
(6, 24)
(7, 24)
(8, 24)
(9, 24)
(0, 25)
(1, 25)
(2, 25)
(3, 25)
(4, 25)
(5, 25)
(6, 25)
(7, 25)
(8, 25)
(9, 25)
(0, 26)
(1, 26)
(2, 26)
(3, 26)
(4, 26)
(5, 26)
(6, 26)
(7, 26)
(8, 26)
(9, 26)
(10, 15)
(11, 15)
(12, 15)
(13, 15)
(14, 15)
(15, 16)
(16, 24)
(17, 22)
(18, 21)
(19, 25)
(10, 16)
(11, 16)
(12, 16)
(13, 16)
(14, 16)
(15, 23)
(17, 26)
(18, 24)
(19, 26)
(10, 17)
(11, 17)
(12, 17)
(13, 17)
(14, 17)
(15, 24)
(10, 18)
(11, 18)
(12, 18)
(13, 18)
(14, 18)
(10, 19)
(11, 19)
(12, 19)
(13, 19)
(14, 19)
(10, 20)
(11, 20)
(12, 20)
(13, 20)
(14 20)
(10, 21)
(11, 21)
(12, 21)
(13, 21)
(14, 21)
(10, 22)
(11, 22)
(12, 22)
(13, 22)
(14, 22)
(10, 23)
(11, 23)
(12, 23)
(13, 23)
(14, 23)
(10, 24)
(11, 24)
(12, 24)
(13, 24)
(14, 24)
(10, 25)
(11, 25)
(12, 25)
(13, 25)
(14, 25)
(10, 26)
(11, 26)
(12, 26)
(13, 26)
(14, 26)
(20, 21)
(21, 24)
(22, 26)
(23, 24)
(25, 26)
(20, 24)
Так как любое di состояние из промежутка от d0 до d14 нельзя объединить ни с каким состоянием dj из этого промежутка (в треугольной таблице на пересечении di и dj стоит знак "x" ), то при любом варианте укрупнения получим число состояний не менее 15. Исходя из этого получим следующие пары эквивалентных состояний, обозначенные буквой "е":
е0 = (0, 15)
е1 = (1, 16)
е2 = (2, 17)
е3 = (3, 18)
е4 = (4, 19)
е5 = (5, 20)
е6 = (6, 21)
е7 = (7, 22)
е8 = (8, 23)
е9 = (9, 24)
е10 = (10, 25)
е11 = (11, 26)
е12 = (12, 15)
е13 = (13, 16)
е14 = (14, 17)
Полученные пары полностью удовлетворяют условиям замкнутости и полноты.
На основе полученных пар получаем таблицу переходов-выходов минимального автомата (таблица 1.4.2.1).
Для устранения критических состязаний в схеме применяют:
1) Генератор тактовых импульсов.
Недостатки: жесткие требования к стабильности длительности импульсов генератора, относительно низкое быстродействие. Достоинства: небольшие аппаратурные затраты.
2) Вспомогательную память.
Недостатки: большие аппаратурные затраты, низкое быстродействие. Достоинства: высокая стабильность работы автомата.
3) Специальное кодирование состояний.
Недостатки: большие аппаратурные затраты, низкое быстродействие. Достоинства: высокая стабильность работы автомата.
Наиболее оптимальным в данном случае является первый способ.
КОДИРОВАНИЕ СОСТОЯНИЙ, ВХОДНЫХ И ВЫХОДНЫХ СИГНАЛОВ
Закодируем состояния (таблица 2.2.1), входные (таблица 2.2.2) и выходные (таблица 2.2.3) сигналы.
Таблица 2.2.1 – Кодированные состояния
Q4
Q3
Q2
Q1
e0
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e11
e12
e13
e14
Таблица 2.2.2 – Кодированные входные сигналы
X2
X1
α
Таблица 2.2.3– Кодированные выходные сигналы
Y2
Y1
α
СОСТАВЛЕНИЕ КОДИРОВАННОЙ ТАБЛИЦЫ ПЕРЕХОДОВ
На основе таблиц 2.2.1, 2.2.2 и 1.4.2.1 построим кодированную таблицу переходов (таблица 2.3.1).