Завдання на курсове проектування за курсом:
«Теоретичні основи інформатики»
Студента: Лепіхова І.М. гр. ІР-1-95.
Тема: «Логічні схеми в різних функціональних наборах та їх реалізація»
1. Вихідні дані
1.1. Рядок з шістнадцяти символів А = (a0, a1 ,..., a15)
Матричний індикатор 5? 7 = 35 осередків.
Безліч ознак H = (h0, h1 ,..., h35)
Умова формування рядка символів і відображення T: H? A -> F.
Правило виділення ФАЛ з даних пункту 1.3.
Інтегральний набір К155 (за довідником)
Умова формування підпростори Ф
Перелік підлягають розробці питань.
2.1. а) відображення Т.
б) ФАЛ F1, F2, F3.
в) підмножина Ф
Комбінаційна схема спільної реалізації ФАЛ F1, F2, F3.
Аналіз підмножини Ф
Схема автомата, що відповідає станам пункту 2.3.
Висновки і ув'язнення.
Тема дослідження.
Структура формальної системи відносини за додатково заданої предметної області знань.
Перелік графічних матеріалів.
Відображення T: H? A -> F.
Комплекс моделей, методів та засобів мінімізації ФАЛ F1 і F2.
Комбінаційна схема спільної реалізації.
Матриця толерантності, карта толерантності для підмножини Ф
Схема автомата А.
ЗМІСТ
Введення.
1. Вихідні дані.
1.1. Рядок з шістнадцяти символів.
1.2. Матричний індикатор.
1.3. Формування відображення рядка символів.
2. Проміжне дослідження вихідних даних.
2.1. Відображення символів рядка А на індикаторі.
2.2. Отримання ФАЛ
2.3. Знаходження номерів ФАЛ по карті Карно
2.4. Таблиця істинності.
2.5. Представлення ФАЛ в досконалої нормальної форми.
2.6. Мінімізація ФАЛ
2.7. Представлення ФАЛ у вигляді куба
3. Дослідження ФАЛ.
3.1. Матриця відносин.
3.2. Дослідження ФАЛ на толерантність.
3.3. Дослідження ФАЛ на еквівалентність.
3.4. Матриця еквівалентності і толерантності.
3.5. Діаграма Ейлера.
3.6. Побудова комбінаційної схеми.
Список використаної літератури
Висновок
Введення.
З розвитком електроніки набувають величезного значення електронні візуальні засоби відображення інформації.
Ці кошти являють собою різноманітної величини екрани, оформлені різними способами (циферблати годин, табло на стадіонах і т.д.) У всіх цих коштів загальна деталь - елемент, що відображає тільки один символ.
Ці елементи являють собою матрицю, у клітках якої змонтовані світяться елементи (лампочки і т.п.) При подачі на них напруги, відображається той чи інший символ візуальної інформації.
Темою даного курсового проекту є розробка автомата, керуючого світяться елементами, для відображення необхідного повідомлення на табло.
Кожен символ повідомлення відображається на окремій матриці (матричному індикаторі) 5? 7 світяться елементів, тобто кожному символу відповідає певна комбінація світяться елементів матриці.
В даному курсовому проекті потрібно вибрати три ознаки (світиться елементу) і побудувати автомат, керуючий цими ознаками при подачі на вхід чотирирозрядний керуючого коду.
Для розробки автомата необхідно зробити аналіз на толерантність і еквівалентність. На закінчення необхідно зробити висновок.
1. Вихідні дані.
Вихідними даними є рядок з шістнадцяти символів, а так само матричний індикатор, призначення якого буде докладніше розглянуто в пункті 1.2.
1.1. Рядок з шістнадцяти символів.
Рядок з шістнадцяти символів вибирається довільно. Вона є об'єктом дослідження. В даному курсовому проекті використовується рядок, наведена на малюнку 1.1.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
І В А Н М И Х А Й Л О В И Ч.
Рис. 1.1. Рядок з шістнадцяти символів
1.2. Матричний індикатор.
Матричний індикатор - матриця розмірністю 5? 7 = 35 осередків. За допомогою матричного індикатора можна будь-якому символу (букви, знаку пунктуації, цифри і т.д.) поставити у відповідність набір ознак H = (h1, h2 ,..., h35). Зовнішній вигляд матричного індикатора представлений на малюнку 1.2.
Рис. 1.2.
1.3. Формування відображення рядка символів.
За допомогою матричного індикатора встановлюється відповідність кожного символу ai з початкової рядка символів А (див. п. 1.1) певний набір ознак На
пристрій повинен видавати сигнал на відповідному виході яка підтверджує, що індикатор розпізнав символ «І». Аналогічно повинні розпізнаватися інші символи рядка А, що відповідає відображенню T: H? A, який представлено у таблиці 1. По горизонталі таблиці розташована рядок А символів, по вертикалі 35 ознак Н. Якщо ознака відповідає даній букві, то на перетині рядка-ознаки та стовпця-букви ставиться «1» і т.д. до заповнення всієї таблиці. Потім проводиться підрахунок одиниць в рядку.
Для спрощення завдання зі всієї безлічі ознак виділяється три ознаки з 35-ти, для яких будується таблиця істинності, причому число одиниць для кожної ознаки підбирається рівним 7,8 і 9. Таким чином, пристрій класифікує символи за двома класами об'єктів: по наявності або відсутності трьох ознак.
Рис. 1.3а, відображення символу «І» на індикаторі Рис. 1.3б, вид матричного індикатора при зображенні символу «І»
2. Проміжне дослідження вихідних даних.
У проміжному дослідженні ми поставимо у відповідність буквах рядки з 16-ти символів набори ознак, сформулюємо відображення T: H? A -> F і виділимо 3 ФАЛ. Побудуємо для них таблицю істинності і по картах Карно знайдемо їхні номери.
2.1. Відображення символів рядка А на індикаторі.
За допомогою матричного індикатора (див. п.1.2) поставимо у відповідність буквах рядки з пункту 1.1 набори ознак (див. рис. 2.1).
Рис. 2.1, відображення символів рядка А на індикаторі.
Випишемо окремо букви і відповідні їм ознаки
І 1,5,6,10,11,14,15,16,18,20,21,22,25,26,30,31,35
У 1,2,3,4,6,10,11,15,16,17,18,19,21,25,26,30,31,32,33,34
A 2,3,4,6,10,11,15,16,17,18,19,20,21,25,26,30,31,35
H 1,5,6,10,11,15,16,17,18,19,20,21,25,26,30,31,35
пробіл
М 1,5,6,7,9,10,11,13,15,16,20,21,25,26,30,31,35
І 1,5,6,10,11,14,15,16,18,20,21,22,25,26,30,31,35
Х 1,5,7,9,12,14,18,22,24,27,29,31,35
A 2,3,4,6,10,11,15,16,17,18,19,20,21,25,26,30,31,35
Й 1,3,5,6,10,11,14,15,16,18,20,21,22,25,26,30,31,35
Л 3,4,5,7,10,11,15,16,20,21,25,26,30,31,35
O 2,3,4,6,10,11,15,16,20,21,25,26,30,32,33,34
У 1,2,3,4,6,10,11,15,16,17,18,19,21,25,26,30,31,32,33,34
І 1,5,6,10,11,14,15,16,18,20,21,22,25,26,30,31,35
Ч 1,5,6,10,11,15,16,17,18,19,20,25,30,35
. 35
2.2. Отримання ФАЛ
В даному курсовому проекті з безлічі ознак виділено 3 (див. табл.1). З номерами 1,3,5 для яких і буде побудована логічна схема пристрою, діагностують їх наявність або відсутність.
Для вирішення завдання в двозначної логікою необхідно перейти до двійкового коду, закодований їм кожний з 16-ти символів рядка А.
При цьому досить чотирирозрядний двійкового числа, що визначає значення XYZP, яким надалі буде кодуватися номер кожного символу. Наприклад, другий символ «В» повинен мати код 0001, перший «І» - 0000 і т.д.
Таблиця істинності для обраних ознак представлена в таблиці 2, де ФАЛ - функція алгебри логіки, в яких значення 1 приймається для кодів, що мають значення ознаки h, рівного 1. У загальному випадку h? (0,1). Слід врахувати, що h1 -> F1, h3 -> F3, h5 -> F5.
Відображення T: H? A -> F
Табл. 1
2.3. Знаходження номерів ФАЛ по карті Карно
Наступним етапом є знаходження 10-значних номерів ФАЛ по карті Карно, загальний вигляд якої для 4-ох змінних представлений на малюнку 2.2. Цифри в квадратах є ступенем числа 2 при визначенні номера ФАЛ, обраних в даній роботі на малюнку 2.2а, б, в
2.5. Представлення ФАЛ в досконалої нормальної форми.
Уявімо обрані ознаки в досконалої діз'юнктівной нормальній формі (СДНФ) і досконалої кон'юнктівной нормальній формі (СКНФ). Для цього з таблиці істинності ФАЛ (див. табл. 2) випишемо констітуенти 0 і 1.
ФАЛ в СДНФ набуде вигляду:
F1 (X, Y, Z, P) = (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)?
(X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)
F3 (X, Y, Z, P) = (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)?
(X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)
F5 (X, Y, Z, P) = (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)?
(X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)? (X, Y, Z, P)
Проведемо мінімізацію отриманих ФАЛ за допомогою карти Карно і представимо їх у ДНФ. Для цього спробуємо оптимальним чином поєднати 0-куби в куби більшої розмірності. Клітки, що утворять k-куб, дають мінітерм nk рангу, де n - число змінних, які зберігають однакове значення на цьому k-кубі. Таким чином, отримаємо ДНФ обраних ФАЛ.
Рис 2.2а Рис 2.2б Рис 2.2в
Проведемо мінімізацію алгебраїчним шляхом, скориставшись тотожність а? а = а.
Побудувати матрицю відносин T: H? A. Матриця відносин представляє собою таблицю, рядками якої є записи (кортежі ознак), а рядками відносини, які мають усі унікальні імена. Матриця відносини представлена в таблиці 3.
Матриця відносин. Табл. 3
3.2. Дослідження ФАЛ на толерантність.
Визначимо класи толерантності. Розглянемо класи толерантності k1, k2, k3, що мають загальні елементи, отже, є пересічними множинами.
h1 = h (? 1) = h (A) = (X0, X1, X3, X5, X6, X7, X9, X12, X13, X14)
h2 = h (? 2) = h (B) = (X1, X2, X8, X9, X10, X11, X12)
h3 = h (? 3) = h (C) = (X0, X3, X5, X6, X7, X9, X10, X13, X14)
Проаналізувавши класи h1, h2, h3, можна отримати: k1? k2 = 0;
k1? k3 = 0; k2? k3 = 0, тобто (k1, k2, k3) - утворюють клас толерантності
Результати дослідження занесемо до таблиці 3.
3.3. Дослідження ФАЛ на еквівалентність.
Визначимо класи еквівалентності для цієї множини А = (Х0, Х1 ,...., х15) розіб'ємо на класи еквівалентності, отримаємо 6 класів
М1 = (AC) = (X0, X3, X5, X6 X7, X13, X14)
М2 = (AB) = (X1, X12)
М3 = (B) = (X2, X8, X11)
М4 = () = (X4, X15)
М5 = (ABC) = (X9)
М6 = (BC) = (X10)
При цьому кожен клас повністю визначається будь-яким його представником. Зіставивши результати дослідження з результатами пункту 3.2 отримаємо наступні залежності
Результати дослідження занесені в таблицю 3. Результати дослідження на еквівалентність та толерантність необхідні для оптимізації побудови логічної схеми.
3.4. Матриця еквівалентності і толерантності.
Матрицю еквівалентності і толерантності можна представити у вигляді квадрата, по діагоналі якого будуються класи еквівалентності, а потім влаштовуються відносини толерантності. Матриця еквівалентності і толерантності представлена в таблиці 4.
Матриця еквівалентності і толерантності. Таблиця 4.
3.5. Діаграма Ейлера.
Діаграма Ейлера дає наочне уявлення про те, як розподіляються ознаки за класами толерантності та еквівалентність. Діаграма Ейлера для обраних ФАЛ представлена на малюнку 3.5.
Діаграма Ейлера. Рис. 3.5
3.6. Побудова комбінаційної схеми.
Комбінаційна схема автомата розпізнавання набору ознак H = (h1, h3, h5) побудована на основі результатів досліджень у пункті 3.1 і пункті 3.4.
Таблиця 5
Використовуючи таблицю 5, можна записати наступні відносини:
F1 = G1? G2? G5
F3 = G2? G3? G5? G6
F5 = G1? G5? G6
Ці відносини еквівалентні ФАЛ в СДНФ, отриманими в пункті 2.5.
Комбінаційна схема будувалася в два етапи:
1 етап: - побудова комбінаційної схеми на елементах і, або,
(нестандартних).
2 етап: - заміна нестандартних елементів на стандартні і-не
Остаточний варіант комбінаційної схеми наведений у додатку 1.
Список використаної літератури
1. В.П. Сигорський. «Математичний апарат інженера» - видавництво Київ: Техніка - 1975 р.
Висновок
Провівши аналіз на толерантність і еквівалентність, ми побудували автомат, що розпізнає кортеж ознак H = (h1, h3, h5), який складається з 16 - ти логічних елементів.
