source: liacs/SCA2010/BDD/report.tex@ 128

%
% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage{graphicx}
\usepackage{url}
\usepackage{multicol}
\usepackage{fancybox}
\usepackage{amssymb,amsmath}

\author{Rick van der Zwet, Universiteit Leiden}
\title{BDD synthese}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}}
\date{\today}

\begin{document}

\maketitle

\section{Inleiding}
Synthese van een Binary Decision Diagram \emph{BDD} is het belangrijke
\emph{BDD} algoritme~\cite[pp 86]{DK2009}. Welke in essentie een \emph{BDD}
functie,$f$, pakt en deze combineert met een andere \emph{BDD} functie,$g$,
zodanig dat er een nieuwe \emph{BDD} ontstaat voor de nieuwe functie.
Bijvoorbeeld $f \wedge g$ of $f \oplus g$.
De reden dat dit zo belangrijk is komt met het feit dat het combineren van
\emph{BDD}s aan de basis staat aan het uitdrukken van complexe systemen dmv van
gecombineerde simpele functies. In sectie~\ref{werking} zal deze techniek
uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}) welke in
sectie~\ref{voorbeeld} dit toegepast zal worden in een concreet voorbeeld.

\section{Samenvoegen van \emph{BDD}}
\label{werking}
De term voor het samenvoegen \emph{BDD} structuren zullen we smelten
(\emph{melding}) noemen. Er werkt volgens de volgende principies.  Men neme
$\alpha = (v,l,h)"$ en $\alpha' = (v',l',h')$. De $\alpha \diamond \alpha'$, de
"\emph{emulsie}" (\emph{meld}) van $\alpha$ en $\alpha'$, is dan als volgt
gedefineerd als $\alpha$ ad $\alpha'$ niet beiden bladeren (\emph{sinks}) zijn:
\begin{equation}
\alpha \diamond \alpha' = \left\{
\begin{array}{l l}
(v, l \diamond \l'), h \diamond h'), & \mathrm{if~} v = v'; \\
(v, l \diamond \alpha'), h \diamond \alpha'), & \mathrm{if~} v < v'; \\
(v, \alpha \diamond l'), \alpha \diamond h'), & \mathrm{if~} v > v'. \\
\end{array} \right.
\end{equation}

De oplettende lezer (voor de rest, voorbeeld figuur~\ref{voorbeeldSamenvoegen}) zal
zien dat je door het samenvoegen van de bladeren er in plaats van de twee bladeren
$\top$ en $\bot$, er nu vier bladeren mogelijk zijn:
\begin{equation}
\label{bladeren}
\begin{array}{l l l l}
\bot \diamond \bot, & \bot \diamond \top, & \top \diamond \bot, & \top \diamond \top\\
\end{array}
\end{equation}
Om er weer een 'valide' \emph{BDD} van te maken zullen deze bladeren vervangen
worden door het uitgerekende blad. Als bijvoorbeeld de $\diamond$ operatie een
$EN$ operatie was, wordt de bladrij in~\ref{bladeren} vervangen door de rij
$\bot, \bot, \bot, \top$. Nu is het zaak de \emph{BDD} te vereenvoudigen, om zo
duplicaat bladeren te snoeien (\emph{pruning}).

De kracht van deze aanpak zit hem in de zogenoemde generieke $\diamond$
operatie. Het maakt niet uit welke booleaanse operatie er gebruikt wordt aan
het eind van de rit. De gegeneerde gesmolten \emph{BDD} is geldig voor allen.

Kijkend naar de limieten kan hetzelfde altijd bereikt worden door in het
slechte geval de \emph{BDD}s achter elkaar te plakken welke dan in dit geval
$B(f)B(g)$ knopen oplevert. Voorbeeld~\ref{voorbeeldPlakken} is hier een geval
van. In het meer algemene geval $B(f) + B(g)$
XXX: TODO 

\section{Voorbeelden}
\label{voorbeeld}
\label{voorbeeldSamenvoegen}
XXX: TODO
\label{voorbeeldPlakken}

\begin{thebibliography}{}
\bibitem[DK2009]{DK2009} D.E. Knuth. Fascicle 1. \texttt{Bitwise Tricks \&
Techniques; Binary Decision Diagrams}, volume 4 of \texttt{The Art of Computer
Programming}. Pearson Education, first edition, March 2009.
\end{thebibliography}
\end{document}