eng
Содержание
Введение 5
Глава 1. Основные понятия, термины, определения 7
1.1.
Булева алгебра 7
1.2.
Формирование графа булевых функций 11
1.3.
Двузначная булева алгебра (алгебра логики) 13
1.4.
Бинарные диаграммы решений (BDD) 19
1.5.
Логическая схема 24
Упражнения 27
Глава 2. Графовые модели КМОП-схем 28
2.1.
Формализация модели КМОП-схемы 28
2.2.
Обобщенный метод декомпозиции КМОП-схемы
с разветвленными цепями земли и питания 36
2.3.
Формирование многоуровневой графовой модели
КМОП-схемы 47
2.4.
Структурная интерпретация графа булевых функций в классе
стандартных КМОП-вентилей 57
Упражнения 63
Глава 3. Анализ помехоустойчивости цифровых схем: основные понятия 66
3.1.
Консервативный метод суммарного влияния узлов-агрессоров
на узел-жертву 66
3.2.
Типы шумов в цифровой схеме (Low Overshoot, High Undershoot,
Low Undershoot, High Overshoot, Falling Slow, Falling Fast, Rising
Slow, Rising Fast) 69
3.3.
Учет логических корреляций в анализе шумов 72
Упражнения 73
Глава 4. Анализ логических корреляций в схеме
на основе метода импликаций 74
4.1.
Понятие простой логической импликации 74
4.2.
Операции над списками простых логических импликаций 76
4.3.
Прямое распространение простых логических импликаций 79
4.4.
Боковое распространение простых логических импликаций 81
4.5.
Преимущества и недостатки метода импликаций 85
Упражнения 86
Глава 5. Анализ логических корреляций в схеме
на основе метода резолюций 88
5.1.
Адаптация метода резолюций для анализа логики цифровой
КМОП-схемы 88
5.2.
Метод резолюций, модифицированный для анализа помех
цифровой КМОП-схемы 97
5.3.
Формирование характеристических диаграмм решений при
анализе помех 98
Глава 6. Анализ влияния шумов на быстродействие схемы 114
6.1.
Анализ помех, влияющих на задержку, в цифровых СБИС 114
6.2.
Логические ограничения и анализ помехоустойчивости 119
6.3.
MWIS(МВНН) – метод анализа влияния шумов
на быстродействие 120
Глава 7. Особенности анализа динамических КМОП-схем 122
7.1.
Генерация дополнительных ограничений для «домино»-схем 122
7.2.
Анализ помехоустойчивости «домино»-схем 128
Приложение А 132
Список литературы 132
Введение
Развитие технологии СБИС приводит к постоянному уменьшению
минимальных размеров элементов и повышению степени интегра-
ции. В этих условиях методы и алгоритмы, используемые в САПР
СБИС, оказываются недостаточно производительными для реаль-
ного проектирования. Возникает потребность в новом поколении
методов и алгоритмов, в том числе методов логического и логико-
временного анализа КМОП СБИС на стадиях проектирования
электрической схемы и верификации топологии.
Процедуры анализа и верификации проектных решений со-
ставляют основу логического проектирования современных циф-
ровых КМОП СБИС. Для выполнения верификации необходимо
располагать математическими моделями и алгоритмами логиче-
ского и логико-временного анализа. В случае схем субмикронного
и нанометрового диапазонов при анализе логики уже нельзя обой-
тись без учета ряда электрических эффектов, которые для схем с
проектными нормами 0,25 мкм и более не оказывали существен-
ного влияния на работу цифровых схем. В большей степени на-
чали проявляться паразитные параметры, обусловливаемые осо-
бенностями топологической реализации схем, такие как емкости
межсоединений и индуктивные связи. Более опасными становятся
скачки напряжений. Рост быстродействия и степени интеграции
одновременно с усложнением моделей ведет к увеличению вы-
числительных затрат на моделирование и, следовательно, наряду
с поиском новых методов создания моделей требуется разработка и
новых методов моделирования.
Указанные проблемы требуют комплексного решения задач
автоматизированного логического проектирования. Данная книга
направлена на решение этих проблем.
Одним из ключевых методов, рассматриваемых в книге, явля-
ется метод анализа и распространения логических ограничений
в цифровой КМОП-схеме, основанный на методе резолюций.
Этот подход позволил сконструировать эффективные алгорит-
мы временного анализа и анализа помехоустойчивости, прибли-
жающиеся по точности к методам электрического моделирова-
ния, но значительно более быстродействующие, чем известные
алгоритмы.
Ââåäåíèå
Развитие технологии СБИС приводит к постоянному уменьшению
минимальных размеров элементов и повышению степени интегра-
ции. В этих условиях методы и алгоритмы, используемые в САПР
СБИС, оказываются недостаточно производительными для реаль-
ного проектирования. Возникает потребность в новом поколении
методов и алгоритмов, в том числе методов логического и логико-
временного анализа КМОП СБИС на стадиях проектирования
электрической схемы и верификации топологии.
Процедуры анализа и верификации проектных решений со-
ставляют основу логического проектирования современных циф-
ровых КМОП СБИС. Для выполнения верификации необходимо
располагать математическими моделями и алгоритмами логиче-
ского и логико-временного анализа. В случае схем субмикронного
и нанометрового диапазонов при анализе логики уже нельзя обой-
тись без учета ряда электрических эффектов, которые для схем с
проектными нормами 0,25 мкм и более не оказывали существен-
ного влияния на работу цифровых схем. В большей степени на-
чали проявляться паразитные параметры, обусловливаемые осо-
бенностями топологической реализации схем, такие как емкости
межсоединений и индуктивные связи. Более опасными становятся
скачки напряжений. Рост быстродействия и степени интеграции
одновременно с усложнением моделей ведет к увеличению вы-
числительных затрат на моделирование и, следовательно, наряду
с поиском новых методов создания моделей требуется разработка и
новых методов моделирования.
Указанные проблемы требуют комплексного решения задач
автоматизированного логического проектирования. Данная книга
направлена на решение этих проблем.
Одним из ключевых методов, рассматриваемых в книге, явля-
ется метод анализа и распространения логических ограничений
в цифровой КМОП-схеме, основанный на методе резолюций.
6 Ââåäåíèå
Этот подход позволил сконструировать эффективные алгорит-
мы временного анализа и анализа помехоустойчивости, прибли-
жающиеся по точности к методам электрического моделирова-
ния, но значительно более быстродействующие, чем известные
алгоритмы.
ÃËÀÂÀ 1
ÎÑÍÎÂÍÛÅ
ÏÎÍßÒÈß,
ÒÅÐÌÈÍÛ,
ÎÏÐÅÄÅËÅÍÈß
1.1. Áóëåâà àëãåáðà
Булева алгебра оперирует некоторым множеством элементов B,
включающим два различных элемента 0 и 1. В общем случае речь
идет о произвольном количестве элементов — не менее двух. Опе-
рации над элементами этого множества определяются на основе
списка аксиом.
Определение 1.1. Пусть задан упорядоченный набор
A = (B,+,⋅,¯,0,1), в котором определены множество элементов B, две
бинарных операции на B — логическое сложение < + > и логическое
умножение < · >, унарная операция на B — отрицание (или дополне-
ние) < ‾ > и два различных элемента 0 и 1 из множества B. Упорядо-
ченный набор A = (B,+,⋅,¯,0,1) называется булевой алгеброй, если для
любых a, b, с ∈ B выполняются следующие аксиомы:
коммутативные законы• : a + b = b + a и a ⋅ b = b ⋅ a;
• дистрибутивные законы: a ⋅ (b + c) = a ⋅ b + a ⋅ c и a + (b ⋅ c) = (a +
b) ⋅ (a + c);
• законы поглощения 0 и 1: a + 0 = a и a ⋅ 1= a;
• законы комплементарности: a+a= 1 и a⋅a = 0 .
8 Глава 1. Основные понятия, термины, определения
На основе аксиом и применения правила суперпозиции (под-
становки) в качестве правила вывода выводятся вычислительные
законы булевой алгебры.
Пусть задана булева алгебра A = (B,+,⋅,¯,0,1). Тогда для любых
a, b, с ∈ A выполняются следующие законы:
законы идемпотентност• и: a + a = a и a ⋅ a = a;
• свойства для 1 и 0: a + 1 = 1 и a ⋅ 0 = 0;
• законы поглощения: a ⋅ (a + b) = a и a + (a ⋅ b) = a + b) ⋅ (a + c);
• ассоциативные законы: a + (b + c) = (a + b) + c
и a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c;
• законы де Моргана (законы двойственности): a+b=a⋅b и
a⋅b =a+b;
• закон двойного отрицания: a=a.
Доказательство этих законов можно найти в [2, 3]. Примерами
булевых алгебр являются, в частности:
• подмножество всех множеств заданного множества;
• алгебра булевых функций;
• классическая булева алгебра двух элементов (алгебра логи-
ки);
• четырехзначная булева алгебра.
Пусть S — некоторое множество, состоящее из |S| элементов.
Тогда можно выбрать 2|S| различных подмножества данного множе-
ства. Множество всех 2|S| подмножеств обозначается через 2S и удо-
влетворяет всем аксиомам булевой алгебры относительно следую-
щих операций:
A ⋅ B = A ∩ B — пересечение множеств;
A + B = A ∪ B — объединение множеств;
A=S\A— дополнение до полного множества S.
То есть алгебра A = (2S, ∪, ∩, S\, ∅, S) является булевой алгеброй,
в которой нулевой элемент — пустое множество ∅, а единичный
элемент — полное множество S.
Другие варианты булевых алгебр рассматриваются ниже.
1.1. Булева алгебра 9
Определение 1.2. Пусть A = (B,+,⋅,¯,0,1) — булева алгебра и задано
n булевых переменных x1,..., xn, каждая из которых может принимать
значения из множества B. Тогда булевой формулой называется выра-
жение, получаемое на основе следующих рекурсивных правил:
1. Элемент множества B есть булева формула;
2. Переменные x1,..., xn являются булевыми формулами;
3. Если F и F — булевы формулы, тогда a + a = a, (F) + (G) и (F)
также являются булевыми формулами.
В дальнейшем для обозначения переменных могут использо-
ваться две формы записи, а именно математическая запись: x1,..., xn,
или строка символов по стандартам языка программирования, на-
пример x1, …, xn или x[0], x[1], .., x[n–1], как это принято в языке
Cи [4].
Для сокращения записи принято опускать лишние скобки,
подразумевая следующий порядок приоритетности выполнения
операций: < ‾ >, < · >, .< + >..
Следует отметить, что понятие булевых формул определено
в терминах абстрактных цепочек символов. Для того чтобы интер-
претировать булевы формулы как булевы функции, нужно симво-
лам в правиле (3) сопоставить булевы операции, а переменным со-
поставить значения булевых переменных из множества B. Поэтому
точное определение булевой функции основано на задании парал-
лельного множества правил формирования.
Определение 1.3. Пусть A = (B,+,⋅,¯,0,1) — булева алгебра и зада-
но n булевых переменных x1,..., xn, каждая из которых может прини-
мать значения из множества B. Отображение f : Bn → B называется
булевой функцией от n переменных x1,..., xn в том и только в том слу-
чае, когда эта функция может быть выражена с помощью булевой
формулы по следующим правилам:
(1) для любого элемента b ∈ B константная функция есть булева
функция от n переменных:
f(x1,..., xn) = b ∀(x1,..., xn) ∈ Bn;
10 Глава 1. Основные понятия, термины, определения
(2) для любой переменной xi ∈ {x1,..., xn} проекционная функ-
ция i-й переменной, i ∈ {1,..., n} является булевой функцией n пере-
менных:
f(x1,..., xn) = xi ∀(x1,..., xn) ∈ Bn;
(3) если f и g — булевы функции n переменных, тогда f + g,
f ⋅ g и ⎯f также являются булевыми функциями от n переменных
и определены следующим образом:
(f + g)(x1,..., xn) = f(x1,..., xn) + g(x1,..., xn) ∀(x1,..., xn) ∈ Bn;
(f ⋅ g)(x1,..., xn) = f(x1,..., xn) ⋅ g(x1,..., xn) ∀(x1,..., xn) ∈ Bn;
f x x f x x x x B n n n
( ,..., ) ( ,..., ) ( ,..., ) n 1 1 1 = ∀ ∈ .
Несмотря на идентичность определений, отношение между бу-
левыми функциями и булевыми формулами не является взаимно-
однозначным. Эквивалентность булевых формул определяется
в лексикографическом смысле. Эквивалентность же булевых функ-
ций определяется по эквивалентности отображений f : Bn → B, а это
означает, что одна и та же булева функция может быть выражена
разными формулами.
Следует отметить, что для заданной булевой алгебры
A = (B,+,⋅,¯,0,1) множество булевых функций Pn(A) само порожда-
ет новую булеву алгебру AF = (BF,+,⋅,¯,F0,F1), в которой BF = Pn(A),
а F0, F1 — константные функции:
F0 : f(x1,..., xn) = 0 ∀(x1,..., xn) ∈ Bn;
F1 : f(x1,..., xn) = 1 ∀(x1,..., xn) ∈ Bn.
1.2. Формирование графа булевых функций 11
Известно следующее [3]: если в булевой алгебре A = (B,+,⋅,¯,0,1)
множество B содержит более двух элементов, то всегда можно по-
строить функцию f : Bn → B, которая не является булевой функцией.
Однако для алгебры двух элементов любая функция f : Bn → B явля-
ется булевой функцией.
1.2. Булева формула (а значит и булева функция) может быть пред-
ставлена графически в виде дерева синтаксического разбора [5—7].
Примеры такого дерева изображены на (рис. 1.1). Листовые терми-
нальные вершины такого дерева соответствуют константам (пункт
(1) — Определение 1.3) или переменным x1,..., xn (пункт (2) — Опре-
деление 1.3), а все остальные вершины соответствуют операциям
а + а = а, (F) + (G) и (F) (пункт (3) — Определение 1.3). Корневая
вершина соответствует полной формуле. Ребра в этом дереве связы-
вают операции с операндами.
Рекурсивное определение булевых формул допускает неодно-
кратное использование одних и тех же компонент в выражениях.
Поэтому, в общем случае целесообразно представлять систему бу-
левых формул и булевых функций в виде ориентированного аци-
клического графа (DAG — Directed Acyclic Graph) [8—9], в котором
общим выражениям соответствуют общие вершины. Для установ-
ления соответствия между булевыми функциями и их графическим
представлением дадим формальное определение графа булевых
функций. Вершины будем метить строками из следующего алфа-
вита:
M V B x x x x n n ( ) = ∪{ ,..., }∪{ ,..., }∪{+,⋅, } 1 1 .
Ребра будем индексировать целыми числами M(E) = {e0, e1} для
обозначения порядка вхождения операндов в выражение.
12 Глава 1. Основные понятия, термины, определения
Определение 1.4. Пусть A = (B,+,⋅,¯,0,1) — булева алгебра и зада-
но n булевых переменных x1,..., xn, каждая из которых может при-
нимать значения из множества B. Тогда графом булевых функций
(сокращенно B-граф) будем называть ориентированный а x1 ⇐ x2
циклический граф G = (V, E), в котором каждая вершина помечена
символом из множества M V B x x x x n n ( ) { ,..., } { ,..., } { = ∪ ∪ ∪ +,⋅, } 1 1
и определяет булеву функцию fG,v согласно следующим правилам:
1. Если вершина v помечена символом b ∈ B, то она не име-
ет ни одной входящей дуги и определяет функцию fG,v(x1,...,
xn) = b.
2. Если вершина v помечена символом xi, то она не имеет
ни одной входящей дуги и определяет функцию fG,v(x1,...,
xn) = xi.
3. Еесли вершина v помечена символом xi , то она не име-
ет ни одной входящей дуги и определяет функцию
f x x x G,v n i ( ,..., ) 1 = .
4. Если вершина v помечена символом < ‾ >, то она имеет ров-
но одну входящую дугу e0 = (x, v) ∈ E и определяет функцию
f x x f G,v n G,x ( ,..., ) 1 = .
5. Если вершина v помечена символом < · >, то она имеет ровно
две входящие дуги e0 = (x, v) ∈ E, e1 = (y, v) ∈ E и определяет
функцию fG,v(x1,..., xn) = fG,x ⋅ fG,y.
– +
.
a b a b b 0
à á
a•b (a•b)+(b+0)
. +
Рис. 1.1. B-граф — дерево разбора для формул (а) a b ⋅ и (б)
(a · b) + (b + 0)
1.3. Двузначная булева алгебра (алгебра логики) 13
6. Если вершина v помечена символом < + >, то она имеет ров-
но две входящие дуги e0 = (x, v) ∈ E, e1 = (y, v) ∈ E и определя-
ет функцию fG,v(x1,..., xn) = fG,x + fG,y.
Каждой вершине v в B-графе можно поставить в соответствие
подграф, состоящий из всех ее последователей и ее самой. Такой
подграф также является B-графом и полностью определяет функ-
цию, заданную в этой вершине. В общем случае может быть не-
сколько корневых вершин, на которые не ссылается ни одна другая
вершина, а также несколько B-графов, реализующих одну и ту же
булеву формулу. Пример совместного графа для двух булевых функ-
ций изображен на (рис. 1.2).
1.3. Наиболее важной разновидностью булевой алгебры является алге-
бра двух элементов или алгебра логики.
Определение 1.5. Пусть задана булева алгебра A = ({0,1},+,⋅,¯,0,1),
в которой B={0,1}, а операции заданы следующими соотношениями:
+
. +
a b 0
–
a•b (a•b)+(b+0)
Рис. 1.2. Совместный B-граф для формул a b ⋅ и (a · b) + (b+0)
14 Глава 1. Основные понятия, термины, определения
0 1 1 0
0 0 0 0 1 1 1 0 1 1 1 1
0 0 0 0 1 0 1 0 0 1 1 1
= =
+ = + = + = + =
⋅ = ⋅ = ⋅ = ⋅ =
, ,
, , , ,
, , , .
Тогда A = ({0,1},+,⋅,¯,0,1) называется двузначной булевой алгеброй
(или алгеброй логики), в этом случае множество B={0,1} будем обо-
значать как B2.
Определение 1.6. Функция f : B2
n → B2 называется двузначной бу-
левой функцией (или логической функцией).
Множество всех двузначных булевых (логических) функций n
переменных будем обозначать через Pn. Общее количество функций
#Pn от n переменных для такой алгебры определяется формулой:
#Pn
n = 22 .
В частности, #P2 = 24 = 16, #P3 = 28 = 256, #P4 = 216 = 65536.
В табл. 1.1 приведен полный набор двузначных булевых функ-
ций двух переменных, а также принятая система обозначений
и разложение функций в соответствии с определением булевых
функций (Определение 1.3).
Каждая строка табл. 1.1 определяет функцию двух переменных
fi(x1,x2) : B2 × B2 → B2, поэтому символы столбца 2 могут быть ис-
пользованы для обозначения бинарных операций на B2. Будем обо-
значать через *w любой из символов бинарных операций табл. 1.1:
* , {, , , , , , , , , } w ∈ = ⋅ ⇒ ⇐ ⊕ + ↓ Ω Ω = ⇐ ⇒ ↑ .
Введем понятие обобщенной булевой формулы, в котором допу-
скается использование любой из перечисленных операций из мно-
жества Ω.
Пусть A = (B,+,⋅,¯,0,1) — двузначная булева алгебра и задано n
булевых переменных x1,..., xn, каждая из которых может принимать
значения из множества B. Тогда обобщенной булевой формулой бу-
1.3. Двузначная булева алгебра (алгебра логики) 15
Таблица 1.1. Система обозначений двузначных булевых функций
двух переменных
f Обо-
значе-
ние
Название Разложение f
(0,0)
f
(0,1)
f
(1,0)
f
(1,1)
f0 0 0
Нуль
0 0 0 0 0
f1 x1 ⋅ x2
x1 & x2
and
Коньюнкция
x1 ⋅ x2 0 0 0 1
f2 x x 1 2 ⇒ not-imply
Отрицание импликации
x x 1 2 ⋅ 0 0 1 0
f3 x1 x1 x1 0 0 1 1
f4 x x 1 2 ⇐ not-implied-by
Отрицание обратной
импликации
x x 1 2 ⋅ 0 1 0 0
f5 x2 x2 x2 0 1 0 1
f6 x1 ⊕ x2 еxor
Сложение по модулю 2
x x x x 1 2 1 2 ⋅ + ⋅ 0 1 1 0
f7 x1 + x2
x1 ∨ x2
or
Дизъюнкция
x1 + x2 0 1 1 1
f8 x1 ↓ x2 nor
Стрелка Пирса(*)
x x 1 2 ⋅
x x 1 2 +
1 0 0 0
f9 x1 = x2 equivalence
Эквивалентность
x x x x 1 2 1 2 ⋅ + ⋅ 1 0 0 1
f10 ⎯x2 ⎯x2 ⎯x2 1 0 1 0
f11 implied-by
Обратная импликация
x x 1 2 ⋅
x x 1 2 +
1 0 1 1
f12 ⎯x1 ⎯x1 ⎯x1 1 1 0 0
f13 x1 ⇒ x2 imply
Импликация
x x 1 2 ⋅
x x 1 2 +
1 1 0 1
f14 x1 ↑ x2 nand
Штрих Шеффера(**)
x x 1 2 ⋅
x x 1 2 +
1 1 1 0
f15 1 1
Единица
1 1 1 1 1
(*) Стрелка Пирса — двуместная логическая операция, введенная в рассмотрение
Чарльзом Пирсом (1839—1914).
(**) Штрих Шеффера — двуместная логическая операция, введенная в рассмотре-
ние Генри Шеффером (1882—1964).
16 Глава 1. Основные понятия, термины, определения
дем называть выражение, получаемое на основе следующих рекур-
сивных правил:
Элемент множеств1. а B есть обобщенная булева формула.
2. Переменные x1,..., xn являются обобщенными булевыми
формулами.
3. Если F — обобщенная булева формула, тогда (F) также яв-
ляется обобщенной булевой формулой.
4. Если F и F — обобщенные булевы формулы, тогда ∀*w ∈ Ω :
((F)*w(G)) также является обобщенной булевой формулой.
В случае двузначной булевой алгебры любая из перечислен-
ных операций может быть выражена в терминах базовых опера-
ций булевой алгебры: конъюнкции, дизъюнкции и отрицания
(табл. 1.1, столбец 4). А это означает, что любая обобщенная бу-
лева формула выражает некоторую булеву функцию f : Bn → B
(Определение 1.3).
Отметим следующее: любая функция fi(x1, x2), i = 0, ..., 15
из табл. 1.1 определяет бинарное отношение, как подмножество
упорядоченных пар значений переменных (x1, x2), для которых
fi(x1, x2) = 1:
{(x,x ): (x,x ) B B, f(x,x ) } 1 2 1 2 2 2 i 1 2 ∈ × =1 .
Заметим, что, в частности, таким образом, определяется отно-
шение эквивалентности (x1 = x2) (табл. 1.1, строка 9), поскольку оно
обладает следующими свойствами:
• рефлексивность а = а;
• симметричность: если а = b, то b = а;
• транзитивность: если. а = b и b = c, то а = c.
При этом функция (x1 = x2) принимает значение 1 тогда и только
тогда, когда аргументы равны. Это дает основание трактовать фор-
мулу f1(x1,..., xn) = f2(x1,..., xn) как логическое уравнение, т. е. использо-
вать один и тот же символ для уравнения и операции эквивалент-
ности.
1.3. Двузначная булева алгебра (алгебра логики) 17
Отметим также, что отношение импликации x1 ⇒ x2 (строка f13
табл. 1.1) соответствует определению частичного порядка, и выпол-
няются следующие законы:
• рефлексивность a ⇒ a;
• антисимметричность: если a ⇒ b и b ⇒ a, то a = b;
• транзитивность: если a ⇒ b и b ⇒ c, то a ⇒ c.
Представление обобщенных булевых формул в виде графа будем
называть функционально-логическим графом булевых функций.
Определение 1.8. Пусть A = (B,+,⋅,¯,0,1) — двузначная булева ал-
гебра и задано n булевых переменных x1,..., xn, каждая из которых
может принимать значения из множества B. Тогда функционально-
логическим графом (сокращенно F-граф) будем называть упоря-
доченный (*) ориентированный ациклический граф G = (V, E),
в котором каждая вершина помечена символом из множества
M V B x x x x n n ( ) = ∪{ ,..., }∪{ ,..., }∪ 1 1 Ω и определяет булеву функ-
цию fG,v согласно следующим правилам:
1. Если вершина v помечена символом b ∈ B, то она не име-
ет ни одной входящей дуги и определяет функцию
fG,v (x1,..., xn) = b.
2. Если вершина v помечена символом xi, то она не име-
ет ни одной входящей дуги и определяет функцию
fG,v (x1,..., xn) = xi.
3. Если вершина v помечена символом xi , то она не име-
ет ни одной входящей дуги и определяет функцию
f x x x G,v n i ( ,..., ) 1 = .
4. Если вершина v помечена символом < ‾ >, то она имеет ров-
но одну входящую дугу e0 = (x, v) ∈ E и определяет функцию
f x x f G,v n G,x ( ,..., ) 1 = .
5. Если вершина v помечена символом *w ∈ Ω, то она имеет
ровно две входящие дуги e0 = (x, v) ∈ E, e1 = (y, v) ∈ E и опре-
деляет функцию fG,v(x1,..., xn) = fG,x *w fG,y.
Замечание (*). Термин упорядоченный относится в данном случае
не к порядку вершин, а к порядку ребер и означает, что важен по-
18 Глава 1. Основные понятия, термины, определения
рядок перечисления ребер, ин-
цидентных вершине, т. е. если
изменить порядок e0, e1, то бу-
дет другой граф, и, возможно,
другая функция.
B-граф (Определение 1.4)
является частным случаем
F-графа для подмножества
из двух базовых бинарных опе-
раций * {, } w ∈ ⋅ + . Пример
F-графа, не удовлетворяюще-
го Определение 1.4, изображен
на рис. 1.3. В данном случае по-
мимо стандартных операций
используются операции сло-
жения по модулю 2 (⊕).
Разложение Шеннона
Пусть f(x1,..., xn) : B2
n → B2 — логическая функция от n переменных.
Будем обозначать через fi0, fi1 функции от (n–1) переменной, полу-
ченные f(x1,..., xn) путем подстановки соответственно xi = 0, xi = 1:
f x x x x f x x x x i i i n 0 1 1 1 1 i 1 i 1 n ( ,..., , ,..., ) ( ,..., ,0, ,..., ) − + − + = =f x x
n x
i
( ,..., ) ; 1 = 0
f x x x x f x x x x i1 1 i1 i 1 n 1 i 1 i 1 n ( ,..., , ,..., ) ( ,..., ,1, ,..., ) − + − + = =f x x
n x
i
( ,..., ) . 1 = 1
Пусть f(x1,..., xn) : B2
n → B2, fi0, fi1 — функции от (n–1) переменной,
полученные f(x1,..., xn) путем подстановки соответственно xi = 0,
xi = 1, тогда верны следующие формулы:
f x x x f x x x x x f x n i i i i n i i ( ,..., ) ( ,..., , ,..., ) ( ,... 1 0 1 1 1 1 1 = ⋅ + ⋅ − + ,x ,x ,...,x) i−1 i+1 n
— классическое разложение Шеннона,
+
+
+
.
.
x
f1 f0
y c
Рис. 1.3. F-граф для полного сумма-
тора
1.4. Бинарные диаграммы решений (BDD) 19
f x x x f x x x x x f x n i i i i n i i ( ,..., ) ( ( ,..., , ,..., )) ( ( , 1 1 1 1 1 0 1 = + ⋅ + − + ...,x ,x ,...,x)) i−1 i+1 n
— двойственное разложение Шеннона,
f x x x f x x x x x f x n i i i i n i i ( ,..., ) ( ,..., , ,..., ) ( ,... 1 0 1 1 1 1 1 = ⋅ ⊕ ⋅ − + ,x ,x ,...,x) i−1 i+1 n
— разложение Шеннона для операции сложения по модулю 2.
См. [3] — доказательство.
1.4. Áèíàðíûå äèàãðàììû ðåøåíèé (BDD)
Рекурсивное применение разложений Шеннона позволяет пред-
ставить любую двузначную булеву функцию в виде суперпозиции
функции-мультиплексора mux(x0, x1, x2) от трех аргументов, опреде-
ленную следующим образом:
mux(x ,x,x ) x x x x 0 1 2 0 1 0 2 = ⋅ + ⋅ .
Графическим представлением такого разложения являются би-
нарные диаграммы решений (BDD — Binary Decision Diagram). Ши-
рокое распространение в области автоматизации проектирования
в электронике BDD получили после появления статьи Р. Е. Брайанта
[10], в которой были описаны эффективные алгоритмы для основ-
ных действий над булевыми функциями, заданными BDD. Многие
из этих алгоритмов имеют полиномиальную сложность [11—12].
Определение 1.9. Пусть задано n булевых переменных x1,..., xn.
Бинарной диаграммой решений (сокращенно BDD — binary decision
diagram) называется ориентированный ациклический граф
G = (V,E), в котором каждая вершина помечена символом из мно-
жества M(V) = {x1,..., xn}∪{0,1} и определяет булеву функцию fG,v со-
гласно следующим правилам:
20 Глава 1. Основные понятия, термины, определения
Eсли вершин1. а v помечена символом b ∈ {0,1}, то она не име-
ет ни одной исходящей дуги и определяет функцию fG,v(x1,...,
xn) = b.
2. Eсли вершина v помечена символом xi, то она имеет ровно
две исходящие дуги e0 = (v, x) ∈ E, e1 = (v, y) ∈ E, помеченные
соответственно символами 0 и 1, и определяет функцию
f x x x f x f G,v n i G,x i G,y ( ,..., ) 1 = ⋅ + ⋅ . При этом дочерние вер-
шины для дуг e0 = (v, x), e1 = (v, y) обозначают соответственно
x = low(v) и y = high(v).
Частным случаем такой диаграммы является бинарное дерево
решений (рис. 1.4, a). Обычно используются сокращенные бинар-
ные диаграммы решений, в которых терминальных листовых вер-
шин ровно две (рис. 1.4, б).
Наибольший интерес представляет канонический вариант би-
нарной диаграммы решений, так называемая сокращенная упоря-
доченная бинарная диаграмма решений (ROBDD — reduced ordered
binary decision diagram).
Определение 1.10. Пусть задан порядок булевых переменных
x1,..., xn. Упорядоченной бинарной диаграммой решений (сокращенно
0
0
1
1
1
1
1
a)
0
0
0
0
0
0
0
1
1 1
1 1
á)
x3
x3 x3
x2
x2
x1
x1
0 1
x1•x2+x3
x1•x2+x3
Рис. 1.4. Бинарное дерево решений (а) и бинарная диаграмма ре-
шений (б) для функции x1 · x2 + x3
1.4. Бинарные диаграммы решений (BDD) 21
ОBDD — ordered binary decision diagram) называется бинарная диа-
грамма решений, в которой на всех направленных путях соблюдается
заданный порядок переменных, т. е., ∀e e= x x e∈E →i < j i j : ( ( , ), ) ,
и количество терминальных вершин — ровно две.
Известно, что сложность бинарной диаграммы решений
в значительной степени зависит от выбора порядка переменных
(рис. 1.5). Метки дуг на этом рисунке опущены, левой дуге всегда
соответствует «0», правой — всегда «1».
Определение 1.11. Упорядоченная бинарная диаграмма решений
называется сокращенной упорядоченной бинарной диаграммой реше-
ний (ROBDD — reduced ordered binary decision diagram), если в ней
нет ни одной вершины v, для которой выполняется low(v) = high(v),
и разным вершинам соответствуют неизоморфные подграфы.
Замечание. Строго говоря, требование исключить вершины, для
которых выполняется low(v) = high(v), избыточно, если под понятием
Рис. 1.5. Бинарная диаграмма решений при разных порядках пе-
ременных (левая дуга — всегда «0», правая — «1»)
0 1
a)
0 1
á)
x4
x5
x6
x3
x2
x1
x3 x3 xx 3 3
x4 x4
x4
x4
x5
x5
x6
xx 2 2
x1
x1x2 + x3x4 + x5x6
x1x4 + x2x5 + x3x6
22 Глава 1. Основные понятия, термины, определения
«граф» понимать обыкновенный граф [13—17], в котором изначаль-
но запрещены повторяющиеся дуги. Однако в САПР-приложениях
обычно под понятием «граф» подразумевается мультиграф, где по-
вторяющиеся ребра и дуги разрешены, если это не оговаривается
особо.
Пример несокращенной и сокращенной диаграмм двоичных
решений для одной и той же функции изображен на рис. 1.6 а и б,
соответственно.
Известно, что ROBDD является каноническим представлением
функции, т. е. для заданной булевой функции при заданном поряд-
ке переменных любые две сокращенные упорядоченные бинарные
диаграммы решений будут изоморфными графами.
Системы из нескольких логических функций могут быть
представлены общей сокращенной упорядоченной BDD (Shared
ROBDD) — BDD с несколькими корневыми вершинами [15].
Обобщение BDD на случай более двух различных терминаль-
ных вершин называют многотерминальной бинарной диаграммой
решений (MTBDD — multi-terminal binary decision diagram) [16].
0 1
1
1
1
0
0
0
á)
0
0
0
0
0
0
1
1
1
1
1
a)
1
x3
x3
x3
x2
x2
x2
x1 x1
Рис. 1.6. Пример несокращенной (а) и сокращенной (б) диаграмм
двоичных решений для функции (x1+x2)·x3
1.4. Бинарные диаграммы решений (BDD) 23
Классические канонические представления
ROBDD является каноническим представлением функции. Дру-
гими классическими каноническими представлениями являются
двухуровневые разложения булевой функции в форме канониче-
ской совершенной дизъюнктивной нормальной формы (СДНФ)
и канонической совершенной конъюнктивной нормальной формы
(СКНФ). Для их описания вводятся следующие определения.
Определение 1.12. Пусть f(x1,..., xn) : B2
n → B2 — двузначная буле-
ва функция от n переменных. Множество значений a(a1,..., an) ∈ B2
n
вектора переменных x = (x1,..., xn)T, при которых функция принима-
ет значение f(a1,..., an) = 1, называется множеством единиц функции f
и обозначается 1(f ). Множество значений a = (a1,..., an) ∈ B2
n вектора
переменных x = (x1,..., xn)T, при которых функция принимает зна-
чение f(a1,..., an) = 0, называется множеством нулей функции f и обо-
значается 0(f ).
Будем обозначать x x i
ai
i = при ai = 1 и x x i
ai
i = при ai = 0.
Определение 1.13. Для заданного двоичного вектора a = (a1,...,
an)T ∈ B2
n максимальным термом ma(x) называется произведение
m x x x a
a
n
( ) = ⋅...⋅ an 1
1 , а минимальным термом sa(x) называется сумма
s x x x a a
a
n
( )= +...+ an 1
1 .
На основе приведенных определений строятся два классиче-
ских канонических представления булевых функций.
Дизъюнктивная нормальная форма (ДНФ) есть любая логиче-
ская сумма из логических произведений:
f x m x a ( ) = Σ ( ).
Определение 1.14. Конъюнктивная нормальная форма (КНФ)
есть любое логическое произведение из логических сумм:
f x s x a ( ) = Π ( ).
24 Глава 1. Основные понятия, термины, определения
Определение 1.15. Совершенная дизъюнктивная нормальная
форма (СДНФ) есть сумма минимальных термов на множестве еди-
ниц функции:
f x m x a
a f
( ) ( )
( )
= Σ
∈1
.
Определение 1.16. Совершенная конъюнктивная нормальная
форма (СКНФ) есть произведение максимальных термов на мно-
жестве нулей функции:
f x s x a
a f
( ) ( )
( )
= Π
∈0
.
Всякая булева функция имеет единственную СДНФ и един-
ственную СКНФ.
Развитие технологии СБИС приводит к постоянному уменьшению
минимальных размеров элементов и повышению степени интегра-
ции. В этих условиях методы и алгоритмы, используемые в САПР
СБИС, оказываются недостаточно производительными для реаль-
ного проектирования. Возникает потребность в новом поколении
методов и алгоритмов, в том числе методов логического и логико-
временного анализа КМОП СБИС на стадиях проектирования
электрической схемы и верификации топологии.
Процедуры анализа и верификации проектных решений со-
ставляют основу логического проектирования современных циф-
ровых КМОП СБИС. Для выполнения верификации необходимо
располагать математическими моделями и алгоритмами логиче-
ского и логико-временного анализа. В случае схем субмикронного
и нанометрового диапазонов при анализе логики уже нельзя обой-
тись без учета ряда электрических эффектов, которые для схем с
проектными нормами 0,25 мкм и более не оказывали существен-
ного влияния на работу цифровых схем. В большей степени на-
чали проявляться паразитные параметры, обусловливаемые осо-
бенностями топологической реализации схем, такие как емкости
межсоединений и индуктивные связи. Более опасными становятся
скачки напряжений. Рост быстродействия и степени интеграции
одновременно с усложнением моделей ведет к увеличению вы-
числительных затрат на моделирование и, следовательно, наряду
с поиском новых методов создания моделей требуется разработка и
новых методов моделирования.
Указанные проблемы требуют комплексного решения задач
автоматизированного логического проектирования. Данная книга
направлена на решение этих проблем.
Одним из ключевых методов, рассматриваемых в книге, явля-
ется метод анализа и распространения логических ограничений
в цифровой КМОП-схеме, основанный на методе резолюций.
Этот подход позволил сконструировать эффективные алгорит-
мы временного анализа и анализа помехоустойчивости, прибли-
жающиеся по точности к методам электрического моделирова-
ния, но значительно более быстродействующие, чем известные
алгоритмы.
Ââåäåíèå
Развитие технологии СБИС приводит к постоянному уменьшению
минимальных размеров элементов и повышению степени интегра-
ции. В этих условиях методы и алгоритмы, используемые в САПР
СБИС, оказываются недостаточно производительными для реаль-
ного проектирования. Возникает потребность в новом поколении
методов и алгоритмов, в том числе методов логического и логико-
временного анализа КМОП СБИС на стадиях проектирования
электрической схемы и верификации топологии.
Процедуры анализа и верификации проектных решений со-
ставляют основу логического проектирования современных циф-
ровых КМОП СБИС. Для выполнения верификации необходимо
располагать математическими моделями и алгоритмами логиче-
ского и логико-временного анализа. В случае схем субмикронного
и нанометрового диапазонов при анализе логики уже нельзя обой-
тись без учета ряда электрических эффектов, которые для схем с
проектными нормами 0,25 мкм и более не оказывали существен-
ного влияния на работу цифровых схем. В большей степени на-
чали проявляться паразитные параметры, обусловливаемые осо-
бенностями топологической реализации схем, такие как емкости
межсоединений и индуктивные связи. Более опасными становятся
скачки напряжений. Рост быстродействия и степени интеграции
одновременно с усложнением моделей ведет к увеличению вы-
числительных затрат на моделирование и, следовательно, наряду
с поиском новых методов создания моделей требуется разработка и
новых методов моделирования.
Указанные проблемы требуют комплексного решения задач
автоматизированного логического проектирования. Данная книга
направлена на решение этих проблем.
Одним из ключевых методов, рассматриваемых в книге, явля-
ется метод анализа и распространения логических ограничений
в цифровой КМОП-схеме, основанный на методе резолюций.
6 Ââåäåíèå
Этот подход позволил сконструировать эффективные алгорит-
мы временного анализа и анализа помехоустойчивости, прибли-
жающиеся по точности к методам электрического моделирова-
ния, но значительно более быстродействующие, чем известные
алгоритмы.
ÃËÀÂÀ 1
ÎÑÍÎÂÍÛÅ
ÏÎÍßÒÈß,
ÒÅÐÌÈÍÛ,
ÎÏÐÅÄÅËÅÍÈß
1.1. Áóëåâà àëãåáðà
Булева алгебра оперирует некоторым множеством элементов B,
включающим два различных элемента 0 и 1. В общем случае речь
идет о произвольном количестве элементов — не менее двух. Опе-
рации над элементами этого множества определяются на основе
списка аксиом.
Определение 1.1. Пусть задан упорядоченный набор
A = (B,+,⋅,¯,0,1), в котором определены множество элементов B, две
бинарных операции на B — логическое сложение < + > и логическое
умножение < · >, унарная операция на B — отрицание (или дополне-
ние) < ‾ > и два различных элемента 0 и 1 из множества B. Упорядо-
ченный набор A = (B,+,⋅,¯,0,1) называется булевой алгеброй, если для
любых a, b, с ∈ B выполняются следующие аксиомы:
коммутативные законы• : a + b = b + a и a ⋅ b = b ⋅ a;
• дистрибутивные законы: a ⋅ (b + c) = a ⋅ b + a ⋅ c и a + (b ⋅ c) = (a +
b) ⋅ (a + c);
• законы поглощения 0 и 1: a + 0 = a и a ⋅ 1= a;
• законы комплементарности: a+a= 1 и a⋅a = 0 .
8 Глава 1. Основные понятия, термины, определения
На основе аксиом и применения правила суперпозиции (под-
становки) в качестве правила вывода выводятся вычислительные
законы булевой алгебры.
Пусть задана булева алгебра A = (B,+,⋅,¯,0,1). Тогда для любых
a, b, с ∈ A выполняются следующие законы:
законы идемпотентност• и: a + a = a и a ⋅ a = a;
• свойства для 1 и 0: a + 1 = 1 и a ⋅ 0 = 0;
• законы поглощения: a ⋅ (a + b) = a и a + (a ⋅ b) = a + b) ⋅ (a + c);
• ассоциативные законы: a + (b + c) = (a + b) + c
и a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c;
• законы де Моргана (законы двойственности): a+b=a⋅b и
a⋅b =a+b;
• закон двойного отрицания: a=a.
Доказательство этих законов можно найти в [2, 3]. Примерами
булевых алгебр являются, в частности:
• подмножество всех множеств заданного множества;
• алгебра булевых функций;
• классическая булева алгебра двух элементов (алгебра логи-
ки);
• четырехзначная булева алгебра.
Пусть S — некоторое множество, состоящее из |S| элементов.
Тогда можно выбрать 2|S| различных подмножества данного множе-
ства. Множество всех 2|S| подмножеств обозначается через 2S и удо-
влетворяет всем аксиомам булевой алгебры относительно следую-
щих операций:
A ⋅ B = A ∩ B — пересечение множеств;
A + B = A ∪ B — объединение множеств;
A=S\A— дополнение до полного множества S.
То есть алгебра A = (2S, ∪, ∩, S\, ∅, S) является булевой алгеброй,
в которой нулевой элемент — пустое множество ∅, а единичный
элемент — полное множество S.
Другие варианты булевых алгебр рассматриваются ниже.
1.1. Булева алгебра 9
Определение 1.2. Пусть A = (B,+,⋅,¯,0,1) — булева алгебра и задано
n булевых переменных x1,..., xn, каждая из которых может принимать
значения из множества B. Тогда булевой формулой называется выра-
жение, получаемое на основе следующих рекурсивных правил:
1. Элемент множества B есть булева формула;
2. Переменные x1,..., xn являются булевыми формулами;
3. Если F и F — булевы формулы, тогда a + a = a, (F) + (G) и (F)
также являются булевыми формулами.
В дальнейшем для обозначения переменных могут использо-
ваться две формы записи, а именно математическая запись: x1,..., xn,
или строка символов по стандартам языка программирования, на-
пример x1, …, xn или x[0], x[1], .., x[n–1], как это принято в языке
Cи [4].
Для сокращения записи принято опускать лишние скобки,
подразумевая следующий порядок приоритетности выполнения
операций: < ‾ >, < · >, .< + >..
Следует отметить, что понятие булевых формул определено
в терминах абстрактных цепочек символов. Для того чтобы интер-
претировать булевы формулы как булевы функции, нужно симво-
лам в правиле (3) сопоставить булевы операции, а переменным со-
поставить значения булевых переменных из множества B. Поэтому
точное определение булевой функции основано на задании парал-
лельного множества правил формирования.
Определение 1.3. Пусть A = (B,+,⋅,¯,0,1) — булева алгебра и зада-
но n булевых переменных x1,..., xn, каждая из которых может прини-
мать значения из множества B. Отображение f : Bn → B называется
булевой функцией от n переменных x1,..., xn в том и только в том слу-
чае, когда эта функция может быть выражена с помощью булевой
формулы по следующим правилам:
(1) для любого элемента b ∈ B константная функция есть булева
функция от n переменных:
f(x1,..., xn) = b ∀(x1,..., xn) ∈ Bn;
10 Глава 1. Основные понятия, термины, определения
(2) для любой переменной xi ∈ {x1,..., xn} проекционная функ-
ция i-й переменной, i ∈ {1,..., n} является булевой функцией n пере-
менных:
f(x1,..., xn) = xi ∀(x1,..., xn) ∈ Bn;
(3) если f и g — булевы функции n переменных, тогда f + g,
f ⋅ g и ⎯f также являются булевыми функциями от n переменных
и определены следующим образом:
(f + g)(x1,..., xn) = f(x1,..., xn) + g(x1,..., xn) ∀(x1,..., xn) ∈ Bn;
(f ⋅ g)(x1,..., xn) = f(x1,..., xn) ⋅ g(x1,..., xn) ∀(x1,..., xn) ∈ Bn;
f x x f x x x x B n n n
( ,..., ) ( ,..., ) ( ,..., ) n 1 1 1 = ∀ ∈ .
Несмотря на идентичность определений, отношение между бу-
левыми функциями и булевыми формулами не является взаимно-
однозначным. Эквивалентность булевых формул определяется
в лексикографическом смысле. Эквивалентность же булевых функ-
ций определяется по эквивалентности отображений f : Bn → B, а это
означает, что одна и та же булева функция может быть выражена
разными формулами.
Следует отметить, что для заданной булевой алгебры
A = (B,+,⋅,¯,0,1) множество булевых функций Pn(A) само порожда-
ет новую булеву алгебру AF = (BF,+,⋅,¯,F0,F1), в которой BF = Pn(A),
а F0, F1 — константные функции:
F0 : f(x1,..., xn) = 0 ∀(x1,..., xn) ∈ Bn;
F1 : f(x1,..., xn) = 1 ∀(x1,..., xn) ∈ Bn.
1.2. Формирование графа булевых функций 11
Известно следующее [3]: если в булевой алгебре A = (B,+,⋅,¯,0,1)
множество B содержит более двух элементов, то всегда можно по-
строить функцию f : Bn → B, которая не является булевой функцией.
Однако для алгебры двух элементов любая функция f : Bn → B явля-
ется булевой функцией.
1.2. Булева формула (а значит и булева функция) может быть пред-
ставлена графически в виде дерева синтаксического разбора [5—7].
Примеры такого дерева изображены на (рис. 1.1). Листовые терми-
нальные вершины такого дерева соответствуют константам (пункт
(1) — Определение 1.3) или переменным x1,..., xn (пункт (2) — Опре-
деление 1.3), а все остальные вершины соответствуют операциям
а + а = а, (F) + (G) и (F) (пункт (3) — Определение 1.3). Корневая
вершина соответствует полной формуле. Ребра в этом дереве связы-
вают операции с операндами.
Рекурсивное определение булевых формул допускает неодно-
кратное использование одних и тех же компонент в выражениях.
Поэтому, в общем случае целесообразно представлять систему бу-
левых формул и булевых функций в виде ориентированного аци-
клического графа (DAG — Directed Acyclic Graph) [8—9], в котором
общим выражениям соответствуют общие вершины. Для установ-
ления соответствия между булевыми функциями и их графическим
представлением дадим формальное определение графа булевых
функций. Вершины будем метить строками из следующего алфа-
вита:
M V B x x x x n n ( ) = ∪{ ,..., }∪{ ,..., }∪{+,⋅, } 1 1 .
Ребра будем индексировать целыми числами M(E) = {e0, e1} для
обозначения порядка вхождения операндов в выражение.
12 Глава 1. Основные понятия, термины, определения
Определение 1.4. Пусть A = (B,+,⋅,¯,0,1) — булева алгебра и зада-
но n булевых переменных x1,..., xn, каждая из которых может при-
нимать значения из множества B. Тогда графом булевых функций
(сокращенно B-граф) будем называть ориентированный а x1 ⇐ x2
циклический граф G = (V, E), в котором каждая вершина помечена
символом из множества M V B x x x x n n ( ) { ,..., } { ,..., } { = ∪ ∪ ∪ +,⋅, } 1 1
и определяет булеву функцию fG,v согласно следующим правилам:
1. Если вершина v помечена символом b ∈ B, то она не име-
ет ни одной входящей дуги и определяет функцию fG,v(x1,...,
xn) = b.
2. Если вершина v помечена символом xi, то она не имеет
ни одной входящей дуги и определяет функцию fG,v(x1,...,
xn) = xi.
3. Еесли вершина v помечена символом xi , то она не име-
ет ни одной входящей дуги и определяет функцию
f x x x G,v n i ( ,..., ) 1 = .
4. Если вершина v помечена символом < ‾ >, то она имеет ров-
но одну входящую дугу e0 = (x, v) ∈ E и определяет функцию
f x x f G,v n G,x ( ,..., ) 1 = .
5. Если вершина v помечена символом < · >, то она имеет ровно
две входящие дуги e0 = (x, v) ∈ E, e1 = (y, v) ∈ E и определяет
функцию fG,v(x1,..., xn) = fG,x ⋅ fG,y.
– +
.
a b a b b 0
à á
a•b (a•b)+(b+0)
. +
Рис. 1.1. B-граф — дерево разбора для формул (а) a b ⋅ и (б)
(a · b) + (b + 0)
1.3. Двузначная булева алгебра (алгебра логики) 13
6. Если вершина v помечена символом < + >, то она имеет ров-
но две входящие дуги e0 = (x, v) ∈ E, e1 = (y, v) ∈ E и определя-
ет функцию fG,v(x1,..., xn) = fG,x + fG,y.
Каждой вершине v в B-графе можно поставить в соответствие
подграф, состоящий из всех ее последователей и ее самой. Такой
подграф также является B-графом и полностью определяет функ-
цию, заданную в этой вершине. В общем случае может быть не-
сколько корневых вершин, на которые не ссылается ни одна другая
вершина, а также несколько B-графов, реализующих одну и ту же
булеву формулу. Пример совместного графа для двух булевых функ-
ций изображен на (рис. 1.2).
1.3. Наиболее важной разновидностью булевой алгебры является алге-
бра двух элементов или алгебра логики.
Определение 1.5. Пусть задана булева алгебра A = ({0,1},+,⋅,¯,0,1),
в которой B={0,1}, а операции заданы следующими соотношениями:
+
. +
a b 0
–
a•b (a•b)+(b+0)
Рис. 1.2. Совместный B-граф для формул a b ⋅ и (a · b) + (b+0)
14 Глава 1. Основные понятия, термины, определения
0 1 1 0
0 0 0 0 1 1 1 0 1 1 1 1
0 0 0 0 1 0 1 0 0 1 1 1
= =
+ = + = + = + =
⋅ = ⋅ = ⋅ = ⋅ =
, ,
, , , ,
, , , .
Тогда A = ({0,1},+,⋅,¯,0,1) называется двузначной булевой алгеброй
(или алгеброй логики), в этом случае множество B={0,1} будем обо-
значать как B2.
Определение 1.6. Функция f : B2
n → B2 называется двузначной бу-
левой функцией (или логической функцией).
Множество всех двузначных булевых (логических) функций n
переменных будем обозначать через Pn. Общее количество функций
#Pn от n переменных для такой алгебры определяется формулой:
#Pn
n = 22 .
В частности, #P2 = 24 = 16, #P3 = 28 = 256, #P4 = 216 = 65536.
В табл. 1.1 приведен полный набор двузначных булевых функ-
ций двух переменных, а также принятая система обозначений
и разложение функций в соответствии с определением булевых
функций (Определение 1.3).
Каждая строка табл. 1.1 определяет функцию двух переменных
fi(x1,x2) : B2 × B2 → B2, поэтому символы столбца 2 могут быть ис-
пользованы для обозначения бинарных операций на B2. Будем обо-
значать через *w любой из символов бинарных операций табл. 1.1:
* , {, , , , , , , , , } w ∈ = ⋅ ⇒ ⇐ ⊕ + ↓ Ω Ω = ⇐ ⇒ ↑ .
Введем понятие обобщенной булевой формулы, в котором допу-
скается использование любой из перечисленных операций из мно-
жества Ω.
Пусть A = (B,+,⋅,¯,0,1) — двузначная булева алгебра и задано n
булевых переменных x1,..., xn, каждая из которых может принимать
значения из множества B. Тогда обобщенной булевой формулой бу-
1.3. Двузначная булева алгебра (алгебра логики) 15
Таблица 1.1. Система обозначений двузначных булевых функций
двух переменных
f Обо-
значе-
ние
Название Разложение f
(0,0)
f
(0,1)
f
(1,0)
f
(1,1)
f0 0 0
Нуль
0 0 0 0 0
f1 x1 ⋅ x2
x1 & x2
and
Коньюнкция
x1 ⋅ x2 0 0 0 1
f2 x x 1 2 ⇒ not-imply
Отрицание импликации
x x 1 2 ⋅ 0 0 1 0
f3 x1 x1 x1 0 0 1 1
f4 x x 1 2 ⇐ not-implied-by
Отрицание обратной
импликации
x x 1 2 ⋅ 0 1 0 0
f5 x2 x2 x2 0 1 0 1
f6 x1 ⊕ x2 еxor
Сложение по модулю 2
x x x x 1 2 1 2 ⋅ + ⋅ 0 1 1 0
f7 x1 + x2
x1 ∨ x2
or
Дизъюнкция
x1 + x2 0 1 1 1
f8 x1 ↓ x2 nor
Стрелка Пирса(*)
x x 1 2 ⋅
x x 1 2 +
1 0 0 0
f9 x1 = x2 equivalence
Эквивалентность
x x x x 1 2 1 2 ⋅ + ⋅ 1 0 0 1
f10 ⎯x2 ⎯x2 ⎯x2 1 0 1 0
f11 implied-by
Обратная импликация
x x 1 2 ⋅
x x 1 2 +
1 0 1 1
f12 ⎯x1 ⎯x1 ⎯x1 1 1 0 0
f13 x1 ⇒ x2 imply
Импликация
x x 1 2 ⋅
x x 1 2 +
1 1 0 1
f14 x1 ↑ x2 nand
Штрих Шеффера(**)
x x 1 2 ⋅
x x 1 2 +
1 1 1 0
f15 1 1
Единица
1 1 1 1 1
(*) Стрелка Пирса — двуместная логическая операция, введенная в рассмотрение
Чарльзом Пирсом (1839—1914).
(**) Штрих Шеффера — двуместная логическая операция, введенная в рассмотре-
ние Генри Шеффером (1882—1964).
16 Глава 1. Основные понятия, термины, определения
дем называть выражение, получаемое на основе следующих рекур-
сивных правил:
Элемент множеств1. а B есть обобщенная булева формула.
2. Переменные x1,..., xn являются обобщенными булевыми
формулами.
3. Если F — обобщенная булева формула, тогда (F) также яв-
ляется обобщенной булевой формулой.
4. Если F и F — обобщенные булевы формулы, тогда ∀*w ∈ Ω :
((F)*w(G)) также является обобщенной булевой формулой.
В случае двузначной булевой алгебры любая из перечислен-
ных операций может быть выражена в терминах базовых опера-
ций булевой алгебры: конъюнкции, дизъюнкции и отрицания
(табл. 1.1, столбец 4). А это означает, что любая обобщенная бу-
лева формула выражает некоторую булеву функцию f : Bn → B
(Определение 1.3).
Отметим следующее: любая функция fi(x1, x2), i = 0, ..., 15
из табл. 1.1 определяет бинарное отношение, как подмножество
упорядоченных пар значений переменных (x1, x2), для которых
fi(x1, x2) = 1:
{(x,x ): (x,x ) B B, f(x,x ) } 1 2 1 2 2 2 i 1 2 ∈ × =1 .
Заметим, что, в частности, таким образом, определяется отно-
шение эквивалентности (x1 = x2) (табл. 1.1, строка 9), поскольку оно
обладает следующими свойствами:
• рефлексивность а = а;
• симметричность: если а = b, то b = а;
• транзитивность: если. а = b и b = c, то а = c.
При этом функция (x1 = x2) принимает значение 1 тогда и только
тогда, когда аргументы равны. Это дает основание трактовать фор-
мулу f1(x1,..., xn) = f2(x1,..., xn) как логическое уравнение, т. е. использо-
вать один и тот же символ для уравнения и операции эквивалент-
ности.
1.3. Двузначная булева алгебра (алгебра логики) 17
Отметим также, что отношение импликации x1 ⇒ x2 (строка f13
табл. 1.1) соответствует определению частичного порядка, и выпол-
няются следующие законы:
• рефлексивность a ⇒ a;
• антисимметричность: если a ⇒ b и b ⇒ a, то a = b;
• транзитивность: если a ⇒ b и b ⇒ c, то a ⇒ c.
Представление обобщенных булевых формул в виде графа будем
называть функционально-логическим графом булевых функций.
Определение 1.8. Пусть A = (B,+,⋅,¯,0,1) — двузначная булева ал-
гебра и задано n булевых переменных x1,..., xn, каждая из которых
может принимать значения из множества B. Тогда функционально-
логическим графом (сокращенно F-граф) будем называть упоря-
доченный (*) ориентированный ациклический граф G = (V, E),
в котором каждая вершина помечена символом из множества
M V B x x x x n n ( ) = ∪{ ,..., }∪{ ,..., }∪ 1 1 Ω и определяет булеву функ-
цию fG,v согласно следующим правилам:
1. Если вершина v помечена символом b ∈ B, то она не име-
ет ни одной входящей дуги и определяет функцию
fG,v (x1,..., xn) = b.
2. Если вершина v помечена символом xi, то она не име-
ет ни одной входящей дуги и определяет функцию
fG,v (x1,..., xn) = xi.
3. Если вершина v помечена символом xi , то она не име-
ет ни одной входящей дуги и определяет функцию
f x x x G,v n i ( ,..., ) 1 = .
4. Если вершина v помечена символом < ‾ >, то она имеет ров-
но одну входящую дугу e0 = (x, v) ∈ E и определяет функцию
f x x f G,v n G,x ( ,..., ) 1 = .
5. Если вершина v помечена символом *w ∈ Ω, то она имеет
ровно две входящие дуги e0 = (x, v) ∈ E, e1 = (y, v) ∈ E и опре-
деляет функцию fG,v(x1,..., xn) = fG,x *w fG,y.
Замечание (*). Термин упорядоченный относится в данном случае
не к порядку вершин, а к порядку ребер и означает, что важен по-
18 Глава 1. Основные понятия, термины, определения
рядок перечисления ребер, ин-
цидентных вершине, т. е. если
изменить порядок e0, e1, то бу-
дет другой граф, и, возможно,
другая функция.
B-граф (Определение 1.4)
является частным случаем
F-графа для подмножества
из двух базовых бинарных опе-
раций * {, } w ∈ ⋅ + . Пример
F-графа, не удовлетворяюще-
го Определение 1.4, изображен
на рис. 1.3. В данном случае по-
мимо стандартных операций
используются операции сло-
жения по модулю 2 (⊕).
Разложение Шеннона
Пусть f(x1,..., xn) : B2
n → B2 — логическая функция от n переменных.
Будем обозначать через fi0, fi1 функции от (n–1) переменной, полу-
ченные f(x1,..., xn) путем подстановки соответственно xi = 0, xi = 1:
f x x x x f x x x x i i i n 0 1 1 1 1 i 1 i 1 n ( ,..., , ,..., ) ( ,..., ,0, ,..., ) − + − + = =f x x
n x
i
( ,..., ) ; 1 = 0
f x x x x f x x x x i1 1 i1 i 1 n 1 i 1 i 1 n ( ,..., , ,..., ) ( ,..., ,1, ,..., ) − + − + = =f x x
n x
i
( ,..., ) . 1 = 1
Пусть f(x1,..., xn) : B2
n → B2, fi0, fi1 — функции от (n–1) переменной,
полученные f(x1,..., xn) путем подстановки соответственно xi = 0,
xi = 1, тогда верны следующие формулы:
f x x x f x x x x x f x n i i i i n i i ( ,..., ) ( ,..., , ,..., ) ( ,... 1 0 1 1 1 1 1 = ⋅ + ⋅ − + ,x ,x ,...,x) i−1 i+1 n
— классическое разложение Шеннона,
+
+
+
.
.
x
f1 f0
y c
Рис. 1.3. F-граф для полного сумма-
тора
1.4. Бинарные диаграммы решений (BDD) 19
f x x x f x x x x x f x n i i i i n i i ( ,..., ) ( ( ,..., , ,..., )) ( ( , 1 1 1 1 1 0 1 = + ⋅ + − + ...,x ,x ,...,x)) i−1 i+1 n
— двойственное разложение Шеннона,
f x x x f x x x x x f x n i i i i n i i ( ,..., ) ( ,..., , ,..., ) ( ,... 1 0 1 1 1 1 1 = ⋅ ⊕ ⋅ − + ,x ,x ,...,x) i−1 i+1 n
— разложение Шеннона для операции сложения по модулю 2.
См. [3] — доказательство.
1.4. Áèíàðíûå äèàãðàììû ðåøåíèé (BDD)
Рекурсивное применение разложений Шеннона позволяет пред-
ставить любую двузначную булеву функцию в виде суперпозиции
функции-мультиплексора mux(x0, x1, x2) от трех аргументов, опреде-
ленную следующим образом:
mux(x ,x,x ) x x x x 0 1 2 0 1 0 2 = ⋅ + ⋅ .
Графическим представлением такого разложения являются би-
нарные диаграммы решений (BDD — Binary Decision Diagram). Ши-
рокое распространение в области автоматизации проектирования
в электронике BDD получили после появления статьи Р. Е. Брайанта
[10], в которой были описаны эффективные алгоритмы для основ-
ных действий над булевыми функциями, заданными BDD. Многие
из этих алгоритмов имеют полиномиальную сложность [11—12].
Определение 1.9. Пусть задано n булевых переменных x1,..., xn.
Бинарной диаграммой решений (сокращенно BDD — binary decision
diagram) называется ориентированный ациклический граф
G = (V,E), в котором каждая вершина помечена символом из мно-
жества M(V) = {x1,..., xn}∪{0,1} и определяет булеву функцию fG,v со-
гласно следующим правилам:
20 Глава 1. Основные понятия, термины, определения
Eсли вершин1. а v помечена символом b ∈ {0,1}, то она не име-
ет ни одной исходящей дуги и определяет функцию fG,v(x1,...,
xn) = b.
2. Eсли вершина v помечена символом xi, то она имеет ровно
две исходящие дуги e0 = (v, x) ∈ E, e1 = (v, y) ∈ E, помеченные
соответственно символами 0 и 1, и определяет функцию
f x x x f x f G,v n i G,x i G,y ( ,..., ) 1 = ⋅ + ⋅ . При этом дочерние вер-
шины для дуг e0 = (v, x), e1 = (v, y) обозначают соответственно
x = low(v) и y = high(v).
Частным случаем такой диаграммы является бинарное дерево
решений (рис. 1.4, a). Обычно используются сокращенные бинар-
ные диаграммы решений, в которых терминальных листовых вер-
шин ровно две (рис. 1.4, б).
Наибольший интерес представляет канонический вариант би-
нарной диаграммы решений, так называемая сокращенная упоря-
доченная бинарная диаграмма решений (ROBDD — reduced ordered
binary decision diagram).
Определение 1.10. Пусть задан порядок булевых переменных
x1,..., xn. Упорядоченной бинарной диаграммой решений (сокращенно
0
0
1
1
1
1
1
a)
0
0
0
0
0
0
0
1
1 1
1 1
á)
x3
x3 x3
x2
x2
x1
x1
0 1
x1•x2+x3
x1•x2+x3
Рис. 1.4. Бинарное дерево решений (а) и бинарная диаграмма ре-
шений (б) для функции x1 · x2 + x3
1.4. Бинарные диаграммы решений (BDD) 21
ОBDD — ordered binary decision diagram) называется бинарная диа-
грамма решений, в которой на всех направленных путях соблюдается
заданный порядок переменных, т. е., ∀e e= x x e∈E →i < j i j : ( ( , ), ) ,
и количество терминальных вершин — ровно две.
Известно, что сложность бинарной диаграммы решений
в значительной степени зависит от выбора порядка переменных
(рис. 1.5). Метки дуг на этом рисунке опущены, левой дуге всегда
соответствует «0», правой — всегда «1».
Определение 1.11. Упорядоченная бинарная диаграмма решений
называется сокращенной упорядоченной бинарной диаграммой реше-
ний (ROBDD — reduced ordered binary decision diagram), если в ней
нет ни одной вершины v, для которой выполняется low(v) = high(v),
и разным вершинам соответствуют неизоморфные подграфы.
Замечание. Строго говоря, требование исключить вершины, для
которых выполняется low(v) = high(v), избыточно, если под понятием
Рис. 1.5. Бинарная диаграмма решений при разных порядках пе-
ременных (левая дуга — всегда «0», правая — «1»)
0 1
a)
0 1
á)
x4
x5
x6
x3
x2
x1
x3 x3 xx 3 3
x4 x4
x4
x4
x5
x5
x6
xx 2 2
x1
x1x2 + x3x4 + x5x6
x1x4 + x2x5 + x3x6
22 Глава 1. Основные понятия, термины, определения
«граф» понимать обыкновенный граф [13—17], в котором изначаль-
но запрещены повторяющиеся дуги. Однако в САПР-приложениях
обычно под понятием «граф» подразумевается мультиграф, где по-
вторяющиеся ребра и дуги разрешены, если это не оговаривается
особо.
Пример несокращенной и сокращенной диаграмм двоичных
решений для одной и той же функции изображен на рис. 1.6 а и б,
соответственно.
Известно, что ROBDD является каноническим представлением
функции, т. е. для заданной булевой функции при заданном поряд-
ке переменных любые две сокращенные упорядоченные бинарные
диаграммы решений будут изоморфными графами.
Системы из нескольких логических функций могут быть
представлены общей сокращенной упорядоченной BDD (Shared
ROBDD) — BDD с несколькими корневыми вершинами [15].
Обобщение BDD на случай более двух различных терминаль-
ных вершин называют многотерминальной бинарной диаграммой
решений (MTBDD — multi-terminal binary decision diagram) [16].
0 1
1
1
1
0
0
0
á)
0
0
0
0
0
0
1
1
1
1
1
a)
1
x3
x3
x3
x2
x2
x2
x1 x1
Рис. 1.6. Пример несокращенной (а) и сокращенной (б) диаграмм
двоичных решений для функции (x1+x2)·x3
1.4. Бинарные диаграммы решений (BDD) 23
Классические канонические представления
ROBDD является каноническим представлением функции. Дру-
гими классическими каноническими представлениями являются
двухуровневые разложения булевой функции в форме канониче-
ской совершенной дизъюнктивной нормальной формы (СДНФ)
и канонической совершенной конъюнктивной нормальной формы
(СКНФ). Для их описания вводятся следующие определения.
Определение 1.12. Пусть f(x1,..., xn) : B2
n → B2 — двузначная буле-
ва функция от n переменных. Множество значений a(a1,..., an) ∈ B2
n
вектора переменных x = (x1,..., xn)T, при которых функция принима-
ет значение f(a1,..., an) = 1, называется множеством единиц функции f
и обозначается 1(f ). Множество значений a = (a1,..., an) ∈ B2
n вектора
переменных x = (x1,..., xn)T, при которых функция принимает зна-
чение f(a1,..., an) = 0, называется множеством нулей функции f и обо-
значается 0(f ).
Будем обозначать x x i
ai
i = при ai = 1 и x x i
ai
i = при ai = 0.
Определение 1.13. Для заданного двоичного вектора a = (a1,...,
an)T ∈ B2
n максимальным термом ma(x) называется произведение
m x x x a
a
n
( ) = ⋅...⋅ an 1
1 , а минимальным термом sa(x) называется сумма
s x x x a a
a
n
( )= +...+ an 1
1 .
На основе приведенных определений строятся два классиче-
ских канонических представления булевых функций.
Дизъюнктивная нормальная форма (ДНФ) есть любая логиче-
ская сумма из логических произведений:
f x m x a ( ) = Σ ( ).
Определение 1.14. Конъюнктивная нормальная форма (КНФ)
есть любое логическое произведение из логических сумм:
f x s x a ( ) = Π ( ).
24 Глава 1. Основные понятия, термины, определения
Определение 1.15. Совершенная дизъюнктивная нормальная
форма (СДНФ) есть сумма минимальных термов на множестве еди-
ниц функции:
f x m x a
a f
( ) ( )
( )
= Σ
∈1
.
Определение 1.16. Совершенная конъюнктивная нормальная
форма (СКНФ) есть произведение максимальных термов на мно-
жестве нулей функции:
f x s x a
a f
( ) ( )
( )
= Π
∈0
.
Всякая булева функция имеет единственную СДНФ и един-
ственную СКНФ.