3-8. СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ С УЧЕТОМ ТЕОРЕТИКО-СТРУКТУРНЫХ СВОЙСТВ БУЛЕВЫХ ФУНКЦИЙ

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

Пусть имеется множество А:

Определим на множестве А две операции: пересечение и объединение удовлетворяющие следующим законам:

а) идемпотенци и

б) коммутативности

в) ассоциативности

г) поглощения

Определение 3-7. Созоку операции удовлетворяют соотношениям пнолзншм (3-16а) — (3-19 б), называется структурой

Рассмотрим структуру 5 и докажем следующую лемму.

Лемма. Если то равенства

выполняются или не выполняются одновременно.

Пусть

Тогда согласно (3-17) и (3-196) имеем:

Следовательно, если

Положим теперь Тогда согласно (3-19а) получим:

Следовательно, если то

Будем писать если для элементов структуры имеет место равенство (3-20), при этом будем говорить, что элементы и а, находятся в бинарном отношении

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

Если то говорят, что элемент находится в отношении к элементу в том и только том случае, если пара принадлежит к подмножеству

Следовательно, записи

и

равносильны.

Покажем, что введенное выше бинарное отношение в А обладает свойствами:

рефлексивности,

антисимметричности,

если и то

транзитивности,

если и то .

Действительно, согласно (3-16) имеем:

Пусть далее т. е.

Тогда согласно (3-17а) имеем:

Следовательно, если то Наконец, если и т. е. , то согласно (3-18а) имеем:

т. е.

Следовательно, если и то

Определение 3-8. Бинарное отношение со свойствами рефлективности, антисимметричности и транзитивности будем называть отношением частичной упорядоченности.

Множество А с заданным в нем отношением частичной упорядоченности называется частично упорядоченным.

Рассмотрим частично упорядоченное множество А, в котором:

а) для всякой пары элементов существует такой элемент что

причем если некоторый элемент также обладает свойствами то

б) для всякой лары элементов существует такой элемент что

причем если некоторый элемент также обладает свойствами то .

Покажем, что удовлетворяющие (3-21), могут быть рассмотрены как результаты операций соответственно. Для этого запишем, что

и докажем, что операции определяемые (3-21), обладают свойствами идемпотентности, коммутативности, ассоциативности и поглощения. Следовательно, и есть операции соответственно.

Свойства идемпотентности операций и очевидны. Докажем свойство ассоциативности, например, для

Согласно условию (3-21а) имеем:

Отсюда согласно тому же условию

Таким образом, мы доказали свойство ассоциативности операции

Аналогично доказывается свойство ассоциативности и операции и.

Докажем свойство поглощения операций Пусть

Согласно свойству рефлексивности отношения имеем:

По условию (3-216) имеем:

Тогда согласно условию (3-21 а) получим:

Следовательно,

Аналогично доказывается условие (3-1 Об) для операций Следовательно, операция совпадают с операциями

Определение 3-9. Структурой называется частично упорядоченное множество, в котором для любой пары элементов выполнены вышеприведенные условия (3-21), где есть соответственно пересечение и объединение по всем элементам А.

Введем бинарное отношение — отношение покрытия.

Будем говорить, что элемент покрывается если и не найдется в элемента такого, что

Диаграмма, представляющая структуру строится следующим образом.

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

Диаграмму, построенную таким образом, обычно называют диаграммой Хассе.

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

Например, функцию

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

Диаграмма Хассе в данном случае имеет вид рис. 3-39.

Рис. 3-39.

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

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

Рассмотрим задачу построения неразделительных декомпозиций функции

через функции соответствующие базисным элементам.

Для исследования этой задачи введем понятие взвешенной структуры.

Определение 3-10. Структура называется взвешенной, если каждому ее элементу сопоставлен первичный терм, т. е. переменная или ее отрицание.

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

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

Будем рассматривать функции такие, что соответствующие им взвешенные структуры представляют собой диаграммы Хассе, в которых не найдется ни одного подграфа, вершинами которого являются первичные термы:

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

Рис. 3-40.

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

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

Лемма. Функция является решетчатой тогда и только тогда, когда в графе задающем эту функцию, не содержится подграфа характеризующегося следующими свойствами:

а) он является циклом, составленным из нечетного числа вершин

б) во множестве номеров, сопоставленных его вершинам, имеется подмножество номеров конъюнкций, соответствующее его вершинам вида, представленных на рис. 3-40.

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

Рис. 3-41.

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

Проиллюстрируем изложенный метод на следующем примере.

Пример 3-25. Пусть функция равна 1, если четное число ее входов возбуждено, в противном случае равна 0, т. е. функция на выборах 0, 3, 5, 6.

Рис. 3-42.

Необходимо построить декомпозицию заданной функции через импликацию и функцию, тождественно равную нулю.

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

Наборы, не соответствующие подграфам типа вычеркиваем, соответствующие — обводим.

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

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

Выделенные подграфы есть:

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

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

