\chapter{Binární rozhodovací diagramy}%
\label{kap_bdd}%
Binární rozhodovací diagramy (anglicky Binary decision diagrams - BDD) jsou
jedním ze způsobů reprezentace logické funkce. Jsou základním stavebním kamenem
z nich odvozených struktur jako OBDD, ROBDD a pochopitelně i MBD. V této
kapitole bude důkladně popsána struktura BDD i její vyspělejší formy OBDD a ROBDD.\\

\noindent Teoretické zázemí, které vedlo k současné definici BDD, se začalo
vyvíjet už na přelomu 50. a 60. let minulého století. Velký pokrok v této
oblasti nastal na konci 70. let, kdy se poprvé objevil název BDD v souvislosti
s vyjádřením logických funkcí. Za otce praktického využití BDD je považován R.
E. Bryant, který v polovině 80. let definoval BDD \cite{Bry86} tak, jak se
používají prakticky dodnes.

\section{Binární rozhodovací diagramy}%
BDD je kořenový orientovaný acyklický graf. Jeho uzly se dělí do tří kategorií:

\begin{itemize}%
    \item \textbf{Kořen}: Je pouze jeden - nevedou do něho žádné hrany.
    \item \textbf{Neterminální uzly}: Mají předky i potomky - hrany
    vedou z nich i do nich. Také se jim říká \emph{rozhodovací} nebo vnitřní
    uzly. V dalším textu bude pod pojem \emph{neterminální uzel} spadat i kořen.
    \item \textbf{Terminální uzly}: Hrany vedou pouze do nich.
\end{itemize}%

\noindent BDD je speciálním případem rozhodovacích diagramů, ve kterém má každý
vnitřní uzel a kořen vždy dva potomky. Příklad jednoduchého BDD je znázorněn na
obrázku \ref{bdd_example}.\\
\indent Každý neterminální uzel představuje jednu vstupní logickou proměnnou a
vedou z něj dvě hrany označované jako \emph{high} a \emph{low}. Hrana
\emph{high} odpovídá tomu, když hodnota proměnné uzlu je $1$, a hrana
\emph{low}, když proměnná je nastavena na $0$. Terminální uzly nabývají pouze
dvou hodnot - $0$ a $1$.\\

\bfig%
    \includegraphics[height=7.6cm]{img/bdd-example.png}
    \caption[Binární rozhodovací diagram funkce]{\textbf{Binární rozhodovací diagram
    funkce f.}
    $f(x_0,x_1,x_2)=\bar{x_0}x_1x_2+\bar{x_0}x_1\bar{x_2}+x_0\bar{x_1}\bar{x_2}$.
    Tečkované čáry představují hrany \emph{low}, plné čáry jsou hrany \emph{high}.}
    \label{bdd_example}
\efig%

\noindent S BDD se pracuje tak, že se prochází od kořene k terminálním
symbolům, a podle toho, jakou má hodnotu terminální uzel, ve kterém takový
průchod skončí, se určí výstupní hodnota funkce.\\
\indent Pokud bychom chtěli z BDD na obrázku \ref{bdd_example} získat hodnotu
funkce pro vstupní proměnné $x_0=0, x_1=0, x_2=1$, pak bychom postupovali
takto:
\begin{enumerate}%
    \item Začali bychom od kořene. Tomu patří proměnná $x_0$,
    která je rovná $0$. Proto bychom se vydali po hraně \emph{low}
    (představované tečkovanou čarou). \item V dalším uzlu s proměnnou $x_1$ (první zleva) se
    vydáme opět po hraně \emph{low}, jelikož vstupní hodnota $x_1$ je také $0$.
    \item V uzlu s proměnnou $x_2$ (opět první zleva) se vydáme po hraně
    \emph{high}, protože vstupní hodnota $x_2$ je $1$.
    \item Cesta končí v terminálním uzlu s hodnotou $0$ (druhý zleva),
    což je výstupní hodnota pro zadané vstupní hodnoty.%
\end{enumerate}

\subsection{Konstrukce BDD}%
BDD se vytváří rekurzivní aplikací Shannonova expanzního teorému. V každém uzlu
se logická funkce rozloží podle proměnné, které uzel patří. Hrana \emph{low}
uzlu se nastaví na sčítanec, který se vytvoří nahrazením proměnné hodnotou $0$,
a hrana \emph{high} povede do sčítance, kde byla proměnná nahrazena hodnotou
$1$.

