Алгоритм синтеза автомата
Работа из раздела: «
Программирование, компьютеры и кибернетика»
26
2
Алгоритм синтеза автомата
Содержание
автомат булевая функция
1. Техническое задание
2. Таблица функционирования и соответствия
3. Абстрактный синтез
3.1 Разметка вход-выходных слов для автомата Мили
3.2 Разметка вход-выходных слов для автомата Мура
3.3 Минимизация автомата
4. Структурный синтез
4.1 Кодировка алфавитов и состояний
4.2 Построение булевых функций
4.3 Раздельная минимизация
4.4 Факторизация и совместная минимизация
4.5 Реализация на элементах малой степени интеграции (К155)
1. Техническое задание
Синтезировать автомат для преобразования двоично-десятичного кода с весами х1=3, х2=3, х3=2, х4=1, который поступает на вход в последовательной форме, начиная со старшего разряда, в двоично-десятичный код с весами у1=5, у2=3, у3=2, у4=1, который снимается с выхода автомата в последовательной форме, начиная со старшего разряда.
2. Таблицы функционирования и соответствия
Ниже приведена одна из возможных таблиц соответствия входных и выходных слов
|
Веса входного слова
|
Веса выходного слова
|
|
|
|
х1
|
х2
|
х3
|
х4
|
у1
|
у2
|
у3
|
у4
|
|
|
№
|
3
|
3
|
2
|
1
|
5
|
3
|
2
|
1
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
|
2
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
|
|
3
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
|
|
4
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
|
|
5
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
|
|
6
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
|
|
7
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
|
|
8
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
|
|
9
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
|
|
Автоматное отображение
|
№ Z доп.
|
W*
|
|
|
0
|
Z0
|
Z0
|
Z0
|
Z0
|
C
|
C
|
W0
|
W0
|
W0
|
W0
|
|
|
1
|
Z0
|
Z0
|
Z0
|
Z1
|
C
|
C
|
W0
|
W0
|
W0
|
W1
|
|
|
2
|
Z0
|
Z0
|
Z1
|
Z0
|
C
|
C
|
W0
|
W0
|
W1
|
W0
|
|
|
3
|
Z0
|
Z0
|
Z1
|
Z1
|
C
|
C
|
W0
|
W0
|
W1
|
W1
|
|
|
4
|
Z0
|
Z1
|
Z0
|
Z1
|
C
|
C
|
W0
|
W1
|
W0
|
W1
|
|
|
5
|
Z0
|
Z1
|
Z1
|
Z0
|
C
|
C
|
W0
|
W1
|
W1
|
W0
|
|
|
6
|
Z0
|
Z1
|
Z1
|
Z1
|
C
|
C
|
W0
|
W1
|
W1
|
W1
|
|
|
7
|
Z1
|
Z1
|
Z0
|
Z1
|
C
|
C
|
W1
|
W0
|
W1
|
W0
|
|
|
8
|
Z1
|
Z1
|
Z1
|
Z0
|
C
|
C
|
W1
|
W1
|
W0
|
W0
|
|
|
9
|
Z1
|
Z1
|
Z1
|
Z1
|
C
|
C
|
W1
|
W1
|
W0
|
W1
|
|
|
Полученное автоматное отображение удовлетворяет следующим условиям:
1. автоматное отображение является однозначным;
2. автоматное отображение сохраняет длину слова;
3. автоматное отображение однозначно переводит любой начальный отрезок входного слова в соответствующий начальный отрезок выходного слова такой же длинны.
3 Абстрактный синтез
3.1 Разметка вход-выходных слов для автомата Мили
3.1.1 Первая стратегия
|
0
|
|
z0
|
|
z0
|
|
z0
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w0
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a4
|
|
a5
|
|
a1
|
|
|
1
|
|
z0
|
|
z0
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a4
|
|
a6
|
|
a1
|
|
|
2
|
|
z0
|
|
z0
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a7
|
|
a8
|
|
a1
|
|
|
3
|
|
z0
|
|
z0
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w1
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a7
|
|
a9
|
|
a1
|
|
|
4
|
|
z0
|
|
z1
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a10
|
|
a11
|
|
a12
|
|
a1
|
|
|
5
|
|
z0
|
|
z1
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a10
|
|
a13
|
|
a15
|
|
a1
|
|
|
6
|
|
z0
|
|
z1
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w1
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a10
|
|
a13
|
|
a15
|
|
a1
|
|
|
7
|
|
z1
|
|
z1
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w0
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a16
|
|
a17
|
|
a18
|
|
a19
|
|
a1
|
|
|
8
|
|
z1
|
|
z1
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w1
|
|
w0
|
|
w0
|
|
|
|
a1
|
|
a16
|
|
a17
|
|
a20
|
|
a21
|
|
a1
|
|
|
9
|
|
z1
|
|
z1
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w1
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a16
|
|
a17
|
|
a20
|
|
a22
|
|
a1
|
|
|
Проверка :
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z0
|
z0
|
z0
|
c
|
|
z(t)
|
z0
|
z0
|
z0
|
z1
|
c
|
|
z(t)
|
z0
|
z0
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a5
|
a1
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a6
|
a1
|
a(t)
|
a1
|
a2
|
a3
|
a7
|
a8
|
a1
|
|
|
w(t)
|
с
|
w0
|
w0
|
w0
|
w0
|
|
w(t)
|
с
|
w0
|
w0
|
w0
|
w1
|
|
w(t)
|
с
|
w0
|
w0
|
w1
|
w0
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z0
|
z1
|
z1
|
c
|
|
z(t)
|
z0
|
z1
|
z0
|
z1
|
c
|
|
z(t)
|
z0
|
z1
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a3
|
a7
|
a9
|
a1
|
a(t)
|
a1
|
a2
|
a10
|
a11
|
a12
|
a1
|
a(t)
|
a1
|
a2
|
a10
|
a13
|
a14
|
a1
|
|
|
w(t)
|
с
|
w0
|
w0
|
w1
|
w1
|
|
w(t)
|
с
|
w0
|
w1
|
w0
|
w1
|
|
w(t)
|
с
|
w0
|
w1
|
w1
|
w0
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z1
|
z1
|
z1
|
c
|
|
z(t)
|
z1
|
z1
|
z0
|
z1
|
c
|
|
z(t)
|
z1
|
z1
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a10
|
a13
|
a15
|
a1
|
a(t)
|
a1
|
a16
|
a17
|
a18
|
a19
|
a1
|
a(t)
|
a1
|
a16
|
a17
|
a20
|
a21
|
a1
|
|
|
w(t)
|
с
|
w0
|
w1
|
w1
|
w1
|
|
w(t)
|
с
|
w1
|
w0
|
w1
|
w0
|
|
w(t)
|
с
|
w1
|
w1
|
w0
|
w0
|
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z1
|
z1
|
z1
|
z1
|
c
|
|
|
|
a(t)
|
a1
|
a16
|
a17
|
a20
|
a22
|
a1
|
|
|
w(t)
|
с
|
w1
|
w1
|
w0
|
w1
|
|
|
|
Таблица переходов-выходов:
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a7
|
a8
|
a9
|
a10
|
a11
|
a12
|
a13
|
a14
|
|
|
z0
|
a2
|
a3
|
a4
|
a5
|
a1
|
a1
|
a8
|
a1
|
a1
|
a11
|
-
|
a1
|
a14
|
a1
|
|
|
с
|
w0
|
w0
|
w0
|
w0
|
w1
|
w1
|
w0
|
w1
|
w1
|
-
|
w1
|
w1
|
w0
|
|
|
z1
|
a16
|
a10
|
a7
|
a6
|
a1
|
a1
|
a9
|
a1
|
a1
|
a13
|
a12
|
a1
|
a15
|
a1
|
|
|
с
|
w0
|
w0
|
w0
|
w0
|
w1
|
w1
|
w0
|
w1
|
w1
|
w0
|
w1
|
w1
|
w0
|
|
|
a(t)
|
a15
|
a16
|
a17
|
a18
|
a19
|
a20
|
a21
|
a22
|
|
|
z0
|
a1
|
-
|
a18
|
-
|
a1
|
a21
|
a1
|
a1
|
|
|
w1
|
-
|
w0
|
-
|
w0
|
w0
|
w0
|
w1
|
|
|
z1
|
a1
|
a17
|
a20
|
a19
|
a1
|
a22
|
a1
|
a1
|
|
|
w1
|
w1
|
w1
|
w1
|
w0
|
w0
|
w0
|
w1
|
|
|
3.1.2 Вторая стратегия
|
0
|
|
z0
|
|
z0
|
|
z0
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w0
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a4
|
|
a5
|
|
a1
|
|
|
1
|
|
z0
|
|
z0
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a4
|
|
a6
|
|
a1
|
|
|
2
|
|
z0
|
|
z0
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a7
|
|
a5+
|
|
a1
|
|
|
3
|
|
z0
|
|
z0
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w1
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a7
|
|
a6+
|
|
a1
|
|
|
4
|
|
z0
|
|
z1
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a8
|
|
a4+
|
|
a6
|
|
a1
|
|
|
5
|
|
z0
|
|
z1
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a8
|
|
a7+
|
|
a5
|
|
a1
|
|
|
6
|
|
z0
|
|
z1
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w1
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a8
|
|
a7
|
|
a6
|
|
a1
|
|
|
7
|
|
z1
|
|
z1
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w0
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a9
|
|
a10
|
|
a11
|
|
a5+
|
|
a1
|
|
|
8
|
|
z1
|
|
z1
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w1
|
|
w0
|
|
w0
|
|
|
|
a1
|
|
a9
|
|
a10
|
|
a4+
|
|
a5
|
|
a1
|
|
|
|
9
|
|
z1
|
|
z1
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w1
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a9
|
|
a10
|
|
a4
|
|
a6
|
|
a1
|
|
|
Проверка :
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z0
|
z0
|
z0
|
c
|
|
z(t)
|
z0
|
z0
|
z0
|
z1
|
c
|
|
z(t)
|
z0
|
z0
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a5
|
a1
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a6
|
a1
|
a(t)
|
a1
|
a2
|
a3
|
a7
|
a5+
|
a1
|
|
|
w(t)
|
с
|
w0
|
w0
|
w0
|
w0
|
|
w(t)
|
с
|
w0
|
w0
|
w0
|
w1
|
|
w(t)
|
с
|
w0
|
w0
|
w1
|
w0
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z0
|
z1
|
z1
|
c
|
|
z(t)
|
z0
|
z1
|
z0
|
z1
|
c
|
|
z(t)
|
z0
|
z1
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a3
|
a7
|
a6+
|
a1
|
a(t)
|
a1
|
a2
|
a8
|
a4+
|
a6
|
a1
|
a(t)
|
a1
|
a2
|
a8
|
a7+
|
a5
|
a1
|
|
|
w(t)
|
с
|
w0
|
w0
|
w1
|
w1
|
|
w(t)
|
с
|
w0
|
w1
|
w0
|
w1
|
|
w(t)
|
с
|
w0
|
w1
|
w1
|
w0
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z1
|
z1
|
z1
|
c
|
|
z(t)
|
z1
|
z1
|
z0
|
z1
|
c
|
|
z(t)
|
z1
|
z1
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a8
|
a7
|
a6
|
a1
|
a(t)
|
a1
|
a9
|
a10
|
a11
|
a5+
|
a1
|
a(t)
|
a1
|
a9
|
a10
|
a4+
|
a5
|
a1
|
|
|
w(t)
|
с
|
w0
|
w1
|
w1
|
w1
|
|
w(t)
|
с
|
w1
|
w0
|
w1
|
w0
|
|
w(t)
|
с
|
w1
|
w1
|
w0
|
w0
|
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z1
|
z1
|
z1
|
z1
|
c
|
|
|
|
a(t)
|
a1
|
a9
|
a10
|
a4
|
a6
|
a1
|
|
|
w(t)
|
с
|
w1
|
w1
|
w0
|
w1
|
|
|
|
Таблица переходов-выходов:
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a7
|
a8
|
a9
|
a10
|
a11
|
|
|
z0
|
a2
|
a3
|
a4
|
a5
|
a1
|
a1
|
a5
|
a4
|
-
|
a11
|
-
|
|
|
с
|
w0
|
w0
|
w0
|
w0
|
w1
|
w1
|
w1
|
-
|
w0
|
-
|
|
|
z1
|
a9
|
a8
|
a7
|
a6
|
a1
|
a1
|
a6
|
a7
|
a10
|
a4
|
a5
|
|
|
с
|
w0
|
w0
|
w0
|
w0
|
w1
|
w1
|
w1
|
w1
|
w1
|
w1
|
|
|
3.2 Разметка вход-выходных слов для автомата Мура
3.2.1 Первая стратегия
|
0
|
|
z0
|
|
z0
|
|
z0
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w0
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a4
|
|
a5
|
|
a6
|
|
|
1
|
|
z0
|
|
z0
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a4
|
|
a7
|
|
a8
|
|
|
2
|
|
z0
|
|
z0
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a9
|
|
a10
|
|
a11
|
|
|
3
|
|
z0
|
|
z0
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w1
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a9
|
|
a12
|
|
a13
|
|
|
4
|
|
z0
|
|
z1
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a14
|
|
a15
|
|
a16
|
|
a17
|
|
|
5
|
|
z0
|
|
z1
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a14
|
|
a18
|
|
a19
|
|
a20
|
|
|
6
|
|
z0
|
|
z1
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w1
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a14
|
|
a18
|
|
a21
|
|
a22
|
|
|
7
|
|
z1
|
|
z1
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w0
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a23
|
|
a24
|
|
a25
|
|
a26
|
|
a27
|
|
|
8
|
|
z1
|
|
z1
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w1
|
|
w0
|
|
w0
|
|
|
|
a1
|
|
a23
|
|
a24
|
|
a28
|
|
a29
|
|
a30
|
|
|
9
|
|
z1
|
|
z1
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w1
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a23
|
|
a24
|
|
a28
|
|
a31
|
|
a32
|
|
|
Проверка :
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z0
|
z0
|
z0
|
c
|
|
z(t)
|
z0
|
z0
|
z0
|
z1
|
c
|
|
z(t)
|
z0
|
z0
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a7
|
a8
|
a(t)
|
a1
|
a2
|
a3
|
a9
|
a10
|
a11
|
|
|
w(t)
|
с
|
c
|
w0
|
w0
|
w0
|
w0
|
w(t)
|
с
|
c
|
w0
|
w0
|
w0
|
w1
|
w(t)
|
с
|
c
|
w0
|
w0
|
w1
|
w0
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z0
|
z1
|
z1
|
c
|
|
z(t)
|
z0
|
z1
|
z0
|
z1
|
c
|
|
z(t)
|
z0
|
z1
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a3
|
a9
|
a12
|
a13
|
a(t)
|
a1
|
a2
|
a14
|
a15
|
a16
|
a17
|
a(t)
|
a1
|
a2
|
a14
|
a18
|
a19
|
a20
|
|
|
w(t)
|
с
|
c
|
w0
|
w0
|
w1
|
w1
|
w(t)
|
с
|
c
|
w0
|
w1
|
w0
|
w1
|
w(t)
|
с
|
с
|
w0
|
w1
|
w1
|
w0
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z1
|
z1
|
z1
|
c
|
|
z(t)
|
z1
|
z1
|
z0
|
z1
|
c
|
|
z(t)
|
z1
|
z1
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a14
|
a18
|
a21
|
a22
|
a(t)
|
a1
|
a23
|
a24
|
a25
|
a26
|
a27
|
a(t)
|
a1
|
a23
|
a24
|
a28
|
a29
|
a30
|
|
|
w(t)
|
с
|
c
|
w0
|
w1
|
w1
|
w1
|
w(t)
|
с
|
c
|
w1
|
w0
|
w1
|
w0
|
w(t)
|
с
|
c
|
w1
|
w1
|
w0
|
w0
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z1
|
z1
|
z1
|
z1
|
c
|
|
|
|
a(t)
|
a1
|
a23
|
a24
|
a28
|
a31
|
a32
|
|
|
w(t)
|
с
|
c
|
w1
|
w1
|
w0
|
w1
|
|
|
Таблица переходов-выходов:
|
a(t)
|
-
|
-
|
w0
|
w0
|
w0
|
w0
|
w0
|
w1
|
w0
|
w1
|
w0
|
|
|
a1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a7
|
a8
|
a9
|
a10
|
a11
|
|
|
z0
|
a2
|
a3
|
a4
|
a5
|
a6
|
-
|
a8
|
-
|
a10
|
a11
|
-
|
|
|
z1
|
a23
|
a14
|
a9
|
a7
|
a6
|
-
|
a8
|
-
|
a12
|
a11
|
-
|
|
|
a(t)
|
w1
|
w1
|
w0
|
w1
|
w0
|
w1
|
w1
|
w1
|
w0
|
w1
|
w1
|
|
|
a12
|
a13
|
a14
|
a15
|
a16
|
a17
|
a18
|
a19
|
a20
|
a21
|
a22
|
|
|
z0
|
a13
|
-
|
a15
|
-
|
a17
|
-
|
a19
|
a20
|
-
|
a22
|
-
|
|
|
z1
|
a13
|
-
|
a18
|
a16
|
a17
|
-
|
a21
|
a20
|
-
|
a22
|
-
|
|
|
a(t)
|
-
|
w1
|
w0
|
w1
|
w0
|
w1
|
w0
|
w0
|
w0
|
w1
|
|
|
a23
|
a24
|
a25
|
a26
|
a27
|
a28
|
a29
|
a30
|
a31
|
a32
|
|
|
z0
|
-
|
a25
|
-
|
a27
|
-
|
a29
|
a30
|
-
|
a32
|
-
|
|
|
z1
|
a24
|
a28
|
a26
|
a27
|
-
|
a31
|
a30
|
-
|
a32
|
-
|
|
|
3.2.2 Вторая стратегия
|
0
|
|
z0
|
|
z0
|
|
z0
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w0
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a4
|
|
a5
|
|
a6
|
|
|
1
|
|
z0
|
|
z0
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a4
|
|
a6+
|
|
a7
|
|
|
2
|
|
z0
|
|
z0
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a8
|
|
a7+
|
|
a1+
|
|
|
3
|
|
z0
|
|
z0
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w0
|
|
w1
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a3
|
|
a8
|
|
a9
|
|
a2+
|
|
|
4
|
|
z0
|
|
z1
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a10
|
|
a11
|
|
a6+
|
|
a7
|
|
|
5
|
|
z0
|
|
z1
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a2
|
|
a10
|
|
a12
|
|
a7+
|
|
a1
|
|
|
6
|
|
z0
|
|
z1
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w0
|
|
w1
|
|
w1
|
|
w1
|
|
|
|
a1
|
|
a2
|
|
a10
|
|
a12
|
|
a9+
|
|
a2
|
|
|
|
7
|
|
z1
|
|
z1
|
|
z0
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w0
|
|
w1
|
|
w0
|
|
|
|
a1
|
|
a13
|
|
a14
|
|
a6+
|
|
a7
|
|
a1
|
|
|
8
|
|
z1
|
|
z1
|
|
z1
|
|
z0
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w1
|
|
w0
|
|
w0
|
|
|
|
a1
|
|
a13
|
|
a14
|
|
a11+
|
|
a15
|
|
a1
|
|
|
9
|
|
z1
|
|
z1
|
|
z1
|
|
z1
|
|
c
|
|
|
|
|
c
|
|
w1
|
|
w1
|
|
w0
|
|
w1
|
|
|
|
a1
|
|
a13
|
|
a14
|
|
a11
|
|
a6+
|
|
a2
|
|
|
Проверка :
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z0
|
z0
|
z0
|
c
|
|
z(t)
|
z0
|
z0
|
z0
|
z1
|
c
|
|
z(t)
|
z0
|
z0
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a6
|
a7
|
a(t)
|
a1
|
a2
|
a3
|
a8
|
a7
|
a1
|
|
|
w(t)
|
с
|
c
|
w0
|
w0
|
w0
|
w0
|
w(t)
|
с
|
c
|
w0
|
w0
|
w0
|
w1
|
w(t)
|
с
|
c
|
w0
|
w0
|
w1
|
w0
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z0
|
z1
|
z1
|
c
|
|
z(t)
|
z0
|
z1
|
z0
|
z1
|
c
|
|
z(t)
|
z0
|
z1
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a3
|
a8
|
a9
|
a2
|
a(t)
|
a1
|
a2
|
a10
|
a11
|
a6
|
a7
|
a(t)
|
a1
|
a2
|
a10
|
a12
|
a7
|
a1
|
|
|
w(t)
|
с
|
c
|
w0
|
w0
|
w1
|
w1
|
w(t)
|
с
|
c
|
w0
|
w1
|
w0
|
w1
|
w(t)
|
с
|
с
|
w0
|
w1
|
w1
|
w0
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z0
|
z1
|
z1
|
z1
|
c
|
|
z(t)
|
z1
|
z1
|
z0
|
z1
|
c
|
|
z(t)
|
z1
|
z1
|
z1
|
z0
|
c
|
|
|
|
a(t)
|
a1
|
a2
|
a10
|
a12
|
a9
|
a2
|
a(t)
|
a1
|
a13
|
a14
|
a6
|
a7
|
a1
|
a(t)
|
a1
|
a13
|
a14
|
a11
|
a15
|
a1
|
|
|
w(t)
|
с
|
c
|
w0
|
w1
|
w1
|
w1
|
w(t)
|
с
|
c
|
w1
|
w0
|
w1
|
w0
|
w(t)
|
с
|
c
|
w1
|
w1
|
w0
|
w0
|
|
|
|
t
|
0
|
1
|
2
|
3
|
4
|
5
|
|
|
z(t)
|
z1
|
z1
|
z1
|
z1
|
c
|
|
|
|
a(t)
|
a1
|
a13
|
a14
|
a11
|
a6
|
a7
|
|
|
w(t)
|
с
|
c
|
w1
|
w1
|
w0
|
w1
|
|
|
Таблица переходов-выходов:
|
a(t)
|
w0
|
w1
|
w0
|
w0
|
w0
|
w0
|
w1
|
w0
|
w1
|
w0
|
w1
|
|
|
a1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a7
|
a8
|
a9
|
a10
|
a11
|
|
|
z0
|
a2
|
a3
|
a4
|
a5
|
a6
|
a7
|
a1
|
a7
|
a2
|
a11
|
a15
|
|
|
z1
|
a13
|
a10
|
a8
|
a6
|
a6
|
a7
|
a1
|
a9
|
a2
|
a12
|
a6
|
|
|
|
a(t)
|
w1
|
-
|
w1
|
w0
|
|
|
a12
|
a13
|
a14
|
a15
|
|
|
z0
|
a7
|
-
|
a6
|
a1
|
|
|
z1
|
a9
|
a14
|
a11
|
a1
|
|
|
Меньшим числом состояний обладает автомат Мили, построенный по второй стратегии. Следовательно, по соответствующей ему таблице переходов-выходов будет проводиться структурный синтез автомата.
Таблица переходов-выходов автомата Мили, построенного по второй стратегии
|
a(t)
|
a1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a7
|
a8
|
a9
|
a10
|
a11
|
|
|
z0
|
a2
|
a3
|
a4
|
a5
|
a1
|
a1
|
a5
|
a4
|
-
|
a11
|
-
|
|
|
с
|
w0
|
w0
|
w0
|
w0
|
w1
|
w1
|
w1
|
-
|
w0
|
-
|
|
|
z1
|
a9
|
a8
|
a7
|
a6
|
a1
|
a1
|
a6
|
a7
|
a10
|
a4
|
a5
|
|
|
с
|
w0
|
w0
|
w0
|
w0
|
w1
|
w1
|
w1
|
w1
|
w1
|
w1
|
|
|
3.3 Минимизация автомата
Диаграмма совместимости
|
2
|
2~3 9~8
|
|
|
|
|
|
|
|
|
|
|
|
3
|
2~4 9~7
|
3~4 7~8
|
|
|
|
|
|
|
|
|
|
|
4
|
2~5 6~9
|
3~5 6~8
|
4~5 7~6
|
|
|
|
|
|
|
|
|
|
5
|
1~2 1~9
|
1~3 1~8
|
1~4 1~7
|
1~5 1~6
|
|
|
|
|
|
|
|
|
6
|
1~2 1~9
|
|
|
|
|
|
|
|
|
|
|
|
7
|
2~5 6~9
|
|
|
|
|
1~5 1~6
|
|
|
|
|
|
|
8
|
2~4 9~7
|
|
|
|
|
4~1 1~7
|
5~4 6~7
|
|
|
|
|
|
9
|
9~10
|
|
|
|
|
1~10
|
6~10
|
7~10
|
|
|
|
|
10
|
2~11 9~4
|
|
|
|
|
|
|
|
10~4
|
|
|
|
11
|
9~5
|
|
|
|
|
1~5
|
6~5
|
7~5
|
10~5
|
4~5
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
|
Из диаграммы видно, что все состояния исходного автомата являются попарно несовместимыми. Следовательно, полученный автомат является минимальным.
|
№
|
МС-классы.
|
|
|
0
|
1,2,3,4,5,6,7,8,9,10,11
|
|
|
1
|
1,3,4,5,6,7,8,9,10,11 1,2,3,4,5
|
|
|
2
|
1,4,5,6,7,8,9,10,11 1,2,3,4,5
|
|
|
3
|
1,5,6,7,8,9,10,11 1,2,3,4,5
|
|
|
4
|
1,6,7,8,9,10,11 1,2,3,4,5
|
|
|
5
|
1,6,7,8,9,11 1,10 1,2,3,4,5
|
|
|
6
|
1 2 3 4 5 6 7 8 9 10 11
|
|
|
4. Структурный синтез автомата
4.1 Кодировка алфавитов и состояний
Кодировка входного алфавита
Определим количество внешних входов L. Пусть 2L - число различных комбинаций, которые можно подать на входы. Тогда 2L ? F- мощности входного алфавита. F = 2. 21=2 , значит L =1.
Кодировка выходного алфавита
Определим количество внешних выходов N. Пусть 2N - число различных комбинаций, которые могут поступить на выходы. Тогда 2N ? G - мощности выходного алфавита. G = 2. 21 = 2 , значит N=1.
Кодировка внутренних состояний
Определим количество элементов памяти (триггеров) R. Пусть 2R- число различных внутренних состояний, в которых может находиться структурный автомат. Тогда 2R ? M - мощности алфавита состояний. M=11. 24 > 11, значит R=4.
|
а(t)
|
Q1
|
Q2
|
Q3
|
Q4
|
|
|
а1
|
0
|
0
|
0
|
1
|
|
|
а2
|
0
|
0
|
1
|
0
|
|
|
а3
|
0
|
0
|
1
|
1
|
|
|
а4
|
0
|
1
|
0
|
0
|
|
|
а5
|
0
|
1
|
0
|
1
|
|
|
а6
|
0
|
1
|
1
|
0
|
|
|
а7
|
0
|
1
|
1
|
1
|
|
|
а8
|
1
|
0
|
0
|
0
|
|
|
а9
|
1
|
0
|
0
|
1
|
|
|
а10
|
1
|
0
|
1
|
0
|
|
|
а11
|
1
|
0
|
1
|
1
|
|
|
4.2 Построение булевых функций
Для заполнения таблицы переходов-выходов будем использовать таблицу функции переходов i-того элемента памяти и словарь JK - триггера.
Таблица функции переходов i-того элемента памяти
|
Qit
|
Qit+1
|
fQi
|
|
|
0
|
0
|
0
|
|
|
0
|
1
|
б
|
|
|
1
|
0
|
?
|
|
|
1
|
1
|
1
|
|
|
Cловарь JK-триггера
|
fQi
|
J
|
K
|
|
|
0
|
0
|
-
|
|
|
1
|
-
|
0
|
|
|
б
|
1
|
-
|
|
|
?
|
-
|
1
|
|
|
Кодированная таблица переходов-выходов
|
t
|
t+1
|
|
t
|
|
|
№
|
x
|
Q1
|
Q2
|
Q3
|
Q4
|
y
|
Q1
|
Q2
|
Q3
|
Q4
|
fQ
|
fQ
|
fQ
|
fQ
|
J1
|
K1
|
J2
|
K2
|
J3
|
K3
|
J4
|
K4
|
|
|
1
|
0
|
0
|
0
|
0
|
1
|
-
|
0
|
0
|
1
|
0
|
0
|
0
|
б
|
?
|
0
|
-
|
0
|
-
|
1
|
-
|
-
|
1
|
|
|
2
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
б
|
0
|
-
|
0
|
-
|
-
|
0
|
1
|
-
|
|
|
3
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
б
|
?
|
?
|
0
|
-
|
1
|
-
|
-
|
1
|
-
|
1
|
|
|
4
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
б
|
0
|
-
|
-
|
0
|
0
|
-
|
1
|
-
|
|
|
5
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
?
|
0
|
1
|
0
|
-
|
-
|
1
|
0
|
-
|
-
|
0
|
|
|
6
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
?
|
?
|
б
|
0
|
-
|
-
|
1
|
-
|
1
|
1
|
-
|
|
|
7
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
?
|
1
|
0
|
-
|
-
|
0
|
-
|
1
|
-
|
0
|
|
|
8
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
?
|
б
|
0
|
0
|
-
|
1
|
1
|
-
|
0
|
-
|
0
|
-
|
|
|
9
|
0
|
1
|
0
|
0
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
10
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
б
|
-
|
0
|
0
|
-
|
-
|
0
|
1
|
-
|
|
|
11
|
0
|
1
|
0
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
12
|
1
|
0
|
0
|
0
|
1
|
-
|
1
|
0
|
0
|
1
|
б
|
0
|
0
|
1
|
1
|
-
|
0
|
-
|
0
|
-
|
-
|
0
|
|
|
13
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
б
|
?
|
б
|
0
|
-
|
1
|
-
|
-
|
1
|
1
|
-
|
|
|
14
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
б
|
1
|
1
|
0
|
-
|
1
|
-
|
-
|
0
|
-
|
0
|
|
|
15
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
б
|
0
|
0
|
-
|
-
|
0
|
1
|
-
|
-
|
0
|
|
|
16
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
?
|
0
|
1
|
0
|
-
|
-
|
1
|
0
|
-
|
-
|
0
|
|
|
17
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
?
|
?
|
б
|
0
|
-
|
-
|
1
|
-
|
1
|
1
|
-
|
|
|
18
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
?
|
0
|
-
|
-
|
0
|
-
|
0
|
-
|
1
|
|
|
19
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
?
|
б
|
б
|
б
|
-
|
1
|
1
|
-
|
1
|
-
|
1
|
-
|
|
|
20
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
б
|
?
|
-
|
0
|
0
|
-
|
1
|
-
|
-
|
1
|
|
|
21
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
?
|
б
|
?
|
0
|
-
|
1
|
1
|
-
|
-
|
1
|
0
|
-
|
|
|
22
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
?
|
б
|
?
|
1
|
-
|
1
|
1
|
-
|
-
|
1
|
-
|
0
|
|
|
4.3 Раздельная минимизация
Минимизация булевых функций с помощью карт Карно
|
y
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
0
|
-
|
1
|
1
|
-
|
0
|
-
|
|
|
01
|
-
|
0
|
-
|
-
|
1
|
-
|
0
|
-
|
|
|
11
|
0
|
1
|
-
|
-
|
1
|
-
|
1
|
0
|
|
|
10
|
0
|
1
|
-
|
0
|
1
|
-
|
1
|
0
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
J1
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
0
|
-
|
-
|
-
|
-
|
0
|
-
|
|
|
01
|
0
|
0
|
-
|
-
|
-
|
-
|
0
|
|
|
|
11
|
0
|
0
|
-
|
-
|
-
|
-
|
0
|
0
|
|
|
10
|
0
|
0
|
-
|
-
|
-
|
-
|
0
|
0
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
K1
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
-
|
-
|
1
|
1
|
-
|
-
|
-
|
|
|
01
|
-
|
-
|
-
|
-
|
0
|
-
|
-
|
-
|
|
|
11
|
-
|
-
|
-
|
-
|
1
|
-
|
-
|
-
|
|
|
10
|
-
|
-
|
-
|
0
|
1
|
-
|
-
|
-
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
J2
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
-
|
-
|
1
|
1
|
-
|
-
|
-
|
|
|
01
|
0
|
-
|
-
|
-
|
0
|
-
|
-
|
0
|
|
|
11
|
1
|
-
|
-
|
-
|
1
|
-
|
-
|
1
|
|
|
10
|
0
|
-
|
-
|
0
|
1
|
-
|
-
|
1
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
K2
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
0
|
-
|
-
|
-
|
-
|
0
|
-
|
|
|
01
|
-
|
1
|
-
|
-
|
-
|
-
|
1
|
-
|
|
|
11
|
-
|
0
|
-
|
-
|
-
|
-
|
0
|
-
|
|
|
10
|
-
|
1
|
-
|
-
|
-
|
-
|
1
|
-
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
J3
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
0
|
-
|
0
|
1
|
-
|
1
|
-
|
|
|
01
|
1
|
0
|
-
|
-
|
1
|
-
|
0
|
0
|
|
|
11
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
10
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
K3
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
01
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
11
|
1
|
-
|
1
|
-
|
1
|
-
|
0
|
0
|
|
|
10
|
0
|
-
|
1
|
0
|
1
|
-
|
1
|
1
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
J4
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
1
|
-
|
0
|
1
|
-
|
-
|
-
|
|
|
01
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
11
|
1
|
-
|
1
|
-
|
1
|
-
|
0
|
0
|
|
|
10
|
0
|
-
|
1
|
0
|
1
|
-
|
1
|
1
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
K4
|
xQ1Q2
|
|
|
|
|
A
|
|
|
|
|
|
Q3Q4
|
|
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|
|
00
|
-
|
-
|
-
|
-
|
-
|
-
|
0
|
-
|
|
|
01
|
1
|
0
|
-
|
-
|
1
|
-
|
0
|
0
|
|
|
11
|
1
|
0
|
-
|
-
|
0
|
-
|
1
|
0
|
|
|
10
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
Таким образом, получена система булевых функций:
4.4 Факторизация и совместная минимизация
Совместная минимизация
Тогда система булевых функций будет выглядеть следующим образом:
Факторизация:
Факторизация Y
Факторизация K3
С учетом факторизации и совместной минимизации функций получаем следующую систему:
4.5 Реализация на элементах малой степени интеграции (К155)
Использованные элементы серии К155 и их УГО:
1) К155ТВ15
Микросхема представляет собой два тактируемых J-K триггера с установкой в 0 и 1. Считывание информации с входов J и K происходит во время положительного перепада на входе С, а на выходы она передается во время отрицательного перепада. Логические уровни на J и K не должны изменяться, пока на С высокий уровень. Если соединить выводы J и K триггер будет работать как обычный счетный (делить частоту на 2).
1,15 - вход установки '0';2 - вход J1;3 - вход K1;4,12 - вход синхронизации;5,11 - вход установки '1';6,7,9,10 - выходы;8 - общий;13 - вход K2;14 - вход J2;16 - напряжение питания;
2) К155ЛН1
Микросхема представляет собой шесть логических элементов НЕ. Корпус К155ЛН1 типа 201.14-1, масса не более 1 г и у КМ155ЛН1 типа 201.14-8, масса не более 2,2 г.
1,3,5,9,11,13 - входы;2,4,6,8,10,12 - выходы;7 - общий;14 - напряжение питания;
3) К155ЛР1
Микросхема представляет собой 2 логических элемента 2-2И-2ИЛИ-НЕ, один расширяемый по ИЛИ. Корпус К155ЛР1 типа 201.14-2, масса не более 1 г и у КМ155ЛР1 типа 201.14-8, масса не более 2,2 г.
1-5,9-13 - входы;6,8 - выходы;7 - общий;14 - напряжение питания;
4) К155ЛИ1
Микросхема представляет собой четыре логических элемента 2И. Корпус К155ЛИ1 типа 201.14-1, масса не более 1 г и у КМ155ЛИ1 типа 201.14-8, масса не более 2,2 г.
1,2,4,5,9,10,12,13 - входы;3,6,8,11 - выходы;7 - общий;14 - напряжение питания;
5) К155ЛЛ1
Микросхема представляет собой четыре логических элемента 2ИЛИ. Корпус К155ЛЛ1 типа 201.14-1, масса не более 1 г и у КМ155ЛЛ1
типа 201.14-8, масса не более 2,2 г.
1,2,4,5,9,10,12,13 - входы;3,6,8,11 - выходы;7 - общий;14 - напряжение питания;
Для всех микросхем на 14 ножку подается +5В, на 7 - заземление
DD1, DD2 - К155ТВ15;
DD3 - К155ЛР1;
DD4, DD10, DD11, DD13 - К155ЛЛ1;
DD6, DD7, DD8, DD9, DD12 - К155ЛИ1;
DD5, DD14, DD15, DD16 - К155ЛН1.
