Известия РАН. Теория и системы управления, 2022, № 4, стр. 66-94

Введение. Математический аппарат бинарных диаграмм решений (binary decision diagrams (BDD) – бинарные диаграммы решений, диаграммы двоичного выбора) в настоящее время используется в различных областях науки [1, 2], в последнее время он применяется для решения задач выполнимости конъюнктивных нормальных форм булевых функций [3]. BDD используются как структуры данных [4] для представления булевых функций, в [5] были предложены эффективные алгоритмы для сокращения BDD и выполнения логических (двухместных) операций над BDD. Статья [5] оказалась настолько актуальной, что она стала наиболее цитируемой в информатике, “поскольку революционизировала структуры данных, используемые для представления булевых функций” [1, с. 303]. Области применения BDD расширяются, этот аппарат явился вычислительной основой решения задач верификации параллельных систем с конечным числом состояний на основе метода model checking, что позволило “увеличить сложность анализируемых систем в миллионы миллионов раз” [2, c. 295]. В [2] приводится много примеров применения BDD, там же указываются и некоторые из модификаций BDD.

В системах проектирования цифровых сверхбольших интегральных схем (СБИС) графовый аппарат BDD применяется при верификации и тестировании СБИС [6], а также при технологически независимой оптимизации, выполняемой как первый этап синтеза логических схем в различных технологических базисах [7]. BDD представляет собой ациклический граф, задающий булеву функцию либо систему полностью определенных булевых функций. Каждой вершине этого графа соответствует полная либо редуцированная (сокращенная) формула разложения Шеннона. Поэтому при построении BDD стремятся сократить число вершин BDD – сложность функционального описания в виде взаимосвязанных формул разложений Шеннона [8–13].

Схемная реализация (логический синтез) исходных систем частичных булевых функций осуществляется чаще всего в три этапа. На первом этапе происходит логическая оптимизация систем частичных функций и их доопределение до систем полностью определенных функций. Логический синтез для полностью определенных булевых функций составляет содержание следующих двух этапов (логической технологически независимой оптимизации) и технологического отображения в требуемый базис (целевую библиотеку) логических элементов. Однако методы логической оптимизации систем частичных функций, ориентированные на требуемую библиотеку элементов, развиты недостаточно. Чаще всего путем минимизации систем в классе дизъюнктивных нормальных форм (ДНФ) на первом этапе осуществляется переход от систем частичных функций к системам полностью определенных функций, после чего может выполняться минимизация BDD-представлений, позволяющая уменьшать число литералов в многоуровневых представлениях систем функций. При синтезе логических схем из библиотечных элементов уменьшение числа литералов в представлениях систем полностью определенных булевых функций приводит к менее сложным схемам. Поэтому число литералов – это основной критерий минимизации алгебраических представлений функций на первых двух этапах синтеза логических схем [14].

В [15] предложено осуществлять поиск в графе BDD-представлений булевых функций в виде разложений кофакторов на две подфункции с алгебраической выходной функцией, в зарубежной литературе такие разложения называют bi-decomposition (англ.). В системе BDS [15] данный вид оптимизации был дополнен также факторизацией – поиском одинаковых логических подвыражений и поиском подфункций, допускающих простое (с одной промежуточной булевой переменной) функциональное разложение.

Различные виды декомпозиции BDD-представлений систем булевых функций изучены в [7], минимизация BDD-представлений может выполняться с нахождением пар взаимно инверсных кофакторов [16], что дает значительный эффект при синтезе схем. Для дополнительной логической оптимизации в [17] предложен метод, основанный на поиске алгебраических разложений подфункций, входящих в минимизированные BDD-представления. Метод позволяет заменять формулы разложения Шеннона двухоперандными формулами дизъюнкций и конъюнкций и формулами вида g_p = g_i $ \oplus $ g_j, что уменьшает число литералов в результирующих логических формулах, по которым выполняется заключительный этап синтеза схемы. Программная реализация алгоритмов и результаты вычислительных экспериментов, приведенные в [18], показали, что для разложений кофакторов целесообразно использовать только дизъюнктивные и конъюнктивные разложения. Причем кофакторы в таких разложениях могут быть как в инверсной, так и безынверсной форме. Эксперименты показали также, что наиболее эффективной эвристикой в данных алгоритмах, влияющей на сокращение площади схем, является эвристика, ориентированная на нахождение дизъюнктивных и конъюнктивных разложений не для всех кофакторов, а только для тех, которые представлены полными уравнениями разложений Шеннона. Эксперименты были проведены на 59 примерах схем из широко известной библиотеки [19] и 14 примерах схем модулярных сумматоров. Используя после BDD-оптимизации программы поиска алгебраических разложений кофакторов, для 33 схем из [19] было получено 10–15% сокращение площади, при этом площадь уменьшалась преимущественно для схем с достаточно большим числом (10–27) входных переменных. Для девяти (из 14) схем модулярных сумматоров было получено сокращение площади, достигающее 28%.

Для систем частичных функций в [7] была предложена модификация BDD, отличительной особенностью которой является то, что для частичных функций все листовые вершины “–” (неопределенные значения частичных функций) рассматриваются как различные, в отличие от вершин-констант 0, 1. Каждая вершина “–” отдельно доопределяется при оптимизации до 0 либо 1. Для таких BDD-представлений систем частичных функций в [20] были предложены методы, позволяющие доопределить частичные функции до полностью определенных и минимизировать сложность BDD, находя пары взаимно инверсных частичных кофакторов. При решении задач логической оптимизации систем частичных булевых функций поиск рациональных доопределений применяется не только при минимизации BDD-представлений [7, с. 102], но и при совместной минимизации функций в классе ДНФ [20, с. 258], сокращении числа аргументов [20, с. 269], декомпозиции [7, с. 146; 20, с. 287] и при решении других задач, возникающих на этапе технологически независимой оптимизации. По аналогии с минимизацией многоуровневых BDD-представлений систем полностью определенных функций для повышения эффективности логической минимизации BDD-представлений систем частичных функций целесообразно проводить дополнительную логическую минимизацию и находить в таких случаях соответствующие доопределения функций с целью увеличения числа кофакторов, которые будут иметь алгебраические (дизъюнктивные либо конъюнктивные) разложения.

