Лекція 1
Розклад викладача, консультації – Пн, Чт після 2-ої пари, 503-V (каф. ЕОМ)
Комп’ютерна логіка
Національний університет “Львівська політехніка”
Комп'ютерних технологій, автоматики та метрології
Кафедри ЕОМ та СКС
Структура семестру
Державна оцінка (залік)
Стандартні вимоги до відповідей на заліках та іспитах
Виконання навчального плану
Полегшені умови отримання семестрової оцінки
Оцінювання відповідей при стандартному підході
Покращення оцінок
Методичні вказівки до курсової роботи “Арифметичні та логічні основи комп’ютерних технологій” з дисципліни "Комп’ютерна логіка"
Методичні вказівки до курсової роботи “Арифметичні та логічні основи комп’ютерних технологій” з дисципліни "Комп’ютерна логіка"
Робочий журнал
Відробка пропущених лекційних контрольних робіт
Віртуальне Навчальне Середовище - ВНС
Тема у ВНС
Білет семестрової контрольної роботи
Конспект
Навички (компетенції) випускників
Навички (компетенції) випускників
Навички (компетенції) випускників
Навички (компетенції) випускників
Навички (компетенції) випускників
Навички (компетенції) випускників
Навички (компетенції) випускників
Навички (компетенції) випускників
Навички (компетенції) випускників
Навички (компетенції) випускників
Спеціальні навички (компетенції) випускників
Спеціальні навички (компетенції) випускників
Застосування придбаних навичок в проектуванні.
Вбудовані ЕОМ
Комірки
(Львівський центр Інституту космічних досліджень НАН та ДКА України) Супутник Січ-2 на етапі відлагодження та тестування
Блоки і комірки для Січ-2 (Львівський центр Інституту космічних досліджень НАН та ДКА України)
Вбудована в атомну елекростанцію комп’ютерна система (НВО “Радій”, м. Кіровоград, 2010 р.)
У Львові 150 IT-компаній (Інформаційні Технології) 25 найбільших IT-компаній України http://jobs.dou.ua/top25/
Комп’ютерна логіка і „Комп’ютерна інженерія”
Лінгвістичні основи – грецька абетка
Лінгвістичні основи – латинська абетка
Математичні основи Просте число — це натуральне число, яке має рівно два різних натуральних дільники (лише 1 і саме число).
Таблиця множення
Математичні основи
Математичні основи
Математичні основи – математичні константи
Математичні основи – модульна арифметика
Системи числення
Позиційні системи числення
Степені 2
Фізичні основи
Основи електроніки
Швидкість, продуктивність
Філософські основи
Матерія
Відображення
Інформація
Стандарти AAAA NNNN-Ч:YYYY
Властивості інформації
Комп’ютерна логіка у системі наук інформаційної сфери
Структурна схема процесу передачі або оброблення інформації
Кодек, Модем
Баланс швидкостей
Функції кодера джерела інформації
Дані
Кодування
Сигнал та повідомлення
АЦП та ЦАП (ADC and DAC)
Порівняння аналогових та цифрових методів обробки інформації
Найпоширеніший аналоговий обчислювач (комп’ютер, помножувач)
Дискретизація та квантування
Дискретиза́ція
Квантування
Дискретизація та квантування
Дискретизація (у часі)
Квантування за рівнем
Дискретизація за часом і квантування за рівнем
Теорема Котельнікова – як часто треба вимірювати сигнал?
Переваги кодування двома символами
Варіанти представлення бітів інформації на фізичному рівні (варіанти сигналів)
Параметри імпульсу
Характеристики імпульса
Дані
Числа з фіксованою комою
Порядок байтів
Числа з рухомою комою. Стандарт IEEE-754
Кодова таблиця КОИ-7
Кодова таблиця KOI-8U
Кодові таблиці:
Структура кодів UTF-8 (Unicode Transformation Formats )
Кодування зображень. Матричні та векторні формати
Кодування відтінків кольору
Кількість кольорів
Формати аудіфайлів
Міри інформації
Структурні міри інформації
1.3 Структурні комбінаторні міри
Структурні комбінаторні міри
Структурні комбінаторні міри
Структурні комбінаторні міри
Структурні комбінаторні міри
1.4 Міра Хартлі, США, 1928 р. (Ральф Хартлі)
Похідні одиниці кількості інформації
2. Семантична міра (за значенням)
Семантична міра
Семантична міра
Семантична міра
Семантична міра
Семантична міра
Семантична міра
3. Статистична міра, Клод Шеннон, 1948, США
Ентропія джерела повідомлення – характеризує здатність джерела віддавати інформацію
Властивості ентропії
Залежність ентропії двох подій від їх імовірності
Кількість отриманої інформації
Усунення надлишковості інформації. Алгоритм ефективного кодування Шеннона – Фано
Абетка Морзе
Послідовний та паралельний спосіб передачі інформації
Способи оброблення даних
Послідовний та паралельний способи опрацювання даних
Опрацювання даних з використанням зворотних зв’язків
Опрацювання даних в ієрархічних структурах
Кодер захисту інформації
Загальна схема криптографічної системи
Перемішування
Контроль на парність / непарність
Код Хеммінга
Код Хеммінга
Контроль виконання операцій. Числовий контроль за модулем
SerDes
Строб (вказівник, спрацьовувати)
Кодер захисту інформації
Позиційні системи числення
Двійково-десяткові коди
Двійково-десяткові коди
Трійкова симетрична (врівноважена) система числення
Системи числення з іраціональними основами Класичний CORDIC-метод обчислення тригонометричних ф-цій Coordinate Rotation Digital Computer метод Дж. Волдера
Система залишкових класів
Поля Галуа
Сусідній код (код Грея)
Сусідні коди
Карти Карно
Скручування карти Карно по вертикалі
Структурна схема процесу передачі або оброблення інформації
Семисегментний індикатор
Алгоритм
Характеристики алгоритму
Властивості алгоритму
Представлення алгоритмів http://uk.wikipedia.org/wiki/Алгоритм
Блок-схема алгоритму
Граф автомата Мура та позначки у вершинах графа з двійковим кодуванням станів
Граф автомата
Блок-схема алгоритму та граф автомата
Таблиці переходів та виходів автомата Мура
Функціональна схема автомата Мура
Часова діаграма роботи автомата Мура
Опис автомата формальною (з правилами без винятків) або неформальною (з правилами та винятками з них) мовами
Теза Черча 
Універсальні ФАС – можуть реалізувати будь-який алгоритм
Повна побудова алгоритму
Загальна структурна схема цифрового автомата
Структурна схема автомата Мура
Структурна схема автомата Мілі
Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра)
Змінні, набори і функції алгебри логіки – для опису комбінаційних схем цифрових автоматів
ФАЛ0, ФАЛ1
Повторювач, інвертор
Функції алгебри логіки двох змінних
Кон'юнкція (від латинського conjunctio – сполучник, зв'язок), логічне множення або функція І (И, AND)
Диз'юнкція (від латинського disjunctio - роз'єднання), логічне додавання або функція АБО (ИЛИ, OR)
Функція (штрих) Шеффера або функція І-НЕ (NOT AND, NAND, И-НЕ)
Функція (стрілка) Пірса (Вебба) або функція АБО-НЕ (ИЛИ-НЕ, NOT OR, NOR)
Виключне АБО (XOR)
Рівнозначність (еквівалентність)
Імплікація (пряма)
Імплікація зворотна
Заперечення імплікації (прямої)
Теорема Поста-Яблонського про функціонально повні системи (ФПС, базиси)
Властивості ФАЛ, монобазиси, базиси
Деякі ФАЛ3
Сингулярні таблиці
Базис Буля
Кон'юнкція (від латинського conjunctio – сполучник, зв'язок), логічне множення або функція І (И, AND)
Диз'юнкція (від латинського disjunctio - роз'єднання), логічне додавання або функція АБО (ИЛИ, OR)
Повторювач, інвертор
Аналітичне представлення функцій алгебри логіки Досконалі нормальні форми
Синтез логічних схем з одним виходом у базисі Буля на елементах з довільною кількістю входів
Використання базису з 2-х ФАЛ: (І, НЕ)
Використання базису з 2-х ФАЛ: (АБО, НЕ)
Основні правила виконання операцій у базисі Буля
Мінімізація ФАЛ
Методи розв’язання канонічної задачі мінімізації
Двовходові елементи базису Буля
Основні правила виконання операцій у монобазисах І-НЕ (Шеффера) та АБО-НЕ (Пірса)
Монобазис І-НЕ (NAND)
Синтез логічних схем з одним виходом у монобазисі І‑НЕ
2І-НЕ
Синтез логічних схем з одним виходом у монобазисі 2І-НЕ (Шеффера)
Монобазис АБО‑НЕ (NOR)
Синтез логічних схем з одним виходом у монобазисі АБО‑НЕ
2АБО-НЕ
Синтез логічних схем з одним виходом у монобазисі 2АБО-НЕ (Пірса)
Схеми елементів монобазисів на КМОН-транзисторах
Основні правила виконання операцій у базисі Жегалкіна
Виключне АБО (XOR)
Реалізація XOR
Порівняння варіантів синтезу комбінаційних логічних схем
ДНФ
КНФ
Поліном Жегалкіна
Небулеві базиси
Порогові функції
Форми представлення ФАЛ
Геометричний спосіб представлення ФАЛ
Аналітичні форми представлення ФАЛ
Терм
Нормальні форми з мінтермами
Нормальні форми з макстермами
Досконалі нормальні форми
Анормальні форми
Критерії синтезу схем ФАЛ
Методи визначення ціни реалізації ФАЛ
Мінімізація ФАЛ
Методи розв’язання канонічної задачі мінімізації
Методи розв’язання загальної задачі мінімізації (аналітичні)
Еврістичний
Винесення за дужки
Метод функціональної декомпозиції проста розділова і загальний випадок
Багаторозрядний суматор
4-розрядні суматори (у прямому, оберненому і доповняльному кодах)
Повний однорозрядний двійковий суматор
Функціональна схема повного однорозрядного двійкового суматора
Повний однорозрядний двійковий суматор (матрична схема)
Двійкові однорозрядні напівсуматор (а) та повний суматор (б)
Багатозначні логіки. Нечітка логіка
Виконання навчального плану
Державна оцінка (іспит)
Стандартні вимоги до відповідей на іспиті
Полегшені умови до іспитів, комісії та повторки
Оцінювання відповідей при стандартному підході
Оцінювання відповідей на іспиті при полегшеному підході
Покращення оцінок
Відпрацювання пропущених лекційних контрольних робіт
Курсова робота
Використання результатів 2-ої частини
Вимоги до оформлення курсової роботи
Комп’ютерна логіка. Курсова робота. Група КІ-21. 2015/2016 н.р. (14 навчальних тижнів)
Оцінювання курсової роботи
Розклад викладача
Консультації – після закінчення останнього лекційного заняття, на каф. ЕОМ, 503-V або за домовленістю
Завдання на курсову роботу
Віртуальне навчальне середовище
ВНС, Комп’ютерна логіка, ч.2
Екзаменаційний білет
Робочий журнал
БАЗОВІ КОМБІНАЦІЙНІ ВУЗЛИ
Газорозрядні індикатори
Дешифратор “3 у 8”
Матрична схема дешифратора “3 у 8"
VHDL-опис дешифратора “3 у 8”
Реалізація ФАЛ на дешифраторах
Нарощування розрядності дешифраторів DC “4 у 16” з DC “3 у 8”
Нарощування розрядності дешифраторів DC “3 у 8” з DC “1 у 2”
Демультиплексор DX = Дешифратор DC
Класифікація DC та DX
Мультиплексор 8 в 1
VHDL-опис
Реалізація ФАЛ на мультиплексорах
Нарощування розрядності мультиплексорів
Класифікація DC, DX, MUX
Шифратор Coder CD
Класифікація DC, CD, DX, MUX
Пріоритетний шифратор
Двійково-десяткові коди
Перетворювач кодів 8421 у 8421+3 DC + CD
Матрична схема перетворювача коду 8421 у код 8421+3
Перетворювач кодів для семигементного індикатора
Перетворювач кодів – дешифратор для 7-сегментного індикатора
Програмовані структури
Постійний запам’ятовуючий пристій
Реалізація ФАЛ на ПЗП
Реалізація ФАЛ на ПЗП
Опис ПЗП на мові VHDL
Програмовані логічні матриці
Реалізація ФАЛ на ПЛМ
Таблиця прошиття ПЛМ
Програмовані матриці логіки
Реалізація ФАЛ на ПМЛ
Таблиця прошиття ПМЛ
Логічна комірка
ПЛІС першого покоління
Конфігуровані логічні блоки (CLB) та електронні комутатори (PSM -Programmable switch matrix )
Електронний комутатор
Операційний пристрій на основі ПЗП
Таблиця прошиття ПЗП
Пам’ять перших комп’ютерів
Вузол порівняння на основі DC
Компаратори
4-розрядний універсальний компаратор
Багаторозрядні компаратори
Неповні дешифратори
Дешифратор діапазону кодів 04B8F ...1Е3А4 (04B8F…0FFFF)
Дешифратор діапазону кодів 04B8F ...1Е3А4 (10000…1E3A4)
Дешифратор діапазону кодів 04B8F ...1Е3А4
Логічні операції над числами
Зсуви
Двійковий суматор з наскрізним (послідовним) переносом
Повний однорозрядний двійковий суматор
Суматор з паралельним переносом
Суматор з паралельним переносом
4-бітний суматор із схемою прискореного переносу
16-бітний суматор із схемою прискореного переносу
64-бітний суматор із схемою прискореного переносу
Двійкові суматори
Паралельний матричний помножувач на комірках Гілда
Паралельний матричний помножувач на комірках Гілда
Матричний (паралельний, комбінаційний) помножувач
Арифметико-логічний пристрій
Арифметичний вузол
Логічний вузол
Вузол зсувів
Структура комп’ютера
Загальна структурна схема цифрового автомата
Структурна схема автомата Мура
Структурна схема автомата Мілі
Часові функції алгебри логіки
Елемент затримки
Часові ФАЛ 1-, 2- та 3-го роду
Часова функція 3-го роду Зворотній зв’язок (техн) Змія, що кусає себе за хвіст – Уроборос (філ.)
Загальна схема тригера (trigger, flip-flop, latch)
Тригер та генератор
Класифікація тригерів
RS-тригер
неRнеS-тригер
Класифікація синхронних тригерів
Синхронний RS-тригер
D-тригер, що спрацьовує по тілу
D-тригер, що спрацьовує по фронту
Функціональна схема D-тригера, що спрацьовує по фронту
Т-тригер
T-тригер з входом дозволу роботи
JK-тригер
Перетворення тригерів
Тригери з асинхронними входами (R, S) та входом дозволу СІ (CE)
Лічильник на T-тригерах
Лічильник на D-тригерах
Лічильник на JK-тригерах
Класифікація регістрів
Регістр зсуву
SerDeS
Паралельний регістр
Оперативний запам’ятовуючий пристрій (ОЗП)
Ієрархія пам’яті
Регістровий файл
Операційний пристрій = ALU+RG File
Структура комп’ютера
Логічна комірка
Конфігуровна логічна комірка
Логічні комірки в складі Slice
ПЛІС першого покоління
Організація перших ПЛІС
Конфігуровані логічні блоки (CLB) та електронні комутатори (PSM -Programmable switch matrix )
Електронний комутатор
Електронний перемикач
Структура комп’ютера
Загальна структурна схема цифрового автомата
Структурна схема автомата Мура
Структурна схема автомата Мілі
Рекомендована послідовність синтезу цифрових автоматів
Кодуванням станів автомата: двійкове, сусіднє, унітарне
Перехід від блок-схеми алгоритму до графа автомата Мура
Перехід від блок-схеми алгоритму до графа автомата Мілі
Збудження тригерів
Синтез автомата Мура
Результат синтезу – схема автомата Мура
Сусіднє кодування станів
Схема автомата
Унітарне кодування станів
Схема автомата
Автомат на Т-тригерах
Схема автомата
Автомат на JK-тригерах
Схема автомата
Синтез автомата Мілі
Схема автомата
Мікропрограмний автомат
46.13M
Categories: informaticsinformatics electronicselectronics

