Минимизация состояний автомата

Минимизация числа состояний выполняется в два этапа. На этапе первичной минимизации необходимо найти и объединить в одно все состояния, имеющие одинаковые выходные символы и при переходе вырабатывающие одинаковые состояния. Второй этап минимизации проводится с помощью треугольной таблицы.

ПЕРВИЧНАЯ МИНИМИЗАЦИЯ

Как видно из таблицы 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.4.2), руководствуясь следующими правилами:

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.4.2.1 – Таблица переходов-выходов минимального автомата

  α
e0 e1/β e2/β e9/0
e1 e3/β e4/β e6/0
e2 e5/β e6/β e7/1
e3 e7/0 e8/β e10/0
e4 e9/β e10/β e6/1
e5 e11/β e12/β e7/0
e6 e13/0 e14/β e11/0
e7 e0/0 e0/0 e11/1
e8 e1/0 e2/1 e0/0
e9 e2/1 e3/0 e0/0
e10 e4/1 e4/0 e9/1
e11 e2/1 e5/0 e0/1
e12 e4/1 e2/0 e9/0
e13 e6/0 e7/1 e6/0
e14 e8/1 e4/0 e7/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).

Таблица 2.3.1 – Кодированная таблица переходов

Наши рекомендации