В работе предлагается метод минимизации BDD-представлений систем частичных функций, основанный на поиске алгебраических разложений частичных кофакторов одного уровня BDD в виде дизъюнкции либо конъюнкции других кофакторов того же уровня BDD. При поиске алгебраических разложений частичных кофакторов проводится их доопределение и используются как прямые (безынверсные), так и инверсные формы кофакторов. Суть предлагаемого метода состоит в нахождении алгебраических разложений кофакторов в классе частичных булевых функций, затем частичные функции доопределяются и для полученных многоуровневых представлений функций дополнительно ищутся алгебраические разложения кофакторов в классе полностью определенных булевых функций. Применение предлагаемого метода позволяет уменьшать число литералов в результирующих многоуровневых представлениях систем булевых функций, состоящих из формул разложения Шеннона и формул дизъюнктивного и конъюнктивного разложений. Приведенный в [7, 16–18] подход к оптимизации многоуровневых BDD-представлений систем полностью булевых функций, включающий:

минимизацию сложности BDD-представлений с нахождением взаимно инверсных кофакторов на каждом уровне BDD [16];

алгебраические разложения кофакторов [17];

программную реализацию и выбор эффективных эвристик [18],

распространяется и на случай систем частичных функций. Для BDD-представлений таких систем функций минимизация сложности BDD на первом этапе выполняется на основе сокращения числа пар взаимно инверсных частичных кофакторов [20], а на втором этапе – на базе предлагаемого в данной статье метода их алгебраических разложений. На третьем этапе предполагается программная реализация и проверка эффективности такого подхода к технологически независимой оптимизации при логическом синтезе схем из библиотечных элементов.

1. Основные определения. Булевыми называются двоичные (0, 1) функции f(x) = f(x₁, x₂, …, x_n) двоичных (булевых) переменных x₁, x₂, …, x_n. Пусть V^x – булево пространство, построенное над переменными булева вектора x = (x₁, x₂, …, x_n). Элементами этого пространства являются n-компонентные наборы (векторы) x* нулей и единиц. Булева функция, значения 0, 1 которой определены на всех элементах x* ∈ V^x, называется полностью определенной. Множество $M_{f}^{1}$ элементов x* булева пространства, на которых полностью определенная булева функция принимает значение 1, называется характеристическим множеством функции. Если же на некоторых элементах булева пространства V^x значения функции не определены, то такая функция будет не полностью определенной, или частичной. Частичная булева функция принимает единичное значение на элементах x* подмножества $M_{f}^{1}$ булева пространства V^x и нулевое значение на элементах подмножества $M_{f}^{0}$. На всех остальных элементах пространства V^x, образующих подмножество $M_{f}^{ - }$ пространства V^x, значения частичной функции не определены, подмножество $M_{f}^{ - }$ будем называть также областью неопределенных значений частичной функции. Неопределенное значение функции обозначается символом “–”. Очевидно, что $M_{f}^{1} \cap M_{f}^{0} = \emptyset $, $M_{f}^{1}\, \cap \,M_{f}^{ - }\, = \,\emptyset $, $M_{f}^{0}\, \cap \,M_{f}^{ - }\, = \,\emptyset $, ${{V}^{x}} = M_{f}^{0} \cup M_{f}^{1} \cup M_{f}^{ - }$.

Частичные функции  f₁(x) и  f₂(x) равны, если и только если

Будем называть частичные функции f₁(x) и f₂(x) взаимно инверсными (f₂ = ${{\bar {f}}_{1}}$, f₁ = ${{\bar {f}}_{2}}$), если и только если

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

Частичная функция f_i реализуется частичной (либо полностью определенной) функцией f_j (обозначается  f_i $ \prec $ f_j), если и только если

Функцию  f_j называют доопределением функции  f_i. Для пары полностью определенных булевых функций  f_i,  f_j отношение реализации является отношением равенства. Под векторной булевой функцией f(x) будем понимать упорядоченную систему частичных булевых функций f(x) = = (f₁(x), …, f_m(x)), значениями векторных функций на элементах x* булева пространства являются m-компонентные троичные векторы  f(x*).

Разложением Шеннона полностью определенной либо частичной булевой функции  f = f(x), x = (x₁, x₂, …, x_n), по переменной x_i называется представление

Функции  f₀ = f₀(x₁, …, x_{i – 1}, 0, x_{i + 1}, …, x_n), f₁ = f₁(x₁, …, x_{i – 1}, 1, x_{i + 1}, …, x_n) называются кофакторами (cofactors, англ.) разложения по переменной x_i либо подфункциями. Они получаются из функции  f = f(x₁, …, x_n) подстановкой вместо переменной x_i константы 0 и 1 соответственно. Каждая из подфункций  f₀ и  f₁ может быть разложена по одной из переменных из множества {x₁, …, x_{i – 1}, x_{i + 1}, …, x_n}. Процесс разложения подфункций заканчивается, когда все n переменных будут использованы для разложения либо когда все подфункции выродятся до констант 0, 1, “–” (неопределенное значение). На каждом шаге разложения выполняется сравнение на равенство полученных подфункций и оставляется одна из нескольких попарно равных подфункций.

Под BDD-представлением частичной векторной булевой функции f(x) = (f₁(x), …, f_m(x)) понимается ориентированный ациклический граф, задающий последовательные разложения Шеннона всех компонентных функций  f_i(x), $i = \overline {1,m} $, по всем ее переменным x₁, …, x_n при одном и том же заданном порядке (перестановке) переменных, по которым проводятся разложения [7]. Для упрощения графа листовые вершины обычно дублируются, а ориентация дуг на рисунках графов BDD не показывается, так как всегда принимается, что дуги ориентированы сверху вниз.

Наиболее близкими к графам BDD для частичных векторных функций (назовем такие графы частичными BDD) являются широко известные в литературе сокращенные упорядоченные BDD (англ. reduced ordered BDD, ROBDD) для одной полностью определенной булевой функции, в которых каждой функциональной вершине соответствует одна функция (подфункция разложения Шеннона), при этом функциональные вершины лишь подразумеваются (отождествляются с вершинами-переменными). Подробное описание OBDD (упорядоченных BDD) дано в [12, 13], ROBDD – в [1]. Далее под BDD будут пониматься ROBDD для систем функций (векторных функций).

Будем изображать на рисунках графы BDD, содержащие три вида вершин: функциональные вершины, соответствующие разлагаемым функциям; вершины-переменные; листовые вершины-константы 0, 1 “–” [7, с. 16]. BDD-представлению соответствуют формулы разложения Шеннона, каждой функциональной вершине – своя формула. По BDD-представлению можно найти задание каждой из компонентных функций f_i(x) в виде трех ортогонализованных ДНФ: одна из таких ДНФ задает область $M_{{{{f}_{i}}}}^{1}$ единичных значений компонентной функции, другая ДНФ – область $M_{{{{f}_{i}}}}^{0}$ нулевых значений функции, третья ДНФ – область $M_{{{{f}_{i}}}}^{ - }$ неопределенных значений компонентной частичной функции  f_i(x). BDD является более компактной формой по сравнению с ортогонализованной формой представления булевых функций (такие формы будут рассмотрены далее). Так BDD – это граф, а ортогонализованная форма задает все пути из корневых вершин в листовые в этом графе. Задание графа более компактно, чем перечисление всех путей в нем. Поэтому BDD и нашли широкое применение не только при проектировании логических схем, но и в информатике в целом [1, 2].

