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

Следовательно, правая часть (4.24) также равна Ь. Поскольку набор у был выбран произвольно, то теорема доказана.

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

На любом наборе из множества {а} симметричная функция прини­

мает одно и то же значение / (ос). Поэтому симметричную функцию мож­ но полностью определить, если известны ее значения на всех N (п, к) множествах симметричных наборов. Следовательно, число различных симметричных функций равно kN{n-kK

Назовем базовой симметричной функцией S n (ос, х) такую функцию,

которая равна а на всех наборах а ( (а) и b на всех остальных на­ борах, то есть

-» - \а при х = сс £ (ос),

(Ь при х = а £ {а}.

Каждому множеству симметричных наборов соответствует одна базо­ вая симметричная функция. Следовательно, число различных функций

S n(ос, х) равно N (п, k). Для любой из них

f (х) можно представить в виде дизъюнкции базовых симметричных функций

100

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

Доказательство теоремы легко вывести из выражений (4.25) и

лютно минимальное представление сумму по mod 2 в булевой алгебре

ные теоремы справедливы при простом k. Если же k не является простым числом, то некоторые решения системы (4.23) могут принад­ лежать различным множествам симметричных наборов и в таком слу­

101

Таким образом, представление симметричной функции, согласно (4.27), содержит

дизъюнктивных членов, в то время как совершенная ДНФ содержит

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

§ 4.4. Минимизация симметричных многозначных функций

Форма представления симметричной многозначной функции со­ гласно (4.27), как и ее совершенная ДНФ, является избыточной фор­ мой представления функций и ее можно минимизировать [1 0 ].

Введем некоторые определения. Назовем симметричным аналогом совершенной ДНФ выражение (4.27). Функции А т-, введенные в

предыдущем параграфе, назовем симметричными аналогами аргумен­ тов xt.

Есть две возможности минимизации симметричных функций. ВоперЕых, можно минимизировать известными методами [191 совершен­ ную ДНФ симметричной функции, а затем с помощью соотношений, аналогичных соотношению (4.26), в минимальной ДНФ заменять ар­ гументы х( их симметричными аналогами. Во-вторых, как и для обыч­ ных совершенных ДНФ, можно ввести понятия симметричных анало­ гов элементарных произведений, импликант, а также сокращенных, тупиковых и минимальных ДНФ, которые будут отличаться от обыч­ ных только тем, что в роли аргументов выступают их симметричные аналоги Ащ.

Первый способ не всегда дает симметричный аналог минимальной ДНФ симметричной функции. Действительно, совершенная ДНФ функции

/ (х, i/) = 1А (х) J 3 (у) V 2А (X) J 3 (у) V ЗА (X) j 3 (У) V

V 1А (х) J 1 (у) V 2Уз (х) А (у)

при к > 5 совпадает с ее минимальной ДНФ, в то время как симмет­ ричный аналог ДНФ этой функции

f (•*->у ) = lA (Ai) А (Аг) V 2A (АО J2 (АО V ЗА (АО А (Аг)

можно упростить и записать как

} (х, у) = АгА (АО-

102

Остановимся на втором способе минимизации симметричных функ­ ций. Выпишем для дальнейшего рассмотрения главные соотношения (здесь и далее вместо A nt подставим А {).

либо k — 1 , то есть, буква х может быть или не быть в соответствую­ щем выражении. Соотношения (4.30) — (4.32) позволяют по симмет­ ричному аналогу ДНФ восстановить симметричный аналог совершен­ ной ДНФ любой симметричной функции.

Как уже отмечалось, задача минимизации симметричной функции сводится к отысканию ее простых импликант (в данном случае их сим­ метричных аналогов), так как найти тупиковые и минимальные ДНФ можно известными методами, например с помощью импликантных матриц. Для отыскания простых импликант необходимы соотношения склеивания и поглощения. Как и в [191, будем считать, что функция /i поглощает функцию /2, если на всех наборах > /2. В дальнейшем слова «симметричный аналог» будем опускать, так как речь будет идти только о симметричных функциях.

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

A (-А) А (Л) и A (-A) J 1 {A-А J 1 (^з)

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

103

Операции, определяемые соотношениями (4.36) — (4.38), назовем операциями неполного склеивания. Если в совершенной ДНФ функ­ ции произвести все операции неполного склеивания как над ее чле­ нами, так и над вновь полученными импликантами, то получим мно­ жество элементарных произведений, среди которых будут и все простые импликанты. Чтобы их выделить, необходимо произвести все операции поглощения согласно критериям поглощения.

Рассмотрим два элементарных произведения

В этих элементарных произведениях не может быть более двух

так как в противном случае или константа, или аргумент без знака

оператора отсутствует.

Теорема. Для того чтобы элементарное произведение U1 поглощало элементарное произведение U2, необходимо и достаточно:

axA m > a2As,.

Доказательство. Докажем вначале необходимость первого усло­ вия. Пусть U1 > U2n Jyz (Л(г) не входят в U2. В этом случае всегда

104

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

и a2A S(. Но так как axAim < о2Л 5(, то в данном случае и Ux < U2,

что невозможно. Следовательно, второе условие также необходимо. Покажем достаточность приведенных условий. Рассмотрим значе­ ния Ux и U2 на тех наборах, на которых U2 Ф 0. Так как все опе­

раторы JVy (AiJ) входят в U2, то на этих наборах Ux = axAtm и U2 =

= a2A S(- Но в силу второго условия axAim > aAS/. Следовательно,

U\ > Uz на этих наборах. На всех остальных наборах U2 — 0. По­ этому на любых наборах Ux >• U2. Теорема доказана.

Таблица 20

Рассмотрим пример. Пусть симметричная функция / (х, у, г) за­ дана ДНФ (k = 4)

f(x, у, z) = J3(x)yJ0(z) V Ja(x) Jo (У) г У xJ3(y)J0(z) V

V xJ0(y)J3(z) V J0(x)Ja(y)z\/ J 0(x)yJ3(z) V 1Ja(x)J2{y)Jx{z) V V 1J2(x) J x{y) J2{z) V Mi(x)Ji(z) V 2Ji{x) J2{y) J 2{z).

Нетрудно проверить, что эта форма является минимальной ДНФ функции / (х, у, z). Совершенная ДНФ этой функции содержит 19

105

дизъюнктивных членов, в то время как ее симметричный аналог только пять членов:

f (x t У<z) = 1А (A) А (А ) A (A) V 2y3 (А ) А (А) А (А) V

V А (A) Jз (А) А (А) V JA (A) A (A) A (A*) V 2A (A) *A (A) A (A)-

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

/ (х, у I z) — A (A) А А (А) V А (А ) ^2 (А) А>

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

дает абсолютно минимальные выражения. Однако можно утверждать, что симметричные аналоги минимальных ДНФ, как правило, гораздо проще обычных минимальных ДНФ, а число операторов Js (х) в них всегда не больше, чем в обычных минимальных ДНФ. Это особенно важно при амплитудно-импульсном принципе представления инфор­ мации, так как в этом случае элементы, реализующие Js (х), значитель­ но сложнее других элементов (гл. 3). Такой метод можно применить для упрощения частично симметричных и обычных функций. Для

этого многозначную функцию / (х) необходимо представить как

f(x) = ф(х) V Ф(х),

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

§ 4.5. Особенности реализации многозначных симметричных функций в системе теоретико-множественных операций

Пусть х V У и ХУ— соответственно операции объединения и пере­ сечения, а Д — характеристическая функция (2.15). Как и в § 4.3,

символом {а} обозначим множество симметричных наборов, образо­

ванных набором а. Функцию S'(а, х), принимающую значение /' на

106

Теорема. Базовую симметричную функцию S' (а, х) можно пред­ ставить в виде

случае левая часть (4.41), согласно (4.39), равна /. Из определения

для множества симметричных наборов которой справедливы усло­ вия (4.40), можно реализовать на основе схемы, реализующей только функцию АпI.

Произвольный набор а, образующий множество {а}, можно пред­ ставить в виде

ГДе ССпг1-у—ССт2 Ф1 ... ifc ctn.

Теорема. Произвольную базовую симметричную функцию можно

Доказать эту теорему можно аналогично предыдущей.

Отметим, что определение базовой симметричной функции и ее реализация, согласно (4.42), не зависят от k. Имея все базовые симмет­ ричные функции (то есть базовый симметричный многополюсник),

можно реализовать любую симметричную функцию f (х).

по всем {а}

Для построения базового симметричного многополюсника необхо­

107

димо реализовать симметричные аналоги A ni аргументов, что можно

венно. Общее число двувходовых элементов, необходимых для реали­

Дальнейшее упрощение симметричных функций в системе теоре­ тико-множественных операций может основываться на использовании соотношений, аналогичных соотношениям (2.56) — (2.58), в которых аргументы заменены их симметричными аналогами. Однако использо­ вание таких соотношений не всегда приводит к отысканию всех сим­ метричных аналогов простых импликант. Примером тому может слу­ жить функция / (х, у, г), которая при k = 3 на наборах (0, 0 , 0), (0 , 0, 1 ) и (0, 0, 2 ) равна 1 , а на остальных наборах принимает произволь­ ные, но не равные единице значения. В этом случае выражения (О^зз)1 V (О^зг)1 AS1 V (О-Дд,) 1 (2А31У не могут быть подвергнуты даль­ нейшим упрощениям. С другой стороны, как легко проверить, спра­

Таким образом, в классе симметричных аналогов ДНФ многознач­

Предположим, что множество наборов {а,} состоит из всех тех наборов, в которых константы а1г а2, ..., аг встречаются соответствен­ но /ь /г» •••> !г и более раз. Пусть, кроме того, подлежащая минимиза­ ции функция принимает на этих наборах одно и то же значение р. В этом случае справедливо соотношение склеивания

т

где q = К SP (а;, х).

108

Произведя все возможные операции склеивания согласно (2.56) — (2.58) и (4 .44), а затем все возможные операции поглощения, получим множество симметричных аналогов простых импликант, из кото­ рых известными методами можно образовать симметричный аналог минимальной ДНФ.

§ 4.6. Синтез многозначных дешифраторов

Дешифратором для п переменных хи х2, ..., хп называют комбина­ ционную схему с п входами и kn выходами, реализующую все функции вида

а при х = а

Сложность дешифратора удобно оценивать отношением числа

тремя основными способами: матричным, пирамидальным и прямо­ угольным 191.

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

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

Ja, (^i) Jаг (Х2).

Затем, используя их, строят схемы, реализующие все выражения вида

Ja, (Д ) J а2 {Х2) J а, (Х3)

109