Синтез комбинационной схемы и проектирование управляющего автомата Мура
Булевая функция 5 переменных: понятие и содержание, закономерности и принципы функционирования. Порядок расчета значений, минимизация функции. Проектирование автоматов. Автомат Мура, принципы их действия, функциональные особенности и использование.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 21.10.2012 |
| Размер файла | 165,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
1 Синтез комбинационной схемы
1.1 Определение значений БФ
Булевая функция 5 переменных F (x1, x2, x3, x4, x5) задается своими значениями, которые определяются 7-разрядовими двоичными эквивалентами чисел,: по значению чисел А, В (на наборах 7-13), С (наборы 14-20), по значению (наборы 21-27) и на наборах 28-31 функции принимает неопределенные значения.
А=13 эквивалентно 4910=1100012.
Проставляем символ неопределенного значения Х110001.
В=07 эквивалентно 1010=10102.
Проставляем символ неопределенного значения ХХХ1010.
С=21 эквивалентно 2310=101112.
Проставляем символ неопределенного значения XХ10111.
А+В+С=41 эквивалентно 7210=10010002.
Соответственно, значение функций F (x1, x2, x3, x4, x5) на наборах от 0 до 31 будет иметь вид
Таблица 1
|
№ набору |
X1 |
X2 |
X3 |
X4 |
X5 |
F |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
X |
|
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
2 |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
3 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
4 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
5 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
6 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
7 |
0 |
0 |
1 |
1 |
1 |
X |
|
|
8 |
0 |
1 |
0 |
0 |
0 |
X |
|
|
9 |
0 |
1 |
0 |
0 |
1 |
X |
|
|
10 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
11 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|
12 |
0 |
1 |
1 |
0 |
0 |
1 |
|
|
13 |
0 |
1 |
1 |
0 |
1 |
0 |
|
|
14 |
0 |
1 |
1 |
1 |
0 |
X |
|
|
15 |
0 |
1 |
1 |
1 |
1 |
X |
|
|
16 |
1 |
0 |
0 |
0 |
0 |
1 |
|
|
17 |
1 |
0 |
0 |
0 |
1 |
0 |
|
|
18 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
19 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
20 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
21 |
1 |
0 |
1 |
0 |
1 |
1 |
|
|
22 |
1 |
0 |
1 |
1 |
0 |
0 |
|
|
23 |
1 |
0 |
1 |
1 |
1 |
0 |
|
|
24 |
1 |
1 |
0 |
0 |
0 |
1 |
|
|
25 |
1 |
1 |
0 |
0 |
1 |
0 |
|
|
26 |
1 |
1 |
0 |
1 |
0 |
0 |
|
|
27 |
1 |
1 |
0 |
1 |
1 |
0 |
|
|
28 |
1 |
1 |
1 |
0 |
0 |
X |
|
|
29 |
1 |
1 |
1 |
0 |
1 |
X |
|
|
30 |
1 |
1 |
1 |
1 |
0 |
X |
|
|
31 |
1 |
1 |
1 |
1 |
1 |
X |
1.2 Минимизация БФ
Получаем МДНФ и МКНФ булевой функции с помощью метода карт Карно. Схемы карт Карно приведены ниже.
Таблица 2 Карта Карно к МДНФ
|
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
||
|
00 |
X |
1 |
0 |
1 |
1 |
X |
0 |
0 |
|
|
01 |
X |
X |
0 |
1 |
X |
X |
0 |
1 |
|
|
11 |
1 |
0 |
0 |
0 |
X |
X |
X |
X |
|
|
10 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
В результате минимизации, получим:
_ _ _ _ _ _ _ _ _ _ _ _ _
Y=X1X3X4+X2X4X5+X3X4X5+X1X2X3X4+X1X4X5+X1X3X4
Таблица 3 Карта Карно к МКНФ
|
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
||
|
00 |
X |
1 |
0 |
1 |
1 |
X |
0 |
0 |
|
|
01 |
X |
X |
0 |
1 |
X |
X |
0 |
1 |
|
|
11 |
1 |
0 |
0 |
0 |
X |
X |
X |
X |
|
|
10 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
В результате минимизации, получим:
_ _ _ _ _ _ _ _ _ _
y=(X1+X2+X4+X5) (X1+X3 +X4 +X5) (X1+ X3+ X4+ X5) (X1+X2+ X4) (X1+X3+ X4)
_ _
(X1+X3+X5)
1.3 Описание минимизации БФ заданными методами
Для выбора минимальной из МДНФ и МКНФ оценим сложность схемы с помощью цены по Квайну. Цена по Квайну определяется как суммарное число входов логических элементов в составе схемы.
Такой подход обусловлен тем, что
- сложность схемы легко вычисляется по БФ, на основе которых строится схема: для ДНФ сложность равняется сумме количества букв, (букве со знаком отвечает цена 2) и количество знаков дизъюнкции, увеличенного на 1 для каждого дизъюнктивного выражения.
- все классические методы минимизации БФ обеспечивают минимальность схеме именно в содержании цены по Квайну.
Схема с минимальной ценой по Квайну часто реализуется с наименьшим числом конструктивных элементов - корпусов интегральных микросхем.
Для данных функций мы имеем:
Cкв (МДНФ)=19+6+5=30;
Cкв(МКНФ)=21+6+5=32.
Так как минимальной ценой является Cкв(МКНФ), то для реализации схемы будем использовать МДНФ.
1.4 Приведение БФ к заданному базису
Заданный базис: 3 И-НЕТ.
Приведем выражение к заданному базису:
_ _ _ _ _ _ _ _ _ _ _ _ _
Y=X1X3X4+X2X4X5+X3X4X5+X1X2X3X4+X1X4X5+X1X3X4 =
=X3(X1X4*X4X5*X1X2X4)*X5(X2X4*X1X4)*X1X3X4
Для реализации функции по останьому выражению необходимо 16 элементов 3И-НЕТ (Рис. 1). Ранг данной схемы равняется 4, что негативно отображается на скорости. Использовал факторный алгоритм возможно улучшить схему, увеличить скорость его работы.
Рис. 1 Функциональная схема для заданного базиса
2. Проектирование автоматов
2.1 Выбор задания
Граф-схемы алгоритмов избираются каждым студентом в индивидуальном порядке. Она состоит из четырех блоков: E, F, G, H. Студенты избирают графскую схему из пяти блоков с номерами 0…4 на основании чисел А, В, С и (А+В+С) по следующим правилам:
- блок «Е» - схема под номером (А) mod 5 = 13 mod 5 = 3;
- блок «F» - схема под номером (В) mod 5 = 7 mod 5 = 2;
- блок «G» - схема под номером (С) mod 5 = 21 mod 5 = 1;
- блок «H» - схема под номером (А+В+С) mod 5 = 41 mod 5 = 1.
Расположение избирается с использованием номера группы. Тип триггера находим по таблицы на основании числа (А) mod 3 = 13 mod 3 = 1.
|
(A) mod 3 |
ТИП ТРИГГЕРА |
||
|
0 |
Т |
D |
|
|
1 |
D |
JK |
|
|
2 |
JK |
T |
|
|
автомат |
Моли |
Мура |
Получаем D - тригер для автомата Моли и JK - тригер для Мура. Для парных номеров по списку (21) - серия КР555.
После соответствующей разметки строим таблицы переходов для обоих автоматов.
2.2 Автомат Мура
Строим таблицу переходов для автомата Мура.
Кодировку состояний выполняем по евристическому алгоритму. Для этого строим матрицу Т.
¦T¦ =
i ¦ j ¦ P (i, j)
1 ¦ 2 ¦ 1
1 ¦ 24¦ 1
1 ¦ 25¦ 1
2 ¦ 4 ¦ 1
2 ¦ 6 ¦ 1
2 ¦ 7 ¦ 1
3 ¦ 5 ¦ 1
3 ¦ 6 ¦ 1
3 ¦ 7 ¦ 1
3 ¦ 13 ¦ 1
3 ¦ 14 ¦ 1
4 ¦ 6 ¦ 1
4 ¦ 7 ¦ 1
5 ¦ 6 ¦ 1
5 ¦ 7 ¦ 2
6 ¦ 8 ¦ 1
6 ¦ 9 ¦ 1
7 ¦ 8 ¦ 1
8 ¦ 10 ¦ 1
9 ¦ 11 ¦ 1
10¦ 11 ¦ 1
10¦ 13 ¦ 1
10¦ 14 ¦ 1
11¦ 12 ¦ 1
11¦ 13 ¦ 1
12¦ 15 ¦ 1
13¦ 15 ¦ 1
15¦ 17 ¦ 1
15¦ 19 ¦ 1
15¦ 20 ¦ 1
16¦ 19 ¦ 1
16¦ 20 ¦ 2
16¦ 22 ¦ 2
16¦ 26 ¦ 1
17¦ 18 ¦ 1
18¦ 21 ¦ 1
19¦ 21 ¦ 1
20¦ 22 ¦ 1
21¦ 23 ¦ 1
21¦ 25 ¦ 1
21¦ 26 ¦ 1
22¦ 25 ¦ 1
22¦ 26 ¦ 2
23¦ 24 ¦ 1
P(1) = 3
P(2) = 4
P(3) = 5
P(4) = 3
P(5) = 3
P(6) = 6
P(7) = 5
P(8) = 3
P(9) = 2
P(10) = 4
P(11) = 4
P(12) = 2
P(13) = 4
P(14) = 2
P(15) = 5
P(16) = 4
P(17) = 2
P(18) = 2
P(19) = 3
P(20) = 3
P(21) = 5
P(22) = 4
P(23) = 2
P(24) = 2
P(25) = 3
P(26) = 3
Дальше согласно правил алгоритма строим матрицу М
¦M¦ =
i ¦ j ¦ P (i, j)
5 ¦ 7 ¦ 2
3 ¦ 7 ¦ 1
3 ¦ 6 ¦ 1
2 ¦ 6 ¦ 1
2 ¦ 7 ¦ 1
3 ¦ 13 ¦ 1
4 ¦ 6 ¦ 1
5 ¦ 6 ¦ 1
6 ¦ 8 ¦ 1
13 ¦ 15 ¦ 1
3 ¦ 5 ¦ 1
4 ¦ 7 ¦ 1
6 ¦ 9 ¦ 1
7 ¦ 8 ¦ 1
10 ¦ 13 ¦ 1
10 ¦ 11 ¦ 1
11 ¦ 13 ¦ 1
15 ¦ 19 ¦ 1
15 ¦ 20 ¦ 1
16 ¦ 20 ¦ 2
16 ¦ 22 ¦ 2
22 ¦ 26 ¦ 2
19 ¦ 21 ¦ 1
21 ¦ 25 ¦ 1
21 ¦ 26 ¦ 1
1 ¦ 2 ¦ 1
2 ¦ 4 ¦ 1
3 ¦ 14 ¦ 1
8 ¦ 10 ¦ 1
12 ¦ 15 ¦ 1
15 ¦ 17 ¦ 1
16 ¦ 19 ¦ 1
16 ¦ 26 ¦ 1
18 ¦ 21 ¦ 1
20 ¦ 22 ¦ 1
21 ¦ 23 ¦ 1
22 ¦ 25 ¦ 1
1 ¦ 25 ¦ 1
9 ¦ 11 ¦ 1
10 ¦ 14 ¦ 1
11 ¦ 12 ¦ 1
1 ¦ 24 ¦ 1
17 ¦ 18 ¦ 1
23 ¦ 24 ¦ 1
Определяем разрядность кода для кодировки состояний автомата
R =] log2 N [=] log2 26 [= 5
Результаты кодировки:
a1 10101
a2 00101
a3 00010
a4 00111
a5 00000
a6 00011
a7 00001
a8 01011
a9 10011
a10 01010
a11 11010
a12 11110
a13 10010
a14 01000
a15 10110
a16 00100
a17 10111
a18 11111
a19 10100
a20 00110
a21 11101
a22 01100
a23 11001
a24 10001
a25 11100
a26 01101
Подсчет эффективности кодировки:
Количество переключений триггеров:
W = E P (i, j)*d (i, j) = P (1,2)*d (1,2) + P (1,24)*d (1,24) + P (1,25)*d (1,25) + P (2,4)*d (2,4) + P (2,6)*d (2,6) + P (2,7)*d (2,7) + P (3,5)*d (3,5) + P (3,6)*d (3,6) + P (3,7)*d (3,7) + P (3,13)*d (3,13) + P (3,14)*d (3,14) + P (4,6)*d (4,6) + P (4,7)*d (4,7) + P (5,6)*d (5,6) + P (5,7)*d (5,7) + P (6,8)*d (6,8) + P (6,9)*d (6,9) + P (7,8)*d (7,8) + P (8,10)*d (8,10) + P (9,11)*d (9,11) + P (10,11)*d (10,11) + P (10,13)*d (10,13) + P (10,14)*d (10,14) + P (11,12)*d (11,12) + P (11,13)*d (11,13) + P (12,15)*d (12,15) + P (13,15)*d (13,15) + P (15,17)*d (15,17) + P (15,19)*d (15,19) + P (15,20)*d (15,20) + P (16,19)*d (16,19) + P (16,20)*d (16,20) + P (16,22)*d (16,22) + P (16,26)*d (16,26) + P (17,18)*d (17,18) + P (18,21)*d (18,21) + P (19,21)*d (19,21) + P (20,22)*d (20,22) + P (21,23)*d (21,23) + P (21,25)*d (21,25) + P (21,26)*d (21,26) + P (22,25)*d (22,25) + P (22,26)*d (22,26) + P (23,24)*d (23,24) = 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*2 + 1*2 + 2*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 2*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 1*1 = 60
Минимально возможное количество переключений триггеров:
Wmin = E P (i, j) = 48
Коэффициент эффективности кодировки: 1.25
|
Am(y) |
Kam |
As |
X |
Kas |
ФВ |
|
|
A1 (-) |
10101 |
A2 |
1 |
00101 |
K1 |
|
|
A2 (y2y5) |
00101 |
A4 A6 A7 |
X5 NX5X2 NX5NX2 |
00111 00011 00001 |
J4 K3J4 K3 |
|
|
A3 (y3) |
00010 |
A5 A6 A7 |
X5 NX5X2 NX5NX2 |
00000 00011 00001 |
K4 J5 K4J5 |
|
|
A4 (y7) |
00111 |
A6 A7 |
X2 NX2 |
00011 00001 |
K3 K3K4 |
|
|
A5 (y5y9) |
00000 |
A6 A7 |
X2 NX2 |
00011 00001 |
J4J5 J5 |
|
|
A6 (y3y4y5) |
00011 |
A8 A9 |
NX4 X4 |
01011 10011 |
J2 J1 |
|
|
A7 (y1y2) |
00001 |
A5 A8 |
NX6 X6 |
00000 01011 |
K5 J2J4 |
|
|
A8 (y2) |
01011 |
A10 |
1 |
01010 |
K5 |
|
|
A9 (y2y4) |
10011 |
A11 |
1 |
11010 |
J2K5 |
|
|
A10 (y3y6) |
01010 |
A11 A13 A14 |
X5 NX5NX6 NX5X6 |
11010 10010 01000 |
J1 J1K2 K4 |
|
|
A11 (y7) |
11010 |
A12 A13 |
NX1 X1 |
11110 10010 |
J3 K2 |
|
|
A12 (y1y9) |
11110 |
A15 |
1 |
10110 |
K2 |
|
|
A13 (y8) |
10010 |
A15 A3 |
X2 NX2 |
10110 00010 |
J3 K1 |
|
|
A14 (y3) |
01000 |
A3 |
1 |
00010 |
K2J4 |
|
|
A15 (y1y8) |
10110 |
A17 A20 A19 |
X4 NX4X3 NX4NX3 |
10111 00110 10100 |
J5 K1 K4 |
|
|
A16 (y5y9) |
00100 |
A19 A20 A20 A22 |
X4NX3 X4X3 NX4X1 NX4NX1 |
10100 00110 00110 01100 |
J1 J4 J4 J2 |
|
|
A17 (y4) |
10111 |
A18 |
1 |
11111 |
J2 |
|
|
A18 (y4y5) |
11111 |
A21 |
1 |
11101 |
K4 |
|
|
A19 (y3y10) |
10100 |
A21 |
1 |
11101 |
J2 |
|
|
A20 (y6) |
00110 |
A22 |
1 |
01100 |
J2K4 |
|
|
A21 (y1y8) |
11101 |
A23 A26 A25 |
X4 NX4X3 NX4NX3 |
11001 01101 11100 |
K3 K1 K5 |
|
|
A22 (y5y9) |
01100 |
A26 A25 A26 A16 |
X4X3 X4NX3 NX4X1 NX4NX1 |
01101 11100 01101 00100 |
J5 J1 J5 K2 |
|
|
A23 (y4) |
11001 |
A24 |
1 |
10001 |
K2 |
|
|
A24 (y4y5) |
10001 |
A1 |
1 |
10101 |
J3 |
|
|
A25 (y3y10) |
11100 |
A1 |
1 |
10101 |
K2J5 |
|
|
A26 (y6) |
01101 |
A16 |
1 |
00100 |
K2K5 |
Выписываем из таблицы выражения для триггеров:
J1=a6*x4+a8+a11*x1+a11*nx1+a21*x4+a22*nx4*nx1=
a6*x4+a8+a11+a21*x4+a22*nx4*nx1
K1=a3*x5+a3*nx5*x2+a3*nx5*nx2+a9+a10*x5+a15*nx4*x3+a16*x4*x3+a16*nx4*x1+a16*nx4*nx1+a17+a19+a24+a26=
a3*x5+a3+a9+a10*x5+a15*nx4*x3+a16*x4*x3+a16+a17+a19+a24+a26
J2=a2*x5+a9+a10*x5+a10*nx5*x6+a15*nx4*nx3+a16*x4*nx3+a16*nx4*nx1+a18+a20+a21*nx4*nx3+a24
K2=a1+a4*x2+a4*nx2+a11*x1+a12+a14+a19+a22*x4*x3+a22*nx4*x1+
a22*nx4*nx1=
a1+a4+a11*x1+a12+a14+a19+a22*x4*x3+a22
J3=a1+a6*nx4+a7*x6+a15*x4+a19+a22*x4*x3+a22*x4*nx3+a22*nx4*x1+a22*nx4*nx1=a1+a6*nx4+a7*x6+a15*x4+a19+a22
K3=a2*x5+a2*nx5*x2+a2*nx5*nx2+a10*x5+a10*nx5*nx6+a10*nx5*x6+
a16*x4*nx3+a16*x4*x3+a16*nx4*x1+a16*nx4*nx1+a24+a25=
a2+a10+a16+a24+a25
J4=a1+a3*x5+a6*x4+a7*nx6+a10*nx5*x6+a13*x2+a16*x4*x3+a16*nx4*x1+a16*nx4*nx1+a17+a19=a1+a3*x5+a6*x4+a7*nx6+a10*nx5*x6+a13*x2+a16*x4*x3+a16*nx4+a17+a19
K4=a2*nx5*x2+a2*nx5*nx2+a4*x2+a4*nx2+a5*x2+a5*nx2+a9+a14+a15*x4+a15*nx4*nx3+a21*nx4*x3+a21*nx4*nx3+a22*x4*x3+a22*x4*nx3+a22*nx4*x1+a22*nx4*nx1+a24=a2*nx5+a4+a5+a9+a14+a15*x4+a15*nx4*nx3+a21*nx4+a22+a24
J5=a1+a3*x5+a3*nx5*nx2+a6*nx4+a6*x4+a23=a1+a3*x5+a3*nx5*nx2+a6+a23
K5=a4*x2+a5*x2+a10*nx5*x6+a12+a13*x2+a13*nx2+a24=
a4*x2+a5*x2+a10*nx5*x6+a12+a13+a24
Для повышения функциональности схемы можно выделить одинаковые элементы:
Z1 = nx5+nx6 Z5 = nx4+x1
Z2 = x4+nx3 Z6 = nx4+x3
Z3 = nx4+nx1 Z7 = nx4+nx3
Z4 = x4+x3
Выполняем необходимые превращения для представления ФЗ в рамках нужной серии:
J1=a6*x4+a10*x5+a10*z1+a16*z2+a22*z2=n((na6+nx4) (na10+nx5) (na10+nz1) (na16+nz2) (na22+nz2))
J2=a6*nx4+a7*x6+a9+a16*z3+a17+a19+a20=n((na6+x4) (na7+nx6) (na16+nz3)*na9*na17*na19*na20)
J3=a3*nx1+a13*x2+a24=n((na3+x1) (na13+nx2)*na24)
J4=a2*x5+a2*nx5*x2+a5*x2+a7*x6+a14+a16*z4+a16*z5=n((na2+nx5)*
(na2+n (nx5*x2)) (na5+nx2) (na7+nx6) (na16+nz4) (na16+nz5)*na14)
J5=a3*nx5+a5+a15*x4+a22*z4+a22*z5+a25=n((na3+x5) (na15+nx4)*
(na22+nz4) (na22+nz5)*na5*na25)
K1=a1+a13*nx2+a15*z6+a21*z6=n((na1*(na13+x2) (na15+nz6) (na21+nz6))
K2=a10*z1+a11*x1+a12+a14+a22*z3+a23+a25+a26=n((na10+nz1) (na11+nx1) (na22+nz3)*na12*na14*na23*na25*na26)
K3=a2*nx5+a4+a21*x4=n((na2+x5) (na21+nx4)*na4)
K4=a3*x5+a3*nx5*nx2+a4*nx2+a10*nx5*x6+a15*z7+a18+a20=n((na3+ nx5) (na3+n (nx5*nx2)) (na4+x2) ((na10+n (nx5*x6)) (na15+nz7)*na18*na20)
K5=a7*nx6+a8+a9+a21*z7+a26=n((na7+x6) (na21+nz7)*na8*na9*na26)
Формируем функции выходов автомата:
Y1=a7+a12+a15+a21=n (na7*na12*na15*na21)
Y2=a2+a7+a8+a9=n (na2*na7*na8*na9)
Y3=a3+a6+a10+a14+a19+a25=n (na3*na6*na10*na14*na19*na25)
Y4=a6+a9+a17+a18+a23+a24=n (na6*na9*na17*na18*na23*na24)
Y5=a2+a5+a6+a16+a18+a22+a24=n (na2*na5*na6*na16*na18*na22*na24)
Y6=a10+a20+a26=n (na10*na20*na26)
Y7=a4+a11=n (na4*na11)
Y8=a13+a15+a21=n (na13*na15*na21)
Y9=a5+a12+a16+a22=n (na5*na12*na16*na22)
Y10=a19+a25=n (na19*na25)
Мы получили все необходимы выражения для принципиальной схемы. Строим ее пользуясь формулами для триггеров и исходными состояниями.
2.3 Автомат Моли
Кодировку состояний выполняем за алгоритмом, разработанным для D - тригера. Для этого строим таблицу переходов автомата, а потом подсчитываем статистику встреч каждого состояния. Отсортировав состояния, кодируем их так, чтобы те, которые встречаются чаще, имели меньше всего единиц.
b1 - 00000 b3 - 00011 b8 - 00111
b4 - 00001 b7 - 00101 b9 - 01011
b14 - 00010 b10 - 01001 b11 - 10011
b17 - 00100 b12 - 10001 b16 - 10101
b18 - 01000 b2 - 00110 b19 - 11001
b22 - 10000 b5 - 01010 b21 - 11010
b13 - 10010
b6 - 01100
b15 - 10100
b20 - 11000
Записываем результаты в таблицу:
|
Am |
Kam |
As |
Kas |
X |
Y |
ФВ |
|
|
B1 |
00000 |
B2 |
00110 |
1 |
Y2Y5 |
D3D4 |
|
|
B2 |
00110 |
B4 |
00001 |
1 |
Y7 |
D5 |
|
|
B3 |
00011 |
B4 |
00001 |
1 |
Y5Y9 |
D5 |
|
|
B4 |
00001 |
B5 B6 |
01010 01100 |
X2 NX2 |
Y3Y4Y5 Y1Y2 |
D2D4 D2D3 |
|
|
B5 |
01010 |
B7 B8 |
00101 00111 |
NX4 X4 |
Y2 Y2Y4 |
D3D5 D3D4D5 |
|
|
B6 |
01100 |
B4 B7 |
00001 00101 |
NX6 X6 |
Y5Y9 Y2 |
D5 D3D5 |
|
|
B7 |
00101 |
B9 |
01011 |
1 |
Y3Y6 |
D2D4D5 |
|
|
B8 |
00111 |
B10 |
01001 |
1 |
Y7 |
D2D5 |
|
|
B9 |
01011 |
B10 B12 B13 |
01001 10001 10010 |
X5 NX5NX6 NX5X6 |
Y7 Y8 Y3 |
D2D5 D1D5 D1D4 |
|
|
B10 |
01001 |
B11 B12 |
10011 10001 |
NX1 X1 |
Y1Y9 Y8 |
D1D4D5 D1D5 |
|
|
B11 |
10011 |
B14 |
00010 |
1 |
Y1Y8 |
D4 |
|
|
B12 |
10001 |
B3 B14 |
00011 00010 |
NX2 X2 |
Y3 Y1Y8 |
D4D5 D4 |
|
|
B13 |
10010 |
B3 |
00011 |
1 |
Y3 |
D4D5 |
|
|
B14 |
00010 |
B16 B17 B18 |
10101 00100 01000 |
X4 NX4NX3 NX4X3 |
Y4 Y3Y10 Y6 |
D1D3D5 D3 D2 |
|
|
B15 |
10100 |
B17 B18 B18 B20 |
00100 01000 01000 11000 |
X4NX3 X4X3 NX4X1 NX4NX1 |
Y3Y10 Y6 Y6 Y5Y9 |
D3 D2 D2 D1D2 |
|
|
B16 |
10101 |
B17 |
00100 |
1 |
Y4Y5 |
D3 |
|
|
B17 |
00100 |
B19 |
11001 |
1 |
Y1Y8 |
D1D2D5 |
|
|
B18 |
01000 |
B20 |
11000 |
1 |
Y5Y9 |
D1D2 |
|
|
B19 |
11001 |
B1 B21 B22 |
00000 11010 10000 |
NX4NX3 X4 NX4X3 |
Y3Y10 Y4 Y6 |
- D1D2D4 D1 |
|
|
B20 |
11000 |
B1 B15 B22 B22 |
00000 10100 10000 10000 |
X4NX3 NX4NX1 X4X3 NX4X1 |
Y3Y10 Y5Y9 Y6 Y6 |
- D1D3 D1 D1 |
|
|
B21 |
11010 |
B1 |
00000 |
1 |
Y4Y5 |
- |
|
|
B22 |
10000 |
B15 |
10100 |
1 |
Y5Y9 |
D1D3 |
D1= b9*nx5*nx6+b9*nx5*x6+b10*x1+b14*x4+b17+b18+b19nx4*x3+b20*nx4* nx1+b20*x4*x3+b20*nx4*x1+b22= b9*nx5+b10*x1+b14*x4+b17+b18+b19nx4*x3+b20*nx4+b20*x4*x3+b22
D2= b4*x2+b4*nx2+b7+b8+b9*x5+b14*nx4*x3+b15*x4*x3+b15*nx4*x1+b15* nx4*nx1+b17+b18+b19*x4= b4+b7+b8+b9*x5+b14*nx4*x3+b15*x4*x3+b15*nx4+b17+b18+b19*x4
D3= b1+b4*nx2+b5*nx4+b5*x4+b6*x6+b14*x4+b14*nx4*nx3+b15*x4*nx3+ b16+ b20*nx4*nx1+b22= b1+b4*nx2+b5+b6*x6+b14*x4+b14*nx4*nx3+b15*x4*nx3+ b16+b20*nx4*nx1+b22
D4 = b1+b4*x2+b5*x4+b7+b10*nx1+b11+b12*nx2+b12*x2+b13+b19*x4= b1+b4*x2+b5*x4+b7+b10*nx1+b11+b12+b13+b19*x4
D5=b2+b3+b5*nx4+b5*x4+b6*nx6+b6*x6+b7+b8+b9*x5+b9*nx5*nx6+ b10*nx1+b10*x1+b12*nx2+b13+b14*x4+b17= b2+b3+b5+b6+b7+b8+b9*x5+b9*nx5*nx6+ b10+b12*nx2+b13+b14*x4+b17
Исходные состояния автомата Моли:
Y1 = b4*nx2+b10*nx1+b11+b12*x2+b17
Y2 = b1+b4*nx2+b5*nx4+b5*x4+b6*x6= b1+b4*nx2+b5+b6*x6
Y3= b4*x2+b7+b12*nx2+b14*nx4*nx3+b15*x4*nx3+b19*nx4*nx3+b20*x4*nx3
Y4 = b4*x2+b5*x4+b14*x4+b16+b19*x4+b21
Y5 = b1+b3+b4*x2+b6*nx6+b15*nx4*nx1+b16+b18+b20*nx4*nx1+b21+b22
Y6 = b7+b14*nx4*x3+b15*x4*x3+b15*nx4*x1+b19*nx4*x3+b20*x4*x3+ b20*nx4*x1
Y7 = b2+b8+b9*x5
Y8 = b9*nx5*nx6+b10*x1+b11+b12*x2+b17
Y9 = b3+b6*nx6+b10*nx1+b15*nx4*nx1+b18+b20*nx4*nx1+b22
Y10 = b14*nx4*nx3+b18*x4*nx3+b19*nx4*nx3+b20*x4*nx3
Мы получили соответствующие выражения для функций возбуждения и исходных состояний автомата Моли. За необходимостью можно представить их в рамках некоторой серии элементов и построить принципиальную схему.
Заключение
В ходе проекта мы получили комбинационную схему булевой функции в заданном базисе и построили принципиальную схему управляющего автомата Мура.
Синтез автомата был выполнен с учетом серии КР 1533, потому может быть сделан и опробований в реальной жизни. В целом курсовая работа довела свою важность в закреплении полученных знаний и приобретении ряда привычек относительно проектирования цифровых автоматов.
Размещено на Allbest.ru
Подобные документы
Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012Разработка функциональной схемы управляющего микропрограммного автомата. Построение графов автомата для модели Мили и Мура. Кодирование состояний для модели Мура на D-триггерах. Алгоритм умножения чисел в дополнительном коде с простой коррекцией.
курсовая работа [764,0 K], добавлен 27.08.2012Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench.
курсовая работа [964,2 K], добавлен 20.07.2015Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012Общая структура и принцип функционирования синхронного управляющего автомата. Анализ граф схемы алгоритма управляющего автомата и детализация блока памяти. Структурный синтез логического преобразователя и разработка электрической функциональной схемы.
курсовая работа [222,6 K], добавлен 19.02.2013Теоретические основы эквивалентности конечных автоматов-распознавателей и их минимизация. Определение математических моделей Мили и Мура. Их графическое и табличное представление. Примеры построения конечных автоматов, распознающих некоторые языки.
курсовая работа [567,8 K], добавлен 02.05.2015Оптимізація схеми мікропрограмного автомата Мура за рахунок нестандартного подання кодів станів. Аналіз методів синтезу автомата та аналіз сучасного елементного базису. Використанні особливостей автомата для зменшення площини матричної схеми автомата.
презентация [357,0 K], добавлен 16.10.2013Понятие и назначение дискретного (цифрового) автомата, сферы и правила его использования. Граф-дерево автомата Мура и мили, их отличительные черты. Таблица переходов с распределением неопределённостей. Представление функции возбуждения и ее минимизация.
курсовая работа [423,7 K], добавлен 11.10.2008Граф-схема автомата Мура та Мілі. Структурний синтез автомата Мура. Кодування станів. Функції збудження тригерів та вихідних сигналів. Переведеня у базис. Структурний синтез автомата Мілі. Кодування станів. Функції збудження тригерів та вихідних сигналів.
курсовая работа [114,6 K], добавлен 28.02.2009Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012
