Мінімізація логічних функцій
ЛАБОРАТОРНА РОБОТА
Мінімізація логічних
функцій
1. Мета роботи: засвоїти типові прийоми
при логічному проектуванні цифрових блоків - навчитися мінімізувати логічні
функції, задані різними способами.
. Методичні вказівки
Виконання даної роботи відбувається у два етапи і
здійснюється після проходження лекційного курсу з теми. На першому етапі
завдання роботи виконуються в лабораторії під керівництвом викладача, на
другому етапі індивідуальні вхідні дані обробляються вдома.
. Короткі теоретичні відомості
Важливим різновидом систем обробки сигналів є так
звані цифрові системи (ЦОС). Такі системи мають n двійкових входів, l двійковий
внутрішній стан та m двійкових виходів. Кількість варіантів входів, внутрішніх
станів та виходів - кінцеві множини, тому такі системи називають кінцевими
автоматами (КА), або цифровими автоматами (ЦА).
Інформаційним ядром кожного ЦА є так звана комбінаційна
схема (КС), яку можна вважати за ЦА без внутрішньої пам’яті, бо комірки
пам’яті (КП) мають уніфіковану функцію - запам’ятовувати сигнал на вході та
видавати цей сигнал на вихід.
Комбінаційні схеми реалізують системи логічних
функцій (ЛФ), які складаються з m окремих ЛФ (за кількістю виходів), кожна з
яких залежить від n двійкових аргументів (за кількістю входів). Вони задаються
так званими таблицями істинності (ТІ), які складаються з двох частин -
вхідної (n стовбців, 2n рядків) та вихідної (m стовпчиків, 2n
рядків). Нижче наведений зразок ТІ для КС із n входами та m виходами.
Таблиця істинності для КС із n входами та m
виходами
|
Вхідна
частина
|
Вихідна
частина
|
|
Xn
|
…….
|
X3
|
X2
|
X1
|
Y1
|
Y2
|
…
|
Ym
|
|
0
|
|
0
|
0
|
0
|
0
|
1
|
|
0
|
|
0
|
|
0
|
0
|
1
|
1
|
1
|
|
1
|
|
0
|
|
0
|
1
|
0
|
0
|
0
|
|
0
|
|
0
|
|
0
|
1
|
1
|
0
|
1
|
|
1
|
|
0
|
|
1
|
0
|
0
|
0
|
0
|
|
1
|
|
0
|
|
1
|
0
|
1
|
1
|
0
|
|
0
|
|
0
|
|
1
|
1
|
0
|
1
|
1
|
|
1
|
|
0
|
|
1
|
1
|
.
|
.
|
|
.
|
|
.
|
.
|
.
|
.
|
.
|
.
|
.
|
|
.
|
|
|
|
|
|
.
|
.
|
|
.
|
|
1
|
|
1
|
1
|
1
|
0
|
1
|
|
0
|
Зручно розглядати кожний вихід КС, тобто кожний стовпчик
вихідної частини ТІ й, отже, кожну ЛФ від n аргументів окремо. При цьому кожна
ЛФ однозначно визначається кількістю аргументів n і її номером N (безпосередньо
у двійковій або будь-якій іншій системі числення) у множині ЛФ із n
аргументами, кількість яких складає 
. Для визначеності, у стовпчику ТІ, який відповідає ЛФ,
верхній рядок буде відповідати молодшому розряду числа N, тобто номера ЛФ, а
весь відповідний стовпчик є двійковим номером ЛФ. Уведена нумерація дозволяє
компактно описувати всю множину L(n), а за номером ЛФ легко відновити для неї
ТІ.
Крім табличного й нумераційного завдання ЛФ застосовуються
різні аналітичні форми подання ЛФ. З огляду на наявність різних функціонально
повних систем ЛФ, одну і ту саму ЛФ, задану, наприклад, у вигляді ТІ, можна
записувати по-різному. Проте, у булєвій алгебрі існують деякі канонічні форми
запису ЛФ. Серед них найбільш уживана диз'юнктивна нормальна форма (ДНФ).
Диз’юнктивною нормальною формою ЛФ називається
диз’юнкція будь-якої кінцевої множини попарно різних елементарних кон’юнкцій.
Елементарною кон’юнкція називається, якщо вона є добутоком попарно різних
аргументів, над частиною яких можуть бути поставлені знаки інверсії. До
елементарних кон’юнкцій відносять константу 1, а також вирази, що складаються
із однієї букви.
Серед усіляких ДНФ, які відповідають заданій ЛФ,
варто виділити так звану досконалу диз’юнктивну нормальну форму (ДДНФ). ДДНФ
являє собою диз’юнкцію, що складається тільки з повних кон’юнкцій, тобто
кон’юнкцій, що містять усі n аргументів у прямій або інверсній формі. Зазначені
повні кон’юнкції ще називаються конституентами одиниці.
,
цифровий логічний сигнал
де знак ~ позначає тут і далі наявність, або
відсутність знака інверсії.
Для будь-якої конституенти одиниці існує один і
тільки один набір аргументів, на якому ця конституента згортається в одиницю.
Будь-яка ЛФ має одну й тільки одну ДДНФ, яку
можна записати у вигляді:
,
де Kj - конституенти одиниці, що
згортаються в одиницю на j-ому наборі аргументів; Сj - коефіцієнти,
рівні 0 або 1, відповідно до того, задається ЛФ на j-ому наборі одиницею або
нулем.
. Програма виконання роботи
Використовуючи знання, отримані в курсі лекцій з
предмету «Цифрова обробка сигналів», виконати наступні завдання:
Спростити заданий булєвий вираз:
За заданим десятковим номером М логічної функції
та кількості її аргументів n:
·
побудувати таблицю істиності ЛФ;
·
мінімізувати ЛФ за допомогою карти Карно;
|
Номер
варінту
|
К-сть
аргум. N
|
Номер
ЛФ М
|
Номер
варінту
|
К-сть
аргум.n
|
Номер
ЛФ М
|
|
1
|
4
|
17485
|
11
|
4
|
12088
|
|
2
|
5
|
115749
|
12
|
5
|
104616
|
|
3
|
4
|
25349
|
13
|
12742
|
|
4
|
5
|
230179
|
14
|
5
|
1243112
|
|
5
|
4
|
24142
|
15
|
4
|
16898
|
|
6
|
5
|
679543
|
16
|
5
|
1157117
|
|
7
|
4
|
15790
|
17
|
4
|
63540
|
|
8
|
5
|
653219
|
18
|
5
|
229190
|
|
9
|
4
|
27151
|
19
|
4
|
60792
|
|
10
|
5
|
797192
|
20
|
5
|
158797
|
За заданою множиною М1 одиничних наборів, множині М0 нульових
наборів логічної функції та кількості її аргументів n:
·
побудувати таблицю істинності ЛФ;
·
раціонально довизначити ЛФ за допомогою карти Карно;
·
записати МДНФ у базисах І-НІ та АБО-НІ;
·
сформувати схеми реалізації ЛФ у цих базисах;
·
отримати абсолютно-мінімальну форму.
|
Ном.
вар.
|
Кіл.
арг. n
|
Множ.
М1
|
Множ.
М0
|
Ном. вар.
|
Кіл.
арг. n
|
Множ.
М1
|
Множ.
М0
|
|
1
|
4
|
0,2,7,6
|
3,9,15,21,30
|
11
|
4
|
1,9,12,19,30
|
3,7,13,20,27
|
|
2
|
5
|
2,9,13,15
|
1,3,10,12
|
12
|
5
|
4,8,12,15
|
|
3
|
4
|
1,3,9,29
|
2,11,13,15,22
|
13
|
4
|
2,8,21,24,31
|
4,6,22,25,30
|
|
4
|
5
|
1,7,12,13
|
2,3,6,14
|
14
|
5
|
0,7,9,12
|
3,5,10,14
|
|
5
|
4
|
2,9,17,20,21
|
5,6,14,30,31
|
15
|
4
|
5,19,22,24,30
|
3,4,20,23,30
|
|
6
|
5
|
0,3,5,15
|
2,6,12,14
|
16
|
5
|
1,3,8,15
|
2,6,10,12
|
|
7
|
4
|
3,5,19,20,31
|
4,7,21,22,30
|
17
|
4
|
1,9,20,30,31
|
3,13,17,23,24
|
|
8
|
5
|
3,7,10,11
|
2,8,12,14
|
18
|
5
|
3,6,10,11
|
2,8,9,15
|
|
9
|
4
|
2,4,20,25,30
|
3,5,18,26,27
|
19
|
4
|
2,10,12,20,21
|
2,6,13,23,25
|
|
10
|
5
|
5,12,13,15
|
3,6,11,14
|
20
|
5
|
2,3,9,10
|
1,7,11,12
|
5. Склад звіту
Звіт із лабораторної роботи повинен містити:
· титульний лист;
· мету роботи;
· формулювання
індивідуального завдання;
докладне викладення розрахунків спрощення
заданого булєвого виразу та результат спрощення;
таблицю істинності, карту Карно, записати
спрощений вираз;
таблицю істинності, довизначену карту Карно,
МДНФ, абсолютно-мінімальну форму;
· висновки.
6. Зразок виконання роботи
Мета роботи: навчитися спрощувати
булєві рівняння, будувати таблицю істинності ЛФ, мінімізувати ЛФ за допомогою
карт Карно, синтезувати логічні схеми в базис І-НЕ і АБО-НІ.
Завдання:
Варіант №.
Спростити заданий булєвий вираз:
За заданим номером М логічної функції і числу її
аргументів n (кількість аргументів - 4, номер ЛФ - 27151) побудувати таблицю
істинності
_
Sдднф = 8*4 = 32
За заданою множиною М1 одиничних наборів,
множиною М0 нульових наборів логічних функцій і числу її аргументів n
побудувати таблицю істинності ЛФ:= 5{2,4,20,25,30}{3,5,18,26,27}
f(x) = 
дднф = 5*5 = 25
Раціонально довизначати ЛФ за допомогою карти
Карно.
Висновок: під час виконання
лабораторної роботи я ознайомилася з методами спрощення логічних функцій, навчилася
формувати таблиці істинності ЛФ та карти Карно, отримала знання про спрощення
булєвих виразів різними методами.