З а м е ч а н и е 1. Рисунки и структуры данных классических BDD не содержат функциональных вершин. Функциональные вершины обычно показываются на рисунках для удобства изложения методов минимизации BDD и иллюстрации зависимостей переменных в формулах разложений Шеннона, в компьютерных структурах данных функциональные вершины не указываются [7, с. 177].

2. Алгебраические разложения частичных функций. З а д а ч а 1. Заданы частичные булевы функции φ(x),  f₁(x),  f₂(x). Требуется найти, если это возможно, такие доопределения φ*(x), $f_{1}^{*}$(x), $f_{2}^{*}$(x) соответствующих функций (запишем это в виде φ(x) $ \prec $ φ*(x),  f₁(x) $ \prec $ $f_{1}^{*}$(x),  f₂(x) $ \prec $ $f_{2}^{*}$(x)), что будет выполняться одно из алгебраических разложений:

Естественно, для каждого из разложений (2.1), (2.2) требуются свои доопределения функций φ(x),  f₁(x),  f₂(x). Логические операторы $ \vee $ (дизъюнкция), & (конъюнкция) в формулах (2.1), (2.2) называют также выходными функциями соответствующего разложения. В [7] логические операции над частичными булевыми функциями (троичными переменными) определены следующим образом:

У т в е р ж д е н и е 1. Задача нахождения разложения (2.1) не имеет решения тогда и только тогда, когда выполняется хотя бы одно из условий (2.3)–(2.5):

Условие (2.3) говорит о том, что, если найдется хотя бы один набор значений переменных, на котором обе функции f₁(x), f₂(x) принимают значение нуль, а функция φ(x) принимает значение единица, то через операцию дизъюнкции функций  f₁(x),  f₂(x) нельзя выразить функцию φ(x), так как дизъюнкция двух нулей не может быть равна единице. В случае (2.4) от значения функции f₂(x) ничего не зависит, дизъюнкция  f₁(x) $ \vee $ f₂(x) не может принять значение нуль (значение нуль имеет функция φ(x)), так  f₁(x) принимает значение единица. Аналогично в случае (2.5). Условия (2.3)–(2.5) можно задать в табличном виде (табл. 1). Таблица 2 позволяет проверить возможность доопределения функций φ(x), f₁(x), f₂(x) для проверки реализации φ*(x) $ \prec $ ($f_{1}^{*}$(x) $ \vee $ $f_{2}^{*}$(x)). Рассмотрим третью строку табл. 2, в которой  f₁(x) = 0,  f₂(x) = 0, φ(x) = “–”. Для выполнения дизъюнктивного разложения нужно заменить значение “–” на 0: φ(x) = 0. Аналогично можно доопределять значения “–” и для других строк из табл. 2, не содержащих пометку “Нет решения”.

У т в е р ж д е н и е 2. Задача нахождения разложения (2.2) не имеет решения тогда и только тогда, когда верно хотя бы одно из условий (2.6)–(2.8):

Условия (2.6)–(2.8) можно задать в табличном виде (табл. 3). Таблица 4 позволяет проверить возможность доопределения функций φ(x),  f₁(x),  f₂(x) для проверки реализации φ*(x) $ \prec $ ($f_{1}^{*}$(x) & $f_{2}^{*}$(x)), замены неопределенных значений “–” нулями или единицами в строках, не содержащих пометку “Нет решения”, всегда могут быть выполнены для конъюнктивного разложения.

Аналогичным образом могут быть рассмотрены условия доопределения функций φ(x), f₁(x), f₂(x) для получения алгебраических разложений по другим выходным функциям, например, таким, как инверсия дизъюнкции, инверсия конъюнкции, исключающее ИЛИ, эквиваленция и т.д.

П р и м е р 1. Приведем пример (табл. 5) такого доопределения частичных функций, заданных таблицами истинности, чтобы выполнялось алгебраическое разложение (2.2). В табл. 5 жирным курсивом выделены замены неопределенных значений функций определенными (0, 1).

3. Ортогонализованные формы частичной векторной булевой функции. Интервальная форма задания частичной векторной функции  f(x) = (f₁(x), …, f_m(x)) состоит из троичной матрицы T ^x задания элементарных конъюнкций и троичной матрицы T  ^f вхождений конъюнкций в ДНФ, представляющих области нулевых и единичных значений компонентных функций. Данная форма задания частичных функций подробно описана в литературе [21]. Если в матричном задании в троичной матрице T ^x все строки (троичные векторы) ортогональны, то такая матричная форма представления векторной булевой функции называется ортогонализованной. Для ортогонализованной формы строки матрицы T  ^f задают значения функций на соответствующих интервалах булева пространства V ^x. Алгоритмы получения ортогонализованных форм систем функций по исходным интервальным формам известны из [21, 22]. Более компактной по сравнению с ортогонализованной является обобщенно ортогонализованная форма, когда частичная векторная функция задается на попарно ортогональных ДНФ, а не на попарно ортогональных интервалах (конъюнкциях), как это осуществляется в ортогонализованных формах. Данная форма представления является более компактной и удобной для решения задач, возникающих при доопределении частичных функций, например с целью сокращения сложности BDD [7].

