Практическое задание: Мінімізація логічних функцій

Мінімізація логічних функцій

ЛАБОРАТОРНА РОБОТА

Мінімізація логічних функцій

1. Мета роботи: засвоїти типові прийоми при логічному проектуванні цифрових блоків - навчитися мінімізувати логічні функції, задані різними способами.

. Методичні вказівки

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

. Короткі теоретичні відомості

Важливим різновидом систем обробки сигналів є так звані цифрові системи (ЦОС). Такі системи мають n двійкових входів, l двійковий внутрішній стан та m двійкових виходів. Кількість варіантів входів, внутрішніх станів та виходів - кінцеві множини, тому такі системи називають кінцевими автоматами (КА), або цифровими автоматами (ЦА).

Інформаційним ядром кожного ЦА є так звана комбінаційна схема (КС), яку можна вважати за ЦА без внутрішньої пам’яті, бо комірки пам’яті (КП) мають уніфіковану функцію - запам’ятовувати сигнал на вході та видавати цей сигнал на вихід.

Комбінаційні схеми реалізують системи логічних функцій (ЛФ), які складаються з m окремих ЛФ (за кількістю виходів), кожна з яких залежить від n двійкових аргументів (за кількістю входів). Вони задаються так званими таблицями істинності (ТІ), які складаються з двох частин - вхідної (n стовбців, 2ⁿ рядків) та вихідної (m стовпчиків, 2ⁿ рядків). Нижче наведений зразок ТІ для КС із 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 аргументів у прямій або інверсній формі. Зазначені повні кон’юнкції ще називаються конституентами одиниці.

,

цифровий логічний сигнал

де знак ~ позначає тут і далі наявність, або відсутність знака інверсії.

Для будь-якої конституенти одиниці існує один і тільки один набір аргументів, на якому ця конституента згортається в одиницю.

Будь-яка ЛФ має одну й тільки одну ДДНФ, яку можна записати у вигляді:

,

де K_j - конституенти одиниці, що згортаються в одиницю на j-ому наборі аргументів; С_j - коефіцієнти, рівні 0 або 1, відповідно до того, задається ЛФ на j-ому наборі одиницею або нулем.

. Програма виконання роботи

Використовуючи знання, отримані в курсі лекцій з предмету «Цифрова обробка сигналів», виконати наступні завдання:

Спростити заданий булєвий вираз:

 

1. 11.
2. 12.
3. 13.
4. 14.
5. 15.
6. 16.
7. 17.
8. 18.
9. 19.
10. 20.

За заданим десятковим номером М логічної функції та кількості її аргументів 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

Раціонально довизначати ЛФ за допомогою карти Карно.

Висновок: під час виконання лабораторної роботи я ознайомилася з методами спрощення логічних функцій, навчилася формувати таблиці істинності ЛФ та карти Карно, отримала знання про спрощення булєвих виразів різними методами.