Прикладна теорія цифрових автоматів 3

Міністерство освіти і науки України

	ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ



	Кафедра комп’ютерних інтелектуальних систем та мереж













Курсове проектування

з дисципліни

„Прикладна теорія цифрових автоматів”











Виконав: студент гр.



















Одеса 2002


1.ВИБІР ВАРІАНТА ЗАВДАННЯ



Граф-схеми алгоритмів обираються кожним студентом в індивідуальному порядку. Вона складається з чотирьох блоків: E, F, G, H. Студенти обирають граф-схему із п’яти блоків з номерами 0...4 на підставі чисел А, В, С та (А+В+С) за наступними правилами:

- блок "Е" – схема під номером (А) mod 5 = 27 mod 5 = 2;

- блок "F" – схема під номером (В) mod 5 = 6 mod 5 = 1;

- блок "G" – схема під номером (С) mod 5 = 13 mod 5 = 3;

- блок "H" – схема під номером (А+В+С) mod 5 = 46 mod 5 = 1.

Блоки E, F, G, H з’єднуються між собою згідно зі структурною схемою графа, яка показана на рис. 10 у методичних вказівках.

Розташування обирається з використанням номера групи. Тип тригера знаходимо по таблиці на підставі числа (А) mod 3 = 27 mod 3 = 0.	



(A) mod 3 

 ТИП ТРИГЕРА 

 0 

Т

 D 

 1 

D

 JK

 2 

JK

 T 

автомат

Мілі

 Мура 

Табл.1



З табл.1 отримуємо T-тригер для автомата Мілі та D-тригер для Мура. 

Серія інтегральних мікросхем для побудови принципових схем синтезованих автоматів для мого варіанта завдання – КР1533.

Після відповідної розмітки будуємо граф-схему для обоіх автоматів: 


2. ОСНОВНА ЧАСТИНА



2.1. Структурний синтез автомата Мура



2.1.1. Кодування станів

 Кодування станів буде проводитися за таким алгоритмом:

	Кожному стану автомата аm (m = 1,2,...,M) ставиться у відповідність ціле число Nm, рівне числу переходів у стан аm (Nm дорівнює числу появ аm у поле таблиці ).

	Числа N1, N2, ..., Nm упорядковуються по убуванні. 

	Стан аs з найбільшим Ns кодується кодом: де R-кількість елементів пам'яті. 

	Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1:00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00. 

	Для станів, що залишилися, знову в порядку списку п.2. використовують коди з двома одиницями, потім із трьома і так далі поки не будуть закодовані всі стани. 

У результаті виходить таке кодування, при якому чим більше мається переходів у деякий стан, тим менше одиниць у його коді. Вираження для функцій збудження будуть простіше для D-тригерів, тому що функції порушення однозначно визначаються кодом стану переходу.

Статистика:

a1 2стана

a2 1стан

a3 2стана

a4 1стан

a5 2стана

a6 1стан

a7 1стан

a8 2стана

a9 2стана

a10 1стан

a11 2стана

a12 1стан

a13 1стан

a14 2стана

a15 2стана

a16 2стана

a17 2стана

a18 2стана

a19 1стан

a20 2стана

a21 2стана

a22 2стана

a23 1стан

a24 2стана

a25 3стана

Результати кодування:

a1 00011

a2 10011

a3 00110

a4 10101

a5 00101

a6 11001

a7 01011

a8 01100

a9 01010

a10 01101

a11 01001

a12 00111

a13 01110

a14 11000

a15 10100

a16 10010

a17 10001

a18 10000

a19 10110

a20 01000

a21 00100

a22 00010

a23 11010

a24 00001

a25 00000



Табл.2. Таблиця переходів D-тригера 

Am	Kam

As(y)	X

Kas

D1D2D3D4D5

a13

a17	

a1(-)

1

00011

D4D5

D4D5

a1	

a2(y2y4)

1

10011	D1

D4D5

a2

a18

a3(y7)

1

X5 

00110

D3D4

D3D4

a3

a4(y1y9)

NX1

10101

D1

D3

 D5

a4

a14

a5(y1y8)

1

X2

00101

D3

D5

D3

D5

a5

a6(y4)

X4

11001

D1D2 

D5

a6

a7(y4y5)

1

01011

D2

 D4D5

a7

a15

a8(y2y4)

1

1

01100

D2D3

D2D3

a8

a22

a9(y7)

1

X5

01010

D2 

D4

D2

D4

a9

a10(y1y9)

NX1

01101

D2D3

D5

a10

a16

a11(y1y8)

1

X2

01001

D2

D5

D2

D5

a11

a12(y4)

X4