Нахождение обобщенно ортогонализованной формы для частичной векторной булевой функции  f(x) = (f₁(x), …, f_m(x)) сводится к решению задачи нахождения ее минимального дизъюнктивного базиса. Зададим каждую компонентную частичную булеву функцию f_i(x) тремя полностью определенными булевыми функциями $\lambda _{i}^{0}$(x), $\lambda _{i}^{1}$(x), $\lambda _{i}^{ - }$(x), такими, что функция $\lambda _{i}^{0}$(x) имеет характеристическое множество $M_{{{{f}_{i}}}}^{0}$, функция $\lambda _{i}^{1}$(x) – характеристическое множество $M_{{{{f}_{i}}}}^{1}$, функция $\lambda _{i}^{ - }$(x) – характеристическое множество $M_{{{{f}_{i}}}}^{ - }$. Минимальным дизъюнктивным базисом для f(x) = (f₁(x), …, f_m(x)) называется минимальная по мощности система попарно ортогональных полностью определенных булевых функций Π = {Π¹(x), …, Π ^k(x)}, такая, что каждая полностью определенная функция $\lambda _{i}^{0}$(x), $\lambda _{i}^{1}$(x), $\lambda _{i}^{ - }$(x) равна дизъюнкции некоторого подмножества функций системы Π. Частичная булева функция  f_i(x) задает трехблочное разбиение R_i = {$M_{{{{f}_{i}}}}^{0}$, $M_{{{{f}_{i}}}}^{1}$, $M_{{{{f}_{i}}}}^{ - }$} булева пространства V^x на попарно непересекающиеся подмножества. Нахождение для  f(x) = = (f₁(x), …, f_m(x)) минимального дизъюнктивного базиса (в теоретико-множественной интерпретации) может быть сведено к нахождению произведения разбиений R_i, $i = \overline {1,m} $, [23, с. 12] и составлению из непустых блоков полученного произведения разбиений каждого из исходных блоков $M_{{{{f}_{i}}}}^{0}$, $M_{{{{f}_{i}}}}^{1}$, $M_{{{{f}_{i}}}}^{ - }$. Пусть каждая компонентная функция f_i задана тройкой попарно ортогональных ДНФ $D_{{{{f}_{i}}}}^{0}$, $D_{{{{f}_{i}}}}^{1}$, $D_{{{{f}_{i}}}}^{ - }$, данные ДНФ представляют функции $\lambda _{i}^{0}$(x), $\lambda _{i}^{1}$(x), $\lambda _{i}^{ - }$(x) соответственно. В этом случае нахождение минимального дизъюнктивного базиса Π может быть сведено к выполнению операций перемножения, инверсирования и сравнения на равенство ДНФ, алгоритм описан в [24, с. 124]. Он оперирует исходными данными для случая, когда каждая из функций задана элементарной конъюнкцией. Алгоритм пригоден и для случая задания функций $\lambda _{i}^{0}$(x), $\lambda _{i}^{1}$(x), $\lambda _{i}^{ - }$(x) в виде ДНФ. Он программно реализован и использован при решении задачи декомпозиции системы булевых функций. Примеры разбиения булева пространства на непересекающиеся подмножества (характеристические множества попарно ортогональных базисных функций Π¹(x), …, Π^k(x)) показаны в [7, с. 135; 24, с. 120].

П р и м е р 2. Пусть каждая из частичных компонентных функций  f₁,  f₂,  f₃ векторной булевой функции  f(x) = (f₁(x),  f₂(x),  f₃(x)), x  = (x₁, x₂, x₃, x₄), задана тремя ДНФ, представляющими области нулевых, единичных и неопределенных значений этой компонентной функции (табл. 6). Чтобы решить задачу нахождения дизъюнктивного разложения (2.1), построим для данных трех функций минимальный дизъюнктивный базис и обобщенно ортогонализованную форму.

Ортогонализованная форма векторной функции  f(x) = (f₁(x),  f₂(x),  f₃(x)) задана в табл. 7. Легко проверить, что каждая пара элементарных конъюнкций, соответствующих троичным векторам из левой части табл. 7, находится в отношении ортогональности (для ортогональных элементарных конъюнкций их произведение равно нулю). Например, рассмотрим первую пару: троичному вектору (0 0 0 –) соответствует элементарная конъюнкция ${{\bar {x}}_{1}}{{\bar {x}}_{2}}{{\bar {x}}_{3}}$, булеву вектору (0 1 0 1) – полная элементарная конъюнкция ${{\bar {x}}_{1}}{{x}_{2}}{{\bar {x}}_{3}}{{x}_{4}}$, они ортогональны по второй компоненте: (${{\bar {x}}_{1}}{{\bar {x}}_{2}}{{\bar {x}}_{3}}$) & & (${{\bar {x}}_{1}}{{x}_{2}}{{\bar {x}}_{3}}{{x}_{4}}$) = 0.

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

Обобщенно ортогонализованная форма частичной векторной функции  f(x) = (f₁(x),  f₂(x),  f₃(x)) дана в табл. 8. Легко видеть, что значения функций на наборах, соответствующих полным элементарным конъюнкциям минимального дизъюнктивного базиса, являются одинаковыми. Теперь легко доопределить функции  f₁,  f₂,  f₃ из табл. 6 так, что возможно провести разложение $f_{3}^{*}$ $ \prec $ ($f_{1}^{*}$ $ \vee $ $f_{2}^{*}$) (табл. 9). Перейдя от ортогонализованной формы (табл. 7) либо от табл. 8 к таблице истинности (табл. 10) частичной векторной функции f(x) = (f₁(x), f₂(x), f₃(x)), можно убедиться, что обобщенно ортогонализованная форма более компактна по сравнению с ортогонализованной формой и значительно более компактна по сравнению с таблицей истинности.

У т в е р ж д е н и е 3. Приведенные в табл. 2, 4 доопределения функций для построения разложений (2.1), (2.2) соответственно справедливы для задания функций таблицами истинности, ортогонализованными, обобщенно ортогонализованными формами и графами BDD.

При задании функций BDD проверка возможности доопределения функций, участвующих в разложениях (2.1), (2.2), сводится к логическим операциям над соответствующими BDD: сначала выполняется операция слияния BDD, реализующих f₁(x), f₂(x), φ(x), т.е. строится BDD векторной функции  f  = (f₁(x),  f₂(x), φ(x)), затем для листовых вершин, заданных трехкомпонентными троичными векторами, проверяются условия возможности доопределения, приведенные в табл. 2 либо табл. 4.

4. Задача нахождения алгебраически представимых функций. Обозначим через G = {g₁, …, g_k} множество частичных функций. Найдем в множестве G (если это возможно) максимальное по мощности подмножество G^c функций, которые могут быть выражены через дизъюнкцию либо конъюнкцию пар функций, не вошедших в множество G^c. Это, естественно, происходит при соответствующем доопределении частичных функций, входящих в разложения. Назовем функции из множества G^b = G\G^c основными (базисными), а функции из множества G^c – представимыми. Каждая функция из множества G^c при этом должна задаваться в алгебраическом (дизъюнктивном либо конъюнктивном) разложении своей парой базисных функций, т.е. каждая основная функция может входить в разложение только одной функции из G^c.

З а д а ч а 2. Для заданного множества G = {g₁, …, g_k} частичных функций требуется найти в G максимальное по мощности подмножество G^c представимых функций (главный критерий) и при этом требуется минимизировать суммарное множество наборов, на которых доопределяются базисные функции (дополнительный критерий оптимизации).

Составим множество всех неупорядоченных пар {g_i, g_j} функций, i, j = $\overline {1,k} $, i ≠ j. Для каждой пары {g_i, g_j} проверим выполнение отношения реализации:

