Керуючий автомат. Схема електрична функціональна
Структурний синтез автомата та синтез комбінаційних схем. Представлення функцій в канонічній формі алгебри Буля, Жегалкіна, Пірса, Шеффера. Мінімізація функції методом невизначених коефіцієнтів, методом Квайна-Мак-Класкі, методом діаграм Вейча.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | украинский |
| Дата добавления | 06.08.2013 |
| Размер файла | 371,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Національний технічний університет України
«Київський політехнічний інститут»
Факультет інформатики та обчислювальної техніки
Кафедра обчислювальної техніки
КУРСОВА РОБОТА
"Прикладна теорія цифрових автоматів"
Виконав: Щербина Микита Валерійович
Факультет ІОТ
Група ІО-22,
Залікова книжка № 2230
Номер технічного завдання - 100010110110
Київ - 2012р.
Опис альбому
|
№ рядка |
Формат |
Позначення |
Найменування |
Кількість |
Примітка |
|
|
1 |
||||||
|
2 |
Документація загальна |
|||||
|
3 |
||||||
|
4 |
розроблена заново |
|||||
|
5 |
||||||
|
6 |
А4 |
ІАЛЦ.109118.002 ТЗ |
Технічне завдання |
5 |
||
|
7 |
А3 |
ІАЛЦ.109118.003 Е2 |
Керуючий автомат |
1 |
||
|
8 |
Схема електрична |
|||||
|
9 |
функціональна |
|||||
|
10 |
А4 |
ІАЛЦ.109118.004 ПЗ |
Пояснювальна записка |
19 |
||
Зміст
1. Призначення розроблюваного об'єкта
2. Вхідні дані для розробки
3. Склад пристроїв
4. Етапи і терміни проектування
5. Перелік текстової і графічної документації
1. Призначення розроблюваного об'єкта
В курсовій роботі необхідно виконати синтез автомата Мура. Керуючий автомат -- це схема, що виконує відображення вхідного сигналу у вихідний за заданим алгоритмом. Практичне застосування даного автомата можливе в області обчислювальної техніки.
2. Вхідні дані
Варіант завдання визначається дев'ятьма молодшими розрядами залікової книжки представлений у двійковій системі числення.
|
h9 |
h8 |
h7 |
h6 |
h5 |
h4 |
h3 |
h2 |
h1 |
|
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
Порядок з'єднання елементів( h8 h4 h2 =101):
3,2,4.
Логічні умови( h8 h7 h3 = 101):
not X2, not X2, not X1.
Послідовність керуючих сигналів( h9 h4 h1 = 000):
(Y1 Y2), Y3, (Y4 Y5), Y2, Y3, (Y1 Y3).
Сигнал тривалістю 2t(h6 h2 = 11):
Y4.
Тригер( h6 h5 = 11):
T - тригер.
Логічні елементи( h3 h2 h1 = 110):
3 АБО-НЕ, 3І.
Тип автомату( h4 = 0):
циклічний автомат Мілі .
Фрагменти блок-схеми алгоритму представлені на рисунку 2.1.
Рисунок 2.1- Фрагменти блок-схеми алгоритму
Система з чотирьох перемикальних функцій задана таблицею 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 |
1 |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
- |
0 |
1 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
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 |
1 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
|
1 |
1 |
0 |
0 |
1 |
- |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
|
|
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.1 Структурний синтез автомата
3. Синтез комбінаційних схем
3.1 Вступ
3.2 Представлення функцій f4 в канонічній формі алгебри Буля
3.3 Представлення функцій f4 в канонічній формі алгебри Жегалкіна
3.4 Представлення функцій f4 в канонічній формі алгебри Пірса
3.5 Представлення функцій f4 в канонічній формі алгебри Шеффера
3.6 Визначення належності функції f4 до п'яти чудових класів
3.7 Мінімізація функції f4 методом невизначених коефіцієнтів
3.8 Мінімізація функції f4 методом Квайна-Мак-Класкі
3.9 Мінімізація функції f4 методом діаграм Вейча
3.10 Мінімізація заперечення функції f4 методом невизначених коефіцієнтів
3.11 Мінімізація заперечення функції f4 методом Квайна-Мак-Класкі
3.12 Мінімізація заперечення функції f4 методом діаграм Вейча
3.13 Комбінаційні схеми реалізації функції F4
3.14 Спільна мінімізація функцій f1, f2, f3
3.15 Одержання операторних форм для реалізації на ПЛМ
4. Висновок
5. Список літератури
1. Вступ
У даній курсовій роботі необхідно виконати синтез автомата і синтез комбінаційних схем. Розробка виконується на підставі «Технічного завдання ІАЛЦ.109118.002 ТЗ».
2. Синтез автомата
2.1 Структурний синтез
За графічною схемою алгоритму (рисунок 2.1 «Технічного завдання ІАЛЦ. 109118.002 ТЗ») виконаємо розмітку станів автомата (рисунок 2.1.1):
Размещено на http://www.allbest.ru/
Рисунок 2.1.1 - Розмітка станів автомата Мілі
Згідно з ГСА ( рисунок 2.1.1) побудуємо граф автомата Мілі (рис. 2.1.2), виконаємо кодування станів автомата.
Размещено на http://www.allbest.ru/
Рисунок 2.1.2 - Граф автомата
Для синтезу логічної схеми автомату необхідно виконати синтез функцій збудження тригерів та вихідних функцій автомата. Кількість станів автомата дорівнює 5, кількість тригерів знайдемо за формулою K>= ]log2N[ = ]log25[ = 3, звідки К = 3. Так як для побудови даного автомата необхідно використовувати T-тригери, запишемо таблицю переходів цього типу тригерів (рисунок 2.1.3).
Размещено на http://www.allbest.ru/
Рисунок 2.1.3 - Таблиця переходів T-тригера
На основі графа автомата (рисунок 2.1.2) складемо структурну таблицю автомата (таблицю 2.1.1).
Таблиця 2.1.1 - Структурна таблиця
|
ПС |
Старий стан |
СП |
Новий стан |
Вхідні сигнали |
Вихідні сигнали |
Функції управління тригерами |
||||||||
|
X1 |
X2 |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
T3 |
T2 |
T1 |
|||||
|
Z1 |
000 |
Z2 |
001 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
||
|
Z1 |
000 |
Z2 |
001 |
-- |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
Z2 |
001 |
Z3 |
011 |
-- |
-- |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
|
|
Z3 |
011 |
Z4 |
111 |
-- |
-- |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
Z4 |
111 |
Z5 |
101 |
-- |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
Z4 |
111 |
Z5 |
101 |
-- |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
Z5 |
101 |
Z5 |
101 |
0 |
-- |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
Z5 |
101 |
Z1 |
000 |
1 |
-- |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
На основі структурної таблиці автомата (таблиці 2.1.1) виконаємо синтез комбінаційних схем для вихідних сигналів і функцій збудження тригерів. Аргументами функцій збудження тригерів та вихідних сигналів є коди станів та вхідні сигнали. Виконаємо мінімізацію заперечення вищевказаних функцій методом Діаграм Вейча (рисунок 2.1.4, 2.1.5). Зауважимо, що виконуємо мінімізацію заперечень, бо елементний базис І/АБО-НЕ отримується із заперечення функцій. операторні представлення функцій сформовані враховуючи елементний базис {3 АБО-НЕ, 3І}.
Мінімізація функцій методом Діаграм Вейча (рисунок 2.1.4)
Після мінімізації функції були подані в заданому елементному базисі.
Функції мають заперечення вихідних сигналів тригерів.
Тригер одночасно видає 2 сигнали: вихідний сигнал та його заперечення. Тому для спрощення комбінаційної схеми, краще використовувати заперечення вихідного сигналу тригеру,ніж ставити інвертор на прямий вихідний сигнал.
Схема даного автомату виконана згідно з єдиною системою конструкторської документації (ЄСКД) і наведена у документі «Керуючий автомат. Схема електрична функціональна ІАЛЦ.109118.003 Е2».
3. Синтез комбінаційних схем
3.1 Вступ
Умова курсової роботи вимагає представлення функції 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(0101)=1, F(1010)=1.
4. Дана функція не монотонна, так як F(0010)> F(0011).
5. Дана форма нелінійна, так як канонічна форма алгебри Жегалкіна, що отримана у підрозділі 3.3 є не лінійним поліномом.
На основі вищесказаного робимо висновок, що функція f4 належить першим двом і не належить останнім трьом передповним класам.
За теоремою Поста-Яблонського випливає, що дана функціє не є функціонально повною.
3.7 Мінімізація функції f4 методом невизначених коефіцієнтів
Ідея цього методу полягає у відшуканні ненульових коефіцієнтів при кожній імпліканті. Рівняння для знаходження коефіцієнтів представимо таблицею (таблиця 3.7.1). Виконаємо викреслення тих рядків на яких функція приймає нульові значення. Викреслимо вже знайдені нульові коефіцієнти в тих рядках таблиці, що залишилися після виконання попередніх дій; поглинають ті імпліканти, що розташовані з права від них.
Далі таблицю коефіцієнтів використовуємо як таблицю покриття функції
|
F4 |
X4 |
X3 |
X2 |
X1 |
K4 |
K3 |
K2 |
K1 |
K43 |
K42 |
K41 |
K32 |
K31 |
K21 |
K432 |
K431 |
K421 |
K321 |
K4321 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
00 |
00 |
00 |
00 |
00 |
00 |
000 |
000 |
000 |
000 |
0000 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
00 |
00 |
01 |
00 |
01 |
01 |
000 |
001 |
001 |
001 |
0001 |
|
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
00 |
01 |
00 |
01 |
00 |
10 |
001 |
000 |
010 |
010 |
0010 |
|
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
00 |
01 |
01 |
01 |
01 |
11 |
001 |
001 |
011 |
011 |
0011 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
00 |
00 |
10 |
10 |
00 |
010 |
010 |
000 |
100 |
0100 |
|
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
01 |
00 |
01 |
10 |
10 |
01 |
010 |
010 |
001 |
101 |
0101 |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
01 |
01 |
00 |
11 |
10 |
10 |
011 |
010 |
010 |
110 |
0110 |
|
|
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
01 |
01 |
01 |
11 |
11 |
11 |
011 |
011 |
011 |
111 |
0111 |
|
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
10 |
10 |
10 |
00 |
00 |
00 |
100 |
100 |
100 |
000 |
1000 |
|
|
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
10 |
10 |
11 |
00 |
01 |
01 |
100 |
101 |
101 |
001 |
1001 |
|
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
10 |
11 |
10 |
01 |
00 |
10 |
101 |
100 |
110 |
010 |
1010 |
|
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
10 |
11 |
11 |
01 |
01 |
11 |
101 |
101 |
111 |
011 |
1011 |
|
|
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
11 |
10 |
10 |
10 |
10 |
00 |
110 |
110 |
100 |
100 |
1100 |
|
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
11 |
10 |
11 |
10 |
11 |
01 |
110 |
110 |
101 |
101 |
1101 |
|
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
11 |
10 |
11 |
10 |
10 |
111 |
110 |
110 |
110 |
1110 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
11 |
11 |
11 |
11 |
11 |
11 |
111 |
111 |
111 |
111 |
1111 |
Отримаємо МДНФ функції:
3.8 Мінімізація функції f4 методом Квайна-Мак-Класкі
Виходячи з таблиці істинності функції, запишемо стовпчик ДДНФ (К0).
1) Розіб'ємо Кі на групи по наявності аргументів.
2) Розіб'ємо кожну групу по наявності аргументів на групи по кількості одиниць у групі.
3) Проводимо попарне склеювання між групами, які входять до однієї групи по аргументам та у яких кількість одиниць відрізняється на 1.
4) Робимо поглинання
5) Повторюємо пункти 1-4 поки можливо, після цього будуємо таблицю покриття і отримуємо МДНФ.
Виконаємо поглинання термів (рис. 3.8.1).
Продовжувати склеювання не можливо, тому будуємо таблицю покриття:
Таблиця 3.8.1-Таблиця покриття функції
|
Імпліканти |
0001 |
0010 |
0101 |
0111 |
1001 |
1010 |
1011 |
1100 |
1111 |
|
|
1100 |
+ |
|||||||||
|
x001 |
+ |
+ |
||||||||
|
x010 |
+ |
+ |
||||||||
|
x111 |
+ |
+ |
||||||||
|
0x01 |
+ |
+ |
||||||||
|
1x11 |
+ |
+ |
||||||||
|
01x1 |
+ |
+ |
||||||||
|
10x1 |
+ |
+ |
||||||||
|
101x |
+ |
+ |
Ядро = {1100; x010}
ТДНФ=1100 ? x010 ? x111 ? 0x01 ? 10x1
МДНФ:
3.9 Мінімізація функції f4 методом діаграм Вейча
Виконаємо мінімізацію функції методом Вейча (рис. 3.9.1). Цей метод дуже зручний при мінімізації функції з невеликою кількістю аргументів. Кожна клітинка відповідає конституенті, а прямокутник з кількох клітинок - імпліканті.
Імплікантою може бути тільки прямокутник з кількістю клітинок,що дорівнює 2k ,k є N.
|
X3 |
||||||
|
X4 |
1 |
0 |
1 |
0 |
||
|
0 |
1 |
1 |
1 |
X2 |
||
|
0 |
1 |
0 |
1 |
|||
|
0 |
1 |
1 |
0 |
|||
|
X1 |
Рисунок 3.9.1 - Мінімізацію функції методом діаграм Вейча
Размещено на Allbest.ru
Подобные документы
Виконання сумісної мінімізації функцій. Операторні представлення для реалізації системи функцій на програмувальних логічних матрицях в канонічних формах алгебри Буля, Жегалкіна, Пірса і Шеффера. Склад пристроїв. Етапи проектування і терміни їх виконання.
контрольная работа [622,1 K], добавлен 07.08.2013Таблиця істинності логічних функцій пристрою, який необхідно синтезувати. Отримання логічних функцій пристрою та їх мінімізація за допомогою діаграм Вейча. Побудова та аналіз структурної схеми пристрою в програмі AFDK з логічними елементами до 3-х входів.
курсовая работа [320,4 K], добавлен 03.05.2015Граф-схема автомата Мура та Мілі. Структурний синтез автомата Мура. Кодування станів. Функції збудження тригерів та вихідних сигналів. Переведеня у базис. Структурний синтез автомата Мілі. Кодування станів. Функції збудження тригерів та вихідних сигналів.
курсовая работа [114,6 K], добавлен 28.02.2009Використання електронно-обчислювальних машин на сучасному етапі, методика та призначення синтезу логічної структури пристрою у базісі АБО-НІ. Мінімізація логічної функції методом Квайна та карт Карно (Вейча). Порядок синтезу структури у заданому базисі.
курсовая работа [144,5 K], добавлен 13.07.2009Граф-схема алгоритму. Серія інтегральних мікросхем. Структурний синтез автомата Мура. Розмітка станів ГСА. Таблиця переходів автомата. Кодування станів. Функції збудження тригерів та вихідних сигналів. Аналіз канонічного методу структурного синтезу.
курсовая работа [30,6 K], добавлен 28.02.2009Специфика построения и минимизации детерминированного автомата методом разбиения. Построение детерминированной сети Петри, моделирующей работу распознающего автомата. Особенности программной реализации праволинейной грамматики, построение ее графа.
курсовая работа [615,1 K], добавлен 19.06.2012Синтез комбінаційної схеми. Отримання вихідної БФ. Мінімізація БФ. Вибір базиса. Застосування факторного алгоритму. Синтез управляючого автомата Мура. Вибір вихідних даних для проектування. Розрахунок даних синтезу. Синтез управляючого автомата Мілі.
курсовая работа [271,5 K], добавлен 26.02.2009Граф-схеми алгоритмів. Серія інтегральних мікросхем для побудови принципових схем синтезованих автоматів. Структурний синтез автомата Мура. Функції збудження тригерів та вихідних сигналів. Кодування станів. Можлива кількість перемикань тригерів.
курсовая работа [36,9 K], добавлен 28.02.2009Дослідження основ двійкової арифметики. Порозрядні логічні операції, Бульові функції та комбінаційні схеми. Еквівалентні формули та закони. Мінімізація методом послідовного виключення логічних змінних та карт Карно. Зведення до базису та часові діаграми.
курсовая работа [481,0 K], добавлен 14.03.2013Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012
