Материал: Захаров, Сайфутдинов - Вычислительная техника

Рис. 2.4. Структура карты Карно для функции

Ячейки, в которых функция принимает значение 1, заполняются единицами. Процесс минимизации заключается в формировании прямоугольников, содержащих по 2k ячеек, где k – целое число. В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям. Например, на рис. 2.4 объединены ячейки с координатами 001 и 101. При объединении этих ячеек образовался прямоугольник, в котором х1 изменяет свое значение. Следовательно, оно исчезает при склеивании соответствующих элементарных произведений х1 х2 х3 и х1 х2 х3 . Ячейки, расположенные в первой строке, содержат 1 и являются соседними. Поэтому они объединяются в прямоугольник, содержащий 22 = 4 ячейки. Переменные х2 и х3 в пределах прямоугольника меняют свое значение, следовательно, они исчезнут из результирующего элементарного произведения. Переменная х1 является неизменной и равной нулю. Таким образом, элементарное произведение, полученное в результате объединения ячеек первой строки, содержит лишь элемент х1 . Это следует из того, что четырем ячейкам первой строки соответствует сумма четырех элементарных произведений:

х1 х2 х3 х1 х2 х3 х1 х2 х3 х1 х2 х3

х1 х2 (х3 х3 ) х1 х2 (х3 х3 ) х1 х2 х1 х2 х1 (х2 х2 ) х1.

Совокупность прямоугольников, покрывающих все единицы, называют покрытием. Одна и та же ячейка может покрываться несколько раз. Итак, можно сделать следующие выводы:

1.Формула, получающаяся в результате минимизации логической функции с помощью карт Карно, содержит сумму стольких элементарных произведений, сколько прямоугольников имеется в покрытии.

2.Чем больше ячеек в прямоугольнике, тем меньше переменных содержится в соответствующем ему элементарном произведении.

26

Несмотря на то, что карты Карно изображаются на плоскости, соседство ячеек устанавливается на поверхности тора или цилиндра. Верхняя и нижняя границы карты Карно как бы «склеиваются», образуя цилиндр. При склеивании боковых границ получается тороидальная поверхность. Поэтому в примере (рис. 2.5) ячейки с координатами 1011 и 0011 являются соседними и объединяются в прямоугольники. Действительно, указанным ячейкам соответствует сумма элементарных произведений

х1 х2 х3 х4 х1 х2 х3 х4 х2 х3 х4 (х1 х1 ) х2 х3 х4 .

Рис. 2.5. Карта Карно для функции четырех переменных

Аналогично объединяются и остальные четыре единичные ячейки. В результате их объединения получаем:

х1 х2 х3 х4 х1 х2 х3 х4 х1 х2 х3 х4 х1 х2 х3 х4х2 х3 х4 (х1 х1 ) х2 х3 х4 (х1 х1 ) х2 х4 (х3 х3 ) х2 х4 .

Поэтому окончательно f(x1, x2, x3, x4) = х2 х3 х4 х2 х4 .

Рассмотренные примеры позволяют сформулировать последовательность действий, выполняемых при минимизации логических функций с использованием карт Карно.

1.Изображается таблица для n переменных и производится разметка ее сторон.

2.Ячейки таблицы, соответствующие набором переменных, обращающих функцию в 1, заполняются единицами, остальные ячейки – нулями.

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

27

Качество минимизации оценивается коэффициентом покрытия: k = m/s,

где m – общее количество прямоугольников; s – суммарное количество покрытых ячеек. Покрытие считается тем лучше, чем меньше его коэффициент k.

2.7. Неполностью определенные логические функции

При рассмотрении двоично-десятичных кодов мы отметили, что из 16 возможных комбинаций используются только 10, а остальные комбинации запрещены и возникать не должны. Если каждому разряду поставить в соответствие двоичную переменную, то для двоично-десятичных кодов получим шесть запрещенных комбинаций переменных. Они приведены в табл. 2.7. Если функция имеет запрещенные наборы переменных, то ее значения на указанных наборах не определены и в таблице истинности отмечаются знаком *. Например, в таблице для трех переменных представлена функция (табл. 2.8), имеющая три запрещенных набора переменных.

Двоичные функции, значения которых определены не для всех наборов входных переменных, называются неполностью определенными. На карте Карно ячейки, соответствующие запрещенным наборам переменных, также отмечаются знаком * (рис. 2.6). При минимизации неполностью определенной функции ее следует доопределить, т. е. неопределенные значения ячеек карты Карно произвольным образом заменить единицами или нулями.

Рис. 2.6. Карта Карно для функции трех переменных

На рис. 2.7 показана функция f1(x1, x2, x3), все значения * которой заменены единицами. Доопределенная функция имеет вид f1(x1, x2, x3) = х1 x3 (не зависит от х2).

28

Рис. 2.7. Замена знаков * функции f1(x1,x2,x3) единицей

Если крайние ячейки верхней строки карты Карно дополнить нулями (рис. 2.8), то получим функцию f2, отличную от f1: f2(x1, x2, x3) = x3.

Рис. 2.8. 3амена знаков * нулями в верхней строке

29

Эти примеры показывают возможности упрощения формулы неполностью определенной функции при ее соответствующем доопределении.

Если функция имеет m запрещенных наборов переменных, то может быть выбран тот вариант, при котором формула минимизированной функции будет наиболее простой.

2.8. Логические элементы и логические операции

Одной из основных операций цифровой обработки информации является реализация функциональных зависимостей y = f(х1, х2, ..., хn), ставящих в соответствие каждой комбинации значений двоичных переменных х1, х2, ..., хn значение двоичной переменной у. Функция такого типа называется переключательной или логической. Переключательную функцию можно задать таблицей, в левой части которой перечисляются комбинации значений аргументов, а в правой значения функции.

Переключательную функцию можно задать в аналитической форме, т. е. в виде некоторого выражения, описывающего последовательность элементарных операций над аргументами функций. Совокупность переключательных функций, определяющая набор элементарных операций, достаточных для реализации любой переключательной функции, называется базисом. В большинстве случаев необходимые логические преобразования двоичных сигналов выполняются на базе трех элементарных операций: логического сложения, логического умножения и инверсии.

30