Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf

дексом 2 сравнивается со всеми наборами, имеющими индексы 3, и т. д. На местах склеивания ставятся прочерки.

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

Исходные члены n-го ранга, подвергшиеся склеиванию, обра­ зуют группы с индексом 0— 1, 1—2, 2—3 и т. д., объединяющие члены п—1-го ранга. В соседних группах, т. е. с индексами, отли­ чающимися на единицу (например, 0—1 и 1—2, 1—2 и 2—3 и т. д.), снова производятся все возможные склеивания и так далее, до тех пор, пока дальнейшие склеивания и поглощения становятся невоз­ можными. Члены, полученные в итоге всех возможных склеиваний и поглощений, как и оставшиеся несклеенными, являются про­ стыми импликантами, дизъюнкция которых образует сокращен­ ную дизъюнктивную нормальную форму функции.

Нахождение лишних импликант, как и при минимизации по Куайну, производится с помощью импликантной матрицы. Проце­ дура минимизации по методу Мак-Класки СДНФ отображена в таб­ лице 6-5. Полученные в виде последовательности единиц, нулей и прочерков простые импликанты записываются с помощью букв и их отрицаний: на местах единиц ставится соответствующая буква, на местах нулей — соответствующая буква со знаком отрицания, а прочерки указывают исключенные в процессе склеиваний пере­

незначительно упрощает, в сравнении с алгоритмом Куайна, про­ цедуру минимизации СДНФ. Основным недостатком данного алго­ ритма является громоздкость и возможность допущения ошибок при склеивании.

Усовершенствованный алгоритм Куайна

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

144

3-й шаг. Двигаясь сверху вниз по столбику исходных конъюнк­ ций, выясним поочередно возможность склеивания каждой конъюнк­ ции с другими исходными конъюнкциями. Для этого номер рассмат­ риваемой конъюнкции ka раскладываем на двоичные слагаемые.

Номера конъюнкций kjy склеивающихся в рассматриваемой kg, получаются от поочередного прибавления к номеру последней всех потенциальных двоичных слагаемых, не являющихся слагаемыми ее номера. Если найденные в результате сложения числа имеются среди номеров конъюнкций, стоящих в столбце ниже рассматривае­ мой, то конъюнкции с этими номерами склеиваются с рассматри­ ваемой.

Метод Карно—Вейча

Отыскивание соседних членов и выполнение всех возможных их склеиваний составляют наиболее трудоемкую часть процедуры минимизации СДНФ методами Куайна, Мак-Класки, усовершен­ ствованного алгоритма Куайна.

Достоинства метода Карно—Вейча заключаются в простоте отыскания склеивающихся конституент единицы, выполнения са­ мого склеивания и нахождения всех минимальных форм функции. Данный метод имеет то преимущество перед всеми рассмотренными методами, что он до некоторой степени делает наглядными те упро­ щения, которые можно производить над данной функцией. Для большого числа переменных (больше 4) этот метод становится менее удобным в силу сложности графического изображения.

Первым шагом процедуры минимизации СДНФ по методу Карно—Вейча является получение карты Карно (диаграммы Вейча), представляющей собой определенным образом построенную прямоугольную таблицу. Расположение по Карно членов СДНФ двух-, трех- и четырехместных переключательных функций показано на рис. 36, а, б, в). Пусть конституенты единицы записаны, как

145

указано на рис. 36. В каждом горизонтальном ряду первому слева квадрату геометрически соседними являются второй и четвертый квадраты. Карту Карно следует рассматривать как плоскость, по­ лученную из поверхности тора.

Соседние, а следовательно, могущие быть склеенными конституенты единицы находятся только в соседних квадратах карты Карно. В этом и состоит облегчение отыскания с помощью карт Карно склеивающихся членов СДНФ.

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

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

Каждый правильный прямоугольник объединяет конституенты единицы, к которым можно применить операцию неполного склеи­

146

вания и закон поглощения. В результате их выполнения получаем из каждого правильного прямоугольника один член ДНФ тем мень­ шей длины, чем больше 2 .

Таким образом, накрывая всю совокупность единичных квадратов карты Карно для данной функции минимальным количеством пра­ вильных прямоугольников, мы, во-первых, получаем минималь­ ное количество членов ДНФ, а во-вторых, максимально понижаем ранги этих членов, т. е. мы приходим к получению минимальной формы заданной функции. В элементарную конъюнкцию, соответст­