\section{OBDD - uspořádané BDD}%
Velmi záhy se v praxi ukázalo, že velikost BDD závisí na pořadí, v jakém se
proměnné pří vytváření BDD zpracovávají. Pořadí proměnných se tedy stalo jedním
z parametrů\/vlastností BDD. BDD, u nějž se vychází z nějakého pořadí, se říká
\emph{Ordered Binary Decision Diagram}\footnote{Uspořádaný binární rozhodovací
diagram.} - OBDD.\\
\indent Jsou-li proměnné $x_i$ a $x_{i+1}$ v uspořádání $x_i < x_{i+1}$, musí
být v OBDD uzel patřící $x_i$ \emph{vždy} rodičem uzlu patřícímu $x_{i+1}$ a
nikdy naopak. Tato vlastnost je důležitým důsledkem uspořádání OBDD.
Problematice řazení proměnných je věnována celá kapitola \ref{kap_razeni}.

\section{ROBDD - redukované uspořádané BDD}
Na obrázku \ref{bdd_example} je možné si všimnout, že některé uzly jsou
zbytečné. Logická funkce by se nezměnila, pokud by byly tyto uzly z BDD
odstraněny. Například jde o první terminální uzel zleva s hodnotou $1$ nebo
první neterminální uzel zleva patřící proměnné $x_2$. Tyto zbytečné
(redundantní) uzly je možné skutečně odstranit. Tomu se říká \emph{redukce}.
OBDD, v němž nejsou žádné redundantní uzly, se říká Reduced Ordered Binary
Decision
Diagram\footnote{redukovaný uspořádaný binární rozhodovací diagram} - ROBDD.\\
Problém nadbytečných uzlů a jejich redukce byl důkladně popsán v \cite{Bry86}.
Podle této práce lze redundantní uzly rozdělit do těchto kategorií:
\begin{itemize}%
    \item Terminální uzly se stejnou hodnotou.%
    \item Neterminální uzel, jehož \emph{high} a \emph{low} hrany směřují
        do stejného uzlu (symbolicky pro uzel $u$: $high(u)=low(u)$).%
    \item Dva či více podgrafů BDD jsou stejné. Pro dva stejné podgrafy
    s kořeny \emph{u} a \emph{v} v BDD platí, že musí patřit stejné proměnné
    ($var(u)=var(v)$) a jejich \emph{high} a \emph{low} hrany musí směřovat do
    stejných uzlů ($high(u)=high(v)$ a $low(u)=low(v)$).
\end{itemize}%
\noindent Bryant rovněž stanovil postup, kterým se redundantní uzly odstraní.
Postupuje se v těchto krocích:
\begin{enumerate}%
\item \textbf{Odstraní se všechny zbytečné terminální uzly}: Na konci zbudou jen
dva terminální uzly s hodnotami $0$ a $1$. Hrany vedoucí do ostatních
terminálních uzlů se do nich přesměrují - všechny, které vedly do $0$~($1$),
nyní povedou do jediného uzlu s hodnotou $0$~($1$).%
\item \textbf{Odstranění stejných podgrafů}: Najdou-li se dva uzly $u$ a $v$, pro něž
zároveň platí: $var(u)=var(v)$, $high(u)=high(v)$ a $low(u)=low(v)$, pak se
jeden z těchto uzlů odstraní, a všichni jeho rodiče se přesměrují do
druhého\footnote{Najednou se odstraňuje jen \textbf{jeden} uzel, nikoliv celý
podgraf. Jsou-li dva grafy stejné, pak každý uzel v jednom grafu má svůj
odpovídající uzel v druhém grafu. Všechny tyto uzly budou tedy nalezeny a
odstraněny \emph{po jednom}.}.%
\item \textbf{Odstranění všech uzlů se stejnými potomky}: Uzel $u$,
pro něhož platí $high(u)=low(u)$, se úplně odstraní a všichni jeho rodiče se
přesměrují do $high(u)$. \item Kroky 2. a 3. se opakují do té doby, dokud je v
BDD nějaký redundantní uzel. Odstraňování jednotlivých zbytečných
neterminálních uzlů může vést ke vzniku nových zbytečných uzlů.%
\end{enumerate}
\noindent Jednotlivé kroky redukce jsou zobrazeny na obrázku \ref{bdd_red}.
Výchozím stavem je BDD z obrázku~\ref{bdd_example}.