00111

D3D4D5

a12

a13(y4y5)

1

01110

D2D3D4

a3

a18

a14(y8)

X1

NX5NX6

11000

D1D2

D1D2

a5

a20

a15(y3y10)

NX4NX3

X4NX3

10100

D1

D3

D1

D3

a9

a22

a16(y8)

X1

NX5NX6

10010

D1

D4

D1

D4  

a11

a24

a17(y3y10)

NX4NX3

X4NX3

10001

D1

D5

D1

D5

a21

a20

a18(y3y6)

1

NX4NX1

10000

D1

D1

a18

a19(y3)

NX5X6	10110

D1

D3D4 

a19

a14

a20(y5y9)

1

NX2

01000

D2

D2

a20

a20

a21(y6)

X4X3

NX4X1

00100

D3

D3

a25

a24

a22(y3y6)

1

NX4NX1

00010 

D4

D4

a22

a23(y3)

NX5X6

11010

D1D2

D4

a23

a16

a24(y5y9)

1

NX2

00001

D5

D5

a24

a24

a11

a25(y6)

X4X3

NX4X1

NX4

X3

00000





2.1.2. Функції збудження тригерів та вихідних сигналів

Введемо слідуючі позначення: 

	Б= a20NХ4NХ1	Х=a3X1

	В= a14NХ2	Ц=a18NX5NX6

	Г= a20Х4Х3	Ч=a5NX4NX3

	Д=a20NХ4Х1	Ш=a20X4NX3

	Е=a18X5	Э=a9X1

	Ж=a3NX1	Ю=a22NX5NX6

	З= a24NХ4NХ1	Я=a11NX4NX3

	И=a14X2	Щ=a24X4NX3

	К=a5X4	Ь=a18NX5X6

	Л= a16NХ2	Ы=a22NX5X6

 П=a22X5

Р=a9NX1

Т=a16X2

У=a11X4

Виписуємо з таблиці вирази для тригерів:

D1=a1+Ж+К+Ы+Х+Ц+Ч+Ш+Э+Ю+Я+Щ+a21+Б+Ь 

D2=К+a6+a7+a15+a8+П+Р+a10+Т+Х+Ц+а12+a19+В+Ы

D3=a2+Е+Ж+a4+И+a7+a15+Р+У+a12+Ч+Ш+Г+Д+Ь

D4= a13+a17+a1+a2+Е+a6+a8+П+У+a12+Э+Ю+Ь+a25+З+Ы

D5=a13+a17+a1+Ж+a4+И+К+a6+Р+a10+Т+У+Я+Щ+a23+Л

Формуємо функції виходів автомата:

Y1=a4+a5+a10+a11

Y2=a2+a8

Y3=a15+a17+a18+a19+a22+a23

Y4=a2+a6+a7+a8+a12+a13

Y5=a7+a13+a20+a24

Y6=a18+a21+a22+a25

Y7=a3+a9

Y8=a5+a11+a14+a16

Y9=a4+a10+a20+a24

Y10=a15+a17



2.1.3. Переведеня у базис:

D1= a1+Ж+К+Ы+Х+Ц+Ч+Ш+Э+Ю+Я+Щ+a21+Б+Ь=

=Na1∙NЖ∙NК∙NЫ∙NХ∙NЦ∙NЧ∙NШ+NЭ∙NЮ∙NЯ∙NЩ∙Na21∙NБ∙NЬ 

D2= К+a6+a7+a15+a8+П+Р+a10+Т+Х+Ц+а12+a19+В+Ы=

=NК∙Na6∙Na7∙Na15∙Na8∙NП∙NР∙Na10+NТ∙NХ∙NЦ∙Nа12∙Na19∙NВ∙NЫ

D3= a2+Е+Ж+a4+И+a7+a15+Р+У+a12+Ч+Ш+Г+Д+Ь=

=Na2∙NЕ∙NЖ∙Na4∙NИ∙Na7∙Na15∙NР+NУ∙Na12∙NЧ∙NШ∙NГ∙NД∙NЬ

D4= a13+a17+a1+a2+Е+a6+a8+П+У+a12+Э+Ю+Ь+a25+З+Ы 

=Na13∙Na17∙Na1∙Na2∙NЕ∙Na6∙Na8∙NП+NУ∙Na12∙NЭ∙NЮ∙NЬ∙Na25∙NЗ∙NЫ

D5= a13+a17+a1+Ж+a4+И+К+a6+Р+a10+Т+У+Я+Щ+a23+Л=

=Na13∙Na17∙Na1∙NЖ∙Na4∙NИ∙NК∙Na6+NР∙Na10∙NТ∙NУ∙NЯ∙NЩ∙Na23∙NЛ

