Логічне проектування та мінімізація

Зміст                Введення         5             1.         Огляд методів логічного проектування та мінімізації           9             1.1         Нормальні форми логічних функцій         10             1.2         Загальні відомості про мінімізації логічних функцій         15             1.3         Розрахунковий метод мінімізації         18             1.4         Розрахунково-табличний метод мінімізації         21             1.5         Табличний метод мінімізації         23             2.         Можливості програми моделювання Electronics Workbench           28             2.1         Загальні відомості про Electronics Workbench         28             2.2         Інтерфейс Electronics Workbench         32             2.3         Властивості і параметри вимірювальної апаратури, яка використовується в роботі           41             3.         Математичні моделі і еквівалентні схеми в програмі логічного проектування           48             4.         Розробка логічних схем практикуму         53             4.1         Схема цифрового автомата         53             4.2         Цифровий компаратор 2-х розрядного коду         54             4.3         Дешифратор 4-х розрядної адреси         56             4.4         Схема контролю парності         58             5.         Методичні вказівки         61             5.1         Опис лабораторної установки         61             5.2         Попереднє розрахункове завдання         62             5.3         Робоче завдання         62             5.4         Контрольні питання         65             6.         Методичні рекомендації щодо швидкого знайомства з програмою           67             6.1         Робота з HELP, проблема мови і русифікація         67             6.2         Про вікно Description         67             6.3         Можливості отримання твердої копії та підготовки звіту           68             6.4         Демонстраційна версія         68             7.         Організаційно-економічна частина         71             7.1         Організація НДР         71             7.2         Розрахунок витрат         73             7.3         Обгрунтування соціально-економічної ефективності розробки           76             8.         Екологія та охорона праці         81             8.1         Загальні відомості про електромагнітних полях         81             8.2         Методика проведення дослідження         87                     Висновок         91                     Список використаної літератури         93     

Введення

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

При всіх безперечних перевагах існуючого практикуму є досить багато зауважень, які в силу об'єктивних і суб'єктивних труднощів практичної реалізації не вирішені на сьогодні:

1) Сучасна напівпровідникова та інтегральна елементна база дуже чутлива до перегріву, перенапруження, статичної електрики, має мініатюрні розміри і тому вимагає складної, дорогий технологічного оснащення для реальної роботи з сучасними електронними схемами. Використання шкідливих хімічних речовин при монтажі вимагає відповідного обладнання приміщення (теж не дешевого).

2) Робота з сучасними швидкодіючими компонентами вимагає постійного оновлення дорогою і складної контрольно-вимірювальної апаратури. Сучасна апаратура складна, вимагає високої кваліфікації дослідника і мало пристосована для студентського практикуму.

3) Цілий ряд досліджень неможливо виконати через унікальності необхідної апаратури (дослідження фазових характеристик, спектральних характеристик, нелінійних характеристик, дослідження впливу температури на роботу електронного пристрою і т.д.).

4) В існуючому практикумі відсутня можливість діагностики несправності електронного пристрою, навчання навичкам ремонту електронних схем, пуско-налагоджувальних робіт, тобто тих обов'язкових навичок, якими зобов'язаний володіти електронщик при розробці й експлуатації електронної апаратури.

5) У розробці сучасної електронної апаратури все ширше використовується обчислювальна техніка, системи автоматичного проектування, інтелектуальна діагностика працездатності пристроїв. Цей напрям зовсім не представлено в існуючому практикумі.

Перераховані зауваження звичайно не повністю описують проблему. Тому актуально стоїть пошук альтернативних методичних напрямів навчання електронним дисциплін.

Один з таких напрямків розглянуто в даній роботі - використання в лабораторному практикумі комп'ютерного моделювання на базі програмного пакета Electronics Workbench фірми Interactive Image Technologies Ltd. (Canada).

Цей пакет представляє закінчену середу (shell) розробки електронних схем з простим інтуїтивним інтерфейсом, близьким для електронщика. Назва пакету вибрано точно - в перекладі - робочий стіл електронщика.