Диаграмма Хассе, соответствующая полученной решетчатой функции, имеет вид рис. 3-43.

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

Рассмотрим этот метод. Введем ряд понятий.

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

где — собственная частота буквы — взаимная частота пары букв число простых импликант в ДНФ функции которое обычно называют рангом ДНФ; буквы являются первичными термами рассматриваемой функции;

2) в диаграмме Хассе, реализующей эту функцию, найдется ярус, вершины которого взаимно однозначно взвешены буквами подмножества так что не найдется ни одной вершины, не принадлежащей этому ярусу и взвешенной буквой

Рис. 3-43.

Уровнем типа В называется подмножество множества X такое, что для него справедливо первое условие предыдущего определения и не справедливо второе условие.

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

Операцию приведения уровня типа В к уровню типа А назовем операцией расщепления первого типа.

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

Вершина называется покрывающей вершину если в графе имеется дуга вида

Расщепление первого типа производим в следующем случае.

Пусть построено I ярусов диаграммы Хассе, причем вершины 1-го яруса взвешены множеством первичных термов и пусть в этом ярусе содержатся две вершины с весами соответственно такие, что при построении яруса множества весов вершин, покрывающих соответственно являются пересекающимися

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

Уровнем типа С называется подмножество множества букв X такое, что

3) подмножество является покрытием матрицы инцидентности, задающей функцию

Пример 3-26. Задана булева функция, ТДНФ которой имеет следующий вид:

Матрица инцидентности, задающая эту ТДНФ, имеет вид:

Определим подмножества букв, которые могут претендовать на взвешивание вершин первого яруса искомой диаграммы Хассе. Очевидно, что претендентом на веса первого яруса могут быть уровни типа А или С.

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

Первое и последнее подмножества являются уровнями тина А, остальные — типа С.

Операцией расщепления второго типа будем называть приведение уровня типа С к уровню типа А или В.

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

При расщеплении второго типа порождаются новые подмножества уровней типов А, В и С.

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

Рост мощности множества проиллюстрируем следующим примером.

Пример 3-27. Пусть функция задана своей матрицей инцидентности

Допустим, что в качестве первого яруса выбраны вершнны, взвешенные буквами уровня типа Тогда, расщепляя букву получаем матрицу инцидентности вида

Если для первой матрицы инцидентности имеем шесть покрытий

то для второй матрицы инцидентности (после расщепления) имеем восемь покрытий

Используя введенные понятия, рассмотрим следующий метод синтеза диаграмм Хассе.

Рис. 3-44.

Для снижения трудоемкости при синтезе оптимальных диаграмм Хассе в этом методе используется понятие производной от модели.

Подграф с начальной вершиной являющейся концом дуги будем называть подграфом, покрывающим вершину (рис. 3-44,а).

Объединение подграфов с начальными вершинами являющееся концом дуг, начала которых есть вершины, у., образующие подъярус, будем называть подграфом, покрывающим подъярус (рис. 3-44, б).

Матрица инцидентностн модели по которой производится оценка, строится следующим образом. Каждой строке взаимно однозначно сопоставляется

первичный терм булевой функции, столбцу - выделенный подуровень и

Уровни, взвешивающие начальные вершины подграфов, покрывающих вершины построенного яруса, будем оценивать с помощью функции

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

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

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

Перед изложением метода синтеза рассмотрим случай неодинаковой длины путей синтезируемого графа. В этом случае имеем четвертый тип уровня — уровень типа

Подмножество множества X называется уровнем типа если выполняются следующие условия:

3) не существует такого элемента включение которого в подмножество приводит подмножество к уровню типа А.

Пусть дай граф (рис. 3-45), реализующий булеву функцию

Уровнем типа является подмножество первичных термов

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

Рис. 3-45.

Следовательно, для получения таких подмножеств первичных термов (уровней типа А) необходимо в уровень типа включать первичный терм такой, что

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

В рассматриваемом примере при синтезе графа в качестве подуровней, взвешивающих подграфы, покрывающие вершины, с весами выбираем соответственно

Очевидно, что подграф покрывающий вершину, с весом является частью подграфа покрывающего вершину, с весом следовательно,

где — взаимная частота подуровней, взвешивающих подграфы и — собственная частота подуровней, взвешивающих подграф

Частоты и вычисляются по матрице инцидентности построенной на этом шаге синтеза.

Опишем процедуру выравнивания длин путей:

1) отыскивается пара первичных термов для которых справедливо

2) проверяется равенство длин путей, началом которых являются соответственно вершины, взвешенные

3) если длпиы путей не равны, то в покрытие вершины, входящей путь с меньшей длиной, включается расщепленный ее вес.