Рис. 37

Например, если правильный прямоугольник состоит из квадра­ тов К 0 и /<4 (рис. 36, в), то искомой элементарной конъюнкцией яв­

ляется х3ХхХ0, а переменная х 2 исключается, так как внутри этого прямоугольника они имеются как в прямых, так и в инверсных обозначениях. Этот прием позволяет сразу же определить резуль­ тат неполного склеивания с последующим поглощением, которые^ выполняются в отношении конституент единицы каждого из най­ денных правильных прямоугольников данной карты. Результат приведенных выше примеров соответствует следующим выкладкам;

ХзХ^Хо \J х3х2ххх0= ХзХгХо (х2 V *2) V х3х2ххх0\/ х3х.,ххх0= *3*1 *0'.

Х3 Х2 ХхХ0 V * 3 * 2 * 1 * 0 V * 3 * 2 * 1 * 0 V * 3 * 2 * 1 * 0 = * 3 * 2 * 0 (* 1 V * l ) V

V * 3 * 1 * 0 (* 2 V * 2) V * 3 * 1 * 0 (* 2 V * 2) V * 3 * 2 * 0 (* 1 V * 1) V * 3 * 2 * 1 * 0 V

V * 3* 2 * 1 * 0 V * 3 * 2 * 1 * 0 V * 3 * 2 * 1 * 0 = * 3 * 2 * 0 V * 3 * 1 * 0 V * 3 * 1 * 0 V * 3 * 2 * 0 =

= Х3 Х0 (ХоV * 2) V * 3 * 0 (* 1 V * l ) V * 3 * 2 * 0 V * 3 * 1 * 0 V * 3 * 1 * 0 V * 3 * 2 * 0 = * 3 * 0 -

147

При построении карт Карно для функций от 5 и более перемен­ ных теряется их основное достоинство — простота отыскания квад­ ратов с соседними конституентами единицы.

Пример 5. Рассмотрим минимизацию СДНФ функции с помощью карт Карно.

Требуется минимизировать СДНФ функции, заданной таблицей (рис. 37). Из карты Карно видно, что вся совокупность квадратов покрывается четырьмя правильными прямоугольниками:

Рис. 38

Прямоугольнику с г — 8 соответствует член х3 минимальной дизъюнктивной нормальной формы, прямоугольникам с z - -- 4 —

соответственно х 2хх и х 2х 0 и прямоугольнику с г = 2 — х2х1х0.

Рис. 39

Таким образом, приходим к минимальной дизъюнктивной нормаль­ ной форме

Здесь возможны лишь два варианта оптимального накрытия единичных значений функции правильными прямоугольниками.

148

Произведя операции склеивания и поглощения, получим минималь­ ную дизъюнктивную нормальную форму

А{\J лулул'оV X^XiXq.

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

Пример 7. Доопределить функцию на карте Карно и произвести минимизацию (рис. 39).

В данном случае целесообразно приписать обоим условным со­ стояниям синтезируемой схемы значения выхода, равные 1. Мини­

мальная форма будет А = х г V *<>•

Метод Нельсона

Минимальная форма заданной функции данным методом полу­ чается путем преобразований:

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

внуль.

2.С помощью правила де Моргана переходим от полученного выражения к СКНФ функции.

3.Выполнив склеивания членов СКНФ в соответствии с зако­ ном (12) и применив к полученному выражению законы дистрибу­ тивности и поглощения (11), получим сокращенную дизъюнктивную нормальную форму функции.

Для преобразований совершенных нормальных форм функций, представленных в виде записей

где п — ранг членов совершенной нормальной формы; а, Ь, с, . . . , v — номера наборов значений аргументов, на которых функция обращается в 1, удобно пользоваться следующими формулами:

‘ # = ^ 2_,)_£,

d" =~k(2n- l )-«>

В качестве примера, иллюстрирующего метод Нельсона, найдем сокращенную дизъюнктивную нормальную форму функции

F ^ y k l t = 0, 1, 2, 4, 5, 8, 9, 10, 12, 13, 14, 16—31.

149