\bfig%
\includegraphics[height=8cm]{img/bdd-red-1.png}\hskip 50pt
\includegraphics[height=8cm]{img/bdd-red-2.png} \vskip 30pt
\includegraphics[height=8cm]{img/bdd-red-3.png}%
\caption[Redukce BDD]{\textbf{Redukce BDD.}~Výchozím stavem je BDD z obrázku
\ref{bdd_example}. Obrázek \emph{a)} ukazuje stav BDD po odstranění zbytečných
terminálních uzlů. Obrázek \emph{b)} uvádí stav po odstranění stejných uzlů (2.
a 3. uzel proměnné $x_2$). Obrázek \emph{b)} předvádí konečný stav po
odstranění uzlů, jejichž obě hrany vedou do jednoho uzlu. }%
\label{bdd_red}
\efig

%\begin{multicols}{}{
%\includegraphics[height=6cm]{img/bdd-red-3.png}
%\includegraphics[height=6cm]{img/bdd-red-3.png}
%}
%\end{multicols}

\subsection{Vlastnosti ROBDD}%
Výhody ROBDD jsou celkem zřejmé. ROBDD má méně uzlů, což nejen snižuje paměťové
nároky na reprezentaci takové struktury\footnote{V případě obrázku
\ref{bdd_red} je ROBDD o 10 uzlů menší než jeho neredukovaná verze.}, ale díky
vypadnutí některých uzlů je i cesta od kořene k~terminálnímu symbolu kratší.\\
\indent Přes to všechno je nejdůležitější vlastností ROBDD jeho kanonicita. Dva
ROBDD vytvořené z jedné logické funkce musí být izomorfní~\cite{Bry86}.
Kanonicita ROBDD přináší řadu zajímavých aplikací ROBDD. Například je možné
snadno se složitostí $O(1)$ provádět testy na tautologii či splnitelnost
logických funkcí.

\section{Operace s ROBDD}%
Samotné ROBDD jsou v podstatě uzavřeným světem. Aby s nimi bylo možné lépe
pracovat, bylo nutné definovat základní operace tak, aby bylo možné ROBDD
spojovat, rozdělovat, případně přehazovat nebo odstraňovat proměnné.\\
\indent Dvě základní operace byly definovány už v \cite{Bry86} - jde o APPLY a
RESTRICT, které budou popsány bezprostředně na dalších řádcích. V kapitole
\ref{kap_razeni} bude následně představena operace \emph{swap}.

\subsection{Operace APPLY}%
Operace APPLY pracuje tak, že mezi dvěma logickými funkcemi reprezentovanými
dvěma ROBDD provede zadanou logickou operaci. $$APPLY(f,g,op) = f <op> g$$
\noindent Důležité je připomenout, že výstupem operace APPLY je \emph{jeden
nový ROBDD} a nikoliv logická hodnota. Pravděpodobně vyvstanou námitky, že je
možné získat hodnotu funkce $f$\footnote{pro dané vstupní hodnoty} i funkce $g$
a pak mezi těmito provést zadanou operaci. Ano, to možné je, ale v praxi se
ukázalo jako výhodnější mít co nejvíc částí jedné logické funkce v jednom
ROBDD\footnote{Každý term funkce může být reprezentován jedním ROBDD, ovšem
není to efektivní.}. Důvodem je především rychlost takto prováděné operace.
Pokud by každá část funkce (např. $f_{on}$ a $f_{dc}$) byla oddělena ve svém
ROBDD, muselo by se udělat tolik průchodů ROBDD, kolik by bylo částí funkcí.
U~částí funkcí \emph{spojených} operací APPLY se provádí jen jeden
průchod\footnote{Časová složitost jednoho průchodu ROBDD je $O(n)$, kde n je
počet proměnných.}.\\
\indent Operace APPLY hraje také zásadní roli při načítání ROBDD. Je v podstatě
jediným snadným způsobem jak ROBDD načíst. Více se uplatněním APPLY při
načítání ROBDD zabývá kapitola \ref{kap_implementace_mbd}. Pro důkladnější
popis APPLY je možné nahlédnout do \cite{Bry86} nebo \cite{Kol06}

\subsection{Operace RESTRICT}
Operace RESTRICT slouží k odstranění proměnné se známou (konstantní) hodnotou z
ROBDD. Odstranění proměnné samozřejmě znamená vyjmout z ROBDD všechny uzly,
které patří dané proměnné. Hrany vedoucí do vyjímaného uzlu se přesměrují podle
toho, jaká je hodnota proměnné, které patří uzel $v$. Je-li rovna $1$, pak se
všichni rodiče přesměrují do $high(v)$, je-li rovna $0$, přesměrují se do
$low(v)$. Více informací i s obrázky je v \cite{Bry86} nebo \cite{Kol06}.