Для рассматриваемого примера повторяем вес (рис.

Входной информацией для алгоритма синтеза диаграмм Хассе является матрица инцидентности модели задающая ДНФ функции

Опишем теперь алгоритм синтеза диаграммы Хассе.

1. Выделяем множества уровней типа А и С, претендующих на взвешивание первого яруса. Каждый уровень выделяется с помощью покрытия в матрице инцидентности строк столбцами. Каждое покрытие взаимно однозначно сопоставляется выделяемому уровню.

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

Выбираем уровень, соответствующий первому покрытию матрицы инцидентности.

2. Для каждого первичного терма в выбранном уровне строим подматрицу инцидентности, соответствующую подграфу, покрывающему вершину с весом

Покрытием подматриц инцидентности находим подуровни, взвешивающие вершины следующего яруса.

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

Каждый уровень оцениваем с помощью функции

где частоты являются элементами частотной матрицы отношений

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

Выбираем уровень с наибольшим значением при наличии уровней с несколькими максимальными значениями выбираем из них уровень с минимальной оценкой числа расщеплений первого типа.

5. Производим выравнивание длин путей.

6. Если диаграмма Хассе не построена, т. е. порядковый номер синтезированного яруса не равен максимальной длине пути графа, то переходим к в противном случае производим подсчет сложности синтезированного графа.

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

Если то выбираем граф из следующего соотношения:

где — сложность графа, полученного на предыдущем этапе; -сложность графа, полученного на данном этапе.

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

Проиллюстрируем предлагаемый метод синтеза диаграммы Хассе на следующем примере.

Примеры 3-28. Синтезировать диаграмму Хассе, реализующую булеву функцию вида

Заданной ТДНФ этой функции соответствует матрица инцидентности вида

Выделяем множество претендентов на первый ярус. Каждый претендент на взвешивание первого яруса является покрытием матрицы инцидентности (уровнем типа А или С).

В нашем случае имеем следующие покрытия:

Всего имеем 15 покрытий Следовательно, для нахождения графа минимальной сложности необходимо синтезировать 15 графов и выбрать граф с минимальной сложностью. Взвесим первый ярус уровнем расщепив Элементам выбранного уровня соответствуют подматрицы

Длина всех рассматриваемых слов одна и та же.

Производя покрытие подматриц и выделяем подуровни.

В результате покрытия подматрицы имеем следующие множества:

Подуровни образуют множество покрытий подматрицы

Покрытиями подматрицы являются

Веса подграфов, покрывающих полученные подуровни, образуют следующие множества.

Для подуровней буквы

Для подуровней буквы

Для подуровней буквы

Матрица инцидентности имеет следующий вид:

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

(см. скан)

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

Подматрицы инцидентности, соответствующие не равны друг другу, следовательно, имеем расщепление первого типа буквы

Дальнейшее построение искомого графа однозначно. Сложность полученной диаграммы Хассе (рис. 3-46) равна

Остальные 14 диаграмм Хассе синтезируются аналогичным образом. Среди них графы (рис. 3-47) со сложностью 10 являются абсолютно минимальными графами, реализующими заданную ТДНФ функции

Перейдем ко второму этапу синтеза. Преобразуем построенную ранее диаграмму Хассе (см. рис. 3-43) в логическую структуру в заданном базисе

Выразим базисную функцию импликации через дизъюнкцию и отрицание. Представим геометрически функции дизъюнкции и отрицания в виде графов на рис. 3-48. Тогда функции импликации будет соответствовать граф вида, показанного на рис. 3-49.

Наложим ограничение на вид базисных функций; это будет вторым ограничением на исследуемую задачу.

Рис. 3-46.

Рис. 3-47.

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

Для более наглядного изложения алгоритма построения логической структуры по диаграмме Хассе,

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

Рис. 3-48.

Рис. 3-49.

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

Ориентированная сеть, соответствующая заданной функции, имеет вид, показанный на рис. 3-50.

Рис. 3-50.

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

Введем операцию разложения ориентированной сети на направления и операцию построения инверсной сети.

Подсеть является элементом разложения ориентированной сети на направления если ее можно получить следующим образом: отмечаем полюс в ориентированной сети и затем

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

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

Ориентированная сеть вида с добавленной к ней дугой, соединяющей полюсы (источниковой дугой), разбивает плоскость, на которой она расположена, на области.

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

Точки, взятые в соседних областях, разделенных источниковой дугой, считаем полюсами сети Ориентацию дуг сети 5 выбираем от одного полюса сети к другому, не изменяя его по мере построения дуг (т. е. слева направо или справа налево, если сеть 5 ориентирована сверху вниз или снизу вверх), при этом не начинаем строить новый ярус сети, пока не построен полностью предыдущий ярус сети (при таком ярусном построении дуг в сети ориентация дуг будет выбрана правильно). Результат такого построения есть сеть, инверсная к данной.

Проиллюстрируем алгоритм построения логической структуры на рассматриваемом примере для базиса, состоящего из импликации и нуля (рис. 3-51).

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

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

Рис. 3-51.

Например, в качестве упражнения читатель может построить неразделительную декомпозицию этой же функции через функцию Шеффера. Эта декомпозиция имеет следующий вид:

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