Синтез комбинационной схемы и проектирование управляющего автомата Мура

1 Синтез комбинационной схемы

1.1 Определение значений БФ

Булевая функция 5 переменных F (x1, x2, x3, x4, x5) задается своими значениями, которые определяются 7-разрядовими двоичными эквивалентами чисел: по значению чисел А, В (на наборах 7−13), С (наборы 14−20), по значению (наборы 21−27) и на наборах 28−31 функции принимает неопределенные значения.

А=13 эквивалентно 4910=1 100 012.

Проставляем символ неопределенного значения Х110 001.

В=07 эквивалентно 1010=10 102.

Проставляем символ неопределенного значения ХХХ1010.

С=21 эквивалентно 2310=101 112.

Проставляем символ неопределенного значения XХ10 111.

А+В+С=41 эквивалентно 7210=10 010 002.

Соответственно, значение функций F (x1, x2, x3, x4, x5) на наборах от 0 до 31 будет иметь вид

Таблица 1

1.2 Минимизация БФ

Получаем МДНФ и МКНФ булевой функции с помощью метода карт Карно. Схемы карт Карно приведены ниже.

Таблица 2 Карта Карно к МДНФ

В результате минимизации, получим:

_ _ _ _ _ _ _ _ _ _ _ _ _

Y=X₁X₃X₄+X₂X₄X₅+X₃X₄X₅+X₁X₂X₃X₄+X₁X₄X₅+X₁X₃X₄

Таблица 3 Карта Карно к МКНФ

В результате минимизации, получим:

_ _ _ _ _ _ _ _ _ _

y=(X₁+X₂+X₄+X₅) (X₁+X₃ +X₄ +X₅) (X₁+ X₃+ X₄+ X₅) (X₁+X₂+ X₄) (X₁+X₃+ X₄)

_ _

(X₁+X₃+X₅)

1.3 Описание минимизации БФ заданными методами

Для выбора минимальной из МДНФ и МКНФ оценим сложность схемы с помощью цены по Квайну. Цена по Квайну определяется как суммарное число входов логических элементов в составе схемы.

Такой подход обусловлен тем, что

— сложность схемы легко вычисляется по БФ, на основе которых строится схема: для ДНФ сложность равняется сумме количества букв, (букве со знаком отвечает цена 2) и количество знаков дизъюнкции, увеличенного на 1 для каждого дизъюнктивного выражения.

— все классические методы минимизации БФ обеспечивают минимальность схеме именно в содержании цены по Квайну.

Схема с минимальной ценой по Квайну часто реализуется с наименьшим числом конструктивных элементов — корпусов интегральных микросхем.

Для данных функций мы имеем:

C_кв (МДНФ)=19+6+5=30;

C_кв(МКНФ)=21+6+5=32.

Так как минимальной ценой является Cкв (МКНФ), то для реализации схемы будем использовать МДНФ.

1.4 Приведение БФ к заданному базису

Заданный базис: 3 И-НЕТ.

Приведем выражение к заданному базису:

_ _ _ _ _ _ _ _ _ _ _ _ _

Y=X₁X₃X₄+X₂X₄X₅+X₃X₄X₅+X₁X₂X₃X₄+X₁X₄X₅+X₁X₃X₄ =

=X₃(X₁X_4*X₄X_5*X₁X₂X₄)_*X₅(X₂X_4*X₁X₄)_*X₁X₃X₄

Для реализации функции по останьому выражению необходимо 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.

Получаем 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 10 101

a2 101

a3 10

a4 111

a5 0

a6 11

a7 1

a8 1 011

a9 10 011

a10 1 010

a11 11 010

a12 11 110

a13 10 010

a14 1 000

a15 10 110

a16 100

a17 10 111

a18 11 111

a19 10 100

a20 110

a21 11 101

a22 1 100

a23 11 001

a24 10 001

a25 11 100

a26 1 101

Подсчет эффективности кодировки:

Количество переключений триггеров:

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

Выписываем из таблицы выражения для триггеров:

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

Для повышения функциональности схемы можно выделить одинаковые элементы:

Z₁ = nx5+nx6 Z₅ = nx4+x1

Z₂ = x4+nx3 Z₆ = nx4+x3

Z₃ = nx4+nx1 Z₇ = nx4+nx3

Z₄ = 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 — 0 b3 — 11 b8 — 111

b4 — 1 b7 — 101 b9 — 1 011

b14 — 10 b10 — 1 001 b11 — 10 011

b17 — 100 b12 — 10 001 b16 — 10 101

b18 — 1 000 b2 — 110 b19 — 11 001

b22 — 10 000 b5 — 1 010 b21 — 11 010

b13 — 10 010

b6 — 1 100

b15 — 10 100

b20 — 11 000

Записываем результаты в таблицу:

D₁= 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

D₂= 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

D₃= 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

D₄ = 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

D₅=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

Исходные состояния автомата Моли:

Y₁ = b4*nx2+b10*nx1+b11+b12*x2+b17

Y₂ = b1+b4*nx2+b5*nx4+b5*x4+b6*x6= b1+b4*nx2+b5+b6*x6

Y₃= b4*x2+b7+b12*nx2+b14*nx4*nx3+b15*x4*nx3+b19*nx4*nx3+b20*x4*nx3

Y₄ = b4*x2+b5*x4+b14*x4+b16+b19*x4+b21

Y₅ = b1+b3+b4*x2+b6*nx6+b15*nx4*nx1+b16+b18+b20*nx4*nx1+b21+b22

Y₆ = b7+b14*nx4*x3+b15*x4*x3+b15*nx4*x1+b19*nx4*x3+b20*x4*x3+ b20*nx4*x1

Y₇ = b2+b8+b9*x5

Y₈ = b9*nx5*nx6+b10*x1+b11+b12*x2+b17

Y₉ = b3+b6*nx6+b10*nx1+b15*nx4*nx1+b18+b20*nx4*nx1+b22

Y₁₀ = b14*nx4*nx3+b18*x4*nx3+b19*nx4*nx3+b20*x4*nx3

Мы получили соответствующие выражения для функций возбуждения и исходных состояний автомата Моли. За необходимостью можно представить их в рамках некоторой серии элементов и построить принципиальную схему.

Заключение

В ходе проекта мы получили комбинационную схему булевой функции в заданном базисе и построили принципиальную схему управляющего автомата Мура.

Синтез автомата был выполнен с учетом серии КР 1533, потому может быть сделан и опробований в реальной жизни. В целом курсовая работа довела свою важность в закреплении полученных знаний и приобретении ряда привычек относительно проектирования цифровых автоматов.