Комп’ютерна логіка

1.

Комп’ютерна логіка (частина 1)
Національний університет «Львівська
політехніка»
Слайдів
410

2. Лекція 1

• Вступ - мета та задачі курсу
• Організаційні питання
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
2

3. Розклад викладача, консультації – Пн, Вт, Ср після 4-ої пари, 503-V (каф. ЕОМ)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
3

4. Комп’ютерна логіка

• ЛОГІКА - наука про закони і різновиди мислення, способи пізнання
та умови істинності знань і суджень
• КОМП’ЮТЕР – пристрій для передавання, зберігання та оброблення
інформації
• КОМП'ЮТЕРНА ЛОГІКА - умовна назва області досліджень, що
ставиться до прикладної логіки, у якій логічні методи застосовуються
для обробки даних і знань у комп'ютерних системах, при створенні
системних програм, що забезпечують функціонування ЕОМ, при
автоматизації програмування й при створенні ЕОМ нових поколінь. К.
л. може виступати як сукупність засобів для імітації пізнавальних
процесів у комп'ютерних системах з підвищеним рівнем
інтелектуальних можливостей, забезпечуючи пошук необхідних знань
для досягнення обраної мети й процес виводу результату, що
відповідає цієї мети.
• КОМП'ЮТЕРНА ЛОГІКА – наука про закони і різновиди мислення,
якими користуються люди коли описують роботу комп’ютерів та
працюють з ними (проектують, ремонтують, обслуговують,
користуються)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
4

5. Національний університет “Львівська політехніка”

ІАРХ
ІБІД
ІГДГ
ІГСН
ІДН
ІЕПТ
ІНЕМ
ІЕСК
ІІМТ
ІКНІ
ІКТА
МІОК
ІППТ
ІПДО
ІНПП
ІМФН
ІТРЕ
ІХХТ
НУЛП 20162017 н.р.
Архітектури
Будівництва та інженерії довкілля
Геодезії
Гуманітарних та соціальних наук
Дистанційного навчання
Екології, природоохоронної діяльності та туризму ім. В’ячеслава
Чорновола
Економіки і менеджменту
Енергетики та систем керування
Інженерної механіки та транспорту
Комп'ютерних наук та інформаційних технологій
Комп'ютерних технологій, автоматики та метрології
Міжнародний інститут освіти, культури та зв’язків з діаспорою
Підприємництва та перспективних технологій
Післядипломної освіти
Права та психології
Прикладної математики та фундаментальних наук
Телекомунікацій, радіоелектроніки та електронної техніки
Хімії та хімічних технологій
Глухов В.С. Комп'ютерна логіка
5

6. Комп'ютерних технологій, автоматики та метрології

БІТ
ЕОМ
ЗІ
ІВТ
Кафедра безпеки інформаційних технологій
Кафедра електронних обчислювальних машин
Кафедра захисту інформації
Кафедра інформаційно-вимірювальних
технологій
КСА
Кафедра комп'ютеризованих систем
автоматики
МСС
Кафедра метрології, стандартизації та
сертифікації
ПТМ
Кафедра приладів точної механіки
СКС
Кафедра спеціалізованих комп'ютерних систем
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
6

7. Кафедри ЕОМ та СКС

• Бакалаврат (каф. ЕОМ та СКС) Комп’ютерна інженерія
• Магістри (спеціалізації каф. ЕОМ)
– Комп’ютерні системи та мережі
– Кіберфізичні системи
– Системне програмування
• Магістри (спеціалізація каф. СКС)
– Спеціалізовані комп’ютерні системи
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
7

8. Структура семестру

• 16 навчальних тижнів (16 лекцій, 8
практичних)
• Заліковий тиждень
• Сесія (2 тижні)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
8

9. Державна оцінка (залік)

• 1. За результатами семестрової контрольної
роботи
• 2а. Оцінка на комісії
– або
• 2б. Оцінка за результатами повторного
вивчення курсу
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
9

10. Стандартні вимоги до відповідей на заліках та іспитах

• Повинна бути дана відповідь на усі питання
білету
• Під час підготовки до відповіді нічим не
можна користуватися
• Під час підготовки до відповіді ні с ким не
можна перемовлятися та обмінюватися
інформацією
• Для допуску до сесії потрібно виконати
навчальний план
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
10

11. Виконання навчального плану

• Студент погоджується самостійно опрацювати деякі
питання учбового плану
• Здана розрахункова робота (є оцінка)
• Виконано програму практичних занять
• Написано усі 16 лекційних контрольних робіт
• Дано відповідь на усі 10 питань семестрової контрольної
роботи
• Є конспект лекцій (приблизно 5 сторінок на лекцію)
• Правильно дано відповіді на усі питання тестів до 1-ої
частини Комп’ютерної логіки (1-ий курс) у ВНС
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
11

12. Полегшені умови отримання семестрової оцінки

• Білет семестрової контрольної роботи видається
достроково до 15-го навчального тижня за умови:
–
–
–
–
Виконано розрахункову роботу
За практичні заняття отримано більше 18 балів (з 25)
Написано усі лекційні контрольні роботи на дану дату
Правильно дано відповіді на усі питання тестів до 1-ої
частини Комп’ютерної логіки (1-ий курс) у ВНС
– Є конспект лекцій (приблизно 5 сторінок на лекцію)
• Під час підготовки до відповіді дозволяється
користуватися чим завгодно
• Повинна бути дана відповідь на усі питання
білету
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
12

13. Оцінювання відповідей при стандартному підході

Оцінка Оцінка практичні Оцінка ЛекційніКР Оцінка білет
Оцінка 100; Оцінка практичні 25; Оцінка ЛекційніКР 5; Оцінка білет 70
Оцінювання відповідей при полегшеному підході
Оцінка Оцінка практичні
Сума балів ЛекційніКР * Сума балів за тести
80 * 100
* Оцінка білет
Оцінка 100; Оцінка практичні 30; Сума балів ЛекційніКР 80; Оцінка білет 70;
Сума балів за тести 100
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
13

14. Покращення оцінок

• Було 51 бал – 51% від 100 балів
(поточний контроль – 1 з 30, іспит - 50 з 70,
3% з 30 за поточку і 71% з 70 за іспит)
• Хоче “добре” (71 бал – 71% від 100 балів)
• Тоді треба набрати спочатку за поточний
контроль 71% від 30 = 21 бал,
а після того -71% від 70 =50 балів за іспит.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
14

15. Методичні вказівки до курсової роботи “Арифметичні та логічні основи комп’ютерних технологій” з дисципліни "Комп’ютерна логіка"

Методичні вказівки до курсової роботи “Арифметичні та
логічні основи комп’ютерних технологій” з дисципліни
"Комп’ютерна логіка"
ВСТУП
ЗАВДАННЯ НА РОБОТУ, ВКАЗІВКИ ЩОДО ВИБОРУ ВАРІАНТА РОБОТИ
1 МЕТОДИЧНІ ВКАЗІВКИ ЩОДО КОДУВАННЯ ІНФОРМАЦІЇ ТА ПЕРЕТВОРЕННЯ
КОДІВ
1.1 W1
1.1.1. Переведення чисел до десяткової системи числення з іншої однорідної позиційної системи
числення з основою k, коли дії виконуються в десятковій системі
1.1.2. Переведення чисел із десяткової системи числення до іншої однорідної позиційної системи
числення з основою k, коли дії виконуються в десятковій системі
1.1.3. Переведення цілої частини числа
1.1.4. Переведення дробової частини числа
1.1.5. Переведення чисел з шістнадцяткової й вісімкової систем до двійкової і зворотне переведення
чисел
1.2 W2 Ефективне кодування. Система залишкових класів
1.2.1. Алгоритм ефективного кодування Шеннона – Фано
1.2.2. Ентропія.
1.2.3. Система залишкових класів
1.3 Код Геммінга
1.4 Визначення помилкових станів при зміні двійкових кодів
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
15

16. Методичні вказівки до курсової роботи “Арифметичні та логічні основи комп’ютерних технологій” з дисципліни "Комп’ютерна логіка"

Методичні вказівки до курсової роботи “Арифметичні та
логічні основи комп’ютерних технологій” з дисципліни
"Комп’ютерна логіка"
• 2 МЕТОДИЧНІ ВКАЗІВКИ ЩОДО
ВИКОРИСТАННЯ ФУНКЦІЙ АЛГЕБРИ
ЛОГІКИ ТА МІНІМІЗАЦІЇ ЦИХ ФУНКЦІЙ У
БАЗИСІ БУЛЯ
• 2.1 Функціональна повнота системи функцій
алгебри логіки і наборів логічних елементів
• 2.2 Мінімізація функцій методом КвайнаМакКласкі-Петрика
• 2.3 Мінімізація функцій за допомогою карт Карно
• 2.4 Визначення сполучного терма
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
16

17. Робочий журнал

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
17

18. Відробка пропущених лекційних контрольних робіт

• Копія конспекту за пропущену лекцію
(якщо у журналі є порожня клітинка або Н)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
18

19. Віртуальне Навчальне Середовище - ВНС

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
19

20. Тема у ВНС

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
20

21. Білет семестрової контрольної роботи

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
21

22. Конспект

• Поле – для важливих приміток (дата, №
лекції, № питання, NB, …)
• Основна частина – для скороченого запису
помилок, які робить викладач
– Графічна частина
– Текстові пояснення
• Знизу - № сторінки, Прізвище І.П.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
22

23. Внаслідок вивчення навчальної дисципліни студент повинен бути здатним продемонструвати такі результати навчання, а саме знати

та використовувати :
інформаційні основи комп’ютерної логіки;
методи представлення чисел в ЦА;
правила переведення чисел з однієї системи числення до іншої;
алгоритми виконання основних арифметичних і логічних операцій в
ЦА;
правила виконання арифметичних і логічних операцій у різних
системах числення;
основи формальної логіки;
форми запису логічних виразів;
основи синтезу і мінімізації функцій алгебри логіки у різних базисах;
правила створення схем електричних функціональних логічних вузлів
цифрових схем;
базові комбінаційні логічні вузли цифрової техніки;
методи і засоби контролю і діагностики логічних схем.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
23

24. Підготовлений фахівець повинен вміти:

• записувати, читати і розуміти логічні
вирази;
• аналізувати і синтезувати ЦА в різних
логічних базисах;
• володіти методами мінімізації логічних
виразів;
• застосовувати набуті знання в практичній
діяльності.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
24

25. Вивчення навчальної дисципліни передбачає формування та розвиток у студентів компетентностей: загальних:

З письмової комунікації (на рівні передавання складної інформації);
З усної комунікації (на рівні передавання складних повідомлень);
Здатність спілкуватися першою (рідною) мовою, вміння правильно, логічно, ясно будувати своє усне й
писемне мовлення;
Володіння необхідними навичками професійного спілкування другою (іноземною) мовою;
Знання та розуміння предметної галузі, професії; основних концепцій, базових категорій, технічних
понять;
Здатність до безперервного та активного навчання, самоосвіти, постійного підвищення кваліфікаціі;
Аналітичного мислення (на рівні застосування загального аналізу);
Здатність до абстрактного мислення, аналізу та синтезу;
Здатність до міжособистісного спілкування; уміння працювати в команді, мотивувати людей та досягати
спільної мети; розуміння та повага до різноманітності та мультикультурності;
Здатність діяти з урахуванням соціальної відповідальності та громадянських зобов’язань, з повагою
ставитися до права й закону;
Здатність визначати, формулювати та розв’язувати задачі, аналізувати соціально-значущі процеси та
приймати обґрунтовані рішення;
Розв’язання проблем (на рівні розв’язання складних проблем);
Планування та організації (на рівні планування та організація багатокомпонентної складної діяльності);
Критичного мислення (на рівні формулювання загальних стратегій з багатовимірних стратегічних
питань);
Здатність розуміти значення інформації в сучасному суспільстві, відповідально ставитися до питань
інформаційної безпеки;
Уміння знаходити, обробляти та аналізувати інформацію з різноманітних джерел; здатність
використовувати інформаційно-комунікативні технології.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
25

26. Фахових компетенцій:

Знання дискретних структур і вміння застосовувати сучасні методи дискретної математики для
аналізу і синтезу складних систем виконання кодування інформаційних повідомлень, у тому числі
користуючись методами побудови завадозахисних кодів та кодами Хеммінга;
Знання теоретичних (логічних та арифметичних) основ побудови сучасних комп’ютерів та їх
архітектури, вміння застосовувати їх в процесі побудови та експлуатації при рішенні професійних
завдань.
Складання логічних виразів;
Читання і розуміння логічних виразів;
Спрощення логічних виразів;
Розроблення комбінаційних схем для реалізації системи перемикальних функцій у заданому
елементному базисі, сформулювавши задачу її побудови у термінах теорії перемикальних
функцій, виконавши мінімізацію функцій та отримавши необхідні операторні форми з
урахуванням засобів уникнення збою в схемах;
Виконання абстрактний синтезу цифрового автомата, зробивши формальний опис алгоритму його
функціонування у термінах теорії цифрових автоматів та виконавши процедуру мінімізації числа
станів автомата;
Виконання структурного синтезу синхронних та асинхронних автоматів, застосовуючи способи
мінімізації функцій збудження та виходів, а також уникнення збоїв в умовах використання для
побудови схеми автомата заданого елементного базису, в тому числі інтегральних схем, що
програмуються;
Розроблення алгоритму функціонування арифметичного пристрою на підставі форми
представлення інформації, алгоритмів виконання арифметичних операцій в різних системах
числення в умовах застосування методів контролю роботи пристрою з використанням систем
автоматизованого проектування комп’ютерних засобів.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
26

27. Результати навчання даної дисципліни деталізують такі програмні результати навчання:

Уміння застосовувати знання у практичних ситуаціях.
Уміння адаптуватись до нових ситуацій
Уміння ефективно працювати як автономно, так і у складі команди.
Уміння відповідально ставитись до виконуваної роботи та досягти поставленої мети
Уміння застосовувати знання і розуміння для розв’язання задач синтезу та аналізу цифрових вузлів.
Уміння спілкуватись включаючи усну та письмову комунікацію українською мовою та однією з іноземних мов
(англійською, французькою, німецькою).
Уміння використовувати інформаційні і комунікаційні технології для вирішення різних дослідницьких і
професійних завдань.
Уміння здійснювати пошук інформації в різних джерелах для розв’язання задач спеціальності.
Уміння приймати обґрунтовані рішення та оцінювати їх наслідки.
Уміння використовувати базові знання основ філософії, психології, педагогіки в професійній і соціальній
діяльності.
Уміння сприймати критику, критикувати особистість, самокритично відноситись до своїх поступків та
критикувати результати роботи.
Уміння дотримуватися кодексу професійної етики, керуватися в поведінці моральними нормами та цінностями,
дотримуватися правил етикету.
Уміння застосовувати сучасні методи дискретної математики для аналізу, синтезу та проектування цифрових
вузлів.
Уміння застосовувати базові знання стандартів в області інформаційних технологій під час розробки цифрових
вузлів.
Уміння обробляти отримані результати, аналізувати та осмислювати їх, представляти результати роботи і
обґрунтовувати запропоновані рішення на сучасному науково-технічному і професійному рівні
Уміння застосовувати комп’ютерніі засоби при проектуванні та створенні цифрових вузлів.
Уміння опановувати та розробляти документацію на системи, продукти і сервіси інформаційних технологій,
спілкуватись рідною мовою, професійно спілкуватись англійською мовою.
Підготовленість до використання існуючих та розроблення нових математичних методів для вирішення задач,
пов’язаних
НУЛП
2016- з проектуванням цифрових вузлів.
27
Глухов В.С. Комп'ютерна логіка
2017 н.р.

28. Навички (компетенції) випускників

• конвертувати академічні знання і навички в результати
практичного вирішення технічних задач;
• вирішувати складні задачі в галузі комп'ютерної техніки
та ефективно адаптуватися у швидко мінливому
середовищі;
• використовувати систематичний і методичний стиль
роботи;
• застосовувати правильну термінологію і позначення як у
письмовій формі так і в усній;
• обговорювати основні теорії та методи аналізу і обробки
аналогових і цифрових сигналів з використанням
правильної термінології;
• застосувати знання математики та фізики (у тому числі
теорії ймовірності, статистики та дискретної математики,
диференціального та інтегрального числення), інші
досягнення науки і техніки;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
28

29. Навички (компетенції) випускників

• визначити, формулювати та проводити дослідження,
направлені на вирішення інженерної завдачі за допомогою
відповідного огляду літератури, робити обгрунтовані
висновки;
• планувати і проводити експерименти та тести, а також
аналізувати та інтерпретувати отримані експериментальні
дані та робити обґрунтовані висновки;
• критично мислити, аналізувати і приймати рішення, які
належним чином враховують глобальні проблеми в
–
–
–
–
–
НУЛП 20162017 н.р.
бізнесі,
етиці,
моралі,
суспільстві і
навколишньому середовищі;
Глухов В.С. Комп'ютерна логіка
29

30. Навички (компетенції) випускників

• проектувати комп’ютерні системи, компоненти або
процеси для задоволення бажаних потреб в рамках
реалістичних обмежень:
–
–
–
–
–
–
–
–
НУЛП 20162017 н.р.
економічних,
екологічних,
соціальних,
політичних,
етичних,
здоров'я та безпеки,
технологічності і
стійкості;
Глухов В.С. Комп'ютерна логіка
30

31. Навички (компетенції) випускників

• розробляти та реалізовувати апаратні засоби або
програмне забезпечення системи вбудованих компонентів
для задоволення бажаних потреб та вимог, у тому числі:
–
–
–
–
–
–
–
–
НУЛП 20162017 н.р.
продуктивності,
економічної ефективності,
безпеки,
маса-габаритних характеристик,
часу,
споживання,
ефективності і
ергономічності та ефективності користувальницьких інтерфейсів;
Глухов В.С. Комп'ютерна логіка
31

32. Навички (компетенції) випускників

• розуміти вплив технічних рішень в соціальному контексті
і бути в змозі ефективно реагувати на потреби сталого
розвитку суспільства;
• бути в змозі оцінити можливості та обмеження теорій та
методів, застосовуваних на практиці;
• працювати в команді;
• ефективно працювати в рамках міждисциплінарних
команд, у тому числі вміння працювати з колегами для
того, щоб розробити і побудувати комплексну
комп’ютерну систему;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
32

33. Навички (компетенції) випускників

