Бибило П.Н. Бинарные диаграммы решений в логическом проектировании

---

Введение				6
Глава 1. Построение и минимизация бинарных диаграмм решений				9
1.1. Формы представления булевых функций				9
1.2. Проверка равенства и реализации булевых функций				26
1.3. Построение бинарных диаграмм решений для полностью определенных булевых функций				33
1.4. Свойства BDD				52
1.5. Классификация BDD				70
1.6. Краткий обзор возникновения и применения BDD				94
1.7. Построение и минимизация бинарных диаграмм решений для систем полностью определенных булевых функций				99
1.8. Построение бинарных диаграмм решений для систем частичных булевых функций				116
1.9. Операции над матричными формами и BDD				151
1.10. Доопределение частичных булевых функций, заданных бинарными диаграммами решений				180
1.11. Выбор перестановки переменных				202
1.12. Разбиение системы булевых функций на подсистемы «связанных» функций				206
Глава 2. Декомпозиция полностью определенных булевых функций, заданных бинарными диаграммами решений				228
2.1. Декомпозиция булевых функций				228
2.2. Краткий обзор методов декомпозиции булевых функций				232
2.3. Раздельная декомпозиция системы полностью определенных булевых функций				235
2.4. Совместная декомпозиция системы полностью определенных булевых функций				242
2.5. Применение логических уравнений для построения промежуточных функций				256
2.6. Выбор разбиения переменных				261
2.7. Технологическое отображение BDD в базисе программируемых элементов FPGA				264
Глава 3. Декомпозиция частичных булевых функций, заданных бинарными диаграммами решений				275
3.1. Раздельная декомпозиция системы частичных булевых функций				275
3.2. Совместная декомпозиция системы частичных булевых функций				288
3.3. Применение логических уравнений для совместной декомпозиции частичных функций				304
Глава 4. Бинарные диаграммы решений с инверсными кофакторами				310
4.1. Минимизация BDDI представлений систем полностью определенных булевых функций				310
4.2. Минимизация BDDI представлений систем частичных булевых функций				318
Глава 5. Алгебраические разложения кофакторов				342
5.1. Минимизация BDD представлений систем полностью определенных булевых функций с использованием алгебраических разложений кофакторов				342
5.2. Минимизация BDD представлений систем частичных булевых функций с использованием алгебраических разложений кофакторов				376
5.3. Простая декомпозиция и алгебраические разложения кофакторов				413
Глава 6. Практические применения и экспериментальные исследования				429
6.1. Представления систем булевых функций в памяти компьютеров и в системах автоматизированного проектирования				429
6.2. Реализация бинарных диаграмм решений логическими схемами				445
6.3. Сравнение эффективности разложений Шеннона и Давио при синтезе логических схем				453
6.4. Экспериментальное исследование алгоритмов минимизации бинарных диаграмм решений				462
6.5. Экспериментальное сравнение методов и программ декомпозиции систем булевых функций				468
6.6. Экспериментальное исследование эффективности логической оптимизации при синтезе комбинационных схем из библиотечных элементов				487
6.7. Экспериментальные исследования схемных реализаций частичных булевых функций				515
6.8. Применение бинарных диаграмм решений при синтезе структур FPGA				520
6.9. Минимизация бинарных диаграмм решений при синтезе схем с пониженным энергопотреблением				524
6.10. Использование моделей частичных булевых функций при синтезе логических схем по VHDL описаниям				530
Заключение				545
Список сокращений				546
Литература				548

---

Введение Проектирование цифровых систем на элементной базе СБИС (сверхбольших интегральных схем) и систем на кристаллах включает много этапов, целью которых является преобразование исходного описания поведения цифровой системы в топологические описания слоев кристалла проектируемой интегральной схемы. Центральным является этап логического проектирования, на котором по функционально-структурным описаниям проектируемых цифровых систем, полученным после этапа высокоуровневого проектирования, синтезируются логические схемы в технологических базисах проектирования СБИС. Логическое проектирование включает технологически независимую оптимизацию и технологическое отображение – выделение и замену фрагментов оптимизированных логических описаний элементами технологических библиотек проектирования СБИС.