У цього пакету є цілий ряд переваг, що привертають увагу:

1. Оригінальний простий графічний редактор, що дозволяє досить просто малювати на екрані практично будь-які електронні схеми в звичному зображенні.

2. Велика бібліотека сучасних електронних компонент, дискретних, інтегральних аналогових, цифрових та змішаних аналогово-цифрових. Бібліотека відкрита, легко може поповнюватися новими елементами, у тому числі і вітчизняними.

3. Багата бібліотека електронних схем, що дозволяє використовувати готові практичні розробки та легко модернізувати під конкретну задачу. Бібліотека відкрита, дозволяє поповнення як за рахунок нових розробок, так і за рахунок підключення бібліотек більш ранніх версій.

4. Чудовий набір віртуальних вимірювальних приладів, що дозволяють виконати будь-яке електричне ( і не тільки електричне вимір). Робота з цими вимірювальними приладами максимально наближена до роботи з реальними приладами. Підключивши віртуальний прилад до будь-якій точці схеми можна отримати вичерпну інформацію про процеси в даному вузлі.

5. Простий по інтерфейсу набір моделюючих засобів, що дозволяє крім традиційного моделювання електронної схеми по постійному і змінному струму, повісті моделювання спектральних, нелінійних, амплітудно-частотних, фазо-частотних характеристик, вплив температури на окремі компоненти й на схему в цілому, можливість сканування (sweep) будь-яких параметрів компонентів, параметрів джерел сигналів та харчування. Досить просто можна виконати імовірнісний аналіз роботи схеми з різними законами розподілу параметрів.

6. Великі можливості документування дослідження, отримання твердої копії як електричної схеми, параметрів моделювання, інформації з екрана вимірювальної апаратури, добре оформлених графічних результатів дослідження.

7. Вражаюче низькі вимоги до комп'ютера. Можлива робота починаючи з 386 моделі.

8. Не потребує знань з програмування. Потрібно лише знайомство з середовищем Windows. Інтуїтивний інтерфейс дозволяє швидко навіть непідготовленому користувачеві (буквально за півгодини) познайомиться з основами і приступити безпосередньо до електронних дослідженням.

9. Не можна не згадати великий, ретельно підготовлений Help, що забезпечує як контекстну допомогу по меню, компонентів, опціях моделювання, так і загальні питання моделювання, можливі помилки.

переваг в цьому пакеті більше, ніж перераховано і про них ще буде говоритися в процесі розробки лабораторного практикуму. Однак те, що перераховано, дозволило серед безлічі відомих пакетів електронних CAD'ов (Computer Aided Design) вибрати саме Electronics Workbench як найбільш придатний для використання в лабораторному практикумі.

В даний час все більша кількість студентів отримує доступ до персональних комп'ютерів. Зростає кількість комп'ютерів на кафедрах і в лабораторіях інститутів, зростає і число студентів, які мають комп'ютери вдома.

Отже російські навчальні заклади вже зацікавлені в появі комп'ютерного лабораторного практикуму. Таким чином об'єктивні економічні причини для розробки комп'ютерного моделювання лабораторних робіт вже є.

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

1. Огляд методів логічного проектування та мінімізації

Термін "логічне проектування" охоплює цілий комплекс проблем, що виникають на одній з ранніх стадій створення цифрового автомата. Одним з етапів логічного проектування є синтез його так званих комбінаційних пристроїв, який полягає у визначенні таких способів з'єднання деяких найпростіших схем, які називаються логічними елементами, при яких побудоване пристрій реалізує поставлене завдання з перетворення вхідних двійкової інформації. У Зокрема логічними елементами є інвертор, кон'юнктор і діз'юнктор. Оскільки ці елементи утворюють функціонально повний набір, то з їх допомогою можна побудувати комбінаційне пристрій (тобто пристрій не володіє пам'яттю, в якому вихідний сигнал у будь-який момент часу визначається тільки комбінацією вхідних сигналів), що реалізує будь-який наперед заданий закон перетворення двійковій інформації.

