- Timestamp:
- Jul 1, 2010, 10:27:13 AM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/SCA2010/BDD/report.tex
r137 r138 108 108 \node (4-4) [state, below left=of 3-3]{4}; 109 109 \node (4-5) [state, below right=of 3-3]{4}; 110 \node (FT) [leaf, below right=of 4-1]{};110 \node (FT) [leaf, below=of 4-1]{}; 111 111 \node (FF) [leaf, below right=of 4-2]{}; 112 112 \node (TT) [leaf, below=of 4-4]{}; … … 156 156 157 157 \end{tikzpicture} 158 \caption{Voorbeeld: twee \emph{BDD}s die samengesmolten worden} 159 \end{figure} 158 \caption{Voorbeeld: twee \emph{BDD}s die samengesmolten worden door gebruik te 159 maken van formule~\ref{melt-eq}. Let wel op dat dit voorbeeld geen ontbrekende 160 laag van nodes heeft, waardoor nodes van alle niveaus beschikbaar zijn. Op het 161 moment dat de $\diamond$ ingevult gaat worden is het ook zaak om de bladeren 162 (zie vergelijking~\ref{bladeren}) te vereenvoudigen} \end{figure} 160 163 161 164 \section{Introductie BDD} … … 179 182 gedefineerd als $\alpha$ ad $\alpha'$ niet beiden bladeren (\emph{sinks}) zijn: 180 183 \begin{equation} 184 \label{melt-eq} 181 185 \alpha \diamond \alpha' = \left\{ 182 186 \begin{array}{l l} … … 237 241 de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009} 238 242 239 Neem aan dat $f(x_{1}, ...,x_{n})$ en $g(x_{1},...,x_{n})$ de respectieve240 \emph{profielen} (\emph{profiles})~\cite[pg 101]{DK2009} $(b_{0}, ...,b_{n})$ en241 $(b'_{0}, ...,b_{n})$ hebben. En de respectieve \emph{quasi-profielen}242 (\emph{quasi-profiles})~\cite[pg 103]{DK2009} $(q_{0}, ...,q_{n})$ en243 $(q'_{0}, ...,q'_{n})$. Om te laten zijn dat de gesmolten $f \diamond g$ het243 Neem aan dat $f(x_{1},dots,x_{n})$ en $g(x_{1},dots,x_{n})$ de respectieve 244 \emph{profielen} (\emph{profiles})~\cite[pg 101]{DK2009} $(b_{0},dots,b_{n})$ en 245 $(b'_{0},dots,b_{n})$ hebben. En de respectieve \emph{quasi-profielen} 246 (\emph{quasi-profiles})~\cite[pg 103]{DK2009} $(q_{0},dots,q_{n})$ en 247 $(q'_{0},dots,q'_{n})$. Om te laten zijn dat de gesmolten $f \diamond g$ het 244 248 aantal knopen van $B(f \diamond g) \leq 245 \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$. 246 247 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. 248 249 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. 249 \sum^{n}_{j=0}(q_{j}b'_{j}+b_{j}q'_{j}-b_{j}b'_{j})$ bevat moet gekeken worden 250 aan het aantal \emph{beads}~\cite[pg 72]{DK2009} dat mogelijkerwijs gemaakt 251 kunnen worden van de functies $f$ en $g$. 252 253 Elke bead van de orde $n - j$ van het geoordende paar $(f,g)$ zal binnen de 254 standaard combinatie vallen de $b_{j}b_{j}'$ geordende beats van $(f,g)$. 255 vallen of is er eentje uit een meer speciaal gegenereerde reeks van een 256 (bead,geen-bead) of (geen-bead, bead) $b_{j}(q_{j}' - b_{j}') + (q_{j} - 257 b{j})b_{j}'$. Zie hierbij dat van een functie het $B(quasi-profiel) \geq 258 B(profiel)$. En dat alle in het profiel altijd in het quasi-profiel zit. Er dus 259 de geen-bead kan beschrijven als de rest van de quasi-profiel minus profiel. 260 261 Dit bij elkaar optellen levert op $b_{j}b_{j}' + b_{j}(q_{j}' - b_{j}') + 262 (q_{j} - b{j})b_{j}'$. Vereenvoudigen en de sommering is oefening voor de 263 lezer. 250 264 251 265 \subsection{Som groei in synthese van \emph{BDD}} … … 254 268 de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009} 255 269 256 Laat $f(x_{1}, ...,x_{n}) = M_{m}(x_{1} \oplus x_{2},x_{3} \oplus257 x_{4}, ...,x_{2m-1} \oplus x_{2m};x_{2m+1},...,x_{n})$ en $g(x_{1},...,x_{n}) =258 M_{m}(x_{2} \oplus x_{3}, ...,x_{2m-2} \oplus x_{2m-1},x_{2m};\overline259 x_{2m+1}, ...,\overline x_{n})$ waar $n = 2m + 2^{m}$.270 Laat $f(x_{1},dots,x_{n}) = M_{m}(x_{1} \oplus x_{2},x_{3} \oplus 271 x_{4},dots,x_{2m-1} \oplus x_{2m};x_{2m+1},dots,x_{n})$ en $g(x_{1},dots,x_{n}) = 272 M_{m}(x_{2} \oplus x_{3},dots,x_{2m-2} \oplus x_{2m-1},x_{2m};\overline 273 x_{2m+1},dots,\overline x_{n})$ waar $n = 2m + 2^{m}$. 260 274 261 275 Dan is $B(f) = 2^{m+2}-1 \approx 4n$, $B(g) = 2^{m+1}-2^{m} \approx 3n$ en $B(g 262 \hat f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 'magische' reeksen te 263 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. 276 \land f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 'magische' reeksen te 277 komen is het belangrijk eerst naar de profielen te kijken van $f$ en $g$ om 278 daarna met sommering van deze tot de antwoorden te komen. Als eerste moet 279 opgemerkt worden dan zoals $f$ als $g$ $2^m$-weg 280 multiplexers~\cite[7.1.2-(31)]{DK2009-0} zijn voor welke de profielen zijn 281 $(1,2,2,\dots,2^{m-1},2^{m-1},2^m,1,1,\dots,1.2)$ respectievelijk 282 $(0,1,2,2,\dots,2^{m-1},2^{m-1},1,1,dots,1,2$. Dit optellen en afschatten wordt 283 (zie ook~\cite[pg 82]{DK2009}) $B(f) = 2^{m+2} - 1 \approx 4n$ en $B(g) = 284 2^{m+1} - 1 \approx 3n$ \\ 285 \\ 286 $B(f \land g)$ wordt aanzienlijk moeilijker. Zie dat er unieke oplossing 287 bestaat -de oplossing kan aan een uniek getal gekoppeld worden- door $x_1 \dots 288 x_{2m}$ als je $((x_1 \oplus x_2)(x_3 \oplus x_4) \dots (x_{2m-1} \oplus 289 x_{2m}))_{2} = p,((x_2 \oplus x_3) \dots (x_{2m-2} \oplus x_{2m-1})x_{2m})_{2} 290 = q$. waar $0 \leq p, q \le 2^m$ en $p=q$ dan en slechts als $x_1 = x_3 = \dots 291 = 2_{2m-1} = 0$. Dit zorgt dat het eerste deel -het stuk voor de punt 292 comma- van het profiel van $f \land g$ geschreven kan worden als $(1, 2, 4,\dots, 293 2^{2m-2}, 2^{2m-1} - 2^{m-1}$. 294 Het tweede deel is aanzienlijk moeilijker, welke bestaat uit de subfuncties 295 $x_{2m+j} \land \overline x_{2m+k}$ of $\overline x_{2m+j} \land x_{2m+k}$ voor 296 $1 \leq j \le k \leq 2^m$ tesamen met de orginelen $x_{2m+j}$ en $\overline 297 x_{2m+j}$ voor $2 \leq j \leq 2^m$. Welke het profiel oplevert van $(2^{m+1}-2, 298 2^{m+1}-2, 2^{m+1}-4, 2^{m+1}-6, \dots, 4, 2, 2)$. 299 Beiden profielen bij elkaar levert op $B(f \land g) = 2^{2m+1} + 2^{m-1} -1 \approx 2n^2$ 264 300 265 301 … … 269 305 \begin{thebibliography}{} 270 306 \bibitem[DK2009]{DK2009} D.E. Knuth. Fascicle 1. \texttt{Bitwise Tricks \& 307 Techniques; Binary Decision Diagrams}, volume 4 of \texttt{The Art of Computer 308 Programming}. Pearson Education, first edition, March 2009. 309 \bibitem[DK2009-Fas0]{DK2009-0} D.E. Knuth. Fascicle 0. \texttt{Bitwise Tricks \& 271 310 Techniques; Binary Decision Diagrams}, volume 4 of \texttt{The Art of Computer 272 311 Programming}. Pearson Education, first edition, March 2009.
Note:
See TracChangeset
for help on using the changeset viewer.