• розуміти фундаментальні засади ефективного управління проектами;
• визначити, формулювати і вирішувати технічні задачі;
• обговорювати концепції створення комп’ютерних системи та мереж,
особливостей використання Інтернет-технологій;
• визначати необхідність, проектувати, впроваджувати та оцінювати
життєздатність рішень для вбудованих комп’ютерних систем, що
працюють у реальному часі;
• виявляти, формулювати, аналізувати і створювати інженерні рішення
з використанням відповідних сучасних технологій, методів та
інструментів, в тому числі і з міжперсональним спілкуванням;
• доводи доцільність та правильність обраних теорій, методів, дизайну
та реалізацій;
• пояснювати та відстоювати методичний та системний підхід до
проектування;
• аргументувати вибрані рішення та пояснювати їхні обмеження;
• оцінювати сильні і слабкі сторони різних рішень і тестів;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
33

34. Навички (компетенції) випускників

• підтримувати проектування для забезпеченням заданої
функціональності
за
допомогою
розрахунків,
моделювання та імплементації результатів моделювання;
• комбінувати
варіанти
об'єднання
апаратного
і
програмного забезпечення для отримання бажаної
функціональності комп’ютерної системи;
• комбінувати загальнотехнічні та специфічні рішення при
роботі з комп’ютерними системами;
• представляти
результати
досліджень
у
вигляді
презентацій, публікації та / або доповідях на конференціях
та семінарах;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
34

35. Навички (компетенції) випускників

• демонструвати розуміння та дотримуватися професійних
та етичних обов'язків;
• мати уявлення, розуміти необхідність та дотримуватися
особистої чесності, професійної етики та культурної
свідомості;
• розуміти і нести професійну, етичну і моральну
відповідальність;
• ефективно спілкуватися та обмінюватися технічною
інформацією в різних форматах і різними способами
(усно, письмово, електронними засобами) як із
спеціалістами так і з неспеціалістами в галузі
Комп’ютерної інженерії;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
35

36. Навички (компетенції) випускників

визначити власні потреби в навчанні і планувати та здійснювати своє власне
навчання в різних середовищах навчання;
самостійно набувати ширшої освіти, необхідної для розуміння впливу
інженерних рішень в
–
–
–
–
глобальному,
економічному,
екологічному та
соціальному значеннях;
визнавати необхідність і здатність займатися самоосвітою протягом усього
життя;
розвиватися і підтримувати на належному сучасному рівні необхідні знання, а
також відповідний рівень компетентності в сучасних наукових технологіях
так, щоб бути в змозі формулювати і вирішувати нові технічні задачі і далі
розвивати і підтримувати свої професійні навички впродовж усієї кар'єри;
розуміти необхідність, прагнути до безперервного навчання, бути
винахідливим і здатним прийняти глобальні виклики та використати всі
можливості, щоб зробити позитивний вплив на суспільство;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
36

37. Навички (компетенції) випускників

• демонструвати знання сучасних проблем;
• розуміти і використовувати методи, навички та сучасні
інженерні інструменти необхідні для інженерної практики
з відповідними міркуваннями щодо забезпечення:
–
–
–
–
–
НУЛП 20162017 н.р.
громадського здоров'я та безпеки,
культурних,
соціальних,
моральних,
екологічних обмежень.
Глухов В.С. Комп'ютерна логіка
37

38. Спеціальні навички (компетенції) випускників

вбудовані комп'ютерні системи в споживчих товарах;
вбудовані комп'ютерні системи медичних пристроїв;
системи керування для автомобілів, літаків і поїздів;
широке коло додатків в областях:
– телекомунікацій,
– фінансових операцій,
– інформаційних систем
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
38

39. Спеціальні навички (компетенції) випускників

апаратно-програмні інтерфейси;
проектування НВІС;
проектування цифрових, аналогових та змішаних схем;
автоматизація проектування;
тестування та діагностика;
комп’ютерні мережі;
вбудовані комп’ютерні системи;
розробка програмного забезпечення для широкого кола
задач;
• кібер-фізичні системи;
• мови програмування: JAVA, C++, C, Assembly, VHDL,
Matlab, Python;
• операційні системи Android, iOS, UNIX, Linux, Windows.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
39

40. Застосування придбаних навичок в проектуванні.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
40

41. Вбудовані ЕОМ

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
41

42.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
42

43. Комірки

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
43

44. (Львівський центр Інституту космічних досліджень НАН та ДКА України) Супутник Січ-2 на етапі відлагодження та тестування

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
44

45. Блоки і комірки для Січ-2 (Львівський центр Інституту космічних досліджень НАН та ДКА України)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
45

46. Вбудована в атомну елекростанцію комп’ютерна система (НВО “Радій”, м. Кіровоград, 2010 р.)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
46

47.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
47

48.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
48

49.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
49

50.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
50

51. У Львові 150 IT-компаній (Інформаційні Технології) 25 найбільших IT-компаній України http://jobs.dou.ua/top25/

№
Компания
Δ Jul'15 /
Jan'16
Технические
специалисты
Вакансии
в Украине
1
EPAM Киев, Харьков, Львов, Днепропетровск, Винница
+500
3800
345
2
SoftServe Киев, Харьков, Львов, Днепропетровск, Ровно, ИваноФранковск, Черновцы
+44
3891
484
4
GlobalLogic Киев, Харьков, Львов, Николаев
+111
2360
174
5
Ciklum Киев, Харьков, Львов, Днепропетровск, Одесса, Винница
+44
2029
224
9
ELEKS Львов, Ивано-Франковск, Тернополь
-3
640
21
11
DataArt Киев, Харьков, Львов, Днепропетровск, Одесса, Херсон
+47
700
185
12
Lohika Systems Киев, Львов, Одесса
+8
588
20
14
ISD* Львов, Днепропетровск, Бердянск, Запорожье
-34
680
30
15
GeeksForLess Inc. Киев, Львов, Николаев
+2
550
15
17
Sigma Software Киев, Харьков, Львов, Одесса
+73
492
75
21
Plarium Киев, Харьков, Львов, Одесса
-40
145
48
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
51

52. Комп’ютерна логіка і „Комп’ютерна інженерія”

Архітектура
комп'ютерів
Комп’ютерні
системи
Комп'ютерна
схемотехніка
Теорія
алгоритмів
Програмування
Комп’ютерна
логіка
Математика
Фізика
Комп'ютерна
електроніка
НУЛП 20162017 н.р.
Філософія
Глухов В.С. Комп'ютерна логіка
52

53. Лінгвістичні основи – грецька абетка

Α α — альфа
Γ γ — гамма
Ε ε — епсилон
Η η — ета
Ι ι — йота
Λ λ — лямбда
Ν ν — ню
Ο ο — омікрон
Ρ ρ — ро
Τ τ — тау
Φ φ — фі
Ψ ψ — псі
НУЛП 20162017 н.р.
Β β — бета
Δ δ — дельта
Ζ ζ — дзета
Θ θ — тета
Κ κ — каппа
Μ μ — мю
Ξ ξ — ксі
Π π — пі
Σ σ ς — сигма
Υ υ — іпсилон
Χ χ — хі
Ω ω — омега
Глухов В.С. Комп'ютерна логіка
53

54. Лінгвістичні основи – латинська абетка

Літера
Aa
Bb
Cc
Dd
Ee
Ff
Gg
Hh
Ii
Jj
Kk
Ll
Mm
НУЛП 20162017 н.р.
Назва
а
бе
це
де
е
еф
ґе, же
га, аш
і
йот, жі
ка
ель
ем
Літера
Nn
Oo
Pp
Qq
Rr
Ss
Tt
те
Uu
Vv
Ww
Xx
Yy
Zz
Назва
ен
о
пе
ку
ер
ес
у
ве
дубль ве
ікс
іпсилон, ігрек
зет (зета)
Глухов В.С. Комп'ютерна логіка
54

55. Математичні основи Просте число — це натуральне число, яке має рівно два різних натуральних дільники (лише 1 і саме число).

• 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 , 127, 131,
137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479,
487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719,
727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881,
883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971,
977, 983, 991, 997…
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
55

56. Таблиця множення

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
56

57. Математичні основи

(m + n)·k = m·k + n·k - дистрибутивний закон
(a+b)+c=a+(b+c) – асоціативний закон
ab=ba – комутативний закон
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
57

58. Математичні основи

n! = 1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ (n − 1) ⋅ n
НУЛП 20162017 н.р.
0! = 1
Глухов В.С. Комп'ютерна логіка
58

59. Математичні основи – математичні константи

i
e 1 0
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
59

60. Математичні основи – модульна арифметика

Два цілих числа a і b називаються рівними (конгруентними)
за модулем n, якщо при цілочисельному діленні на n вони
мають однакові залишки. Рівність чисел a і b за модулем n
записують так:
Еквівалентні визначення:
Різниця a-b ділиться на n націло. Тобто a - b = kn, де k —
якесь ціле число.
Число a може бути записано у вигляді a = b + kn, де k —
якесь ціле число.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
60

61. Системи числення

8 2
3
16 2
4
16 2 4
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
61

62. Позиційні системи числення

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
62

63. Степені 2

10-ва
система
числення
2n
2-ва система
16-ва
числення
система
числення
1024
512
256
128
64
32
16
8
4
2
1
0,5
0,25
0,125
0,0625
0,03125
0,015625
0,007813
0,003906
0,001953
0,000977
10000000000
1000000000
100000000
10000000
1000000
100000
10000
1000
100
10
1
0,1
0,01
0,001
0,0001
0,00001
0,000001
0,0000001
0,00000001
0,000000001
0,0000000001
n
10
9
8
7
6
5
4
3
2
1
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
-10
НУЛП 20162017 н.р.
400
200
100
80
40
20
10
8
4
2
1
0,8
0,4
0,2
0,1
0,08
0,04
0,02
0,01
0,008
0,004
8-ва
система
числення
Степені 2
2000
1000
400
200
100
40
20
10
4
2
1
0,4
0,2
0,1
0,04
0,02
0,01
0,004
0,002
0,001
0,0004
Глухов В.С. Комп'ютерна логіка
63

64. Фізичні основи

Напруга U (В), струм I (А), потужність P (Вт),
опір R (Ом), ємність C (Ф), індуктивність L (Гн)
Закон Ома I = U/R
Потужність P = UI
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
64

65. Основи електроніки

Транзистори – біполярні та польові
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
65

66. Швидкість, продуктивність

• v=F/t (F – шлях, об’єм води, кількість
операцій, кількість інформації, …)
• v=(Fк-Fп)/(tк-tп)=ΔF/ Δt
• Δt →0 => dt
• v=dF/ dt – перша похідна
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
66

67. Філософські основи

• Матерія - філософська категорія для позначення
об'єктивної реальності, яка дана людині у відчуттях її, яка
копіюється, фотографується, відображується нашими
відчуттями, існуючи незалежно від них
• Катего́рія — загальне філософське поняття, яке
відображає універсальні властивості і відношення
об'єктивної дійсності, загальні закономірності розвитку
всіх матеріальних, природних і духовних явищ.
• Діале́ктика (грец. διαλεκτική — «мистецтво сперечатись»,
«міркувати») — метод філософії, що досліджує категорії
розвитку.
• Атрибут – невід’ємна характеристика
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
67

68. Матерія

Атрибути
Властивості
Види
Форми руху
Простір
об'єктивність
Речовина
Механічний
Час
вічність
Поле
Фізичний
Рух
нестворенність
Хімічний
Інформація
взаємодія
Біологічний
Матерія
відображення
інші
Основні закони діалектики
Закон єдності і боротьби протилежностей
Закон взаємного переходу кількісних змін у якісні
Закон заперечення заперечення
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
68

69. Відображення

• Відобра́ження — загальна властивість, що
виявляється в здатності матеріальних систем
відтворювати визначеність інших матеріальних
систем у формі зміни власної визначеності в
процесі взаємодії з ними.
• Приватними
і
специфічними
формами
відображення є інформація, відчуття і свідомість.
• Загальне поняття інформації подано у філософії,
де під нею розуміють відображення реального
світу.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
69

70. Інформація

• Інформація - Відомості про факти, концепції, об'єкти,
події та ідеї, які в даному контексті мають цілком певне
значення (ДСТУ ISO/IEC 2382-5:2005 Інформаційні
технології. Словник термінів. Частина 5. Подання даних)
• Інформація – це поняття, що пов'язано з об'єктивною
властивістю матеріальних об'єктів і явищ (процесів)
породжувати різноманіття станів, які за допомогою
взаємодії (фундаментальні взаємодії) передаються до
інших об'єктів та відображаються в їх структурі. (В.М.
Глушков, М.М. Амосов «Енциклопедія кібернетики»,
Київ. 1975 р.)
• Конце́пція (лат. conceptio — розуміння) — система
поглядів, те або інше розуміння явищ і процесів; єдиний,
визначальний задум.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
70

71. Стандарти AAAA NNNN-Ч:YYYY

Стандарт
Стандарти підприємства
Галузеві стандарти
Державні (національні) стандарти:
Державний стандарт України
Государственный стандарт (СРСР, до 1992 р.),
Міждержавний стандарт (СНД, з 1992 р.)
Государственный стандарт (Росія, з 1992 р.)
Американська організація стандртизації
Стандарти Німеччини
Міжнародні стандарти:
Міжнародна організація стандартизації
Міжнародна електротехнічна комісія
Міжнародний інститут інженерів електриків
НУЛП 20162017 н.р.
Позначення
(AAAA)
СТП
ГСТ
Приорітет
0 (найнижчий)
1
2
ДСТУ
ГОСТ
ГОСТ Р
ASA
DIN
3 (найвищий)
ISO
IEC
IEEE
Глухов В.С. Комп'ютерна логіка
71

72. Властивості інформації

Інформація
Властивості
Скінченість у просторі
Скінченість у часі
Цінність
Старіння
Розсіювання
інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
72

73. Комп’ютерна логіка у системі наук інформаційної сфери

Наука і техніка
Матерія
Речовина
Інформація
Поле
Отримання
Збереження
Перетворення
Пересилання
Комп’ютерна
логіка
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
73

74. Структурна схема процесу передачі або оброблення інформації

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
НУЛП 20162017 н.р.
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Глухов В.С. Комп'ютерна логіка
Модулятор
Канал /
обчислювач
Демодулятор
74

75. Кодек, Модем

• Кодек = кодер + декодер
• Модем = Модулятор + демодулятор
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
75

76. Баланс швидкостей

vi = vi1+vi2+…+vin
vo = vo1+vo2+…+von
Повинно бути: vi ≤ vo .
Інакше швидкість заповнення пам’яті буде
v = vi -vo > 0
Джерело
інформації
1
Джерело
інформації
2
...
Джерело
інформації
n
НУЛП 20162017 н.р.
ti1
F
ti2
tin
V
to1
Приймач
інформації
1
to2
Приймач
інформації
2
...
tom
Приймач
інформації
m
Глухов В.С. Комп'ютерна логіка
76

77. Функції кодера джерела інформації

Джерело
інформації
1.
2.
3.
НУЛП 20162017 н.р.
Інформація
Кодер
джерела
інформації
Дані
Код
Кодер
захисту
інформації
Перетворення неелектричних величин в електричні
Перетворення інформації в дані - аналого-цифрове
перетворення інформації
Усунення
надлишковості
інформації
Глухов В.С. Комп'ютерна логіка
77

78. Дані

• Дані - Інформація, представлена у вигляді, придатному для обробки
автоматичними засобами при можливій участі людини
• Дискретний - Визначення, що відноситься до даних, представлених
окремими елементами, наприклад, знаками або фізичними величинами,
які приймають кінцеве число цілком певних значень
• Числовий - Визначення, що відноситься до даних, які складаються з
чисел
• Цифровий - Визначення, що відноситься до даних, які складаються з
цифр
• Аналоговий - Визначення, що відноситься до даних, які представлені
безперервними значеннями будь-якої фізичної змінної
ДСТУ 3044-95 ПОДАННЯ ДАНИХ Терміни та визначення
ISO/IEC/IEEE 24765-2010 Systems and software engineering — Vocabulary
ISO/IEC 2382:2015 Information technology — Vocabulary
ДСТУ ISO/IEC 2382-5:2005 Інформаційні технології. Словник термінів.
Частина 5. Подання даних
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
78

79. Кодування

• Кодування даних Кодування
Процес побудови даних з елементів скінченої множини за
встановленими правилами
• кодовий набір
Скінчена множина елементів, з яких будують дані при
кодуванні
• алфавіт
Кодовий набір, в якому встановлено відношення порядку
• кодон
Елемент кодового набору
• Код даних Код
Система, утворена кодовим набором і правилами, за
якими з елементів цього кодового набору будують дані
при кодуванні
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
79

80. Сигнал та повідомлення

• Фізичне явище, наявність, відсутність або
зміна якого представляє Дані.
• Сигнал - матеріальний носій інформації, який
використовується для передачі повідомлень в
системі зв'язку.
• Сигнал може генеруватися, але його прийом не
обов'язковий, на відміну від повідомлення, яке
розраховане
на
прийняття
приймаючою
стороною, інакше воно не є повідомленням.
• Сигналом може бути будь-який фізичний процес,
параметри якого змінюються відповідно до
переданого повідомлення.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
80

81. АЦП та ЦАП (ADC and DAC)

АЦП – аналого-цифровий перетворювач
ЦАП – цифро-аналоговий перетворювач
ЦАП
Всесвіт
Аналоговий
Цифровий
Комп’ютер
АЦП
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
81

82. Порівняння аналогових та цифрових методів обробки інформації

Характеристика
Швидкодія
Універсальність
Мікромініатюризація
Точність
Масштабування
Передача у просторі
Передача у часі
Завадостійкість
Надійність
НУЛП 20162017 н.р.
Аналогові
способи
+
Цифрові
способи
-
-
+
+
-
+
+
+
+
+
+
Глухов В.С. Комп'ютерна логіка
82

83. Найпоширеніший аналоговий обчислювач (комп’ютер, помножувач)

Кут повороту = U*I*t*k
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
83

84. Дискретизація та квантування

квантування
y
0
НУЛП 20162017 н.р.
Під квантуванням (англ. quantization) неперервної або дискретної
величини розуміють розбивку діапазону її значень на кінцеве
число інтервалів. Квантування часто використовується при
обробці цифрових сигналів, у тому числі при стисканні звуку й
зображень. Квантування приводить сигнал до заданих значень,
тобто, розбиває за рівнем сигналу (на графіку — по горизонталі).
Не слід плутати квантування з дискретизацією (і, відповідно,
рівень квантування з частотою дискретизації). При дискретизації
величина, що змінюється в часі (сигнал) заміряється із заданою
частотою (частотою дискретизації), таким чином, дискретизація
розбиває сигнал за часовою складовою (на графіку — по
вертикалі).
Сигнал, до якого застосована дискретизація й квантування,
називається цифровим.
дискретизація
x
Глухов В.С. Комп'ютерна логіка
84

85. Дискретиза́ція

• Дискретиза́ція — перетворення функцій
неперервних змінних у функції дискретних
змінних, за якими початкові неперервні
функції можуть бути відновлені із заданою
точністю.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
85