\section{Způsoby vyjádření neúplně určených funkcí pomocí BDD}
Jak plyne z názvu této práce, zabývá se neúplně určenými logickými funkcemi.
Bohužel ROBDD, tak jak byly popsané v předchozím textu, jsou navrženy jen pro
úplně určené funkce. Chceme-li pomocí ROBDD vyjádřit neúplně určenou funkci,
musíme ho zákonitě upravit. Tato podkapitola je věnována známým modifikacím
ROBDD, s nimiž lze neúplně určené funkce vyjádřit.\\
\indent Nejprve budou popsány základní způsoby reprezentace neúplně určených
funkcí a pak bude vysvětlen jeden velmi zajímavý způsob vycházející z
reprezentace logické funkce pomocí charakteristické funkce.\\

\subsection{Základní způsoby reprezentace neúplně určených
funkcí pomocí ROBBD} V literatuře se vyskytují tři základní způsoby
reprezentace neúplně určených funkcí pomocí ROBBD:
\begin{itemize}
    \item Dvojice ROBDD reprezentující funkce $f_{on}$ a $f_{dc}$.
    \item Přidání třetí výstupní hodnoty pro DC.
    \item Zavedení speciální proměnné na vyjádření DC.
\end{itemize}
\paragraph{Neúplně určené funkce pomocí dvou ROBDD} Jde o základní možnost popisu neúplně
určené funkce $f$ pomocí ROBDD. Je-li logická funkce $f$ \emph{úplně} určená,
pak $f_{on}$ (logická funkce, která popisuje množinu takových ohodnocení
vstupních proměnných, pro které logická funkce $f$ vrací $1$) stačí na
vytvoření ROBDD a vyjádření logické funkce. Ovšem pokud je funkce určena
neúplně, a vlastně do \emph{hry} vstupuje třetí terminální hodnota pro
neurčenou výstupní hodnotu, pak se pro vyjádření všech výstupních hodnot
konstruuje druhý ROBBD pro množinu $f_{dc}$. Získání výstupní hodnoty ($0$, $1$
nebo $X$) pak lze například pomocí $ite$ (if-then-else) operátoru:
\begin{center}%
$ite (f_{dc}, X, f_{on}) = (f_{dc}~\wedge~X)~\vee~(\neg f_{dc}~\wedge~f_{on})$.
\end{center}%
\noindent Tato metoda je popsána v \cite{Bry89}. Její nespornou výhodou je, že
pro práci s neúplně určenými funkcemi lze použít naprosto stejné mechanismy
jako pro práci s úplně určenými funkcemi. Prostě se jen pracuje se dvěma ROBDD
a jejich výsledky se pak ještě vyhodnocují. Nevýhodami jsou velká redundance
dat a omezená možnost redukce - snáze se redukuje jeden velký BDD než dva menší
a oddělené.
\paragraph{Neúplně určené funkce pomocí třetí terminální hodnoty}
Tato metoda je jednoznačně nejjednodušší i nejelegantnější. Spočívá pouze v
tom, že místo dvou terminálních hodnot $0$~a~$1$~se zavedou tři: $0$, $1$ a
$X$. Kde $X$ představuje neurčenou výstupní hodnotu - \emph{don't care}. Velkou
výhodou tohoto způsobu je fakt, že množiny $f_{on}$ a $f_{dc}$ jsou v jednom
grafu, což přispívá k~lepší možnosti graf redukovat. Nevýhodou pochopitelně je,
že funkce vrací tři hodnoty, s čímž musí počítat struktury, které s jejími
výstupy pracují. Větší nevýhodou však je, že používané softwarové balíky pro
práci s ROBDD takto definované ROBDD nepodporují. Tento způsob reprezentace
neúplně určené funkce pomocí ROBDD byl představen v \cite{Min90} a do hloubky
se tím zabývá \cite{Jac93}. Celý tento text pracuje právě s touto reprezentací
neúplně určených logických funkcí.

\paragraph{Neúplně určené funkce se zavedením speciální proměnné \emph{z}}
Tento způsob je asi nejméně přímočarý a průhledný. Pro neúplně určenou funkci
$ff$ se zavádí speciální rozšířená (\emph{extended}) funkce: $ext(ff)=
(z~\wedge~ff_{dc})~\vee~(\neg z~\wedge
~ff_{on})$%\\%(tj. $ext(ff)~=~ite(z, ff^{on}, ff^{dc})$)
, kde $z$ je rozšiřující (\emph{extending}) proměnná představuje neurčené
výstupní hodnoty. V ROBDD pro $ext(ff)$ pak proměnné $z$ odpovídají uzly $z_i$
(podle toho, v jaké výšce je). Na takto vytvořený BDD se použije operace
$remove\_Z$, která uzly $z_i$~vyjme. Výsledný ROBDD je pak reprezentací neúplně
určené funkce $ff$. Funkce $remove\_Z$ pracuje takto:
\begin{itemize}%
    \item Pro každý uzel $z_i$ najdi jeho pokrytí $f(z_i)$ a vyjádři ho pomocí ROBBD.
    \item Všechny hrany, které vedly do uzlu $z_i$, pak přesměruj do ROBDD pro $f(z_i)$.
\end{itemize}
\noindent Výhodou této metody je její ohebnost. S proměnnou $z$ lze různě
manipulovat. Především je možné ji při vytváření ROBDD zpracovat v jiném
pořadí, což pak podobně jako při zpracovávání obyčejného ROBDD může vést k jeho
menší výsledné velikosti. Nevýhodou této metody je na rozdíl od předchozích
dvou postupů její složitost. Tento postup byl důkladně vysvětlen v
\cite{Cha94}.

%\subsubsection{Doplnění}
%Většina materiálů jako \cite{chang} nebo \cite{jacobi} se nezabývá jen tím, jak vyjádřit
%NULF, ale rovnou řeší i to jak popsat vícehodnotové logické funkce. Ačkoliv se jednotlivé
%přístupy liší v~tom jak popsat NULF, u vyjádření vícehodnotových funkcí se prakticky
%shodují -- zavádějí ROBDD s více kořeny, kde každý kořen náleží jedné výstupní hodnotě.
%Tomuto přístupu se samozřejmě nebrání ani samotný standardní ROBDD, který si příliš
%nerozumí s neúplně určenými funkcemi. Důsledkem toho je několik odlišných přístupů k této
%problematice. Jak už bylo řečeno dříve v jiné souvislosti, více funkcí integrovaných do
%jednoho ROBDD dává větší šanci na celkovou redukci/minimalizaci funkce, než kdyby pro
%každou její hodnotu byl vytvořen speciální ROBDD. Asi nejkomplexnější řešení bylo
%představeno v \cite{jacobi}, kde byl pro BDD s více kořeny a třetí terminální hodnotou
%zaveden výraz MBD - \emph{Modified Binary Decision Diagram} (Modifikovaný binární
%rozhodovací diagram).

\subsection{Reprezentace neúplně určených logických funkcí pomocí BDD\_for\_CF}
V závěru je vhodné se alespoň okrajově zmínit o poměrně odlišném přístupu k
této problema-tice. Stále se pro reprezentaci logické funkce používá BDD, ale
to, z čeho se vytváří, je odlišné. BDD se nevytváří ze samotné logické funkce
(určené pravdivostní tabulkou nebo součtem termů), ale z \emph{charakteristické
funkce} (characteristic function) dané logické funkce. Charakteris-tická funkce
$\chi$ pro vícehodnotovou neúplně určenou funkci je definována takto:
\begin{center}
$\chi({\mathbf X}, {\mathbf Y})~=~ \bigwedge^m_{i=1} ((\neg y_i\wedge
f^{i}_{off})~\vee~( y_i\wedge f^{i}_{on})~\vee~f^{i}_{dc})$,
\end{center}
\noindent kde $f^{i}_{set}$ představují jednotlivé výstupní funkce s indexem
$i$, $y_i$ je výstupní proměnná funkce $f^{i}_{set}$.\\
\indent Z této funkce vznikne speciální struktura nazvaná BDD\_for\_CF, která
je velmi podobná klasickému BDD, ovšem má pouze jeden kořen (pro vícehodnotovou
funkci). Při jeho vyhodnocování se používají speciální pravidla (nestačí ho jen
projít a vrátit hodnotu nalezeného terminálu). To je především proto, že
některé uzly obsahují výstupní proměnné $y_i$. Více informací je v
\cite{Sas05}.