Комп’ютерна логіка (частина 1)

1.

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

2. Лекція 1

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

3. Розклад викладача, консультації – Пн, Чт після 2-ої пари, 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
Оцінювання відповідей при полегшеному підході
Оцінка Оцінка практичні
75 * Сума балів ЛекційніКР * Сума балів за тести
70 * 80 * 100
* Оцінка білет
Оцінка 100; Оцінка практичні 25; Сума балів ЛекційніКР 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. Навички (компетенції) випускників

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

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

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

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

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

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

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

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


визначити власні потреби в навчанні і планувати та здійснювати своє власне
навчання в різних середовищах навчання;
самостійно набувати ширшої освіти, необхідної для розуміння впливу
інженерних рішень в




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

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

• демонструвати знання сучасних проблем;
• розуміти і використовувати методи, навички та сучасні
інженерні інструменти необхідні для інженерної практики
з відповідними міркуваннями щодо забезпечення:





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

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


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

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


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

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

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

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

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

37.

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

38. Комірки

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

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

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

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

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

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

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

42.

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

43.

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

44.

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

45.

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

46. У Львові 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 н.р.
Глухов В.С. Комп'ютерна логіка
46

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

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

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

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

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

Літера
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
Назва
ен
о
пе
ку
ер
ес
у
ве
дубль ве
ікс
іпсилон, ігрек
зет (зета)
Глухов В.С. Комп'ютерна логіка
49

