Теория автоматов. Аралбаев Т.З - 20 стр.

    4.  Практическое занятие №4. Минимизация логических
функций по картам Карно


         Минимизация ЛФ необходима для построения комбинационных схем
цифровых автоматов минимальной сложности.
        Минимизация ДНФ и КНФ по картам Карно представляет собой процесс,
аналогичный минимизации ЛФ, представленных в аналитическом виде с
использованием правил преобразования формул, рассмотренных на практическом
занятии № 2, в частности, правил склеивания.
        Известно, что каждая клетка карты Карно, заполненная единицей,
соответствует элементарной конъюнкции r–го ранга. Двум соседним клеткам
карты Карно, расположенным в одном столбце или строке, заполненными
единицами, соответствуют ЭК, отличающиеся лишь в одном разряде. К этим
клеткам можно применить правило склеивания. Область (покрытие),
соответствующая этим двум клеткам, называется смежной и может быть
аналитически описана ЭК ранга (r-1), в которой отсутствует элемент (x),
меняющий своѐ значение при переходе из одной клетки в другую. Если покрытие
включает в себя 21, 22 или же любое другое число клеток, равное 2m, то ЭК,
описывающие это покрытие, содержит число элементов входного набора, равное
n – m. Покрытие на карте Карно обводится контуром. Аналогично определяются
контуры при минимизации КНФ.
        Процесс минимизации ДНФ (КНФ) ЛФ может быть описан следующим
алгоритмом:
        1) определить множество возможных покрытий карты Карно;
        2) из этого множества последовательно в порядке убывания m выделяем
контурами покрытие до тех пор, пока не “покроем” все клетки карты Карно;
        3) оптимизируем покрытие, руководствуясь следующим принципом:
        необходимо наименьшим числом контуров, каждый из которых
охватывает как можно большую область смежных клеток, “покрыть” все клетки,
содержащие единицы (или нули);
        4) определим вид тупиковой ДНФ (КНФ). Для этого определяем
дизъюнкцию (конъюнкцию) ЭК (ЭД) по следующему правилу: переменная х
        включается в ЭК (ЭД) в прямом виде, если эта переменная имеет значение
1 (0) на всех клетках области. Соответственно, переменная х включается в ЭК
(ЭД) в инверсном виде, если эта переменная имеет значение 0 (1) на всех клетках
области.
         В результате минимизации возможно получение нескольких ТДНФ
(ТКНФ) одинаковой сложности.
        При минимизации частичных ЛФ на карте Карно первоначально в клетках,
соответствующих неопределѐнным наборам ЛФ, ставится прочерк. При
определении контуров покрытия в зависимости от необходимости эти клетки
доопределяется единицами или нулями. В остальном процесс минимизации
аналогичен процессу для полностью определенных ЛФ.

20