т.е. решим задачу 1 нахождения разложений (2.1), (2.2) для троек функций g_i, g_j, g_s (с учетом возможности их доопределения). Если реализация (4.1) возможна, то присвоим ей вес ρ(g_i, g_j, g_s, $ \vee $), равный числу неопределенных значений функций g_i, g_j, которые надо заменить определенными.

Если реализация (4.2) возможна, то присвоим ей вес ρ(g_i, g_j, g_s, &), равный числу неопределенных значений функций g_i, g_j, которые надо заменить определенными. Составим двудольный неориентированный граф R, вершины первой доли помечены парами {g_i, g_j}, вершины второй доли – функциями множества G. Число вершин первой доли равно $C_{k}^{2}$, число вершин второй доли – k. Если пара {g_i, g_j} не реализует g_s ни в виде (4.1), ни в виде (4.2), то между вершинами {g_i, g_j}, g_s нет ребра. Если же реализация в виде (4.1) возможна, а реализация (4.2) невозможна, то ребру присваивается вес ρ(g_i, g_j, g_s, $ \vee $); и наоборот, если реализация в виде (4.2) возможна, а реализация (4.1) невозможна, то ребру присваивается вес ρ(g_i, g_j, g_s, &). Если же частичные функции такие, что возможны обе реализации (4.1) и (4.2), то ребру между вершинами {g_i, g_j} и g_s присваивается вес

Каждое ребро 〈{g_s, g_j}, g_s〉 графа R задает тройку функций, реализующих дизъюнктивное (4.1) либо конъюнктивное (4.2) разложение.

Для построения графа R для каждой функции g_s, $s = \overline {1,k} $, требуется рассмотреть $C_{k}^{2}$ – (k – 1) вариантов пар проверки возможности дизъюнктивного разложения (исключаются k – 1 пар (g_i, g_s), i ≠ s;) и столько же $C_{k}^{2}$ – (k – 1) вариантов пар проверки возможности конъюнктивного разложения.

Таким образом, для построения графа R требуется проверить

вариантов получения формул (2.1), (2.2) для G = {g₁, …, g_k}.

Двудольный граф для G = {g₁, g₂, g₃, g₄} для подсчета числа Z вариантов приведен на рис. 1. В графе на рис. 1 имеется 12 ребер (k = 4) для проверки дизъюнктивного разложения и соответственно столько же ребер для проверки конъюнктивного разложения, поэтому Z = 2 × 4 × ($C_{4}^{2}$ – – (4 – 1)) = 8(6 – 3) = 24.

С использованием графа R решение задачи 2 можно свести к нахождению такого паросочетания графа, которое содержит максимальное количество ребер имеющих минимальный суммарный вес. При этом пометки вершин каждого ребра, вошедшего в паросочетание, должны задавать различные тройки функций. Множество G ^c представимых функций будут образовывать функции, помечающие вершины второй доли.

4.1. Э в р и с т и ч е с к и й а л г о р и т м р е ш е н и я з а д а ч и 2.

Ш а г 1. Вычислить для каждого ребра 〈{g_i, g_j}, g_s〉 графа R оценку α(g_i, g_j, g_s) – число неизолированных вершин в сокращенном графе R, из которого удалено ребро 〈{g_i, g_j}, g_s〉 и исключены из первой доли графа R вершины-пары (в них входит g_i  либо g_b, либо g_j), а из второй доли исключена вершина g_s.

Ш а г 2. Найти ребро между вершинами 〈{g_a, g_b}, g_c〉 графа R, которое характеризуется максимальной оценкой α(g_a, g_b, g_c), и включить его в решение. Заметим, что каждое ребро помечено одним из видов разложения (конъюнктивным либо дизъюнктивным). Если таких ребер несколько, то выбрать ребро, характеризуемое минимальным значением веса ρ. Если и таких ребер несколько, то выбрать первое из них.

Ш а г 3. Редуцировать граф, т.е. исключить из первой доли графа R вершины-пары, в которые входит g_a либо g_b, либо g_c, а также исключить вершину g_c из второй доли.

Ш а г 4. Выполнять шаги 1, 2 до тех пор, пока в графе R не останется ребер. Перейти на шаг 5.

Ш а г 5. Конец.

5. Использование инверсий функций при их алгебраическом разложении. Поиск алгебраических разложений может быть осуществлен с учетом инверсирования функций – некоторые функции нельзя представить в виде алгебраических разложений, но их инверсии могут быть представимы. Тогда в уравнение для соответствующей переменной добавляется оператор инверсии. Рассмотрим задачу 2 для случая, когда могут быть использованы для дизъюнктивных либо конъюнктивных разложений функции множества G как в инверсной ${{\bar {g}}_{1}}$, …, ${{\bar {g}}_{k}}$, так и прямой g₁, …, g_k форме.

Так как каждая из функций g_s рассматривается как в прямой g_s, так и инверсной ${{\bar {g}}_{s}}$ форме, поэтому в первой (левой) доли графа R  будет $C_{{2k}}^{2}$ – k неупорядоченных пар-вершин (пары {g_i, g_i}, {${{\bar {g}}_{i}}$, ${{\bar {g}}_{i}}$}, {g_i, ${{\bar {g}}_{i}}$} не рассматриваются), в правой доли – 2k вершин g₁, ${{\bar {g}}_{1}}$, g₂, ${{\bar {g}}_{2}}$ ,…, g_k, ${{\bar {g}}_{k}}$. По сути, каждое ребро ({g_i, g_j}, g_s) на рис. 1 заменяется подграфом, показанным на рис. 2. Описанный ранее эвристический алгоритм решения задачи 2 подвергается модификации: в шагах 1–3 алгоритма при нахождении оценки α(g_i, g_j, g_s) ребра 〈{g_i, g_j}, g_s〉 и ребра 〈{g_a, g_b}, g_c〉, включаемого в решение, из первой доли графа R исключаются вершины-пары, в которые входит любая функция из множества {g_a, ${{\bar {g}}_{a}}$, g_b, ${{\bar {g}}_{b}}$, g_c, ${{\bar {g}}_{c}}$}, из второй доли исключаются две вершины g_c и ${{\bar {g}}_{c}}$.

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

6. Пример BDD для частичной векторной функции. П р и м е р 3. Рассмотрим BDD (рис. 3) для частичной векторной функции  f(x) = (f₁, f₂, f₃), заданной таблицей истинности (табл. 11), по перестановке переменных 〈x₁, x₂, x₃, x₄, x₅〉.