86. Квантування

• Під квантуванням розуміють перетворення
неперервної за значеннями величини у величину з
дискретною шкалою значень з скінченної
множини дозволених, які називають рівнями
квантування.
• Квант (крок квантування) - відстань між
сусідніми рівнями квантування
• Імпульс (електричний) – короткочасне
збільшення або зменшення напруги або струму
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
86

87. Дискретизація та квантування

Неперервний у часі.
Дискретний за рівнем
НУЛП 20162017 н.р.
Дискретний у часі.
Неперервний за рівнем
Дискретний у часі.
Дискретний за рівнем
Глухов В.С. Комп'ютерна логіка
87

88. Дискретизація (у часі)

s(t)
T
Аналоговий сигнал:
Неперервний у часі.
Неперервний за рівнем
t
s
T
s 2n-1
s3
s2
s 2n
Δt
s1
s0
t
t0
t1
t2
t3
НУЛП 20162017 н.р.
Дискретний у часі.
Неперервний за рівнем
t 2n-1 t 2n
Глухов В.С. Комп'ютерна логіка
88

89. Квантування за рівнем

s(t)
T
Аналоговий сигнал:
t
s(t)
sk
Неперервний у часі.
Неперервний за рівнем
sk-1
Δs
s4
s3
Неперервний у часі.
Дискретний за рівнем
s2
s1
t
s0
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
89

90. Дискретизація за часом і квантування за рівнем

s(t)
T
Аналоговий сигнал:
t
s
Неперервний у часі.
Неперервний за рівнем
T
s8
s7
s6
Δs
s5
s4
Дискретний у часі.
Дискретний за рівнем
s3
s2
Δt
s1
t
s0
t0
t1
t2
НУЛП 20162017 н.р.
t3
t 2n-1 t 2n
Глухов В.С. Комп'ютерна логіка
90

91. Теорема Котельнікова – як часто треба вимірювати сигнал?

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
91

92. Переваги кодування двома символами

• Просто
• Надійно
+U
формування
аналіз
S1
VD1
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
92

93. Додатня і від’ємна логіка

• (0 – менша напруга, 1 – більша напруга) –
додатня логіка, використовується
приблизно в 50%
• (1 – менша напруга, 0 – більша напруга) –
від’ємна логіка, використовується
приблизно в 50%
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
93

94. Варіанти представлення двійкових значень на фізичному рівні

Інтервали часу
t0
0
t1
1
t2
0
t3
0
t4
1
t5
1
t6
0
t7
1
• Амплітудний (рівнем)
• Частотний
t0
0
t1
1
Моменти часу
t2
t3
t4
t5
0
0
1
1
t6
0
t7
1
• Фазовий
• Імпульсний
• Інтервальний
• Інші
НУЛП 20162017 н.р.
t0
0
t1
1
Інтервали часу
t2 t3 t4
t5 t6
0 0 1
1 0
Глухов В.С. Комп'ютерна логіка
t7
1
94

95. Параметри імпульсу

Фронт, перепад з високого рівня на
низький, у цьому прикладі це "задній
" фронт, оскільки у часі він перший
Параметр
A - амплітуда
T - період
t - тривалість
F = 1/T - частота
t
A
T
Час
Фронт, перепад з низького рівня на
високий, у цьому прикладі це
"передній" фронт, оскільки у часі
він перший
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
95

96. Характеристики імпульса

• Амплітуда - найбільше значення, яке приймає будь-яка
величина, що змінюється за гармонійним законом
• Перíод колива́нь — проміжок часу між двома
послідовними максимальними відхиленнями фізичної
системи від положення рівноваги. Період коливань
позначається зазвичай великою літерою T (c, 1 мс=10-3с, 1
мкс=10-6с, 1 нс=10-9с, 1 пс=10-12с)
• Частота коливань обернено пропорційна періоду F = 1/T
(Гц, 1 кГц =103 Гц, 1 МГц =103 Гц, 1 ГГц =103 Гц)
• Фаза — кількісна характеристика коливання, що визначає
відмінність між двома подібними коливаннями, які
починаються в різні моменти часу.
• Спектр - розподіл значень фізичної величини
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
96

97. Дані

• Числа
– ФК
• Без знаку
• Із знаком (ПК, ОК, ДК, МДК)
– РК
• IEEE 754 (S, D, E, Q)
• Текст
– Укр (КОІ-8У), Рос (КОІ-7, КОІ-8Р), англ (ASCII)
– Windows 1251, UTF
• Відео
• Аудіо
• Інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
97

98. Числа з фіксованою комою

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
98

99. Порядок байтів

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
99

100. Числа з рухомою комою. Стандарт IEEE-754

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
100

101. Кодова таблиця КОИ-7

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
101

102. Кодова таблиця KOI-8U

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
102

103. Кодові таблиці:

Windows1251
KOI8-U
KOI8-R
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
103

104. Структура кодів UTF-8 (Unicode Transformation Formats )

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
104

105. Кодування зображень. Матричні та векторні формати

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
105

106. Кодування відтінків кольору

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
106

107. Кількість кольорів

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
107

108. Формати аудіфайлів

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
108

109. Міри інформації

Структурні
Семантичні
Статистичні
Інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
109

110. Структурні міри інформації

• 1.1 Фізичні – вага, швидкість, тиск, інші
фізичні величини
• 1.2 Геометричні – розміри, габарити
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
110

111. 1.3 Структурні комбінаторні міри

• 1.3.1 Сполучення по l елементів з h (різняться складом)
• Нехай є множина М, яка складається з l різних елементів. Будь-яка
підмножина множини М, яка містить h елементів (h=0, 1, 2, ..., l),
називається сполученням (combination) або комбінацією з даних l
елементів по h елементів, якщо ці підмножини відрізняються хоча б
одним елементом. Число різних сполучень із l елементів по l
позначається (combination від combinare лат. сполучати).
h!
C
l! ( h l )!
5!
1 2 3 4 5
3
C5
10
3! ( 5 3 )! 1 2 3 1 2
l
h
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
111

112. Структурні комбінаторні міри

• 1.3.1a Сполучення з повторенням
(h l - 1)!
~l
l
Ch Ch l 1
l! ( h 1 )!
7!
1 2 3 4 5 6 7
~ 3 ( 5 3 1 )!
C5
35
3! ( 5 1 )! 3! 4! 1 2 3 1 2 3 4
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
112

113. Структурні комбінаторні міри

• 1.3.2 Перестановлення h елементів (різняться порядком)
Q h!
Q 5! 1 2 3 4 5 120
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
113

114. Структурні комбінаторні міри

• 1.3.3 Розміщення по l елементів з h (різняться складом та порядком)
h!
A
( h l )!
l
h
5!
1 2 3 4 5
A
60
( 5 3 )!
1 2
3
5
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
114

115. Структурні комбінаторні міри

1.3.3a Розміщення по l елементів з h з повторенням (різняться складом та
порядком)
~l
l
Ah h
~3
3
A5 5 125
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
115

116. 1.4 Міра Хартлі, США, 1928 р. (Ральф Хартлі)

h – кількість різних елементів, система числення
l - довжина, розрядність
Q – можлива кількість повідомлень
Q h
l
1.4a Адитивна двійкова логарифмічна
міра Хартлі
I log 2 Q log 2 h l log 2 h
l
I( M N ) I( M ) I( N )
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
116

117.

Одиниця кількості інформації
I 1 log 2 Q log 2 h l log 2 h 1 log 2 2
l
• Один двійковий розряд – Binary Digit – bit (b, б)
• Байт (B, Б) – найчастіше це 8 біт.
I log 2 Q log 2 hl l log 2 h
M 613; I M log 2 613 9 ,26 10
M 61310 10011001012 10 біт
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
117

118. Похідні одиниці кількості інформації

• 1 К = 1024
1 М = 1024 К;
1 Г = 1024 М;
1 Т = 1024 Г;
1 П = 1024 Т.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
118

119. 2. Семантична міра (за значенням)

• властивості інформації:
–
–
–
–
–
–
–
–
–
–
–
НУЛП 20162017 н.р.
повнота,
достовірність,
цінність,
адекватність,
актуальність,
чіткість,
доступність,
невичерпність,
кумулятивність,
зрозумілість,
суб'єктивність.
Глухов В.С. Комп'ютерна логіка
119

120. Семантична міра

• Повнота
інформації
характеризує
якість
інформації і визначає достатність даних для
прийняття рішень.
• Достовірність інформації - її властивість
відображати реальні об'єкти з необхідною
точністю.
• Цінність інформації не може бути абстрактною.
Інформація має бути корисною і цінною для
певної
категорії
користувачів.
Цінність
інформації залежить від того, які задачі можна
вирішувати за її допомогою.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
120

121. Семантична міра

• Адекватність інформації характеризує ступінь
відповідності інформації реаліям. Адекватна
інформація - це повна і достовірна інформація.
• Актуальність інформації - ступінь зберігання
цінності інформації для керування в момент її
використання, що залежить від динаміки зміни її
характеристик і від інтервалу часу, що пройшов із
моменту виникнення певної інформації.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
121

122. Семантична міра

• Своєчасність інформації - її надходження
не пізніше заздалегідь визначеного часу,
узгодженого з часом вирішення
поставленого перед користувачем завдання.
• Чіткість інформації - інформація має бути
зрозуміла для того, кому вона призначена.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
122

123. Семантична міра

• Доступність інформації - це можливість
отримання і перетворення інформації.
• Точність інформації - ступінь подібності
отриманої інформації до реального стану
об'єкта, процесу, явища тощо.
• Суб'єктивність інформації. Інформація має
суб'єктивний характер, оскільки її цінність
визначається ступенем сприйняття суб'єкта
(одержувача інформації).
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
123

124. Семантична міра

• Корисна інформація - властивість, що
зменшує невизначеність прийняття
рішення.
• Репрезентативність інформації правильність її відбору і формування для
адекватного відображення властивостей
об'єкта.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
124

125. Семантична міра

• Змістовність інформації - це відношення
кількості семантичної інформації в
повідомленні до обсягу даних, які
обробляються.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
125

126. 3. Статистична міра, Клод Шеннон, 1948, США

1
I log 2 h log 2 Q log 2 log 2 p
Q
l
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
126

127. Ентропія джерела повідомлення – характеризує здатність джерела віддавати інформацію

N –дослідів, k – різних,
i-тий результат повторюється ni разів та дає Ii
інформації
I сер
n1 I 1 n2 I 2 ... nk I k
; I i log 2 pi ;
N
ni
pi
N
k
I сер p1 log 2 p1 p 2 log 2 p 2 ... p k log 2 p k pi log 2 pi ;
k
i 1
H pi log 2 pi ;
i 1
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
127

128. Властивості ентропії

• Невід’ємна
• = 0, коли ймовірність однієї події = 1
• Максимальна, коли ймовірності всіх подій
однакові
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
128

129. Залежність ентропії двох подій від їх імовірності

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
129

130. Кількість отриманої інформації

• I = Hпочаткове – Hкінцеве
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
130

131. Усунення надлишковості інформації. Алгоритм ефективного кодування Шеннона – Фано

повідомлення, які складаються з літер
певного алфавіту, можна закодувати так, що
середнє число двійкових символів на літеру
буде як завгодно близьке до ентропії
джерела цих повідомлень, але не менше
цієї величини
7
H - pi log 2 pi 1/2 1 1/4 2 1/8 3 1/16 4 ... 1/128 7 127/64.
i 0
7
Lсер.еф. pi ni 1/2 1 1/4 2 1/128 7 127/64. Lсер.еф. H.
i 0
7
Lсер.нееф. pi ni 1/2·3 1/4·3 ... 1/128·3 3 H
i 0
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
131

132. Абетка Морзе

А.Б -…
В .--
Л .-..
М -Н -.
Ц -.-.
Ч ---.
Ш ----
Г--.
Д -..
Е.
О --П .--.
Р .-.
Щ --.Ъ .--.-.
Ы -.--
Ж …З --..
И ..
С…
ТУ ..-
Ь -..Э ..-..
Ю ..--
Й .--К -.-
Ф ..-.
Х ….
Я .-.-
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
132

133. Послідовний та паралельний спосіб передачі інформації

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
133

134. SerDes

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
134

135. Строб (вказівник, спрацьовувати)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
135

136. Способи оброблення даних

X
ЦА1
Y1
ЦА3
ЦА2
Y=f(Y1,Y2)
Y2
а
X
ЦА1
Y1
ЦА2
Y=f(Y1)
б
X
ЦА1
X1=f(X,Y2)
ЦА2
Y=f(X1)
Y2=f(Y)
ЦА3
в
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
136

137. Послідовний та паралельний способи опрацювання даних

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
137

138. Опрацювання даних з використанням зворотних зв’язків

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
138

139. Опрацювання даних в ієрархічних структурах

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
139

140. Кодер захисту інформації

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Модулятор
Канал /
обчислювач
Демодулятор
Кодер захисту інформації необхідний для інформаційної безпеки
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
140

141. Загальна схема криптографічної системи

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
141

142. Перемішування

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
142

143.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
143

144. Контроль на парність / непарність

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
144

145. Код Хеммінга

i
i
F
k
F
Лінія зв’язку
==
Код
помилкового
k біта
F – вузол формування кода Геммінга
K1 = i3 i5 i7 i9 i11 i13 i15
K2 = i3 i6 i7 i10 i11 i14 i15
K4 = i5 i6 i7 i12 i13 i14 i15
K8 = i9 i10 i11 i12 i13 i14 i15
K k = (K8 k8)(K4 k4)(K2 k2)(K1 k1)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
145

146. Код Хеммінга

Таблиця 1.6.2
n1
n2
n3
n4
n5
n6
n7
n8
n9
n10
n11
n12
n13
n14
n15
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
k1
k2
i3
k4
i5
i6
i7
k8
i9
i10
i11
i12
i13
i14
i15
k1 = i3 i5 i7 i9 i11 i13 i15;
k2 = i3 i6 i7 i10 i11 i14 i15;
k4 = i5 i6 i7 i12 i13 i14 i15;
k8 = i9 i10 i11 i12 i13 i14 i15;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
146

147. Контроль виконання операцій. Числовий контроль за модулем

i-розрядні
операнди
:m
k-розрядні
модулі
операндів
НУЛП 20162017 н.р.
i-розрядний
арифметичний
пристрій
k-розрядний
арифметичний
пристрій
i-розрядний
результат
:m
k-розрядний
модуль
результату
k << i
Ознака
помилки
==
k-розрядний результат арифметичної
операції над модулями операндів
:m - вузол формування модуля
Глухов В.С. Комп'ютерна логіка
147

148. Кодер каналу / обчислювача

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
НУЛП 20162017 н.р.
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Глухов В.С. Комп'ютерна логіка
Модулятор
Канал /
обчислювач
Демодулятор
148

149. Позиційні системи числення

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
149

150. Двійково-десяткові коди

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
150

151. Двійково-десяткові коди

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
151

152. Трійкова симетрична (врівноважена) система числення

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
152

153. Системи числення з іраціональними основами Класичний CORDIC-метод обчислення тригонометричних ф-цій Coordinate Rotation Digital

Computer
метод Дж. Волдера
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
153

154. Система залишкових класів

Таблиця 1.5.1
Система залишкових класів
— индикт менялся от 1 до 15 и снова сбрасывался на 1;
— круг Солнцу менялся от 1 до 28 и снова сбрасывался на 1;
— круг Луне менялся от 1 до 19 и снова сбрасывался на 1.
7980 = 15 х 28 х 19
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
Чис- Залишки від Код
ло
ділення на
у
2 3 5 СЗК
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
0,0,0
1,1,1
0,2,2
1,0,3
0,1,4
1,2,0
0,0,1
1,1,2
0,2,3
1,0,4
0,1,0
1,2,1
0,0,2
1,1,3
0,2,4
1,0,0
0,1,1
1,2,2
0,0,3
1,1,4
0,2,0
1,0,1
0,1,2
1,2,3
0,0,4
1,1,0
0,2,1
1,0,2
0,1,3
1,2,4
0,0,0
154

155. Поля Галуа

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
155

156. Сусідній код (код Грея)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
156

157. Сусідні коди

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
157

158. Карти Карно

d
b
d
0
1
3
2
10
11
13
12
4
5
7
6
14
15
17
16
8
C
D
F
E
8
1C
1D
1F
1E
8
9
B
A
18
19
1B
1A
*
e
НУЛП 20162017 н.р.
c
b
c
a
e
Глухов В.С. Комп'ютерна логіка
158

159. Скручування карти Карно по вертикалі і горизонталі

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
159

160. Структурна схема процесу передачі або оброблення інформації

Джерело
інформації
Кодер
джерела
інформації
Кодер
захисту
інформації
Кодер
каналу /
обчислювача
Джерело
завад
Приймач
інформації
НУЛП 20162017 н.р.
Декодер
приймача
інформації
Декодер
захисту
інформації
Декодер
каналу /
обчислювача
Глухов В.С. Комп'ютерна логіка
Модулятор
Канал /
обчислювач
Демодулятор
160

161. Семисегментний індикатор

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
161

162.

а
б
a
f
g
e
b
c
d
Выход
8
4
2
1
a
b
c
d
e
f
g
Символ
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
0
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
1
2
0
0
1
1
1
1
1
1
0
0
1
3
0
1
0
0
0
1
1
0
0
1
1
4
0
1
0
1
1
0
1
1
0
1
1
5
0
1
1
0
1
0
1
1
1
1
1
6
0
1
1
1
1
1
1
0
0
0
0
7
1
0
0
0
1
1
1
1
8
0
0
1
1
1
1
1
1
1
1
1
0
1
1
9
DI
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
162

163. Алгоритм

• Система формальних правил або приписів,
які
визначають
процес
досягнення
конкретної мети – перетворення деяких
даних у бажаний результат, а також набір
умов, які визначають порядок застосування
цих правил до даних, що обробляються
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
163

164. Характеристики алгоритму

• 3 множини:
– Множина вхідних даних
– Множина можливих результатів
– Множина проміжних результатів
• 4 правила:
–
–
–
–
НУЛП 20162017 н.р.
Правило початку роботи
Правило безпосереднього перетворення даних
Правило закінчення роботи
Правило вилучення результату
Глухов В.С. Комп'ютерна логіка
164

165. Властивості алгоритму

