Навчальний матеріал
до курсової роботи на тему
«СИНТЕЗ КОМБІНАЦІЙНИХ СХЕМ»
з дисципліни
«АРХІТЕКТУРА ОБЧИСЛЮВАЛЬНИХ СИСТЕМ»
(Змістовий модуль 1.1. Логічні основи комп’ютерної схемотехніки)
Зміст
Вступ
ТЕОРЕТИЧНІ ПОЛОЖЕННЯ
1.1. Задачі синтезу і аналізу комбінаційних схем
1.2. Представлення булевої функції в аналітичному вигляді
1.3. Мінімізація булевих функцій на картах Карно
1.4. Факторизація і декомпозиція булевих функцій
1.5. Синтез комбінаційних схем в різних базисах
1.5.1. Основні положення
1.5.2. Булев базис
1.5.3. Універсальні базиси
1.5.4. Скорочені булеві базиси
1.5.5. Базис Жегалкіна
2. СИНТЕЗ КОМБІНАЦІЙНИХ СХЕМ, РЕАЛІЗУЮЧИХ ЗАДАНУ ЛОГІЧНУ(БУЛЕВУ) ФУНКЦІЮ
2.1. Складання таблиці істинності
2.2. Уявлення булевої функції в аналітичному вигляді
2.3. Мінімізація булевої функції на карті Карно
2.3.1. Визначення МДНФ
2.3.2. Визначення МКНФ
2.4. Перетворення мінімальних форм булевої функції
2.5. Синтез комбінаційних схем в булевому базисі
2.6. Синтез комбінаційних схем в універсальних базисах
2.6.1. Базис (АБО-НЕ)
2.6.2. Базис (І-НЕ)
3.МОДЕЛЮВАННЯ КОМБІНАЦІЙНИХ СХЕМ В ElectronicsWorkbench
Додаток 1. Варіанти завдань до курсової роботи
Вступ
Основною метою курсової роботи з дисципліни «Архітектура обчислювальних систем» є закріплення практичних навичок при вирішенні задачі синтезу комбінаційних схем в різних базисах.
Як показники ефективності синтезованої схеми в рамках курсової роботи прийняті витрати обладнання (число логічних елементів або вентилів схеми) і швидкодія (час реалізації логічної функції).
У зв'язку з цим виникає необхідність вирішення задач мінімізації, факторизації і декомпозиції булевих функцій. Для вирішення завдання мінімізації застосовуються метод Квайна-Мак-Класки, заснований на кубічному поданні булевих функцій і є формалізованим, і метод мінімізуючих карт (карт Карно), який у великій мірі є інтуїтивним.
У курсової роботі в якості вихідної задається не повністю визначена булева функція від п'яти змінних, безліч варіантів якої наводиться в додатку, що в повній мірі дозволяє вирішити проблему індивідуального навчання.
При виконанні роботи необхідно:
скласти таблицю істинності заданої булевої (логічної) функції;
уявити булеву функцію в аналітичному (алгебраїчному) вигляді, а саме у вигляді ДДНФ (КДНФ) і ДКНФ (ККНФ);
знайти МДНФ і МКНФ на картах Карно (по 2 варіанти кожного виду);
перетворити МДНФ і МКНФ до форми, що забезпечує мінімум «ціни схеми» (мінімум числа ЛЕ, а по можливості і часу затримки схеми);
перетворити логічну функцію в універсальні базиси операцій штрих Шеффера і стрілка Пірса;
синтезувати комбінаційні схеми в булевому і універсальних базисах (за однією схемою в кожному базисі) з урахуванням накладених обмежень (всі логічні елементи двовходові);
розробити моделі схем в програмному додатку ElectronicsWorkbench (EWB);
проаналізувати побудовані схеми, визначивши їх реакцію на задані комбінації вхідних сигналів, ціну і затримку.
Зауваження.
Варіанти завдань представлені в Додатку 1 (для 411/1 групи номери 1-16 у відповідності із номером курсанта по навчальному журналу, для 411/2 групи – номери 17-32 у відповідності із номером курсанта 1-16 по навчальному журналу).
Результатом роботи є комбінаційні схеми, що реалізують задану функцію і побудовані на логічних елементах різних базисів (довільному булевом базисі, універсальних базисах логічних елементів «І-НЕ» і «АБО-НЕ»), а також їх моделі, реалізовані в програмному додатку EWB (скріншоти вікон програми з комбінаційними схемами привести в тексті роботи).
З послідовністю виконання курсової роботи також можна ознайомитися в матеріалах практичних занять по модулю і в літературі [1-5].
1. ТЕОРЕТИЧНІ ПОЛОЖЕННЯ
1.1. Завдання синтезу та аналізу комбінаційних схем
Логічну схему, що має n входів X = {x1, x2, ..., xn} і m виходів Y = {y1, y2, ..., ym}, можна уявити в узагальненому вигляді (рис. 1).
(1)Рисунок 1 - Узагальнена структура КС
Логічна схема називається комбінаційною (КС), якщо значення множини Y={y1, y2, …, ym} її виходів можуть бути виражені як система m булевих функцій від безлічі вхідних змінних X = {x1, x2, ..., xn} виду (1 ).
Кожна функція yi = yi (x1, x2, ..., xn) при i = 1, 2, ..., m визначає значення yi ∈ {0, 1} на виході схеми для будь-якого з 2n можливих n- мірного довічного набору (e0, e1 , ...,), що подається на незалежні входи схеми (наприклад, e0 = {0, 0, ..., 0}, а = {1, 1, ..., 1}).
Система (1) описує залежність між входами і виходами схеми, але не дає уявлення про її внутрішню структуру.
Функціонування комбінаційної схеми можна виразити також у вигляді таблиці істинності, що має 2n рядків (по рядку для кожного набору вхідних змінних) і (n + m) стовпців (n стовпців для входів і m стовпців для виходів схеми).
Завдання синтезу комбінаційної схеми полягає в побудові схеми для заданої булевої функції або системи булевих функцій на основі певної системи логічних елементів. Як правило, початковий опис для синтезу схеми задається або у вигляді таблиці істинності, або в аналітичній формі у вигляді системи (1). При вирішенні задачі синтезу комбінаційної схеми, що реалізує задану булеву функцію, попередньо проводиться мінімізація булевої функції та подальше спрощення мінімальної форми шляхом факторизації і декомпозиції. Комбінаційна схема будується в заданому базисі, як правило, з урахуванням коефіцієнта об'єднання по входах і коефіцієнта розгалуження по виходу (в роботі ці вимоги не пред'явлені).
Задача аналізу комбінаційної схеми полягає у визначенні функції заданої схеми і показників її якості. В окремому випадку завдання аналізу полягає у визначенні реакції схеми на задані набори вхідних сигналів (змінних).
1.2. Подання булевої функції в аналітичному вигляді
Для подання булевих функцій в аналітичному вигляді зазвичай використовуються нормальні форми.
В якості аналітичних форм булевих функцій використовуються «букви», що об'єднуються у вирази знаками булевих операцій (кон'юнкції і диз'юнкції). Під буквою розуміється булева змінна, що представляє аргумент булевої функції, або її заперечення. Для уявлення нормальних форм булевих функцій використовуються найпростіші булеві вирази, що називаються елементарна кон'юнкція (кон'юнктивним або міні-термом) і елементарна диз'юнкція (диз'юнктивним або максі-термом).
Елементарною кон'юнкцією (диз'юнкцією) або кон'юнктивним (диз'юнктивним) термом називається вираз, що представляє собою кон'юнкцію (диз'юнкцію) будь-якої кінцевої множини попарно відмінних букв або що складається з однієї букви.
Для подання булевих функцій можуть використовуватися диз'юнктивна і кон'юнктивна нормальні форми.
Диз'юнктивною нормальною формою (ДНФ) називається диз'юнкція будь-якої кінцевої множини попарно відмінних елементарних кон'юнкцій.
Кон'юнктивною нормальною формою (КНФ) називається кон'юнкція будь-якої кінцевої множини попарно відмінних елементарних диз'юнкцій.
В окремому випадку, як ДНФ, так і КНФ можуть складатися з одного терма.
Елементарні кон'юнкції (диз'юнкції) називаються конституентами одиниці (нуля), якщо вони містять в прямому або інверсному вигляді всі змінні, які є аргументами булевої функції. Конституента одиниці приймає одиничне значення тоді і тільки тоді, коли всі вхідні в конституенту букви приймають значення, рівні одиниці.
Конституента нуля приймає нульове значення тоді і тільки тоді, коли всі вхідні в конституенту букви приймають значення, рівне нулю. З цього випливає, що конституанта одиниці (нуля) приймає одиничне (нульове) значення на одному і тільки одному наборі аргументів мулевої функції.
На основі конституант одиниці (нуля) складаються досконалі (канонічні) диз'юнктивні (кон'юнктивні) нормальні форми мулевих функцій.
ДНФ (КНФ) називається досконалою або канонічною, якщо всі її елементарні кон'юнкції (диз'юнкції) є конституантами одиниці (нуля).
Канонічну диз'юнктивну нормальну форму (КДНФ або ДДНФ) і кон'юнктивну нормальну форму (ККНФ або ДКНФ) можна скласти за таблицею істинності наступним чином.
Для отримання КДНФ в таблиці істинності виділяються набори аргументів, на яких функція приймає значення, рівне одиниці. Для кожного з них складаються конституанти одиниці. При цьому змінна, що приймає значення, рівне одиниці, входить в конституенту в прямому вигляді, а змінна, що приймає нульове значення - в інверсному. Конституенти одиниці об'єднуються знаками диз'юнкції, утворюючи КДНФ.
Для отримання ККНФ виділяються набори аргументів, на яких функція приймає значення, рівне нулю. Для кожного з них складаються конституенти нуля. При цьому змінна, що приймає значення, рівне одиниці, входить в конституенту в інверсному вигляді, а змінна, що приймає нульове значення - в прямому. Конституенти нуля об'єднуються знаками кон'юнкції, утворюючи ККНФ.
1.3. Мінімізація булевих функцій на картах Карно
В роботі обмежимося застосуванням для мінімізації булевих функцій методу мінімізації на основі карт Карно.
Карти Карно є одним із способів таблично-графічного представлення булевих функцій. Вони використовуються для мінімізації булевих функцій від невеликого числа змінних (як правило, від трьох до шести). З використанням карт Карно досить просто виділяється мінімальне покриття функції, за яким складається МДНФ (для одиничного покриття) або МКНФ (для нульового). Для цієї мети на карті виділяються максимальні куби, що подаються прямокутниками з клітин, зазначених одиницями або нулями (набори, які породжують невизначені значення виходів, можуть входити і в «нульові», і в «поодинокі» куби). Дві сусідні клітини карти утворюють 1-й куб, чотири - 2-й куб, вісім - 3-й куб і т.д.
Покриття з мінімальною «ціною» формується, якщо кожна суттєва вершина (набори одиниць або нулів) буде покрита максимальним кубом найбільшої розмірності і для покриття всіх істотних вершин буде використано найменше число кубів.
1.4. Факторизація і декомпозиція булевих функцій
Факторизація булевої функції полягає у винесенні загальних частин з термів з метою зменшення ціни схеми. У деяких випадках факторизація може привести і до збільшення ціни схеми. Якщо булева функція має кілька мінімальних форм, для найбільш ефективного факторного перетворення необхідно вибрати таку форму, у якій вдасться винести найбільше число букв з найбільшого числа термів.
Задача декомпозиції булевої функції f (X) в найпростішому випадку, так званій розділової декомпозиції, полягає в розбитті безлічі аргументів X на ряд підмножин, в окремому випадку на дві - V і W - таким чином, щоб V∪W = X і f (X) = f [ (V), W], де (V) - допоміжна булева функція. У деяких випадках застосування декомпозиції дозволяє зменшити ціну схеми.
1.5. Синтез комбінаційних схем в різних базисах
1.5.1. Основні положення
В результаті синтезу повинні бути визначені склад логічних елементів, що входять в комбінаційну схему, і порядок їх з'єднання між собою. При побудові КС рекомендується спиратися на наступні положення:
1. Якість схеми, що синтезується, оцінюється двома основними показниками: витратами обладнання та швидкодією. Витрати обладнання визначаються числом логічних елементів, а швидкодія схеми – затримкою поширення сигналів від входів схеми до їх виходу. Затримка схеми T визначається у вигляді T = kτ, де τ - затримка на одному логічному елементі (ЛЕ), k - максимальне число елементів схеми на «шляху» від її входів до виходу.
2. В залежності від того, який з показників якості обирається за основний, задача синтезу комбінаційних схем може вирішуватися в одній з двох постановок:
• синтезувати схему з мінімальною ціною (в якості «ціни» часто використовують «ціну схеми за Квайном», яку можна для простоти замінити мінімумом числа ЛЕ з заданим числом входів);
• синтезувати схему з мінімальною затримкою.
У першому випадку для отримання аналітичної форми булевої функції, що дає мінімум ціни схеми, послідовно вирішуються задачі мінімізації, факторизації і декомпозиції.
У другому випадку в якості аналітичної форми булевої функції вибирають МДНФ або МКНФ, нехтуючи рішенням задач факторизації і декомпозиції, які зменшуючи ціну схеми, збільшують її затримку.
В рамках курсової роботи завдання синтезу комбінаційної схеми вирішується в першій постановці. Однак, при наявності декількох аналітичних форм, що забезпечують однакове і мінімальне значення ціни схеми, перевагу слід віддавати тій з них, яка призводить до побудови схеми з меншою затримкою.
3. Як правило, схема що синтезується, будується на логічних елементах, що відносяться до деякого базису. Система елементів, що утворюють базис, повинна мати властивість функціональної повноти, тобто бути достатньою для побудови комбінаційної схеми, що реалізує будь-яку як завгодно складну булеву функцію. До основних функціонально повних систем елементів відносяться:
• «І, АБО, НЕ» - логічний базис;
• «І-НЕ», «АБО-НЕ» - універсальні базиси;
• «І, НЕ», «АБО, НЕ» - скорочені булеві базиси;
• «І, М2» - базис Жегалкіна.
4. При синтезі комбінаційних схем необхідно враховувати, в якому вигляді подаються вхідні сигнали схеми (вхідні змінні, інтерпретують в схемі аргументи реалізованої функції): в прямому і інверсному або тільки в прямому. У першому випадку синтезується схема з парафазними входами, в другому - з однофазними входами. У схемах з однофазними входами заперечення вхідних змінних реалізуються окремими елементами - інверторами.
5. При побудові схем у реальній системі елементів необхідно враховувати ряд конструктивних вимог, основною з яких є обмеження на число входів логічних елементів, яке визначається коефіцієнтом об'єднання по входах.
В рамках курсової роботи приймається значення цього коефіцієнта, що дорівнює двом.
1.5.2. Булев базис
Логічні елементи цього базису «І, АБО, НЕ» реалізують булеві функції, за допомогою яких представлено аналітичний вираз заданої функції, що використовується для побудови схеми з мінімальною ціною. У зв'язку з цим синтез схеми здійснюється безпосередньою інтерпретацією операцій булевого базису (кон'юнкції, диз'юнкції, заперечення) до відповідних логічних елементів «І, АБО, НЕ». Аргументи булевої функції та їх інверсії інтерпретуються входами в логічні елементи для схем з парафазними входами. Для схем з однофазними входами заперечення аргументів інтерпретуються вхідними інверторами.
1.5.3. Універсальні базиси
Для побудови схем в універсальних базисах можна використовувати такі підходи:
а) перетворення аналітичного виразу до відповідного універсального базису шляхом заміни операцій булевого базису на операції штрих Шеффера (заперечення кон'юнкції) для базису «І-НЕ» або стрілка Пірса (заперечення диз'юнкції) для базису «АБО-НЕ» і побудова схеми по отриманому виразу. Перехід до універсальних базисів здійснюється з використанням законів подвійного заперечення і подвійності (правил де Моргана);
б) перетворення схеми з булевого базису в універсальний базис.
Таке перетворення здійснюється шляхом заміни елементів булевого базису відповідними логічними еквівалентами універсального базису. Логічні еквіваленти універсальних базисів елементам булевого базису наведені в табл. 1.
Таблиця 1 - Відповідність операцій (елементів) булевого і універсальних базисів
Після формальної побудови схеми по логічним еквівалентам з неї виключаються вхідні інвертори з заміною прямих значень вхідних змінних на їх інверсії (тільки для схем з парафазними входами) і інверсій вхідних змінних на їхні прямі значення. Крім того зі схеми виключаються пари послідовних інверторів.
Зауваження.
Перетворення диз'юнктивної форми в базис «АБО-НЕ» призводить використання в схемі додаткового вихідного інвертора, також як іперетворення кон'юнктивної форми в базис «І-НЕ», що, в свою чергу, збільшує ціну і затримку схеми.
1.5.4. Скорочені булеві базиси
Побудова комбінаційних схем в базисах «І, НЕ» і «АБО, НЕ» проводиться по вихідному аналітичному виразу, в якому попередньо всі операції диз'юнкції для базису «І, НЕ» або кон'юнкції для базису «АБО, НЕ» замінюються наступним чином:
Зауваження.
Перетворення диз'юнктивної форми в базис «І, НЕ» призводить до схеми з додатковим вихідним інвертором, також як і перетворення кон'юнктивної форми в базис «АБО, НЕ», що, в свою чергу, збільшує ціну і затримку схеми.
1.5.5. Базис Жегалкіна
Класичним підходом до побудови комбінаційних схем в цьому базисі є попереднє перетворення вихідної аналітичної форми шляхом заміни операцій диз'юнкції на операції кон'юнкції і складання по модулю два відповідно до виразу:
В якості спрощеного підходу можна використовувати попереднє перетворення аналітичної форми в базис «І, НЕ» з подальшою реалізацією інверсій над кон'юнкціями за допомогою двовходових елементів М2, на один вхід яких подається змінна, що інвертується, а на іншій - логічна константа «одиниця». Це перетворення відповідає співвідношенню:
2. СИНТЕЗ КОМБіНАЦІЙНИХ СХЕМ, ЩО РЕАЛІЗУЮТЬ ЗАДАНУ ЛОГІЧНУ (БУЛЕВУ) ФУНКЦІЮ
Розглянемо методику синтезу комбінаційних схем, а по суті послідовність виконання курсової роботи, на прикладі рішення наступної задачі.
Задача.
Побудувати комбінаційні схеми в різнх базисах, що реалізують не повністю певну булеву функцію f(X) = f(x1, x2,…, xn),котра приймає значення «1» за умови: 2 ≤ |x4 x5 x1 – x2 x3| ≤ 5 і невизначене значення на наборах, для котрих x4 x5 = 0.
При виконанні роботи необхідно:
скласти таблицю істинності заданої булевої (логіченої) функції;
представити булеву функцію в аналітичному (алгебраїчному) вигляді, а саме у вигляді ДДНФ (КДНФ) и ДКНФ (ККНФ);
знайти МДНФ и МКНФ на картах Карно (по 2 варіанти кожного виду);
перетворити МДНФ і МКНФ до форми, що забезпечує мінімум «ціни схеми» (мінімум числа ЛЕ, а по можливості і часу затримки схеми);
перетворити логічну функцію в універсальні базиси операцій штрих Шеффера і стрілка Пірса;
синтезувати комбінаційні схеми в булевих і універсальних базисах (по одній схемі в кожному базисі) з урахуванням накладених обмежень (всі логічні елементи двовходові);
розробити моделі схем в додатку Electronics Workbench (EWB);
проаналізувати побудовані схеми, визначивши їх реакцію на задані комбінації вхідних сигналів, ціну і затримку.
Зауваження.
Варіанти завдань наведені в Додатку 1 (для 411/1 групи номери 1-16 в співвідношенні з номером курсанта у навчальному журналі, для 411/2 групи – номери 17-32 в співвідношенні з номером курсанта 1-16 у навчальному журналі).
2.1. Складання таблиці істинності
У таблиці істинності перечисляються всі можливі набори аргументів і значення функції на цих наборах. Стрічки упорядковуються по зростанню двійкових наборів аргументів. Таким чином, перша стрічка складається з нулевих наборів, а остання – одиничний з десятковим значенням 2n-1, в якому n-число аргументів функції. Для наочності порядку (послідовність) визначення значень функції в таблицю вводяться додаткові стовбці для значень операндів (x4 x5 x1) та (x2 x3) вихідного виразу, їх десяткових еквівалентів, а також для значень модуля їх різниці, позначеного через | – |. Крім того, представлено значення (x4 x5), що визначає умову для байдужих («d» – disinterested) наборів аргументів. Ця умова має пріоритетом зрівняно з умовою для одиничного значення функції.
Таблиця істинності заданої функції представлена в табл. 2.
Таблиця 2 – Таблиця істинності заданої логічної функції
2.2. Представлення булевої функції в аналітичному вигляді
2.3. Мінімізація булевої функції на картах Карно
2.3.1. Визначення МДНФ
Для мінімізації булевої функції від п'яти змінних використовуємо дві чотиривимірні карти Карно, що відрізняються по змінній x1.
На карті виділені максимальні куби, що утворюють мінімальне покриття. Куби 1 і 2 є 3-кубами. Куб 2 представлений на правій карті (x1 = 1) прямокутником, що складається з восьми клітин, а куб 1 - на обох картах. Куби 3, 4 і 5 є 2-кубами і складаються з чотирьох клітин. При цьому куб 5 утворює квадрат на правій карті (x1 = 1), а куби 3 і 4 є об'єднанням сусідніх клітин, що належать обом картам. Куб 6 є 1-кубом і представлений двома сусідніми клітинами на лівій карті (x1 = 0).
МДНФ має наступний вигляд:
(1)2.3.2. Визначення МКНФ
Одержання МКНФ здійснюється за нульовим покриттям булевої функції. З цією метою на карті Карно виділяються клітини, що відповідають наборам аргументів, на яких функція приймає нульове значення (клітини відмічаються нулем). Мінімальне нульове покриття визначається за тими ж принципами, що і одиничне.
На карті виділені максимальні куби, що утворюють мінімальне покриття. Куби 1 і 2 є 3-кубами. Куб 2 представлений на правій карті (x1 = 1) прямокутником з восьми клітин, а куб 1 - на обох картах. Куби 3, 4 і 5 є 2-кубами і складаються з чотирьох клітин. При цьому куб 5 утворює квадрат на правій карті (x1 = 1), а куби 3 і 4 є об'єднанням сусідніх клітин, що належать обом картам. Куб 6 є 1-кубом і представлений двома сусідніми клітинами на лівій карті (x1 = 0).
МДНФ має наступний вигляд:
(2)
2.4. Перетворення мінімальних форм булевої функції
МНФ, як правило, не дають цілком мінімальну ціну схеми, що реалізує задану функцію. У зв'язку з цим після знаходження МДНФ і МКНФ проводиться їх подальше перетворення шляхом вирішення завдань факторизации і декомпозиції.
Факторне перетворення для МДНФ:
або в еквівалентній формі запису –
.(3)
Вирішимо задачу декомпозиції стосовно отриманої форми.
Для цього введемо допоміжну функцію і її інверсію
З урахуванням нової функції вираз (3) має вид:
(4)Реалізація комбінаційної схеми виразу (4) з урахуванням витрат на допоміжну функцію та її інверсію надає таку ж ціну схемы, як ідля схеми, побудованої за формою (3), але затримка схеми буде більшою (Т=4τ).
Факторне перетворення для МКНФ.
(5)
Для подальшої декомпозиції є доцільним введення рівної, як і в попередньому випадку, допоміжної функції . Вираз (5) після декомпозиції приймає вигляд:
, 
(6)
для якого ціна схеми дає цілковитий мінімум за умови, що синтезована схема будується на елементах в булевому базисі з парафазними входами.
2.5. Синтез комбінаційних схем в булевому базисі
Комбінаційні схеми, що реалізують задану логічну функцію в булевому базисі, можна синтезувати за її аналітичним представленням як в МДНФ, наприклад, (3), так і в МКНФ, наприклад, (6).
Комбінаційна схема, що реалізує задану функцію за аналітичною формою (6), в булевому базисі з «парафазними входами» представлена на рис. 2а, а з однофазними входами – на рис . 2б.
Затримка схеми з парафазними входами дорівнює Т=4τ, а для схеми з «однофазними входами» – Т=5τ.
2.6. Синтез комбінаційних схем в універсальних базисах
2.6.1. Базис «АБО-НЕ»
Для приведення ЛФ (див. табл.2) до базиса «АБО-НЕ» доцільно використовувати МКНФ, наприклад, аналітичний вираз (6). Таке приведення здійснюється заміною операцій булевого базису на операцію стрілка Пірса (заперечення диз’юнкції) шляхом використання законів двоїстості (правила де Моргана).
За допомогою отриманого виразу будуємо схему з парафазними входами в базисі «АБО-НЕ» (рис.3).
Затримка даної схеми також Т=4τ.
2.6.2. Базис «І-НЕ»
Для приведення ЛФ (див. табл.2) до базису «І-НЕ» доцільно використовувати МДНФ, наприклад, аналітичний вираз (3). Таке приведення здійснюється заміною операцій булевого базису на операцию штрих Шеффера (заперечення кон’юнкції) шляхом використання законів двоїстості (правила де Моргана).
Таким чином, після перетворення ЛФ має вигляд –
(8).Комбінаційна схема в універсальному базисі «І-НЕ» с однофазними входами, побудована за виразу (8) без урахування обмежень кількості входів, приведена на рис.5. Затримка схеми Т=4τ співпадає з затримкою для булева базису. Для врахування обмежень, а саме – усі ЛЕ повинні мати два входи, необхідно замінити віе багатовходові ЛЕ на 2-х входові з урахуванням відповідностей в табл.1.
3. Моделювання комбінаційних схем в Electronics Workbench
Для моделювання комбінаційних схем, що реалізують задані логічні функції, часто використовується додаток ElectronicsWorkbench (EWB). Такі моделі дозволяють при використанні допоміжних індикаційних вузлів перевірити правильність функціонування КС, тобто відповідність їх виходів значенням логічних функцій для всіх можливих комбінацій вхідних параметрів.
В курсовій работі необхідно привести моделі комбинаційних схем реалізації заданої ЛФ в обох универсальних (по одній схемі) і булевому базисі.
На рис.6 приведена КС, що реалізує співвідношення (8) заданої ЛФ, без обліку накладеного обмеження (всі ЛЕ двовходові).
Рис. 6 – Модель КС з однофазними входами, що реалізує співвідношення (8)
ЛІТЕРАТУРА
Довгий П.С., Поляков В.І.Синтез комбінаційних схем. Навчальний посібник до курсової роботи з дисципліни "Дискретна математика". – СПб: СПбГУ ІТМО, 2009. – 64 с.
Макоха А.Н., Сахнюк П.А., Червяков Н.І. Дискретна математика: Навчальний посібник. – М.: ФІЗМАТЛІТ, 2005. – 368 с.
Хаггарті Р. Дискретна математика для програмістів. М.:Техносфера, 2003. – 320 с.
Осипова В.А. Основи дискретної математики: навч.посібник. Інфра-М, Форум, 2006.-160 с.
Приходько В.М., Євсеєв С.П., Садовий К.В. Комп’ютерна схемотехніка: навч. посібник. – Харків: Вид. ХНЕУ, 2011. – 298 с.
Додаток 1. Варіанти завдань до курсової роботи
Номер
варіанту
Умови, при яких f=1 Умови, при яких f=d (def) (для інших f=0)
1. 5≤(x1x2+x3x4x5)<9 (x1x2+x3x4x5)=3
2. -2≤(x4x5-x1x2x3)<1 (x4x5-x1x2x3)=-5
3. (x4x5+x1x2x3)=0,5,8,10 (x1x2x4)=1
4. 2≤|x1x2x5-x3x4|≤4 |x1x2x5-x3x4|=5
5. 2<|x2x10-x3x4x5|≤5 |x2x10-x3x4x5|=1
6. 0<|x1x2x4-x3x5|≤2 |x1x2x4-x3x5|=5
7. 3<(x1x2x3+x4x5)<8 (x3x4)=0
8. 2≤|x1x2-x3x4x5|≤4 |x1x2-x3x4x5|=5
9. 3<(x4x5+x1x2x3)<8 (x1x2x3)=1
10. 4≤(x1x2x3+x4x5)≤6 (x1x2x3+x4x5)=7
11. 5≤(x2x3+x4x5x1)≤8 (x4x5x1)=1
12. -2≤(x1x2-x3x4x5)≤1 (x1x2-x3x4x5)=-3
13. -2<(x2x30-x4x5x1)≤3 (x2x30-x4x5x1)=-2
14. -2≤(x4x50-x1x2x3)<2 (x4x2x3)=2
15. 2≤|x4x5x1-x2x3|≤5 |x4x5x1-x2x3|=0
16. -2≤(x1x20-x3x4x5)<3 (x1x20-x3x4x5)=-3
17. (x2x3+x1)>x4x5 (x2x4x5)=3
18. 2≤|x1x2-x3x4x5|≤4 |x1x2-x3x4x5|=1
19. -3≤(x3x4-x1x2x5)≤0 (x3x4-x1x2x5)=-4
20. 5≤(x1x2x3+x4x5)<9 (x3x4x5)=7
21. 1<|x3x4x5-x1x2|<4 |x3x4x5-x1x2|=6,7
22. -4≤(x2x3-x1x4x5)≤0 (x2x3-x1x4x5)=-3
23. 2≤|x30x4-x5x1x2|≤4 |x30x4-x5x1x2|=1
24. 5<(x1x2+x3x4x5)≤9 (x1x2+x3x4x5)=4
25. 1<|x1x2x5-x3x4|≤4 |x1x2x5-x3x4|=2
26. -2≤(x4x5-x1x2x3)<1 -4≤(x4x5-x1x2x3)≤-3
27. (x4x5+x1x2x3)=2, 5, 8, 10 (x1x2x3)=0
28. 3≤|x2x10-x3x4x5|≤6 |x2x10-x3x4x5|=2
29. 2≤|x2x3x4-x5x1|≤4 (x2x3x4)=1
30. (x1x21+x3x4x5)=5,8,10,11,12 (x1x3x4)=0
31. 4<(x1x2+x3x4x5)≤8 (x3x4x5)=2
32. 1<|x1x2-x3x4x5|≤4 |x1x2-x3x4x5|=7
Зауваження (важливе).
При виконанні роботи слід мати на увазі, що двійковий розряд x1 є старшим, а x5 – молодшим, і, відповідно, таблиця істинності повинна містити послідовність вхідних наборів x1 x2 x3 x4 x5 у вигляді, представленому в табл.2.