Алгоритм построения BDD для частичных векторных функций описан в [7, с. 56] и сводится к нахождению одинаковых подфункций, найденных в результате разложения Шеннона по переменной x₁ исходных компонентных функций f₁, f₂, f₃, разложением Шеннона по переменной x₂ различных частичных подфункций h₁, …, h₅, полученных на шаге 1 разложения, и т.д. Графу BDD (рис. 3) соответствуют формулы разложений Шеннона, заданные в правом столбце табл. 11, при этом частичные функции t₁, …, t₉ первого уровня BDD приведены в табл. 12. Кофакторы первого уровня зависят от одной переменной x₅ и являются частичными функциями. Число частичных булевых функций, зависящих от n переменных, определяется по формуле ${{3}^{{{{2}^{n}}}}}$. Для n = 1 имеется девять частичных функций, заметим, что все они заданы на первом уровне BDD (рис. 3).

На третьем уровне BDD имеется девять кофакторов g₁, …, g₉, на четвертом – пять кофакторов, на пятом (корневом уровне BDD) – три корневые вершины разлагаемых компонентных частичных функций. Если какая-то дуга BDD пересекает рассматриваемый уровень BDD и заходит в функциональную вершину α более низкого уровня, то считается, что на данном уровне BDD есть кофактор α, зависящий от меньшего числа аргументов. Позже будут представлены примеры таких BDD.

Из BDD можно получить области определения как исходных функций, так и любого из кофакторов, это подробно описано в [7, с. 37]. Каждому пути из корневой вершины BDD, помеченной функцией  f_j, к листовой вершине 1 соответствует элементарная конъюнкция, включающая дуги (литералы) x_i, ${{\bar {x}}_{i}}$ на этом пути. При этом дуге, помеченной символом 0, соответствует отрицательный литерал ${{\bar {x}}_{i}}$; дуге, помеченной символом 1, – положительный литерал x_i, а всем путям между указанными вершинами – дизъюнкция получаемых элементарных конъюнкций, образующая ортогонализованную ДНФ $D_{{{{f}_{j}}}}^{1}$. Пути из корневой вершины  f_j  к листовой вершине 0 задают ортогонализованную ДНФ $D_{{{{f}_{j}}}}^{0}$, а пути к вершине “–” – ортогонализованную ДНФ $D_{{{{f}_{j}}}}^{ - }$. При построении ДНФ, описывающих области определения кофактора, вместо корневой вершины BDD рассматривается функциональная вершина данного кофактора.

Например, области нулевых, единичных и неопределенных значений кофактора g₁, полученные из графа BDD (рис. 3), задаются следующими ортогонализованными ДНФ:

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

Э т а п 1. Нахождения алгебраически представимых кофакторов.

Выполняется для каждого уровня BDD, начиная с уровня кофакторов, получаемых в результате разложения Шеннона по первой переменной, и исключая последний листовой уровень, на котором расположены константы 0, 1, “–”. Исключается из рассмотрения также первый уровень BDD, соответствующий разложению по последней переменной в заданной перестановке переменных, по которым ведется разложение Шеннона.

З а м е ч а н и е 2. Метод может быть применен с выбранного уровня BDD, двигаясь как вниз, так и вверх по уровням BDD. При движении вверх рассмотрение кофакторов начинается со второго уровня BDD.

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

Ш а г 1. Выбор формы представления кофакторов данного уровня BDD (таблица истинности; пара ДНФ, задающая области определения кофактора; подграф BDD) и задание кофакторов в требуемой форме.

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

Ш а г 3. Нахождение максимального по мощности множества частичных кофакторов, которые представимы в виде конъюнкции либо дизъюнкции базисных частичных кофакторов того же уровня BDD – решение задачи 2. Доопределение частичных кофакторов, участвующих в алгебраических разложениях, до полностью определенных.

Ш а г 4. Исключение представимых кофакторов, участвующих в алгебраических разложениях, из шага 5.

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

Ш а г 6. Сокращение BDD на верхних уровнях в случае, если сократилось число кофакторов рассматриваемого уровня за счет доопределения и появления одинаковых функциональных вершин.

Э т а п 2. Доопределение частичной BDD до полностью определенной.

Если после выполнения этапа 1 в BDD остаются листовые вершины “–”, то выполняется замена листовых значений “–” константами 0, 1, т.е. осуществляется доопределение частичной BDD до полностью определенной с возможным выполнением процедуры сокращения BDD [20].

Э т а п 3. Формирование функционального представления системы полностью определенных функций в виде формул разложений Шеннона и формул для представимых кофакторов.

Э т а п 4. Дополнительная оптимизация на основе метода [17] алгебраического разложения полностью определенных кофакторов.

На каждом (из рассматриваемых в методе) уровне BDD, на котором были найдены алгебраические разложения частичных кофакторов, исключаются представимые кофакторы, а для оставшихся решается задача нахождения алгебраических разложений [17], сокращаются множества базисных кофакторов и формируется результирующее многоуровневое представление.

Э т а п 5. Проверка отношения реализации “$ \prec $” между исходной BDD частичной векторной функцией и результирующим многоуровневым представлением.

Общий вид многоуровневого представления векторной функции f(x) = (f₁(x), …, f_m(x)), получаемого предлагаемым методом, показан на рис. 4. Нахождение алгебраически представимых кофакторов может быть выполнено и в процессе построения BDD при задании в виде ДНФ областей определения компонентных функций исходной частичной векторной функции. Кроме того, предлагаемый метод обобщается на случай других выходных функций алгебраических разложений, таких, как исключающее ИЛИ, эквиваленция, а также на случай, когда выходные функции представляют собой n-операндные алгебраические функции дизъюнкции, конъюнкции.

8. Пример применения метода минимизации многоуровневого BDD-представления частичной векторной функции от верхних уровней BDD. Проиллюстрируем метод на примере 3 (рис. 3) векторной булевой функции (табл. 11), начиная с третьего уровня BDD. Подграф BDD, построенный после разложения функций  f₁, f₂, f₃ по переменным x₁, x₂, показан на рис. 5. Данному подграфу соответствуют следующие формулы разложения Шеннона:

Таким образом, на третьем уровне BDD имеются девять кофакторов g₁, …, g₉.

Э т а п 1. Нахождения алгебраически представимых кофакторов на третьем уровне BDD.

Ш а г 1. Выбор формы представления кофакторов.

Алгебраические разложения кофакторов можно проводить по ортогонализованным ДНФ либо по обобщенно ортогонализованным формам, либо по подграфам BDD. Для удобства изложения примера будем рассматривать таблицу истинности (табл. 13) кофакторов g₁, …, g₉ (частичных подфункций, зависящих от переменных x₃, x₄, x₅).

Ш а г 2. Нахождение на третьем уровне BDD пар взаимно инверсных кофакторов.

В данном примере нет пар взаимно инверсных кофакторов, поэтому на шаге 3 рассматриваются кофакторы g₁, …, g₉.

