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 – блок-схема алгоритму


 

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

73554. Символічний метод розрахунку лінійних електричних кіл (ЛЕК) однофазного синусоїдного змінного струму 856.5 KB
  Розрахункові дії з комплексними параметрами ЛЕК однофазного СЗС. Закони Ома і Кірхгофа в комплексній формі. Символічний метод розрахунку однофазних кіл СЗС з одним джерелом ЕРС.
73555. Українська історіографія в епоху Гетьманщини 177 KB
  Події від середини ХVІІ і до кінця ХVІІІ ст. – це період Національної революції, Гетьманщини і ліквідації автономного ладу України в складі Російської імперії. Національна революція, що почалася 1848 року, привела до утворення Української гетьманської держави. На червень 1652 року Україна фактично виборола незалежність
73556. Введение в высокотемпературную теплотехнологию и энергетику теплотехнологии 32.17 MB
  Возобновляемые источники энергии – энергия солнца ветра тепла земли естественного движения водных потоков а также энергия существующих в природе градиентов температур. Возобновляемые ТЭР основаны на использовании возобновляемых источников энергии: солнечного излучения энергии морей рек и океанов внутреннего тепла Земли воды и воздуха энергии естественного движения водных потоков и существующих...
73557. Методи розрахунку однофазних лінійних електричних кіл синусоїдного змінного струму при наявності двох і більше джерел живлення 668.5 KB
  Застосування символічного методу при розрахунку Іф кіл СЗС при наявності двох і більше джерел живлення. Методи вузлових і контурних рівнянь та контурних струмів. Методи вузлових потенціалів (двох вузлів) та суперпозиції. Метод еквівалентного генератора.
73558. Українська історіографія на початку національного відродження (кінець XVIII — перша половина XIX ст.) 97 KB
  Україна переживала з кінця XVIII століття складний етап своєї історії. Після поділу Польщі українські землі опинилися у складі двох імперій: Російської (80% території) і Австрійської. Суспільне життя краю характеризувалося кризою кріпосницького ладу, розгортанням російського визвольногопольського національно-визвольного та процесом українського національного відродження.
73559. Источники энергии высокотемпературных теплотехнологических установок 261 KB
  Классификация реакторов высокотемпературной теплотехнологической установки; Структурная схема теплотехнологического реактора; Схемы размещения источников энергии и движения дымовых газов в камерах (зонах) реакторов высокотемпературных технологических установок; Схема тепломассообмена в рабочем пространстве высокотемпературных теплотехнических установках;
73560. Розрахунок лінійних електричних кіл синусоїдного змінного струму методом провідностей 404.5 KB
  Визначення співвідношень опорів для перетворення схеми з послідовним зєднанням опорів в схему з їх паралельним зєднанням. Визначення співвідношень провідностей для перетворення схеми з паралельним зєднанням опорів в схему з їх послідовним зєднанням...
73561. Українська iсторiографiя другої половини ХIХ – початку ХХ століть 201 KB
  Народницький напрям в українськiй iсторiографiї сформувався в 40-вi роки ХIХ столiття. Вiн став домiнуючим у другiй половинi ХIХ ст. i поширився на першi десятилiття ХХ столiття. Його засновниками були Михайло Олександрович Максимович i Микола Iванович Костомаров, а, за висловом М.С.Грушевського, він сам був «останнiм могiканом» української народницької iсторiографii.
73562. Резонансні режими в лінійних електричних колах СЗС 757.5 KB
  Резонансом напруг Іф. ЛЕК СЗС називається такий режим роботи нерозгалуженого кола, що містить послідовно з’єднані активний, індуктивний і ємнісні опори, при якому повний опір кола набуває активного характеру, спади напруг на індуктивних і ємнісних опорах компенсують один одного, а повна напруга співпадає за фазою зі струмом.