50. Математичні основи Просте число — це натуральне число, яке має рівно два різних натуральних дільники (лише 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 н.р.
Глухов В.С. Комп'ютерна логіка
50

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

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

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

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

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

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

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

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

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

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

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

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

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

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

58. Степені 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
Глухов В.С. Комп'ютерна логіка
58

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

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

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

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

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

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

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

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

63. Матерія

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
Глухов В.С. Комп'ютерна логіка
71

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

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

73. Дані

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

74. Кодування

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
Глухов В.С. Комп'ютерна логіка
85

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

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

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

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

88. Варіанти представлення бітів інформації на фізичному рівні (варіанти сигналів)

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

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

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

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

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

91. Дані

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

105. 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 н.р.
Глухов В.С. Комп'ютерна логіка
105

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

• 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 н.р.
Глухов В.С. Комп'ютерна логіка
106

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

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

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

• 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 н.р.
Глухов В.С. Комп'ютерна логіка
108

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


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

110. 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 н.р.
Глухов В.С. Комп'ютерна логіка
110

111.

Одиниця кількості інформації
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 н.р.
Глухов В.С. Комп'ютерна логіка
111

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

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

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

• властивості інформації:











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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
121

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

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

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

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

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

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

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

повідомлення, які складаються з літер
певного алфавіту, можна закодувати так, що
середнє число двійкових символів на літеру
буде як завгодно близьке до ентропії
джерела цих повідомлень, але не менше
цієї величини
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 н.р.
Глухов В.С. Комп'ютерна логіка
125

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

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

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
128

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

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

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

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

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

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

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

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

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

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

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

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

135.

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

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
137

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

Таблиця 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 н.р.
Глухов В.С. Комп'ютерна логіка
138

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

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

140. SerDes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблиця 1.5.1
Система залишкових
класів
НУЛП 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
148

149. Поля Галуа

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

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

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

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

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

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

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
Глухов В.С. Комп'ютерна логіка
152

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

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

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

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

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

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

156.

а
б
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 н.р.
Глухов В.С. Комп'ютерна логіка
156

157. Алгоритм

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

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

• 3 множини:
– Множина вхідних даних
– Множина можливих результатів
– Множина проміжних результатів
• 4 правила:




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

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


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

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

• У процесі розробки алгоритму можуть використовуватись
різні способи його опису, які відрізняються за простотою,
наочністю, компактністю, мірою формалізації, орієнтації
на машинну реалізацію тощо.





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

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

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

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

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

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

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

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

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

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


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
165

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

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

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

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

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


Опис автомата формальною (з правилами без винятків) або
неформальною (з правилами та винятками з них) мовами
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 н.р.
Глухов В.С. Комп'ютерна логіка
168

169. Теза Черча 

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

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


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

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

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

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

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

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

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

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

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

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

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

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

кількість
змінних
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
176

177. ФАЛ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
НУЛП 20162017 н.р.
Глухов В.С. Комп'ютерна логіка
ФАЛ0
177

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• З ФАЛ, які мають якусь властивість, можна
утворити тільки ФАЛ, які мають цю ж властивість
• З ФАЛ, які мають якусь властивість не можна
утворити ФАЛ, які не мають цієї властивості
• До ФПС повинна входити хоча би одна ФАЛ, яка:





НУЛП 20162017 н.р.
1) не зберігає 0;
2) не зберігає 1;
3) несамодвоїсна;
4) немонотонна;
5) нелінійна
Глухов В.С. Комп'ютерна логіка
189

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

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