Зазвичай логічне проектування виконується в наступній послідовності:

1) складання таблиці істинності синтезованого вузла згідно з його визначенням, призначенням і (словесному) опису принципу роботи;

2) складання математичної формули для логічної функції, що описує роботу синтезує вузла, згідно наявної таблиці істинності;

3) аналіз отриманої функції з метою побудови різних варіантів її математичного виразу (на підставі законів булевої алгебри) і знаходження найкращого з них у відповідності з тим чи іншим критерієм;

4) складання функціональної (логічної) схеми вузла з заздалегідь заданого набору логічних елементів.

1.1 Нормальні форми логічних функцій

Синтез комбінаційних пристроїв зазвичай починається з табулювання значень істинності всіх вхідних і вихідних величин. Табличне завдання закону функціонування деякого пристрою є найбільш наочною і універсальним засобом опису його роботи. Результатом розглянутого етапу є таблиця істинності, що зв'язує всі можливі комбінації значень аргументів і функцій. Нехай, наприклад, потрібно синтезувати цифровий пристрій, що реалізує складання двох двійкових цифр (полусумматор).

1-й етап синтезу - дається словесний опис полусумматора та принципу його роботи. Він повинен аналізувати всі комбінації вхідних сигналів (тобто двійкових цифр 00, 01, 10, 11) і відповідно до них формувати на виході двухразрядние суми. У першому розряді результату формується цифра переносу, а в другому - цифра багаторозрядних суми. Отже, синтезується полусумматор повинен мати два входи (n = 2) і два виходи. Далі від нестрогого словесного опису переходимо до суворого формального опису роботи полусумматора на табличному мовою. Таблиця істинності (див. табл. 1.1) в загальному випадку при n входах має 2 в ступені n комбінацій значень аргументів.

Таблиця 1.1

Таблиця істинності полусумматора.        1-а цифра доданок Х1         0         0         1         1             2-а цифра доданок Х2         0         1         0         1             Цифра переносу р.         0         0         0         1             Цифра суми s         0         1         1         0     

2-й етап синтезу - для того, щоб показати методику переходу від таблиці істинності до аналітичного висловом, розглянемо деяку узагальнену таблицю істинності двох аргументів f (X1, X2) (див. табл. 1.2). Обмеження на число аргументів не є в даному випадку істотним, але значно спрощує всі міркування.

Таблиця 1.2

Узагальнена таблиця істинності функції двох аргументів.        1-й логічний аргумент Х1         0         0         1         1             2-й логічний аргумент Х2         0         1         0         1             Логічна функція f (X1, X2)         f0         f1         f2         f3     

Тут f0 = f (0,0); f1 = (0,1); f2 = (1,0); f3 = (1,1) - конкретні реалізації функції f (X1, X2) за певних приватних значеннях аргументів X1 і X2. Вони також є двійковими змінними. Десяткові індекси при їх символи число дорівнює тим двійковим числах, які утворюються відповідними приватними значеннями аргументів. Крім того, кожен десятковий індекс можна трактувати як номер деякого стовпця в Таблиці 1.2, що змінюється в межах від 0 до 2n -1, тому що звичайно значення аргументів в таблиці записуються таким чином, щоб виходило з них по вертикалі двійкове число було рівне номеру стовпця. Виходячи з вищевикладеного, вже можна перейти від табличної запису логічної функції f (X1, X2) до аналітичної:

f (X1, X2) = f0 прі, х1 = 0, х2 = 0;

f1 прі, х1 = 0, х2 = 1; (1.1)

f2 прі, х1 = 1, х2 = 0;

f3 прі, х1 = 1, х2 = 1;

Такий запис кілька зручніше і компактніше таблиці, однак вона все-таки громіздка й погано доступні для огляду (особливо у випадку великої кількості аргументів). Але від неї можна перейти до запису іншого виду, зручнішою і компактної:

f (x1, x2) = x1x2f0 + x1x2f1 + x1x2f2 + x1x2f3 (1.2)

