\chapter{Modifikovaný binární diagram}
\label{kap_mbd} V kapitole \ref{kap_bdd} byla popsána struktura ROBDD a také
několik jejích modifikací umožňujících reprezentaci neúplně určených funkcí. V
této kapitole bude hlouběji popsána struktura modi-fikovaného binárního
diagramu - MBD, která byla zvolena pro vyjádření neúplně určených logických
funkcí.\\
\indent Hlavním důvodem, proč pracujeme právě s MBD, je jeho
přímočarost a průhlednost, což je dáno tím, že jde o nejmenší úpravu ROBDD.
Bude-li na dalších stránkách použit termín BDD, pak jím bude vždy automaticky
myšlen ROBDD. Stejně tak pojem MBD bude přesně znamenat \emph{Modifikovaný
redukovaný uspořádaný binární rozhodovací diagram} - místo zkratky MROBDD bude
použito jen MBD.

\section{MBD}%
Velmi podrobný popis MBD je možné nalézt v \cite{Jac93}, proto se tento text
omezí jen na nejnutnější vztahy a definice. Je důležité zdůraznit, že úplná
definice MBD pracuje s vícehodnotovými výstupy, zatímco
implementace MBD v této práci pracuje jen s jednohodnotovým výstupem.\\

\noindent Zásadní změnou, kterou MBD přináší do BDD, je přidání třetího
terminálu, který reprezentuje neurčené výstupy a označuje se $X$. Příklad MBD
je na obrázku \ref{mbd_example}. Přítomnost terminálního uzlu $X$, je vynucena
tím, že v MBD nejsou uloženy pouze termy z $f_{on}$, ale také termy z
$f_{dc}$.\\
\indent Výhodou takového řešení\footnote{Neúplně určené funkce je možné
vyjádřit pomocí dvou různých BDD, kde jeden se vytvoří pro $f_{on}$ a druhý pro
$f_{dc}$ - více v kapitole \ref{kap_bdd}.} je to, že se uspoří paměťový prostor
potřebný na reprezentaci dvou BDD, ale především to, že integrace dvou BDD do
jednoho může přinést nové redundance, které se odstraní a celkový počet uzlů se
sníží. Tuto vlastnost dokumentuje obrázek \ref{mbd_example_sets}. O~tomto
fenoménu byla zmínka i v kapitole \ref{kap_bdd} v souvislosti s operací APPLY.
Tato shoda však není nijak překvapující, protože MBD se z $f_{on}$ a $f_{dc}$
vytváří pomocí APPLY s funkcí logický OR: $MBD(f) = APPLY(f_{on}, f_{dc}, OR)$.

\bfig \begin{multicols}{2}{
\includegraphics[height=8cm]{img/mbd-example.png} \pagebreak
~\\
~\\
~\\
~\\
\begin{tabular}{ccccc} \toprule
$x_0$ & $x_1$ & $x_2$ & ~ & $f$\\
\midrule
$0$ & $0$ & $0$ & ~ & $0$\\
$1$ & $0$ & $0$ & ~ & $0$\\
$0$ & $1$ & $0$ & ~ & $-$\\
$1$ & $1$ & $0$ & ~ & $1$\\
$0$ & $0$ & $1$ & ~ & $1$\\
$1$ & $0$ & $1$ & ~ & $0$\\
$0$ & $1$ & $1$ & ~ & $0$\\
$1$ & $1$ & $1$ & ~ & $0$\\
\bottomrule \end{tabular} }\end{multicols} \caption
[MBD logické funkce a jeho pravdivostní tabulka]{\textbf{MBD logické funkce}
$f_{on}=x_0x_1\bar{x_2}+\bar{x_0}\bar{x_1}x_2$;
 $f_{dc}=x_0\bar{x_1}x_2$ a jeho pravdivostní tabulka.}
\label{mbd_example} \efig

\bfig \includegraphics[height=8.4cm]{img/mbd-example-1.png} \hskip 80pt
\includegraphics[height=8.4cm]{img/mbd-example-dc.png} \caption[Dva BDD pro
logickou funkci s DCsetem]{ \textbf{Dva BDD pro logickou funkci s DCsetem.} BDD
na obrázku \emph{a)} zobrazuje $f_{on}$ a~BDD na obrázku \emph{b)} zase
$f_{dc}$. Jde o~stejnou logickou funkci jako na předchozím vyobrazení. Je možné
si všimnout, že celkový počet uzlů je zde o~tři vyšší než u MBD. }
\label{mbd_example_sets} \efig

\subsection{Vlastnosti MBD}%
Ve zkratce lze říci, že vlastnosti a použití MBD jsou totožné s vlastnostmi a
použitím BDD - pochopitelně s přihlédnutím k faktu, že MBD má navíc jeden
terminální symbol. Jinými slovy se s MBD pracuje úplně stejně jako s BDD. Více
je tato podobnost rozebrána v \cite{Jac93}

\subsection{Zvláštnosti MBD} To, že se v MBD pracuje i s $f_{on}$ a
$f_{dc}$, má však určité nároky. Při provádění všech logických ope-rací s
terminálními uzly \footnote{Například během operace APPLY s nějakou logickou
funkcí - např. OR.} se musí počítat s logickou hodnotou $X$.
Tyto operace jsou vyjádřeny na obrázku \ref{dc_log_op}.\\

\noindent Komplikacím, které se vyskytují při implementaci MBD, bude věnována
část kapitoly \ref{kap_implementace_mbd}.

\bfig \begin{multicols}{3}
{
\begin{tabular}{cccc}
\toprule
\textbf{AND} & $0$ & $1$ & $X$\\
\midrule
$0$ & $0$ & $0$ & $0$ \\
$1$ & $0$ & $1$ & $X$ \\
$X$ & $0$ & $X$ & $X$ \\
\bottomrule
\end{tabular}
\pagebreak

\begin{tabular}{cccc}
\toprule
\textbf{OR} & $0$ & $1$ & $X$\\
\midrule
$0$ & $0$ & $0$ & $0$ \\
$1$ & $0$ & $1$ & $X$ \\
$X$ & $0$ & $X$ & $X$ \\
\bottomrule
\end{tabular}
\pagebreak

\begin{tabular}{cccc}
\toprule
\textbf{NEG} & ~\\
\midrule
$0$ & $1$\\
$1$ & $0$\\
$X$ & $X$\\
\bottomrule
\end{tabular}
\pagebreak
}
\end{multicols}
\caption[Logické operace s DCsetem]{\textbf{Logické operace s DCsetem.}
Místo logických symbolů bylo použito anglických názvů. \emph{AND} je logický součin,
\emph{OR} je logický součet a \emph{NEG} je logická negace.}
\label{dc_log_op}
\efig
