МИНИМИЗАЦИЯ СОСТОЯНИЙ АВТОМАТА

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

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

Как видно из таблицы 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 – Кодированная таблица переходов

 

Входные сигналы	Состояние в момент времени t	Состояние в момент времени t+1
X2	X1	Q4	Q3	Q2	Q1	Q4	Q3	Q2	Q1