Правило побудови кожного члена в цій пропозиції нескладно; проводиться логічне множення елементів кожного стовпця табл.1.2, причому замість 1 береться символ відповідного аргументу, а замість 0 - його заперечення. Рівносильність співвідношень (1.1) та (1.2) простий підстановкою у вираз (1.2) всіх можливих комбінацій значень аргументу xi .

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

- для того щоб одержати аналітичний вираз функції, заданої таблично, потрібно скласти суму констітуент (див. нижче) одиниці для тих наборів значень вхідних двійкових змінних, для яких реалізації функції fi рівні 1, причому будь-який символ змінної в деякій констітуенте береться зі знаком заперечення, якщо конкретне значення змінної xi в даному наборі має значення 0.

Оскільки логічна сума всіх елементарних творів найвищого рангу n обов'язково дорівнює 1, який би набір значень вхідних змінних ні розглядався, то ці твори цілком логічно називати констітуентамі (складовими) одиниці. Аналогічно пояснюється і назва констітуенти (складової) нуля, тому що відомо, що логічне твір всіх елементарних сум найвищого рангу тотожно дорівнює нулю.

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

Оскільки алгебра логіки симетрична, то вищенаведені міркування можна застосувати для виведення ще однієї канонічної форми логічних функцій - сукупності констітуент нуля, з'єднаних знаком кон'юнкції. Таким чином сформулюємо друге правило:

- для того щоб одержати аналітичний вираз функції, заданої таблично, в досконалої кон'юктівной нормальній формі, потрібно скласти логічне твір констітуент нуля для тих наборів значень, вхідних двійкових змінних, для которих реалізація функції fi дорівнює 0, причому символ будь-якої змінної в деякій констітуенте береться зі знаком заперечення, якщо її конкретне значення xi в даному наборі одно 1.

У загальному випадку перехід до досконалої нормальній формі проводиться за три кроки.

1-й крок - за допомогою багаторазового застосування законів інверсії знімаються загальні та групові заперечення так, щоб заперечення залишалися тільки в одиночних змінних.

2-й крок - за допомогою розподільних законів здійснюється перехід до однієї з нормальних форм функції.

3-й крок - проводиться перетворення членів ДНФ або КНФ у відповідні констітуенти за допомогою правила розгортання.

Користуючись сформульованими правилами та таблицею 1.1 для полусумматора записуємо:

p (x1, x2) = x1x2

s (x1, x2) = x1x2 + x1x2 СДНФ (1.3)

p (x1, x2) = (x1 + x2) (x1 + x2) (x1 + x2)

s (x1, x2) = (x1 + x2) (x1 + x2) СКНФ (1.4)

3-й етап синтезу - аналіз та оптимізація (мінімізація) логічних функцій є досить важливими компонентами синтезу цифрових автоматів без пам'яті. Тому методи аналізу і оптимізації будуть розглянуті окремо.

4-й етап синтезу - до побудови функціональної схеми синтезованого вузла в принципі можна переходити відразу ж, як тільки стає відомим аналітичний опис його роботи. Побудова схеми засноване на прямому заміщення елементарних творів, сум і заперечень відповідно кон'юнкторамі, діз'юнкторамі і інвертора. Користуючись співвідношеннями (1.3), (1.4) можемо побудувати для полусумматора два функціональні схеми.

а) СДНФ

б) СКНФ

Рис. 1.1 Функціональна схема полусумматора.

З функціональної точки зору обидві схеми повністю тотожні, хоча зі структурної складності вони значно розрізняються.

1.2. Загальні відомості про мінімізації логічних функцій

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

Таким чином, виникає задача знаходження з усіх можливих форм логічної функції її так званої мінімальної форми, що забезпечує мінімум витрат обладнання при побудові синтезованого вузла, якщо є заданий набір логічних елементів (НЕ, І, АБО) з певними технічними характеристиками (наприклад, максимально можливе число входів у елементів І, АБО та ін.) Неважко помітити, що в рамках нормальних форм мінімальної буде такий різновид функції, яка складається з найменшої кількості членів при найменшому, по можливості, загальній кількості символів змінних.

З більшого числа різних прийомів і методів мінімізації розглянемо три найбільш показових, типових:

розрахунковий метод (метод безпосередніх перетворень);

2 розрахунково-табличний метод (метод Квайна-Мак-Класкі);

табличний метод (метод Вейча-Карно).

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

1-й етап-перехід від досконалої Д (К) НФ до скороченої Д (К) НФ шляхом виробництва всіх можливих склеювання один з одним констітуент, а потім всіх похідні членів більш низького рангу. Таким чином, під скороченою формою будемо розуміти діз'юнктівную (або кон'юнктівную) форму функції, членами якої служать тільки ізольовані (несклеівающіеся) елементарні кон'юнкції (або диз'юнкції). Члени скороченою Д (К) НФ в алгебрі логіки носять назву простих імплікант (імпліцент). Не виключений випадок, коли СД (К) НФ тотожно дорівнює скороченою формі даної функції.

2-й етап-перехід від скороченої нормальної до тупикової нормальної форми. Тупиковій будемо називати таку нормальну діз'юнктівную (кон'юнктівную) форму функції, членами якої є прості імпліканти (імпліценти), серед яких немає жодної зайвої. Термін "зайвий" тут має пряме значення. Зайвим будемо називати такий член функції, видалення якого не впливає на значення істинності цієї функції. Можливі випадки, коли у скороченій формі не виявляється зайвих членів. Тоді скорочена Д (К) НФ тотожно дорівнює тупикової формі. Не виключені випадки появи декількох тупикових форм з однієї скороченою. Назва "тупикова форма" показує, що подальша мінімізація в рамках нормальних форм вже неможлива.

3-й етап - перехід від тупикової (мінімальної серед нормальних форм) форми функції до її мінімальної формі. Цей етап, званий зазвичай факторизації, вже не є регулярним, як два попередніх, і вимагає певної вправності, інтуїції і досвіду. Тут мається на увазі пошук можливостей спрощення функції методом проб і випробувань. Для зменшення числа операцій заперечення слід застосовувати закони інверсії, а для зменшення числа кон'юнкція і диз'юнкція - розподільні закони. На цьому ж етапі вирішується і друге завдання-приведення логічних функцій до виду, зручному для застосування реальних логічних елементів, які на практиці мають певні обмеження на кількість входів і за величиною допустимої навантаження. Різні методи мінімізації відрізняються один від одного шляхами і засобами практичної реалізації того чи іншого етапу. При мінімізації складних функцій найчастіше обмежуються двома першими етапами, тобто отриманням найпростішою серед тупикових ДНФ (КНФ). Розглянемо кожен з вищеназваних методів.

1.3. Розрахунковий метод мінімізації

Нехай задана деяка функція в СДНФ, яку потрібно мінімізувати:

fсднф = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 (1.5)

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

fпр = x1 x3 + x2 x3 + x1x2 (1.6)

Потім проводиться другий крок випробування на склеювання всіх членів функції у проміжній формі. Розглядаючи співвідношення (1.6), переконуємося, що всі його члени ізольовані. Отже, отримана проміжна форма є скороченої ДНФ вихідної функції (сДНФ). Відзначимо, що всі констітуенти функції (1.5) брали участь хоча б в одному склеюванні, тому ні в скороченій, ні тим більше у тупиковій формі членів максимального рангу не буде:

fсднф = x1x3 + x2x3 + x1x2 (1.7)

2-й етап - здійснюється перевірка кожної простий імпліканти в сДНФ з метою виявлення і видалення зайвих членів. Перевірка полягає в наступним. На значення істинності функції впливає тільки та імпліканта, яка сама дорівнює 1. будь-яка імпліканта стає рівною 1 лише на одному, цілком певному наборі значень істинності своїх аргументів. Але якщо саме на цьому наборі суми інших членів теж звертається до 1, то розглянута імпліканта не впливає на значення істинності функції навіть в цьому єдиному випадку, тобто є зайвою. Застосуємо це правило до перевірки членів функції в сДНФ (1.7):

1) x1x3 = 1 при x1 = 0, x3 = 1; сума решти членів на цьому ж наборі дорівнює x21 + 1x2 = 1; отже, що перевіряється, член - зайвий;

2) x2x3 = 1 при x2 = 0, x3 = 1; сума решти членів на цьому ж наборі дорівнює x11 + x10 = x1; отже, що перевіряється, член не є зайвим;

3) x1x2 = 1 при x1 = 0, x2 = 1; сума решти членів на цьому ж наборі дорівнює 1x3 + 0x3 = x3; отже, що перевіряється, член не є зайвим.

Таким чином, відкинувши зайвий член, отримаємо тупикову діз'юнктівную нормальну форму (ТДНФ) вихідної функції:

fтднф = x1x2 + x2x3 (1.8)

Більш докладно зупинимося на випадку, коли зайвих членів виявляється більше, наприклад два. Це не означає, що обидва зайвих члена можна відкинути, тому що кожний з них перевірявся при входженні іншого в суму, що залишилася. Отже, відкинути напевно можна тільки один з них, а потім потрібно знову провести перевірку можливості відкинути і другий член.

Слід також зупиниться докладніше і на разі, коли вихідною формою є СКНФ. Методика проведення першого етапу при цьому практично не змінюється, але реалізація другого етапу має свою специфіку. На значення істинності функції в кон'юнктівной нормальної формі впливає тільки та імпліцента, яка сама дорівнює 0. Але будь-яка імпліцента стає нулем тільки при одному наборі своїх аргументів. Отже, правило перевірки скороченою КНФ на зайві члени потрібно сформулювати таким чином: для кожного члена скороченою КНФ знаходиться такий набір значень істинності його змінних, який звертає даний член в 0. Далі визначається значення істинності твори інших членів на цьому ж наборі. Якщо твір також дорівнює 0, то перевіряється член - зайвий.

3-й етап - спрощуємо ТДНФ або ТКНФ функції. Застосувавши закон інверсії до першого члену функції в ТКНФ, одержимо мінімальну форму (МФ):

fмф = x1x2 (x2 + x3)

для апаратурною реалізації якої потрібної всього сім умов транзисторів. Цікаво, що перетворення в мінімальну форму ТДНФ функції виходить більш складним шляхом:

fтднф = x1x2 + x2x3 = (x1 + x2) (x2 + x2) (x1 + x3) (x2 + x3) = (x1 + x2) (x1 + + x3) (x2 + x3) = fскнф

Перехід від сКНФ до МФ неважко здійснити через ТКНФ, як це було зроблено вище.

1.4. Розрахунково-табличний метод мінімізації

Мінімізація цим способом відрізняється від розрахункової мінімізації тільки методикою виявлення зайвих членів у скороченою Д (К) НФ. Даний метод запропонований американським вченим У. Квайном. Перший і третій етапи мінімізації в цьому випадку будуть ідентичні відповідним етапів при розрахунковий метод. Знаходження тупикової форми (другий етап) проводиться за допомогою спеціальної таблиці (звідси назва методу), значно спрощує виявлення зайвих членів. розглянемо методику розрахунково-табличній мінімізації на тому ж прикладі, який розбирався нами при розрахунковому способі, що дає можливість більш чітко показати як загальні риси обох методів, так і їх відмінності.

Отже, нехай потрібно мінімізувати функцію (1.5), задану в СДНФ:

fсднф = x1x2x3 + x1x2x3 + x1x2x3 + X1x2x3

1-й етап - не відрізняється за змістом від 1-го етапу при розрахунковий метод. Тому відразу ж запишемо вихідну функцію в сДНФ:

fcднф = x1x3 + x2x3 + x1x2

