План.
1. Мета мінімізації.
2. Мінімізація функцій за допомогою законів та аксіом АЛ.
3. Мінімізація функцій за допомогою карт Вейча (Карно).
1. Метою мінімізації логічної функції є зменшення вартості її технічної реалізації. Слід відмітити, що критерій, відповідно до якого виконується мінімізація ФАЛ, залежить як від типу задачі, що вирішується, так і від рівня розвитку технології. Так, в ті часи, коли цифрові пристрої будувалися на дискретних елементах, мінімізація числа цих елементів та числа побудованих на їх основі елементарних логічних вузлів визначала і зменшення вартості технічної реалізації. З появою ВІС та НВІС, вартість яких визначається в основному площею схеми на кристалі і мало залежить від кількості транзисторів та інших елементів, що в неї входить, критерії мінімізації ФАЛ зазнали суттєвих змін. На перше місце при проектуванні самих ІС висувається вимога регулярності внутрішньої структури та мінімізація числа зовнішніх з’єднань навіть за рахунок збільшення кількості елементів та внутрішніх з’єднань. Ці вимоги диктуються вимогами підвищення надійності електронної апаратури.
Однак при проектуванні апаратури із застосуванням ВІС та НВІС вимоги зменшення числа корпусів ІС та їх міжз׳єднань залишаються досить важливими.
Вимоги зменшення кількості елементарних ЛЕ, що входять в пристрій, в нинішній час не втратили своєї актуальності. Пояснюється це все більш широким застосуванням при проектуванні електронної апаратури програмованих логічних НВІС широкого застосування та напівзамовленних
НВІС на основі базових матричних кристалів. Ці ВІС та НВІС, як правило містять окремі нескомутовані між собою елементарні ЛЕ, наприклад 2І-НІ, 2АБО-НІ, або просто набори транзисторів, резисторів та діодів, які можуть бути з’єднані між собою у відповідності із заданим алгоритмом обробки логічних сигналів. Оскільки кількість елементів в одній НВІС задано з технологічних міркувань, то мінімізація ФАЛ за критерієм зменшення числа елементів, що використовуються, дозволяє на одному кристалі вирішити більш складні задачі логічної обробки сигналів, тобто зменшити кількість потрібних ІС та зв’язків між ними. Це зменшує вартість та підвищує надійність електронної апаратури.
2. Логічні функції мінімізуються за допомогою аксіом та законів АЛ. При цьому отримують спрощені логічні вирази, на основі яких розробляються логічні схеми.
F=x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 = x2x3 (x1+x1) + x1x2x3 + x1x2x3 = x2x3 + x1x2x3 + x1x2x3 = x3(x2 = x1x2) + x1x2x3 = x3 (x2+x2) (x2+x1) + x1x2x3 = x2x3 + x1x3 + x1x2x3 = x2x3 + x1(x3 + x2x3) = x2x3 + x1(x3+x3) (x3+x2) = x2x3 + x1x3 + x1x2.
В процесі мінімізації логічних функцій використовується поняття сумісних термів.
Сумісними мінтермами називаються мін терми, що розрізняються лише однією змінною: в один мін терм вона входить у прямому вигляді, а в другий – в інверсному. Над сумісними мін термами виконують операцію склеювання, в результаті чого формується кон’юнкція, що називають імплікантою
x1x2x3 + x1x2x3 = х2х3 (х1+х1) = х2х3
Рангом мінтерма чи імпліканти називають кількість змінних у мін термі чи імпліканті. При виконанні склеювання імпліканта має на 1-цю менший ранг в порівнянні з мін термами, що склеюються.
3. Мінімізація ФАЛ за допомогою карт Вейча (Карно). Даний метод базується на табличному представленні функції. Він широко застосовується при ручній, без застосування ЕОМ, мінімізації ФАЛ, число змінних в якій зазвичай не перевищує п’яти.
Карта Вейча (Карно) – прямокутна таблиця, кількість клітин в якій для ФАЛ n змінних дорівнює 2n. Стовбці і рядки карти розмічаються таким чином, щоб у поряд розташованих стовбцях і рядках знаходилися сумісні терми. У клітинах карти записуються значення функції привідповідних наборах змінних.
Розглянемо карту Карно для 2-х змінних.
2n=4
0 1
АВ АВ
АВ АВ
0
1
Розглянемо карту Карно для 3-х змінних
2n=8
0 0 0 1 1 1 1 0
АВС АВС АВС АВС
АВС АВС АВС АВС
0
1
Розглянемо карту Карно для 4-х змінних
2n=16
0 0 0 1 1 1 1 0
0 0
0 1
1 1
1 0
Хоча карта Карно на площині зображується у вигляді прямокутника, на справді вона має форму тора, таким чино верхній і нижній рядок та крайні лівий і правий стовбці теж мають сумісні терми.
А В С F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
0 0 0 1 1 1 1 0
1 1
1
0
1
При мінімізації функції поряд розташовані одиниці охоплюються овалами, при чому кількість одиниць в овалі повинна бути кратною 2к, де к = 1,2,3…
F = АС + АВС – результуюча імпліканта.
АВС + АВС = АС(В+В) = АС
Правила мінімізації функції чотирьох аргументів.
1. Якщо одиницями заповнені два сусідніх рядка, або два сусідніх стовбці, то результуюча імпліканта буде мати 1-й ранг.
00 01 11 10
1 1 1 1
1 1 1 1
1 1
1 1
00
01
11
10
F=С+В
2. Якщо одиницями заповнені стовбець або рядок з урахуванням тороїдальності карти, результуюча імпліканта буде мати 1-й ранг.
00 01 11 10
1 1 1 1
1 1 1 1
00
01
11
10
F=D
3. Якщо одиницями заповнені 4 поряд розташовані клітини , то результуюча імпліканта буде мати 2-й ранг.
00 01 11 10
1
1 1 1 1
1
1
00
01
11
10
F=АВ+СD
00 01 11 10
1 1 1
1 1
1 1 1
00
01
11
10
F=СА+ВD
4. Якщо одиниці знаходяться у двох поряд розташованих клітинах, то результуюча імпліканта буде мати 3-й ранг.
00 01 11 10
1 1
1 1 1
00
01
11
10
F=ВD+АСD