Скінченність, результативність
– алгоритм має завжди завершуватись після виконання скінченної кількості кроків. Процедуру,
яка має решту характеристик алгоритму, без, можливо, скінченності, називають методом
обчислень.
Дискретність
– процес, що визначається алгоритмом, можна розчленувати (розділити) на окремі елементарні
етапи (кроки), кожен з яких називається кроком алгоритмічного процесу чи алгоритму.[31]
Визначеність, однозначність
– кожен крок алгоритму має бути точно визначений. Дії, які необхідно здійснити, повинні бути
чітко та недвозначно визначені для кожного можливого випадку.
Масовість, універсальність, повторюваність
– властивість алгоритму, яка полягає в тому, що алгоритм повинен забезпечувати розв'язання
будь-якої задачі з класу однотипних задач за будь-якими вхідними даними, що належать до
області застосування алгоритму.
Ефективність
– Алгоритм вважають ефективним, якщо всі його оператори досить прості для того, аби їх
можна було точно виконати за скінченний проміжок часу з допомогою олівця та аркушу
паперу.
Вхідні дані
– алгоритм має деяку кількість (можливо, нульову) вхідних даних, тобто, величин, заданих до
початку його роботи або значення яких визначають під час роботи алгоритму.
Вихідні дані
– алгоритм має одне або декілька вихідних даних, тобто, величин, що мають досить визначений
зв'язок із вхідними даними.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
165

166. Представлення алгоритмів http://uk.wikipedia.org/wiki/Алгоритм

• У процесі розробки алгоритму можуть використовуватись
різні способи його опису, які відрізняються за простотою,
наочністю, компактністю, мірою формалізації, орієнтації
на машинну реалізацію тощо.
–
–
–
–
–
словесна або вербальна (неформальні мови, формульно-словесна);
псевдокод (формальні алгоритмічні мови);
Таблична;
Часові діаграми;
схемна:
• Функціональні схеми;
• блок-схема, виконується за вимогами стандарту
• граф автомата
– інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
166

167. Блок-схема алгоритму

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
167

168. Граф автомата Мура та позначки у вершинах графа з двійковим кодуванням станів

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
168

169. Граф автомата

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
169

170. Блок-схема алгоритму та граф автомата

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
170

171. Таблиці переходів та виходів автомата Мура

№
0
1
2
3
4
5
6
7
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
a0
0
0
a0
0
0
0
1
a1
0
1
a1
1
0
a2
1
0
a2
a3
1
1
1
1
a3
x
0
1
0
1
0
1
0
1
Наступний стан
автомата
Позначення
Код
aj
q1
q0
a1
0
1
a0
0
0
1
0
a2
1
0
a2
1
1
a3
1
1
a3
a0
0
0
0
0
a0
Сигнали
збудження
тригерів
D1
D0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
0
№
0
1
2
3
НУЛП 20162017 н.р.
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
0
0
a0
0
1
a1
1
0
a2
1
1
a3
Глухов В.С. Комп'ютерна логіка
Вихідні
сигнали
автомата
y
1
1
0
0
171

172. Функціональна схема автомата Мура

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
172

173. Часова діаграма роботи автомата Мура

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
173

174. Опис автомата формальною (з правилами без винятків) або неформальною (з правилами та винятками з них) мовами

Опис автомата формальною (з правилами без винятків) або
неформальною (з правилами та винятками з них) мовами
State_machine: process (c)
begin
if rising_edge(c) then
case State is
when a0 =>
if x='1' then
State <= a0;
elsif x='0' then
State <= a1;
end if;
when a1 =>
State <= a2;
when a2 =>
State <= a3;
when a3 =>
State <= a0;
when others =>
null;
end case;
end if;
end process;
y_assignment:
y <= '1' when (State = a0) else
'1' when (State = a1) else
'0';
end fsm1_arch;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
174

175. Теза Черча 

Теза Черча
• Теза Черча — для кожного алгоритму
може
бути
побудована
формальна
алгоритмічна система (ФАС), яка його
реалізує
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
175

176. Універсальні ФАС – можуть реалізувати будь-який алгоритм

Рекурсивні функції
Машина Тюринга
Машина Поста
Схеми Колмогорова-Успенського
Нормальні алгорифми Маркова
Скінченні цифрові автомати (комп’ютери та їх програми)
зараз ФАС –
– програма для універсального комп’ютера або
– новий (спеціалізований) комп’ютер і програма для нього
http://uk.wikipedia.org/wiki/Алгоритм
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
176

177. Повна побудова алгоритму

• формулювання задачі;
• побудови моделі абстрактного алгоритм;
– АБСТРАКТНИЙ - той, що є наслідком мисленого виділення з усіх
ознак, властивостей і зв'язків конкретного предмета його основних,
найзагальніших;
розроблення абстрактного алгоритму;
перевіряння правильності абстрактного алгоритму;
реалізації структурного алгоритму;
аналізу алгоритму і його складності;
перевіряння реалізації структурного алгоритму;
оформлення документації.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
177

178. Загальна структурна схема цифрового автомата

КСх
ПА
δ
{X}
λ
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
НУЛП 20162017 н.р.
{A}
{Y}
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Глухов В.С. Комп'ютерна логіка
178

179. Структурна схема автомата Мура

i
КСх
ПА
δ
{X} j
{A}
КСх
λ
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
j – кількість вхідних сигналів
k – кількість вихідних сигналів
НУЛП 20162017 н.р.
i
k
{Y}
2
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
i – розрядність зворотного зв’язку,
кількість тригерів у пам’яті
автомата
Глухов В.С. Комп'ютерна логіка
179

180. Структурна схема автомата Мілі

КСх
{X}
δ
ПА
{A}
КСх
λ
1
{Y}
2
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
НУЛП 20162017 н.р.
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Глухов В.С. Комп'ютерна логіка
180

181. Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра)

• Використовується для опису комбінаційних схем
• Розділ математичної логіки, що вивчає систему
логічних операцій над висловлюваннями.
Найчастіше передбачається, що висловлювання
можуть бути тільки істинними або помилковими,
тобто використовується так звана бінарна або
двійкова логіка, на відміну від, наприклад,
тризначної логіки.
• Вивчає функції, які можуть приймати тільки два
значення: 0 (істина) та 1 (хибність), так само, як і
їх аргументи
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
181

182. Змінні, набори і функції алгебри логіки – для опису комбінаційних схем цифрових автоматів

кількість
змінних
0
кількість
наборів
1
кількість
ФАЛ
2
1
2
3
2
4
8
4
16
256
4
…
n
16
…
65536
…
n
2
2
2n
n
n 1
2
An 2 C n
НУЛП 20162017 н.р.
n 2
An 1 C n
h!
C h l!(h l )!
l
1
...
Cn
An 2
Глухов В.С. Комп'ютерна логіка
A A
1
0
182

183. ФАЛ0, ФАЛ1

f0
f1
a
f0(a)
f1(a)
f2(a)
f3(a)
0
1
0
0
0
1
1
1
0
1
0
1
Фактично є
ФАЛ0
ФАЛ0
A0 2 2
20
A1 2 A0 2
21
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
183

184. Повторювач, інвертор

a
1
a
a
a
a
а
a
1
а
a
(a=1)
б
a
a
( a 0)
a
б
Інверсія, інвертор, НЕ
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
184

185. Функції алгебри логіки двох змінних

A2 2 C21 A1 A0 16 2 2 2 10
22
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
185

186. Кон'юнкція (від латинського conjunctio – сполучник, зв'язок), логічне множення або функція І (И, AND)

a b
a
a
&
b
а
ab
b
Зафарбована область - a & b
a
b
ab
б
Кон'юнкція, кон’юнктор, І
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
186

187. Диз'юнкція (від латинського disjunctio - роз'єднання), логічне додавання або функція АБО (ИЛИ, OR)

ab
a
a
1
b
а
a b
a
b
a b
b
Зафарбована область - a v b
б
Диз'юнкція, диз’юнктор,
АБО
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
187

188. Функція (штрих) Шеффера або функція І-НЕ (NOT AND, NAND, И-НЕ)

ab
a
b
Зафарбована область - ab
a
&
b
а
НУЛП 20162017 н.р.
ab
a
b
ab
б
Глухов В.С. Комп'ютерна логіка
188

189. Функція (стрілка) Пірса (Вебба) або функція АБО-НЕ (ИЛИ-НЕ, NOT OR, NOR)

a b
a
a
1
b
а
НУЛП 20162017 н.р.
a b
a
a b
b
b
Зафарбована область - a b
б
Глухов В.С. Комп'ютерна логіка
189

190. Виключне АБО (XOR)

a
a
=1 a b
b
а
НУЛП 20162017 н.р.
a
b
a b
b
Зафарбована область - a b
б
Глухов В.С. Комп'ютерна логіка
190

191. Рівнозначність (еквівалентність)

a
a
b
b
= = a b
Зафарбована область - a b
а
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
191

192. Імплікація (пряма)

x
a
b
а
НУЛП 20162017 н.р.
a
b
б
x
a
b
x b
a
в
г
Глухов В.С. Комп'ютерна логіка
192

193. Імплікація зворотна

x
b
a
а
НУЛП 20162017 н.р.
b
a
б
x
b
a
x a
b
в
г
Глухов В.С. Комп'ютерна логіка
193

194. Заперечення імплікації (прямої)

Заперечення зворотної імплікації
b
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
194

195. Теорема Поста-Яблонського про функціонально повні системи (ФПС, базиси)

• З ФАЛ, які мають якусь властивість, можна
утворити тільки ФАЛ, які мають цю ж властивість
• З ФАЛ, які мають якусь властивість не можна
утворити ФАЛ, які не мають цієї властивості
• До ФПС повинна входити хоча би одна ФАЛ, яка:
–
–
–
–
–
НУЛП 20162017 н.р.
1) не зберігає 0;
2) не зберігає 1;
3) несамодвоїсна;
4) немонотонна;
5) нелінійна
Глухов В.С. Комп'ютерна логіка
195

196. Властивості ФАЛ, монобазиси, базиси

0 1 Л М С
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
* *
f1
0 0 0 1 кон'юнкція, І
*
f7
0 1 1 1 диз'юнкція, АБО х0 v х1
1 1 0 0 інверсія х0
x0
НУЛП 20162017 н.р.
x
0
x
1
1
1
1
1
x
0
1
x
x
x
x
x
x
x
1
x
0
x
1
1
1
x
x
x
1
1
1
1
x
1
0
0
0
0
0
0
x
x
x
x
x
x
x
1
1
x
x
0
0
x
x
1
1
x
x
1
1
1
x
x
x
1
0
0
x
1
0
*
*
x0
*
1
x
1
0
0
x
x
x
1
x
*
1
* *
x
0
x
1
1
0 1 Л М С
*
1
x
x
x
1
1
1
0
0
x
x
x
x
x
Властивості
0
x
1
1
1
x
x
x
0
0
0
x
x
x
Вираз
ФАЛ
0 1 1 1 диз'юнкція, АБО х0 v х1
1 1 0 0 інверсія х0
x0
Глухов В.С. Комп'ютерна логіка
Властивості
Базис АБО, НЕ
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
f12
0
0
x
x
x
x
x
* *
x
х0 ·х1
x
0 0 0 1 кон'юнкція, І
*
f7
* * *
* * *
x
f1
x
1
*
0 1 Л М С
0
x0 x1
*
Вираз
ФАЛ
0
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
f12 1 1 0 0 інверсія х0
*
Властивості
1
*
*
*
x
x0 x1 x0 x1 *
x
0 1 1 0 сума за mod 2
0
* *
0
х0 ·х1
x
0 0 0 1 кон'юнкція, І
x
0 1 Л М С
x
x0 x1
x0
f12 1 1 0 0 інверсія х0
f13 1 1 0 1 імплікація пряма x0 x1
f14 1 1 1 0 І-НЕ (Шефера)
f15 1 1 1 1 константа "1"
Вираз
ФАЛ
0
f11
x1
*
Базис І, НЕ
* *
*
1
f10
1 0 1 0 інверсія х1
1 0 1 1 імплікація звор.
x0 x1 x0 x1
*
1
1 0 0 1 рівнозначність
Властивості
Базис Жегалкіна
f15 1 1 1 1 константа "1"
*
x
f9
* *
x
f8
0 1 1 1 диз'юнкція, АБО х0 v х1
1 0 0 0 АБО-НЕ (Пірса) x0 x1
x
f7
x
f6
*
x
x0 x1 x0 x1 *
x
0 1 1 0 сума за mod 2
0
f6
0
f1
* * * * *
0
х1
f4
1
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
x
*
x
x0 x1
f5
0 1 0 0 заборона по х0
0 1 0 1 х1
x
* * * * *
1
х0
f3
f12
*
x0 x1
*
x
f2
0 0 1 0 заборона по х1
0 0 1 1 х0
* *
1
* *
0
х0 ·х1
*
0
0 0 0 1 кон'юнкція, І
* *
0
f1
х0 ·х1
*
x
0
0
0 0 0 0 константа "0"
0 1 Л М С
0
f0
Вираз
ФАЛ
x
Властивості
Базис Буля
Вираз
ФАЛ
0
х0 0 0 1 1 Назва ФАЛ
х1 0 1 0 1
196
*

197. Деякі ФАЛ3

A3 2 C32 A2 C31 A1 A0 256 3 10 3 2 2 218
23
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
197

198. Сингулярні таблиці

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
198

199. Базис Буля

a
b
a
&
a b ... z
...
z
елемент І (AND),
кон'юнктор
НУЛП 20162017 н.р.
b
1
a b ... z
...
z
елемент АБО (OR),
диз'юнктор
a
1
a
елемент НЕ (NOT),
інвертор
Глухов В.С. Комп'ютерна логіка
199

200. Кон'юнкція (від латинського conjunctio – сполучник, зв'язок), логічне множення або функція І (И, AND)

a b
a
a
&
b
а
ab
b
Зафарбована область - a & b
a
b
ab
б
Кон'юнкція, кон’юнктор, І
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
200

201. Диз'юнкція (від латинського disjunctio - роз'єднання), логічне додавання або функція АБО (ИЛИ, OR)

ab
a
a
1
b
а
a b
a
b
a b
b
Зафарбована область - a v b
б
Диз'юнкція, диз’юнктор,
АБО
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
201

202. Повторювач, інвертор

a
1
a
a
a
a
а
a
1
а
a
(a=1)
б
a
a
( a 0)
a
б
Інверсія, інвертор, НЕ
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
202

203. Аналітичне представлення функцій алгебри логіки Досконалі нормальні форми

ДДНФ:
f(a, b, c) = F0(0, 0, 0) F3(0, 1, 1) F4(1, 0, 0) = a b c a b c a b c.
ДКНФ:
f(a, b, c) = Ф1(0,0,1)& Ф2(0, 1, 0) & Ф5(1, 0, 1) & Ф6(1, 1, 0) & Ф7(1, 1, 1) =
= (a b c)&(a b c)&( a b c)&( a b c) &( a b c).
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
203

204. Терм

• Терм - це група літерал і констант, об'єднаних тим самим знаком
логічного зв'язування: логічного додавання або ж логічного
множення. У термі кожен літерал і кожна константа зустрічається
тільки один раз, тобто в терм може входити або змінна, або її
заперечення.
• Диз'юнктивний терм (макстерм, елементарна диз’юнкція) - це
логічна функція, що зв'язує всі літерали знаком диз'юнкції.
• Наприклад:
• f1 = a b c d;
f2 = a b.
• Макстерм називають також конституентою нуля, тому що ця логічна
функція дорівнює 0 тільки тоді, коли всі її літерали рівні 0 одночасно.
• Кон'юнктивний терм (мінтерм, елементарна кон’юнкція) - це
логічна функція, що зв'язує літерали знаком кон'юнкції.
• Наприклад:
• f1 = a & b & c & d;
f2 = a b c.
• Мінтерм називають також конституентою одиниці, тому що ця
функція дорівнює 1 тільки тоді, коли всі її літерали одночасно
дорівнюють одиниці.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
204

205. Досконалі нормальні форми

ДДНФ – Досконала диз’юнктивна нормальна форма
ДКНФ – Досконала кон’юнктивна нормальна форма
Ознаки ДНФ:
1) Кількість термів в ДДНФ (ДКНФ) дорівнює кількості одиничних
(нульових) значень ФАЛ у таблиці істинності цієї ФАЛ
2) Усі терми різні
3) У кожному термі присутні усі змінні
Кожна ФАЛ має лише одну ДДНФ і лише одну ДКНФ
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
205

206. Синтез логічних схем з одним виходом у базисі Буля на елементах з довільною кількістю входів

Матриця
Диз'юнктор
кон'юнкторів
a
&
1
a b c
b
c
Входи
a
Матриця
інверторів
a
1
a
b
b
1
b
c
c
1
c
a
b
c
&
a
&
a b c
&
a b c
a b c
Вихід
f
b
c
a
b
c
f a b c a b c a b c a b c
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
206

207. Основні правила виконання операцій у базисі Буля

a vb = b va
a v (b v c ) = (a v b ) v c
a v bc = (a v b )(a v c )
a = 1, якщо a 0;
Якщо a = 0, то a = 1
0 v 0 = 0;
0 v1 = 1
1 v1 = 1
0 = 1
a v0 = a
a v1 = 1
a va = a
a a
a v a = 1
ab = ba
a (bc ) = (ab )c
a (b v c ) = ab v ac
a = 0, якщо a 1;
Якщо a = 1, то a = 0
0 0 = 0;
1 0 = 0;
1 1 = 1;
1 = 0;
a 1 = a;
a 0 = 0;
a a = a;
a a
a a = 0;
a b c a b c
a (a v b ) = a
a v ab = a v b
ab v ab = b (a v a ) = b
НУЛП 20162017 н.р.
Закон комутативності
Закон асоціативності
Закон дистрибутивності
abc a b c
a v ab = a
a ( a v b ) = ab
(a v b )( a v b ) = b
Глухов В.С. Комп'ютерна логіка
Правило де Моргана
(закон поглинання)
(закон поглинання)
(закон склеювання)
207

208. Використання базису з 2-х ФАЛ: (І, НЕ)

Диз'юнктор
a b a b
Матриця
Матриця
кон'юнкторів
інверторів
a
1
&
a b c
b
кон'юнктор
&
c
Входи
a
Матриця
інверторів
a
1
a
b
b
1
b
c
c
НУЛП 20162017 н.р.
1
c
a
b
c
&
a
&
a b c
1
&
a b c
1
a b c
1
інвертор
Вихід
1
b
f
c
a
b
c
Глухов В.С. Комп'ютерна логіка
208

209. Використання базису з 2-х ФАЛ: (АБО, НЕ)

ab a c
Входи
a
Матриця
диз'юнкторів
a
1
b
c
Матриця
інверторів
a
1
b
b
1
c
1
a
Диз'юнктор
1
Вихід
c
a
b
b c
1
1
a
1
1
f
a
c
1
1
b
c
НУЛП 20162017 н.р.
1
Матриця
інверторів
b
c
Глухов В.С. Комп'ютерна логіка
209

210. Мінімізація ФАЛ

• Канонічна задача мінімізації
– У базисі Буля
– Над нормальними формами
– Мета – зменшення кількості літер
• Загальна задача мінімізації
– Усі інші методи
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
210

