Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Луцький національний технічний університет
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Прикладна теорія цифрових автоматів
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Луцький національний технічний університет
Кафедра КІ
КУРСОВА РОБОТА
з курсу
«Прикладна теорія цифрових автоматів»
Роботу допущено
Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині, а останні – дробовій.
1.2 Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині, а останні – дробовій.
Вважаючи це число шістнадцятковим, перевести його до десяткової, вісімкової та двійкової системи числення з точністю відповідно 3, 3 та 5 розрядів після коми.
1.3 Визначити класи функцій алгебри логіки, до яких належить задана за допомогою таблиці функція трьох змінних, і її функціональну повноту.
2.1 Функцію
f
4
мінімізувати методом Квайна.
2.2 Функцію
f
4
мінімізувати методом Квайна-Мак-Класкі.
2.3 Функцію
f
4
мінімізувати методом діаграм Вейча.
2.4 Виконати спільну мінімізація функцій f1, f2, f3. Зобразити комбінаційну схему для реалізації системи функцій f1, f2, f3 мінімізоване.
2.5 Отримати операторні форми функції
f
4
, зобразити комбінаційну схему в заданому елементному базисі 4І/3АБО.
3.1 Реалізувати функцію f4 у базисі Буля. На виході кожного елемента написати формулу сигналу, який даним елементом реалізується. Для 1 довільного вхідного набору визначити рівні сигналів (0 або1) на виході кожного елемента схеми. Усі елементи повинні мати не більше двох входів. Навести таблиці істинності задіяних елементів
3.2 Реалізувати функцію f4 у базисі Буля. На виході кожного елемента написати формулу сигналу, який даним елементом реалізується. Для 1 довільного вхідного набору визначити рівні сигналів (0 або1) на виході кожного елемента схеми. Усі елементи повинні мати не більше двох входів. Навести таблиці істинності задіяних елементів.
3.3 Реалізувати функцію f4 у монобазисі І-НЕ. На виході кожного елемента І-НЕ написати формулу сигналу, який даним елементом реалізується. Для 1 довільного вхідного набору визначити рівні сигналів (0 або1) на виході кожного елемента схеми. Елементи можуть мати довільну кількість входів. Навести таблиці істинності задіяних елементів.
3.4 Реалізувати функцію f4 у монобазисі Шеффера. На виході кожного елемента Шеффера написати формулу сигналу, який даним елементом реалізується. Для 1 довільного вхідного набору визначити рівні сигналів (0 або1) на виході кожного елемента схеми. Усі елементи Шеффера повинні бути двовходовими. Навести таблиці істинності елемента Шеффера.
3.5 Реалізувати функцію f4 у монобазисі АБО-НЕ. На виході кожного елемента АБО-НЕ написати формулу сигналу, який даним елементом реалізується. Для 1 довільного вхідного набору визначити рівні сигналів (0 або1) на виході кожного елемента схеми. Елементи можуть мати довільну кількість входів. Навести таблиці істинності задіяних елементів.
3.6 Реалізувати функцію f4 у монобазисі Пірса. На виході кожного елемента Пірса написати формулу сигналу, який даним елементом реалізується. Для 1 довільного вхідного набору визначити рівні сигналів (0 або1) на виході кожного елемента схеми. Усі елементи Пірса повинні бути двовходовими. Навести таблиці істинності елемента Пірса.
3.7 Функцію f4 реалізувати за допомогою дешифраторів. У кожного з задіяних дешифраторів кількість виходів не повинна перевищувати 16. Навести таблиці істинності, які пояснюють роботу задіяних дешифраторів.
3.8 Функцію f4 реалізувати за допомогою мультиплексорів. У кожного з задіяних мультиплексорів кількість інформаційних виходів не повинна перевищувати 16. Навести таблиці істинності, які пояснюють роботу задіяних мультиплексорів.
Календарний план
№
п/п
Назва етапів роботи
Термінт виконання еттапів роботи
Примітка
1
Кодування інформації та перетворення кодів
10.03
2
Функції алгебри логіки та їх мінімізація
08.04
3
Синтез комбінаційних схем
05.05
4
Оформлення пояснювальної записки
12.05
Студент Купира Ольга Миколаївна
(підпис) (прізвище, ім’я та по-батькові )
Керівник Бортник Катерина Яківна
(підпис) (прізвище, ім’я та по-батькові )
«23» лютого 2011р.
ЗМІСТ
ВСТУП 8
І. ТЕОРЕТИЧНА ЧАСТИНА 12
1. Системи числення та функції алгебри логіки 12
1.1. Позиційні системи числення 13
1.2. Алгоритми переведення чисел з однієї позиційної системи числення в іншу 16
1.3. Функціональна повнота системи функцій алгебри логіки і наборів логічних елементів 18
2. Булеві функції. 22
2.1. Булеві функції однієї та двох змінних 24
2.2. Еквівалентні формули 27
2.3. Принцип двоїстості булевих функцій 29
3. Мінімізація булевих функцій 30
3.1. Метод послідовного застосування законів та тотожностей алгебри логіки 33
3.2. Метод Квайна 34
3.3. Метод Квайна - Мак - Класкі 36
4.Синтез комбінаційних схем. 46
4.1 Синтез функцій у базисі Були на елементах з довільною кількістю входів 47
4.2. Реалізація функцій алгебри логіки на дешифраторах 50
4.3. Синтез комбінаційних схем на базі мультиплексорів 53
4.4. Синтез комбінаційних схем на базі постійних запам'ятовуючих пристроїв 56
ІІ. Практична частина 60
Перша частина 60
Завдання 1.1 60
Завдання 1.2 62
Завдання 1.3 63
Друга частина 65
Завдання 2.1 65
Завдання 2.2 67
Завдання 2.3 68
Завдання 2.4 68
Третя частина 73
Завдання 3.1 73
Завдання 3.2 75
Завдання 3.3 76
Завдання 3.4 77
Завдання 3.5 78
Завдання 3.6 80
Завдання 3.7 82
Завдання 3.8 84
Висновок 86
ЛІТЕРАТУРА 87
ВСТУП
Стрімкий розвиток цифрової обчислювальної техніки (ОТ) та становлення науки про принципи її побудови і проектування розпочалося в 40-х роках ХХ- го сторіччя, коли технічною базою ОТ стала електроніка, потім мікроелектроніка, а основою для розвитку архітектури комп’ютерів (електронних обчислювальних машин ЕОМ) – досягнення в галузі штучного інтелекту.
До цього часу протягом майже 500 років цифрова обчислювальна техніка зводилася до найпростіших пристроїв для виконання арифметичних операцій над числами. Основою практично усіх винайдених за 5 століть пристроїв було зубчате колесо, розраховане на фіксацію 10 цифр десяткової системи числення.
Перший у світі ескізний малюнок тринадцяти розрядного десяткового підсумовуючого пристрою на основі коліс із десятьма зубцями належить Леонардо да Вінчі (1452-1519). Він був зроблений в одному із його щоденників (учений почав вести щоденник ще до відкриття Америки в 1492 р.)
Першим реально здійсненим і ставшим відомим механічним цифровим обчислювальним пристроєм стала «паскаліна» великого французького вченого Блеза Паскаля (1623 - 1662) – 6 ти (або 8-ми) розрядний пристрій на зубчатих колесах, розрахований на підсумовування та віднімання десяткових чисел (1642 р.).
Через 30 років після «паскаліни» у 1673 р. з’явився «арифметичний прилад» Готфріда Вільгема Лейбніца (1646 – 1716) – дванадцятирозрядний десятковий пристрій для виконання арифметичних операцій, включаючи множення і ділення, для чого, на додаток до зубчатих коліс використовувався східчастий валик. « Моя машина дає можливість чинити множення і ділення над величезними числами миттєво» - із гордістю писав Лейбніц своєму другу.
У тому ж 1937 р., коли запрацювала перша у світі двійкова машина Z1, Джон Атанасов (1903 – 1963) болгарин за походженням, що жив у США, почав розробку спеціалізованого комп’ютера вперше у світі застосувавши електронні лампи (300 ламп).
Завершальну крапку в створенні перших ЕОМ поставили, майже одночасно, у 1949 – 1952 рр. вчені Англії, Радянського Союзу і США, які створили ЕОМ із програмою, що зберігалася у пам’яті: Моріс Уілкс – ЕДСАК (1913, Electronic Delay Storage Automate Computer EDSAC) – електронний автоматичний комп’ютер на лініях затримки, 1949 р.; Сергій Лебедєв (1902 – 1974) – Мала електронно лічильна машина «МЕСМ», 1951р.
Перші покоління утворювали лампові ЕОМ, промисловий випуск яких розпочався на початку 50-х років. В якості компонентів логічних елементів використовувались електронні лампи.
Обчислювальні можливості мікро ЕОМ виявились достатніми для створення на їх основі в рамках ЕОМ четвертого покоління, нового за рядом експлуатаційних характеристик та способу використання типа обчислювальних пристроїв – персональних ЕОМ ( персональних комп’ютерів), які отримали в теперішній час широке поширення.
Згідно цьому проекту ЕОМ і обчислювальні системи п’ятого покоління крім більш високої продуктивності та надійності при більш низькій вартості повинні мати такі якісно нові властивості: можливість взаємодії з ЕОМ за допомогою природної мови, людського голосу і графічних зображень; здатність системи «розуміти» вміст бази даних, яка при цьому перетворюється в «базу знань», і використовуючи ці «знання» при розв’язку задач.
Розвиток електроніки, є однією із прогресивних галузей науки і техніки сприяє розв’язку задач фундаментальних наукових досліджень і прикладних проблем, зв’язаних з науково-технічним прогресом. За допомогою електронних систем здійснюється контроль, керування і регулювання, різними виробничими процесами і пристроями, вимір електричних і неелектричних величин, відбір, обробка і передача інформації будь-якого призначення. Більшість методів дослідження в різних сферах науки і техніки зв’язано з використанням електронних пристроїв.
Сучасні засоби електронної техніки виробляються, в основному, на основі інтегральних мікросхем. Інтеграція радіо компонентів дозволила не тільки зменшити розміри електронного приладу і використовуєму цим приладом потужність, але і відкрила принципово новий етап в розвитку радіоелектроніки, охоплюючий всю сферу організаціїви робництва. І. ТЕОРЕТИЧНА ЧАСТИНА
1. Системи числення та функції алгебри логіки
Кожне число містить цифри. Спосіб запису чисел цифровими знаками називається системою числення. Звичайно для нас і загальноприйнятою є позиційна десяткова система числення.
Система числення, в якій значення кожної цифри в довільному місці послідовності цифр, яка означає запис числа, не змінюються, називається не позиційною. Система числення, в якій значення кожної цифри залежить від місця в послідовності цифр у записі числа, називається позиційною.
Запис числа в деякій системі числення називають кодом числа. Коротко число можна представити наступним чином:
A=a n a n-1 …a2 a 1 a0 .
Окрему позицію зображення числа прийнято називати розрядом а номер позиції – номер розряду. Число розрядів у записі числа називають його розрядністю і співпадає з його довжиною. В технічному аспекті довжина числа інтерпретується як розрядність сітки.
Системи числення можна класифікувати наступним чином:
Рис 1.1 Системи числення
В основному системи числення будуються за наступним принципом:
А(р)=а1р1+а2р2+…+аnрn
Де А(р) – запис числа у системі з базисом рі, аі це база або послідовність цифр системи числення з Рі алфавітом. {pc} – базис системи числення.
1.1. Позиційні системи числення
Загальноприйнятою в сучасному світі є десяткова позиційна система числення, яка з Індії через арабські країни прийшла в Європу. Основою цієї системи числення є число десять. Основою системи числення називається число, яке означає, у скільки разів одиниця наступного розряду більше за одиницю попереднього.
Позиційними називається алфавіт, який має обмежену кількість символів, причому значення кожної цифри в числі знаходиться в строгій залежності від позиції в числі. Позиційні системи числення мають ряд переваг у порівнянні з непозиційними, зокрема зручність у виконання арифметичних операцій. У позиційній системі числення число може бути представлене наступним чином:
А=а nр n-1…р1+а n-1р n-2 …р1+…+а2р1+а1,
де аі – цифра і-го розряду числа, рі – основа системи числення.
Проблема вибору системи числення для подання чисел у пам’яті комп’ютера має велике практичне значення. В разі її вибору звичайно враховуються такі вимоги, надійність подання чисел при використанні фізичних елементів, економічність (використання таких систем числення, в яких кількість елементів для подання чисел із деякого діапазону була б мінімальною). Для зображення цілих чисел від 1 до 999 у десятковій системі числення достатньо трьох розрядів, тобто трьох елементів. Оскільки кожен елемент може перебувати в десятьох станах, то загальна кількість станів – 30, у двійковій системі числення 99910=1111100, необхідна кількість станів – 20 (індекс знизу зображення числа – основа системи числення). У такому розумінні є ще більш економічна позиційна система числення трійкова. Так, для запису цілих чисел від 1 до у десятковій системі числення потрібно 90 станів, у двійковій – 60, у трійковій – 57. Але трійкова система числення не дістала поширення внаслідок труднощів фізичної реалізації.
Тому найпоширенішою для подання чисел у пам’яті комп’ютера є двійкова система числення. Для зображення чисел у цій системі необхідно дві цифри: 0 і 1, тобто достатньо двох стійких станів фізичних елементів. Ця система є близькою до оптимальної за економічністю, і крім того, таблички додавання й множення в цій системі елементарні:
Оскільки 23=8, а 24=16, то кожних три двійкових розряди зображення числа утворюють один вісімковий, а кожних чотири двійкових розряди – один шістнадцятковий. Тому для скорочення запису адрес та вмісту оперативної пам’яті комп’ютера використовують шістнадцяткову й вісімкову системи числення.
В процесі налагодження програм та в деяких інших ситуаціях у програмуванні актуальною є проблема переведення чисел з однієї позиційної системи числення в іншу. Якщо основа нової системи числення дорівнює деякому степеню старої системи числення, то алгоритм переводу дуже простий: потрібно згрупувати справа наліво розряди в кількості, що дорівнює показнику степеня і замінити цю групу розрядів відповідним символом нової системи числення. Цим алгоритмом зручно користуватися коли потрібно перевести число з двійкової системи числення у вісімкову або шістнадцяткову. Наприклад, 101102=268, 10111002=5С8.
У двійковому відбувається за зворотнім правилом: один символ старої системи числення заміняється групою розрядів нової системи числення, в кількості рівній показнику степеня нової системи числення.
Як бачимо, якщо основа однієї система числення дорівнює деякому степеню іншої, то перевід тривіальний. У протилежному випадкові користуються правилами переведення числа з однієї позиційної системи числення в іншу (найчастіше для переведення із двійкової, вісімкової та шістнадцяткової систем числення у десяткову, і навпаки).
1.2. Алгоритми переведення чисел з однієї позиційної системи числення в іншу
Ефективний засіб переведення чисел з однієї системи числення в іншу – це використання схеми Горнера або ваги коефіцієнтів.
Схема Горнера для цілої частини має вигляд:
Ар=(…(аn-1р+аn-2)р+…а2)р+а0 , де
аі – цифра і-ого розряду, рі – основа системи числення.
Правила переведення дробової частини з системи числення з довільною основою в десяткову систему числення.
Дробова частина записується, як і ціла частина з використанням розширеного запису схеми Горнера:
Ap=(a-1pm-1+a-2pm-2+…+amp0)1/pm , де
m – число розрядів після коми.
Правила переведення цілих чисел з десяткової системи числення в систему числення з довільною основою.
Ціле число в десятковій системі числення послідовно ділимо на основу системи числення поки не з’явиться частка, менша за основу. Число в новій системі числення запишеться як послідовність залишків ділення, починаючи з останнього.
Правила переведення дробової частини з десяткової системи числення в систему числення з довільною основою.
Переведення дробової частини проводиться як множення дробу на основу, і обчислюється результат як ціла частина добутку, починаючи з першої, після відокремлення крапкою, цифри.
1.3. Функціональна повнота системи функцій алгебри логіки і наборів логічних елементів
Основна вимога, яка ставиться до набору логічних елементів, полягає в тому, щоб за допомогою цього набору можна було побудувати будь-яку логічну схему. З огляду на те, що функціонування елементів однозначно описується функціями алгебри логіки (ФАЛ), застосовуючи операцію суперпозиції, можна з деякої системи ФАЛ отримати будь-яку, скільки завгодно складну ФАЛ. Тоді ця деяка система ФАЛ буде називатися функціонально повною (ФПС ФАЛ).
Функціонально повним є такий набір ФАЛ, який містить хоча б одну функцію, яка:
не зберігає константу «0»;
не зберігає константу «1»;
не є монотонною;
не є само двоїстою;
не є лінійною.
Якщо функція f на нульовому наборі змінних дорівнює 0, тобто f(0,0,…,0)=0, то ця функція зберігає константу «0».
Якщо функція f на одиничному наборі змінних дорівнює 1, тобто f(1,1,…,1)=1, то ця функція зберігає константу «1».
ФАЛ називається монотонною, якщо при будь-якому зростанні кількості «1» у послідовності сусідніх (тобто таких, які відрізняються тільки в одному розряді) наборів змінних (х18х19…,хn) значення функції не зменшується.
ФАЛ називається самодвоїстою, якщо на кожній парі протилежних наборів вона приймає протилежні значення, тобто, якщо f0=f15, f2=f11 і т.д.
ФАЛ називається лінійною, якщо її можна зобразити поліномом Жегалкіна без добутків змінних:
f(x1,…,xn) = a0 /a1x1/…/an xn ,
де а = (1,0).
Для того щоб записати функцію, яка задано таблично, у вигляді полінома Жегалкіна, досить записати цю функцію у вигляді суми за модулем 2 тих наборів аргументів, на яких функція дорівнює 1. Після цього потрібно всі змінні, які входять до отриманого виразу з інверсіями, замінити за допомогою співвідношення / розкрити дужки і звести подібні члени за допомогою тотожності
х/х/…/х=х, якщо кількість х непарна;
х/х/…/х=0, якщо кількість х парна.
У табл.. 1.2 наведені функції двох змінних і позначкою * вказана їх належність кожному з класів ФАЛ. У графі «Клас» позначено:
0 - зберігає константу «0»;
1 - зберігає константу «1»;
Л - лінійна;
М - монотонна;
С - само двоїста.
Таблиця 1.3.1 Функції алгебри логіки
f14 i f8 – є функціонально повними. Використовуючи f14 i f8 можна записати формулу будь-якої логічної функції.
Є 5 основних базисів:
1) Базис Буля, який включає і, або, не.
2) Базис і, не.
3) Базис або, не.
4) Базис Шиффера.
5) Базис Пірса.
Приклад. Перевірити функцію задано таблично (таблиця 1.3.2) чи становить функціонально повну систему.
Таблиця 1.3.2 Таблиця істинності функції
x1
x2
x3
f
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
1) Функція не зберігає константу «0». f(0,0,0)=0
2) Функція не зберігає константу «1». f(1,1,1)=1
3) Функція не монотонна: f(0,0,0)=0 = f(0,0,1)=0 < f(0,0,0)=1 = f(0,0,0)=1
4) Функція само двоїста:
f(0,0,0)=0 f(1,1,1)=1
f(0,0,1)=0 f(1,1,0)=1
f(0,1,0)=1 f(1,0,1)=0
f(0,1,1)=1 f(1,0,0)=0
5) Запишемо ДДНФ
/
Замінимо диз’юнкцію на додавання по модолю 2.
/
/
Функція лінійна, бо не включає добутки.
Висновок: Отже, функція не є функціонально повною, тому що вона не зберігає константу «0» та константу «1».
2. Булеві функції.
Щоб описати схеми, які будуються шляхом сполучення різних вентилів, потрібний особливий тип алгебри, у якій всі змінні й функції можуть приймати тільки два значення: 0 і 1. Така алгебра називається булевою алгеброю. Вона названа на честь англійського математика Джорджа Буля (1815-1864). Насправді в цьому випадку ми говоримо про особливий тип мулевої алгебри, а саме про алгебру релейних схем, але термін «булева алгебра» дуже часто використовується в значені «алгебра релейних схем», тому ми не будемо їх розрізняти.
Основним предметом мулевої алгебри є висловлювання – просте твердження, про яке можна стверджувати: істинне воно (позначають символом 1), або хибне (позначають символом 0). Прості висловлювання позначають буквами, наприклад xx,x2,…,xm, які у цифровій техніці називають змінними (аргументами).
У даний час головна задача алгебри логіки – аналіз, синтез і структурне моделювання будь-яких дискретних скінчених систем.
Змінну із скінченим числом значень (станів) називають перемикальною, а з двома значення ми – булевою.
Операція це чітко визначена дія над одним або декількома операндами, яка створює новий об’єкт (результат).
У булевій операції операнди і результат набувають «булевого значення 1» і «булевого значення 0».
Булеві функції можуть залежати від однієї, двох і в цілому n – змінних. Булева функція n – аргументів може мати до N = 2N наборів. Оскільки функції приймають тільки два значення, загальне число булевих функцій n - аргументів дорівнює 2N = 22N. Отже, функція одного аргументу може мати чотири значення:
y = x;y = x;y = 1 (константа1); y = 0 (константа 0).
Основними мулевими операціями є заперечення (операція НЕ, інверсія), диз’юнкція (операція АБО, логічне додавання, об’єднання) і кон’юнкція (операція І, логічне множення).
Основні аксіоми алгебри логіки:
х=0, якщо х≠1;
х=1, якщо х≠0;
1۷1=1;
0۷0=0;
0۷1=1۷0=1;
0=1;
1=0;
0۸0=0;
1۸1=1;
1۸0=0۸1=0;
Довільна булева функція задається 1 із 3 методів:
Матричний
Геометричний
Аналітичний
Суттєві та несуттєві змінні.
Розглянемо поняття суттєвої залежності функції від її змінних. Почнемо з прикладів: значення функції h2(x,y) з прикладу 2 на кожному з наборів збігаються зі значеннями x. Отже, зміна значення y не впливає на значення функції, тобто вона фактично не залежить від у. В той час як зміна значення x веде до зміни значення h2. Уточнимо ці міркування наступними означеннями.
Означення. Змінна xi функції f(n)(x1,x2,…,xi,…,xn) називається суттєвою, якщо існує хоча б одна пара наборів значень змінних
(1,2,…,і-1,0,і+1,…,n) і (1,2,…,і-1,1,і+1,…,n),
Така, що
f(n)(1,2,…,і-1,0,і+1,…,n) f(n)(1,2,…,і-1,1,і+1,…,n).
Зміна хі називається несуттєвою у противному разі, тобто коли за всіх можливих пар наборів значень (1,2,…і-1,0,і+1,…n) і (1,2,…,і-1,1,і+1,. ..,n) мають місце рівності:
f(n)(1,2,…,i-1,0,i+1,…,n)=f(n)(1,2,…,i-1,1,i+1,…,n).
Наприклад, неважко переконатися, що всі змінні функції h1 з прикладу 1 є суттєвими. Функція h2 має суттєву змінну х і несуттєву у. Функція двох змінних задана як вектор (1111), не має суттєвих змінних.
2.1. Булеві функції однієї та двох змінних
Булеві функції однієї змінної, N=1, отже P=22N=4. Всього таких функцій чотири, їх таблиця істинності подана в таблиці 2.1.1:
Табл..2.1.1 Булеві функції однієї змінної
Змінна х
0
1
Назва функції
Позначення
Нуль
0
0
0
Тотожність
~
0
1
Заперечення
02.04.2013 19:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора