Дайте загальну характеристику мінімізації булевих функцій

Мінімізація булевих функцій

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

Способи мінімізації булевих функцій:

· метод Блейка-Порецького;

· метод Нельсона;

· метод Карта Карно.

Метод Блейка-Порецького

Метод дозволяє отримувати скорочену ДНФ булевої функції f з її довільної ДНФ. Базується на застосуванні методу загального склеювання Ax v Bẍ = Ax v Bẍ v AB, правильність якого легко доводиться: Ax = Ax v ABx; Bẍ = Bẍ v ABẍ. З цього слідує: Ах v Вẍ = Ах v АВх v Вẍ v АВẍ = Ах V Вẍ V АВ. В основу методу покладено наступне твердження: якщо в випадковій ДНФ булевій функції f зробити всі можливі узагальнені склеювання, а потім виконати всі поглинання, то в результаті вийде скорочена ДНФ функція f.
Приклад: Булева функція f задана випадковою ДНФ: f = ẍ1ẍ2 v x1ẍ2ẍ3 v x1x2. Знайти методом Блейка - Порецкого скороченну ДНФ функцїї f. Проводимо узагальнені склеювання. Легко бачити, що перший і другий елемент заданої ДНФ допускають узагальнене склеювання по змінній х1. В результаті склеювання маємо:

ẍ1ẍ2 v x1ẍ2ẍ3 = ẍ1ẍ2 v x1ẍ2ẍ3 v ẍ2ẍ3

Перший і третій елемент вихідної ДНФ допускають узагальнене склеювання як по змінній х1, так і по х2. Після склеювання по x1 маємо:

ẍ1ẍ2 v x1x2 = ẍ1ẍ2 v x1x2 v ẍ2x2 = ẍ1ẍ2 v x1x2.

Після склеювання по x2 маємо:

ẍ1ẍ2 v x1x2 = ẍ1ẍ2 v x1x2 v ẍ1x1 = ẍ1ẍ2 v x1x2.

Другий і третій елемент ДНФ допускають узагальнене склеювання по змінній х2. Після склеювання отримуємо:

x1ẍ2ẍ3 v x1x2 = x1ẍ2ẍ3 v x1x2 v x1x3.

Виконавши останнє узагальнене склеювання, приходимо до ДНФ:

f = ẍ1ẍ2 v x1ẍ2ẍ3 v ẍ2ẍ3 v x1x2 v x1ẍ3.

Після виконання поглинань отримуємо:

f = ẍ1ẍ2 v ẍ2ẍ3 v x1x2 v x1ẍ3.

Спроби подальшого застосування операції узагальненого склеювання і поглинання не дають результату. Отже, отримана скорочена ДНФ функції f. Далі завдання пошуку мінімальної ДНФ вирішується за допомогою імплікаційної матриці точно так само, як у методі Квайна. "

Метод Нельсона

Метод дозволяє отримати скорочену ДНФ булевої функції f з її випадкової КНФ. Якщо у довільній КНФ булевої функції розкрити всі дужки і провести всі поглинання, то в результаті буде отримана скорочена ДНФ булевої функції.
Приклад:

f = (x1 v ẍ2)(ẍ1 v x3)(x1 v x2 v ẍ3)

f = (x1x3 v ẍ1ẍ2 v ẍ2x3)((x1 v x2 v ẍ3))=

Знайдемо скорочену ДНФ: = x1x3 v x1x2x3 v ẍ1ẍ2ẍ3 v x1ẍ2x3
Зробимо поглинання: f = x1x3 v ẍ1ẍ2ẍ3 і виходить скорочена ДНФ.

 

Дайте загальну характеристику цифрових мікросхем

Мікросхе́ма, інтегральна мікросхема (англ. integrated circuit) — електронна схема, що реалізована у вигляді напівпровідниковогокристалу (чипу) та виконує певну функцію. Винайдена у 1958 році американськими винахідниками Джеком Кілбі та Робертом Нойсом.

Чіп — напівпровідникова структура, на поверхні якої сформовані контактні площинки.^[1] Часто під інтегральною схемою (ІС) розуміють власне кристал або плівку з електронною схемою, а під мікросхемою (МС) — ІС в корпусі.

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

Перша радянська напівпровідникова мікросхема була створена у 1961 році, в Таганрозькому радіотехнічному інституті, в лабораторії Л. Н. Колесова.

 

Ступінь інтеграції

Залежно від ступеня інтеграції застосовують наступні назви інтегральних схем:

· мала інтегральна схема (МІС) — до 100 елементів у кристалі,

· середня інтегральна схема (СІС) — до 1000 елементів у кристалі,

· велика інтегральна схема (ВІС) — до 10 тис. елементів у кристалі,

· надвелика інтегральна схема (НВІС) — понад 10 тис. елементів у кристалі.

Цифрові інтегральні мікросхеми мають ряд переваг в порівнянні з аналоговими:

· Зменшене енергоспоживання пов'язане із застосуванням в цифровій електроніці імпульсних електричних сигналів. При отриманні і перетворенні таких сигналів активні елементи електронних пристроїв (транзисторів) працюють в «ключовому» режимі, тобто транзистор або «відкритий» — що відповідає сигналу високого рівня (1), або «закритий» — (0), в першому випадку на транзисторі немає падіння напруги, в другому — через нього не йде струм. У обох випадках енергоспоживання близьке до 0, на відміну від аналогових пристроїв, в яких велику частину часу транзистори знаходяться в проміжному (резистивному) стані.

· Висока завадостійкість цифрових пристроїв пов'язана з великою відмінністю сигналів високого (наприклад, 2,5-5 В) і низького (0-0,5 В) рівня. Помилка можлива при таких перешкодах, коли високий рівень сприймається як низький і навпаки, що маловірогідно. Крім того, в цифрових пристроях можливе застосування спеціальних кодів, що дозволяють виправляти помилки.

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