Ш а г 3. Решение задачи 2 для кофакторов третьего уровня BDD и доопределение частичных кофакторов, участвующих в алгебраических разложениях, до полностью определенных.

Для третьего уровня BDD множество G = {g₁, …, g₉} составляют девять (k = 9) кофакторов, $C_{9}^{2}$ = 36 – множество всех неупорядоченных пар кофакторов из такого множества, Z – число перебираемых вариантов проверки существования разложений (4.2), (4.3) для построения графа R:

В качестве одного из решений задачи 2 для множества G = {g₁, …, g₉} было получено решение (рис. 6) из шести базисных функций g₁,  g₂,  g₃,  g₄,  g₅,  g₇ с разложениями $g_{7}^{*}$ $ \prec $ ($g_{1}^{*}$ $ \vee $ $g_{2}^{*}$), $g_{8}^{*}$ $ \prec $ ($g_{3}^{*}$ & $g_{4}^{*}$), $g_{6}^{*}$ = ($g_{5}^{*}$ & $g_{9}^{*}$) трех представимых функций $g_{6}^{*}$, $g_{7}^{*}$, $g_{8}^{*}$ и с суммарным числом (девять) замен неопределенных значений определенными. В данном примере число заменяемых неопределенных значений функций определенными подсчитывалось по таблицам истинности функций. Если сравнение функций производится по ортогонализованным формам, то число замен неопределенных значений подсчитывается по таблицам, задающим ортогонализованные формы, если используются подграфы BDD, то – по заменам значений листовых вершин BDD.

Доопределения функций g₁, g₇, g₃, g₄, g₈, g₅, g₆, g₉  для разложений $g_{7}^{*}$ $ \prec $ ($g_{1}^{*}$ $ \vee $ $g_{2}^{*}$), $g_{8}^{*}$ $ \prec $ ($g_{3}^{*}$ & $g_{4}^{*}$), $g_{6}^{*}$ = $g_{5}^{*}$ & $g_{9}^{*}$ даны в табл. 14–16 соответственно, доопределенные значения выделены жирным курсивом. Выполнять доопределение частичных кофакторов нужно, используя табл. 2, 4. Если для некоторого набора значений переменных (см. последние строки в табл. 2, 4) значения всех кофакторов, участвующих в дизъюнктивном либо конъюнктивном разложениях, не определены, то замена всех значений “–” нулевыми значениями переведет частичные функции в класс полностью определенных и тогда отношение реализации можно заменить отношением равенства. Выполним, не нарушив отношения реализации, доопределения частичных кофакторов из табл. 14–16 следующим образом: $g_{1}^{*}$(1, 0, 0) = 0; $g_{2}^{*}$(1, 1, 1) = 0; $g_{3}^{*}$(1, 1, 0) = 0; $g_{8}^{*}$(1, 1, 0) = 0, получим полностью определенные кофакторы (табл. 17). Теперь отношение реализации в формулах $g_{7}^{*}$ $ \prec $ ($g_{1}^{*}$ $ \vee $ $g_{2}^{*}$) $g_{8}^{*}$ $ \prec $ ($g_{3}^{*}$ & $g_{4}^{*}$) можно заменить отношением равенства и записать формулы алгебраических разложений:

Граф BDD c реализацией кофакторов в виде алгебраических разложений показан на рис. 7. Этому графу соответствуют логические формулы:

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

Ш а г 4. Исключение представимых кофакторов из рассмотрения. Кофакторы $g_{6}^{*}$, $g_{7}^{*}$, $g_{8}^{*}$ удаляются из шага 5.

Ш а г 5. Построение BDD, реализующей доопределенные базисные кофакторы.

Дальнейшее построение многоуровневого представления связано с рассмотрением шести полностью определенных кофакторов $g_{1}^{*}$, $g_{2}^{*}$, $g_{3}^{*}$, $g_{4}^{*}$, $g_{5}^{*}$, $g_{9}^{*}$ из табл. 17. Разложение Шеннона по переменной x₃, кофакторов, заданных в табл. 17, приводит к следующим формулам (8.2), где кофакторы, зависящие от двух переменных x₄ и x₅, приведены в табл. 18:

На рис. 8 показана BDD, реализующая полностью определенные кофакторы третьего уровня. Если сравнить три нижних уровня исходной BDD (рис. 3) и BDD из рис. 8, то можно легко увидеть, что BDD на рис. 8 не содержит неопределенных листовых вершин “–”.

Шаг 6 не выполняется – одинаковые функциональные вершины в результате преобразования графа BDD не появились.

Н а х о ж д е н и е а л г е б р а и ч е с к и п р е д с т а в и м ы х к о ф а к т о р о в н а в т о р о м у р о в н е B D D. Исходной является BDD на рис. 8.

Э т а п 1. Ш а г 1. Выбор формы представления кофакторов.

Будем рассматривать кофакторы, заданные таблицей истинности (табл. 18).

Ш а г 2. Нахождение пар взаимно инверсных кофакторов.

Для неконстантных функций с помощью метода из работы [20] найдем множество функций (табл. 19), к которым (либо к их инверсиям) доопределяются кофакторы из табл. 18. С учетом того, что w₈ = 1, w₂ = w₃, w₄ = w₁, w₆ = w₁, w₁₀ = ${{\bar {w}}_{7}}$, w₁₁ = w₉, w₁₂ = ${{\bar {w}}_{9}}$, формулы (8.2) перепишутся в виде

Ш а г 3. Нахождение максимального по мощности множества кофакторов из табл. 19, которые представимы в виде конъюнкции либо дизъюнкции кофакторов рассматриваемого уровня BDD.

Будем искать алгебраические разложения полностью определенных кофакторов из табл. 19, используя другие кофакторы из этой же таблицы. Для случая полностью определенных функций не требуется доопределение базисных кофакторов, поэтому один и тот же кофактор может участвовать в разложении нескольких кофакторов. Метод решения этой задачи для полностью определенных кофакторов рассмотрен в [17]. Применяя данный метод, получим, то что инверсии ${{\bar {w}}_{5}}$, ${{\bar {w}}_{7}}$ представимых кофакторов w₅, w₇ выражаются через основные кофакторы w₁, w₃, w₉  следующим образом: ${{\bar {w}}_{5}} = {{w}_{7}}\& {{w}_{9}}$, ${{\bar {w}}_{7}} = {{w}_{1}}\& {{w}_{3}}$. Последние формулы можно переписать как

Итак, на втором уровне BDD остаются базисные кофакторы w₁, w₃, w₉, реализация которых в виде BDD приводит к формулам w₁ = ${{\bar {x}}_{4}}{{\bar {x}}_{5}}$; w₃ = x₄x₅; w₉ = x₅. Граф BDD, реализующий кофакторы второго уровня BDD с учетом возможности использования их инверсий, показан на рис. 9.

