Changeset 166 for liacs/SCA2010/BDD

Timestamp:

Jul 27, 2010, 12:11:28 PM (14 years ago)

Author:

Rick van der Zwet

Message:

More fixes to go

File:

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

liacs/SCA2010/BDD/report.tex

@@ -241 +241 @@
 \section{Voorbeelden}
 \label{voorbeeld}
-\subsection{Product groei in synthese van \emph{BDD}}
+\subsection{Product-groei in synthese van \emph{BDD}}
 \label{voorbeeldSamenvoegen}
 Het volgende voorbeeld is een uitwerking van opgave 60~\cite[p.~130]{DK2009}
@@ -247 +247 @@
 
 Neem aan dat $f(x_{1},\dots,x_{n})$ en $g(x_{1},\dots,x_{n})$ de respectieve
-\emph{profielen} (\emph{profiles})~\cite[p.~101]{DK2009} $(b_{0},\dots,b_{n})$ en
+\emph{profielen} (\emph{profiles})~\cite[p.~101]{DK2009}
+$(b_{0},\dots,b_{n})$\footnote{Waar er $b_{k}$ knopen zijn die splitsen
+op variable $f(x_{k+1})$ en $b_{n}$ het aantal bladeren is.} en
 $(b'_{0},\dots,b_{n})$ hebben, en de respectieve \emph{quasi-profielen}
-(\emph{quasi-profiles})~\cite[p.~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 $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
-naar het aantal \emph{beads}~\cite[p.~72]{DK2009} dat mogelijkerwijs gemaakt
-kan worden van de functies $f$ en $g$.  
+(\emph{quasi-profiles})~\cite[p.~103]{DK2009}
+$(q_{0},\dots,q_{n})$\footnote{Waar $q_{k-1}$ het aantal \circle{k} knopen in
+de \emph{QDD} is.} en $(q'_{0},\dots,q'_{n})$.  
+
+Om te laten zijn dat de gesmolten $f \diamond g$ het aantal knopen $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 naar het aantal \emph{beads}~\cite[p.~72]{DK2009} dat
+mogelijkerwijs gemaakt kan worden van de functies $f$ en $g$.  
 
 Hierbij geldt dan voor een willikeurige functie $n$ met als profiel
@@ -272 +276 @@
 lezer.
 
-\subsection{Som groei in synthese van \emph{BDD}}
+\subsection{Som-groei in synthese van \emph{BDD}}
 \label{voorbeeldPlakken}
-Het volgende voorbeeld is een uitwerking van opgave 63~\cite[pg. 131]{DK2009}
-de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}
-
-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}$. 
+Het volgende voorbeeld is een uitwerking van opgave 63~\cite[p.~131]{DK2009}
+de offi\"{e}le uitwerking is te vinden op \cite[p.~195]{DK2009}.
+
+\begin{equation}
+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}
+\caption{\oplus is de binary operator \emph{XOR}}
+\end{equation}
 
 Dan is $B(f) = 2^{m+2}-1 \approx 4n$, $B(g) = 2^{m+1}-2^{m} \approx 3n$ en $B(g
-\land f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 'magische' reeksen te
+\land f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 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
+opgemerkt worden dat zowel $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$ \\
+(zie ook~\cite[p.~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
+De bereking $B(f \land g)$ wordt aanzienlijk moeilijker. We constateren eerst
+dat er een unieke oplossing bestaat ---de oplossing kan aan een uniek getal
+gekoppeld worden---
+in de vorm van $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
-komma- 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 sub-functies
+= 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
+komma--- 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, het bestaat uit de sub-functies
 $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$ tezamen met de originelen $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$
+x_{2m+j}$ voor $2 \leq j \leq 2^m$. Dat levert het profiel $(2^{m+1}-2,
+2^{m+1}-2, 2^{m+1}-4, 2^{m+1}-6, \dots, 4, 2, 2)$ op.
+Beide profielen bij elkaar optellen levert op $B(f \land g) = 2^{2m+1} +
+2^{m-1} -1 \approx 2n^2$.