Y1=a4+a5+a10+a11=Na4∙Na5∙Na10∙Na11

Y2=a2+a8= Na2∙Na8

Y3=a15+a17+a18+a19+a22+a23= Na15∙Na17∙Na18∙Na19∙Na22∙Na23

Y4=a2+a6+a7+a8+a12+a13= Na2∙Na6∙Na7∙Na8∙Na12∙Na13

Y5=a7+a13+a20+a24= Na7∙Na13∙Na20∙Na24

Y6=a18+a21+a22+a25= Na18∙Na21∙Na22∙Na25

Y7=a3+a9= Na3∙Na9

Y8=a5+a11+a14+a16= Na5∙Na11∙Na14∙Na16

Y9=a4+a10+a20+a24= Na4∙Na10∙Na20∙Na24

Y10=a15+a17= Na15∙Na17

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



2.2. Структурний синтез автомата Мілі



2.2.1. Кодування станів

Аналіз канонічного методу структурного синтезу автомата показує, що різні варіанти кодування станів автомата приводять до різних виражень функцій збудження пам'яті і функцій виходів, у результаті чого складність комбінаційної схеми істотно залежить від обраного кодування.

	Мы повинні кодувати стани автомату з допомогою евристичного алгоритму кодування, тому що у мене Т-тригер.

Даний алгоритм мінімізує сумарне число переключень елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базі T, RS, JK-тригерів. Для даних типів тригерів (на відміну від D-тригерів) на кожнім переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа переключень тригерів приводить до зменшення кількості одиниць відповідних функцій збудження, що при відсутності мінімізації однозначно приводить до спрощення комбінаційної схеми автомата.

Будую матрицю |T|, яка складається із всіх пар номерів (i, j), для яких P(i, j)  0, ij. Для кожної пари вказуємо її вагу. 

║T║ =

 i │ j │ P(i,j)

 1 │ 2 │ 1

 1 │ 11 │ 1

 1 │ 12 │ 1

 1 │ 21 │ 1

 2 │ 3 │ 1

 3 │ 4 │ 1

 3 │ 13 │ 1

 3 │ 15 │ 1

 4 │ 5 │ 1

 5 │ 6 │ 1

 5 │ 7 │ 1

 5 │ 13 │ 1

 5 │ 18 │ 1

 6 │ 7 │ 1

 7 │ 8 │ 1 

 7 │ 17 │ 1

 

 8 │ 9 │ 1

 9 │ 10 │ 1

 9 │ 14 │ 1

 9 │ 19 │ 1

 10 │ 11 │ 1

 11 │ 12 │ 1

 11 │ 14 │ 1

 11 │ 22 │ 1

 13 │ 15 │ 1

 13 │ 17 │ 1

 14 │ 19 │ 1

 14 │ 21 │ 1

 15 │ 16 │ 1

 15 │ 17 │ 1

 15 │ 18 │ 1

 16 │ 17 │ 1

 17 │ 18 │ 2

 19 │ 20 │ 1

 19 │ 21 │ 1

 19 │ 22 │ 1

 20 │ 21 │ 1

 21 │ 22 │ 2

Підраховуємо вагу всіх компонентів всіх пар 

 P(1) = 4

P(2) = 2

P(3) = 4

P(4) = 2

P(5) = 5

P(6) = 2

P(7) = 4

P(8) = 2

P(9) = 4

P(10) = 2

P(11) = 5

P(12) = 2

P(13) = 4

P(14) = 4

P(15) = 5

P(16) = 2

P(17) = 5

P(18) = 3

P(19) = 5

P(20) = 2

 P(21) = 5

 P(22) = 3

Далі згідно правил алгоритму будуємо матрицю М

 i │ j │ P(i,j)

 17 │ 18 │ 2

 15 │ 17 │ 1

 3 │ 15 │ 1

 7 │ 17 │ 1

 5 │ 7 │ 1

 5 │ 13 │ 1

 13 │ 15 │ 1

 13 │ 17 │ 1

 3 │ 13 │ 1

 5 │ 18 │ 1

 15 │ 18 │ 1

 4 │ 5 │ 1

 5 │ 6 │ 1

 15 │ 16 │ 1

 16 │ 17 │ 1

 2 │ 3 │ 1

 1 │ 2 │ 1

 1 │ 11 │ 1

 1 │ 21 │ 1

 21 │ 22 │ 2

 19 │ 21 │ 1

 9 │ 19 │ 1

 11 │ 14 │ 1

 14 │ 19 │ 1

 14 │ 21 │ 1

 9 │ 14 │ 1

 11 │ 22 │ 1

 19 │ 22 │ 1

 10 │ 11 │ 1

 11 │ 12 │ 1

 19 │ 20 │ 1

 20 │ 21 │ 1

 1 │ 12 │ 1

 3 │ 4 │ 1

 6 │ 7 │ 1

 7 │ 8 │ 1

 8 │ 9 │ 1

 9 │ 10 │ 1

