книги из ГПНТБ / Цифровые многозначные элементы и структуры учеб. пособие

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

/ (х), то есть получить сокращенную ДНФ этой функции. Доказательство. Импликанта, которая не зависит от Js (х), принима­

ет одно и то же значение А при s = 1, 2, .... k — 1. Поскольку А Ф О,

то среди элементарных произведений, составляющих СДНФ функции

—у

f (х), должны быть и те, которые обеспечивают выполнение соотношения (2.48). Рассуждения относительно аргумента xt и соотношения (2.49) аналогичны, следовательно, теорема доказана.

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

Рх \J Р = Р (х \J (k — 1)) = Р.

Следовательно, любая собственная часть какого-либо элементар­ ного произведения поглощает его.

Собственной частью называют произведение, полученное путем исключения из данного произведения одного или нескольких сомно­ жителей. Например, элементарное произведение aJr (хх) Jq (х2) имеет такие собственные части: aJr (хг), aJq (x2), Jr {xi)Jq(x2), a, /Д х ^ ,

Jq(x2).

Приведенное условие является достаточным, но не необходимым для поглощения одного элементарного произведения другим. Дей­ ствительно, элементарное произведение 5х поглощает элементарное произведение 3J6{x) и при этом не является его собственной частью.

Теорема. Для того чтобы элементарное произведение Рг погло­ щало элементарное произведение Р2, необходимо и достаточно, чтобы соблюдались следующие условия:

60

1) Ci > C2, где Ci и C2 — константы элементарных произведений

иР 2;

2)все функции У, (х), входящие в состав произведения Р 1( должны быть и в Р2;

3)если в состав Рг входит аргумент х{, не содержащийся в Р2,

то в состав Р 2 должна входить функция J, (хс) этого аргумента, причем

С2.

Доказательство. Необходимость первого условия очевидна. Не­ обходимым является и второе условие, так как элементарное произве-

—у

дение Pi должно накрывать функцию f (х) на тех наборах, которые накрыты элементарным произведением Р2. Следовательно, если Р1зави­ сит от какой-либо функции J s(x), то Р2тоже должно от нее зависеть.

которые сведут разницу между элементарными произведениями Рх и Р2 к случаю, предусмотренному условием 3. Согласно (2.50), элемен­ тарное произведение Рг будет поглощать вновь полученное произве­

ведение может поглощать только те элементарные произведения, которые участвовали в его образовании при склеивании (если элемен­

тарные произведения — суть импликанты функции / (х)). Приведенные условия позволяют выделить простые импликанты.

Дальнейший процесс отыскивания минимальной (тупиковой) ДНФ не зависит от k [19] и может идти известными в булевой алгебре пу­ тями, поскольку возможны всего два варианта: или простая импликанта поглощает данное произведение, или нет.

Рассмотрим пример. Определим все простые импликанты для функ­ ции из предыдущего примера. Для этого к каждой импликанте спра­ ва припишем все импликанты, которые поглощаются этой импликан-

61

в рассматриваемом случае произвести нельзя.

Сравнивая приведенный перечень поглощенных импликант с СДНФ

Минимальную Д//Ф этой функции найдем с помощью импликантной матрицы. Матрица представляет собой таблицу, строки которой обозначены простыми импликантами, а столбцы — членами совершен­ ной ДНФ. Для упрощения записи каждую простую импликанту обо­ значим буквой J с индексом, равным ее порядковому номеру в сокра­ щенной ДНФ (например, У4 = 1 x1Jl (х2)), а каждый член совершенной ДНФ — буквой К с индексом, также равным его порядковому номеру (например, Кь — 2J 1 (х4) J 3 (х2)). Клетки такой импликантной матрицы (табл. 15), образованные пересечением строк с простыми импликанта­ ми и столбцов с поглощаемыми ими членами СДНФ, отметим крестиками.

62

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

сее сокращенной ДНФ.

§2.8. Критерии и методы получения минимальных Д Н Ф многозначных функций

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

ДНФ:

1)минимальное число двухместных операций;

2)минимальное число функций J s (х);

3)минимальное число суперпозиций.

Можно привести примеры, когда минимальная ДНФ, выбираемая по первому или второму критерию, не является минимальной по третье­ му критерию. В то же время именно третий критерий наиболее соот­ ветствует практическим целям. Однако при kn > ЮО (если не фикси­

руется k , то kn будет более удобной характеристикой функции, чем просто га) число одноместных функций в общем случае пренебрежимо мало по сравнению с числом двухместных.

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

/ (л:), при формировании которых могут использоваться одни и те же одноместные функции. Однако при синтезе комбинационных схем в избыточных базисах подобный подход недопустим, так как в этом слу­ чае число одноместных функций может быть очень велико и пренебре­ гать им нельзя.

Рассмотрим пример. Требуется найти минимальную форму функ­ ции хх + х2 (mod 3), заданной в виде

хх + х2 (mod 3) = J0(хх) х2 V 1A (*i) А (*2) V V A (*1) A (*2) V A (•'t) A (-*2) V 1 A (xi) А (*г)«

63

Применяя к первому дизъюнктивному члену соотношение (2.45), восстановим СДНФ этой функции

x i х 2(mod3 ) = U 0 (хх) Ji (х2) V А (Xj) J2 (х2) V

V 1 A (^l) А С*а) V A Wl) A W2) V ^ i ( Xl) ^о(Х2) V lA C*i) A C^a)*

Из членов этой СДНФ составим все возможные выражения, удовле­ творяющие соотношениям (2.48) и (2.49),

и 0 (Х1) А (*а) V А (*i) А (•’‘-г) = 1 А (x i) А (-'-г) V V A Wi) А (^г) V A Wi) *2*

1 A Wi) А Аг) V A Ai) А (^а) = 1A Wi) А (^а) V V A Wi) А (*а) V V o (Л'г)-

Таким образом, импликантами функции х2 + х2 (mod3) помимо членов ее СДНФ будут также элементарные произведения J0 (хг) х2 и х Д 0 (х2). Выполнив все возможные операции поглощения согласно приве­ денным в § 2.7 условиям, получим сокращенную ДНФ этой функции

хх + х2 (mod 3) = J0 (Xj) х2 V V o W V A W A W V 1A W A W -

Как и ранее, обозначим каждую импликанту буквой J, а каждый член совершенной ДНФ,— буквой К. Индексы при J и К указывают их порядковые номера в сокращенной и совершенной ДНФ. Построив для функции xl + х2 (mod 3) импликантную матрицу (табл. 16), убе­ димся, что ее минимальная ДНФ совпадает с сокращенной ДНФ.

Таблица 16

Нетрудно проверить, что найденная минимальная форма функции

xi+ х 2 (mod 3) минимальна по всем приведенным ранее критериям. Описанная методика связана с громоздкими вычислениями при

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

Функцию записывают таблицей, столбцы и строки которой обозна­ чаются функциями Js. (хс). Затем находят простые импликанты, начиная

с односимвольных (констант, переменных х{, функций J s. (х(-)), дву­

64

Следующий метод подобен известному в булевой алгебре методу Мак-Класки. Зафиксируем порядок аргументов в наборах: индекс аргумента соответствует его порядковому номеру слева. В этом случае каждое элементарное произведение тоже будет иметь свой номер: цифра /-го разряда любого набора равна значению п — / + 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