Минимизация состояний автомата
Минимизация числа состояний выполняется в два этапа. На этапе первичной минимизации необходимо найти и объединить в одно все состояния, имеющие одинаковые выходные символы и при переходе вырабатывающие одинаковые состояния. Второй этап минимизации проводится с помощью треугольной таблицы.
ПЕРВИЧНАЯ МИНИМИЗАЦИЯ
Как видно из таблицы 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 – Кодированная таблица переходов