Минимизация булевых функций методом Мак-Класки

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

Идея метода Мак-Класки заключается в следующем: конституенты 1 в СДНФ представляются не в буквенном виде, а виде условных чисел – номеров соответствующих конституент.

Пример 2.4. =

= 0000 0001 0010 0111 1001 1010 1110 1111 =

= 0 1 2 7 9 10 14 15 = (0, 1, 2, 7, 9, 10, 14, 15).

При этом оказывается, что переменные имеют вес: ABCD 8421.

Давайте посмотрим, какие конституенты 1 склеиваются. Мы говорили, что могут склеиваться те, у которых число отрицаний отличается на 1.

= 0000 0001 = 0 1= ; 0 1 = (0, 1), (1), т.е. склеиваются конституенты 0 и 1, а в скобках указывается разность, какая переменная исключается (D).

Еще пример: 0100 0110 = 4 6 = (4, 6), (2) – склеиваются по C.

Вводится понятие индекса. Индексом целого числа называется количество 1 в двоичном представлении этого числа: 7 = 0111 – индекс равен 3, 0000 – индекс равен 0 и т.д. Если конституенты 1 склеиваются, то их индексы отличаются на 1, а в скобках должно быть число (их разности), равное целой степени 2 (по какой переменной склеиваются).

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

Так конституенты 1 с номерами 4 и 3, равными 0100 и 0011, не склеиваются, хотя их разности равны 1.

Все конституенты 1 разбиваются на группы в соответствии с индексом и располагаются в порядке их возрастания. Группы отделяются друг от друга чертой. Склеиваться могут конституенты только соседних групп.

Пример 2.5. (0, 1, 3, 4, 5, 6, 10, 11, 12, 14, 15). Минимизировать методом Мак-Класки.

Прежде всего группируем номера конституент в порядке роста их индексов. В нулевую группу попадает номер 0. В 1 группу – конституенты с индексом 1 (1 и 4), во 2 группу – конституенты с индексом 2 (3 = 0011, 5 = 0101, 6 = 0110, 10 = 1010 и 12 = 1100), в 3 группу – конституенты с индексом 3 (11 = 1011 и 14 = 1110), в 4 группу – конституенты с индексом 4 (15 = 1111). В результате имеем следующее разбиение конституент функции на группы:

В силу рассмотренного правила, склеивание возможно между номерами конституент соседних групп, т.е. 0 и 1, 1 и 2, 2 и 3 и 3 и 4. Никакие другие склеивания невозможны. Необходимо также, чтобы число, стоящее в следующей группе, было больше соответствующего числа в предыдущей группе, причем больше на целую степень 2. Например, 0 склеивается с 1, записывается пара (0,1) и рядом их разность: 1 – 0 = 1. Запись выглядит так: (0, 1), (1).

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

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

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

Возьмем, например, пары (0, 1),(1) и (1, 3), (2). 0 и 1 склеиваются, 1 и 3 тоже, но разности у них не одинаковы – поэтому склеивание невозможно (у первой пары нет переменной D, у второй пары нет переменной С – они, конечно, и не могут склеиваться). В результате склеивания пишем уже четверки (0, 1, 4, 5) и две разности (1, 4), т.е. в результирующем выражении нет 2-х переменных B и D. После завершения этих склеиваний получают, если возможно, восьмерки, при этом должны совпадать уже разности в скобках у четверок и т.д.

Обозначим пары и четверки, которые не участвовали в склеивании, латинскими буквами. Тогда . При получении выражения для импликант а, в, с и т.д., поступают следующим образом: берут любую из конституент 1, участвующих в операции склеивания, и исключают переменные, указанные в разностях. Например, для импликанты а получим: 0001= (разность 2). Эта разность говорит о том, из выражения необходимо исключить переменную с весом 2, т.е. С. Тогда а = .

Аналогично получим: для в : 0011= (разность 8), в = , для с: 0001= (разности 1 и 4), с = , для d : 0100 = (разности 2 и 8), d = , для e: 1111=AВCD (разности 1 и 4), e = АС. В результате получим: .

Дата добавления: 2015-07-26; просмотров: 191; Нарушение авторских прав

Мы поможем в написании ваших работ!