43140

Синтез автомата по заданому алгоритму роботи

Курсовая

Информатика, кибернетика и программирование

Система з чотирьох перемикальніх функцій задана таблицею 2.1 – таблиця істиності заданих функцій Необхідно виконати сумісну мінімізацію функцій f1 f2 f3. Отримати операторні представлення для реалізації системи функцій на програмувальних логічних матрицях. 4 Етапи проектування і терміни їх виконання 1 Розмітка станів автомата 2 Формування вхідного та вихідного алфавітів 3 Побудова графа автомата 4 Побудова таблиці переходів 5 Побудова структурної таблиці автомата 6 Синтез комбинаційних схем для функцій збудження тригерів і вихідних...

Украинкский

2013-11-03

1.49 MB

5 чел.

Національний технічний університет України

 «Київський політехнічний інститут»

Факультет інформатики та обчислювальної техніки

Кафедра обчислювальної техніки

 

                        КУРСОВА РОБОТА

з дисципліни "Прикладна теорія цифрових автоматів"

Виконав:      Кравчук Ігор Веніамінович

                      Факультет     ІОТ

                      Група       ІО-81,  
                      
Залікова книжка  №  8108

Допущена до захисту__________________

Номер технічного завдання1 111 110 101 100

                                                                         _______________________

(підпис керівника)

 

Київ  - 2008р.


Опис альбому


№ рядка

Формат

Позначення

Найменування

Кількість

Примітка

1

2

Документація загальна

3

4

розроблена заново

5

6

А4

ІАЛЦ.463626.002 ТЗ

Технічне завдання

5

7

А3

ІАЛЦ.463626.003 Е2

Керуючий автомат

1  

8

Схема електрична

9

функціональна

10

А4

ІАЛЦ.463626.004 ПЗ

Пояснювальна записка

17

 


                                 

                                                                                                        

Технічне завдання


Зміст

1. Призначення розроблюваного обєкта                  2

2. Вхідні дані для розробки                                       2

3. Склад пристроїв                                           5

4. Етапи і терміни проектування ___________________5

5. Перелік текстової і графічної документації                 5


1 Призначення розроблюваного об’єкта

В курсовій роботі нам необхідно виконати синтез автомата Мілі. Керуючий автомат — це електрична схема, що виконує відображення вхідного сигналу у вихідний по заданому алгоритму. Практичнее застосування данного автомата можливе в області обчислювальної техніки.

2 Вхідні дані

Варіант завдання визначається дев’ятьма молодшими розрядами залікової книжки представлений у двійковій системі числення.

h9=1,  h8=1,   h7=0,   h6=1,   h5=0,   h4=1,   h3=1,   h2=0,   h1=0

Логічні умови(h8 h7 h3 = 000):

X2, NOT X2, NOT X1.

Послідовність керуючих сигналів(h9 h4 h1 = 001):   

Y1, (Y1, Y2), Y3, (Y4, Y5), Y2, (Y1, Y3).

Сигнал тривалістю 2t(h6 h2 = 11):

Y4

Тригер(h6 h5 = 10):

JK – тригер.

Логічні елементи(h3 h2 h1 = 011):

3І, 2АБО, НЕ.

Тип автомату(h4 = 0):

Мілі.

Система з чотирьох перемикальніх функцій задана таблицею 2.1:

x4

x3

x2

x1

f1

f2

f3

F4

0

0

0

0

1

1

1

0

0

0

0

1

1

1

0

1

0

0

1

0

1

1

1

0

0

0

1

1

0

0

0

0

0

1

0

0

0

1

0

0

1

0

1

0

0

0

0

0

1

1

0

1

0

0

1

1

1

1

1

1

0

0

0

1

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

0

0

1

0

1

1

1

0

0

1

1

1

0

0

1

1

1

1

1

0

1

1

0

0

0

1

1

1

0

0

1

0

1

1

1

1

1

1

1

1

1

Таблиця 2.1 – таблиця істиності заданих функцій

 

Необхідно виконати сумісну мінімізацію функцій f1, f2, f3. Отримати операторні представлення для реалізації системи функцій на програмувальних логічних матрицях.

Функцію f4 необхідно представити в канонічних формах алгебр Буля, Жегалкіна, Пірса та Шеффера. Визначити належність даної функції до п’яти передповних класів. Виконати мінімізацію функції методами:

- невизначених коефіцієнтів;

- Квайна (Квайна-Мак-Класкі);

- діаграм Вейча.

3 Склад пристроїв

Керуючий автомат.

Керуючий автомат складається з комбінаційної схеми і пам’яті на тригерах. Тип тригерів і елементний базис задані в технічному завданні.

Програмувальна логічна матриця.