211. Методи розв’язання канонічної задачі мінімізації

• Аналітичні
– Квайна-МакКласскі-Петрика
– Інші
• Табличні
• Геометричні
• Графо-аналітичні
– Карти Карно
– Діаграми Вейча
• Алгебро-топологічні
• інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
211

212. Двовходові елементи базису Буля

a
b
&
a
b
ab
елемент 2І (2AND),
кон'юнктор
a
a
b
&
ab
&
abc
c
a
b
&
c
&
d
ab
&
&
cd
c
d
&
e
a b
ab
&
abc
a
b
1
a b
c
1
a b c
a
b
1
c
1
a b
&
1
a
елемент НЕ (NOT),
інвертор
1
abc deh
de
&
1
deh
h
i
j
a
елемент 2АБО (2OR),
диз'юнктор
b
abcd
1
hi
&
abc deh ijk
ijk
k
1
a b c d
c d
d
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
212

213. Основні правила виконання операцій у монобазисах І-НЕ (Шеффера) та АБО-НЕ (Пірса)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
213

214. Монобазис І-НЕ (NAND)

a
a
&
b
b
a b ... z
...
z
&
a
a b ... z
...
z
елемент І-НЕ (NAND)
a
1
a
елемент НЕ-АБО
1
a
a
&
b
a b ... z
1
ab... z
a
1
a
b
1
b
a b ... z
...
z
елемент І-НЕ (NAND)
...
елемент НЕ (NOT)
z
1
елементи НЕ
НУЛП 20162017 н.р.
1
z
елемент НЕ-АБО
Глухов В.С. Комп'ютерна логіка
214

215. Синтез логічних схем з одним виходом у монобазисі І‑НЕ

Синтез логічних схем з одним виходом у монобазисі І-НЕ
Матриця
Елемент НЕ-АБО
елементів І-НЕ
a
&
1
a b c
b
c
d
Входи
&
e
d e h
Вихід
h
i
j
f=abc v deh v іjk
f
&
i j k
k
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
215

216. 2І-НЕ

a
2І-НЕ
&
a b
&
a b
1
b
b
елемент 2І-НЕ
a
b
a
1
ab
&
c
a
ab
&
b
1
ab
&
abc
c
b
c
cd
&
cd
1
a a a
елемент НЕ-2АБО
&
&
a
1
a b
b
a
b
a
b
c
d
&
&
елементи 2І-НЕ
ab
елементи 2І-НЕ
&
a
&
1
a b
елемент НЕ-2АБО
&
b
&
a b
1
a b c
c
abcd
&
d
НУЛП 20162017 н.р.
1
елемент НЕ-2АБО
ab
&
a
елемент 2І-НЕ
a
a
a a a
1
c
&
&
ab cd
d
cd
&
a
1
a b
&
b
c
1
c d
d
&
a b
1
a b c d
c d
елемент НЕ-2АБО
Глухов В.С. Комп'ютерна логіка
216

217. Синтез логічних схем з одним виходом у монобазисі 2І-НЕ (Шеффера)

a
&
ab
f=abc v deh v іjk
1
b
ab
&
c
d
e
h
i
j
&
&
k
НУЛП 20162017 н.р.
de
ij
abc
1
de
&
deh
ij
&
ijk
1
abc deh
&
abc deh
1
f
1
Глухов В.С. Комп'ютерна логіка
217

218. Монобазис АБО‑НЕ (NOR)

Монобазис АБО-НЕ (NOR)
a
a
1
b
a b ... z
...
z
a
b
a b ... z
...
z
елемент АБО-НЕ (NOR)
a
&
b
1
a
a
елемент НЕ-І
&
a
a
1
a
b
1
b
a b ... z
1
a b ... z
...
z
&
a b ... z
елемент НЕ (NOT)
...
z
1
елемент АБО-НЕ (NOR)
елементи НЕ
НУЛП 20162017 н.р.
&
z
елемент НЕ-І
Глухов В.С. Комп'ютерна логіка
218

219. Синтез логічних схем з одним виходом у монобазисі АБО‑НЕ

Синтез логічних схем з одним виходом у монобазисі
АБО-НЕ
Матриця
Елемент НЕ-І
елементів АБО-НЕ
a
1
&
a b c
b
f=(avbvc)&(dvevh)&(іvjvk)
c
d
Входи
1
e
d e h
Вихід
h
i
j
f
1
i j k
k
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
219

220. 2АБО-НЕ

a
1
a
a a a
&
елемент 2АБО-НЕ
a
a b
1
&
a b
a
b
1
a b
1
c d
&
b
елемент 2АБО-НЕ (NOR)
a
1
a
елемент НЕ-2І
c
1
&
a
1
b
c
d
1
елементи 2АБО-НЕ
a
1
b
c
НУЛП 20162017 н.р.
a b
a
b
b
елементи 2АБО-НЕ
a
1
1
a b c d
&
1
b
ab
&
abc
c
1
c
( a b ) (c d )
c d
a
1
a
b
1
b
&
c
1
c
1
a b c
d
&
ab
елемент НЕ-2І
a b
&
ab
1
елемент НЕ-2І
a b
c d
елемент НЕ-2І
d
ab
b
&
a b
a a a
1
1
ab
&
abcd
&
cd
d
Глухов В.С. Комп'ютерна логіка
1
cd
220

221. Синтез логічних схем з одним виходом у монобазисі 2АБО-НЕ (Пірса)

Синтез логічних схем з одним виходом у монобазисі 2АБОНЕ (Пірса)
f (a b c)( d e h)(i j k )
a
1
a b
&
b
c
d
e
h
i
j
1
1
d e
i j
&
&
(a b c)( d e h)
(a b c)(d e h)
a b
1
a b c
&
1
&
d e
1
d e h
i j
1
i j k
f
k
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
221

222. Схеми елементів монобазисів на КМОН-транзисторах

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
222

223.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
223

224. Елеманти монобазисів на КМОН-транзисторах

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
224

225. Основні правила виконання операцій у базисі Жегалкіна

a b a b a b ( a b )( a b )
Для цієї функції справедливі наступні аксіоми:
a a = 0; a a a = a;
a a 1 a a 1
a 0 a
На підставі розглянутих аксіом і властивостей
елементарних логічних функцій можна, наприклад,
вивести правила представлення функцій І, АБО, НЕ
через функцію додавання за модулем 2 і навпаки:
a v b = a b ab;
ab = (a b) (a v b).
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
225

226. Виключне АБО (XOR)

a
a
=1 a b
b
а
НУЛП 20162017 н.р.
a
b
a b
b
Зафарбована область - a b
б
Глухов В.С. Комп'ютерна логіка
226

227. Реалізація XOR

a b a b a b
a b ( a b )( a b )
Входи
Матриця
інверторів
a
1
1-ий ступінь
a
a
b
b
1
b
a
b
a
b
&
&
a
1
&
1-ий ступінь
a
a
b
&
b
b
2-ий ступінь
a b
Матриця
інверторів
Входи
a
b
a
&
2-ий ступінь
a b
&
1
Вихід
f
a b
b
Вихід
a b
f
Входи
Матриця
інверторів
a
1
a
b
b
1
1-ий ступінь
a
a
1
2-ий ступінь
( a b)
b
a
b
b
1
&
Вихід
f
( a b)
a b a b a b
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
227

228. Порівняння варіантів синтезу комбінаційних логічних схем

c
0
1
1
0
1
5
1
7
a b d
6
1
F
1
9
1
B
5
8
C
a b d
A
1
D
8
1
7
6
F
E
1
9
1
2
a b c d
1
1
a
3
1
1
b
E
1
8
4
c
D
1
1
1
8
C
a
2
1
4
c
3
c
b
1
B
A
a b c d
1
d
d
f a b c d a b c d c
f a b d a b d c
( 1 a )( 1 b )c( 1 d ) a b c ( 1 d ) ( 1 c )
.
c
0
1
3
2
0
4
c d
5
7
0
8
C
D
a b c
6
F
0
b
E
f c d a b c a b c (c d ) (a b c) (a b c)
0
a
8
9
B
a b c
A
0
0
d
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
228

229. ДНФ

Входи
Матриця
інверторів
a
1
1-ий ступінь
1
2-ий ступінь
Входи
a
a
b
f a b d a b d c
b
b
a
&
a b d
b
1
a
Вихід
d
&
b
a b c
b
&
1-ий ступінь
a
a
f
a
Матриця
інверторів
&
b
b
d
1
c
d
&
a b d
b
d
1
Вихід
f
a
&
a b c
b
d
c
a
2-ий ступінь
d
c
d
d
&
d
c
c
d
Матриця
інверторів
Входи c
1
1-ий ступінь
c
a
d
b
c
1
d
a
&
b
2-ий ступінь
a b d
d
d
Вихід
1
a b d a b d c
a
b
3-ий ступінь
1
&
f
a b d
b
d
c
d
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
229

230. КНФ

Матриця
інверторів
Входи a
&
1-ий ступінь
a
a
b
&
b
b
c
&
c
c
d
&
d
d
c
1
c d
d
a
1
b
2-ий ступінь
&
Матриця
інверторів
Вихід
a b c
Входи a
f
b
c
a
1
b
c
a b c
d
&
1-ий ступінь
a
a
b
НУЛП 20162017 н.р.
1
b
&
b
c
1
d
a
1
c
c
c
Входи a
d
a
b
Матриця
інверторів
c
1
1-ий ступінь
a
d
b
f ( c d ) ( a b c ) ( a b c )
2-ий ступінь
c d
1
a b c
1
a b c
b
1
d
c
1
c d
d
a
2-ий ступінь
1
a b c
1
a b c
b
&
Вихід
f
c
a
b
c
3-ий ступінь
Вихід
&
(c d )(a b c)(a b c)
1
f
c
a
b
c
Глухов В.С. Комп'ютерна логіка
230

231. Поліном Жегалкіна

Суматори за
модулем 2 як
Матриця
інвертори
кон'юнкторів
a
&
a b c d
"1"
b
Входи
a
b
c
d
=1
a
=1
b
=1
c
=1
d
c
d
a
a
b
b
c
d
c
c
Суматори за
модулем 2
=1
=1
&
Вихід
a b c d
f
d
f ( 1 a )( 1 b )c( 1 d ) a b c ( 1 d ) ( 1 c )
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
231

232. Поліном Жегалкіна

Трикутник Паскаля
f x2 x3 x1 x3 x1 x2
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
232

233. Небулеві базиси

• Базис Жегалкіна (1, І, XOR)
• Мажоритарний базис f ( x , x ,..., x
1
2
2n 1
1, якщо xi n
i 1
2 n 1 )
2n 1
0 , якщо xi n
i 1
• Пороговий базис, wi, T - const
n
1, якщо xi wi T
i 1
f ( x1 , x 2 ,..., x n )
n
0 , якщо xi wi T
i 1
• Штучний інтелект, wi, T - var
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
233

234. Порогові функції

(>0)
(=n)
(=2)
a
b
avb
ab
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
234

235. Форми представлення ФАЛ

• Табличні
– Таблиці істинності
– Сингулярні таблиці
Геометричні
Числові
Часові діаграми
Схеми
Аналітичні (формули)
інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
235

236. Геометричний спосіб представлення ФАЛ

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
236

237. Аналітичні форми представлення ФАЛ

• Нормальні
– Досконалі
• ДДНФ
• ДКНФ
• інші
– Скорочені (ДНФ, КНФ)
• Глухого кута – з найменшою кількістю термів
• Мінімальні – форма глухого кута з найменшою кількістю літер
• Абсолютно мінімальні – мінімальна у базисі Буля
• Анормальні
– Дужкові
– Із запереченням більше ніж над однією змінною
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
237

238. Терм

• Терм - це група літерал і констант, об'єднаних тим самим знаком
логічного зв'язування: логічного додавання або ж логічного
множення. У термі кожен літерал і кожна константа зустрічається
тільки один раз, тобто в терм може входити або змінна, або її
заперечення.
• Диз'юнктивний терм (макстерм, елементарна диз’юнкція) - це
логічна функція, що зв'язує всі літерали знаком диз'юнкції.
• Наприклад:
• f1 = a b c d;
f2 = a b.
• Макстерм називають також конституентою нуля, тому що ця логічна
функція дорівнює 0 тільки тоді, коли всі її літерали рівні 0 одночасно.
• Кон'юнктивний терм (мінтерм, елементарна кон’юнкція) - це
логічна функція, що зв'язує літерали знаком кон'юнкції.
• Наприклад:
• f1 = a & b & c & d;
f2 = a b c.
• Мінтерм називають також конституентою одиниці, тому що ця
функція дорівнює 1 тільки тоді, коли всі її літерали одночасно
дорівнюють одиниці.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
238

239. Нормальні форми з мінтермами

• Будь-яка таблично задана ФАЛ може бути
представлена аналітично у вигляді
– диз'юнкції скінченого числа мінтермів, на кожнім з яких
функція дорівнює одиниці (диз’юнктивна нормальна
форма, ДНФ):
f(a, b,..., z) = F1 F2 ... F n,
– суми за модулем 2 скінченого числа мінтермів, на
кожнім з яких функція дорівнює одиниці (поліном
Жегалкіна):
f ( a ,b ,..., z ) F 1 F 2 ... Fn ,
де i - номери наборів, на яких функція дорівнює 1.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
239

240. Нормальні форми з макстермами

• Будь-яка таблично задана ФАЛ може бути
представлена аналітично у вигляді
– кон'юнкції скінченого числа макстермів, на кожнім з
яких функція дорівнює нулю (кон’юнктивна нормальна
форма, КНФ):
f(a, b,..., z) = Ф1 & Ф2 & ... & Фm,
– результату порівняння скінченого числа макстермів, на
кожнім з яких функція дорівнює нулю (поліном
рівнозначності):
f ( a ,b ,..., z ) 1 2 , , , m ,
де i - номери наборів, на яких функція дорівнює 1.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
240

241. Досконалі нормальні форми

• Кількість термів дорівнює кількості
одиничних (нульових) значень ФАЛ у її
таблиці істиності
• У кожному термі присутні усі змінні
• Немає однакових термів
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
241

242. Анормальні форми

Дужкова
f ab ab ( a b )ab
Із запереченням більше ніж над
однією літерою
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
242

243. Критерії синтезу схем ФАЛ

• Правильна робота
• Швидкодія (продуктивність)
• Апаратні витрати
Споживана потужність
Надійність
Складність
Однорідність структури
Ціна
інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
243

244. Методи визначення ціни реалізації ФАЛ

• Грошові одиниці
• Негрошові одиниці
– Кількість операцій
• І, АБО, НЕ
• І, АБО
• І (АБО)
– Кількість термів
• В ДНФ
• В КНФ
– Кількість літер
• В нормальних формах
• В анормальних формах
– Кількість входів
• І, АБО, НЕ
• І, АБО
• І (АБО)
– інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
244

245. Мінімізація ФАЛ

• Канонічна задача мінімізації
– У базисі Буля
– Над нормальними формами
– Мета – зменшення кількості літер
• Загальна задача мінімізації
– Усі інші методи
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
245

246. Методи розв’язання канонічної задачі мінімізації

• Аналітичні
– Квайна-МакКласскі-Петрика
– Інші
• Табличні
• Геометричні
• Графо-аналітичні
– Карти Карно
– Діаграми Вейча
• Алгебро-топологічні
• інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
246

247. Методи розв’язання загальної задачі мінімізації (аналітичні)

• Еврістичний (Метод спроб і помилок)
• Винесення за дужки
• Внесення надлишковості і глобального
винесення за дужки
• Перехід до небулевого базису
• Метод функціональної декомпозиції
• інші
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
247

248. Еврістичний

f ab ab ( a b )ab
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
248

249. Винесення за дужки

f abc acde abdg deg
ac( b de ) dg( ab e )
Внесення надлишковості і
глобального винесення за дужки
f abc acde abdg deg
aabc acde abdg d deg
ab( ac dg ) de( ac dg )
( ab de )( ac dg )
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
249

250. Метод функціональної декомпозиції проста розділова і загальний випадок

X1
f a bd bc ac
Ф1
Ф2
X2
f(X1,X2)
2 1 d 1 c
X1
Ф1
f(X1,X2,X3 )
X3
X2
1 a b
Ф2
f ab ade bc d be
1 b de
2 1 a 1 ( c e )
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
250

251. Багаторозрядний суматор

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
251

252. 4-розрядні суматори (у прямому, оберненому і доповняльному кодах)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
252

253. Повний однорозрядний двійковий суматор

Co ABCi ABCi ABCi ABCi BCi ACi AB
S A BCi ABCi AB Ci ABCi
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
253

254. Функціональна схема повного однорозрядного двійкового суматора

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
254

255. Повний однорозрядний двійковий суматор (матрична схема)

SUM
A
B
CI
S
CO
Входи
Матриця
інверторів
(елементі
в НЕ)
Матриця кон'юнкторів
(елементів І)
І 0 І1 І 2 І 3 І 4 І 5 І 6
A
A
A
B
- точки, де є
з'єднання
B
B
CI
CI
CI
Co ABCi ABCi AB Ci ABC i BCi AC i AB
S A BCi ABCi AB Ci ABCi
Виходи
АБО0
S
CO
АБО1
A B CI
BC I
AB
A B C I ABC I AC I
A B CI
Матриця диз'юнкторів
(елементів АБО)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
255

256. Двійкові однорозрядні напівсуматор (а) та повний суматор (б)

a
c0 = ab;
s
b
s ab ab ( a b )co
a
b
ci
co
co
Ci
&
a
s
1
a
b
НУЛП 20162017 н.р.
s
б
а
1
A
a
s
.
&
ab
co
B
b
b
S
s
co
1
Ci
co
Глухов В.С. Комп'ютерна логіка
256

257. Багатозначні логіки. Нечітка логіка

• Тризначна логіка Лукасевича {0,1/2,1}
(ні, може бути, так)
• N-значна логіка Лукасевича {0/n-1,1/n-1, …,n-1/n-1}
a 1 a; a & b min( a ,b ); a b max( a ,b )
• Тризначна логіка Поста {0,1,2}
• N-значна логіка Поста {0,1,2, …,n-1}
a ( a 1 ) mod N ; a & b min( a ,b ); a b max( a ,b )
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
257

258.

Комп’ютерна логіка (частина 2)
Національний університет «Львівська політехніка»
Lviv Polytechnic National University
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
258

259. Виконання навчального плану

• Здана курсова робота
• Виконано програму практичних занять
• Написано усі 16 лекційних контрольних
робіт
• Дано правильні відповіді на усі тести
• Є конспект лекцій (приблизно 5 сторінок на
лекцію)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
259

260. Державна оцінка (іспит)

