Перелік використаної літератури.

Синтез комбінаційної схеми

1.1 Визначення значень БФ

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

     А=13 еквівалентно 49₁₀=110001₂.

     Проставляємо символ невизначеного значення Х110001.

     В=07 еквівалентно 10₁₀=1010₂.

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

     С=21 еквівалентно 23₁₀=10111₂.

Проставляємо символ невизначеного значення XХ10111.

     А+В+С=41  еквівалентно 72₁₀=1001000₂.

Відповідно, значення функцій F(x1,x2,x3,x4,x5) на наборах від 0 до 31 буде мати вигляд:                            

Таблиця 1

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=X₁X₃X₄+X₂X₄X₅+X₃X₄X₅+X₁X₂X₃X₄+X₁X₄X₅+X₁X₃X₄

 Таблиця 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=(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 Функціональна схема для заданого базису

Проектування автоматів

Вибір завдання.

Граф-схеми алгоритмів обираються кожним студентом в індивідуальному порядку. Вона складається з чотирьох блоків: 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 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

Виписуємо з таблиці вирази для тригерів (та виконуємо необхідні перетворення для представлення їх в рамках потрібної серії): 

       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)

Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами (Лист 1).

Автомат Мілі.

Кодування станів виконуємо за алгоритмом, розробленим для 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

Вносимо результати в таблицю:

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

Ми отримали відповідні вирази для функцій збудження і вихідних станів автомата Мілі. За необхідністю можна представити їх в рамках деякої

серії елементів і побудувати принципову схему.

Заключення

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

Синтез автомата був виконаний з урахуванням серії КР 555, тому може бути

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

Перелік використаної літератури.

1. Методичні вказівки до курсової роботи по дисципліні “Прикладна теорія ци фрових автоматів”. Одеса. ОГПУ. 1998р.

2. Мікросхеми серії 1533(555). Стислі теоретичні дані. Одеса. Центр

НТТМ ОГПУ. 1975г.

3. ГОСТ 2.708-81 ЄСКД. Правила виконання електричних схем цифрової  обчи слювальної техніки.

4. ГОСТ 2.743-82. ЄСКД. Умовні графічні позначення в схемах. Елементи цифрової техніки.