Э т а п 2. Доопределение частичной BDD до полностью определенной.

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

Э т а п 3. Формирование функционального представления в виде формул разложений Шеннона и формул для представимых кофакторов.

Логические уравнения после алгебраического разложения кофакторов на третьем и втором уровнях BDD будут иметь следующий вид:

Формулы (8.4) содержат 19 внутренних переменных и 70 литералов.

Э т а п 4. Дополнительная оптимизация на основе метода [17] алгебраического разложения полностью определенных кофакторов.

На втором уровне BDD рассматривались полностью определенные кофакторы, поэтому для этого уровня дополнительная оптимизация не выполняется. На третьем уровне BDD располагаются базисные кофакторы $g_{1}^{*}$, $g_{2}^{*}$, $g_{3}^{*}$, $g_{4}^{*}$, $g_{5}^{*}$, $g_{9}^{*}$, которые изначально были частичными, а затем стали полностью определенными. Для них выполняется дополнительная оптимизация, в результате выясняется, что множество базисных кофакторов можно сократить (удалить кофактор $g_{2}^{*}$), так как справедливо конъюнктивное разложение $g_{2}^{*}$ = $g_{3}^{*}$ & $g_{5}^{*}$. Формируется результирующее многоуровневое представление:

Формулы (8.5) содержат 19 внутренних переменных и 68 литералов. Результирующий граф BDD, соответствующий формулам (8.5), показан на рис. 10. Алгебраическое представление кофакторов в виде дизъюнкций и конъюнкций на третьем и втором уровнях BDD позволяет уменьшить общее число литералов в результирующем многоуровневом представлении полностью определенной векторной функции, которая реализует частичную векторную функцию из табл. 11. Получение многоуровневого представления системы полностью определенных функций позволяет применить для такого представления еще раз (на этапе 4) метод алгебраических разложений [17], на этот раз уже для полностью определенных кофакторов.

Э т а п 5. Проверка отношения реализации “$ \prec $” между исходной BDD частичной векторной функцией и многоуровневым представлением.

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

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

Рассмотрим частичные кофакторы на втором уровне BDD (табл. 20). С помощью методов из [20] найдем минимальное число кофакторов, к которым доопределяются частичные кофакторы из табл. 20 – это кофакторы p₃, p₇, p₉, p₁₂, p₁₅, p₅ = p₈ = 1 (табл. 21). При этом частичные кофакторы p₉, p₁₅, p₅, p₈  доопределены, им оставлены прежние обозначения. В нижней строке табл. 21 указаны кофакторы, которые реализуются соответствующими доопределенными кофакторами из верхней части этой таблицы. Найдем BDD-представление кофакторов p₃, p₇, p₉, p₁₂, p₁₅ и выполним сокращение BDD, так как выясняется, что

Обозначим u₇ = ${{\bar {p}}_{7}}$, тогда многоуровневое представление из табл. 11 принимает вид

Сложность формул (9.1): 20 внутренних переменных, 78 литералов. Заметим, что доопределение снизу может потребовать выполнения процедуры сокращения верхней части BDD тогда, когда в результате доопределения появились одинаковые кофакторы.

Перейдем к нахождению алгебраических разложений кофакторов из табл. 21. Заметим, что кофакторы p₃ = x₄x₅, p₁₂ = ${{\bar {x}}_{4}}{{\bar {x}}_{5}}$ , p₁₅ = ${{x}_{4}}{{\bar {x}}_{5}}$ реализуются одной логической операцией “конъюнкция” и нет смысла находить их алгебраические разложения, это касается и кофактора p₉ = x₅. Кофактор p₇ = ${{\bar {x}}_{4}}{{x}_{5}}$ $ \vee $ ${{x}_{4}}{{\bar {x}}_{5}}$ можно представить в виде алгебраического разложения p₇ = $\overline {{{p}_{3}} \vee {{p}_{{12}}}} $.

Рассмотрим третий уровень BDD, на котором находятся полностью определенные кофакторы, заданные в табл. 22. По сравнению кофакторами из табл. 17, исходные частичные кофакторы g₃ и g₉ (табл. 22) доопределены по-другому (эти доопределения в табл. 22 отмечены жирным курсивом), в результате чего только один кофактор g₇ может быть алгебраически разложен: g₇ = g₁$ \vee $ g₂.

Многоуровневое представление при разложении кофакторов от нижних уровней BDD имеет вид (9.2) и сложность 20 внутренних переменных, 74 литералов:

10. Сравнение с другими методами доопределения частичных векторных функций. 10.1. “Н у л е в о е д о о п р е д е л е н и е”. Если не проводить алгебраические разложения кофакторов, а заменить в табл. 11 все неопределенные значения “–” компонентных функций нулевыми значениями (выполнить “нулевое” доопределение), то получим многоуровневое BDD-представление с 20 внутренними переменными и 79 литералами. Заметим, что при “нулевом” доопределении можно провести алгебраическое разложение только одного полностью определенного кофактора g₇ в виде g₇ = g₁$ \vee $ g₂.

10.2. “С о в м е с т н а я м и н и м и з а ц и я в к л а с с е ДНФ”. Совместная минимизация в классе ДНФ исходных частичных функций с помощью программы из [25] приводит к системе ДНФ, содержащей 21 элементарную конъюнкцию. BDD-представление (по найденной лучшей перестановке 〈x₁, x₃, x₂, x₄, x₅〉) полученной системы полностью определенных функций с помощью программы из [16] содержит 19 внутренних переменных в формулах разложений Шеннона и 76 литералов в этих формулах. Такой результат свидетельствует о том, что целесообразно развивать методы многоуровневой оптимизации для частичных функций, а не минимизировать функции в классе ДНФ и проводить для минимизированных ДНФ оптимизацию в классе BDD.

10.3. “Д о о п р е д е л е н и е B D D”. Доопределение BDD (формул из табл. 11), начинаемое с листьев и  выполняемое  по правилам  (табл. 23), где t_i  $ \prec $  $t_{i}^{*}$,  i  = 1, …, 9, c последующим сокращением BDD приводит к нахождению одинаковых функциональных вершин: p₁₇ = p₃; p₅ = = p₈ = 1; p₄ = p₆ = p₁₂; p₂ = p₁₅ и получению следующих уравнений:

Уравнения (10.1) содержат 24 внутренних переменных и 89 литералов.

Приведем в табл. 24 полностью определенные векторные функции, являющиеся доопределениями частичной векторной функции из табл. 11. Жирным курсивом в табл. 24 выделены полностью определенные значения (0, 1) функций, которые заменили неопределенные значения “–” исходных компонентных частичных функций.

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