2-й етап - для виявлення можливих зайвих членів у СД (К) НФ функції побудуємо таблицю, вхідними величинами в якій будуть констітуенти - члени СД (К) МФ і імпліканти (імпліценти) - члени скороченою Д (К) НФ. Тому найчастіше таку таблицю називають констітуентно-імплікантной (імпліцентной) матрицею; застосовуються також назви: таблиця Квайна і таблиця покриттів. Вона має кількість стрічок, що дорівнює кількості імплікант (імпліцент) у скороченій Д (К) НФ. Строки діляться на стовпчики, число яких береться рівним кількості констітуент в СД (К) НФ. Тому в горизонтальні (малі) входи таблиці записуються всі прості імпліканти (імпліценти), а у вертикальні входи - Всі члени досконалої нормальної форми (див. табл. 1.3).

Таблиця 1.3

Таблиця Квайна.        Імпла -         Констітуенти             канти         x1x2x3         x1x2x3         x1x2x3         x1x2x3             x1x3         X                 X                     x2x3         X                         X             x1x2                 X         X             

Процес мінімізації починається з послідовного складання кожної імпліканти з усіма констітуентамі. Якщо яка-небудь імпліканта є власною частиною деякої констітуенти, то в табличній клітині, що відповідає обом членам, проставляється будь-який умовний значок (так, в табл.1.3 клітина перекреслюється навхрест). Таким чином, значки в кожному рядку заповненої таблиці показують, які члени досконалої форми функції з'являться при розгортанні даної імпліканти в сімейство констітуент. В ідеальному випадку кожна імпліканта розгорталася б тільки в "свої" констітуенти, і в кожному стовпці тоді був би тільки один умовний значок. Практично цього не відбувається, і дуже часто одна і та ж констітуента покривається в таблиці кількома імплікантамі. Завдання полягає в тому, щоб викресленням деяких (зайвих!) імплікантов спробувати залишити в кожній колонці тільки значок або принаймні мінімальне число імплікант, що покривають всі констітуенти. Практично звичайно по таблиці спочатку знаходиться так зване ядро функції, що складається з трьох імплікант (імпліцент), кожна з яких здійснює єдине покриття деякої констітуенти і тому жодним чином не може опинитися в числі зайвих.

Повертаючись до розглянутого прикладу (см.табл.1.3), констатує. що в ядро функції входять імпліканти x1x2 і x2x3. Отже, залишається тільки перевірити можливість викреслення імпліканти x1x3. Її Викреслювання не порушує умови про наявність хоча б одного покриття кожної констітуенти будь-який імплікантой. Отже, імпліканта x1x3 є зайвою. Тупикова діз'юнктівная нормальна форма вихідної функції

fтднф = x1x2 + x2x3 (1.8 *)

Порівняння показує ідентичність співвідношень (1.8) та (1.8 *), що й повинно було статися.

3-й етап - за своїм змістом не відрізняється від відповідного етапу при розрахунковому методі, тому відразу запишемо мінімальну форму вихідної функції:

fмф = x1x2 (x2 + x3)

1.5. Табличний метод мінімізації

При відносно невеликому числі змінних (R <= 6) вельми зручним і наочним є графічне представлення логічних функцій у вигляді так званих карт мінтермов. Найбільш поширеною формою їх є карти Карно. На ріс.1.2 показані карти Карно для функцій R = 2, 3, 4 і 5.

Ріс.1.2 Карти Карно і розташування в них мінтермов для функцій двох (а), трьох (б), чотирьох (в) і п'яти (г) змінних.

Карта Карно містить q = 2R клітин, причому кожній клітині відповідає одна з q мінтермов. Для ілюстрації цього на рис. 1.2 (a-в) в клітинах карт Карно записані відповідні їм мінтерми. Якщо потрібно представити на карті Карно логічну функцію, задану у вигляді СДНФ, то в клітинах карти, що відповідають мінтермам, що входять до СДНФ, ставляться 1. Решта клітини залишаються незаповненими або заповнюються 0. Приклади графічного представлення функцій, заданих у вигляді СДНФ, показані на рис.1.3 (a-в).

рис.1.3 Приклади графічного представлення логічних функцій з допомогою карт Карно: а) F = AB + AB; б) F = ABC + ABC + ABC + ABC; в) F = ABCD + ABCD + ABCD + ABCD.