ПЛМ складається із двох (кон’юктивної і диз’юнктивної ) матриць, де виходи першої приєднуються на входи другої і дозволяють реалізувати комбінаційні схеми в базисі  {І/АБО, І/АБО-НЕ}.

4 Етапи проектування і терміни їх виконання

1) Розмітка станів автомата

2) Формування вхідного та вихідного алфавітів

3) Побудова графа автомата

4) Побудова таблиці переходів

5) Побудова структурної таблиці автомата

6) Синтез комбинаційних схем для функцій збудження тригерів і вихідних сигналів

7) Побудова схеми автомата в заданому базисі.

5 Перелік текстової и графічної документації

  1.  Титульний лист
  2.  Аркуш з написом «Опис альбому»
  3.  Опис альбому
  4.  Аркуш з написом «Технічне завдання»
  5.  Технічне завдання
  6.  Аркуш з написом «Керуючий автомат. Схема електрична функціональна»
  7.  Керуючий автомат. Схема електрична функціональна
  8.  Аркуш з написом «Пояснювальна записка»
  9.  Пояснювальна записка


Керуючий автомат

Схема електрична функціональна


Пояснювальна записка


Зміст

1 Вступ                                                                                                        2

2 Синтез автомата                                                                            2

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

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

3.1 Вступ_____________________________________________________________7  

3.2 Представлення функцій f4 в канонічній формі алгебри Буля_______________7

3.3 Представлення функцій f4 в канонічній формі алгебри Жегалкіна__________7

3.4 Представлення функцій f4 в канонічній формі алгебри Пірса______________7

3.5 Представлення функцій f4 в канонічній формі алгебри Шеффера__________8

3.6 Визначення належності функції f4 до п’яти чудових класів_______________8                         

  3.7 Мінімізація функції f4 методом невизначених коефіцієнтів_______________8                          

  3.8 Мінімізація функції f4 методом Квайна-Мак-Класкі_____________________9

  3.9 Мінімізація функції f4 методом діаграм Вейча__________________________10

  3.10 Спільна мінімізація функцій f1, f2, f3                                                      11

3.11 Спільна мінімізація заперечень функцій f1,f2,f3                                         13

3.12 Одержання операторних форм для реалізації на ПЛМ                                     15

4 Висновок                                                                                16

5 Список літератури                                                                     17


1 Вступ

У даній курсовій роботі необхідно виконати синтез автомата і синтез комбінаційних схем. Розробка виконується на підставі

«Технічного завдання ІАЛЦ.463626.002 ТЗ».

2 Синтез автомата

2.1 Структурний синтез

За графічною схемою алгоритму (рисунок 2.1 «Технічного завдання ІАЛЦ.463626.002 ТЗ») виконаєму розмітку станів автомата (рисунок 2.1):  

Рисунок 2.1 - розмітка станів автомата


Згідно з блок-схемою алгоритму(рисунок 2.1) побудуємо граф автомата Мілі

(рис. 2.2), виконаємо кодування станів автомата.

Рисунок 2.2 – Граф автомата

