Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf

Следующий метод подобен известному в булевой алгебре методу Мак-Класки. Зафиксируем порядок аргументов в наборах: индекс аргумента соответствует его порядковому номеру слева. В этом случае каждое элементарное произведение тоже будет иметь свой номер: цифра /-го разряда любого набора равна значению п — / + 1-го ар­ гумента на этом наборе и равна индексу при функции J s.

соответствующего элементарного произведения. Элементарные про­ изведения, склеивающиеся по формулам (2.48) и (2.49), должны иметь все цифры /г-й системы счисления (исключая 0 в случае формулы (2.49)) в том разряде, по которому производится склеивание, при одинаковых остальных цифрах. Процесс склеивания необходимо вести в опреде­ ленном порядке, так как пропуск хотя бы одной операции склеивания дает неверный результат.

Для того чтобы сократить время поиска нужных элементарных про­ изведений, разобьем их на группы с различными индексами. Индекс группы — это количество цифр k — 1 в номере данного элементарного произведения. Число групп не превышает п + 1. Склеиваться могут лишь те элементарные произведения, которые находятся в группе с индексом / и одно — в группе / -f- 1. Для удобства номера элементарных произведений можно перевести из k-й системы счисления в какую-либо другую, например, в десятичную. В этом случае разность между чис­

лами, отличающимися на 1 в /-ом разряде, равна kl. Очевидно, что число, имеющее цифру k — 1 в 1-ом разряде (в k-ou представлении), будет наибольшим и именно оно должно содержаться в группе с боль­

в группе с индексом / — 1; 2) разность между двумя соседними чис­ лами есть степень /г; 3) число с большим индексом больше всех осталь­ ных. Константа полученного элементарного произведения равна наи­ меньшей из констант склеиваемых произведений.

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

Итак, вначале нужно знать номера элементарных произведений в /г-й системе счисления, чтобы разбить их на группы в соответствии с индексами, затем перевести их в десятичную систему счисления и ис­ кать номера склеиваемых элементарных произведений, заключая их

66

в скобки (начиная с большего числа). Справа, тоже в скобках, записы­ вается разность с индексом * (* — пара) или J (J — пара). Дальнейшие склеивания производятся между скобками.

Приведенные в § 2.7 правила поглощения легко интерпретируются для рассматриваемой модификации метода Мак-Класки. Процесс перевода простых импликант из цифровой записи в аналитическую также не труден.

Рассмотрим пример. Выберем функцию, заданную табл. 17, и за­ пишем номера элементарных произведений в системе счисления с осно­

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

Склеиваем элементарные произведения в соответствии с приведен­ ными правилами

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

3 — (64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240) (16У, 64*),

3 — (80, 96, 112, 144, 160, 176, 208, 224, 240) (16*. 64*).

Как видно, дальнейшие склеивания невозможны.

67

Правила поглощения для рассматриваемого примера формулируют­ ся аналогично. Для удобства выполнения алгоритма поглощения сфор­ мулируем эти правила отдельно для двух случаев.

1. Пусть для каждой разности с индексом х импликанты U2 у импликанты и г найдется разность с индексом / . В этом случае погло­ щает U если С1 >• С2 (Сх и С2 — соответственно константы импликант Ux и 1/2) и множество номеров элементарных произведений в скобках импликанты Ux включает в себя множество номеров элементарных про­ изведений в скобках U2.

2. Пусть Ux имеет разность с индексом х, причем эта разность от­ сутствует среди разностей импликанты U2. В этом случае целесообразно проверять поглощение лишь тогда, когда импликанта U2 входит в со­

ется импликантой 3 — (64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240) (16/, 64х), поскольку не выполняется условие / > С2, а проверка его необходима, ибо здесь имеет место случай 2.

Поглощенные импликанты отметим звездочкой *. Неотмеченные им­ пликанты являются простыми. Выпишем их:

3 — (64, 80, 96, 112, 128, 144, 160, 176, 192,208, 224, 240) (16/, 64*),

Необходимо записать эти импликанты в буквенной форме. Для этого воспользуемся следующим, вытекающим из описанного выше, приемом. Выберем из множества номеров в скобках какой-нибудь один (например, наибольший) и запишем его в &-й системе счисления. По полученному числу восстанавливаем элементарное произведение. Вычеркиваем оператор / 5 (xt), если рассматриваемая простая импликан­ та имеет разность с индексом / , соответствующую аргументу xt (в на­ шем примере аргументу хг соответствует разность 64, хг — 16, ха — 4). Если разность имеет индекс х, то соответствующий оператор заменяет­ ся своим аргументом. Константа импликанты сохраняется неизменной (если она не равна k — 1). Таким образом, первая простая импликанта имеет вид 3—240 — 3—330 -> 3 /3 (хх) / 3 (х2) / 0 (х3) -*■ 3 ^ /0 (х3) -»

—*■XyJо (*з). а остальные 2 /2 (хх) / 2 (х2)х3, 1/2 (х2) / 2 (х2), 2/ х (хх) / 0 (*3), 1/о (*]) /1 (х2).

68

Если построить импликантную матрицу для данной функции, то можно убедиться, что простая импликанта 1J2 (хд ^ 2 (xz) в минималь­ ную ДНФ не входит и последняя имеет такой же вид, как в предыду­ щем примере.

Следует отметить, что некоторые функции в классе ДНФ очень слабо поддаются минимизации. Так, например, не удается получить простое выражение для функции х + у (mod k). При k = 3 минималь­ ная форма этой функции содержит 8 двухместных операций и 6 одно­ местных (без минимизации их потребовалось бы 14 и 6 соответственно), но с увеличением k эффект минимизации уменьшается.

§ 2.9. Минимизация Д Н Ф многозначных функций

в избыточных базисах

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

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

Рассмотрим избыточную базисную систему, которая содержит все

69