Кожній клітці карти поставлений також відповідно один з наборів логічних змінних, який визначається номером стовпця і рядка, на перетині яких розташована клітина. Наприклад на рис.1.3 (в) на перетині стовпця з номером АВ = 01 та рядки з номером CD = 10 розташована клітка, що відповідає набору змінних ABCD = 0110 (мінтерм ABCD). Завдяки цьому зручно представляти на карті Карно функції, задані таблицями істинності. Якщо при i-му наборі змінних значення функції в таблиці істинності F = fi = 1, то у відповідній клітині карти Карно ставиться 1 (тобто відповідний мінтерм mi входить в СДНФ функції). Якщо ж F = fi = 0, то клітина залишається порожньою або ставиться 0 (тобто відповідний мінтерм не входить до СДНФ функції). Таким чином, між поданням функції в табличній (таблиця істинності), алгебраїчної (у вигляді сДНФ) і графічної (на карті Карно) формах є однозначна відповідність.

Логічна функція F на карті Карно представляється сукупністю клітин, заповнених 1, інверсія функції F представляється сукупністю порожніх клітин (або заповнених 0). На рис.1.3 (a) дано подання у вигляді карти Карно функції виключає Або F6 в відповідно до її таблицею істинності. Її інверсія F6 = F9 = AB + AB представляється на цій карті сукупністю порожніх клітин.

Для логічних функцій з числом змінних R> 6 карти Карно стають громіздкими (число клітин q> 64) і не зручними для практичного застосування. Тому використання карти Карно можна рекомендувати при числі змінних * R <= 6.

Розглянуті вище логічні функції були визначені, тобто мали певне значення fi = 0 або fi = 1, при всіх можливих наборах логічних змінних. Такі логічні функції називаються повністю визначеними.

Крім них є великий клас функцій, значення яких визначено тільки для частини логічних наборів змінних. Такі функції називаються частково визначеними. Набори змінних, для яких функція визначена, називаються робочими, а для яких не визначена - байдужими. Значення функції, відповідні байдужим розділами, будемо позначати в таблицях істинності і на картах Карно знаком "Х". На практиці байдужими є такі набори значень логічних змінних, які при роботі даного конкретного цифрового пристрою ніколи не реалізуються. Частково певну функцію можна зробити повністю визначеною (доопределіть), приписав байдужим розділами будь-які значення функції: fi = 0 або 1. Зазвичай довизначення функції проводиться таким чином, щоб спростити її алгебраїчне вираз і практичну реалізацію.

Логічні функції більшого числа змінних можна уявити у вигляді композиції функцій меншого числа змінних

F (A, B, C ,..., N) = AF0 (O, B, C ,..., N) + AF1 (1, B, C ,..., N)

де А - виділяється змінна, функції F0 (0, B, C ,..., N) і F1 (1, B, C ,..., N) виходять з функції F підстановкою значень А = 0 і А = 1. Як виділяється може використовуватися будь-яка змінна. Наприклад:

F = AB + ACD + DE = A (B + DE) + A (CD + DE) = AF1 + AF0, F = AB + ACD + DE = D (AB + AC) + D (AB + E) = DF'1 + DF'0

Процес виділення більш простих складових функції називається декомпозицією. Отримані функції F0, F1 можуть піддаватися подальшої декомпозиції. Таким чином, складну логічну функцію можна виконати, послідовно реалізуючи композицію простіших функцій, отриманих шляхом декомпозиції.

2. Можливості програми моделювання Electronics Workbench

2.1 Загальні відомості про Electronics Workbench

Electronics Workbench канадської фірми Interactive Image Technologies розроблена досить давно і в Россі відомі версії 3.0, 4.0, 4.1, 5.0, 5.12 Professional Edition. Програма безперервно розвивається, удосконалюється. Росте бібліотека компонент, вимірювальних приладів, моделюючих функцій. Версії 3.0, 4.0 були 16 р.