Синтез комбінаційної схеми
1. Синтез комбінаційної схеми
.1 Визначення значень БФ
Булева функція 5 змінних F(x1,x2,x3,x4,x5) задається своїми
значеннями, які визначаються 7-разрядовими двійковими еквівалентами чисел: по
значенню чисел А (на наборах 0-6), В (на наборах 7-13), С (набори 14-20), по
значенню (А+В+С) (набори 21-27) і на наборах 28-31 функції приймає невизначені
значення.
А= 1011000;
В= X101000;
С= XXXXXXX;
(А+В+С) = XX11001;
Відповідно, значення функцій F(x1,x2,x3,x4,x5) на наборах від
0 до 31 буде мати вигляд:
Таблиця 1
Х1
|
Х2
|
Х3
|
Х4
|
Х5
|
F
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
X
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
X
|
0
|
1
|
1
|
1
|
1
|
X
|
1
|
0
|
0
|
0
|
0
|
X
|
1
|
0
|
0
|
0
|
1
|
X
|
1
|
0
|
0
|
1
|
0
|
X
|
1
|
0
|
0
|
1
|
1
|
X
|
1
|
0
|
1
|
0
|
0
|
X
|
1
|
0
|
1
|
0
|
1
|
X
|
1
|
0
|
1
|
1
|
0
|
X
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
X
|
1
|
1
|
1
|
0
|
1
|
Х
|
1
|
1
|
1
|
1
|
0
|
Х
|
1
|
1
|
1
|
1
|
1
|
Х
|
1.2 Мінімізація БФ (Карти Карно)
Отримуємо МДНФ і МКНФ булевой функції за допомогою метода
карт Карно. Схеми карт Карно приведені
нижче:
Таблиця 2 - Карта Карно для МДНФ
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
00
|
1
|
|
1
|
1
|
|
X
|
|
|
01
|
1
|
|
|
1
|
X
|
X
|
|
|
11
|
1
|
|
1
|
|
X
|
X
|
X
|
X
|
10
|
X
|
X
|
X
|
X
|
X
|
1
|
X
|
X
|
В результаті мінімізації, отримаємо:
=|x3|x4|x5+x1x4x5+|x2|x3x4+|x1|x3x4|x5
Таблиця
3 - Карта Карно для МКНФ
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
00
|
|
0
|
|
|
0
|
X
|
0
|
0
|
01
|
|
0
|
0
|
|
X
|
X
|
0
|
0
|
11
|
|
0
|
|
0
|
X
|
X
|
X
|
X
|
10
|
X
|
X
|
X
|
X
|
X
|
|
X
|
X
|
В результаті мінімізації, отримаємо:
Y=(x4+|x5)(x1+|x3)(x1+|x2+|x5)(|x1+|)
1.3 Мінімізація БФ (Квайна-МакКласки)
Отримуємо МДНФ і МКНФ булевої функції за допомогою метода
Квайна-МакКласки. Для цього будуємо комплекси кубів, які відрізняються між
собою кількістю одиниць ( в двох сусідніх кубів ця різниця дорівнює одиниці ) і
склеюємо набори сусідніх кубів які відрізняються лише однією одиницею. Біля
наборів що склеюються ставимо знак “ü”.Далі набори що склеюються повинні
відрізнятись на одиницю і мати спільні Х. Склеювання проводимо поки не
залишиться лише не склеюванні набори.
Спочатку знайдемо МДНФ. Комплекси кубів та їх склеювання.
C0:
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
C1:
X0 ü
X000 ü
X0000 ü
X ü
X010 ü
X0010 ü
X0 ü
X1000 ü
X ü
X0 ü
X00 ü
X000 ü
X11 ü
X0011 ü
X10
X1 ü
X01 ü
X ü
X10 ü
X ü
X0 ü
X100 ü
X00 ü
X111 ü
X0111 ü
X ü
X1110 ü
X11 ü
X011 ü
X1 ü
X101 ü
X ü
X110 ü
X ü
X0 ü
X1111 ü
X111 ü
X11 ü
X1 ü
C2 :
X0X0
X00X0
XX000
X001X
XX ü
XX0 ü
X0X ü
XX00
X0X11
XX1 ü
X1X ü
XX ü
X10X ü
X1X0 ü
XX111
X111X
XX11
X1X1 ü
X11X ü
XX ü
C3:
XXX
X1XXX
X1X1
Складемо таблицю покривань:
Таблиця 4 - Покривання
|
00000
|
00010
|
00011
|
01000
|
01010
|
10111
|
11000
|
11011
|
01X10
|
|
|
|
|
ü
|
|
|
|
0X0X0
|
ü
|
ü
|
|
ü
|
ü
|
|
|
|
X00X0
|
ü
|
ü
|
|
|
|
|
|
|
XX000
|
ü
|
|
|
ü
|
|
|
ü
|
|
X001X
|
|
ü
|
ü
|
|
|
|
|
|
1XX00
|
|
|
|
|
|
|
ü
|
|
X0X11
|
|
|
ü
|
|
|
ü
|
|
ü
|
XX111
|
|
|
|
|
|
ü
|
|
|
X111X
|
|
|
|
|
|
|
|
|
1XX11
|
|
|
|
|
|
ü
|
|
|
10XXX
|
|
|
|
|
|
ü
|
|
|
1X1XX
|
|
|
|
|
|
ü
|
|
|
1X1X1
|
|
|
|
|
|
ü
|
|
|
Ядро: X0X11
Будуємо скорочену таблицю покривань:
Таблиця 5 - Скорочена таблиця покривань
|
00000
|
00010
|
00011
|
01000
|
01010
|
11000
|
01X10
|
|
|
|
|
ü
|
|
0X0X0
|
ü
|
ü
|
|
ü
|
ü
|
|
X00X0
|
ü
|
ü
|
|
|
|
|
XX000
|
ü
|
|
|
ü
|
|
ü
|
X001X
|
|
ü
|
ü
|
|
|
|
1XX00
|
|
|
|
|
|
ü
|
Найменша МДНФ:
Y=x1x4x5+|x1x2x4|x5+|x1|x3|x5+|x3|x4|x5+|x2|x3|x5+|x2|x3x4+x1|x4|x5+|x2x4x5+x3x4x5
Тепер знайдемо МКНФ. Для цього повторимо всі попередні дії
для ДНФ.
C0:
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
ü
C1:
X01 ü
X001 ü
X0001 ü
X ü
X0 ü
X100 ü
X ü
X0 ü
X00 ü
X1 ü
X101 ü
X0101 ü
X ü
X110 ü
X0110 ü
X1 ü
X01 ü
X1001 ü
X ü
X0 ü
X1100 ü
X1 ü
X01 ü
X001 ü
X1 ü
X10 ü
X010 ü
X ü
X0 ü
X100 ü
X111 ü
X11 ü
X1101 ü
X1 ü
X1110 ü
X ü
X101 ü
X110 ü
X01 ü
X10 ü
X0 ü
X ü
X1111 ü
X1 ü
X ü
C2:
XXX01
0X1XX
XX10X
XX1X0
X11XX
Таблиця покривань приведена нижче:
Таблиця 6 - Покривання
|
0001
|
00100
|
00101
|
00110
|
01001
|
01011
|
01100
|
01101
|
11001
|
11010
|
10X0X
|
|
|
|
|
|
|
|
|
|
|
10XX0
|
|
|
|
|
|
|
|
|
|
ü
|
01XX1
|
|
|
|
|
ü
|
ü
|
|
ü
|
ü
|
|
1XX10
|
|
|
|
|
|
|
|
|
|
|
XXX01
|
ü
|
|
ü
|
|
ü
|
|
|
ü
|
|
|
0X1XX
|
|
ü
|
ü
|
ü
|
|
|
ü
|
ü
|
|
|
XX10X
|
|
ü
|
ü
|
|
|
|
ü
|
ü
|
|
|
XX1X0
|
|
ü
|
|
ü
|
|
|
ü
|
|
|
|
X11XX
|
|
|
|
|
|
|
ü
|
ü
|
|
|
Ядро: XXX01
XX1
XX10
Будуємо скорочену таблицю покривань:
Таблиця 7 - Скорочена таблиця покривань
|
0001
|
00100
|
00101
|
0X1XX
|
ü
|
ü
|
ü
|
XX10X
|
ü
|
|
ü
|
XX1X0
|
ü
|
ü
|
ü
|
X11XX
|
|
|
ü
|
Найменша МКНФ:
Y=(x4+|x5)(x1+|x2+|x5)( |x1+x3)( |x3+x4)( |x3+x5) (|x2+|x3)
1.4 Опис мінімізації БФ заданими методами
Для вибору мінімальної з МДНФ і МКНФ оцінимо складність схеми
за допомогою ціни по Квайну. Ціна по Квайну визначається як сумарне число
входів логічних елементів у складі схеми.
Такий підхід обумовлений тим, що:
складність схеми легко обчислюється по БФ, на основі яких
будується схема: для ДНФ складність дорівнює сумі кількості літер, (літері зі
знаком відповідає ціна 2), і кількість знаків диз’юнкції, збільшеного на 1 для
кожного диз’юнктивного виразу.
усі класичні методи мінімізації БФ забезпечують мінімальність
схемі саме у змісті ціни по Квайну.
Схема з мінімальною ціною по Квайну часто реалізується з
найменшим числом конструктивних елементів - корпусів інтегральних мікросхем.
Для даних функцій ми маємо:
С(МДНФ)=43
С(МКНФ)=21
Так як ціна МКНФ менше, то для реалізації схеми будемо
використовувати МКНФ.
1.5 Приведення БФ до заданого базису
Заданий базис: 3 АБО, так як це не повний функціональний базис, то ми
використовуємо базис 3 АБО-НІ.
Y=|(|(Х1Х3))+|(|(|Х3|X5))+|(|(|X1|X2|X3))+|(|(|X2|X4|X5))+|(|(X2X4|X5))+ |(|(|X1X2|X4X5))
Для реалізації функції по останньому виразу необхідно 15 елементів 3 АБО-НІ (Рис.1). Ранг даної схеми
дорівнює 5.
Рисунок 1 - Комбінаційна схема
1.6 Аналіз комбінаційної схеми методом П-алгоритму
Для аналізу методом П-алгоритму ми пронумерували кожен вихід
елемента схеми.
Нульове покриття С0:
10XX0
XX10
XXX01
X1XX
2. Проектування керуючих автоматів Мілі та Мура
2.1 Вибір вихідних даних
Граф схема складається з чотирьох блоків E,F,G,H і вершин BEGIN та END.
Вони обираються наступним чином:
блок E 17 mod 5 = 2;
- блок F
7 mod 5 = 2;
блок G 1 mod 5 = 1;
блок H 25 mod 5 = 0.
Блоки E, F, G, H з’єднуються між собою схемою яка має
вигляд :
Рисунок 2 - Алгоритм
Граф-схема алгоритму показана в додатку 1.
Тип тригера обирається за формулою: 17mod4=1.
Отже для автомата Мілі використовуємо D тригер, а для Мура - JK. Серія інтегральних мікросхем для побудови принципових мікросхем КР 555.
2.2 Структурний синтез автомата Мілі
2.2.1 Розмітка ГСА для автомата Мілі
Для автомата Мілі розмітка ГСА позначається буквою bi. Відмічаються входи в вершини, які
слідують за операторними. Виходячи з цього ми отримуємо для автомата Мілі 21 стан.
2.2.2 Кодування станів
Оскільки ми використовуємо D тригер, а його особливістю є те, що
вихід тригера такий же як стан у момент часу (t+1), то для оптимального
кодування будуємо таблицю переключення автомата, тобто записуємо скільки разів
автомат переключається у певний стан.
Таблиця 8 - Переключення автомата
Стан
|
Кількість
переключень
|
b0
|
6
|
|
b1
|
1
|
|
b2
|
2
|
|
b3
|
1
|
|
b4
|
2
|
|
b5
|
2
|
|
b6
|
1
|
|
b7
|
2
|
|
b8
|
1
|
|
b9
|
2
|
|
b10
|
2
|
|
b11
|
2
|
|
b12
|
2
|
|
b13
|
1
|
|
b14
|
1
|
|
b15
|
2
|
|
b16
|
2
|
|
b17
|
2
|
|
b18
|
2
|
|
b19
|
2
|
|
b20
|
1
|
|
Оптимальне кодування станів буде таким:
Таблиця 9 - Оптимальне кодування станів
Стан
|
Кількість
переключень
|
Кодування
|
b0
|
6
|
|
00000
|
b2
|
2
|
|
00001
|
b4
|
2
|
|
00010
|
b5
|
2
|
|
00100
|
b7
|
2
|
b9
|
2
|
|
10000
|
b10
|
2
|
|
00011
|
b11
|
2
|
|
00110
|
b12
|
2
|
|
01100
|
b15
|
2
|
|
11000
|
b16
|
2
|
|
10001
|
b17
|
2
|
|
10010
|
b18
|
2
|
|
10100
|
b19
|
2
|
|
01010
|
b1
|
1
|
|
01011
|
b3
|
1
|
|
01001
|
b6
|
1
|
|
00101
|
b8
|
1
|
|
00111
|
b13
|
1
|
|
01110
|
b14
|
1
|
|
11100
|
b20
|
1
|
|
10110
|
2.2.3 Таблиця переходів автомата Мілі
На основі ГСА і закодованих стані будуємо таблицю 10 переходів автомата.
Останній стовбець таблиці 10 заповнюється за допомогою оберненої таблиці переходів D- тригера .
булевий мінімізація комбінаційний керуючий
автомат
Таблиця 10 - Переходи автомата
b(t)
|
K(b(t))
|
b(t+1)
|
K(b(t+1))
|
x
|
y
|
ФЗ
|
b0
|
00000
|
b1
|
01011
|
1
|
y2y4
|
D2D4D5
|
b1
|
01011
|
b2
|
00001
|
1
|
y7
|
D5
|
b2
|
00001
|
b3
|
01001
|
|x1
|
y1y9
|
D2D5
|
|
|
b9
|
10000
|
x1
|
y8
|
D1
|
b3
|
01001
|
b4
|
00010
|
1
|
y2y4
|
D4
|
b4
|
00010
|
b5
|
00100
|
1
|
y7
|
D3
|
b5
|
00100
|
b6
|
00101
|
|x1
|
y1y9
|
D3D5
|
|
|
b11
|
00110
|
x1
|
y8
|
D3D4
|
b6
|
00101
|
b7
|
01000
|
1
|
y3y6
|
D2
|
b7
|
01000
|
b2
|
00001
|
x5
|
y7
|
D5
|
|
|
b8
|
00111
|
|x5x6
|
y3
|
D3D4D5
|
|
|
b9
|
10000
|
|x5|x6
|
y8
|
D1
|
b8
|
00111
|
b10
|
00011
|
1
|
y3y6
|
D4D5
|
b9
|
10000
|
b4
|
00010
|
x2
|
y2y4
|
D4
|
|
|
b10
|
00011
|
|x2
|
y3y6
|
D4D5
|
b10
|
00011
|
b5
|
00100
|
x5
|
y7
|
D3
|
|
|
b11
|
00110
|
|x5|x6
|
y8
|
D3D4
|
|
|
b12
|
01100
|
|x5x6
|
y1y8
|
D2D3
|
b11
|
00110
|
b7
|
01000
|
x2
|
y3y6
|
D2
|
|
|
b12
|
01100
|
|x2
|
y1y8
|
D2D3
|
b12
|
01100
|
b13
|
01110
|
x4
|
y4
|
D2D3D4
|
|
|
b16
|
10001
|
|x3
|
y3y10
|
D1D5
|
b13
|
01110
|
b14
|
11100
|
1
|
y4y5
|
D1D2D3
|
b14
|
11100
|
b15
|
11000
|
1
|
y1y2
|
D1D2
|
b15
|
11000
|
b0
|
00000
|
|x4x2
|
y4y5
|
-
|
|
|
b20
|
10110
|
x4
|
y3
|
D1D3D4
|
|
|
b18
|
10100
|
|x1|x2|x4
|
y5y9
|
D1D3
|
|
|
b0
|
00000
|
x1|x2|x4
|
-
|
-
|
b16
|
10001
|
b15
|
11000
|
1
|
y1y2
|
D1D2
|
b17
|
10010
|
b0
|
00000
|
|x3
|
y2y6
|
-
|
|
|
b19
|
01010
|
x3
|
y7
|
D2D4
|
b18
|
10100
|
b16
|
10001
|
x4|x3
|
y3y10
|
D1D5
|
|
|
b17
|
10010
|
x3x4
|
y6
|
D1D4
|
|
|
b17
|
10010
|
|x4x1
|
y6
|
D1D4
|
|
|
b0
|
00000
|
x1|x3|x4
|
y2y6
|
-
|
|
|
b19
|
01010
|
x1|x3x4
|
y7
|
D2D4
|
b19
|
01010
|
b0
|
00000
|
x1
|
-
|
-
|
|
|
b18
|
10100
|
|x1
|
y5y9
|
D1D3
|
b20
|
10110
|
b0
|
00000
|
1
|
y2y6
|
-
|
Побудуємо на основі останньої колонки Таблиці 13 функції
збудження і приведемо їх до базису І-НІ:
D1=| (| (b2x1) | (b7|x5|x6) |(b12|x3) |b13|b14|(b15x4) |(b15|x1|x2|x4) |b16|(b18|x3x4) | (b18x3x4) |(b18|x4x1) |(b19|x1))
D2=|(|b0|(b2|x1) |b6|(b10|x5x6) |(b11x2) |b11|(b12x4) |b13|b14|b16|(b17x3) |(b18|x1x3|x4))
D3=|(|b4|b5|(b7|x5x6) | (b10x5) |(b10|x5|x6) |(b10Vx5x6) |(b11|x2) |(b12x4) |b13|(b15x4) |(b15|x1|x2) |(b19|x1))
D5=|(|b0|b1|(b2|x1) |(b5|x1) |b5x7) |(b7|x5x6) |b8|(b9|x2) |(b12|x3) |(b18|3x4))
На основі передостанньої колонки Таблиці 10 будуємо функції виходу:
Y1=|(|(b2|x1) | (b5|x1) | (b10|x5x6) | (b11x2) |b14|b16)
Y2=|(|b0|b3| (b9x2) |b14|b16|(b17|x3) |(b18|x1|x3|x4) |b20)
Y3=|(|b|(b7|x5x6) |b8| (b9|x2) |(b11x2) |(b12|x3) |(b15x4) |(b18|x3x4))
Y4=|(|b0|b3|(b9x2) |(b12x4) |b13|(b15|x4x2))
Y5=|(|b13|(b15x2|x4) |(b15|x1|x2|x4) |b19)
Y6=|(|b6|b8|(b9|x2) |(b11x2) |(b16|x3) |(b18x3x4)(b18x1|x4) |(b18|x1|x3|x4) |b20)
Y7=|(|b1|b4|(b7x5) |(b10x5) |(b17x3) |(b18|x1x3|x4))
Y8=|(| (b2|x1) |(b5x1) |b7|x5|x6) |(b10|x5|x6) |(b11|x2))
Y9=|(|(b2|x1) |(b5|x1) |(b15|x1|x2|x4) |(b19|x1))
Y10=|(|(b12|x3) |(b18x4|x3))
За отриманими функціями збудження та виходу будуємо схему
автомата Мілі. Вона представлена у додатку 2.
2.3 Структурний синтез автомата Мура
2.3.1 Розмітка ГСА для автомата Мура
Для автомата Мура розмітка ГСА позначається буквою аi (Додаток 1).
Відмічаються всі операторні вершини, вершина початку та кінця
позначається а0. Таким чином для автомата Мура ми отримали 23 стани.
2.3.2 Кодування станів
Для оптимального кодування станів автомата використовуємо
евристичний метод. Для цього будуємо матрицю Т. Перший стовбець цієї матриці
номер вихідного стану, другий - номер стану в який переключається автомат, а
третій кількість переходів між даними станами.
Матриця Т:
i
|
j
|
P(i,j)
|
1
|
2
|
2
|
2
|
3
|
1
|
3
|
5
|
1
|
3
|
6
|
1
|
4
|
3
|
1
|
4
|
6
|
4
|
4
|
7
|
2
|
4
|
8
|
1
|
6
|
8
|
5
|
9
|
1
|
7
|
9
|
1
|
8
|
10
|
1
|
9
|
11
|
1
|
9
|
12
|
1
|
9
|
13
|
1
|
10
|
11
|
1
|
10
|
12
|
2
|
11
|
4
|
1
|
12
|
4
|
1
|
12
|
13
|
1
|
13
|
15
|
1
|
13
|
17
|
1
|
13
|
18
|
2
|
14
|
17
|
1
|
14
|
18
|
1
|
14
|
22
|
1
|
14
|
23
|
1
|
15
|
16
|
1
|
16
|
19
|
1
|
17
|
19
|
2
|
18
|
22
|
1
|
18
|
23
|
1
|
19
|
21
|
1
|
19
|
20
|
1
|
19
|
1
|
1
|
19
|
14
|
1
|
20
|
1
|
2
|
21
|
22
|
1
|
22
|
1
|
1
|
23
|
14
|
1
|
23
|
1
|
1
|
Оптимальне кодування станів буде таким:
Таблиця 11 - Оптимальне кодування станів
a0
|
00011
|
a1
|
00111
|
a2
|
01111
|
a3
|
11111
|
a4
|
01101
|
a5
|
01011
|
a6
|
11100
|
a7
|
11011
|
a8
|
11101
|
a9
|
10011
|
a10
|
11001
|
a11
|
10111
|
a12
|
10101
|
a13
|
00000
|
a14
|
10001
|
a15
|
10010
|
a16
|
10000
|
a17
|
00101
|
a18
|
00010
|
a19
|
01010
|
a20
|
00110
|
a21
|
00100
|
a22
|
00001
|
2.3.3 Таблиця переходів автомата Мура
На основі ГСА і закодованих стані будуємо таблицю13 переходів автомата.
Останній стовбець таблиці 12 заповнюється за допомогою оберненої таблиці переходів JK- тригера ( таблиця 12 ).
Таблиця 12 -
Обернена таблиці переходів JK- тригера
Q(t)
|
Q(t+1)
|
J
|
K
|
0
|
0
|
X
|
0
|
0
|
1
|
1
|
X
|
1
|
0
|
X
|
1
|
1
|
1
|
0
|
X
|
Таблиця 13 - Переходи автомата
а(t)/y
|
K(a(t))
|
a(t+1)
|
K(a(t+1))
|
x
|
ФЗ
|
a0
|
00011
|
a1
|
00111
|
1
|
J3
|
a1/y2y4
|
00111
|
a2
|
01111
|
1
|
J2J3
|
a2/y7
|
01111
|
a4
|
01101
|
|x1
|
K4
|
|
|
a5
|
01011
|
x1
|
K3
|
a3/y3y6
|
11111
|
a2
|
01111
|
x5
|
K1
|
|
|
a5
|
01011
|
|x5|x6
|
K1K3
|
|
|
a6
|
11100
|
|x5x6
|
K4K5
|
a4/y1y9
|
01101
|
a7
|
11011
|
1
|
J1K3J4
|
a5/y8
|
01011
|
a7
|
11011
|
x2
|
J1
|
|
|
a8
|
11101
|
|x2
|
J1J3K4
|
a6/y3
|
11100
|
a8
|
11101
|
1
|
J5
|
a7/y2y4
|
11011
|
a9
|
10011
|
1
|
K2
|
a8/y3y6
|
|
a9
|
10011
|
x5
|
K2K3J4
|
|
|
a11
|
10111
|
|x5|x6
|
K2J4
|
|
11101
|
a12
|
10101
|
|x5x6
|
K2
|
a9/y7
|
10011
|
a10
|
11001
|
|x1
|
J2K4
|
|
|
a11
|
10111
|
x1
|
J3
|
a10/y1y9
|
11001
|
a3
|
11111
|
1
|
J3J4
|
a11/y8
|
10111
|
a3
|
11111
|
x2
|
J2
|
|
|
a12
|
10101
|
|x2
|
K4
|
a12/y1y8
|
10101
|
a14
|
10001
|
x4
|
K3
|
|
|
a16
|
10000
|
|x3|x4
|
K3K5
|
|
|
a17
|
00101
|
x3|x4
|
J1
|
a13/y5y9
|
00000
|
a16
|
10000
|
|x3x4
|
J1
|
|
|
a17
|
00101
|
x3x4
|
J3J5
|
|
|
a17
|
00101
|
x1|x4
|
J3J5
|
|
|
a21
|
00100
|
|x1|x3|x4
|
J3
|
|
|
a22
|
00001
|
|x1|x3|x4
|
J5
|
a14/y4
|
10001
|
a15
|
10010
|
1
|
J4K5
|
a15/y4y5
|
10010
|
a18
|
00010
|
1
|
K1
|
a16/y3y10
|
10000
|
a18
|
00010
|
1
|
K1J4
|
a17/y6
|
00101
|
a21
|
00100
|
|x3
|
K5
|
|
|
a22
|
00001
|
x3
|
K3
|
a18/y1y2
|
00010
|
a0
|
00011
|
x1|x2|x4
|
J5
|
|
|
a19
|
x2|x4
|
J2
|
|
|
a20
|
00110
|
x4
|
J3
|
|
|
a13
|
00000
|
|x1|x2|x4
|
K4
|
a19/y4y5
|
01010
|
a0
|
00011
|
1
|
K2J5
|
a20/y3
|
00110
|
a21
|
00100
|
1
|
K4
|
a21/y2y6
|
00100
|
a0
|
00011
|
1
|
K3J4J5
|
a22/y7
|
00001
|
a0
|
00011
|
x1
|
J4
|
|
|
a13
|
00000
|
|x1
|
K5
|
Побудуємо на основі останнього cтовпця функції збудження і
переведемо ці функції у зручний базис (і-ні).
J1=|(|a4|a5|(a12|x3x4) |(a13|x3x4))=|(|a1|(a9|x1) |(a11x2) |(a18x2|x4))=|(|a0|a1|(a5|x2)|(a9x1) |a10|(a13x3x4) |(a13x1|x4) |(a13|x1|x3|x4) |(a18x4))=|(|a4|(a8x5) |(a8|x5|x6) |a10|a14|a16|a21|(a22x1))=|(|a6|(a13x3x4) |(a13x1|x4) |(a13|x1x3|x4) |(a18x1|x2|x4) |a19|a21)=|(|(a3x5) |(a3|x5|x6) |a15|a16)=|(|a7|(a8x5) |(a8|x5|x6) |(a8|x5x6) |a19)=|(|a2x1) |(a3|x5|x6) |a4|(a8x5) |(a12x4) |(a12|x3|x4) |(a17x3) |a21)=|(|a2|x1) |(a3|x5x6) |(a5x2) |(a9|x1) |(a11|x2) |(a18|x1|x2|x4) |a20)=|(|(a3|x5x6) |a12|x3|x4) |(a17|x3) |(a22|x1))=a4+a10+a12+a18=a1+a7+a18+a21=a3+a6+a8+a16+a20=a1+a7+a14+a15+a19=a13+a15+a19=a3+a8+a17+a21=a2+a9+a22=a5+a11+a12=a4+a10+a13=a16
За отриманими функціями збудження та виходу будуємо схему
автомата Мура. Вона представлена у додатку 3.