Для синтезу логічної схеми автомату необхідно виконати синтез функцій збудження тригерів та вихідних функцій автомата. Кількість станів автомата дорівнює 6, кількість тригерів знайдемо за формулою K>= ]log2N[ = ]log26[ = 3, звідки К = 3. Так як для побудови данного автомата необхідно використовувати    JK-тригери, запишемо таблицю переходів цього типу тригерів (рисунок 2.3).

Рисунок 2.3 – Таблиця переходів JK-тригера

На основі графа автомата (рисунок 2.2) складемо структурну таблицю автомата (таблицю 2.1).

Таблиця 2.1 – Структурна таблиця

                                              

На основі структурної таблиці автомата (таблиці 2.1) виконаємо синтез комбінаційних схем для вихідних сигналів і функцій збудження тригерів. Аргументами функцій збудження тригерів є коди станів та вхідні сигнали, для вихідних сигналів – тільки коди станів. Виконаємо Мінімізацію вищевказаних функцій методом діаграм Вейча (рисунок 2.4, 2.5). Зауважимо, що операторні представлення функцій сформовані враховуючи елементний базис {3І, 2АБО, НЕ}.

Рисунок 2.4 – діаграми Вейча

                                                                

Рисунок 2.5 – діаграми Вейча

                                                                                 

Виконаємо мінімізацію вихідних функцій теж методом діаграм                   Вейча (рисунок 2.6).

Рисунок 2.6 – мінімізація вихідних функцій

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

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

Схема даного автомату виконана згідно з єдиною системою конструкторської документації  (ЄСКД) і наведена у документі «Керуючий автомат. Схема електрична функціональна ІАЛЦ.463626.003 Е2».


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

3.1 Вступ

На основі «Технічного завдання ІАЛЦ.463626.002 ТЗ» виконуємо синтез комбінаційних схем.

Умова курсової роботи вимагає представлення функції f4 в канонічних формах алгебр Буля, Жегалкіна, Пірса і Шеффера.

3.2 Представлення функцій f4 в канонічній формі алгебри Буля.

В даній алгебрі визначені функції {І, АБО, НЕ}.

3.3 Представлення функцій f4 в канонічній формі алгебри Жегалкіна.

В даній алгебрі визначені функції {І, виключне АБО, const 1}.

3.4 Представлення функцій f4 в канонічній формі алгебри Пірса.

В даній алгебрі визначені функції {АБО-НЕ}.

        

3.5 Представлення функцій f4 в канонічній формі алгебри Шеффера

В даній алгебрі визначені функції {І-НЕ}.

3.6 Визначення належності функції f4 до п’яти чудових класів

1. Дана функція зберігає нуль, так як F(0000)=0.

2. Дана функція зберігає одиницю, так як F(1111)=1.

3. Дана функція не самодвоїсна, так як F(0001)=1, F(1110)=1.

4. Дана функція не монотонна, так як F(0001)=1 < F(0010)=0.

5. Дана форма нелінійна, так як канонічна форма алгебри Жегалкіна, що отримана у підрозділі 3.3 є не лінійним поліномом.

На основі вищесказаного робимо висновок, що функція f4 належить першим двом і не належить останнім трьом передповним класам.

3.7 Мінімізація функції f4 методом невизначених коефіцієнтів

Ідея цього методу полягає у відшуканні ненульових коефіцієнтів при кожній імпліканті. Рівняння для знаходження коефіцієнтів представимо таблицею     (таблиця 3.7.1). Виконаємо ви креслення тих рядків на яких функція приймає нульові значення. Викреслимо вже знайдені нульові коефіцієнти в тих рядках таблиці, що залишилися імпліканти, що залишилися після виконання попередніх дій поглинають ті імпліканти, що розташовані зправа від них.

Таблиця 3.7.1 – таблиця невизначених коефіцієнтів

Отримаємо СДНФ функції:

Построим таблицю покриття(таблиця 3.7.2).

Таблиця 3.7.2 – таблиця покриття

Отримаємо МДНФ функції:

3.8 Мінімізація функції f4 методом Квайна-Мак-Класкі

Виходячи з таблиці істинності функції, запишемо стовпчик ДДНФ, розподіливши терми за кількістю одиниць. Проводимо попарне склеювання між сусідніми групами. Подальше склеювання неможливе.

Виконаємо поглинання термів(рисунок 3.8.1).

 

Рисунок 3.8.1 – поглинання термів

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

3.9 Мінімізація функції f4 методом діаграм Вейча

Виконаємо мінімізацію функції методом Вейча (рисунок 3.9.1). Цей метод дуже зручний при мінімізації функції з кількістю аргументів до чотирьох включно. Кожна клітинка відповідає констітуєнті, а прямокутник з кількох клітинок – імпліканті.

Рисунок 3.9.1 - мінімізацію функції методом Вейча

3.10 Спільна мінімізація функцій f1, f2, f3

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

Виконаємо мінімізацію системи функцій f1, f2, f3, заданих таблицею істинності (технічного завдання ІАЛЦ.463626.002 ТЗ) методом діаграм Вейча (рисунок 3.10.1).

Рисунок 3.10.1 - мінімізацію системи функцій f1, f2, f3


Виведемо перші чотирі нормальні формі:

           І/АБО

         І-НЕ/І-НЕ

 АБО/І-НЕ

АБО-НЕ/АБО

Реалізуємо системи функцій f1, f2, f3 на елементах І-НЕ/І-НЕ. Реалізація функцій в заданому елементному базисі представлена на рисунку 3.10.2.

Рисунок 3.10.2 – схема систем функцій f1, f2, f3


3.11 Спільна мінімізація заперечень функцій f1, f2, f3

Виконаємо мінімізацію заперечень невизначених систем функцій f1, f2, f3, заданих таблицею істинності (технічного завдання ІАЛЦ.463626.002 ТЗ) методом діаграм Вейча (рисунок 3.11.1).

Рисунок 3.11.1 – мінімізація заперечень функцій


Виведемо перші чотирі нормальні формі:

        І/АБО-НЕ

           І-НЕ/І

   АБО-І

АБО-НЕ/АБО-НЕ

Реалізуємо системи функцій f1, f2, f3 на елементах АБО-НЕ/АБО-НЕ. Реалізація функцій в заданому елементному базисі представлена на рисунку 3.11.2.

Рисунок 3.11.2 - схема систем функцій f1, f2, f3


3
.12 Одержання операторних форм для реалізації на ПЛМ

Одержимо операторне представлення функцій на ПЛМ.

       На ПЛМ можна реалізувати форми {І/АБО, І/АБО-НЕ}.

І/АБО : Всього 4 змінні, 9мплікант, 3 функції.

І/АБО-НЕ : Всього 4 змінні, 9мплікант, 3 функції.

Тому не має різниці яку ПЛМ обрати. Для зразку оберемо ПЛМ(4,9,3).

Побудуємо карту програмування ПЛМ (рисунок 3.12.1).

X4

X3

X2

X1

F1

F2

F3

Рисунок 3.12.1 - мнемонічна схема ПЛМ

Покажемо умовне графічне позначення даної ПЛМ (рисунок 3.12.2)

Рисунок 3.12.2 -  умовне графічне позначення ПЛМ

4 Висновок

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

При побудові комбінаційних схем було показано доцільність та ефективність сумісної мінімізації кількох функцій.

Усі схеми та керуючий автомат були перевірені в программі AFDK 2.0. Перевірка дала позитивні результати.

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

5 Список літератури

1) Жабін В.І.,Ткаченко В.В. Логические основы и схемотехника цифровых ЭВМ.–Київ ТОО "Век+",1999.

