Применение диаграмм двоичного выбора при синтезе логических схем
В монографии рассматривается применение аппарата диаграмм двоичного выбора (Binary Decision Diagrams, BDD) для минимизации многоуровневых представлений булевых функций и систем; предлагаются методы декомпозиции систем булевых функций, заданных в виде BDD; приводятся результаты экспериментальных исследований применения технологически независимой минимизации и декомпозиции BDD при синтезе логических схем в различных технологических базисах.
Адресуется научным сотрудникам, разработчикам систем автоматизированного проектирования, аспирантам и студентам соответствующих специальностей.
Содержание
Содержание книги "Применение диаграмм двоичного выбора при синтезе логических схем "
Отрывок из книги
42 1210ac=ϕ=, 1211a=ϕ=; 1310ac=ϕ=, 1311ac=ϕ=; 1410ac=ϕ=, 1411ac=ϕ=. Далее следует провести разложение ко�ффициентов 1c, 1c и функции 1s по переменной 2b. Однако у нас нет представления ко�ффициента 1c в явном виде. Конечно, в данном иллюстративном примере получит� представление инверсии 1c функции 1c, зависящей от двух переменных, не вызывает трудно-сти. Однако в практических ситуациях выполнение операции инверсирования может быт� трудоемким, а полученное представление – громоздким. Будем продолжат� строит� BDD для двух оставшихся функций 1c, 1s. Ко�ффициенты разложения функций 1c, 1s по переменной 2b имеют следующий вид: 2100bc==; 2111bcb==; 2110bsb==; 2111bsb==. Разложение полученных ко�ффициентов 1b, 1b по переменной 1b тривиал�-но, полученная BDD изображена на рис. 1.15.Далее пришло время воспол�зоват�ся одним из замечател�ных свойств BDD, а именно получит� BDD-представление инверсной функции 1c по BDD-пред-ставлению исходной функции 1c. Получение BDD для инверсии 1c показано на рис. 1.16, а BDD для системы функций изображена на рис. 1.17, а.Далее требуется выполнит� операцию сокращения графа, так как BDD (см. рис. 1.17, а) содержит одинаковые подграфы. В рассматриваемом примере на первом шаге процедуры сокращения будут найдены два одинаковых под-графа, реализующих один и тот же ко�ффициент 1b. Затем выяснится, что на более высоких уровнях одинаковых подграфов нет, и BDD примет вид, как на рис. 1.17, б. Резул�тирующей BDD (см. рис. 1.17, б) соответствует новое мно-гоуровневое представление системы функций: 23422caa=ϕ ∨ ϕ; 21222saa=ϕ ∨ ϕ; 12112sb bb b=∨; 1ϕ = 11a c; 2ϕ = 11a c; 3ϕ = 51 11a ca∨ ϕ; 4ϕ = 511 1aa cϕ ∨; 5ϕ = 212bb b∨; 1c = 2 1b b, построенное по исходному также многоуровневому представлению. Для од-нородности записи ко�ффициент разложения 1c переименован: 1c = 5ϕ.Алгоритм построения BDD для формул�ного задания булевых функций можно найти в работе [22, с. 325].Легко видет�, что если строит� BDD по мно...
Бибило П. Н. другие книги автора
Внимание!
При обнаружении неточностей или ошибок в описании книги "Применение диаграмм двоичного выбора при синтезе логических схем (автор Петр Бибило)", просим Вас отправить сообщение на почту help@directmedia.ru. Благодарим!
и мы свяжемся с вами в течение 15 минут
за оставленную заявку