Оценка сложности реализации булевых функций,
минимизация недоопределенных булевых функций
ЛЕКЦИЯ 4
--------
План
1.Оценка сложности реализации булевых функций
2.Минимизация недоопределенных булевых функций.
4.1 Оценка сложности реализации булевых функций
Приблизительную оценку сложности реализации функции можно дать по
ДНФ,подсчитав коэффициент сложности Кс как сумму общего количества пе-
ременных, вошедших в импликанты, и количества импликант. Например ,
для функции y= x4x1 + x4x2 + x4x3 + x3x2x1 получим Кс=9+4=13.
4.2. Минимизация недоопределенных булевых функций.
-------------------------------------------------
Функция от n переменных называется недоопределенной(НОЛФ),если она
задана не на всех 2^n наборах. Задача минимизации такой функции заклю-
чается в оптимальном доопределении, которое позволило бы покрыть рабо-
чие наборы минимальным количеством прямоугольников Карно, каждый из
которых имел бы максимальную площадь.
Задача 4.1.
-----------
Найти минимальную форму функции y, представленной на рис.4.1.
\ х2х1
х4х3 \
\ 00 01 11 10
----¬---¬---¬---¬
00¦ +¦ 1¦ +¦ 1 ¦
¦---¦---¦---¦---¦
01¦ -¦ -¦ 0¦ - ¦
¦---¦---¦---¦---¦
11¦ -¦ 0¦ -¦ - ¦
¦---¦---¦---¦---¦
10¦ +¦ 1¦ +¦ + ¦
L----------------
Рис.4.1. Решение задачи 4.1.
Доопределение РН отмечено знаком '+',доопределение ЗН - знаком
'-'.В результате доопределения получим МДНФ: y = x3'.
\ х2х1 \ х2х1 \ х2х1
х4х3 \ х4х3 \ х4х3 \
\ 00 01 11 10 \ 00 01 11 10 \ 00 01 11 10
----¬---¬---¬---¬ ----¬---¬---¬---¬ ----¬---¬---¬---¬
00¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 00¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 00¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦
¦---¦---¦---¦---¦ ¦---+---¦---¦---¦ ¦---+---¦---¦---¦
01¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 01¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 01¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦
¦---¦---¦---¦---¦ ¦---¦---¦---¦---¦ ¦---¦---¦---¦---¦
11¦ - ¦ + ¦ + ¦ - ¦ 11¦ + ¦ + ¦ + ¦ + ¦ 11¦ - ¦ - ¦ + ¦ + ¦
¦---¦---¦---¦---¦ ¦---¦---¦---¦---¦ ¦---¦---¦---¦---¦
10¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 10¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 10¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦
L---------------- L---------------- L----------------
y1 = x1 y2 = x3 y3 = x4x2
Для карт Карно на 6 переменных удобно использовать двойную коди-
ровку:двоичную и восьмеричную.Тогда при заполнении карт нужно исполь-
зовать 8-ичную кодировку,а для минимизации - двоичную.
После проведения минимизации необходимо проверить результат.Для
этого в полученное выражение нужно поочередно подставить значения всех
заданных входных наборов и убедиться в том,что значения функции соот-
ветствуют таблице истинности.
ДОМАШНЕЕ ЗАДАНИЕ 1
Логические функции заданы 8-ичными наборами.
ПОЛФ
1.00,01,05,04,10,11,13,17,15,14,31,33,37,35,50,51,55,54,40,41,45,
44 - 1. Kc = 7.
2.04,06,02,00,14,16,12,10,34,35,31,30,24,25,21,20,64,65,61,60,74,
75,71,70 - 1. Kc = 7.
НОЛФ
1.70,65,32,01,04 - 1.
53,17,05 - 0. Kc = 7.
2.51,75,32,17 - 1.
63,24 - 0. Kc = 5.
Практическая работа(семинар).
1.Построить дешифратор 2-10-кода в семисегментный.
2.Использовать генератор псевдослучайных чисел для синтеза логи-
ческих функций от 6 переменных.Количество РН и ЗН варьировать.