000001011010110111101100
|
|
|
|
|
|
|
|
|
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 =
Для реализации функции по останьому выражению необходимо 16
элементов 3И-НЕТ (Рис. 1). Ранг данной схемы равняется 4, что негативно
отображается на скорости. Использовал факторный алгоритм возможно улучшить
схему, увеличить скорость его работы.
Рис. 1 Функциональная схема для заданного базиса
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)
│ 2 │ 1
│ 24│ 1
│ 25│ 1
│ 4 │ 1
│ 6 │ 1
│ 7 │ 1
│ 5 │ 1
│ 6 │ 1
│ 7 │ 1
│ 13 │ 1
│ 14 │ 1
│ 6 │ 1
│ 7 │ 1
│ 6 │ 1
│ 7 │ 2
│ 8 │ 1
│ 9 │ 1
│ 8 │ 1
│ 10 │ 1
│ 11 │ 1
│ 11 │ 1
│ 13 │ 1
│ 14 │ 1
│ 12 │ 1
│ 13 │ 1
│ 15 │ 1
│ 15 │ 1
│ 17 │ 1
│ 19 │ 1
│ 20 │ 1
│ 19 │ 1
│ 20 │ 2
│ 22 │ 2
│ 26 │ 1
│ 18 │ 1
│ 21 │ 1
│ 21 │ 1
│ 22 │ 1
│ 23 │ 1
│ 25 │ 1
│ 26 │ 1
│ 25 │ 1
│ 26 │ 2
│ 24 │ 1(1) = 3(2) = 4(3) = 5(4) =
3(5) = 3(6) = 6(7) = 5(8) = 3(9) = 2(10) = 4(11) = 4(12) = 2(13) = 4(14) =
2(15) = 5(16) = 4(17) = 2(18) = 2(19) = 3(20) = 3(21) = 5(22) = 4(23) = 2(24) =
2(25) = 3(26) = 3
Дальше согласно правил алгоритма строим матрицу М
║M║ =│ j │ P (i, j)
│ 7 │ 2
│ 7 │ 1
│ 6 │ 1
│ 6 │ 1
│ 7 │ 1
│ 13 │ 1
│ 6 │ 1
│ 6 │ 1
│ 8 │ 1
│ 15 │ 1
│ 5 │ 1
│ 7 │ 1
│ 9 │ 1
│ 8 │ 1
│ 13 │ 1
│ 11 │ 1
│ 13 │ 1
│ 19 │ 1
│ 20 │ 1
│ 20 │ 2
│ 22 │ 2
│ 26 │ 2
│ 21 │ 1
│ 25 │ 1
│ 26 │ 1
│ 2 │ 1
│ 4 │ 1
│ 14 │ 1
│ 10 │ 1
│ 15 │ 1
│ 17 │ 1
│ 19 │ 1
│ 26 │ 1
│ 21 │ 1
│ 22 │ 1
│ 23 │ 1
│ 25 │ 1
│ 25 │ 1
│ 11 │ 1
│ 14 │ 1
│ 12 │ 1
│ 24 │ 1
│ 18 │ 1
│ 24 │ 1
Определяем разрядность кода для кодировки
состояний автомата
R =] log2 N [=] log2 26 [= 5
Результаты кодировки:
a1
1010100101000100011100000000110000101011100110101011010111101001001000101100010010111111111010000110111010110011001100011110001101
Подсчет эффективности кодировки:
Количество переключений триггеров:
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
Минимально возможное количество переключений триггеров:
= 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=*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=*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=a1+a4*x2+a4*nx2+a11*x1+a12+a14+a19+a22*x4*x3+a22*nx4*x1+*nx4*nx1=+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=a2*x5+a2*nx5*x2+a2*nx5*nx2+a10*x5+a10*nx5*nx6+a10*nx5*x6+*x4*nx3+a16*x4*x3+a16*nx4*x1+a16*nx4*nx1+a24+a25=+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=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=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=*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+nx34 = x4+x3
Выполняем необходимые превращения для представления ФЗ в
рамках нужной серии:
J1=a6*x4+a10*x5+a10*z1+a16*z2+a22*z2=n((na6+nx4)
(na10+nx5) (na10+nz1) (na16+nz2)
(na22+nz2))=a6*nx4+a7*x6+a9+a16*z3+a17+a19+a20=n((na6+x4) (na7+nx6)
(na16+nz3)*na9*na17*na19*na20)=a3*nx1+a13*x2+a24=n((na3+x1)
(na13+nx2)*na24)=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)=a3*nx5+a5+a15*x4+a22*z4+a22*z5+a25=n((na3+x5) (na15+nx4)*
(na22+nz4)
(na22+nz5)*na5*na25)=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)=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)=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)=a3+a6+a10+a14+a19+a25=n (na3*na6*na10*na14*na19*na25)=a6+a9+a17+a18+a23+a24=n
(na6*na9*na17*na18*na23*na24)=a2+a5+a6+a16+a18+a22+a24=n
(na2*na5*na6*na16*na18*na22*na24)=a10+a20+a26=n (na10*na20*na26)=a4+a11=n
(na4*na11)=a13+a15+a21=n (na13*na15*na21)=a5+a12+a16+a22=n (na5*na12*na16*na22)10=a19+a25=n (na19*na25)
Мы получили все необходимы выражения для принципиальной
схемы. Строим ее пользуясь формулами для триггеров и исходными состояниями.
.3 Автомат Моли
Кодировку состояний выполняем за алгоритмом, разработанным
для D - тригера. Для этого строим таблицу переходов автомата, а потом
подсчитываем статистику встреч каждого состояния. Отсортировав состояния,
кодируем их так, чтобы те, которые встречаются чаще, имели меньше всего единиц.
b1 - 00000 b3 - 00011 b8 - 00111-
00001 b7 - 00101 b9 - 01011- 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 - 0110015 - 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
|
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+b215
= b1+b3+b4*x2+b6*nx6+b15*nx4*nx1+b16+b18+b20*nx4*nx1+b21+b226 =
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+b179
= b3+b6*nx6+b10*nx1+b15*nx4*nx1+b18+b20*nx4*nx1+b2210 =
b14*nx4*nx3+b18*x4*nx3+b19*nx4*nx3+b20*x4*nx3
Мы получили соответствующие выражения для функций возбуждения
и исходных состояний автомата Моли. За необходимостью можно представить их в рамках
некоторой серии элементов и построить принципиальную схему.
Заключение
В ходе проекта мы получили комбинационную схему булевой
функции в заданном базисе и построили принципиальную схему управляющего
автомата Мура.
Синтез автомата был выполнен с учетом серии КР 1533, потому
может быть сделан и опробований в реальной жизни. В целом курсовая работа
довела свою важность в закреплении полученных знаний и приобретении ряда
привычек относительно проектирования цифровых автоматов.