2) Самофалов К.Г., Корнійчук В.І., Тарасенко В.П. Электронные цифровые вычислительные машины. – К. Вища школа, 1983.

3) Савельєв А.Я. Арифметические и логические основы цифровых автоматов.– Москва: Энергия,1974 г.

4) Поспелов Д.А. Логические методы анализа и синтеза схем.– Москва: Энергия,1974г.

5) Хоуп Г. «Проектирование цифровых вычислительных машин и интегральных схем. » Москва: Мир, 1984 г.

За алгоритмом вказаним на рисунку 2.1 виконати синтез і побудувати функціональну схему управляючого автомату.

Рисунок 2.1 – блок-схема алгоритму


 

А также другие работы, которые могут Вас заинтересовать

59663. Тетянин день (25 січня). Гра на зразок Поля чудес 38 KB
  Завдання першій трійці: Ця квітка є обовязковою в українському віночку без неї не обходиться жоден весільний букет. Завдання для другої трійки: Народна легенда говорить що ця квітка колись була птахою навчала людей любові та щирості.
59664. Три спаса: Литературно-музыкальная композиция 50.5 KB
  Август - последний месяц лета. Днем жарко печет солнце, а ночью уже свежо, прохладно. Август - месяц обильных и длинных утренних рос, густых вечерних туманов. Лето на исходе, это чувствуется по-всему.
59665. Україна - славний край козацький: Методико-бібліографічні матеріали на допомогу бібліотечним працівникам у відзначенні 510-ї річниці українського козацтва 127.5 KB
  Пропонуємо до вашої уваги матеріали до історичного калейдоскопу Українське козацтво в датах; до історичних годин: Освічені жінки козацької доби; Закоханий в Україну: козацька тематика в творах Рєпіна історичної години Гетьман Іван Виговський і Конотопська...
59666. Україно, незборима зроду - ти душа великого народу: Сценарій тематичного вечора, присвяченого 10-й річниці прийняття Декларації про державний суверенітет України 38.5 KB
  Прочитаймо давню й сиву Свою долю нещасливу. Кінець вісімдесятих початок дев’яностих років були позначені небувалим піднесенням національновизвольної боротьби. Ведуча 1: Василь Скрипка Незалежність Нарешті дочекалися і ми Своєї незалежної держави.
59667. Ясне-красне Купайло: Фольклорний вечір 46.5 KB
  Ведучий 1: Сьогодні ми хочемо розповісти про надзвичайно поетичне свято Івана Купала яке дійшло до нас ще з поганських часів. Ведучий 2: Купайло свято молодіжне саме звідси єднання молодих сердець на святі і оспівування в піснях хлопця і дівчини попарне стрибання через багаття.
59668. Свято закінчення початкової школи 49.5 KB
  Прийшла така вже пора Але не сумувати тут зібрались А пригадати як все починалось 1 клас Ведучі. Пісня Вчать у школі Ведучі. І виявилось ой нелегко Писати палички й гачки Каліграфія моя Веж мере замучила...
59669. Буду я природі другом 38 KB
  Природа дає все необхідне для життя людей, тварин, рослин — воду і повітря. Природа потребує постійної уваги, турботи. Ми повинні берегти природу, охороняти її багатства.
59670. Ми до тебе, казко, в гості завітали 47 KB
  І знову пісня радісно дзвенить І казка на екрані оживає. Сьогодні ми Казку сюди запросили Щоб бачити Казку слухать гуртом А Казка в завії десь там заблудила. Але Казка до нас прийде тоді коли ми покажемо як добре знаємо казки. Казка виходить на сцену.