Бинарные диаграммы решений (англ. Binary Decision Diagrams, BDD) – это компактная и эффективная форма задания булевых (логических) функций и систем булевых функций в виде ориентированных бесконтурных графов, применяемая на этапе технологически независимой оптимизации функциональных описаний логических схем, реализуемых как в составе цифровых заказных СБИС, так и в составе ПЛИС (программируемых логических интегральных схем). В русскоязычной литературе BDD называют также диаграммами двоичных решений, диаграммами двоичного выбора, двоичными решающими диаграммами и т. д. Представления булевых функций в виде BDD соответствуют многоуровневым представлениям на базе разложения Шеннона и во многих случаях являются гораздо более компактными, чем представления тех же функций в матричных формах, под которыми понимаются матричные задания дизъюнктивных нормальных форм и таблиц истинности. Кроме того, компактность BDD и использование специальных структур данных при программной реализации алгоритмов обработки BDD позволили получить эффективные программы выполнения операций над BDD. Аппарат BDD широко используется при решении различных задач, возникающих при проектировании цифровых систем: верификации алгоритмических описаний цифровых систем, синтезе логических схем, поиске тестов для логических схем и др.

В книге рассматриваются классические бинарные диаграммы решений – сокращенные упорядоченные BDD (англ. Reduced Ordered BDD, ROBDD). Среди русскоязычной научной литературы и книг, посвящен ных различным применениям BDD, следует выделить четвертый том серии «Искусство программирования» Д. Кнута [32], в котором описываются структуры данных для представления ROBDD в компьютерах и подробно излагаются разнообразные вычислительные алгоритмы обработки ROBDD для полностью определенных булевых функций и систем.

Книга посвящена использованию аппарата BDD при решении задач синтеза логических схем в технологических базисах заказных СБИС и ПЛИС типа FPGA (Field-Programmable Gate Array), при этом рассматриваются системы полностью и не полностью определенных булевых функций. Синтез логических схем, наряду с верификацией, является одним из важнейших применений BDD, где аппарат BDD применяется на этапе технологически независимой оптимизации, после которого осуществляется покрытие оптимизированных BDD представлений функциональными описаниями базовых логических элементов. Для систем полностью определенных булевых функций вычислительной основой методов минимизации BDD являются операции сравнения булевых функций на равенство. Для систем не полностью определенных (частичных) булевых функций при минимизации BDD осуществляются проверки выполнения отношений реализации между частичными подфункциями, получающимися в процессе построения BDD, и выполняется процесс доопределения частичных функций до полностью определенных. Все это усложняет задачу нахождения минимизированных BDD, реализующих исходные системы частичных функций, требует решения новых оптимизационных логико-комбинаторных задач и разработки новой вычислительной базы. Проводится сравнение BDD с матричными представлениями булевых функций и показывается, что BDD соответствуют ортогонализованным матричным представлениям булевых функций, для которых эффективно решаются многие задачи логического проектирования. Постоянное внимание уделяется переходу от графовых к различным аналитическим (формульным) представлениям оптимизированных систем булевых функций. Основные проблемы, которые рассматриваются в книге:

- представления систем булевых функций в виде графов BDD, матричных и скобочных алгебраических форм;

- минимизация сложности BDD представлений (и их модификаций) для систем полностью и не полностью определенных булевых функций;

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

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

- использование языка VHDL, являющегося входным языком САПР

(систем автоматизированного проектирования), для представления различных форм булевых функций, в том числе и BDD;

- экспериментальные исследования и анализ эффективности предложенных (и ориентированных на решение задач практической размерности) методов, алгоритмов и программ технологически независимой оптимизации при последующем синтезе схем заказных СБИС и синтезе структур FPGA в промышленных САПР цифровых схем. Автор выражает благодарность П. В. Леончику за программную реализацию некоторых алгоритмов, а также О. В. Клачко за помощь в подготовке иллюстраций. Номера рисунков, таблиц, листингов, формул «привязаны» к номеру соответствующего раздела книги.

---