• 1. Оцінка на іспиті
• 2. Оцінка на іспиті за талоном
• 3. Оцінка на комісії
– або
• 3б. Оцінка за результатами повторного
вивчення курсу – можливо більше не буде
Державна оцінка
(залік за курсову роботу)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
260

261. Стандартні вимоги до відповідей на іспиті

• Повинна бути дана відповідь на усі питання
білету
• Під час підготовки відповіді нічим не
можна користуватися
• Під час підготовки відповіді ні з ким не
можна перемовлятися та обмінюватися
інформацією
• Для допуску до іспиту потрібно виконати
навчальний план
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
261

262. Полегшені умови до іспитів, комісії та повторки

• Студент погоджується самостійно опрацювати
учбового плану
• Білет на іспит видається достроково за умови
деякі
питання
– До 15-го навчального тижня здано усі задачі курсової роботи і отримано
за них більше 60 балів
– У сумі за практичні заняття отримано більше 20 балів (з 30)
– Написано усі лекційні контрольні роботи на дану дату
– Правильно дано відповіді на усі питання тестів до 2-ої частини
Комп’ютерної логіки (2-ий курс) у ВНС
– Є конспект лекцій (приблизно 5 сторінок на лекцію)
– Здано академрізницю (в кого вона є)
– Складено іспит за повторне вивчення 1-ої частини Комп’ютерної логіки
(кому це потрібно)
• Під час підготовки до відповіді дозволяється користуватися чим
завгодно
• Повинна бути дана відповідь на усі питання білету
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
262

263. Оцінювання відповідей при стандартному підході

Оцінка Оцінка практичні Оцінка ЛекційніКР 65 * Оцінка білет / 70
Для іспиту:
Оцінка 100; Оцінка практичні 30; Оцінка ЛекційніКР 5; Оцінка білет 70
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
263

264. Оцінювання відповідей на іспиті при полегшеному підході

Оцінка Оцінка практичні
Оцінка ЛекційніКР
5 * 16
Оцінка Тести
*
* Оцінка білет
100
Оцінка 100; Оцінка практичні 30; Оцінка ЛекційніКР 5 * 16 ;
Оцінка Тести 100; Оцінка білет 70
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
264

265. Покращення оцінок

• Було 51 бал – 51% від 100 балів
(поточний контроль – 1 з 30, іспит - 50 з 70,
3% з 30 за поточку і 71% з 70 за іспит)
• Хоче “добре” (71 бал – 71% від 100 балів)
• Тоді треба набрати спочатку за поточний
контроль 71% від 30 = 21 бал,
а після того -71% від 70 =50 балів за іспит.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
265

266. Відпрацювання пропущених лекційних контрольних робіт

• Копія власноручно написаного конспекту
лекції, на якій писали пропущену
контрольну роботу
• Ескізи слайдів, що демонструвалися на
лекції, на якій писали пропущену
контрольну роботу
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
266

267. Курсова робота

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
267

268. Використання результатів 2-ої частини

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
268

269. Вимоги до оформлення курсової роботи

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
269

270. Комп’ютерна логіка. Курсова робота. Група КІ-21. 2015/2016 н.р. (14 навчальних тижнів)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
270

271. Оцінювання курсової роботи

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
271

272. Розклад викладача

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
272

273. Консультації – після закінчення останнього лекційного заняття, на каф. ЕОМ, 503-V або за домовленістю

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
273

274. Завдання на курсову роботу

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
274

275. Віртуальне навчальне середовище

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
275

276. ВНС, Комп’ютерна логіка, ч.2

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
276

277. Екзаменаційний білет

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
277

278. Робочий журнал

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
278

279. БАЗОВІ КОМБІНАЦІЙНІ ВУЗЛИ

дешифратори і демультиплексори;
мультиплексори;
шифратори;
перетворювачі кодів;
постійні запам’ятовуючі пристрої;
програмовані логічні матриці;
програмовані матриці логіки;
суматори і напівсуматори;
вузли порівняння;
арифметично-логічні пристрої;
вузли зсуву;
помножувачі;
вузли прискорення переносу;
інші.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
279

280. Газорозрядні індикатори

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
280

281. Дешифратор “3 у 8”

Матриця
кон'юнкторів
Дешифратор “3 у 8”
Виходи
1
&
4 2 1 CS
0
І0
&
4 2 1 CS
1
2
Входи
4
CS
Матриця
інверторів
1
1
1
2
1
2
4
4
1
1
1
2
4
CS
2
4
CS
1
І1
&
4 2 1 CS
2
І2
&
4 2 1 CS
3
2
4
CS
1
2
4
CS
1
2
4
CS
1
1
2
4
CS
1
4 2 1 CS
4
I0
I1
I2
І4
&
4 2 1 CS
5
CS
І5
&
4 2 1 CS
6
I[2:0]
CS
DC O0
O1
O2
O3
O4
O5
O6
O7
в
DC
O[7:0]
г
І6
&
2
4
CS
CS
І3
&
2
4
CS
1
2
4
DC 0
1
2
3
4
5
6
7
б
4 2 1 CS
7
І7
а
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
281

282. Матрична схема дешифратора “3 у 8"

Матрична схема дешифратора “3 у 8"
Матриця
інверторів
Матриця кон'юнкторів
І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7
Входи
4
4
2
2
1
1
CS
0 1 2 3 4 5 6 7
Виходи
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
282

283. VHDL-опис дешифратора “3 у 8”

library IEEE;
use IEEE.STD_LOGIC_1164.all;
use IEEE.STD_LOGIC_UNSIGNED.all;
entity DC is
port (
O : out STD_LOGIC_VECTOR (7 downto 0);
I : in STD_LOGIC_VECTOR (2 downto 0);
CS : in STD_LOGIC);
end entity;
architecture DC_arch of DC is
begin
O(0) <= CS when (I = 0) else '0';
O(1) <= CS when (I = 1) else '0';
O(2) <= CS when (I = 2) else '0';
O(3) <= CS when (I = 3) else '0';
O(4) <= CS when (I = 4) else '0';
O(5) <= CS when (I = 5) else '0';
O(6) <= CS when (I = 6) else '0';
O(7) <= CS when (I = 7) else '0';
end architecture;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
283

284. Реалізація ФАЛ на дешифраторах

Матриця
інверторів
Матриця кон'юнкторів
І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7
Входи
c
b
a
"1"
1
2
4
CS
DC 0
1
2
3
4
5
6
7
a b c
a b c
a b c
4
4
2
2
1
1
1
Вихід
f
a b c
a b c
CS
Вихід
f
АБО0
0 1 2 3 4 5 6 7
Виходи дешифратора
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
284

285. Нарощування розрядності дешифраторів DC “4 у 16” з DC “3 у 8”

1
2
4
d
c
d
c
b
b
DC 0
8
a
d
c
1
2
4
b
a CS
1
d
c
1
2
4
b
CS
CS
CS
D1 1
НУЛП 20162017 н.р.
a CS
CS
a b c d CS
DC 0
a b c d CS
1
a b c d CS
2
a b c d CS
3
a b c d CS
4
a b c d CS
5
a b c d CS
6
a b c d CS
D2 7
a b c d CS
DC 0
a b c d CS
1
a b c d CS
2
a b c d CS
3
a b c d CS
4
a b c d CS
5
a b c d CS
6
a b c d CS
D3 7
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Глухов В.С. Комп'ютерна логіка
1
2
4
8
CS
DC 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
285

286. Нарощування розрядності дешифраторів DC “3 у 8” з DC “1 у 2”

1
1
DC
0
ВК
1
1
DC
0
ВК
D1
1
ВК
1
1
DC
0
ВК
1
ВК D1 1
НУЛП 20162017 н.р.
ВК
D1
1
ВК
DC
D1
DC
D1
DC
D1
DC
D1
Глухов В.С. Комп'ютерна логіка
0
1
0
1
0
1
0
1
286

287. Демультиплексор DX = Дешифратор DC

Матриця
кон'юнкторів
Виходи
1
Дані
Керування
1
2
4
CS
DC 0
1
2
3
4
5
6
7
&
4 2 1 CS
0
І0
&
4 2 1 CS
1
І1
&
4 2 1 CS
2
І2
&
4 2 1 CS
3
І3
&
4 2 1 CS
4
І4
&
4 2 1 CS
5
І5
&
4 2 1 CS
6
І6
&
4 2 1 CS
7
2
4
CS
Матриця
інверторів
1
1
1
1
2
1
4
1
1
2
2
4
CS
4
2
4
CS
1
2
4
CS
1
2
4
CS
Керування
1
2
4
Дані
CS
DX 0
1
2
3
4
5
6
7
1
2
4
CS
1
2
4
CS
1
2
4
CS
1
2
4
CS
НУЛП 20162017 н.р.
І7
Глухов В.С. Комп'ютерна логіка
287

288. Класифікація DC та DX

Дешифратор DC
Демультиплексор DX
Входів
Виходів
Назва
Входів
Виходів
Назва
1
2
1у2
1
2
1у2
2
4
2у4
2
4
1у4
3
8
3у8
3
8
1у8
4
16
4 у 16
4
16
1 у 16
5
32
5 у 32
5
32
1 у 32
n
2n
n у 2n
n
2n
1 у 2n
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
288

289. Мультиплексор 8 в 1

Інформаційні
входи
Входи
управління
Інформаційні
входи
Входи
управління
0
1
2
3
4
5
6
7
1
2
4
Матриця кон'юнкторів
І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7
Входи управління
а
I0 MUX
I1
I2
I3
I4
I5
I6
I7
S0
S1
S2
б
MUX
Інформаційні входи
Входи управління
Матриця
інверторів
MUX
4
4
2
2
1
1
Інформаційні входи
0
1
2
3
4
5
6
7
Вихід
АБО0
г
I[7:0]
S[2:0]
в
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
289

290. VHDL-опис

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
entity mux is
port ( I : in std_logic_vector (7 downto 0);
S : in std_logic_vector (2 downto 0);
O : out std_logic);
end entity;
architecture mux_arch of mux is
begin
O <= I(CONV_INTEGER(S));
end architecture;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
290

291. Реалізація ФАЛ на мультиплексорах

"1"
"0"
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
c
b
a
0
1
2
3
4
5
6
7
1
2
4
MUX
f
291

292. Нарощування розрядності мультиплексорів

0
1
2
3
4
5
6
7
1
1
2
2
4
4
8
9
10
11
12
13
14
15
1
2
4
НУЛП 20162017 н.р.
0
1
2
3
4
5
6
7
1
2
4
0
1
2
3
4
5
6
7
1
2
4
MUX
0
MUX
D1
MUX
0 MUX
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
8
1
1
D2
1
2
4
8
D2
Глухов В.С. Комп'ютерна логіка
292

293. Класифікація DC, DX, MUX

Дешифратор DC
Демультиплексор DX
Мультиплексор MUX
Входів
Виходів
Назва
Входів
Виходів
Назва
Входів
Виходів
Назва
1
2
1у2
1
2
1у2
2
1
2в1
2
4
2у4
2
4
1у4
4
1
4в1
3
8
3у8
3
8
1у8
8
1
8в1
4
16
4 у 16
4
16
1 у 16
16
1
16 в 1
5
32
5 у 32
5
32
1 у 32
32
1
32 в 1
n
2n
n
2n
1 у 2n
2n
1
2n в 1
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
293

294. Шифратор Coder CD

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
294

295. Класифікація DC, CD, DX, MUX

Дешифратор DC
Шифратор CD
Демультиплексор DX
Мультиплексор MUX
Входів
Виходів
Назва
Входів
Виходів
Назва
Входів
Виходів
Назва
Входів
Виходів
Назва
1
2
1у2
2
1
2у1
1
2
1у2
2
1
2в1
2
4
2у4
4
2
4у2
2
4
1у4
4
1
4в1
3
8
3у8
8
3
8у3
3
8
1у8
8
1
8в1
4
16
4 у 16
16
4
16 у 4
4
16
1 у 16
16
1
16 в 1
5
32
5 у 32
32
5
32 у 5
5
32
1 у 32
32
1
32 в 1
n
2n
n у 2n
2n
n
2n у n
n
2n
1 у 2n
2n
1
2n в 1
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
295

296. Пріоритетний шифратор

CD
0
1
2
0
1
2
1
3
4
5
6
7
2
4
3
4
5
6
7
CD
1
2
4
RDY
7
6
5
4
3
2
1
0
4
2
1
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
Rd
0
1
2
3
4
5
6
7
6
5
4
3
2
1
0
4
2
1
1
X
X
X
X
X
X
X
1
1
1
1
0
1
X
X
X
X
X
X
1
1
0
1
0
0
1
X
X
X
X
X
1
0
1
1
1
0
0
0
1
X
X
X
X
1
0
0
1
2
0
0
0
0
1
X
X
X
0
1
1
1
0
0
0
0
0
1
X
X
0
1
0
1
0
0
0
0
0
0
1
X
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
X
X
X
0
7
4
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
y
296

297. Двійково-десяткові коди

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
297

298. Перетворювач кодів 8421 у 8421+3 DC + CD

Перетворювач кодів 8421 у 8421+3
‘0’
DC + CD
DC
a1
a2
a4
a8
НУЛП 20162017 н.р.
1
2
4
8
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
‘0’
‘0’
‘0’
0
1
2
3
4
5
6
7
8
9
‘0’
‘0’
‘0’
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CD
1
2
4
8
b1
b2
b4
b8
a1
a2
a4
a8
a1
a2
a4
a8
Глухов В.С. Комп'ютерна логіка
X/Y
b1
b2
b4
b8
b1
b2
b4
b8
298

299. Матрична схема перетворювача коду 8421 у код 8421+3

8
4
Дешифратор –
набір елементів І,
матриця І
2
1
АБО1
8
АБО2
4
АБО3
2
АБО4
1
Шифратор –
набір елементів
АБО, матриця АБО
I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 I12 I13 I14 I15
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
299

300. Перетворювач кодів для семигементного індикатора

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
300

301. Перетворювач кодів – дешифратор для 7-сегментного індикатора

Перетворювач кодів – дешифратор для 7сегментного індикатора
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
301

302. Програмовані структури

n
ПЗП
ROM
Матриця
І
Непрограмована
Повний DC
n
N=2n
Матриця
АБО
Програмована
CD
ПЛМ
PLA
Матриця
І
Програмована
Неповний DC
n
N<<2n
m
Матриця
АБО
Програмована
CD
N<<2n
m
Організація: 2n x m
Об’єм: V = 2n x m
НУЛП 20162017 н.р.
ПМЛ
PAL
Матриця
І
Програмована
Неповний DC
Матриця
АБО
Непрограмована
CD
m
Зворотні зв’язки
Глухов В.С. Комп'ютерна логіка
302

303. Постійний запам’ятовуючий пристій

Матриця кон'юнкторів
(елементів І)
ROM
A0
A1
D0
D1
D2
D3
A2
Матриця І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7
інверторів
Входи
A2
A2
A1
A1
A0
A0
CS
а
ROM
D[3:0]
A[2:0]
CS
б
CS
Виходи
- точки, де завжди
є з'єднання
- точки, де може бути
з'єднання
АБО0
D0
D1
D2
D3
АБО1
АБО2
АБО3
Матриця диз'юнкторів
(елементів АБО)
в
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
303

304. Реалізація ФАЛ на ПЗП

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
304

305. Реалізація ФАЛ на ПЗП

Входи
a
b
c
"0"
"1"
A0 ROM D0
D1
A1
D2
A2
D3
A3
A4
A5
A6
A7
CS
Матриця Матриця кон'юнкторів
інверторів
(елементів І)
І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7 І 8
A7
A7
A3
A3
A2
A2
A1
A1
A0
A0
І 255
f0
f1
f2
CS
- точки, де є з'єднання
Виходи
АБО0
D0
D1
D2
D3
АБО 1
АБО2
АБО3
Матриця диз'юнкторів
(елементів АБО)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
305

306. Опис ПЗП на мові VHDL

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
entity rom is
port (
CS : in STD_LOGIC;
A : in STD_LOGIC_VECTOR(2 downto 0);
D : out STD_LOGIC_VECTOR(3 downto 0));
end entity;
architecture rom_arch of rom is
begin
process(A, CS)
begin
if (CS = '1') then
case (A) is
when "000" => D <= "0100";
when "001" => D <= "0010";
when "010" => D <= "0111";
when "011" => D <= "0100";
when "100" => D <= "0001";
when "101" => D <= "0011";
when "110" => D <= "0101";
when "111" => D <= "0101";
when others => D <= "0000";
end case;
else
D <= "0000";
end if;
end process;
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
306

307. Програмовані логічні матриці

PLA
D0
D1
D2
D3
A0
A1
A2
Входи
Матриця
інверторів
(елементів
НЕ)
A2
A2
A1
A1
A0
A0
Матриця кон'юнкторів
(елементів І)
І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7
CS
а
PLA
D[3:0]
A[2:0]
CS
б
CS
- точки, де завжди
є з'єднання
- точки, де може бути
з'єднання
Виходи
АБО0
D0
D1
D2
D3
АБО1
АБО2
АБО3
Матриця диз'юнкторів
(елементів АБО)
в
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
307

308. Реалізація ФАЛ на ПЛМ

PLA
a
b
c
"1"
A0
A1
A2
D0
D1
D2
D3
f0
f1
f2
Входи
Матриця кон'юнкторів
(елементів І)
І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7
Матриця
інверторів
(елементів
НЕ)
A0
A0
a
a
A1
b
b
A2
c
c
CS
а
A1
A2
CS
- точки, де є з'єднання
Виходи
АБО0
D0 f0
D1 f1
D2 f2
D3
АБО1
АБО 2
АБО3
b c
a b
c
a c a b c a b
Матриця диз'юнкторів
(елементів АБО)
НУЛП 20162017 н.р.
f0 b c a c a b
f1 a b a b c
f2 c a b a b
б
Глухов В.С. Комп'ютерна логіка
308

309. Таблиця прошиття ПЛМ

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
309

310. Програмовані матриці логіки

PAL
A0
A1
A2
D0
D1
D2
D3
Входи
Матриця 1
інверторів
(елементів
НЕ)
A2
A2
A1
A1
A0
A0
Матриця кон'юнкторів
(елементів І)
І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7
CS
а
PAL
D[3:0]
A[2:0]
CS
б
Матриця 2
інверторів
(елементів
НЕ)
CS
- точки, де завжди
є з'єднання
D3
D3
- точки, де може бути
з'єднання
D2
D2
D1
D1
D0
D0
Виходи
АБО0
D0
D1
D2
D3
АБО1
АБО 2
АБО3
Матриця диз'юнкторів
(елементів АБО)
в
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
310

311. Реалізація ФАЛ на ПМЛ

