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

Міністерствоосвіти і науки УкраїниОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙУНІВЕРСИТЕТКафедракомп’ютерних інтелектуальнихсистем та мереж

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

з дисципліни

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

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

Одеса 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 mod3 = 0.   

(A) mod 3  ТИП ТРИГЕРА  0 Т  D  1 D  JK  2 JK  T автомат Мілі  Мура

Табл.1

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

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

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

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

 

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

 

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

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

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

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

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

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

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

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

Статистика:

a12стана

a21стан

a32стана

a41стан

a52стана

a61стан

a71стан

a82стана

a92стана

a101стан

a112стана

a121стан

a131стан

a142стана

a152стана

a162стана

a172стана

a182стана

a191стан

a202стана

a212стана

a222стана

a231стан

a242стана

a253стана

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

a100011

a210011

a300110

a410101

a500101

a611001

a701011

a801100

a901010

a1001101

a1101001

a1200111

a1301110

a1411000

a1510100

a1610010

a1710001

a1810000

a1910110

a2001000

a2100100

a2200010

a2311010

a2400001

a2500000

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

Am         Kam

As(y)      X

Kas

D1D2D3D4D5

a13

a17        

a1(-)

1

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

/> /> /> /> /> /> /> <td/> /> /> /> /> /> /> /> />

/>/>/> 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 ЄСКД. Правила виконання електричнихсхем цифрової обчи слювальноїтехніки.

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