191. Деякі ФАЛ3

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

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

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

193. Базис Буля

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

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

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

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

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

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

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

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

ДДНФ:
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 н.р.
Глухов В.С. Комп'ютерна логіка
197

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

Матриця
Диз'юнктор
кон'юнкторів
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 н.р.
Глухов В.С. Комп'ютерна логіка
198

199. Використання базису з 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
Глухов В.С. Комп'ютерна логіка
199

200. Використання базису з 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
Глухов В.С. Комп'ютерна логіка
200

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

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
Глухов В.С. Комп'ютерна логіка
Правило де Моргана
(закон поглинання)
(закон поглинання)
(закон склеювання)
201

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

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

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
204

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

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

206. Монобазис І-НЕ (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
елемент НЕ-АБО
Глухов В.С. Комп'ютерна логіка
206

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

Синтез логічних схем з одним виходом у монобазисі І-НЕ
Матриця
Елемент НЕ-АБО
елементів І-НЕ
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 н.р.
Глухов В.С. Комп'ютерна логіка
207

208. 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АБО
Глухов В.С. Комп'ютерна логіка
208

209. Синтез логічних схем з одним виходом у монобазисі 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
Глухов В.С. Комп'ютерна логіка
209

210. Монобазис АБО‑НЕ (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
елемент НЕ-І
Глухов В.С. Комп'ютерна логіка
210

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

Синтез логічних схем з одним виходом у монобазисі
АБО-НЕ
Матриця
Елемент НЕ-І
елементів АБО-НЕ
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 н.р.
Глухов В.С. Комп'ютерна логіка
211

212. 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
212

213. Синтез логічних схем з одним виходом у монобазисі 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 н.р.
Глухов В.С. Комп'ютерна логіка
213

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

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

215.

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
216

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

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
219

220. ДНФ

Входи
Матриця
інверторів
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 н.р.
Глухов В.С. Комп'ютерна логіка
220

221. КНФ

Матриця
інверторів
Входи 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
Глухов В.С. Комп'ютерна логіка
221

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

Суматори за
модулем 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 н.р.
Глухов В.С. Комп'ютерна логіка
222

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

• Базис Жегалкіна (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 н.р.
Глухов В.С. Комп'ютерна логіка
223

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

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

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

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

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

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

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

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

228. Терм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
239

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
240

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

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

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

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

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

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

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
245

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

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
Глухов В.С. Комп'ютерна логіка
246

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

• Тризначна логіка Лукасевича {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 н.р.
Глухов В.С. Комп'ютерна логіка
247

248.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

271. Дешифратор “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 н.р.
Глухов В.С. Комп'ютерна логіка
271

272. Матрична схема дешифратора “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 н.р.
Глухов В.С. Комп'ютерна логіка
272

273. 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 н.р.
Глухов В.С. Комп'ютерна логіка
273

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

Матриця
інверторів
Матриця кон'юнкторів
І 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 н.р.
Глухов В.С. Комп'ютерна логіка
274

275. Нарощування розрядності дешифраторів 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
275

276. Нарощування розрядності дешифраторів 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
276

277. Демультиплексор 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
Глухов В.С. Комп'ютерна логіка
277

278. Класифікація 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 н.р.
Глухов В.С. Комп'ютерна логіка
278

279. Мультиплексор 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 н.р.
Глухов В.С. Комп'ютерна логіка
279

280. 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 н.р.
Глухов В.С. Комп'ютерна логіка
280

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

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

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

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
Глухов В.С. Комп'ютерна логіка
282

283. Класифікація 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 н.р.
Глухов В.С. Комп'ютерна логіка
283

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

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

285. Класифікація 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 н.р.
Глухов В.С. Комп'ютерна логіка
285

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

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
286

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

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

288. Перетворювач кодів 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
1
2
4
8
Глухов В.С. Комп'ютерна логіка
X/Y
1
2
4
8
b1
b2
b4
b8
288

289. Матрична схема перетворювача коду 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 н.р.
Глухов В.С. Комп'ютерна логіка
289

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

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

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

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

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

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
Зворотні зв’язки
Глухов В.С. Комп'ютерна логіка
292

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

Матриця кон'юнкторів
(елементів І)
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 н.р.
Глухов В.С. Комп'ютерна логіка
293

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

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

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

Входи
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 н.р.
Глухов В.С. Комп'ютерна логіка
295

296. Опис ПЗП на мові 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 н.р.
Глухов В.С. Комп'ютерна логіка
296

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
297

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

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
б
Глухов В.С. Комп'ютерна логіка
298

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
300

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

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
б
Глухов В.С. Комп'ютерна логіка
301

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

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

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

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

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

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

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

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

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

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

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

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

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

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
308

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

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

310. Вузол порівняння на основі 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
310

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

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

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

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

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

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

314.

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

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

Таблиця 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
Глухов В.С. Комп'ютерна логіка
315

316. Дешифратор діапазону кодів 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 н.р.
Глухов В.С. Комп'ютерна логіка
316

317. Дешифратор діапазону кодів 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 н.р.
Глухов В.С. Комп'ютерна логіка
317

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

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

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

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

320. Зсуви

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 н.р.
Глухов В.С. Комп'ютерна логіка
320

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
329

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
330

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

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
Глухов В.С. Комп'ютерна логіка
331

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

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

0
A
B
F
A
B
F
ALU
R
R
1
R
ShU
R

2
F
Reserve
A
R
B
F
Код операції -КОП

3
Sel
Fст
00 - арифметичні
01 - логічні
10 - зсуви
11 - резерв
Глухов В.С. Комп'ютерна логіка
Fмл
332

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

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
333

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

A
B
A
B
A
B
A
B
MUX
&
R
RAND
0
1
R
ROR
1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

342. Часові ФАЛ 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 н.р.
Глухов В.С. Комп'ютерна логіка
342

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

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

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

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

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

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

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

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

347. 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 н.р.
Глухов В.С. Комп'ютерна логіка
347

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


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

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

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

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

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

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


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

352. 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 н.р.
Глухов В.С. Комп'ютерна логіка
352

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

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

354. Т-тригер


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

355. 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
Глухов В.С. Комп'ютерна логіка
355

356. 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
Глухов В.С. Комп'ютерна логіка
356

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

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

358. Тригери з асинхронними входами (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
Працюють
асинхронні входи
Заборона
Немає дозволу
Немає потрібного
фронту СІ
Запис даних по
фронту СІ
Глухов В.С. Комп'ютерна логіка
358

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

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

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

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

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

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

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

• За функціональним призначенням
– регістри зсуву
– Регістри для збереження інформації (паралельні)
• За типом тригерів
• За організацією зсуву
– Ліворуч, праворуч, універсальні
• За способом прийому і видачі даних при зсуві (вхід/вихід)




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

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

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

364. SerDeS

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

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

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
Глухов В.С. Комп'ютерна логіка
365

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
366

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

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

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

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
Глухов В.С. Комп'ютерна логіка
368

369. Операційний пристрій = 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
Глухов В.С. Комп'ютерна логіка
369

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

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

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

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

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

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
Глухов В.С. Комп'ютерна логіка
372

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
384

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

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
Кінець
Глухов В.С. Комп'ютерна логіка
385

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

Початок
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 н.р.
Кінець
Глухов В.С. Комп'ютерна логіка
386

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

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 н.р.
Глухов В.С. Комп'ютерна логіка
387

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

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
388

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

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

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

КСх
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
390

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

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

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

КСх
{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
392

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

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

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

КСх
ПА
δ
{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
Глухов В.С. Комп'ютерна логіка
394

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

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

396. Автомат на 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
396

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

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

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


КСх
{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
398

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

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

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

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
Глухов В.С. Комп'ютерна логіка
400
English     Русский Rules