PAL
a
b
c
"1"
D0
D1
D2
D3
A0
A1
A2
f0 Входи
f1
Матриця 1
інверторів
(елементів
НЕ)
Матриця кон'юнкторів
(елементів І)
І 0 І1 І 2 І 3 І 4 І 5 І 6 І 7
A2
a
a
A1
A1
b
b
A0
A0
c
c
A2
CS
а
Матриця 2
інверторів
(елементів
НЕ)
CS
- точки, де є з'єднання
D3
D3
D2
D2
D1
D1
D0
D0
Виходи
АБО0
АБО1
АБО 2
АБО3
b c
a c
D0
D1
c a b
f1
f0
D2
D3
f1
f0 b c a c a b
f1 c a b a b
c
a b
b c a c
a b
a b
c a b
Матриця диз'юнкторів
(елементів АБО)
НУЛП 20162017 н.р.
b c a c
f0
б
Глухов В.С. Комп'ютерна логіка
311

312. Таблиця прошиття ПМЛ

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
312

313. Логічна комірка

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
313

314. ПЛІС першого покоління

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
314

315. Конфігуровані логічні блоки (CLB) та електронні комутатори (PSM -Programmable switch matrix )

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
315

316. Електронний комутатор

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
316

317. Операційний пристрій на основі ПЗП

S = 2M + 3N
A
Адреса
a3
1
a2
1
M
N
НУЛП 20162017 н.р.
a1
0
m1
a0
1
m0
1
n1
n0
3
Глухов В.С. Комп'ютерна логіка
317

318. Таблиця прошиття ПЗП

A
(адреса
ПЗП)
A10
a2
A2
n0
a3
A3
n1
НУЛП 20162017 н.р.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
a0
A0
m0
a1
A1
m1
N
2M + 3N=S
M
S16
M
N
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Дані
Розрахунок
Адреса
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
1
1
1
1
2
2
2
2
3
3
3
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
*0
*0
*0
*0
*1
*1
*1
*1
*2
*2
*2
*2
*3
*3
*3
*3
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
0
2
4
6
3
5
7
9
6
8
10
12
9
11
13
15
0
2
4
6
3
5
7
9
6
8
A
С
9
B
D
F
s3
D1
0
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
s2
D0
0
0
1
1
0
1
1
0
1
0
0
1
0
0
1
1
Глухов В.С. Комп'ютерна логіка
s1
D1
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
s0
D0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
D
(дані
ПЗП)
0
2
4
6
3
5
7
9
6
8
A
С
9
B
D
F
318

319. Пам’ять перших комп’ютерів

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
319

320. Вузол порівняння на основі DC

I = 638 = 110 011 = i5i4i3i2i1i0
Вузол
порівняння на
основі DC
i3
i4
1
2
4
i5
" 1"
CS
DC 0
1
2
3
4
5
6
D2 7
i0
i1
i2
110 = i5i4i3
1
2
4
CS
DC 0
1
2
3
4
5
6
D3 7
Рівно
I = 638 = 110 011 = i5i4i3i2i1i0
Вузол
порівняння
на основі
MUX
0
0
0
0
0
0
1
0
i3
i4
i5
НУЛП 20162017 н.р.
0
1
2
3
4
5
6
7
1
2
4
MUX
D1
0
0
0
1
0
2
110 = i5i4i3
3
0
4
0
5
0
6
0
7
i0
1
i1
2
i2
4
Глухов В.С. Комп'ютерна логіка
MUX
Рівно
D2
320

321. Компаратори

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
321

322. 4-розрядний універсальний компаратор

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
322

323. Багаторозрядні компаратори

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
323

324.

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
324

325. Неповні дешифратори

Таблиця 3.12.1
Адреса у 16ковому
коді
A7
A6
A5
A4
A3
A2
A1
A0
b8
1
0
1
1
1
0
0
0
b9
1
0
1
1
1
0
0
1
ba
1
0
1
1
1
0
1
0
bb
1
0
1
1
1
0
1
1
bc
1
0
1
1
1
1
0
0
bd
1
0
1
1
1
1
0
1
be
1
0
1
1
1
1
1
0
bf
1
0
1
1
1
1
1
1
b8…bf
1
0
1
1
1
-
-
-
НУЛП 20162017 н.р.
Розряди адреси
Diap A7 A6 A5 A4 A3
Глухов В.С. Комп'ютерна логіка
325

326. Дешифратор діапазону кодів 04B8F ...1Е3А4 (04B8F…0FFFF)

DIAP
00000 04B8F
D2
0FFFF
M
10000
1E3A4
1FFFF
S
D1
┌──┬────────────────────────────────┬───────┬─────────┐
│N │
Входи A ПЛМ
│Виходи │Диапазон │
│ │15 13 11 09 07 05 03 01 │0 1 2 3│ кодів
│
│ │ 14 12 10 08 06 04 02 00│
│
│
│ ├────────────────────────────────┼───────┼────┬────┤
│ │A15 A13 A11 A9 A7
A5 A3 A1 │M
│ від│ до │
│ │ A14 A12 A10 A8 A6
A4 A2 A0│
│
│
│
├──┼────────────────────────────────┼───────┼────┼────┤
│I0│ L H L L H L H H H L L L H H H H│A - - -│4B8F│4B8F│
│I1│ L H L L H L H H H L L H - - - -│A - - -│4B90│4B9F│
│I2│ L H L L H L H H H L H - - - - -│A - - -│4BA0│4BBF│
│I3│ L H L L H L H H H H - - - - - -│A - - -│4BC0│4BFF│
│I4│ L H L L H H - - - - - - - - - -│A - - -│4C00│4FFF│
│I5│ L H L H - - - - - - - - - - - -│A - - -│5000│5FFF│
│I6│ L H H - - - - - - - - - - - - -│A - - -│6000│7FFF│
│I7│ H - - - - - - - - - - - - - - -│A - - -│8000│FFFF│
└──┴────────────────────────────────┴───────┴────┴────┘
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
326

327. Дешифратор діапазону кодів 04B8F ...1Е3А4 (10000…1E3A4)

DIAP
00000 04B8F
D2
0FFFF
M
10000
1E3A4
1FFFF
S
D1
┌──┬────────────────────────────────┬───────┬─────────┐
│N │
Входи A ПЛМ
│ Виходи│Диапазон │
│ │15 13 11 09 07 05 03 01 │0 1 2 3│ кодів │
│ │ 14 12 10 08 06 04 02 00│
│
│
│ ├────────────────────────────────┼───────┼────┬────┤
│ │A15 A13 A11 A9 A7
A5 A3 A1 │S
│ від│ до │
│ │ A14 A12 A10 A8 A6
A4 A2 A0│
│
│
│
├──┼────────────────────────────────┼───────┼────┼────┤
│I0│ H H H L L L H H H L H L L H L L│A - - -│E3A4│E3A4│
│I1│ H H H L L L H H H L H L L L - -│A - - -│E3A0│E3A3│
│I2│ H H H L L L H H H L L - - - - -│A - - -│E380│E39F│
│I3│ H H H L L L H H L - - - - - - -│A - - -│E300│E37F│
│I4│ H H H L L L H L - - - - - - - -│A - - -│E200│E2FF│
│I5│ H H H L L L L - - - - - - - - -│A - - -│E000│E1FF│
│I6│ H H L - - - - - - - - - - - - -│A - - -│C000│DFFF│
│I7│ H L - - - - - - - - - - - - - -│A - - -│8000│BFFF│
│I8│ L - - - - - - - - - - - - - - -│A - - -│0000│7FFF│
└──┴────────────────────────────────┴───────┴────┴────┘
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
327

328. Дешифратор діапазону кодів 04B8F ...1Е3А4

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
328

329. Логічні операції над числами

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
329

330. Зсуви

M=6
m2 m1
1
1
m3
0
Co=0
m0
0
Ci=1
1
r3
1
0
r2
r1
R=D
1
r0
m3
0
Co=0
m3
0
m0
0
Ci=1
1
r3
Логічний зсув ліворуч
1
0
r2
r1
R=D
1
r0
1
r3
1
0
r2
r1
R=C
m0
0
0
r0
Циклічний зсув ліворуч
Арифметичний зсув ліворуч
m3
0
M=6
m2 m1
1
1
m0
0
1
r3
0
r2
1
r0
Ci=1
1
r1
R=B
M=6
m2 m1
1
1
M=6
m2 m1
1
1
Co=0
Логічний зсув праворуч
m3
0
M=6
m2 m1
1
1
m0
0
0
r3
0
r2
1
r0
1
r1
R=3
m3
0
M=6
m2 m1
1
1
m0
0
0
r3
0
r2
1
r0
Co=0
1
r1
R=3
Циклічний зсув праворуч
Арифметичний зсув праворуч
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
330

331. Двійковий суматор з наскрізним (послідовним) переносом

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
331

332. Повний однорозрядний двійковий суматор

Co ABC i ABCi ABCi ABCi BC i ACi AB
S A BCi ABCi AB Ci ABCi
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
332

333. Суматор з паралельним переносом

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
333

334. Суматор з паралельним переносом

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
334

335. 4-бітний суматор із схемою прискореного переносу

PG P0 P1 P2 P3
GG C3 C2 P3 C1 P2 P3 C0 P1 P2 P3
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
335

336. 16-бітний суматор із схемою прискореного переносу

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
336

337. 64-бітний суматор із схемою прискореного переносу

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
337

338. Двійкові суматори

• Суматор з паралельним переносом (1 вузол
прискорення переносу)
• Суматор з послідовним (наскрізним)
переносом (немає вузлів прискорення
переносу)
• Суматор з груповим переносом (декілька
вузлів прискорення переносу)
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
338

339. Паралельний матричний помножувач на комірках Гілда

x 1 1 0 1 =1310 - множене
1 1 0 1 =1310 - множник
1101
+
часткові
0
000
+
101
добутки
+11
101
1 0 1 0 1 0 0 1 =A916=16910 - добуток
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
339

340. Паралельний матричний помножувач на комірках Гілда

x 1 1 0 1 =1310 - множене
1 1 0 1 =1310 - множник
1101
+
часткові
0
000
+
1
1
0
1
добутки
+1101
1 0 1 0 1 0 0 1 =A916=16910 - добуток
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
340

341. Матричний (паралельний, комбінаційний) помножувач

x 1 1 0 1 =1310 - множене
1 1 0 1 =1310 - множник
0000
+1101
1101
1101
+ 0000
01101
+ 01101
1101
1000001
+1000001
1101
1 0 1 0 1 0 0 1 =A916=16910
- добуток
sk aj bi ck
&
Комірка Гілда
A
Co
B
Σ
ck+1
НУЛП 20162017 н.р.
Ci
S
sk+1
Глухов В.С. Комп'ютерна логіка
341

342. Арифметико-логічний пристрій

A
B
A
B
Fмл
F
MUX
AU
R
LU
A
A
B
R
B
Fмл
F
A
Fмл
A
B
Fмл
Fст
НУЛП 20162017 н.р.
A
Ra
Rл
0
A
B
F
A
B
F
ALU
R
R
1
R
ShU
R
Rз
2
F
Reserve
A
R
B
F
Код операції -КОП
Rр
3
Sel
Fст
00 - арифметичні
01 - логічні
10 - зсуви
11 - резерв
Глухов В.С. Комп'ютерна логіка
Fмл
342

343. Арифметичний вузол

00...0
A
11...1
F4F3
Код операції - арифметичні
Fст
00 - арифметичні
F4F3
01
01
01
00
01
11
00
11
F2F1
01
10
00
01
11
01
00
00
F0
0
1
1
1
0
0
0
0
(Fмл)
(0A)
(0D)
(09)
(03)
(0E)
(1A)
(00)
(18)
A+B+0 =
A+(not B) +1 =
A+0+1=
0+B+1=
A+11...1+0=
11...1+B+0=
0+0+0=
11...1+0+0=
A+B
A-B
A+1
B+1
A-1
B-1
0
11...1
1
MUX
0
1
R
2
3
Sel
1
MUX
0
1
R
2
3
Sel
00...0
B
11...1
F2F1
F0
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
SUM
OpA
OpB
A
B
Ci
S
Co
Ra
Co
343

344. Логічний вузол

A
B
A
B
A
B
A
B
MUX
&
R
RAND
0
1
R
ROR
1
Rл
A
B
A
B
Fмл
НУЛП 20162017 н.р.
A
B
A
B
=1
R
RXOR
2
==
R
REQ
3
Sel
Глухов В.С. Комп'ютерна логіка
344

345. Вузол зсувів

A
A
A
A
A
A
A
LSL
RL
ASL
LSR
RR
ASR
R
0
R
1
R
2
R
3
R
4
R
5
MUX
Rз
6
7
Fмл
НУЛП 20162017 н.р.
Sel
Глухов В.С. Комп'ютерна логіка
345

346. Структура комп’ютера

Пам'ять
Пристрій
вводу
Пристрій
керування
Пристрій
виводу
Операційний
пристрій
Процесор
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
Дані
Стан
Керування
Команда
346

347. Загальна структурна схема цифрового автомата

КСх
ПА
δ
{X}
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
НУЛП 20162017 н.р.
λ
{A}
{Y}
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Глухов В.С. Комп'ютерна логіка
347

348. Структурна схема автомата Мура

i
КСх
ПА
δ
{X} j
i
{A}
КСх
λ
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
j – кількість вхідних сигналів
k – кількість вихідних сигналів
НУЛП 20162017 н.р.
k
{Y}
2
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
i – розрядність зворотного зв’язку,
кількість тригерів у пам’яті
автомата
Глухов В.С. Комп'ютерна логіка
348

349. Структурна схема автомата Мілі

КСх
{X}
δ
ПА
{A}
КСх
λ
1
{Y}
2
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
НУЛП 20162017 н.р.
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Глухов В.С. Комп'ютерна логіка
349

350. Часові функції алгебри логіки

Для опису роботи елементів пам’яти крім
ФАЛ потрібно мати хоча би одну функцію,
яка змінює час
• ЧФАЛ 1-го роду
• ЧФАЛ 2-го роду
• ЧФАЛ 3-го роду
Функціонально-повна система часових
функцій алгебри логіки = ФПЧ ФАЛ +
функція, що змінює час
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
350

351. Елемент затримки

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
351

352. Часові ФАЛ 1-, 2- та 3-го роду

a, b, c, ...
F
Y=f(a,b,c,…,t)) Часові ФАЛ 1-го роду, t - час
t
а
at, bt, ct, ...
F
at-1, bt-1, ct-1, ...
Y=f(at,bt,ct,…,at-1,bt-1,ct-1,…))
Часові ФАЛ 2-го роду
б
at, bt, ct, ...
F
Yt-1
Yt=f(at,bt,ct,…,Yt-1)
Часові ФАЛ 3-го роду
в
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
352

353. Часова функція 3-го роду Зворотній зв’язок (техн) Змія, що кусає себе за хвіст – Уроборос (філ.)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
353

354. Загальна схема тригера (trigger, flip-flop, latch)

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
354

355. Тригер та генератор

• Тригер – логічний елемент, що може знаходитися у двох сталих
станах та переходити з одного стану в інший під дією зовнішніх
сигналів = елемент пам’яті для збереження 1 біта.
• Генератор - логічний елемент, що може знаходитися у двох
станах та переходити з одного стану в інший без дії зовнішніх
сигналів
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
355

356. Класифікація тригерів

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
356

357. RS-тригер

№
0
1
2
3
R
0
0
1
1
S
0
1
0
1
Qt
Qt-1
1
0
Заборона
S
RS-тригер
a0
0
R S
RS
a1
1
R
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
357

358. неRнеS-тригер

№
0
1
2
3
R
0
0
1
1
S
0
1
0
1
НУЛП 20162017 н.р.
Qt
Заборона
0
1
Qt-1
Глухов В.С. Комп'ютерна логіка
358

359. Класифікація синхронних тригерів

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
359

360. Синхронний RS-тригер

S
a0
0
R S
RS
a1
1
R
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
360

361. D-тригер, що спрацьовує по тілу

№
0
1
C
0
1
Qt
Qt-1
D
D
a0
0
D
D
a1
1
D
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
361

362. D-тригер, що спрацьовує по фронту

№
0
1
2
3
C
0
1
Qt
Qt-1
Qt-1
Qt-1
D
D
a0
0
D
D
a1
1
D
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
362

363. Двоступеневий тригер

• Ведучий-ведений
• Master-Slave
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
363

364. Функціональна схема D-тригера, що спрацьовує по фронту

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
364

365. Т-тригер

№
0
1
2
3
C
0
1
НУЛП 20162017 н.р.
a0
0
Qt
Qt-1
Qt-1
Qt-1
a1
1
Q t 1
Глухов В.С. Комп'ютерна логіка
365

366. T-тригер з входом дозволу роботи

№
0
1
2
3
4
C
0
1
X
НУЛП 20162017 н.р.
CE
X
X
X
0
1
Qt
Qt-1
Qt-1
Qt-1
Qt-1
CE
a0
0
CE
CE
a1
1
CE
Q t 1
Глухов В.С. Комп'ютерна логіка
366

367. JK-тригер

№
0
1
2
3
4
5
6
C
0
1
НУЛП 20162017 н.р.
J
X
X
X
0
0
1
1
K
X
X
X
0
1
0
1
Qt
Qt-1
Qt-1
Qt-1
Qt-1
0
1
J
a0
0
J
K
a1
1
K
Q t 1
Глухов В.С. Комп'ютерна логіка
367

368. Перетворення тригерів

• D -> T
• JK -> T
• JK -> D
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
368

369. Тригери з асинхронними входами (R, S) та входом дозволу СІ (CE)

S
D
C
CE
R
T
R
0
1
1
0
0
0
0
S
1
0
1
0
0
0
0
0 0
НУЛП 20162017 н.р.
CE
X
X
X
0
1
1
1
C
X
X
X
X
0
1
↓
Qt
1
0
X
Qt-1
Qt-1
Qt-1
Qt-1
1
↑
D
Працюють
асинхронні входи
Заборона
Немає дозволу
Немає потрібного
фронту СІ
Запис даних по
фронту СІ
Глухов В.С. Комп'ютерна логіка
369

370. Лічильник на T-тригерах

a0
000
a7
111
a1
001
a2
010
a6
110
a5
101
a3
011
a4
100
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
370

371. Лічильник на D-тригерах

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
371

372. Лічильник на JK-тригерах

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
372

373. Класифікація регістрів

• За функціональним призначенням
– регістри зсуву
– Регістри для збереження інформації (паралельні)
• За типом тригерів
• За організацією зсуву
– Ліворуч, праворуч, універсальні
• За способом прийому і видачі даних при зсуві (вхід/вихід)
–
–
–
–
НУЛП 20162017 н.р.
Послідовний/послідовний
Послідовний/паралельний
Паралельний/послідовний
Паралельний/паралельний
Глухов В.С. Комп'ютерна логіка
373