Визначемо розрядність кода для кодування станів автомата

R = ] log2 N [ = ] log2 22 [ = 5

Результати кодування:

 b1 01011

 b2 01111

 b3 00111

 b4 01101

 b5 00101

 b6 01100

 b7 00100

 b8 10100

 b9 10000

b10 11000

b11 11010

b12 01010

b13 00110

b14 11001

 b15 00011

b16 00010

b17 00000

b18 00001

b19 10001

b20 10101

b21 10011

b22 10010

Підрахунок ефективності кодування:

Кількість перемикань тригерів:

 W = E P(i,j)*d(i,j) = P(1,2)*d(1,2) + P(1,11)*d(1,11) + P(1,12)*d(1,12) + P(1,21)*d(1,21) + P(2,3)*d(2,3) + P(3,4)*d(3,4) + P(3,13)*d(3,13) + P(3,15)*d(3,15) + P(4,5)*d(4,5) + P(5,6)*d(5,6) + P(5,7)*d(5,7) + P(5,13)*d(5,13) + P(5,18)*d(5,18) + P(6,7)*d(6,7) + P(7,8)*d(7,8) + P(7,17)*d(7,17) + P(8,9)*d(8,9) + P(9,10)*d(9,10) + P(9,14)*d(9,14) + P(9,19)*d(9,19) + P(10,11)*d(10,11) + P(11,12)*d(11,12) + P(11,14)*d(11,14) + P(11,22)*d(11,22) + P(13,15)*d(13,15) + P(13,17)*d(13,17) + P(14,19)*d(14,19) + P(14,21)*d(14,21) + P(15,16)*d(15,16) + P(15,17)*d(15,17) + P(15,18)*d(15,18) + P(16,17)*d(16,17) + P(17,18)*d(17,18) + P(19,20)*d(19,20) + 

 P(19,21)*d(19,21) + P(19,22)*d(19,22) + P(20,21)*d(20,21) + P(21,22)*d(21,22) = 

 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 = 52

Мінімально можлива кількість перемикань тригерів

Wmin = E P(i,j) = 40

Коефіціент ефективності кодування: 1.30



Табл.3. Таблиця переходів Т-тригера

		Am

	Kam

As

Kas

X

Y

ФЗ

	b1

	01011

b2

01111

1

Y2Y4

          T3

	b2

	01111

b3

00111

1

Y7

     T2

	b3

	00111

b4

b13

01101

00110

NX1

X1

Y1Y9

Y8

     T2       T4

                     T5

	b4

	01101

b5

00101

1

Y1Y8

     T2

	b5

	00101

b6

b7

b18

01100

00100

00001

X4

NX4NX3

NX4X3

Y4

Y3Y10

Y6

     T2            T5

                      T5

T3

	b6

	01100

b7

00100

1

Y4Y5

     T2

	b7

	00100

b8

10100

1

Y2Y4

T1 

	b8

	10100

b9

10000

1

Y7

T3

	b9

	10000

b10

b14

11000

11001

NX1

X1

Y1Y9

Y8

     T2

     T2            T5

	b10

	11000

b11

11010

        1

Y1Y8

            T4

	b11

	11010

b12

b1

b22

01010

01011

10010

X4

NX4NX3

NX4X3

Y4

Y3Y10

Y6

T1       

T1                 T5

     T2

	b12

	01010

b1

01011

1

Y4Y5

                      T5

	b13

	00110

b5

b17

00101

00000

X2

NX2

Y1Y8

Y5Y9

                 T4T5

           T3  T4

	b14

	11001

b11

b21

11010

10011

X2

NX2

Y3Y10

Y6

                 T4T5

   T2        T4

	b15

	00011

b3

b13

b16

00111

00110

00010

X5

NX5NX6

NX5X6

Y7

Y8

Y3

T3

           T3      T5

                      T5

	b16

	00010

b17

00000

1

Y5Y9

             T4

	b17

	00000

b7

b18

b18

b15

00100

00001

00001

00011

X4NX3

X4X3

NX4X1

NX4NX1

Y3Y10

Y6

Y6

Y3Y6

T3 

T5

T5

T4T5



2.2.2. Функції збудження тригерів та вихідних сигналів

Введемо слідуючі позначення:

A=b3NX1 П=b21Х4NX3 

	Б=b5X4	Р= b5NX4Х3

	H=b9X1 С=В15Х5

	Г=b11X4	Т= b17Х4NX3

	Д=b13X2	У= b19NX5X6

	Е=b13NX2	Ф= b21NX4NX1

	Ж=b14X2	Х= b3Х1

	З=b14NX2	Ц= b5NX4NX3

	И=b15NX5NX6	Ч= b11NX4NX3

	К=b17NX4NX1	Ш= b15NX5X6

	Л=b9NX1	Щ= b17X4X3

	М=b11NX4X3	Э= b17NX4X1

	O= b19NX5NX6	Ю= b21X4X3

	Я= b21NX4X1	В=В19Х5

 Виписуємо з таблиці вирази для тригерів: 

 T1=b7+Г+Ч+П 

Т2=b2+А+b4+Б+b6+Л+Н+М+З+О+П 

 Т3=b1+Р+b8+Е+С+И+Т+У+b20

Т4 =А+b10+Д+Е+Ж+З+b16+К+b18+b20+Ф+b22 

 Т5=Х+Б+Ц+H+Ч+b12+Д+Ж+И+Ш+Щ+Э+K+Ю+Я+b22

 Формуємо функції виходів автомата:

 Y1=А+b4+Л+b10+Д

 Y2=b1+b7

 Y3=Ц+Ч+Ж+Ш+Т+К+b18+У+П+Ф+b22

 Y4=b1+Б+b6+b7+Г+b12

 Y5=b6+b12+Е+b16+b20

 Y6=М+З+Щ+Э+К+b18+Ю+Я+Ф+b22

 Y7=b2+b8+С+В

 Y8=Х+b4+Н+b10+Д+И+О

 Y9=А+Л+Е+b16+b20

 Y10=Ц+Ч+Ж+Т+П

 2.2.3. Переведеня у базис:

 T1=b7+Г+Ч+П= Nb7∙NГ∙NЧ∙NП 

Т2=b2+А+b4+Б+b6+Л+Н+М+З+О+П= 

 =Nb2∙NА∙Nb4∙NБ∙Nb6∙NЛ∙NН∙NМ+NЗ∙NО∙NП 

 Т3=b1+Р+b8+Е+С+И+Т+У+b20= 

 =Nb1∙NР∙Nb8∙NЕ∙NС∙NИ∙NТ∙NУ+b20

Т4 =А+b10+Д+Е+Ж+З+b16+К+b18+b20+Ф+b22=

=NА∙Nb10∙NД∙NЕ∙NЖ∙NЗ∙Nb16∙NК+Nb18∙Nb20∙NФ∙Nb22

 Т5=Х+Б+Ц+H+Ч+b12+Д+Ж+И+Ш+Щ+Э+K+Ю+Я+b22=

 =NХ∙NБ∙NЦ∙NH∙NЧ∙Nb12∙NД∙NЖ+NИ∙NШ∙NЩ∙NЭ∙NK∙NЮ∙NЯ∙Nb22



 Y1=А+b4+Л+b10+Д= NА∙Nb4∙NЛ∙Nb10∙NД

 Y2=b1+b7= Nb1∙Nb7

 Y3=Ц+Ч+Ж+Ш+Т+К+b18+У+П+Ф+b22=NЦ∙NЧ∙NЖ∙NШ∙NТ∙NК∙Nb18∙NУ+

 +NП∙NФ∙Nb22

 Y4=b1+Б+b6+b7+Г+b12=Nb1∙NБ∙Nb6∙Nb7∙NГ∙Nb12

 Y5=b6+b12+Е+b16+b20= Nb6∙Nb12∙NЕ∙Nb16∙Nb20

 Y6=М+З+Щ+Э+К+b18+Ю+Я+Ф+b22= NМ∙NЗ∙NЩ∙NЭ∙NК∙Nb18∙NЮ∙NЯ+

 +NФ∙Nb22

 Y7=b2+b8+С+В= Nb2∙Nb8∙NС∙NВ

 Y8=Х+b4+Н+b10+Д+И+О= NХ∙Nb4∙NН∙Nb10∙NД∙NИ∙NО

 Y9=А+Л+Е+b16+b20= NА∙NЛ∙NЕ∙Nb16∙Nb20

 Y10=Ц+Ч+Ж+Т+П= NЦ∙NЧ∙NЖ∙NТ∙NП

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

	
Висновок



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

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


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



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

2. Мікросхеми серії 1533(555). Стислі теоретичні дані. Одеса. Центр НТТМ ОГПУ. 1975г.

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

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