Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПТЦА
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Не вказано
Інформація про роботу
Рік:
2006
Тип роботи:
Конспект лекцій
Предмет:
ПТЦА
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторних занять з дисципліни «Прикладна теорія цифрових автоматів» для студентів напрямку «Комп’ютерна інженерія»
ЗАТВЕРДЖЕНО
кафедрою АПОТ.
Протокол № 8
від 14.04.2006
Харків 2006
Методичні вказівки до лабораторних занять з дисципліни «Прикладна теорія цифрових автоматів» для студентів напрямку «Комп’ютерна інженерія» / Упоряд. Какурін М.Я., Кулак Е.М., Карасьов А.Л. ( Харків: ХНУРЕ, 2006. ( с.
Упорядники: М.Я. Какурін
Е.М. Кулак
А.Л. Карасьов
Рецензент: В.О. Гуліус, канд. техн. наук., доц. каф. ЕОМ
ЗМІСТ
Вступ………………………………………………………………….……….4
1 Контролюючі та коригуючі коди Хемінга і Бергера…………..………....5
2 Синтез комбінаційних схем………………………………………………15
3 Елементарні автомати (тригери). Типи та засоби їх завдання……..…...21
4 Структурний синтез елементарних автоматів (тригерів)………...……..29
5 Засоби завдання складних цифрових автоматів………………………....36
6 Кодування внутрішніх станів автоматів………...…………………..…...42
7 Структурний синтез мікропрограмних автоматів Мілі…………...…....50
8 Структурний синтез мікропрограмних автоматів Мура…...……….…..56
Висновки………………………………………………………………..……63
Перелік посилань……………………………………………………......…..64
ВСТУП
Методичні вказівки призначені для проведення лабораторних робіт з використанням навчаючих програм на персональних комп'ютерах. Для виконання відповідної лабораторної роботи студент повинен вивчити теоретичний матеріал з теми по лекційному матеріалу та по літературі, наведеній у методичних вказівках до цієї роботи
Перед виконанням лабораторної роботи студенти повинні скласти допуск з теоретичного матеріалу у співбесіді з викладачем чи за допомогою комп'ютерної тестової програми. Студенти, які успішно склали допуск, переходять до роботи з комп'ютерними навчаючими програмами. Кожна з таких програм складається з двох частин : власне навчаючої програми та частини, що виконує (обчислює) конкретне завдання. Під час роботи з першою частиною студенти знайомляться з завданням, яке вони будуть виконувати в ході проведення роботи, та методом його рішення з даними, які використовуються як приклад. Для роботи з другою частиною програми кожен студент отримує індивідуальне завдання у вигляді даних до відповідних комп’ютерних обчислювальних програм. Вони надаються комп'ютером в ймовірному режимі чи обираються з таблиці, наведеної в методичних вказівках. Працюючи з цією частиною навчаючої програми, студент моделює свої дані на комп'ютерній моделі процесу, що вивчається, чи заповнює відповідні таблиці в діалоговому (інтерактивному) режимі роботи з комп'ютером. Комп'ютер виступає тут у ролі не тільки моделюючого (обчислювального) інструмента, але й слідкує за правильністю виконання завдання.
Після отримання результатів виконання завдання студент оформлює індивідуальний звіт про виконану роботу та здає його викладачу у формі співбесіди чи за допомогою комп'ютерної тестової програми за темою проведеної роботи і отримує відповідну оцінку.
За вказаною технологією лабораторні роботи з використанням комп'ютерних навчаючих програм можуть виконуватися студентами на ОЦ ХНУРЕ чи індивідуально на особистому персональному комп'ютері за згодою з викладачем. Звіти про виконання лабораторних робіт здаються викладачу незалежно від місця виконання лабораторних робіт у зазначений час.
1 КОНТРОЛЮЮЧІ ТА КОРИГУЮЧІ КОДИ ХЕМІНГА І БЕРГЕРА
1.1 Мета роботи
Отримати уявлення про код Хемінга і Бергера та практичні навики їх використання.
1.2 Методичні вказівки з організації самостійної роботи студентів
1. Код Хемінга дозволяє відновлювати частково пошкоджену інформацію за рахунок надлишкового її кодування. Кількість контрольних розрядів для коду Хемінга з виправленням поодинокої помилки визначається за формулою:
2k m+k+1, (1.1)
де m - число інформаційних розрядів; k – число контрольних розрядів.
Кількість контрольних розрядів для коду Хемінга з контролем подвійної помилки визначається як і для коду Хемінга з виправленням поодинокої помилки, плюс ще один додатковий контрольний розряд.
У загальному випадку для виправлення будь-якої помилки деякої кратності (і) треба використовувати коригуючий код з мінімальною кодовою відстанню:
Dmin. випр.=2i+1. (1.2)
Методика виправлення поодинокої помилки заснована на розвитку ідеї виявлення. Якщо є не один, а хоча б два контрольних розряди, то можна локалізувати (визначити місце) помилку з точністю до півслова, тобто виявити, в якій половині кодової комбінації вона знаходиться. Збільшуючи кількість контрольних розрядів та продовжуючи ділення розрядів слова навпіл «вглиб», можна локалізувати помилку з точністю до одного розряду. Залишається тільки визначити, скільки розрядів треба виділити в n-розрядному слові, щоб знайти у ньому місце помилки (та після цього виправити її).
Для спрощення вирішення поставленої задачі, існуе одне істотне обмеження: вважатимемо, що у кодових комбінаціях (машинних словах) можливі тільки поодинокі помилки та неможливі помилки більш високої кратності. Далі діємо наступним чином: якщо є декілька контрольних розрядів, то кожний з них можна використовувати для відкриття помилки тільки в одному півслові кодової комбінації, що перевіряється, причому півслова потрібно формувати так: перше півслово будується з будь-якої половини розрядів слова, що перевіряється; друге півслово утворюється з половини першого півслова та з тих розрядів, що не увійшли до першого півслова; третє півслово формується з половини тих розрядів, що досі належали тільки до першого півслова, з половини розрядів, що досі належали тільки до другого півслова, з половини розрядів, що належать досі і першому, і другому півсловам, з половини розрядів, що не належать ані першому, ані другому півслову, і так до тих пір, доки у кожному півслові не залишиться по одному розряду, що належить тільки до цього півслова. Кількість півслів, отриманих в результаті розбиття, визначається за формулою:
k log2 (n+1). (1.3)
Видно, що якщо в слові можливі тільки поодинокі помилки, кожна з них локалізується з точністю до одного розряду у межах n розрядів. Якщо, наприклад, перевірка на парність показала наявність помилок в усіх чотирьох півсловах, то зрозуміло, що помилка відбулася у тому єдиному розряді, що входить в усі чотири півслова (15-ий розряд).
В табл. 1.1 показано, як бере участь кожний з розрядів у тому або іншому півслові (якщо i-ий розряд входить в j-е півслово, то на перетині i-го рядка та
j-го стовпчика у таблиці поставлена одиниця, в інших позиціях поставлені нулі).
Таблиця 1.1 – Двійкови та десяткові значення номерів розрядів
Номер розряду слова
Півслова
Десятковий еквівалент двійкового
числа
4-е
3-е
2-е
1-е
1-й (контрольний)
2-й (контрольний)
3-й
4-й (контрольний)
5-й
6-й
7-й
8-й (контрольний)
9-й
10-й
11-й
12-й
13-й
14-й
15-й
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Аналіз табл. 1.1 показує, що жодна двійкова комбінація в її рядках не повторюється. Отже, порівняння комбінації сигналів помилок у чотирьох контрольних розрядах із двійковими комбінаціями у рядках таблиці обов'язково забезпечить відкриття того розряду, в якому відбулася поодинока помилка.
Структура коду Хемінга для 15-розрядного числа (11 інформаційних розрядів та 4 контрольних) надана на рис. 1.1.
Рисунок 1.1 – Структура коду Хемінга для 15-розрядного числа
Узагальнені формули обчислення контрольних розрядів (4),...,(7) мають вигляд:
K4 = S09 + S10 + S11 + S12 + S13 + S14 + S15; (1.4)
K3 = S05 + S06 + S07 + S12 + S13 + S14 + S15; (1.5)
K2 = S03 + S06 + S07 + S10 + S11 + S14 + S15; (1.6)
K1 = S03 + S05 + S07 + S09 + S11 + S13 + S15, (1.7)
де + позначає суму по модулю 2 (mod 2).
Якщо деякі інформаційні розряди будуть відсутні (наприклад, S14, S15), то необхідно вважати, що вони дорівнюють нулю.
2. Код Хемінга з виправленням поодинокої помилки та контролем подвійної. Даний код відрізняється від коду з виправленням поодинокої помилки тим, що вводиться ще один додатковий контрольний розряд. Його називають «розрядом подвійного контролю» (ПК). Він визначається додаванням всіх розрядів (інформаційних та контрольних) по модулю 2, тобто по суті цей розряд подвійного контролю здійснює контроль на парність отриманого коду. Якщо уявити вектор помилки (ВП) коду Хемінга, як число, що приймає значення 0 або 1, то можна заповнити таку таблицю:
Таблиця 1.2 – Результати декодування в залежності від ПК та ВП
ПК
ВП
Результат, отриманий під час декодування
0
0
Відсутність помилки
0
1
Подвійна помилка
1
0
Помилка у додатковому контрольному розряді
1
1
Помилка не у додатковому контрольному розряді
3. Елементи теорії побудови кодів Хемінга.
Питання, розглядувані в цьому розділі, виникли найперше в основному у техніці зв'язку, а не в обчислювальної техніці. Саме тому типова ситуація, розглянута тут, полягає у тому, що виконується передача (а не переробка) інформації, і з деякою ймовірністю можуть виникати випадкові помилки. Передачу інформації можна розуміти у широкому розумінні цього слова, включаючи зміну фізичної форми сигналів, затримку їх по часу, зміну порядку слідування сигналів та ін. Практичну важливість цих питань для обчислювальної техніки та їх застосування до обчислювальної техніки не слід переоцінювати. У більшості випадків в подальшому припускається, що при передачі числа найбільш ймовірною є помилка в одному розряді, менш ймовірною – помилка водночас у двох розрядах, ще менш ймовірною – одночасна помилка у трьох розрядах і т.д. Часто, однак, таке припущення виявляється занадто штучним.
У залежності від призначення та можливостей перешкодозахищених кодів розрізняють коди коригуючі та контролюючі. Коди, що дозволять автоматично виявляти найбільш ймовірні помилки при передачі чисел, називаються контролюючими, а коди, у яких можливе автоматичне виправлення помилок, коригуючими. Коди Хемінга – найбільш відомі та, певно, перші з коригуючих та контролюючих кодів. Вони побудовані стосовно до двійкової системи числення.
Нехай кожне число представлене m двійковими розрядами, та нехай найбільш ймовірна помилка полягає у викривленні одного з них (замість нуля приймається одиниця або навпаки). Для побудови контролюючого коду достатньо приписати до кожного числа один додатковий (контрольний) двійковий розряд та вибрати цифру цього розряду так, щоб загальна кількість одиниць у зображенні будь-якого числа була, наприклад, парним. Поодинока помилка в будь-якому з розрядів числа (і у контрольному розряді теж) змінює парність загальної кількості одиниць. Лічильник по модулю 2, що підраховує кількість одиниць, які містяться серед двійкових цифр числа, міг би давати сигнал про наявність помилок. При цьому ми не одержуємо жодних вказівок про те, в якому саме розряді сталася помилка, тому не маємо можливості виправити її. Залишаються непомітними також помилки, що виникають водночас у двох, у чотирьох або взагалі у парній кількості розрядів. Проте подвійні, а тем більш чотирикратні помилки вважаються малоймовірними.
Якщо кількість інформаційних розрядів непарна, то вигідно цифру контрольного розряду вибирати так, щоб загальна кількість одиниць у коді була непарною. Тоді за наявності всіх нулів в інформаційних розрядах контрольний розряд повинен бути одиницю, а за наявності всіх одиниць в інформаційних розрядах цифра контрольного розряду буде нуль; це допоможе виявити помилки, що виникають, може бути, по провині ланцюгів управління, коли в усіх розрядах замість потрібної інформації передаються нулі або, навпаки, одиниці. Інколи розрізнюють «контроль по парності » та «контроль по непарності », але частіше, незалежно від того, яка умова прийнята для вибору цифри контрольного розряду, цей метод контролю називають контролем по парності.
Для побудови коригуючого коду, розрахованого на виправлення поодиноких помилок, одного контрольного розряду недостатньо. Як видно з подальшого контролю, кількість розрядів k слід вибирати так, щоб задовольнялася нерівність
2k k+m+1 (1.8)
або
k log2 (k+m+1), (1.9)
де m – кількість інформаційних двійкових розрядів числа. Мінімальні значення k при заданих значеннях m, знайдені у відповідності з цією нерівністю, наведені у табл. 1.3.
Таблиця 1.3 – Кількість k в залежності від m
m
k
m
k
m
k
m
k
1
2
3
4
5
6
7
8
9
10
2
3
3
3
4
4
4
4
4
4
11
12
13
14
15
16
17
18
19
20
4
5
5
5
5
5
5
5
5
5
21
22
23
24
25
26
27
28
29
30
5
5
5
5
5
5
6
6
6
6
31
32
33
34
35
36
37
38
39
40
6
6
6
6
6
6
6
6
6
6
Маючи m+k розрядів, коригуючий код можна побудувати наступним чином. Присвоюємо кожному з розрядів свій номер – від 1 до (m+k); запишемо ці номери у двійкової системі. Оскільки 2k>m+k, кожний номер можна представити, очевидно, k-розрядним двійковим числом. Для визначеності будемо вважати, що при записі номерів розрядів у двійковій системі використано позиційний засіб зображення чисел з природними вагами розрядів; взагалі ця умова не є необхідною.
Припустимо далі, що всі m+k розрядів коду розбиті на контрольні групи (що частково перекриваються), причому так, що одиниці у двійковому представленні номеру розряду вказують на його належність до певних контрольних груп. Наприклад, розряд №5 належить до 1-ї та 3-ї контрольних груп, тому що у двійковому представленні його номеру 510 = 01012 1-й та 3-й розряди містять одиниці; розряд №7 належить 1-й, 2-й та 3-й контрольним групам, тому що у двійковому представленні його номеру 710=01112 містяться одиниці у 1-му, 2-му та 3-му розрядах і т.д.
Серед m+k розрядів коду при цьому є k розрядів, кожний з яких належить тільки до однієї контрольної групи. Це розряди, номери яких є цілими ступенями двійки і тому у двійковому представленні містять по одній одиниці. Наприклад, розряд №1, що належить тільки 1-й контрольній групі (тому що його номер у двійковій системі має вигляд...0001), розряд №2, що належить тільки до 2-ї контрольної групи (бо 210=00102 ),... розряд 2(k-1), що належить тільки до k-ї контрольної групи. Ці k розрядів ми будемо вважати контрольними. Інші m розряди, кожний з яких належить не менше ніж до двох контрольних груп, будуть основними розрядами числа (інформаційними розрядами).
При цьому у кожній з k контрольних груп будемо мати по одному контрольному розряду. Наприклад, у 1-у контрольну групу входять всі розряди, номери яких у двійковому представленні містять одиниці у молодшому розряді: 1-й, 3-й, 5-й, 7-й і т.д.; з них контрольним є 1-й. В 2-у контрольну групу входять всі розряди, номери яких у двійковому представленні містять одиницю 2-го розряду: 2-й, 3-й, 6-й, 7-й і т.д.; з них контрольним є 2-й. Вміст основних m розрядів числа заздалегідь заданий: у них розміщується інформація, що передається . У кожний з контрольних розрядів помістимо таку цифру (0 або 1), щоб загальна кількість одиниць у його контрольній групі була парною. Кожний контрольний розряд належить тільки до однієї контрольної групи, тому цифри у контрольних розрядах не залежать одна від другої. Таким чином формується код числа.
Після прийому коду зробимо контроль по парності окремо у кожній контрольній групі. Якщо код був прийнятий вірно, то в усіх контрольних групах кількість одиниць буде парною. Якщо в будь-якому розряді при передачі коду була допущена помилка, то у тих контрольних групах, в які цей розряд входить, кількість одиниць виявиться непарною. Але будь-який розряд коду входить до тих контрольних груп, що відповідають одиницям у його номері, записаному у двійковій системі. Отже, за результатами контролю, проведеного у контрольних групах, можна одержати інформацію про номер розряду, прийнятого невірно. Змінивши цифру цього розряду на протилежну, отримаємо правильний код.
Можна побудувати такий код, що виявляв би подвійні помилки та виправляв поодинокі. Для цього до коригуючого коду, розрахованого на виправлення поодиноких помилок, потрібно приписати ще один контрольний розряд (розряд подвійного контролю). Повна кількість розрядів коду при цьому буде рівна m+k+1, де m – кількість інформаційних розрядів, k визначається за таблицею 1.4. Цифра у розряді подвійного контролю встановлюється така, щоб загальна кількість одиниць в усіх m+k+1 розрядах коду була парною. Цей розряд не включається у загальну нумерацію розрядів та не входить ні в одну контрольну групу .
Таблиця 1.4 – Коди Хемінга для m=4
Звичайний запис числа
Зображення в коригуючому коді
Десятковий
Двійковий
Номер розряду
ПК
7 6 5 4 3 2 1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 0 1 1 0 0 1
0 0 1 1 1 1 0
0 1 0 1 0 1 0
0 1 0 1 1 0 1
0 1 1 0 0 1 1
0 1 1 0 1 0 0
1 0 0 1 0 1 1
1 0 0 1 1 0 0
1 0 1 0 0 1 0
1 0 1 0 1 0 1
1 1 0 0 0 0 1
1 1 0 0 1 1 0
1 1 1 1 0 0 0
1 1 1 1 1 1 1
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
1
Після прийому коду контроль по парності буде вироблятися роздільно по контрольних групах та для усього коду у цілому. У цьому разі можуть бути таки випадки:
1) у прийнятому коді у цілому та по всіх контрольних групах кількість одиниць парна;
2) у прийнятому коді у цілому кількість одиниць непарна, але в усіх контрольних групах кількість одиниць парна;
3) у прийнятому коді у цілому та у деяких з контрольних груп кількість одиниць непарна;
4) у прийнятому коді у цілому кількість одиниць парна, але у деяких контрольних групах є непарна кількість одиниць.
Якщо потрійні помилки у великій кількості розрядів виключаються, то перший випадок відповідає безпомилковому прийому коду, другий випадок – помилка тільки у розряді подвійного контролю, третій випадок – поодинокій помилці у будь-якому з інших розрядів (яку можна виправити у відповідності з наведеними вище правилами), четвертий випадок – подвійній помилці. Виправлення подвійних помилок тут, кінцево, неможливо. Приклад такого коду наведений у таблиці 1.4, де колонка «ПК» дасть цифри розряду подвійного контролю. Збільшуючи далі кількість контрольних розрядів, можна було б побудувати коди, розраховані на виправлення подвійних помилок та відкриття тройних і т.д. Проте методи побудови цих кодів не цілком розроблені.
Контрольні приклади
1.Закодувати чотирирозрядну інформаційну комбінацію 1011 коригуючим кодом Хеминга.
k=3 (тому що n=4). Розмістимо інформаційні та контрольні розряди, пронумерувавши їх від 1 до 7:
S7S6S5S4S3S2S1
1 0 1 ? 1 ? ?
Обчислимо значення контрольних розрядів:
k1=S3S5S7=111=1;
k2=S3S6S7=101=0;
k4=S5S6S7=101=0.
Тоді повна кодова комбінація коду Хемінга буде мати вигляд:1010101.
2. Знайти та виправити помилку у прийнятій комбінації коригуючого коду Хемінга 1000101.
Обчислюємо значення контрольних розрядів:
k`1=S1S3S5S7=110=1
k`2=S2S3S6S7=0101=0
k`4=S4S5S6S7=0001=1
Вектор помилки V= k`4 k`2 k`1=1012=510
Отже, помилка відбулася у 5 розряді. Після виправлення помилки отримаємо комбінацію 1010101.
3. Інформаційну комбінацію 1011 закодувати контролюючим кодом Бергера.
к=[log2(n+1)]=3 (тому що n=4).
Знайдемо число одиниць у комбінації: nе=3.
Інвертований двійковий запис числа 310=0112 рівний 1002. Комбінація коду Бергера має наступний вигляд: 1011100.
4. Визначити наявність помилки у комбінаціях коду Бергера
к1=1000000 та к2=111100. Підраховуємо число одиниць в інформаційних розрядах к1 та к2. Тоді n1e=1 і n2e=3.
Знаходимо інвертований двійковий запис n1e. Вона рівна (110=0012) 110 та не співпадає з 000. Отже, комбінація к1 прийнята з помилкою.
У комбінації к2 число одиниць в інформаційних розрядах n2e =3 (310=0112). Інвертований двійковий запис n2e =100 та співпадає зі значеннями контрольних розрядів. Отже, комбінація к2 прийнята без помилок.
Література: [конспект; 1, с.4 – 10, с.219 – 227; 2, с.300 – 304.]
1.3 Опис лабораторної установки
Лабораторні роботи виконуються на комп'ютерах типу IBM PC 486 та вище, з оперативною пам'яттю не менше 1 Мбайт, швидкодією понад 450 МГЦ, з монітором VGA. Програмне забезпечення розташоване у:
\\10.13.20.100/library/education/Какурин/ ПТЦА / Лабораторные работы
при доступі з мережі ХНУРЕ через “Мережне оточення” або
Сетевое окружение/…/APVT/nserv/library/education/ Какурин/ ПТЦА / Лабораторные работы
при доступі з кафедри АПОТ (ОЦ, ауд. 320).
Інструкція з використання програмних засобів є у тому ж каталозі.
1.4 Порядок виконання роботи і методичні вказівки з її виконання
1.4.1 Вивчити літературу до даної лабораторної роботи.
1.4.2 Номер варіанту для виконання індивідуального завдання визначається по двох останніх цифрах номеру залікової книжки або за вказівкою викладача.
1.4.3 Ознайомитися з навчальною програмою.
1.4.4 Перед дослідженням вибраного варіанту кодових комбінацій необхідно відповісти на контрольні запитання з теми роботи.
1.4.5 Виконати лабораторну роботу у відповідності з наступними пунктами:
1. Побудувати код Хемінга з виправленням поодинокої помилки.
2. Побудувати код Хемінга з виправленням поодинокої помилки та контролем подвійної.
3. Побудувати контролюючий код Бергера.
1.4.6 Оформити звіт по виконаній лабораторній роботі.
1.5 Зміст звіту
Звіт про роботу оформлюється кожним студентом індивідуально. У звіті повинні бути наведені всі результати роботи з програмою – шляхом отримання копій екрана або на окремому аркуші вручну.
1.6 Контрольні запитання
1. Що таке коригуючий код?
2. Що таке контролюючий код?
3. У чому полягає різниця між коригуючими та контролюючими кодами?
4. Як знайти кодову відстань між двома кодовими комбінаціями?
5. Що таке кратність помилки?
6. Чому дорівнює кількість контрольних розрядів у контролюючому коді Хемінга?
7. Чому дорівнює кількість контрольних розрядів у коригуючому коді Хемінга?
8. Чому дорівнює кількість контрольних розрядів у контролюючому коді Бергера?
9. Які вимоги до кодової відстані за Хемінгом коригуючого коду, що виявляє p-кратні помилки та коригує q-кратні?
2 СИНТЕЗ КОМБІНАЦІЙНИХ СХЕМ
2.1 Мета роботи
Вивчення методів синтезу та мінімізації комбінаційних схем (КС); отримання практичних навиків у побудові схем, що синтезують.
2.2 Методичні вказівки з організації самостійної роботи студентів
Комбінаційною схемою прийнято називати схему з n входами та m виходами, в якої сукупність вихідних сигналів у даний момент часу повністю визначається сукупністю вхідних сигналів у даний момент часу та не залежить від вхідних сигналів, маючих місто у попередні моменти часу. Отже, поведінка комбінаційної схеми (КС) може бути описана системою булевих функцій (БФ).
У зв'язку з тим, що одній булевій функції можуть відповідати різні суперпозиції функцій функціонально повної системи, то виникає задача знаходження такої форми запису функції, при якій кожній функції буде відповідати одна та тільки одна формула стандартного типу та кожній формулі стандартного типу буде відповідати одна та тільки одна функція. Такі форми запису функцій називаються канонічними.
Такими канонічними формами є: досконала диз’юнктивна нормальна форма (ДДНФ) та досконала кон’юнктивна нормальна форма (ДКНФ).
Термін «диз‘юнктивна» вказує на те, що зовнішньою функцією розкладу є диз’юнкция, а внутрішньою – кон’юнкція, бо для обчислення значень функцій треба визначити значення всіх кон’юнкцій, а після цього обчислити їх диз’юнкцію.
При проектуванні цифрових автоматів, зокрема КС, широко використовують методи мінімізації булевих функцій, що дозволяє одержувати рекомендації для побудови економічних схем цифрових автоматів. Загальна задача мінімізації булевих функцій може бути сформульована наступним чином: знайти аналітичний вираз заданої булевої функції у формі, що містить мінімально можливе число літер. У такій постановці задача достатньо добре досліджена у класі диз’юнктивно-кон’юнктивних нормальних форм.
Синтез комбінаційної схеми проводять, виходячи з таблиці істинності, що описує роботу комбінаційної схеми, що синтезується. Застосовуючи різні методи мінімізації, знаходять мінімальну диз’юнктивну форму (МДНФ) функції.
З великого числа різних методів мінімізації найбільш розроблені три методи:
розрахунковий метод (метод безпосередніх перетворень);
розрахунково-табличний метод (метод Квайна Мак-Класкі);
табличний метод (метод карт Карно).
Розглянемо більш докладно останній метод мінімізації за допомогою карт (діаграм) Карно, як один із найбільш зручних методів спрощення логічних функцій при невеликому числі змінних, розроблений у 1953 р. Морісом Карно. Карта Карно є певною таблицею істинності для двох, трьох та чотирьох аргументів. Різні види карт Карно зображені на рис. 2.1, 2.2, 2.3, 2.4.
Змінні, що позначають клітки діаграми, розставляються таким чином, щоб набори, записані у двох сусідніх клітках, мали загальну частину, яка б складалася з усіх змінних крім однієї, по якій вони можуть бути склеєні.
Для мінімізації БФ із допомогою методу Карно необхідно по таблиці істинності заповнити карту, після чого провести прямокутні або квадратні контури за наступним правилам:
1. Всередині контура мають бути клітки, що містять тільки одиниці (первісна форма ДДНФ).
2. Кількість кліток у контурі повинна бути цілим ступенем двійки.
3. При проведенні контурів крайні нижні та крайні верхні (крайні ліві та крайні праві) рядки вважаються сусідніми .
4. Контур повинен включати якомога більше число кліток.
5. Всі одиниці, записані на карті, повинні бути охоплені контурами або ж описані.
Для того, щоб провести мінімізацію у КНФ, необхідно провести контури, що будуть охоплювати нулі; змінні елементарних кон’юнкцій МКНФ беруться із запереченнями. Так, наприклад, для карти Карно, наведеної на рис. 2.1, вираз для МКНФ дорівнює: МКНФ: Y= X1 ( X2 .
Рисунок 2.1 – Карта Карно двох змінних
Для рис. 2.1:
СДНФ: ,
МДНФ:Y=X1 ( X2.
Рисунок 2.2 – Карта Карно трьох змінних
Для рис. 2.2:
СДНФ: ,
МДНФ: .
Рисунок 2.3 – Карта Карно чотирьох змінних
Для рис. 2.3:
СДНФ: ,
МДНФ: .
Рисунок 2.4 – Карта Карно чотирьох змінних
Для рис. 2.4
СДНФ: ,
МДНФ: .
Контрольні приклади
1. Мінімізувати БФ чотирьох змінних, що дорівнює констітуенті одиниці на наборах: 0, 2, 4, 8, 12; отримати МДНФ та МКНФ. Карта Карно для БФ чотирьох змінних має наступний вигляд :
Рисунок 2.5 – Карта Карно функції F(x1,x2, x3,x4)
МДНФ F(x1,x2, x3,x4) = ,
МКНФ F(x1,x2, x3,x4) = .
На рис. 2.6 наведена КС для функції F(x1,x2, x3,x4) МДНФ у булевому базисі.
Рисунок 2.6 – МДНФ функції F(X1,X2, X3,X4)
Перехід від мінімальної диз’юнктивної нормальної форми до базиса Шефера простий: всі терми (логічні добутки) укладаються у дужки, а всі знаки диз’юнкції та кон’юнкції замінюють на операції Шефера (/). Якщо у МДНФ є однолітерний терм, то у базисі Шефера над ним ставиться заперечення.
Аналогічним чином виконується перехід від базиса Буля до базиса Пірса, якщо похідною формою є МКНФ.
При переході від МДНФ до базиса Пірса схема буде трьохступеневою та значення усіх змінних у порівнянні з ДНФ змінюються на інверсні. Нехай є функція:
2. Синтезувати перетворювач чисел (0-9) з одного двійково-десяткового коду у інший (8421+3 ( 5121). Зобразимо цифри від 0 до 9 у відповідних кодах (табл. 2.1). Код 8421+3 буде визначати значення вхідних змінних, а код 5121 – значення вихідних змінних.
Таблиця 2.1 – Двійкови тетради кодів 8421+3 та 5121
Десяткови цифри
8421+3
5121
0
0 0 1 1
0 0 0 0
1
0 1 0 0
0 0 0 1
2
0 1 0 1
0 0 1 0
3
0 1 1 0
0 0 1 1
4
0 1 1 1
0 1 1 1
5
1 0 0 0
1 0 0 0
6
1 0 0 1
1 0 0 1
7
1 0 1 0
1 0 1 0
8
1 0 1 1
1 0 1 1
9
1 1 0 0
1 1 1 1
X1X2X3X4
Y1Y2Y3Y4
Побудуємо карти Карно для функцій Y1, (рис. 2.7)Y2, Y3, Y4. Набори, на яких значення функції не визначено, позначимо «Х» (функція неповністю визначена);
Рисунок 2.7 – Карта Карно для функції Y1
МДНФ функції Y1:
Аналогічно одержуємо вирази для Y2, Y3, Y4. На підставі отриманих логічних виразів будується КС.
Література: [конспект; 4, с.107 – 114; 8, с.46 – 49.]
2.3 Опис лабораторної установки
Лабораторні роботи виконуються на комп'ютерах типу IBM PC 486 та вище, з оперативною пам'яттю не менше 1 Мбайт, швидкодією понад 450 МГЦ, з монітором VGA. Програмне забезпечення розташоване у:
\\10.13.20.100/library/
06.02.2014 00:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора