Changeset 138 for liacs/SCA2010/BDD

Timestamp:

Jul 1, 2010, 10:27:13 AM (14 years ago)

Author:

Rick van der Zwet

Message:

Raw version completed

File:

• liacs/SCA2010/BDD/report.tex (modified) (6 diffs)

liacs/SCA2010/BDD/report.tex

@@ -108 +108 @@
 \node (4-4) [state, below left=of 3-3]{4};
 \node (4-5) [state, below right=of 3-3]{4};
-\node (FT) [leaf, below right=of 4-1]{};
+\node (FT) [leaf, below=of 4-1]{};
 \node (FF) [leaf, below right=of 4-2]{};
 \node (TT) [leaf, below=of 4-4]{};
@@ -156 +156 @@
 
 \end{tikzpicture}
-\caption{Voorbeeld: twee \emph{BDD}s die samengesmolten worden}
-\end{figure}
+\caption{Voorbeeld: twee \emph{BDD}s die samengesmolten worden door gebruik te
+maken van formule~\ref{melt-eq}. Let wel op dat dit voorbeeld geen ontbrekende
+laag van nodes heeft, waardoor nodes van alle niveaus beschikbaar zijn. Op het
+moment dat de $\diamond$ ingevult gaat worden is het ook zaak om de bladeren
+(zie vergelijking~\ref{bladeren}) te vereenvoudigen} \end{figure}
 
 \section{Introductie BDD}
@@ -179 +182 @@
 gedefineerd als $\alpha$ ad $\alpha'$ niet beiden bladeren (\emph{sinks}) zijn:
 \begin{equation}
+\label{melt-eq}
 \alpha \diamond \alpha' = \left\{
 \begin{array}{l l}
@@ -237 +241 @@
 de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}
 
-Neem aan dat $f(x_{1},...,x_{n})$ en $g(x_{1},...,x_{n})$ de respectieve
-\emph{profielen} (\emph{profiles})~\cite[pg 101]{DK2009} $(b_{0},...,b_{n})$ en
-$(b'_{0},...,b_{n})$ hebben. En de respectieve \emph{quasi-profielen}
-(\emph{quasi-profiles})~\cite[pg 103]{DK2009} $(q_{0},...,q_{n})$ en
-$(q'_{0},...,q'_{n})$.  Om te laten zijn dat de gesmolten $f \diamond g$ het
+Neem aan dat $f(x_{1},dots,x_{n})$ en $g(x_{1},dots,x_{n})$ de respectieve
+\emph{profielen} (\emph{profiles})~\cite[pg 101]{DK2009} $(b_{0},dots,b_{n})$ en
+$(b'_{0},dots,b_{n})$ hebben. En de respectieve \emph{quasi-profielen}
+(\emph{quasi-profiles})~\cite[pg 103]{DK2009} $(q_{0},dots,q_{n})$ en
+$(q'_{0},dots,q'_{n})$.  Om te laten zijn dat de gesmolten $f \diamond g$ het
 aantal knopen van $B(f \diamond g) \leq
-\sum^{n}_{j=0}(q_{j}b'_{j}+b_{j}q'_{j}-b_{j}b'_{j})$ bevat moet gekeken worden aan het aantal \emph{beads}~\cite[pg 72]{DK2009} dat mogelijkerwijs gemaakt kunnen worden van de functies $f$ en $g$.  
-
-Elke bead van de orde $n - j$ van het geoordende paar $(f,g)$ zal binnen de standaard combinatie vallen de $b_{j}b_{j}'$ geordende beats van $(f,g)$. vallen of is er eentje uit een meer speciaal gegenereerde reeks van een (bead,geen-bead) of (geen-bead, bead) $b_{j}(q_{j}' - b_{j}') + (q_{j} - b{j})b_{j}'$. Zie hierbij dat van een functie het $B(quasi-profiel) \geq B(profiel)$. En dat alle in het profiel altijd in het quasi-profiel zit. Er dus de geen-bead kan beschrijven als de rest van de quasi-profiel minus profiel.
-
-Dit bij elkaar optellen levert op $b_{j}b_{j}' + b_{j}(q_{j}' - b_{j}') + (q_{j} - b{j})b_{j}'$. Vereenvoudigen en de sommering is oefening voor de lezer.
+\sum^{n}_{j=0}(q_{j}b'_{j}+b_{j}q'_{j}-b_{j}b'_{j})$ bevat moet gekeken worden
+aan het aantal \emph{beads}~\cite[pg 72]{DK2009} dat mogelijkerwijs gemaakt
+kunnen worden van de functies $f$ en $g$.  
+
+Elke bead van de orde $n - j$ van het geoordende paar $(f,g)$ zal binnen de
+standaard combinatie vallen de $b_{j}b_{j}'$ geordende beats van $(f,g)$.
+vallen of is er eentje uit een meer speciaal gegenereerde reeks van een
+(bead,geen-bead) of (geen-bead, bead) $b_{j}(q_{j}' - b_{j}') + (q_{j} -
+b{j})b_{j}'$. Zie hierbij dat van een functie het $B(quasi-profiel) \geq
+B(profiel)$. En dat alle in het profiel altijd in het quasi-profiel zit. Er dus
+de geen-bead kan beschrijven als de rest van de quasi-profiel minus profiel.
+
+Dit bij elkaar optellen levert op $b_{j}b_{j}' + b_{j}(q_{j}' - b_{j}') +
+(q_{j} - b{j})b_{j}'$. Vereenvoudigen en de sommering is oefening voor de
+lezer.
 
 \subsection{Som groei in synthese van \emph{BDD}}
@@ -254 +268 @@
 de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}
 
-Laat $f(x_{1},...,x_{n}) = M_{m}(x_{1} \oplus x_{2},x_{3} \oplus
-x_{4},...,x_{2m-1} \oplus x_{2m};x_{2m+1},...,x_{n})$ en $g(x_{1},...,x_{n}) =
-M_{m}(x_{2} \oplus x_{3},...,x_{2m-2} \oplus x_{2m-1},x_{2m};\overline
-x_{2m+1},...,\overline x_{n})$ waar $n = 2m + 2^{m}$. 
+Laat $f(x_{1},dots,x_{n}) = M_{m}(x_{1} \oplus x_{2},x_{3} \oplus
+x_{4},dots,x_{2m-1} \oplus x_{2m};x_{2m+1},dots,x_{n})$ en $g(x_{1},dots,x_{n}) =
+M_{m}(x_{2} \oplus x_{3},dots,x_{2m-2} \oplus x_{2m-1},x_{2m};\overline
+x_{2m+1},dots,\overline x_{n})$ waar $n = 2m + 2^{m}$. 
 
 Dan is $B(f) = 2^{m+2}-1 \approx 4n$, $B(g) = 2^{m+1}-2^{m} \approx 3n$ en $B(g
-\hat f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 'magische' reeksen te
-komen is het belangrijk eerst naar de profielen te kijken van $f$ en $g$ om daarna met sommering van deze tot de antwoorden te komen.
+\land f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 'magische' reeksen te
+komen is het belangrijk eerst naar de profielen te kijken van $f$ en $g$ om
+daarna met sommering van deze tot de antwoorden te komen. Als eerste moet
+opgemerkt worden dan zoals $f$ als $g$ $2^m$-weg
+multiplexers~\cite[7.1.2-(31)]{DK2009-0} zijn voor welke de profielen zijn
+$(1,2,2,\dots,2^{m-1},2^{m-1},2^m,1,1,\dots,1.2)$ respectievelijk
+$(0,1,2,2,\dots,2^{m-1},2^{m-1},1,1,dots,1,2$. Dit optellen en afschatten wordt
+(zie ook~\cite[pg 82]{DK2009}) $B(f) = 2^{m+2} - 1 \approx 4n$ en $B(g) =
+2^{m+1} - 1 \approx 3n$ \\
+\\
+$B(f \land g)$ wordt aanzienlijk moeilijker. Zie dat er unieke oplossing
+bestaat -de oplossing kan aan een uniek getal gekoppeld worden- door $x_1 \dots
+x_{2m}$ als je $((x_1 \oplus x_2)(x_3 \oplus x_4) \dots (x_{2m-1} \oplus
+x_{2m}))_{2} = p,((x_2 \oplus x_3) \dots (x_{2m-2} \oplus x_{2m-1})x_{2m})_{2}
+= q$. waar $0 \leq p, q \le 2^m$ en $p=q$ dan en slechts als $x_1 = x_3 = \dots
+= 2_{2m-1} = 0$.  Dit zorgt dat  het eerste deel -het stuk voor de punt
+comma- van het profiel van $f \land g$ geschreven kan worden als $(1, 2, 4,\dots,
+2^{2m-2}, 2^{2m-1} - 2^{m-1}$.
+Het tweede deel is aanzienlijk moeilijker, welke bestaat uit de subfuncties
+$x_{2m+j} \land \overline x_{2m+k}$ of $\overline x_{2m+j} \land x_{2m+k}$ voor
+$1 \leq j \le k \leq 2^m$ tesamen met de orginelen $x_{2m+j}$ en $\overline
+x_{2m+j}$ voor $2 \leq j \leq 2^m$. Welke het profiel oplevert van $(2^{m+1}-2,
+2^{m+1}-2, 2^{m+1}-4, 2^{m+1}-6, \dots, 4, 2, 2)$.
+Beiden profielen bij elkaar levert op $B(f \land g) = 2^{2m+1} + 2^{m-1} -1 \approx 2n^2$
 
 
@@ -269 +305 @@
 \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.
+\bibitem[DK2009-Fas0]{DK2009-0} D.E. Knuth. Fascicle 0. \texttt{Bitwise Tricks \&
 Techniques; Binary Decision Diagrams}, volume 4 of \texttt{The Art of Computer
 Programming}. Pearson Education, first edition, March 2009.