Ignore:
Timestamp:
Jun 20, 2010, 7:53:35 PM (14 years ago)
Author:
Rick van der Zwet
Message:

Work in process we are getting somewhere...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • liacs/SCA2010/BDD/report.tex

    r127 r128  
    2525
    2626\section{Inleiding}
    27 Samenvoegen van een Binary Decision Diagram \emph{BDD} is het belangrijke
     27Synthese van een Binary Decision Diagram \emph{BDD} is het belangrijke
    2828\emph{BDD} algoritme~\cite[pp 86]{DK2009}. Welke in essentie een \emph{BDD}
    2929functie,$f$, pakt en deze combineert met een andere \emph{BDD} functie,$g$,
     
    3333\emph{BDD}s aan de basis staat aan het uitdrukken van complexe systemen dmv van
    3434gecombineerde simpele functies. In sectie~\ref{werking} zal deze techniek
    35 uitgelegd worden, welke in sectie~\ref{voorbeeld} dit toegepast zal worden in een
    36 concreet voorbeeld.
     35uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}) welke in
     36sectie~\ref{voorbeeld} dit toegepast zal worden in een concreet voorbeeld.
    3737
    38 \section{Samenvoegen}
     38\section{Samenvoegen van \emph{BDD}}
    3939\label{werking}
    4040De term voor het samenvoegen \emph{BDD} structuren zullen we smelten
     
    5151\end{array} \right.
    5252\end{equation}
    53  
    5453
    55 \section{Voorbeeld}
     54De oplettende lezer (voor de rest, voorbeeld figuur~\ref{voorbeeldSamenvoegen}) zal
     55zien dat je door het samenvoegen van de bladeren er in plaats van de twee bladeren
     56$\top$ en $\bot$, er nu vier bladeren mogelijk zijn:
     57\begin{equation}
     58\label{bladeren}
     59\begin{array}{l l l l}
     60\bot \diamond \bot, & \bot \diamond \top, & \top \diamond \bot, & \top \diamond \top\\
     61\end{array}
     62\end{equation}
     63Om er weer een 'valide' \emph{BDD} van te maken zullen deze bladeren vervangen
     64worden door het uitgerekende blad. Als bijvoorbeeld de $\diamond$ operatie een
     65$EN$ operatie was, wordt de bladrij in~\ref{bladeren} vervangen door de rij
     66$\bot, \bot, \bot, \top$. Nu is het zaak de \emph{BDD} te vereenvoudigen, om zo
     67duplicaat bladeren te snoeien (\emph{pruning}).
     68
     69De kracht van deze aanpak zit hem in de zogenoemde generieke $\diamond$
     70operatie. Het maakt niet uit welke booleaanse operatie er gebruikt wordt aan
     71het eind van de rit. De gegeneerde gesmolten \emph{BDD} is geldig voor allen.
     72
     73Kijkend naar de limieten kan hetzelfde altijd bereikt worden door in het
     74slechte geval de \emph{BDD}s achter elkaar te plakken welke dan in dit geval
     75$B(f)B(g)$ knopen oplevert. Voorbeeld~\ref{voorbeeldPlakken} is hier een geval
     76van. In het meer algemene geval $B(f) + B(g)$
     77XXX: TODO
     78
     79\section{Voorbeelden}
     80\label{voorbeeld}
     81\label{voorbeeldSamenvoegen}
    5682XXX: TODO
    57 \label{voorbeeld}
     83\label{voorbeeldPlakken}
    5884
    5985\begin{thebibliography}{}
Note: See TracChangeset for help on using the changeset viewer.