374. Регістр зсуву

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
374

375. SerDeS

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
375

376. Паралельний регістр

D0
D
C
D1
D
C
D2
D
C
D3
C
НУЛП 20162017 н.р.
D
C
T
RG
Q0
D1
T
Q1
D2
T
Q2
D0
D1
D2
D3
C
Q0
Q1
Q2
Q3
RG
D3
T
D(3:0) Q(3:0)
Q3
C
D4
Глухов В.С. Комп'ютерна логіка
376

377. Оперативний запам’ятовуючий пристрій (ОЗП)

DI
A
m
n
Wr
DC
B
CS
Q
CS0
D
C
CS1
D
C
n
CS 2
RG
RG
Q
Q
Word0
Word1
0
MUX
m
1
DO
RAM
m
CS2^n-1
D
C
RG
2n-1
Q
n
m
DI
Wr
A
DO
n
Sel
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
377

378. Ієрархія пам’яті

n
m
A
RAM
m
DI
DO
WR
RD
OE
CS
Основні кількісні характеристики ОЗП:
кількість слів N = 2n;
об’єм пам’яті V = N * m = 2n * m біт.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
378

379. Регістровий файл

DI
AW
m
n
DC
B
CS
Wr
Q
CS0
D
C
CS1
D
C
CS2^n-1
D
C
n
CS 2
RG
RG
RG
Q
Q
Q
Word0
Word0
Word1
Word1
m DOA
1
Word2^n-1
Word2^n-1
2n-1
Sel
Word0
m
n
n
n
НУЛП 20162017 н.р.
MUX
n
AA
AB
0
RG
File
DI
Wr
AW
AA
DOA
AB
DOB
Word1
0
MUX
1
m DOB
m
m
Word2^n-1
2n-1
n
Sel
Глухов В.С. Комп'ютерна логіка
379

380. Операційний пристрій = ALU+RG File

A
In
Sel
MUX
0
1
Sel
R
m A
B
НУЛП 20162017 н.р.
RG
File
ALU
R
F
Wr
AW
AA
AB
A
R m
F Sel Wr AA AB AW
КОП
DI
F
B
AA AB AW
(AA)*(AB)=>(AW)
In=>(AW)
n
n
n
Wr
AW
AA
AB
DOA
DOB
m
m
Out
Глухов В.С. Комп'ютерна логіка
380

381. Структура комп’ютера

Пам'ять
Пристрій
вводу
Пристрій
керування
Пристрій
виводу
Операційний
пристрій
Процесор
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
Дані
Стан
Керування
Команда
381

382. Логічна комірка

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
382

383. Конфігуровна логічна комірка

DconfO
Комбінаційних вихід
0
RG
C
D
Cconf
НУЛП 20162017 н.р.
DconfI
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 MUX
1
2
3
4
5
6
7
8
9
10
11
MUX
f
Регістровий
вихід
T
C
D
C
Contr
1
1
D2
12
13
14
d
c
b
a
15
1
2
4
8
Глухов В.С. Комп'ютерна логіка
383

384. Логічні комірки в складі Slice

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
384

385. ПЛІС першого покоління

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
385

386. Організація перших ПЛІС

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
386

387. Конфігуровані логічні блоки (CLB) та електронні комутатори (PSM -Programmable switch matrix )

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
387

388. Електронний комутатор

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
388

389. Електронний перемикач

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
389

390. Структура комп’ютера

Пам'ять
Пристрій
вводу
Пристрій
керування
Пристрій
виводу
Операційний
пристрій
Процесор
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
Дані
Стан
Керування
Команда
390

391. Загальна схема цифрового автомата

КСх
ПА
δ
{X}
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
НУЛП 20162017 н.р.
λ
{A}
{Y}
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Глухов В.С. Комп'ютерна логіка
391

392. Cхема автомата Мура

i
КСх
ПА
δ
{X} j
i
{A}
КСх
λ
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
j – кількість вхідних сигналів
k – кількість вихідних сигналів
НУЛП 20162017 н.р.
k
{Y}
2
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
i – розрядність зворотного зв’язку,
кількість тригерів у пам’яті
автомата
Глухов В.С. Комп'ютерна логіка
392

393. Схема автомата Мілі

КСх
{X}
δ
ПА
{A}
КСх
λ
1
{Y}
2
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
НУЛП 20162017 н.р.
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Глухов В.С. Комп'ютерна логіка
393

394. Рекомендована послідовність синтезу цифрових автоматів

•Синтез абстрактного автомата (результат – абстрактний автомат)
• Синтез алгоритму роботи автомата.
• Вибір структури автомата (Мура або Мілі).
• Фіксація алгоритму у вигляді графа.
•Синтез структурного автомата (результат – структурний автомат)
• Вибір елементної бази комбінаційної частини.
• Вибір елементної бази пам’яті автомата.
• Вибір способу кодування вхідних та вихідних сигналів.
• Вибір способу кодування внутрішніх станів автомата.
• Створення таблиці переходів автомата.
• Створення таблиці виходів автомата.
• Мінімізація формул для сигналів збудження тригерів автомата. Фіксація
результатів у вигляді диз’юнктивної нормальної форми (ДНФ).
• Для деяких структурних автоматів (у яких комбінаційна частина реалізується
на дешифраторах, мультиплексорах, а також для мікропрограмних автоматів, у
яких комбінаційна частина реалізується на ПЗП) даний етап мінімізації
непотрібний.
• Мінімізація формул для виходів автомата. Фіксація результатів у вигляді
диз’юнктивної нормальної форми (ДНФ).
• Для деяких структурних автоматів (у яких комбінаційна частина реалізується
на дешифраторах, мультиплексорах, а також для мікропрограмних автоматів, у
яких комбінаційна частина реалізується на ПЗП) даний етап мінімізації
непотрібний.
• Синтез пам’яті автомата.
• Синтез комбінаційної частини автомата.
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
394

395. Кодуванням станів автомата: двійкове, сусіднє, унітарне

i
i
КСх
ПА
δ
{X} j
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
j – кількість вхідних сигналів
k – кількість вихідних сигналів
КСх
КСх
i
{A}
λ
{Y}
k
ПА
δ
{X} j
i
КСх
{A}
2
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
i – розрядність зворотного зв’язку,
кількість тригерів у пам’яті
автомата
k
λ
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
j – кількість вхідних сигналів
k – кількість вихідних сигналів
{Y}
2
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
i – розрядність зворотного зв’язку,
кількість тригерів у пам’яті
автомата
Кількість тригерів залежить тільки від
кількості станів і способу їх кодування
№
0
1
2
...
8
9
Позначення
ai
a0
a1
a2
НУЛП 20162017 н.р.
Стан автомата
Унітарний код
Q9 Q8
Q2 Q1
...
0
0
0
0
...
0
0
0
1
...
0
0
1
0
...
...
...
a8
a9
0
1
...
1
0
...
...
...
...
0
0
...
0
0
№
Q0
1
0
0
...
0
0
0
1
2
...
8
9
Стан автомата
Позначення
Двійковий код
ai
Q3 Q2 Q1 Q0
0
0
0
0
a0
0
0
0
1
a1
a2
0
0
1
0
...
...
a8
a9
1
1
Глухов В.С. Комп'ютерна логіка
...
0
0
...
0
0
...
0
1
395

396. Перехід від блок-схеми алгоритму до графа автомата Мура

a0
Початок
a0
Початок
a1
Лч:=n
y0
S := 0
Мол. р. Мк
y0
a1
0
1
1
a2
x0
a3
S := АЗП(S)
Мк:=ЛЗП(Мк)
a4
0
x0
S:=S+Ме
y3
y1
x0 x1
x0
y2
x0 x1
Лч:=Лч-1
Лч=0?
1
S:=S-Ме
0
1
1
Мол. р. Мк
0
0
x1
a4
y3
x0 x1
1
a2
x0
0
y1
a3
y2
x0 x1
Кінець
НУЛП 20162017 н.р.
a0
Кінець
Глухов В.С. Комп'ютерна логіка
396

397. Перехід від блок-схеми алгоритму до графа автомата Мілі

Початок
y0
Початок
a0
a0
Лч:=n
y0
S := 0
Мол. р. Мк
a1
0
0
x0
1
y1
Мк:=ЛЗП(Мк)
y1
S:=S-Ме
a3
x1
0
1
1
Мол. р. Мк
0
y0
y2
a2
Лч:=Лч-1
1
x0 x1
x0
S := АЗП(S)
Лч=0?
x0
y2
1
S:=S+Ме
a1
x0 x1
y3
0
x0 x1
1
a2
x0
0
y3
a3
y2
y2
x0 x1
a0
Кінець
НУЛП 20162017 н.р.
Кінець
Глухов В.С. Комп'ютерна логіка
397

398. Збудження тригерів

D
Сигнали збудження тригерів
Щоб змінити
Щоб перевести
Щоб перевести
стан (з 0 до 1 або
тригер до стану 0 тригер до стану 1
з 1 до 0)
D
a0
0
T
D=0
C
J
D
D=1
T
K=1
C
K
D
a1
1
J
D
a0
0
J
J=1
a1
1
CE
CE
C
K
a0
0
T
CE=1
CE
K
CE
a1
1
CE
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
398

399. Синтез автомата Мура

i
Синтез автомата Мура
КСх
КСх
ПА
δ
{X} j
{A}
i
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
j – кількість вхідних сигналів
k – кількість вихідних сигналів
№
№
0
1
2
3
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
0
0
a0
0
1
a1
1
0
a2
1
1
a3
Вихідні
сигнали
автомата
y
1
1
0
0
0
1
2
3
4
5
6
7
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
a0
0
0
a0
0
0
0
1
a1
0
1
a1
1
0
a2
1
0
a2
a3
1
1
1
1
a3
0
Q1
4
1
1
5
3
1
7
1
2
{Y}
k
2
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
i – розрядність зворотного зв’язку,
кількість тригерів у пам’яті
автомата
Наступний стан
автомата
Позначення
Код
aj
q1
q0
a1
0
1
a0
0
0
1
0
a2
1
0
a2
1
1
a3
1
1
a3
a0
0
0
0
0
a0
x
0
1
0
1
0
1
0
1
Q0
Сигнали
збудження
тригерів
D1
D0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
0
Q0
0
1
6
x
D1 Q1Q0 Q1Q0
НУЛП 20162017 н.р.
λ
Q1
4
1
1
1
5
1
3
2
7
6
x
D0 Q1Q0 Q0 x
Глухов В.С. Комп'ютерна логіка
Q0
0
Q1
2
1
1
1
3
y Q1
399

400. Результат синтезу – схема автомата Мура

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
400

401. Сусіднє кодування станів

КСх
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
№
0
1
2
3
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
0
0
a0
0
1
a1
1
0
a3
1
1
a2
Вихідні
сигнали
автомата
y
0
1
1
0
0
1
2
3
4
5
6
7
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
a0
0
0
a0
0
0
0
1
a1
0
1
a1
1
0
a3
1
0
a3
a2
1
1
1
1
a2
0
1
3
4
5
7
1
2
6
{Y}
λ
2
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
x
0
1
0
1
0
1
0
1
Наступний стан
автомата
Позначення
Код
aj
q1
q0
a1
0
1
a1
0
1
1
1
a2
1
1
a2
0
0
a0
0
0
a0
a3
1
0
0
0
a0
Q0
Q1
НУЛП 20162017 н.р.
{A}
δ
{X}
№
КСх
ПА
Q0
0
1
1
x
D1 Q0 x Q1Q0
Q1
4
1
1
3
1
5
7
1
2
6
Сигнали
збудеження
тригерів
D1
D0
0
1
0
1
1
1
1
1
0
0
0
0
1
0
0
0
Q0
0
1
Q1
2
1
1
1
3
x
D0 Q1
Глухов В.С. Комп'ютерна логіка
y Q1Q0 Q1Q0
401

402. Схема автомата

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
402

403. Унітарне кодування станів

КСх
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Попередній стан автомата
Позначення
ai
a0
a1
a2
a3
Попередній стан автомата
D3 Q2 x
D2 Q1
D1 Q0
D0 Q3 Q2 x
y Q3 Q1
НУЛП 20162017 н.р.
№
0
1
2
3
4
5
6
7
Позначення
ai
a0
a0
a1
a1
a2
a2
a3
a3
Q3
0
0
0
0
0
0
1
1
Код
Q2 Q1
0
0
0
0
0
1
0
1
1
0
1
0
0
0
0
0
Q3
0
0
0
1
{Y}
λ
2
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
0
1
2
3
{A}
δ
{X}
№
КСх
ПА
Код
Q2 Q1
0
0
0
1
1
0
0
0
Q0
1
0
0
0
Вихідні
сигнали
автомата
y
0
1
0
1
Наступний стан автомата
x
Q0
1
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
Позначення
aj
a1
a1
a2
a2
a3
a0
a0
a0
Глухов В.С. Комп'ютерна логіка
q3
0
0
0
0
1
0
0
0
Код
q2
q1
0
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
q0
0
0
0
0
0
1
1
1
D3
0
0
0
0
1
0
0
0
Сигнали
збудеження
тригерів
D2 D1
0
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
D0
0
0
0
0
0
1
1
1
403

404. Схема автомата

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
404

405. Автомат на Т-тригерах

КСх
ПА
δ
{X}
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
№
0
1
2
3
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
0
0
a0
0
1
a1
1
0
a2
1
1
a3
0
1
2
3
4
5
6
7
Вихідні
сигнали
автомата
y
1
1
0
0
Q0
0
Q1
НУЛП 20162017 н.р.
4
1
1
1
3
5
7
1
1
1
2
6
1
x
CE0 Q1 Q0 x
Q1
0
1
3
4
5
7
x
CE1 Q0
1
1
2
6
{Y}
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Наступний стан
автомата
Позначення
Код
aj
q1
q0
a1
0
1
a0
0
0
1
0
a2
1
0
a2
1
1
a3
1
1
a3
a0
0
0
0
0
a0
x
0
1
0
1
0
1
0
1
Q0
1
λ
2
Попередній стан
автомата
Позначення
Кодt
ai
Q1 Q0
a0
0
0
a0
0
0
0
1
a1
0
1
a1
1
0
a2
1
0
a2
a3
1
1
1
1
a3
№
КСх
{A}
Сигнали
збудеження
тригерів
CE1
CE0
0
1
0
0
1
1
1
1
0
1
0
1
1
1
1
1
Q0
0
1
1
Q1
2
1
1
1
3
y Q1
Глухов В.С. Комп'ютерна логіка
405

406. Схема автомата

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
406

407. Автомат на JK-тригерах

КСх
ПА
δ
{X}
1
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
№
№
0
1
2
3
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
0
0
a0
0
1
a1
1
0
a2
1
1
a3
Вихідні
сигнали
автомата
y
1
1
0
0
0
1
2
3
4
5
6
7
Q0
Q1
0
1
3
4
5
7
X
X
1
X
Q0
2
6
1
X
1
3
2
0
4
5
7
6
4
X
Q1
X
НУЛП 20162017 н.р.
X
x
K 1 Q0
1
x
0
1
0
1
0
1
0
1
X
1
Q1
1
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
Наступний стан
автомата
Позначення
Код
aj
q1
q0
a1
0
1
a0
0
0
1
0
a2
1
0
a2
1
1
a3
1
1
a3
a0
0
0
0
0
a0
1
3
2
0
1
3
5
7
6
4
5
7
1
x
J 0 Q1 x
1
Сигнали збудеження
тригерів
J1
0
0
1
1
X
X
X
X
Q0
1
X
X
1
X
Q1
X
{Y}
λ
2
Q0
0
x
J 1 Q0
Попередній стан
автомата
Позначення
Кодt
ai
Q1 Q0
a0
0
0
a0
0
0
0
1
a1
0
1
a1
1
0
a2
1
0
a2
a3
1
1
1
1
a3
КСх
{A}
X
X
K0 1
1
X
K1
X
X
X
X
0
0
1
1
J0
1
0
X
X
1
1
1
1
K0
X
X
1
1
X
X
X
X
Q0
2
6
0
1
X
Q1
2
1
1
1
3
x
Глухов В.С. Комп'ютерна логіка
y Q1
407

408. Схема автомата

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
408

409. Синтез автомата Мілі

№
КСх
{X}
δ
ПА
{A}
КСх
λ
1
{Y}
0
1
2
3
4
5
6
7
Попередній стан
автомата
Позначення
Код
ai
Q1 Q0
a0
0
0
a0
0
0
0
1
a1
0
1
a1
1
0
a2
1
0
a2
a3
1
1
1
1
a3
Наступний стан
автомата
Позначення
Код
aj
q1
q0
a1
0
1
a0
0
0
1
0
a2
1
0
a2
1
1
a3
1
1
a3
a0
0
0
0
0
a0
x
0
1
0
1
0
1
0
1
Сигнали
збудеження
тригерів
D1
D0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
0
y
1
1
0
0
0
0
1
1
2
КСх - комбінаційна схема
ПА - пам’ять автомата
δ – функція переходів
λ – функція виходів
Q0
{X} – множина вхідних сигналів
{Y} – множина вихідних сигналів
{A} – множина внутришніх станів
0
Q1
4
1
1
5
3
1
7
1
2
Q0
6
x
D1 Q1Q0 Q1Q0
НУЛП 20162017 н.р.
0
1
Q1
4
1
1
1
5
1
3
2
7
6
x
D0 Q1Q0 Q0 x
Глухов В.С. Комп'ютерна логіка
Q0
0
Q1
4
1
1
5
1
3
7
2
1
6
1
x
y Q1Q0 Q1Q0
409

410. Схема автомата

НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
410

411. Мікропрограмний автомат

ROM
ПА
δ
{X}
{A}
{Y}
λ
ROM - комбінаційна схема мікропрограмного автомата - постійний
запам’ятовуючий пристрій
{X} – множина вхідних сигналів
ПА - пам’ять автомата
δ – функція переходів
{Y} – множина вихідних сигналів
λ – функція виходів
{A} – множина внутришніх станів
A
(адреса №10
ПЗП)
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
НУЛП 20162017 н.р.
Попередній стан
автомата
Код
Позначення
Q1 Q0
ai
A2 A1
a0
0
0
a0
0
0
0
1
a1
0
1
a1
1
0
a2
a2
1
0
a3
1
1
1
1
a3
x
y
A0
0
1
0
1
0
1
0
1
D2
1
1
1
1
0
0
0
0
Сигнали
збудеження
тригерів
D1
D0
D1
D0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
0
Наступний
стан
автомата
aj
a1
a0
a2
a2
a3
a3
a0
a0
D
(дані
ПЗП)
5
4
6
6
3
3
0
0
Глухов В.С. Комп'ютерна логіка
411