%% History:
% Pavel Tvrdik (26.12.2004)
%  + initial version for PhD Report
%
% Daniel Sykora (27.01.2005)
%   
% Michal Valenta (3.12.2008)
% rada zmen ve formatovani (diky M. Duškovi, J. Holubovi a J. Žďárkovi)
% sjednoceni zdrojoveho kodu pro anglickou, ceskou, bakalarskou a diplomovou praci

% One-page layout: (proof-)reading on display
%%%% \documentclass[11pt,oneside,a4paper]{book}
% Two-page layout: final printing
\documentclass[11pt,twoside,a4paper]{book}   
%=-=-=-=-=-=-=-=-=-=-=-=--=%
% The user of this template may find useful to have an alternative to these 
% officially suggested packages:
\usepackage[czech, english]{babel}
\usepackage[T1]{fontenc} % pouzije EC fonty 
% pripadne pisete-li cesky, pak lze zkusit take:
% \usepackage[OT1]{fontenc} 
\usepackage[utf8]{inputenc}
%=-=-=-=-=-=-=-=-=-=-=-=--=%
% In case of problems with PDF fonts, one may try to uncomment this line:
%\usepackage{lmodern}
%=-=-=-=-=-=-=-=-=-=-=-=--=%
%=-=-=-=-=-=-=-=-=-=-=-=--=%
% Depending on your particular TeX distribution and version of conversion tools 
% (dvips/dvipdf/ps2pdf), some (advanced | desperate) users may prefer to use 
% different settings.
% Please uncomment the following style and use your CSLaTeX (cslatex/pdfcslatex) 
% to process your work. Note however, this file is in UTF-8 and a conversion to 
% your native encoding may be required. Some settings below depend on babel 
% macros and should also be modified. See \selectlanguage \iflanguage.
%\usepackage{czech}  %%%%%\usepackage[T1]{czech} %%%%[IL2] [T1] [OT1]
%=-=-=-=-=-=-=-=-=-=-=-=--=%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Styles required in your work follow %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{graphicx}
%\usepackage{indentfirst} %1. odstavec jako v cestine.
\usepackage{longtable}
\usepackage{color}
\usepackage{k336_thesis_macros} % specialni makra pro formatovani DP a BP
 % muzete si vytvorit i sva vlastni v souboru k336_thesis_macros.sty
 % najdete  radu jednoduchych definic, ktere zde ani nejsou pouzity
 % napriklad: 
 % \newcommand{\bfig}{\begin{figure}\begin{center}}
 % \newcommand{\efig}{\end{center}\end{figure}}
 % umoznuje pouzit prikaz \bfig namisto \begin{figure}\begin{center} atd.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zvolte jednu z moznosti 
% Choose one of the following options
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand\TypeOfWork{Diplomová práce} \typeout{Diplomova prace}
% \newcommand\TypeOfWork{Master's Thesis}   \typeout{Master's Thesis} 
% \newcommand\TypeOfWork{Bakalářská práce}  \typeout{Bakalarska prace}
% \newcommand\TypeOfWork{Bachelor's Project}  \typeout{Bachelor's Project}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zvolte jednu z moznosti 
% Choose one of the following options
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% nabidky jsou z: http://www.fel.cvut.cz/cz/education/bk/prehled.html

%\newcommand\StudProgram{Elektrotechnika a informatika, dobíhající, Bakalářský}
%\newcommand\StudProgram{Elektrotechnika a informatika, dobíhající, Magisterský}
% \newcommand\StudProgram{Elektrotechnika a informatika, strukturovaný, Bakalářský}
 \newcommand\StudProgram{Elektrotechnika a informatika, strukturovaný, Navazující magisterský}
% \newcommand\StudProgram{Softwarové technologie a management, Bakalářský}
% English study:
% \newcommand\StudProgram{Electrical Engineering and Information Technology}  % bachelor programe
% \newcommand\StudProgram{Electrical Engineering and Information Technology}  %master program


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zvolte jednu z moznosti 
% Choose one of the following options
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% nabidky jsou z: http://www.fel.cvut.cz/cz/education/bk/prehled.html

%\newcommand\StudBranch{Výpočetní technika}   % pro program EaI bak. (dobihajici i strukt.)
\newcommand\StudBranch{Výpočetní technika}   % pro prgoram EaI mag. (dobihajici i strukt.)
%\newcommand\StudBranch{Softwarové inženýrství}            %pro STM
%\newcommand\StudBranch{Web a multimedia}                  % pro STM
%\newcommand\StudBranch{Computer Engineering}              % bachelor programe
%\newcommand\StudBranch{Computer Science and Engineering}  % master programe


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Vyplnte nazev prace, autora a vedouciho
% Set up Work Title, Author and Supervisor
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand\WorkTitle{Ortogonalizace logických funkcí}
\newcommand\FirstandFamilyName{Bc. Lukáš Höger}
\newcommand\Supervisor{Ing. Petr Fišer, Ph.D.}


% Pouzijete-li pdflatex, tak je prijemne, kdyz bude mit vase prace
% funkcni odkazy i v pdf formatu
\usepackage[
pdftitle={\WorkTitle},
pdfauthor={\FirstandFamilyName},
bookmarks=true,
colorlinks=true,
breaklinks=true,
urlcolor=red,
citecolor=blue,
linkcolor=blue,
unicode=true,
]
{hyperref}




\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zvolte jednu z moznosti 
% Choose one of the following options
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\selectlanguage{czech}
%\selectlanguage{english} 

% prikaz \typeout vypise vyse uvedena nastaveni v prikazovem okne
% pro pohodlne ladeni prace


\iflanguage{czech}{
	 \typeout{************************************************}
	 \typeout{Zvoleny jazyk: cestina}
	 \typeout{Typ prace: \TypeOfWork}
	 \typeout{Studijni program: \StudProgram}
	 \typeout{Obor: \StudBranch}
	 \typeout{Jmeno: \FirstandFamilyName}
	 \typeout{Nazev prace: \WorkTitle}
	 \typeout{Vedouci prace: \Supervisor}
	 \typeout{***************************************************}
	 \newcommand\Department{Katedra počítačů}
	 \newcommand\Faculty{Fakulta elektrotechnická}
	 \newcommand\University{České vysoké učení technické v Praze}
	 \newcommand\labelSupervisor{Vedoucí práce}
	 \newcommand\labelStudProgram{Studijní program}
	 \newcommand\labelStudBranch{Obor}
}{
	 \typeout{************************************************}
	 \typeout{Language: english}
	 \typeout{Type of Work: \TypeOfWork}
	 \typeout{Study Program: \StudProgram}
	 \typeout{Study Branch: \StudBranch}
	 \typeout{Author: \FirstandFamilyName}
	 \typeout{Title: \WorkTitle}
	 \typeout{Supervisor: \Supervisor}
	 \typeout{***************************************************}
	 \newcommand\Department{Department of Computer Science and Engineering}
	 \newcommand\Faculty{Faculty of Electrical Engineering}
	 \newcommand\University{Czech Technical University in Prague}
	 \newcommand\labelSupervisor{Supervisor}
	 \newcommand\labelStudProgram{Study Programme} 
	 \newcommand\labelStudBranch{Field of Study}
}




%%%%%%%%%%%%%%%%%%%%%%%%%%    Poznamky ke kompletaci prace
% Nasledujici pasaz uzavrenou v {} ve sve praci samozrejme 
% zakomentujte nebo odstrante. 
% Ve vysledne svazane praci bude nahrazena skutecnym 
% oficialnim zadanim vasi prace.
% {
% \pagenumbering{roman} \cleardoublepage \thispagestyle{empty}
% \chapter*{Na tomto místě bude oficiální zadání vaší práce}
% \newpage
% }

%%%%%%%%%%%%%%%%%%%%%%%%%%    Titulni stranka / Title page 

\coverpagestarts

%%%%%%%%%%%%%%%%%%%%%%%%%%%    Podekovani / Acknowledgements 

\acknowledgements
\noindent
Rád bych na tomto místě poděkoval Ing. Petru Fišerovi, Ph.D. za vedení diplomové práce, za jeho cenné rady, podklady a připomínky. 

	Dále děkuji mé rodině za poskytnuté zázemí při psaní této práce. Zejména patří dík otci Vítězslavovi za výpomoc při stylizaci textu a mé matce Věře za gramatickou korekturu textu. Chtěl bych také poděkovat své přítelkyni Janě Steblové za psychickou podporu a bratru Tomášovi za technické konzultace. 


Děkuji také svému Bohu za to, že mohu studovat technickou školu a že se mohu učit trpělivosti a systematičnosti při každé nové práci. 

	



%%%%%%%%%%%%%%%%%%%%%%%%%%%   Prohlaseni / Declaration 

\declaration{V Praze dne 4.\,1.\,2010}
%\declaration{In Kořenovice nad Bečvárkou on May 15, 2008}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%    Abstract 
 
\abstractpage
This thesis pursues orthogonalization of a logic function - decomposition of logic function to disjoint sum of products. The thesis proposes implementation of a algorithm for orthogonalization with optimalization of results. A product of this work is a tool which is able to load logic function from PLA file, minimize it and save it back. Implementation of the algorithm is compared on MCNC benchmarks with DSOP and a subprogram of Espresso for orthogonalization.  

\vglue60mm

\noindent{\Huge \textbf{Abstrakt}}
\vskip 2.75\baselineskip

\noindent
Tato diplomová práce se zabývá ortogonalizací logické funkce - rozklad logické funkce na součet vzájemně nepřekrývajících se součinů termů. Práce předkládá návrh vhodného algoritmu pro ortogonalizaci s optimalizaci výsledného řešení. Výsledkem je nástroj, který dokáže načíst logickou funkci z PLA souboru, ortogonalizovat ji a uložit zpět. Implementace algoritmu je porovnána na MCNC benchmarcích s cizími dostupnými nástroji DSOP a Espresso s podprogramem pro ortogonalizaci.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Obsah / Table of Contents 

\tableofcontents


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Seznam obrazku / List of Figures 

\listoffigures


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Seznam tabulek / List of Tables

\listoftables


%**************************************************************

\mainbodystarts
% horizontalní mezera mezi dvema odstavci
%\parskip=5pt
%11.12.2008 parskip + tolerance
\normalfont
\parskip=0.2\baselineskip plus 0.2\baselineskip minus 0.1\baselineskip

% Odsazeni prvniho radku odstavce resi class book (neaplikuje se na prvni 
% odstavce kapitol, sekci, podsekci atd.) Viz usepackage{indentfirst}.
% Chcete-li selektivne zamezit odsazeni 1. radku nektereho odstavce,
% pouzijte prikaz \noindent.

%**************************************************************

% Pro snadnejsi praci s vetsimi texty je rozumne tyto rozdelit
% do samostatnych souboru nejlepe dle kapitol a tyto potom vkladat
% pomoci prikazu \include{jmeno_souboru.tex} nebo \include{jmeno_souboru}.
% Napr.:
% \include{1_uvod}
% \include{2_teorie}
% atd...

%*****************************************************************************
\chapter{Úvod}

\section{Úvod do problematiky}
Elektronická digitální zařízení v dnešní době hluboce pronikly do života každého z nás. Můžeme je najít v mnoha oblastech, od dětských hraček až po automobily. S rychlým tempem rozvoje elektroniky přichází potřeba její efektivní implementace. Návrh logických obvodů se stal klíčovým faktorem ekonomické úspěšnosti převážné většiny současných průmyslových výrobků.

Oblast logických funkcí přirozeně zavádí početní algebru v dvouhodnotovém světě jedniček a nul, která modeluje vlastnosti množinových a logických operací. Proces ortogonalizace, kterým se v této práci budeme zabývat, je algebraický způsob převodu zadané logické funkce do tvaru, kdy se jednotlivé součty součinů vstupních proměnných vzájemně neprotínají. Úkolem této práce je nejen nalézt způsob transformace logické funkce do ortogonalizované podoby, ale také optimalizace výsledku hledáním co nejúspornějšího vyjádření řešení.


S ortogonalizaci logických funkcí se dnes setkáváme v mnoha oblastech moderních návrhů logických obvodů. Používá se jako startovní bod pro syntézu ESOPs [1] nebo pro výpočet spektra logických funkcí [2].


\section{Cíle práce}
\begin{itemize} 
\item Seznámení se stávajícími (konkurenčními) nástroji pro ortogonalizaci logické funkce.
\item Návrh a implementace algoritmu pro ortogonalizaci.
\item Otestování vytvořeného řešení na zkušebních úlohách.
\item Srovnání s konkurenčními nástroji.
\end{itemize} 


\section{Implementační požadavky na řešení}
\begin{itemize}
\item Implementace algoritmu v programovacím jazyce C++.
\item Realizace nástroje postavena na programu BOOM (BOOlean Minimizer).
\end{itemize}

\section{Rozdělení textu na kapitoly}

Diplomová práce je rozdělena do osmi kapitol. První kapitola popisuje úvod do problematiky a shrnuje cíle práce. V druhé kapitole jsou zavedeny pojmy a definice z oblastí logických obvodů. V třetí kapitole je přiblížen proces ortogonalizace logické funkce. Ve čtvrté kapitole jsou nastíněny cizí dostupné nástroje na ortogonalizaci. V páté kapitole je analyzován problém ortogonalizace logické funkce s návrhem co nejoptimálnějšího vlastního řešení. V šesté kapitole je popsána realizace samotného řešení. Sedmá kapitola se zabývá testováním jednotlivých verzí navrženého algoritmu a srovnání s konkurenčními implementacemi. Osmá kapitola zhodnocuje splnění cílů práce, shrnuje výsledky testování a popisuje možné budoucí rozšíření a vylepšení navrženého algoritmu.









%*****************************************************************************
\chapter{Definice}
\section{Opakování pojmů}
V této sekci budou nastíněny základní termíny a definice z oblastí booleovy algebry a logických funkcí použitých v textu této práce. Záměrem této části je připomenout tyto pojmy, ne však dostačujícím způsobem vysvětlit. 

\subsection{Booleova algebra} 
Logické funkce využívající dvouhodnotovou logiku se označují jako Booleovy funkce. Matematickým nástrojem na práci s Booleovými funkcemi je Booleova algebra, která je definována jako distributivní a komplementární svaz skládající se z:
\begin{itemize}
\item Konečné množiny logických proměnných ($a$, $b$, $c$, $d$, $e$, ...$z$). 
\item Binárních operací logického součtu (označovaného + nebo $\vee$ ) a logického součinu (. nebo $\wedge$).
\item Unární operace negace ($^{-}$ nebo $\neg$).
\item Dvou nulárních operací v podobě logických konstant 0 a 1.
\end{itemize}$\\$
Pro Booleovou algebru platí tyto základní zákony:
\begin{itemize}
\item Asociativita: $(x + y) + z = x + (y + z)$, $(x * y) * z = x * (y * z)$ 
\item Komutativita: $x + y = y + x$, $x * y = y * x$ 
\item Distributivní zákon: $x + ( y * z ) = ( x + y ) * ( x + z )$, $x * ( y + z ) = x * y + x * z$
\item Absorpce: $x + (x * y) = x, x * (x + y) = x$, $x + x = x, x * x = x$
\item Absorpce negace: $x + (\overline{x} * y) = x + y$, $x * (\overline{x} + y) = x * y$
\item Agresivita nuly a jedničky: $x * 0 = 0$, $x + 1 = 1$
\item Komplementarita: $x + \overline{x} = 1$, $x * \overline{x} = 0$
\item Dvojitá negace: $\overline{(\overline{x})} = x$
\item De Morganovy zákony: $\overline{x} * \overline{y} = \overline{(x + y)}$, $\overline{x} + \overline{y} = \overline{(x * y)}$
\end{itemize}
\subsection{Vyjádření logických funkcí}
Logická (Booleova) funkce $n$ proměnných je definována jako $f$ : $B^n$ $\rightarrow$ $B$, je-li $B$ Booleova algebra. Logickou funkci lze zapsat několika způsoby:
\begin{itemize}
\item \textbf{Pravdivostní tabulka} $ $ Tabulka obsahující všechny možné kombinace vstupních proměnných a pro ně definovaných výstupů.
\item \textbf{Logický výraz} $ $ Vyjádření logické funkce v algebraické formě.
\item \textbf{Mapa} $ $ Karnaughova mapa využívající se pro minimalizaci logické funkce s malým počtem proměnných.
\item \textbf{Vícerozměrné jednotkové krychle} $ $ Popis logické funkce pomocí vícerozměrné krychle, kde souřadnice jsou dány hodnotami vstupních proměných.
\item \textbf{Modifikované binární diagramy} $ $ Reprezentace logické funkce vhodná pro strojovou minimalizaci.
\end{itemize}
\subsection{Používané důležité termíny}
\textbf{Literál} $ $ Proměnná nebo její negace. Literál může nabývat pouze dvou hodnot "0" nebo "1".
\\\\
\textbf{Term} $ $ Logický výraz složený z literálů mezi sebou navzájem vázaných logickým operátorem. Termy dělíme na součinový term = krychle (neobsahuje operátory součtu) a součtový term (neobsahuje operátory součinu). \textbf{Upozornění}: V textu této práce bude pod pojmem term myšlen term součinový nebude-li uvedeno jinak! 
\\\\
\textbf{ONset} $ $ Množina termů logické funkce, jejichž výstupem je logická "1".
\\\\
\textbf{OFFset} $ $ Množina termů logické funkce, jejichž výstupem je logická "0".
\\\\
\textbf{DCset (Don't care set)} $ $ Množina termů logické funkce, jejichž výstup není určen.
\\\\
\textbf{Implikant logické funkce} $ $ Součinový term, který definuje logickou funkci. Každý term z množiny ONset je implikantem logické funkce.
\\\\
\textbf{Přímý implikant} $ $ Implikant logické funkce, který už není možné více zjednodušit.
\\\\
\textbf{Minterm} $ $ Součinový term, který obsahuje všechny vstupní proměnné (mohou být v přímém nebo inverzním tvaru)
\\\\
\textbf{Maxterm} $ $ Součtový term, který obsahje všechny vstupní proměnné (mohou být v přímém nebo inverzním tvaru)
\\\\
\textbf{Součet termů (SOP)} $ $ Množina termů zahrnující všechny jedničky "1".
\\\\ 
\textbf{Disjunktivní normální forma (DNF)} $ $ Logický výraz ve tvaru součtu součinových termů, který má funkční hodnotu logickou "1".
\\\\
\textbf{Konjunktivní normální forma (CNF)} $ $ Logický výraz ve tvaru součinu součtových termů, který má funkční hodnotu logickou "0".
\\\\
\textbf{Pokrytí logické funkce} $ $ Množina termů reprezentující danou logickou funkci (nejmenší počet termů).
\\\\
\textbf{Booleova minimalizace} $ $ Dvouúrovňová minimalizace, která hledá pokrytí o minimální velikosti (nejmenší počet termů).




\section{Operace pro dekompozici termů} \label{sec:sharp}
Úloha ortogonalizace logické funkce je postavena na postupném rozkladu termů. V této sekci si uvedeme dvě operace pro dekompozici. Jsou to Sharp a Disjoint sharp. 
\\\\
\textbf{Operace Sharp}
\\\\
Operaci Sharp označíme $\#$; $\alpha$ a $\beta$ jsou implikanty logické funkce. \\
Pro $\alpha \# \beta$ vrací operace Sharp součet implikantů, kdy $\alpha$ bude zachován a $\beta$ pokrývají implikanty, které nesmí pokrýt žádnou $"1"$ z $\alpha$. 
\\\\
Příklad použití operace Sharp:
\\\\
$\alpha = bc$\\
$\beta = a\overline{d} + \overline{a} d $\\
$\alpha \# \beta = bc + \overline{b}a\overline{d} + \overline{c}a\overline{d} + \overline{a}d\overline{b} + \overline{a}d\overline{c}$
\\\\
Zápis příkladu použití operace Sharp je v Karnaughové mapě na obrázku \ref{fig:sharp_operation}.
\\
\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/sharp_operation}
\caption{Příklad použití operace Sharp}
\label{fig:sharp_operation}
\end{center}
\end{figure} $ $
\\\\
\textbf{Operace Disjoint sharp}
\\\\
Operace Disjoint sharp vychází z operace Sharp. Operaci Disjoint sharp označíme $\bigodot$. \\
Pro $\alpha \bigodot \beta$ vrací operace Disjoint sharp součet implikantů, kdy $\alpha$ bude zachován a $\beta$ pokrývají implikanty, které nesmí pokrýt žádnou $"1"$ z $\alpha$. Zároveň všechny výsledné implikanty jsou vzájemně disjunktní (vzájemně se neprotínají).   
\\\\
Příklad použití operace Disjoint sharp:
\\\\
$\alpha = bc$\\
$\beta = a \overline{d} + \overline{a} d $\\
$\alpha \bigodot \beta = bc + \overline{b}ac\overline{d} + \overline{c}a\overline{d} + \overline{a}d\overline{b} + \overline{a}bd\overline{c}$
\\\\
Zápis příkladu použití operace Disjoint sharp je v Karnaughové mapě na obrázku \ref{fig:disjointsharp_operation}.
\\
\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/disjointsharp_operation}
\caption{Příklad použití operace Disjoint sharp}
\label{fig:disjointsharp_operation}
\end{center}
\end{figure}
\\
\\


\section{Formát PLA} \label{sec:formatpla}

Formát PLA je navržen University of California Berkeley v USA. Používá se pro načítání a ukládání logické funkce. PLA formát je způsob zápisu reprezentace dvouúrovňové logické funkce. V této části budou popsány jeho nejdůležitější vlastnosti, více informací je možné najít v [16].

PLA formát se zapisuje v textovém souboru s příponou $.pla$. Soubor se načítá po jednotlivých řádcích a každý řádek udává parametr nebo vlastnost logické funkce.
\\\\
Základní nejdůležitější parametry jsou:
\\\\
\textbf{.i [číslo]} Parametr udává počet vstupních proměnných.\\
\textbf{.o [číslo]} Parametr udává počet výstupů logické funkce.\\
\textbf{.p [číslo]} Parametr udává počet termů.\\
\textbf{.type [typ]} Typ způsobu definice logické funkce. \\
\textbf{e.} Příznak označující konec definice logické funkce.\\
\\\\
Logická funkce je definována pomocí seznamu termů (jeden term = jeden řádek). Každý term je v součinovém tvaru a má podobu: 

1100-1-1 11-0
\\
Levá část po mezeru určuje vstupní proměnné funkce a pravá část za mezerou odpovídá výstupním hodnotám, které definují, zda je term na levé straně pravdivý. Znak "-" označuje neurčený vstup / výstup. Ve vstupní části označuje znak "1" literál a znak "0" označuje negovaný literál. Ve výstupní části znak "1" říká, že term patří do ONsetu pro daný výstup a znak "0" říká, že term patří do OFFsetu daného výstupu. 
\\\\
Příklad PLA souboru je na obrázku \ref{fig:plaformat}.
\begin{figure}
\begin{center}
\includegraphics[width=2.9cm]{figures/PLAformat}
\caption{Příklad výpisu souboru s logickou funkcí v PLA formátu.}
\label{fig:plaformat}
\end{center}
\end{figure}




\section{Nástroj BOOM} \label{sec:boom}
Program BOOM (BOOlean Minimizer) byl použit jako základ při vytváření algoritmu ortogonalizace logické funkce. BOOM je heuristický nástroj pro minimalizaci (booleovských) logických funkcí, vyvíjený katedrou výpočetní techniky fakulty elektrotechnické ČVUT v Praze. Běží jako Win32 console aplikace a obsahuje škálu funkcí a operací pro práci z logickými funkcemi. Je to např. již zmiňovaná minimalizace logické funkce, přidávání a odebírání termů, informativní funkce vracející vlastnosti termů, funkce porovnávající termy aj. 

BOOM podporuje formát PLA. Na programu se stále pracuje a vylepšují se jeho schopnosti, nejnovější verze je BOOM 2.7.


%*****************************************************************************
\chapter{Popis problému ortogonalizace}
V následujích řádcích této kapitoly je popsána činnost ortogonalizace logických funkcí a úskalí, která jsou s ní spojené.

\section{Ortogonalizace}

V lineární algebře se ortogonalizací označuje postup hledání souboru ortogonálních (vzájemně kolmých) vektorů, které pokrývají vymezený podprostor [14]. Formálně popsáno, ortogonalizace je proces nalezení v lineárně nezávislém souboru vektorů $(v_{1} , v_{2}, ..., v_{k})$ soubor vektorů $(u_{1} , u_{2}, ..., u_{k})$, který generuje stejný podprostor jako vektory $(v_{1} , v_{2}, ..., v_{k})$. Přitom každý vektor z nového souboru je kolmý ke všem ostatním vektorům v novém souboru. 
\\\\
Jednoduše řečeno, ortogonalizace je proces rozdělení problému nebo systému na jednotlivé odlišné prvky, které po složení dají stejný výsledek. 

\section{Ortogonalizace logické funkce} \label{sec:ortogonalizace_definice}

Ortogonalizací je v tomto projektu myšlen rozklad logické funkce na součet vzájemně nepřekrývajících se součinů termů. Tento tvar logické funkce se označuje DSOP (Disjoint Sum of Product).
\\
\\
Názorná ukázka ortogonalizace logické funkce je na obrázku \ref{fig:mapa0}. Je patrné, že výsledek ortogonalizace má úzkou spojitost s operaci $\bigodot$ (viz. kap \ref{sec:sharp}). Postupný rozklad termů pomocí této operace zaručí ortogonalitu logické funkce. 

\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/mapa0}
\caption{Logická funkce a její ortogonalizovaný tvar zapsaný v Karnaughové mapě.}
\label{fig:mapa0}
\end{center}
\end{figure} 
$ $\\
Pro ortogonalizovanou logickou funkci $f2$, která vznikla rozkladem logické funkce $f1$, musí platit tyto dvě vlastnosti:
\begin{itemize}
\item Každý term z $f2$ musí být disjunktní (nesmí se protínat) s ostatními termy z $f2$.  
\item $f1$ a $f2$ musí být vzájemně ekvivalentní logické funkce, tj. termy z $f1$ musí pokrýt všechny termy z $f2$ a naopak.
\end{itemize}
$ $ 
\\
Elementární rozklad, který zaručí vždy ortogonalitu logické funkce, je dekompozice na jednotlivé mintermy.


\section{Rozložení dvou termů}
Pro dva termy $t_{1}$ a $t_{2}$, které se vzájemně překrývají (příklad na obrázku \ref{fig:mapa1}), existují vždy dvě efektivní možnosti rozkladu. Zachová se buď term $t_{1}$ (zůstane nezměněn) a podle něho se rozdělí term $t_{2}$ na součet podtermů  ($t_{1} \bigodot t_{2}$; levá Karnaughová mapa na obrázku \ref{fig:mapa2}). 

V druhém případě naopak  term $t_{2}$ zůstane nezměněn a rozdělí term $t_{1}$ na součet podtermů ($t_{2} \bigodot t_{1}$; pravá Karnaughová mapa na obrázku \ref{fig:mapa2}). 

Různými možnostmi dekompozice logické funkce můžeme ve výsledku dosáhnout odlišného počtu termů. Přichází tím první důležité zamyšlení. Jakým způsobem provést rozklad aby počet termů byl co nejmenší a tím bylo dosáženo co nejlepšího možného výsledku? Toto můžeme označit jako stěžejní otázku problému ortogonalizace, na kterou se snažím v této práci najít odpověď.
\\\\
\begin{figure}[ht]
\begin{center}
\includegraphics[width=5cm]{figures/mapa1}
\caption{Logická funkce zapsaná v Karnaughové mapě.}
\label{fig:mapa1}
\end{center}
\end{figure}


\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/mapa2}
\caption{Ortogonalizovaná logická funkce. Ukázka dvou způsobů rozkladu.}
\label{fig:mapa2}
\end{center}
\end{figure}

\section{Časová složitost algoritmu}
Cena za algoritmus, který hledá nejlepší výsledek, je obvykle penalizován časem, tzv. je časově náročnější. Algoritmus, který dokáže rozložit logickou funkci na co nejmenší počet vzájemně disjunktních termů, vede k řešení postavit časově složitější programovou konstrukci. 

A jak moc nás zajímá v úloze tohoto projektu časová složitost? Z využití ortogonalizace logických funkcí v praxi můžeme usoudit, že jediným kritériem pro časovou náročnost je vytvoření algoritmu, který bude schopný dokončit úlohy v akceptovatelném čase. 

\subsection{Optimální řešení}

Nalezení optimálního řešení ortogonalizace logické funkce lze převést na úlohu minimálního pokrytí. Algoritmus minimálního pokrytí je NP těžká úloha [8]. Z časové složitosti algoritmu vyplývá, že optimální řešení ortogonalizace logické funkce nelze vždy najít v polynomiálním čase. 

Pro úlohu, která je zadaná logickou funkcí o stovkách až tisících termech, je ale důležité, aby její řešení bylo nalezeno v polynomiálním čase, jinak by doba čekání na výsledek byla neúnosná. Proto v této práci je vytvářen algortimus, který pracuje v polynomiálním čase, ale s ryzikem, že nenajde vždy optimální řešení.



%*****************************************************************************
\chapter{Seznámení s existujícími implementacemi}

V této kapitole si přiblížíme existující implementace ortogonalizace logických funkcí. Programů, které řeší tento problém, není mnoho. Z dostupných, které jsem měl možnost vyzkoušet, to byly tyto tři: Espresso, DSOP, DSOP využívající maximální binate proměnné. 

V následujících podkapitolách se s těmito nástroji podrobněji seznámíme. Testování a srovnávání jednotlivých nástrojů se nachází v kapitole \ref{sec:testovani}.

\section{Espresso} \label{sec:Espresso_Disjoint}

Program Espresso [5] je heuristický nástroj pro dvouúrovňovou minimalizaci logických funkcí. Autorem základního algoritmu je Richard Rudell působící na University of California Berkeley. Na jeho základě byl vyvinut samotný nástroj Espresso, který byl navržen Robert Braytonem z IBM. Jedná se o volně kopírovatelný program, který je v oblasti minimalizace široce rozšířen. 

Espresso je implementováno v K \& R C [10], ale existuje také i v mnoha jiných podobách, včetně knihovny do C++. Podporovaný formát pro načtení a uložení logické funkce je PLA.

Přestože hlavní přínos Espressa je v oblasti optimalizace heuristické minimalizace, nástroj obsahuje také i podprogram na rozklad termů na disjunktní části. Spuštění programu se provádí pomocí parametru -Ddisjoint.

Rozložení termů je založeno na operaci Disjoint sharp. Samotný proces ortogonalizace je implementován velice jednoduše, bez žádných složitějších sofistikovaných metod.

\section{DSOP} \label{sec:DSOP_1}

Nejsilnější dostupný nástroj na ortogonalizaci logických funkcí, s kterým jsem měl možnost se seznámit, je DSOP [11] vzniklý na Katedře informačních technologií na universitě v Pise v Itálii. Jejími autory jsou A. Bernasconi, V. Ciriani, F. Luccio, L. Pagli. 

DSOP představuje implementaci heuristického rozhodování pro nalezení disjunktního součtu součinů termů logické funkce. Nástroj je implementován v programovacím jazyku Java a podporuje PLA formát.
\\\\ 
Algoritmus pracuje ve čtyřech fázích:
\begin{itemize} 
\item V první fázi se spustí Espresso pro minimalizaci zadané logické funkce. 
\item V druhé fázi se přiřadí termům váha $w$, která je závislá na počtu protnutí s ostatními termy.
\item V třetí fázi se setřídí pořadí termů podle váhy $w$.  
\item Ve čtvrté fázi se provede rozložení termů na disjunktní celky pomocí metody postavené na operaci Disjoint sharp.
\end{itemize} 
Složitost celého algoritmu je polynominální ve velikosti výstupu, tj. počtem termů vzniklých při rozkladu.
\\\\
DSOP je vytvořena ve třech dostupných verzích:
\begin{itemize} 
\item DSOP-1 $ $ Jednoduchá nejrychlejší verze, založený na základním algoritmu bez průběžného uspořádání termů během procesu rozkladu. 
\item DSOP-2  $ $ Zdokonalený algoritmus rozšířen o průběžné uspořádání termů během procesu rozkladu.
\item DSOP-3  $ $ Algoritmus DSOP-2 s vylepšeným výběrem termů pro rozklad.
\end{itemize} 
Pro každou variantu algoritmu je možnost volby mezi dvěmi typy uspořádání termů podle váhy a to vzestupně nebo sestupně.


\section{DSOP využívající maximální binate proměnné}

Algortimus ortogonalizace logické funkce, který je postaven na heuristice nalezení největší binate proměné [6]. Jeho autoři jsou L. Shivakumaraiah and A. Thornton z Department of Electrical and Computer Engineering v Mississippi State University. 
\\\\
Algoritmus v prvním kroku hledá proměnnou (tzv. největší binate proměnnou), která má nejčastější výskyt ve všech termech logické funkce v přímé nebo negované podobě. Termy jsou rozděleny podle této největší binate proměnné na dvě kategorie. Na termy, které ji obsahují v přímé podobě (A) a termy , které ji obsahují v negované podobě (B). Termy, které mají na pozici binate proměnné don't care, se přepíšou v dané proměnné na "1" a uloží se do A a zároveň na "0" a uloží se do B. Algoritmus se opakuje tak dlouho, dokud se postupně neprojdou všechny proměnné dané logické funkce.
\\\\
Nástroj, postavený na popisovaném algoritmu, využívá pro načtení a uložení logické funkce formát PLA.
\\\\
Program DSOP využívající maximální binate proměnné není volně dostupný k použití. Měl jsem pouze možnost se s ním seznámit teoreticky a to prostřednictvím informací, které lze nalézt na internetu [6]. Jsou tam k vidění i srovnávací testy s jinými algoritmy. Podle mého názoru, ale nejsou použitelné, protože počet úloh, na kterém byla tato implementace testovaná, je velice malý. Je jich pouze 7. Z tohoto důvodu algoritmus DSOP využívající maximální binate proměnné nebude začleněn do srovnávacích testů této diplomové práce.





%*****************************************************************************
\chapter{Analýza problému a návrh implementace}

Záměrem této kapitoly je analyzovat problém ortogonalizace a návrh co nejoptimálnějšího vlastního řešení. 

\section{Rozklad termů}

Při dekompozici, jak už u procesu ortogonalizace víme, musíme rozdělit logickou funkci na nezávislé nepřekrvající se termy. Pro tento účel nám poslouží již popisovaná operace $\bigodot$.

\subsection{Postupný rozklad}
Abychom rozkladem získali vzájemně disjunktní množinu termů, musíme rozložit všechny překrývající se termy. Základní postup pro rozklad s použitím $\bigodot$ vypadá následovně: Pro logickou funkci $F$, která se skládá z množiny termů $T = \{t_{1},t_{2},t_{3},t_{4}, ...t_{n} \}$, provedeme pro každý term z $T$ operaci $\bigodot$ ze všemi ostatními termy z $T$.  

\section{Řízení rozkladu} \label{sec:rizeni_rozkladu}

Už víme, že hledáme způsob, kterým rozložíme zadanou logickou funkcí na co nejmenší počet termů. Průběh procesu dekompozice je závislý na významném parametru a tím je pořadí, ve kterém se budou termy postupně rozkládat. Jedna z nejvyužitelnějších metod, které se nabízí, jak zajistit vhodné pořadí pro rozklad, je setřízení termů. 

Je důležité termy řadit průběžně. Při běhu operace $\bigodot$ vznikají nové termy, které jsou různých vlastností a je nezbytné je porovnat a začlenit do již uspořádané sekvence termů.  
\\\\
Pro úlohu ortogonalizace logické funkce lze použít tyto řadící metody:
\begin{itemize} 
\item Seřazení podle velikosti termů
\item Seřazení termů podle počtu protnutí s ostatními termy
\item Seřazení termů podle možnosti sloučení (viz. kap \ref{sec:slozeni_termu})
\end{itemize} 

Popis jednotlivých setřízení se nachází v částech \ref{sec:sort1}, \ref{sec:sort2} a \ref{sec:sort_by_merge}.
\\\\
Každou metodu řazení můžeme navíc realizovat dvěma způsoby a to vzestupně nebo sestupně. Třídící metody lze také kombinovat - umístit více typů uspořádání za sebou (viz. kap \ref{sec:sort_seriove}).
\\\\
Jednotlivé zmiňované varianty řazení a jejich kombinace jsou v určitých případech užitečné a mohou dopomoci k dosážení optimálnějšího výsledku ortogonalizace. 


\subsection{Seřazení podle velikosti termů} \label{sec:sort1}

Kritériem řazení je v této metodě velikost termů (počtu pokrytých “1“). Výhody použití sestupného a vzestupného řazení jsou ukázány na dvou příkladech.

\paragraph{Příklad 5.1}
Logická funkce $F_{1}$ je zadaná Karnaughovou mapou (obrázek \ref{fig:exam_termsizesort_dec_1}). Výsledky rozkladu s použitím řazení podle velikosti termů jsou na obrázku \ref{fig:exam_termsizesort_dec_2}. 

\paragraph{Příklad 5.2}
Logické funkce $F_{2}$ je zadaná Karnaughovou mapou (obrázek \ref{fig:exam_termsizesort_inc_1}). Výsledky rozkladu s použitím setřízení podle velikosti termů jsou znázorněny na obrázku \ref{fig:exam_termsizesort_inc_2}.


\begin{figure}[ht]
\begin{center}
\includegraphics[width=5cm]{figures/sort/exam_termsizesort_dec_1}
\caption{Logická funkce $F_{1}$ zapsaná v Karnaughové mapě.}
\label{fig:exam_termsizesort_dec_1}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/sort/exam_termsizesort_dec_2}
\caption{Rozklad $F_{1}$ s použitím metod řazení podle velikosti termů sestupně a vzestupně. }
\label{fig:exam_termsizesort_dec_2}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5cm]{figures/sort/exam_termsizesort_inc_1}
\caption{Logická funkce $F_{2}$ zapsaná v Karnaughové mapě.}
\label{fig:exam_termsizesort_inc_1}
\end{center}
\end{figure}


\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/sort/exam_termsizesort_inc_2}
\caption{Rozklad $F_{2}$ s použitím metod řazení podle velikosti termů sestupně a vzestupně. }
\label{fig:exam_termsizesort_inc_2}
\end{center}
\end{figure}

V prvním příkladu 5.1 s logickou funkcí $F_{1}$ při rozkladu s metodou vzestupného třizení (levá Karnaughová mapa na obrázku \ref{fig:exam_termsizesort_dec_2}) malé červené termy nevhodně rozdělí velký term na izolované malé kousky termů. Na výsledku se to projeví téměř v dvojnásobném počtu termů oproti rozkladu s metodou sestupného řazení (pravá Karnaughová mapa na obrázku \ref{fig:exam_termsizesort_dec_2}). 

V druhém příkladu 5.2 s logickou funkcí $F_{2}$, která není minimalizovaná, je výhodnější rozklad s metodou vzestupného uspořádání. Červené malé termy zde plně pokrývají modrý term a tím ho zcela nahradí (obrázek.  \ref{fig:exam_termsizesort_inc_2}).

\subsection{Seřazení termů podle počtu protnutí s ostatními termy} \label{sec:sort2}

Kritériem setřízení je v této metodě počet protnutí s ostatními termy. Výhody použití sestupného a vzestupného řazení jsou ukázány na dvou příkladech.

\paragraph{Příklad 5.3}
Logická funkce $F_{3}$ zadaná Karnaughovou mapou je (obrázek \ref{fig:exam_termintsort_dec_1}). Výsledky rozkladu s použitím seřazení podle počtu protnutí s ostatními termy jsou na obrázku \ref{fig:exam_termintsort_dec_2}.

\paragraph{Příklad 5.4}
Logická funkce $F_{4}$ je zadaná Karnaughovou mapou (obrázek \ref{fig:exam_termintsort_inc_1}). Výsledky rozkladu s použitím setřízení podle počtu protnutí s ostatními termy jsou na obrázku \ref{fig:exam_termintsort_inc_2}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5cm]{figures/sort/exam_termintsort_dec_1}
\caption{Logická funkce $F_{3}$ zapsaná v Karnaughové mapě.}
\label{fig:exam_termintsort_dec_1}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/sort/exam_termintsort_dec_2}
\caption{Rozklad $F_{3}$ s použitím metod řazení podle velikosti termů sestupně a vzestupně. }
\label{fig:exam_termintsort_dec_2}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5cm]{figures/sort/exam_termintsort_inc_1}
\caption{Logická funkce $F_{4}$ zapsaná v Karnaughové mapě.}
\label{fig:exam_termintsort_inc_1}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/sort/exam_termintsort_inc_2}
\caption{Rozklad $F_{4}$ s použitím metod řazení podle počtu protnutí s ostatními termy sestupně a vzestupně. }
\label{fig:exam_termintsort_inc_2}
\end{center}
\end{figure}

První příklad 5.3 s logickou funkcí $F_{3}$ poukazuje na výhodu použití sestupného řazení (pravá Karnaughova mapa na obrázku \ref{fig:exam_termintsort_dec_2}). Nejvíce protínaný modrý term s dominantní velikostí zde vhodně rozdělí ostatní menší termy.

Ve druhém příkladu 5.4 u logické funkce $F_{4}$ se třemi stejně velikými termy vychází naopak výhodněji použití vzestupného uspořádání (levá Karnaughova mapa na obrázku \ref{fig:exam_termintsort_inc_2}), kdy nejprotínanější modrý term je rozdělen zbylými dvěmi termy.  



\subsection{Sériové použití více třídících metod} \label{sec:sort_seriove}

Odlišné řadící metody můžeme umístit sériově za sebou a tím dosáhnout dvojitého uspořádání. Můžeme tak v určitých situacích využít částečně výhody obou řazení. Použití si vysvětlíme na následujícím příkladu. 


\paragraph{Příklad 5.5} Logická funkce $f_{5}$ je zadaná pravdivostní tabulkou a Karnaughovou mapou na obrázku \ref{fig:seriove_razeni_zadani}. Termy nejdříve uspořádáme sestupným řazením podle počtu protnutí a následně setřídíme sestupným řazením podle velikosti termů. 
\\\\
Uspořádání termů v prvním kroku rozkladu je znázorněno na obrázku \ref{fig:seriove_razeni}. Sériové použití těchto dvou řazení s porovnáním s třízením podle počtu protnutí s ostatními termy lze vidět po rozkladu na obrázku \ref{fig:seriove_razeni_pr1}. 

Dominantní vliv na výsledek uspořádání má druhé řazení. První setřízení navíc uspořádá, ale ještě i ty termy, které mají stejnou velikost. 


\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/seriove_razeni_zadani}
\caption{Logická funkce $f_{5}$ zadaná pravdivostní tabulkou a Karnaughovou mapou.}
\label{fig:seriove_razeni_zadani}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=17.5cm]{figures/seriove_razeni}
\caption{Sériové použití dvou třídících metod během prvního kroku rozkladu.}
\label{fig:seriove_razeni}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/seriove_razeni_pr1}
\caption{Rozklad logické funkce $f_{5}$ s použitím sestupného seřazení podle počtu protnutí s ostatními termy - levá Karnaughová mapa, s použítím dvou sériových řadících metod za sebou - pravá Karnaughová mapa.}
\label{fig:seriove_razeni_pr1}
\end{center}
\end{figure}




\section{Složení termů} \label{sec:slozeni_termu}

\subsection{Pohlcení termů}
Zadaná logická funkce nemusí být vždy v minimalizované podobě. Termy se mohou zcela překrývat a tím být nadbytečné v procesu ortogonalizace. Jejich eliminaci nazveme pohlcení termů neboli absorpci. 

Formálně zapsáno: $t_{1}$, $t_{2}$ patří do množiny termů logické funkce $F$. Pohlcení termu $t_{1}$ nastane, když term $t_{2}$ plně pokrývá term $t_{1}$. Příklad pohlcení nadbytečných termů logické funkce je znázorněn na obrázku \ref{fig:mergeterm1}.
\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/mergeterm1}
\caption{Pohlcení nadbytečných termů. }
\label{fig:mergeterm1}
\end{center}
\end{figure}

\subsection{Sloučení termů} \label{sec:slouceni_termu}

Cíl procesu ortogonalizace není pouze rozložit logickou funkci na disjunktní termy, ale také pokusit se získat minimální počet těchto termů. Zavedeme si novou funkci, která pomáhá tento požadavek splnit, a tou je sloučení termů.
\\\\
Podmínky, které musí současně platit, pro sloučení dvou termů $t_{1}$ a $t_{2}$ jsou:
\begin{enumerate}
\item Stejná velikost termů $t_{1}$ a $t_{2}$.
\item Termy $t_{1}$ a $t_{2}$ se liší v polaritě jedné proměnné.      
\end{enumerate} $ $ \\
Možnost sloučení termů nastává ve dvou případech když:
\begin{enumerate}
\item Procesem ortogonalizace vznikají nové termy, které lze spojit s ostatními termy.
\item Zadaná logická funkce není minimalizovaná.   
\end{enumerate} $ $ \\
Příklad sloučení dvou termů po procesu ortogonalizace je znázorněno na obrázku \ref{fig:mergeterm2}. Modré termy rozdělí červené termy na mintermy a ty se poté spojí. 

\begin{figure}[ht]
\begin{center}
\includegraphics[width=16.0cm]{figures/mergeterm2}
\caption{Logická funkce, její ortogonalizovaná podoba a její tvar po sloučení dvou termů. }
\label{fig:mergeterm2}
\end{center}
\end{figure}

$\\$ 
Sloučení termů lze efektivně použít ve dvou variantách:
\begin{itemize}
\item Dopředná - sloučení vybraného zpracovávaného termu s ostatními ještě neortogonalními termy.
\item Zpětná - sloučení vybraného zpracovávaného termu s již ortogonálními termy.
\end{itemize}$\\$
 
\subsection{Seřazení termů podle počtu možností sloučení} \label{sec:sort_by_merge}
Na funkci spojení termů můžeme postavit další druh řazení pořadí termů během procesu ortogonalizace. Termy se uspořádají podle statistiky, kde kritériem je z kolika možnými sousedy se mohou eventuálně sloučit. Toto řazení může být výhodné při zpracování logické funkce z malými termy, především mintermy.

Využití tohoto řazení je znázorněno na následujících ilustracích. Na obrázku \ref{fig:mergesort1} je proveden proces ortogonalizace bez setřízení, na obrázku \ref{fig:mergesort2} s metodou seřazení termů podle počtu možností sloučení. Červenou barvou jsou označeny termy, které nemají možnost spojení s jiným termem, zelenou barvou termy, které mají jednu možnost spojení s jiným termem a fialovou barvou je označen výsledek. 

\begin{figure}[ht]
\begin{center}
\includegraphics[width=11.8cm]{figures/mergesort1}
\caption{Logická funkce a jeji ortogonalizovaná podoba bez použití seřazení termů podle počtu možností sloučení.}
\label{fig:mergesort1}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=16.0cm]{figures/mergesort2}
\caption{Logická funkce, jeji ortogonalizovaná podoba a podoba s použitím ortogonalizace s řazením termů podle počtu možností sloučení.}
\label{fig:mergesort2}
\end{center}
\end{figure}

\section{Předzpracování vstupního seznamu termů} \label{sec:nastaveni_vystupu_uvod}
\subsection{Nastavení výstupů termů} \label{sec:nastaveni_vystupu}
Jak již víme, každý zpracovávaný term logické funkce ve formátu PLA má dvě části. Vstupní část určující vstupní proměnné funkce a výstupní část určující zda term patří do ONset nebo OFFset množiny. 

Zaměříme se teď na termy, které nemají ve výstupní části definovány hodnoty (obsahují výstupní hodnoty, které jsou nastaveny na "-"). Můžeme si u nich vybrat, zda je překlopíme do ONsetu nebo OFFsetu. Jak ale poznáme to, jak termy správně nastavit? V tomto projektu nedostaneme odpověď na tuto otázku. Výzkum optimálního nastavení neurčených hodnot na výstupu při procesu ortogonalizace je problém, který přesahuje rozsah této diplomové práce. 
\\\\
Existuje ale specifický případ, kdy je nevyhnutelné udělat rozhodnutí, jak se k těmto termům postavit. A to tehdy, když výstup termu není určen žádnou ONset hodnotou. Tento term z pohledu definice logické funkce je zanedbatelný a lze jej vynechat.

\subsection{Minimalizace termů} \label{sec:predzpracovani_espresso}

Před procesem ortogonalizace se nabízí možnost zkusit vstupní termy minimalizovat. Pro tuto funkci lze použít např. osvědčený nástroj Espresso [13].  

Přinese tento krok po rozkladu optimálnější ortogonalizované řešení? Výsledek tohoto experimentu není zřejmý. Zda bude tato možnost prospěšná, určí až testy (viz. kap \ref{sec:testovani}).


\section{Návrh algoritmu}
Záměrem této části je navrhnout základní strukturu algoritmu pro ortogonalizaci logické funkce. 


\subsection{Schéma algoritmu}

Schéma koncepce algoritmu je znázorněna na obrázku \ref{fig:algorithm1}. Algoritmus je rozdělen do pěti fází: A, B, C, D, E. 
  
\begin{figure}[ht]
\begin{center}
\includegraphics[width=16.3cm]{figures/algorithm1}
\caption{Schéma základní koncepce algoritmu ortogonalizace logické funkce}
\label{fig:algorithm1}
\end{center}
\end{figure}

\subsection{Popis fází algoritmu}



\begin{description}
\item [] \textbf{A - 1. fáze}
Načte se logická funkce z PLA souboru a uloží se do seznamu termů. Dále se provede úvodní předzpracování tohoto seznamu (viz. kap \ref{sec:nastaveni_vystupu_uvod}). V dalším kroku se spustí cyklus, který probíhá tak dlouho, dokud všechny termy nebudou vzájemně ortogonální. 
\item [] \textbf{B - 2. fáze}
V těle cyklu se provede setřízení termů (viz. kap \ref{sec:rizeni_rozkladu}). Vybere se první term z množiny nezpracovaných termů $t_{f}$. Pomocí vnořeného cyklu se postupně prochází všechny nezpracované termy. 
\item [] \textbf{C - 3. fáze}
Na každém aktuálně procházeném termu $t_{t}$ se nejprve zkusí vzájemná absorpce s $t_{f}$ a poté možnost slučitelnosti s $t_{f}$ (viz. kap \ref{sec:slozeni_termu}). Nedojde-li k pohlcení ani k sloučení provede se operace $t_{f} \bigodot t_{t}$. 
\item [] \textbf{D - 4. fáze}
Po ukončení vnořeného cyklu se nově ortogonální term $t_{f}$ zkusí spojit pomocí metody zpětného sloučení (viz. kap \ref{sec:slouceni_termu}) s předešlými již hotovými termy. Nedojde-li ke sloučení, term se uloží na poslední pozici do seznamu hotových termů. V dalším kroku se aktualizuje množina nezpracovaných termů, odebráním zpracovaného termu $t_{f}$ a přidáním nových termů vzniklých po operaci $\bigodot$ s aktuálním termem $t_{f}$. 

\item [] \textbf{E - 5. fáze}
Po dokončení procesu ortogonalizace se výsledek uloží do nového PLA souboru.   
\end{description}





%*****************************************************************************
\chapter{Realizace řešení}

\section{Programové vybavení pro implementaci algoritmu}


Nástroj ortogonalizace logické funkce staví na programu BOOM (viz. kap \ref{sec:boom}), který je vyvíjen v programovacím jazyce C++. Výhody tohoto jazyka jsou rychlost, výkonnost, podpora objektů a snadná platformová přenositelnost. Vytvářený algoritmus má vysoké nároky na paměť, proto je volba C++ pro implementaci vhodná. Je to navíc také součásti zadání.  

Pro napsání zdrojových kódů a odladění programu bylo zvoleno prostředí DevCpp verze 4.9.9.2. pod operačním systémem Microsoft Windows XP.


\section{Pseudokód zjednodušeného algoritmu}
(1) $\;\;\;\;\;\;\;\;$ $w$ $\leftarrow$ LoadPLA()\\
(2) $\;\;\;\;\;\;\;\;$ $w$ $\leftarrow$ EliminateUndefined($w$) nebo $w$ $\leftarrow$ EspressoMinimization($w$)\\
(3) $\;\;\;\;\;\;\;\;$ $t_{1}$ $\leftarrow$ první term v seznamu $w$\\
(4) $\;\;\;\;\;\;\;\;$ While ($t_{1}$ není poslední term v seznamu $w$) proveď\\
(5) $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ Seřadit seznam termů $w$ \\
(6) $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $t_{2}$ $\leftarrow$ následující term v seznamu za $t_{1}$\\
(7) $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ While ($t_{2}$ není poslední term v seznamu $w$) proveď\\
(8) $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $t_{3}$ $\leftarrow$ MergeNeighbors($t_{1}$, $t_{2}$)\\
(9) $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ If ( nedošlo k sloučení $t_{1}$ a $t_{2}$) proveď\\
(10)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $z$ $\leftarrow$ TermDisjointSharp($t_{1}$, $t_{2}$)\\
(11)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ If (došlo k sloučení termů $t_{1}$ a $t_{2}$) proveď\\
(12)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $t_{2}$ $\leftarrow$ následující term za $t_{1}$\\
(13)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $t_{1}$ $\leftarrow$ $t_{3}$\\
(14)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ Vyprázdnit seznam termů $z$\\
(15)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $t_{2}$ $\leftarrow$ následující term v seznamu, který je za $t_{2}$\\
(16)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ Přidání $t_{1}$ do seznamu \textit{výsledek}\\
(17)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ \textit{výsledek} $\leftarrow$ BackMerge(\textit{výsledek})\\
(18)$\;\;\;\;\;\;\;\;$ $\;\;\;\;\;\;\;\;$ $t_{1}$ $\leftarrow$ následující term v seznamu, který je za $t_{1}$\\
(19)$\;\;\;\;\;\;\;\;$ SavePLA(\textit{výsledek})\\
\\\\
Popis použitých příkazů:\\

\textit{LoadPLA} $ $ $ $  $ $ $ $ Načtení logické funkce ze souboru formátu PLA

\textit{SavePLA} $ $ $ $  $ $ $ $ Uložení logické funkce do souboru formátu PLA

\textit{TermDisjointSharp} $ $ $ $  $ $ $ $ Operace Disjoint sharp mezi dvěmi termy

\textit{MergeNeighbors} $ $ $ $  $ $ $ $ Spojení dvou slučitelných termů

\textit{BackMerge} $ $ $ $  $ $ $ $ Zpětné spojení dvou slučitelných termů

\textit{EliminateUndefined} $ $ $ $  $ $ $ $ Eliminace termů nepatřící do ONsetu 

\textit{EspressoMinimization} $ $ $ $  $ $ $ $ Minimalizace termů pomocí Espressa


  
  
\section{Proces dekompozice termů}
Základní programovou konstrukcí rozkladu jsou dva vnořené cykly. V prvním se postupně prochází aktualizovaný seznam nezpracovaných termů (fáze B) a v druhém cyklu se provádí samotný rozklad termů (fáze C). Dekompozici termů provádí funkce TermDisjointSharp. 

\subsection{Funkce TermDisjointSharp}
Ústřední funkce celé ortogonalizace. Vstupem jsou dva termy $t_{1}$ a $t_{2}$, výstupem je seznam termů.
\\\\
Funkce je rozdělena na tyto 3 části:

\begin{enumerate} 
\item Otestuje se, zda se termy $t_{1}$ a $t_{2}$ protínají. Jestliže ne, proces se ukončí, rozklad není nutný. Test protnutí se provede pomocí funkce Intersects [17].
\item Provedení operace $\bigodot$ mezi termy $t_{1}$ a $t_{2}$, výsledné termy jsou uloženy do nového seznamu. Rozložení probíhá v cyklu, prochází se po bitech vstupní proměnné termů $t_{1}$ a $t_{2}$. Když na pozici vstupní hodnoty termu $t_{1}$ je DCset a na pozici $t_{2}$ logická "0" nebo "1" vytvoří se nový term, který se nastaví podle předurčených podmínek (viz. obrázek \ref{fig:source1}).
\item Vytvoření doplňujícího termu. Term vznikne za předpokladu, že term $t_{2}$ má ve výstupní části alespoň jednu "1" na pozici, kde ho term $t_{2}$ nemá.  
\end{enumerate} 

\begin{figure}[ht]
\begin{center}
\includegraphics[width=9.1cm]{figures/source1}
\caption{Výpis zdrojového kódu operace $\bigodot$ mezi termy $t_{1}$ a $t_{2}$ (2. část funkce TermDisjointSharp)}
\label{fig:source1}
\end{center}
\end{figure}

\section{Setřízení termů}

Uspořádání termů probíhá ve fázi B. Vstupem a výstupem je datová struktura PLA.
\\\\
Proces setřízení je rozdělen na 2 části:

\begin{enumerate}
\item Podle typu zadaného třídícího kriteria se vytvoří statistika požadovaných vlastností jednotlivých termů, která se uloží do pole. Pořadí položek v poli odpovídá posloupnosti pořadí termů v seznamu.  
\item Postupným procházením seznamu termů, který se porovnává se statistikou, se vytváří nový seznam setřízených termů. Vzestupné a sestupné třízení termů závisí na tom, zda se jednotlivé údaje ze statistiky porovnávají od největších hodnot nebo od nejmenších.
\end{enumerate} $ $\\
Vytvoření statistiky vlastností termů v první části je závislá na metodě řazení. Jsou to tyto implementace: 
\begin{itemize}  
\item Setřízení podle velikosti termů (funkce SizeSortInc a SizeSortDec). Sečte se počet DCsetů ve vstupní části, suma těchto hodnot = velikost daného termu. 
\item Setřízení podle počtu protnutí s ostatními termy (funkce IntersectionSortInc a IntersectionSortDec). Využívá funkci Intersects [17] pro nalezení společného průniku mezi dvěmi termy. 
\item Setřízení termů podle počtu možností sloučení (funkce SortByMergeInc a SortByMergeDec). Test slučitelnosti termů je postaven na podmínce odlišnosti právě jednoho literálu "1" - "0" nebo "0" - "1".
\end{itemize} 

\section{Sloučení termů a absorbce}

Dopředné i zpětné složení slučitelných termů je postaveno na funkci MergeNeighbors [17]. Funkce MergeNeighbors plně zastoupí také i funkci pro absorpci termů, kterou není proto nutné samostatně implementovat.  

Funkce zpětného sloučení BackMerge je popsána v následujícím odstavci. 
\\\\

\subsection{Funkce BackMerge} \label{sec:backmerge}
Vstupem a výstupem je datová struktura PLA. Funkce v cyklu testuje možnost spojení posledního vloženého termu v seznamu s předešlými. Po úspěšném sloučení se term uloží na poslední pozici v seznamu a cyklus se opakuje od začátku. Pro sloučení dvou termů se využívá obdobně funkce MergeNeighbors.




\section{Eliminace termů nepatřící do ONsetu} \label{sec:realizace_nastaveni_hodnot}

Termy, které nemají výstup definován žádnou hodnotou nastavenou na "1", odstraní funkce EliminateUndefined. Funkce postupně prochází seznam vstupních termů, termy nepatřící do ONsetu vynechá a ostatní uloží do nového seznamu.



\section{Minimalizace vstupních termů pomocí Espressa} \label{sec:predzpracovani_espresso}

Program Espresso je v algoritmu ortogonalizace logické funkce spuštěn externě pomocí příkazu system().



%*****************************************************************************
\chapter{Testování} \label{sec:testovani}

V této kapitole se zabýváme experimentálním vyhodnocením navrženého algoritmu, jeho jednotlivých variant a srovnání s cizími dostupnými implementacemi. 

\section{Označení testovaných algoritmů}
Vyvíjený algoritmus ortogonalizace logické funkce je implementován v 12 testovacích verzích. 
\\\\
Varianty základního navrženého alogritmu postavené na rozdílném průbežném řazaní termů během procesu ortogonalizace (viz. kap \ref{sec:rizeni_rozkladu}) jsou:
\begin{description}
\item \textit{\textbf{WithoutSort}} $ $ $ $ Bez řazení.
\item \textit{\textbf{SizeSortInc}} $ $ $ $ Podle velikosti termů (vzestupně).
\item \textit{\textbf{SizeSortDec}} $ $ $ $ Podle velikosti termů (sestupně).
\item \textit{\textbf{IntersectionSortInc}} $ $ $ $ Podle počtu protnutí s ostatními termy (vzestupně).
\item \textit{\textbf{IntersectionSortDec}} $ $ $ $ Podle počtu protnutí s ostatními termy (sestupně).

\item \textit{\textbf{SizeIntersectionSortInc}} $ $ $ $ Podle počtu protnutí s ostatními termy (vzestupně) a podle velikosti termů (sestupně).
\item \textit{\textbf{SizeIntersectionSortDec}} $ $ $ $ Podle počtu protnutí s ostatními termy (sestupně) a podle velikosti termů (sestupně).

\item \textit{\textbf{SortByMergeInc}} $ $ $ $ Podle počtu možností sloučení s ostatními termy (vzestupně) .
\item \textit{\textbf{SortByMergeDec}} $ $ $ $ Podle počtu možností sloučení s ostatními termy (sestupně).
\end{description}
$ $
\newline \newline \newline \newline \newline \newline
Rozšířené verze navrženého algoritmu:
\begin{description}
\item \textit{\textbf{A\_BackMerge}} $ $ $ $ Varianta algoritmu \textit{SizeSortDec} s použitím zpětného sloučení termů (viz. kap \ref{sec:slouceni_termu}).
\item \textit{\textbf{A\_EliminateUndefined}} $ $ $ $ Varianta algoritmu \textit{A\_BackMerge} s eliminací termů, které nemají určen výstup ani jednou hodnotou definovanou na ONset (viz.kap \ref{sec:nastaveni_vystupu}). 
\item \textit{\textbf{A\_Espresso}} $ $ $ $ Varianta algoritmu \textit{A\_EliminateUndefined} s minimalizací vstupních termů pomocí Espressa \ref{sec:predzpracovani_espresso}) .
\end{description}$\\$
Cizí testované algoritmy:
\begin{description}
\item[] \textbf{Espresso -Ddisjoint} $ $ $ $ $ $ Podprogram Espressa pro ortogonalizaci logické funkce (viz. kap \ref{sec:Espresso_Disjoint}).
\item[] \textbf{DSOP} $ $ $ $ $ $ Implementace heuristického algoritmu pro ortogonalizaci logické funkce (viz. kap \ref{sec:DSOP_1}).
\end{description}


\section{Postup testování}

Implementovaný nástroj pro ortogonalizaci logické funkce byl testovaný na MCNC benchmarkcích [7], sadě testovacích souborů formátu PLA. 

Všechny testy byly prováděny na notebooku Lenovo 3000 N100 s procesorem Intel Centrino Duo 1.8 GHz, s operační pamětí 1024MB RAM a pevným diskem s rychlostí 5400ot/min. Programy pro testování byly kompilovány v DevCpp 4.9.9.2. pod systémem Microsoft Windows XP SP2.
\\\\
Byly provedeny tyto dva typy testů:
\begin{itemize}
 \item Test funkčnosti - testování správné činnosti algoritmu.
 \item Srovnavací test - porovnání výsledků algoritmů 
\end{itemize} 


\section{Test funkčnosti}
Záměrem testu funkčnosti bylo ověřit, zda výsledek algoritmu je ortogonální logická funkce (viz. kap \ref{sec:ortogonalizace_definice}). Pro testování byly použity tyto dva nástroje: 
\begin{itemize}
\item Podprogram Espressa [13] spouštějící se s parametrem "Dverify" testující, zda nová ortogonalizovaná podoba logické funkce je ekvivalentní s původní logickou funkcí ze které vychází.
\item Program Ortho [15] spouštějící se s parametrem "Check" testující, zda termy v logické funkci jsou vzájemně disjunktní.
\end{itemize}

V následujících srovnávacích testech byly všechny výsledky ověřeny testováním funkčnosti. Každá použitá varianta algoritmu prošla tímto testem úspěšně a jejich výsledek byl ortogonální.


\section{Srovnávací testy} \label{sec:srovnavaci_test}

Při testech byly porovnány tyto experimentální měření:
\begin{itemize}
\item srovnání metod průběžného uspořádání termů
\item srovnání časů výpočtů jednotlivých algoritmů
\item srovnání nejefektivnějších variant navrženého algoritmu s ostatními konkurenčními implementacemi
\end{itemize}

Výsledky měření se nachází v přílohách \ref{sec:test_one}, \ref{sec:test_two}, \ref{sec:test_three} a \ref{sec:test_four}. Symbol "-", který se nachází v některých buňkách tabulky znázorňuje, že ani po několika hodinách algoritmus nespočítal výsledek.



\section{Porovnání průběžného uspořádaní termů} \label{sec:test_razeni}

Byly provedeny testy řadících metod \textit{WithoutSort}, \textit{SizeSortInc}, \textit{SizeSortDec}, \textit{IntersectionSortInc}, \textit{IntersectionSortDec}, \textit{SizeIntersectionSortInc}, \textit{SizeIntersectionSortDec}, \textit{SortByMergeInc} a \textit{SortByMergeDec} na 101 testovacích úlohách. Naměřené hodnoty se nachází v příloze \ref{sec:test_one}. Čas, za který jednotlivé varianty algoritmu vypočítaly výsledek jsou v příloze \ref{sec:test_two}. 

\subsection{Porovnání výsledků metod řazení}

Po sečtení všech hodnot výsledků získaných z testovaných benchmarků můžeme metody seřadit od nejlepší:
\begin{enumerate}
\item 14300 termů $ $ $ $ \textit{SizeSortDec}  
\item 14363 termů $ $ $ $ \textit{SizeIntersectionSortInc}
\item 14360 termů $ $ $ $ \textit{SizeIntersectionSortInc} 
\item 16266 termů $ $ $ $ \textit{IntersectionSortDec}
\item 20127 termů $ $ $ $ \textit{WithoutSort}
\item 21925 termů $ $ $ $ \textit{SortByMergeDec}
\item 44236 termů $ $ $ $ \textit{IntersectionSortInc}
\end{enumerate}$\\$
Metody, které nedokázaly spočítat všechny testované úlohy:
\begin{itemize}
\item 22255 termů  $ $ $ $ \textit{SizeSortInc}
\item 15945 termů  $ $ $ $ \textit{SortByMergeInc}
\end{itemize}


\subsection{Porovnání času metod řazení}


Po sečtení všech výsledných časů získaných z testovaných benchmarků můžeme metody seřadit od nejlepší:
\begin{enumerate}
\item 110 s  $ $ $ $ $ $ $ $\textit{WithoutSort}
\item 241 s  $ $ $ $ $ $ $ $\textit{SizeSortDec} 
\item 1011 s  $ $ $ $ \textit{SizeIntersectionSortInc}
\item 1069 s  $ $ $ $ \textit{SizeIntersectionSortInc} 
\item 1418 s  $ $ $ $ \textit{IntersectionSortDec}
\item 6884 s  $ $ $ $ \textit{SortByMergeDec}
\item 9707 s  $ $ $ $ \textit{IntersectionSortInc}
\end{enumerate}$\\$
Metody, které nedokázaly spočítat všechny testované úlohy:
\begin{itemize}
\item 1051 s  $ $ $ $ \textit{SizeSortInc} 
\item 2875 s  $ $ $ $ \textit{SortByMergeInc}  
\end{itemize}$\\$
Pozn. časy v tomto meření mají pouze orientační charakter.


\subsection{Srovnání algoritmu \textit{WithoutSort} s algoritmy s průběžným řazením}
Z měření je patrné, že vhodná řazení dopomáhají získat ve výsledcích ortogonalizace menší počet termů než implementace bez řazení, což potvrdilo základní předpoklad použití třídících metod. 

Dalším důležitým poznatkem, který můžeme z toho měření odvodit je, že lepším řešením je použití algoritmu bez řazení \textit{WithoutSort} než s použitím nevhodně navržených třídících metod, např. jako jsou \textit{SizeSortInc}, \textit{SizeIntersectionSortInc}, \textit{SortByMergeInc} a \textit{SortByMergeDec}. 



\subsection{Srovnání řazení \textit{SizeSortInc} a \textit{SizeSortDec}}

Algoritmus s použitím řazení \textit{SizeSortInc} generoval oproti řešení \textit{SizeSortDec} téměř dvojnásobný počet termů v čtyřnásobném čase.
Test tedy prokázal, že užitečnějším řešením je termy řadit sestupným způsobem, což znamená logickou funkci rozkládat od největších termů po nejmenší. Je nutno také zmínit, že algoritmus s \textit{SizeSortInc} uspořádáním nedokázal některé logické funkce z testovacího benchmarku spočítat v přijatelném čase v délce několika hodin.

\subsection{Srovnání řazení \textit{IntersectionSortInc}  a \textit{IntersectionSortDec} }
Porovnání algoritmu podle počtu protnutí s ostatními termy ukázalo, že je jednoznačně výhodnější řešení využívající řazení \textit{IntersectionSortDec} oproti \textit{IntersectionSortInc} . Metoda \textit{IntersectionSortInc}  ve výsledku vytvořila více než dvojnásobný počet termů než \textit{IntersectionSortDec}. Tzn. prokázalo se, že je výhodnější začít dekomponovat logickou funkci od co nejvíce protínatějších termů, které svým rozkladem ovlivní největší počet ostatních termů. Řešení \textit{IntersectionSortDec} bylo také oproti řešení \textit{IntersectionSortInc}  podstatně rychlejší (téměř šestkrát). 


\subsection{Srovnání řazení \textit{SizeSortDec} se sériovým řazením \textit{SizeIntersectionSortInc} a \textit{SizeIntersectionSortDec}}

Podle provedených testů jsou tyto tři varianty uspořádání nejúčinnější. Při sériovém řazení dvou třídících metod podle počtu protnutí s ostatními termy a sestupného uspořádání podle velikosti termů, se intuitivně dalo předpokládat, že toto řešení by mohlo dopadnout lépe než samotné řazení \textit{SizeSortDec}  z kterého vychází. Výsledek je překvapivý, protože jejich "síla" je vzájemně srovnatelná. Při porovnání času je implementace \textit{SizeSortDec}  oproti  \textit{SizeIntersectionSortInc}, \textit{SizeIntersectionSortDec} téměr čtyřikrát rychlejší.
\\\\  
Během tohoto testu se neprokázalo viditelné zlepšení, které by sériové řazení třídících metod mohlo přinést. 



\subsection{Srovnání řazení \textit{SortByMergeInc} a \textit{SortByMergeDec} s metodou \textit{WithoutSort} }

\textit{SortByMergeInc} a \textit{SortByMergeDec} jsou třídící metody, které obě ve výsledku zaostávají za variantou algoritmu bez použití řazení. Test tedy ukázal, že jejich použití není v praxi příliš užitečné. 


\subsection{Zhodnocení testování řadících metod algoritmu}
Řazení \textit{SizeSortDec} můžeme z hlediska kvality řešení a časové rychlosti definitivně považovat za nejefektivnější třídící metodu algoritmu, která byla odzkoušena. Na tomto algoritmu, proto stavíme následující vylepšené varianty ortogonalizace \textit{A\_BackMerge}, \textit{A\_EliminateUndefined} a \textit{A\_Espresso}.   


\section{Porovnání algoritmu s cizími implementacemi} \label{sec:test_razeni}


Vybrané nejsilnější varianty vytvářeného algoritmu \textit{A\_BackMerge}, \textit{A\_Eli-minateUndefined} a \textit{A\_Espresso} jsou v tomto testu porovnány s cizími implementacemi \textit{Espresso -Ddisjoint} a \textit{DSOP} na 86 testovacích úlohách. Pro srovnání je do testování zahrnuta i metoda algoritmu \textit{SizeSortDec}. Naměřené hodnoty se nachází v příloze \ref{sec:test_three}. Čas, za který jednotlivé varianty algoritmu vypočítaly výsledek se nachází v příloze \ref{sec:test_four}. 
\\\\


\subsection{Porovnání výsledků algoritmů}

Po sečtení všech hodnot výsledků získaných z testovaných benchmarků můžeme algoritmy seřadit od nejlepšího:
\begin{enumerate}
\item 11394 termů $ $ $ $ \textit{A\_Espresso} 
\item 11613 termů $ $ $ $ \textit{A\_EliminateUndefined}
\item 12490 termů $ $ $ $ \textit{A\_BackMerge} 
\item 13702 termů $ $ $ $ \textit{DSOP} 
\item 13799 termů $ $ $ $ \textit{SizeSortDec} 
\item 24901 termů $ $ $ $ \textit{Espresso -Ddisjoint}
\end{enumerate}$\\$




 
\subsection{Porovnání časů algoritmů}


Po sečtení všech výsledných časů získaných z testovaných benchmarků můžeme algoritmy seřadit od nejlepšího:
\begin{enumerate}
\item 7,1 s $ $ $ $ $ $ $ $ $ $ \textit{DSOP}
\item 25,2 s $ $ $ $ $ $ $ $\textit{Espresso -Ddisjoint} 
\item 253,3 s $ $ $ $ \textit{A\_Espresso} 
\item 260,7 s $ $ $ $ \textit{SizeSortDec} 
\item 302,2 s $ $ $ $ \textit{A\_EliminateUndefined}
\item 339,1 s $ $ $ $ \textit{A\_BackMerge} 
\end{enumerate}$\\$

\subsection{Srovnání algoritmů \textit{SizeSortDec}, \textit{A\_BackMerge}, \textit{A\_EliminateUnde-fined} a \textit{A\_Espresso} }
Algoritmus se zpětným sloučením \textit{A\_BackMerge}  přináší ve výsledcích kladnou odezvu, kdy můžeme vidět zdokonalení oproti metodě \textit{SizeSortDec} z které vychází. 

Algoritmus \textit{A\_EliminateUndefined}   s eliminací termů s výstupem neurčeným ani jednou hodnotou definovanou na ONset, přináší očekávané vylepšení, které je zřetelné už na první pohled hned ze zadání testovaných úloh.

Algoritmus \textit{A\_Espresso}  přináší díky novému přístupu značně odlišné výsledky oproti předchozím navrženým variantám. Lze vypozorovat, že minimalizace logické funkce před orotogonalizací může být v některých případech prospěšná, někdy však může navést algoritmus špatným směrem a být tak ke škodě.

V testech byl algoritmus \textit{A\_EliminateUndefined} lepší v 54\% úloh než \textit{A\_Espresso}. Při konečné sumě všech výsledných termů byl ale naopak algoritmus \textit{A\_Espresso}  úspěšnější než \textit{A\_EliminateUndefined} .
\\\\

\subsection{Srovnání algoritmu \textit{Espresso -Ddisjoint} s ostatními implementacemi}
\textit{Espresso -Ddisjoint} je jednoduchý algoritmus, který podle testů očekávaně zaostává za ostatními implementacemi.  

\subsection{Srovnání algoritmů \textit{A\_EliminateUndefined} , \textit{A\_Espresso}   a \textit{DSOP}} \label{ref:srovnani_s_DSOP}
Algoritmus \textit{A\_EliminateUndefined} s porovnáním s \textit{DSOP} byl u 60\% testovaných úloh lepší. Algoritmus \textit{A\_Espresso}  byl ve srovnání s \textit{DSOP} také lepší a to v 54\% úloh.

V čem se skrývá výhoda \textit{A\_EliminateUndefined} a \textit{A\_Espresso} oproti \textit{DSOP}? V první řadě to může být důsledek použité metody průběžného řazení termů. \textit{DSOP} používá setřízení termů podle počtu protnutí s ostatními termy, oproti tomu \textit{A\_EliminateUndefined} a \textit{A\_Espresso} jsou postaveny na uspořádání termů podle jejich velikosti, které se osvědčily v testech řazení lépe. Dalším důvodem, který může mít vliv na výsledek, jsou metody dopředného a zpětného sloučení termů které, \textit{A\_EliminateUndefined}  a \textit{A\_Espresso}   využívají.    
\\\\
Srovnávací testy ukázaly, že \textit{A\_EliminateUndefined} a \textit{A\_Espresso} jsou nejúčinnější navržené algoritmy této práce.


%*****************************************************************************
%*****************************************************************************
%*****************************************************************************
\chapter{Závěr}


Hlavním záměrem projektu bylo seznámení se stávajícími konkurenčními nástroji pro ortogonalizaci logické funkce, návrh a implementace vlastního algoritmu, jeho otestování a srovnání s konkurenčními nástroji. Je možné konstatovat, že všechny tyto cíle diplomové práce byly úspěšně splněny.
\\\\
Vývoj projektu byl rozdělen do čtyř částí. V první fázi byly formulovány požadavky na zadání práce a byly připomenuty základní definice a termíny z oblasti logických funkcí. Obsahem druhé fáze byl analytický rozbor procesu ortogonalizace, seznámení se s existujícími dostupnými nástroji a návrh vlastního algoritmu. V třetí fázi byla provedena programová realizace algoritmu, při které byl vytvořen funkční nástroj pro ortogonalizaci logické funkce. Ve čtvrté fázi bylo provedeno testování navržené implementace, jejich jednotlivých variant a srovnání s konkurenčními algoritmy. 
\\\\
Nástroj na ortogonalizaci byl implementován v programovacím jazyce C++ a je postaven na programu BOOM. Základním kamenem algoritmu je operace Disjoint sharp, která rozloží logickou funkci na disjunktní termy. Výsledky testu funkčnosti prokázaly, že vytvořený nástroj pracuje správně a dokáže zadanou logickou funkci spolehlivě ortogonalizovat. Experimentálním testováním bylo potvrzeno, že vhodné uspořádání termů během procesu ortogonalizace má zásadní vliv na výsledný počet termů. Z třídících metod se nejvíce osvědčilo průběžné sestupné řazení termů podle velikosti. Další podstatnou funkcí, která dokáže vylepšit výsledek algoritmu, je možnost složení slučitelných termů při rozkladu. Algoritmus s minimalizací vstupních termů pomocí Espressa přinesl v testech zlepšení ve výsledku ortogonalizace, avšak u některých logických funkcí byl naopak k neprospěchu.

Na testovaných úlohách z MCNC benchmarků vytvořený algoritmus generoval lepší výsledky než dostupné konkurenční implementace DSOP a Espresso s podprogramem pro ortogonalizaci. 
\\\\
Budoucí zdokonalování algoritmu je v pokračování hledání nejvýhodnější dekompozice logické funkce, která ji rozloží na co nejmenší počet termů. Případný vývoj vidím v heuristickém rozhodování nastavení vstupních termů logické funkce před ortogonalizací na místech, kde nemají termy ve výstupní hodnotě definovaný ONset ani OFFset. Správná konfigurace těchto hodnot může pomoci během procesu rozkladu dosáhnout výhodnějšího výsledku. Druhou oblastí, na které by se dalo dál pracovat, je spojení dílčích kroků ortogonalizace s vhodnými algoritmy na minimalizaci. 
\\\\
Zdrojové kódy, jejich komentáře, testovací úlohy a další náležitosti týkající se této práce se nachází na přiloženém CD. Jeho struktura je popsána v příloze \ref{sec:priloha_CD}.



%*****************************************************************************
\chapter{Literatura a použité zdroje}


\begin{description}

\item[][1] $ $ $ $N. Song, M. Perkowski, Minimization of Exclusive Sum of Products Expressions for Multi-Output Multiple-Valued Input, IEEE Trans. on CAD, Vol. 15, 1996, pp. 385-395.

\item[][2] $ $ $ $ G. McGuire, Spectra of Boolean Functions, School of Mathematical Sciences University College Dublin, 2007

\item[][3] $ $ $ $J. Bílek, Minimalizace neúplně určených logických funkcí pomocí modifikovaných binárních rozhodovacích algoritmů, Diplomová práce, FEL ČVUT, 2007.

\item[][4] $ $ $ $ P. Černý, Skupinová minimalizace neúplně určených logických funkcí pomocí modifikovaných rozhodovacích diagramů, Diplomová práce, FEL ČVUT, 2008.

\item[][5] $ $ $ $ R. K. Brayton, G. D. Hachtel, C. T. McMullen, A. L. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, 1984.

\item[][6] $ $ $ $ L. Shivakumaraiah, M. A. Thornton, Computation of disjoint cube representations using a maximal binate variable heuristic, System Theory, 2002.

\item[][7] $ $ $ $ S. Yang, Synthesis on Optimization Benchmarks, User guide, Microelectronic Center, 1991.
\item[][8] $ $ $ $ R M. Karp, Reducibility among combinatorial problems, Plenum, 1972, pp. 85–103.

\item[][9] $ $ $ $ M. Miklánek, Úprava minimalizačního nástroje ESPRESSO, Bakalářská práce, FEL ČVUT, 2008.

  \item[][10] $ $ $ $B. Kernighan, D. Ritchie, The C Programming Language, Prentice Hall, 1978.
  \item[][11]$\;$ $ $A. Bernasconi, V. Ciriani, F. Luccio, L. Pagli, A New Heuristic for
DSOP Minimization, Proc. 8th Int. Workshop on Boolean Problems, Freiberg, Germany, 18.-19.9.2008, pp. 169-174.

  \item[][12] $ $ $ $J. Rybička, Latex pro začátečníky, 3. vydání, Konvoj, 2003.

  \item[][13] $ $ $ $Espresso - list of the command, \\ http://www.ece.duke.edu/\~dwyer/courses/ece52/espresso.1.html
  \item[][14] $ $ $ $ Wikipedia - Orthogonalization, http://en.wikipedia.org/wiki/Orthogonalization
  \item[][15] $ $ $ $ Nástroj Ortho, http://cs.felk.cvut.cz/$\sim$fiserp
  \item[][16] $ $ $ $ Formát PLA, http://service.felk.cvut.cz/vlsi/prj/BOOM/pla{\_}c.html
  \item[][17] $ $ $ $ BOOM - the Boolean Minimizer, http://service.felk.cvut.cz/vlsi/prj/BOOM
  \item[][18] $ $ $ $ Wikipedia - Espresso heuristic logic minimizer,

http://en.wikipedia.org/wiki/Espresso\_heuristic\_logic\_minimizer




\end{description}

%------------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------------


\appendix
\chapter{Porovnání metod průběžného řazení termů} \label{sec:test_one}

Označení metod průběžného řazení termů:
\begin{description}
\item[] \textbf{WS} $ $ $ $ WithoutSort (bez řazení) 
\item[] \textbf{SSI} $ $ $ $ SizeSortInc (Podle velikosti termů - vzestupně)
\item[] \textbf{SSD} $ $ $ $ SizeSortDec (Podle velikosti termů - sestupně)
\item[] \textbf{ISI} $ $ $ $ IntersectionSortInc (Podle počtu protnutí s ostatními termy - vzestupně)
\item[] \textbf{ISD} $ $ $ $ IntersectionSortDec (Podle počtu protnutí s ostatními termy - sestupně)
\item[] \textbf{SISI} $ $ $ $ SizeIntersectionSortInc (Podle počtu protnutí s ostatními termy - vzestupně a podle velikosti termů - sestupně)
\item[] \textbf{SISD} $ $ $ $ SizeIntersectionSortDec (Podle počtu protnutí s ostatními termy - sestupně a podle velikosti termů - sestupně)
\item[] \textbf{MI} $ $ $ $ SortByMergeInc (Podle počtu možností sloučení s ostatními termy - vzestupně) 
\item[] \textbf{MD} $ $ $ $ SortByMergeDec (Podle počtu možností sloučení s ostatními termy - sestupně) 
\end{description}$\\$
Jednotlivé naměřené hodnoty metod algoritmů jsou v tabulce uvedeny v termech. 
\\
\begin{longtable}{|p{0.5cm}|p{2cm}|p{0.77cm}|r|r|r|r|r|r|r|r|r|}

\hline
&\textbf{PLA}&\textbf{SOP}&\textbf{WS}&\textbf{SSI}&\textbf{SSD}&\textbf{ISI}&\textbf{ISD}&\textbf{SISI}&\textbf{SISD}&\textbf{MI}&\textbf{MD}\\ \hline
1&al2.pla&103&101&109&105&101&109&105&105&109&101\\ \hline
2&alcom.pla&47&46&47&46&46&46&46&46&46&46\\ \hline
3&alu1.pla&19&23&23&19&23&19&19&19&23&23\\ \hline
4&alu2.pla&91&126&195&102&104&122&93&122&122&132\\ \hline
5&alu3.pla&72&159&254&72&199&144&72&72&159&159\\ \hline
6&apla.pla&134&100&100&100&100&100&100&100&100&100\\ \hline
7&b10.pla&138&121&122&121&121&121&121&121&121&120\\ \hline
8&b11.pla&74&31&41&31&41&30&31&31&31&33\\ \hline
9&b12.pla&431&177&698&96&292&120&74&66&188&161\\ \hline
10&b2.pla&110&127&198&111&151&134&111&111&125&127\\ \hline
11&b3.pla&234&697&2215&392&765&382&381&370&752&580\\ \hline
12&b4.pla&54&80&-&63&5826&81&116&63&80&80\\ \hline
13&b7.pla&74&31&41&31&41&30&31&31&31&33\\ \hline
14&b9.pla&123&261&530&181&301&269&181&181&275&244\\ \hline
15&bc0.pla&479&383&504&377&396&382&369&381&385&375\\ \hline
16&bca.pla&301&202&202&202&202&202&202&202&202&207\\ \hline
17&bcb.pla&299&188&188&188&188&188&188&188&187&194\\ \hline
18&bcc.pla&245&163&163&163&163&163&163&163&163&166\\ \hline
19&bcd.pla&243&149&149&149&149&149&149&149&149&156\\ \hline
20&br1.pla&34&20&20&20&20&20&20&20&20&20\\ \hline
21&br2.pla&35&19&19&19&19&19&19&19&19&19\\ \hline
22&check.pla&16&14&14&14&14&14&14&14&14&14\\ \hline
23&check2.pla&16&14&14&14&14&14&14&14&14&14\\ \hline
24&chkn.pla&153&933&-&174&3906&252&171&187&-&1009\\ \hline
25&clpl.pla&20&20&231&20&20&20&20&20&20&20\\ \hline
26&dc1.pla&15&19&20&19&19&19&19&19&19&19\\ \hline
27&dc2.pla&58&45&45&45&45&45&45&45&45&46\\ \hline
28&dist.pla&256&179&179&179&179&179&179&179&179&179\\ \hline
29&dk17.pla&93&76&76&76&76&76&76&76&76&76\\ \hline
30&dk27.pla&52&52&52&52&52&52&52&52&52&52\\ \hline
31&dk48.pla&148&142&142&142&142&142&142&142&142&142\\ \hline
32&ex1010.pla&1024&1020&1020&1020&1020&1020&1020&1020&-&1020\\ \hline
33&ex5.pla&256&179&179&179&179&179&179&179&179&182\\ \hline
34&ex7.pla&123&261&530&181&301&269&181&181&275&244\\ \hline
35&example.pla&153&933&-&174&3906&252&171&187&-&1009\\ \hline
36&exp.pla&89&74&74&74&74&74&74&74&74&74\\ \hline
37&exps.pla&196&165&165&165&166&165&166&165&167&165\\ \hline
38&f51m.pla&256&256&256&256&256&256&256&256&256&256\\ \hline
39&gary.pla&214&122&765&116&421&157&139&112&122&131\\ \hline
40&ibm.pla&173&785&2455&376&865&486&375&381&866&918\\ \hline
41&in0.pla&138&137&137&137&137&137&137&137&137&136\\ \hline
42&in1.pla&110&127&198&111&151&134&111&111&125&127\\ \hline
43&in2.pla&137&405&1640&167&683&286&165&169&479&556\\ \hline
44&in3.pla&75&253&615&121&407&133&120&121&254&276\\ \hline
45&in5.pla&62&250&502&172&455&183&176&173&268&242\\ \hline
46&in6.pla&54&80&-&63&5826&81&116&63&80&80\\ \hline
47&in7.pla&84&591&-&76&2632&352&74&93&1559&869\\ \hline
48&inc.pla&34&33&33&33&33&33&33&33&33&33\\ \hline
49&intb.pla&664&1979&5570&830&3301&1134&838&866&-&2508\\ \hline
50&luc.pla&27&42&42&29&38&30&29&29&42&42\\ \hline
51&m1.pla&32&23&23&23&23&23&23&23&23&24\\ \hline
52&m2.pla&96&64&64&64&64&64&64&64&64&67\\ \hline
53&m3.pla&128&90&90&90&90&90&90&90&90&91\\ \hline
54&m4.pla&256&165&165&165&165&165&165&165&165&164\\ \hline
55&mark1.pla&129&128&143&128&128&128&128&128&128&128\\ \hline
56&max1024.pla&1024&569&569&569&569&569&569&569&568&580\\ \hline
57&max128.pla&128&89&89&89&89&89&89&89&89&89\\ \hline
58&max46.pla&46&47&47&46&47&47&46&46&47&47\\ \hline
59&max512.pla&512&284&284&284&284&284&284&284&284&291\\ \hline
60&misj.pla&48&48&51&48&48&48&48&48&48&48\\ \hline
61&mlp4.pla&256&256&256&256&256&256&256&256&256&256\\ \hline
62&mp2d.pla&123&146&248&166&184&177&158&172&145&155\\ \hline
63&mytest.pla&4&4&4&4&4&4&4&4&4&4\\ \hline
64&mytest3.pla&4&4&4&4&4&4&4&4&4&4\\ \hline
65&newapla.pla&17&40&105&35&106&35&42&35&48&40\\ \hline
66&newapla1.pla&10&10&10&10&10&10&10&10&10&10\\ \hline
67&newapla2.pla&7&7&7&7&7&7&7&7&7&7\\ \hline
68&newbyte.pla&8&8&8&8&8&8&8&8&8&8\\ \hline
69&newcond.pla&31&59&125&37&101&44&36&37&63&60\\ \hline
70&newcpla1.pla&38&65&202&49&202&58&50&53&66&92\\ \hline
71&newcpla2.pla&19&29&42&19&29&24&19&19&29&29\\ \hline
72&newcwp.pla&11&13&13&13&13&13&13&13&13&13\\ \hline
73&newill.pla&8&19&32&8&19&8&8&8&21&19\\ \hline
74&newtag.pla&8&14&21&8&14&14&8&8&14&14\\ \hline
75&newtpla.pla&23&34&44&23&34&31&23&23&34&34\\ \hline
76&newtpla1.pla&4&4&4&4&4&4&4&4&4&4\\ \hline
77&newtpla2.pla&9&9&9&9&9&9&9&9&9&9\\ \hline
78&p82.pla&24&22&22&22&22&22&22&22&22&22\\ \hline
79&pope.pla&64&61&61&61&61&61&61&61&61&61\\ \hline
80&prom1.pla&502&478&478&478&478&478&478&478&478&479\\ \hline
81&prom2.pla&287&287&287&287&287&287&287&287&287&287\\ \hline
82&risc.pla&74&33&43&33&43&32&33&33&33&35\\ \hline
83&root.pla&256&143&143&143&143&143&143&143&141&153\\ \hline
84&ryy6.pla&112&112&2218&112&148&112&112&112&112&214\\ \hline
85&sec.pla&23&28&38&26&28&28&26&26&32&28\\ \hline
86&shift.pla&100&100&100&100&100&100&100&100&100&100\\ \hline
87&soar.pla&529&733&3687&552&1512&742&545&555&-&923\\ \hline
88&sqn.pla&96&69&69&69&69&69&69&69&69&75\\ \hline
89&sqr6.pla&64&64&64&64&64&64&64&64&64&64\\ \hline
90&t1.pla&865&567&572&558&561&563&553&556&571&575\\ \hline
91&t2.pla&301&263&265&262&263&263&262&262&263&266\\ \hline
92&t3.pla&152&86&86&86&86&86&86&86&86&86\\ \hline
93&t4.pla&516&516&516&516&516&516&516&516&516&516\\ \hline
94&tcheck.pla&3&3&3&3&3&3&3&3&3&3\\ \hline
95&ts10.pla&128&128&128&128&128&128&128&128&128&128\\ \hline
96&vg2.pla&110&236&1172&207&374&246&204&210&230&312\\ \hline
97&vtx1.pla&110&516&1121&213&642&260&212&211&538&489\\ \hline
98&wim.pla&16&16&16&16&16&16&16&16&16&16\\ \hline
99&x1dn.pla&112&391&1115&213&595&284&212&211&454&487\\ \hline
100&x6dn.pla&121&220&377&153&255&230&153&153&226&225\\ \hline
101&x9dn.pla&120&437&1370&229&765&316&227&227&510&579\\ \hline
$\Sigma$&&15700&\textcolor{blue}{20127}&\textcolor{blue}{22255}&\textcolor{blue}{14300}&\textcolor{blue}{44236}&\textcolor{blue}{16266}&\textcolor{blue}{14360}&\textcolor{blue}{14363}&\textcolor{blue}{15945}&\textcolor{blue}{21925}\\ \hline

\caption{Srovnávací test - porovnání metod průběžného uspořádání termů}
\label{tab:tab11}

\end{longtable}



%------------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------------

\chapter{Porovnání časů metod průběžného řazení termů} \label{sec:test_two}

Označení metod průběžného řazení termů:
\begin{description}
\item[] \textbf{WS} $ $ $ $ WithoutSort (bez řazení) 
\item[] \textbf{SSI} $ $ $ $ SizeSortInc (Podle velikosti termů - vzestupně)
\item[] \textbf{SSD} $ $ $ $ SizeSortDec (Podle velikosti termů - sestupně)
\item[] \textbf{ISI} $ $ $ $ IntersectionSortInc (Podle počtu protnutí s ostatními termy - vzestupně)
\item[] \textbf{ISD} $ $ $ $ IntersectionSortDec (Podle počtu protnutí s ostatními termy - sestupně)
\item[] \textbf{SISI} $ $ $ $ SizeIntersectionSortInc (Podle počtu protnutí s ostatními termy - vzestupně a podle velikosti termů - sestupně)
\item[] \textbf{SISD} $ $ $ $ SizeIntersectionSortDec (Podle počtu protnutí s ostatními termy - sestupně a podle velikosti termů - sestupně)
\item[] \textbf{MI} $ $ $ $ SortByMergeInc (Podle počtu možností sloučení s ostatními termy - vzestupně) 
\item[] \textbf{MD} $ $ $ $ SortByMergeDec (Podle počtu možností sloučení s ostatními termy - sestupně) 
\end{description}$\\$
Jednotlivé naměřené hodnoty časů metod algoritmů jsou v tabulce uvedeny v sekundách.
\\
\begin{longtable}{|p{0.5cm}|p{2cm}|r|r|r|r|r|r|r|r|r|}
\hline
&\textbf{PLA}&\textbf{WS}&\textbf{SSI}&\textbf{SSD}&\textbf{ISI}&\textbf{ISD}&\textbf{SISI}&\textbf{SISD}&\textbf{MI}&\textbf{MD}\\ \hline
1&al2.pla&0&0&0&1&2&2&1&2&1\\ \hline
2&alcom.pla&0&0&0&0&0&0&0&0&0\\ \hline
3&alu1.pla&0&0&0&0&0&0&0&0&0\\ \hline
4&alu2.pla&0&1&1&1&1&1&1&1&1\\ \hline
5&alu3.pla&0&0&0&1&2&0&0&2&3\\ \hline
6&apla.pla&1&0&0&0&0&1&1&1&2\\ \hline
7&b10.pla&0&1&1&1&1&2&1&1&2\\ \hline
8&b11.pla&0&0&0&1&0&0&0&0&0\\ \hline
9&b12.pla&1&39&1&159&6&10&2&142&19\\ \hline
10&b2.pla&0&1&1&0&1&1&1&1&1\\ \hline
11&b3.pla&5&35&11&8&19&16&19&621&60\\ \hline
12&b4.pla&0&-&0&747&1&1&1&1&1\\ \hline
13&b7.pla&0&0&0&0&0&0&0&0&0\\ \hline
14&b9.pla&0&5&0&2&6&4&2&8&2\\ \hline
15&bc0.pla&2&7&5&15&11&V&23&70&50\\ \hline
16&bca.pla&0&2&2&6&8&11&7&24&12\\ \hline
17&bcb.pla&1&1&1&6&10&11&7&17&16\\ \hline
18&bcc.pla&0&1&1&3&4&4&4&14&6\\ \hline
19&bcd.pla&0&1&1&3&2&2&4&9&12\\ \hline
20&br1.pla&0&0&0&0&0&0&0&0&0\\ \hline
21&br2.pla&0&0&0&0&0&0&0&0&0\\ \hline
22&check.pla&0&0&0&0&0&0&0&0&0\\ \hline
23&check2.pla&0&0&0&0&0&0&0&0&0\\ \hline
24&chkn.pla&13&-&1&2067&5&3&4&-&696\\ \hline
25&clpl.pla&0&1&0&0&0&0&0&0&0\\ \hline
26&dc1.pla&0&0&0&0&0&0&0&0&0\\ \hline
27&dc2.pla&0&0&0&0&0&0&0&0&0\\ \hline
28&dist.pla&1&1&1&2&1&1&3&12&7\\ \hline
29&dk17.pla&0&0&0&0&0&0&0&1&1\\ \hline
30&dk27.pla&0&0&0&0&0&1&0&0&0\\ \hline
31&dk48.pla&0&0&0&1&1&0&1&2&2\\ \hline
32&ex1010.pla&9&51&46&160&179&206&182&-&600\\ \hline
33&ex5.pla&0&1&1&4&5&3&4&14&15\\ \hline
34&ex7.pla&1&1&2&2&5&2&2&13&2\\ \hline
35&example.pla&12&&2&2063&10&2&5&-&689\\ \hline
36&exp.pla&1&1&0&0&0&0&0&0&0\\ \hline
37&exps.pla&0&1&2&2&1&3&2&5&4\\ \hline
38&f51m.pla&0&1&2&3&2&6&4&6&14\\ \hline
39&gary.pla&1&5&1&11&2&5&2&6&6\\ \hline
40&ibm.pla&1&35&8&8&36&12&15&378&49\\ \hline
41&in0.pla&1&1&0&1&1&1&1&3&2\\ \hline
42&in1.pla&0&0&0&1&1&0&1&3&3\\ \hline
43&in2.pla&1&29&1&13&8&1&2&71&51\\ \hline
44&in3.pla&1&4&0&1&2&1&0&18&13\\ \hline
45&in5.pla&0&3&1&2&2&2&3&8&3\\ \hline
46&in6.pla&0&-&0&712&0&1&0&1&0\\ \hline
47&in7.pla&8&-&0&2569&37&1&1&-&990\\ \hline
48&inc.pla&0&0&0&1&0&0&0&0&0\\ \hline
49&intb.pla&18&353&46&553&435&228&254&-&1925\\ \hline
50&luc.pla&0&0&0&0&0&0&0&0&1\\ \hline
51&m1.pla&0&0&0&0&1&0&0&0&0\\ \hline
52&m2.pla&0&1&0&0&0&1&1&0&0\\ \hline
53&m3.pla&0&0&1&0&0&1&0&1&2\\ \hline
54&m4.pla&0&2&0&2&1&4&2&15&9\\ \hline
55&mark1.pla&1&1&1&0&1&2&1&2&5\\ \hline
56&max1024.pla&8&22&23&89&87&95&99&308&276\\ \hline
57&max128.pla&0&0&1&1&1&1&1&3&2\\ \hline
58&max46.pla&1&0&0&0&0&0&0&0&0\\ \hline
59&max512.pla&2&3&4&7&13&19&19&44&38\\ \hline
60&misj.pla&1&0&0&0&0&0&1&0&0\\ \hline
61&mlp4.pla&1&1&1&3&5&3&2&6&8\\ \hline
62&mp2d.pla&0&1&0&0&3&1&1&2&1\\ \hline
63&mytest.pla&0&0&0&0&0&0&0&0&0\\ \hline
64&mytest3.pla&0&0&0&0&0&0&0&0&0\\ \hline
65&newapla.pla&0&1&0&0&0&0&0&0&0\\ \hline
66&newapla1.pla&0&0&0&0&0&0&0&0&0\\ \hline
67&newapla2.pla&0&0&0&0&0&0&0&0&0\\ \hline
68&newbyte.pla&0&0&0&0&0&0&0&0&0\\ \hline
69&newcond.pla&0&0&0&1&0&0&1&0&0\\ \hline
70&newcpla1.pla&0&1&0&0&0&0&0&0&0\\ \hline
71&newcpla2.pla&0&0&0&0&0&0&0&0&0\\ \hline
72&newcwp.pla&0&0&0&0&0&0&0&0&0\\ \hline
73&newill.pla&0&0&0&0&0&0&0&0&0\\ \hline
74&newtag.pla&0&0&0&0&0&0&0&0&0\\ \hline
75&newtpla.pla&0&0&0&0&0&0&0&0&0\\ \hline
76&newtpla1.pla&0&0&0&0&0&0&0&0&0\\ \hline
77&newtpla2.pla&0&0&0&0&0&0&0&0&0\\ \hline
78&p82.pla&0&0&0&0&0&0&0&0&0\\ \hline
79&pope.pla&0&0&0&0&1&0&0&1&0\\ \hline
80&prom1.pla&2&10&5&24&12&22&22&124&115\\ \hline
81&prom2.pla&1&3&1&3&7&6&7&14&14\\ \hline
82&risc.pla&0&1&0&1&0&0&0&0&0\\ \hline
83&root.pla&0&1&1&1&3&1&2&9&4\\ \hline
84&ryy6.pla&0&30&1&3&6&4&3&5&28\\ \hline
85&sec.pla&0&0&0&0&0&0&0&0&0\\ \hline
86&shift.pla&1&1&0&0&1&0&0&1&1\\ \hline
87&soar.pla&3&320&29&311&320&164&197&-&679\\ \hline
88&sqn.pla&0&1&0&1&1&0&0&0&0\\ \hline
89&sqr6.pla&0&0&0&0&0&0&0&0&1\\ \hline
90&t1.pla&4&18&18&89&105&103&107&364&267\\ \hline
91&t2.pla&1&3&4&5&3&4&3&15&17\\ \hline
92&t3.pla&0&1&0&1&0&0&1&1&1\\ \hline
93&t4.pla&3&13&7&18&21&27&27&107&91\\ \hline
94&tcheck.pla&0&0&0&0&0&0&0&0&0\\ \hline
95&ts10.pla&0&1&0&1&1&0&0&1&2\\ \hline
96&vg2.pla&0&9&1&2&5&1&2&3&6\\ \hline
97&vtx1.pla&1&4&1&3&3&2&3&191&15\\ \hline
98&wim.pla&0&0&0&0&0&0&0&0&0\\ \hline
99&x1dn.pla&1&4&1&4&3&2&2&119&17\\ \hline
100&x6dn.pla&0&3&1&1&2&1&1&5&4\\ \hline
101&x9dn.pla&1&13&1&6&5&2&4&79&20\\ \hline
$\Sigma$&&\textcolor{blue}{110}&\textcolor{blue}{1051}&\textcolor{blue}{241}&\textcolor{blue}{9707}&\textcolor{blue}{1418}&\textcolor{blue}{1011}&\textcolor{blue}{1069}&\textcolor{blue}{2875}&\textcolor{blue}{6884}\\ \hline
\caption{Srovnávací test - Porovnání časů metod průběžného uspořádání termů}
\label{tab:tab12}

\end{longtable}


%*****************************************************************************
%*****************************************************************************
%*****************************************************************************



\chapter{Porovnání navrženého algoritmu s cizími implementacemi} \label{sec:test_three}

Označení algoritmů:
\begin{description}
\item[] \textbf{SSD} $ $ $ $ SizeSortDec (Algoritmus s řazením termů podle velikosti - sestupně)
\item[] \textbf{ABM} $ $ $ $ A\_BackMerge (Algoritmus \textit{SizeSortDec} s použitím zpětného sloučení termů)
\item[] \textbf{AEU} $ $ $ $ A\_EliminateUndefined (Algoritmus \textit{A\_BackMerge} s eliminací termů nepatřící do ONsetu)
\item[] \textbf{AE} $ $ $ $ A\_Espresso (Algoritmus \textit{A\_EliminateUndefined} s minimalizací vstupních termů pomocí Espressa)
\end{description}
Cizí algoritmy:
\begin{description}
\item[] \textbf{DSOP} $ $ $ $ (Implementace heuristického algoritmu pro ortogonalizaci logické funkce)
\item[] \textbf{Espresso -Ddisjoint} $ $ $ $ (Podprogram Espressa pro ortogonalizaci logické funkce)
\end{description}$\\$
Jednotlivé naměřené hodnoty algoritmů jsou v tabulce uvedeny v termech.
\\ 
\begin{longtable}{|p{0.5cm}|p{2cm}|r|r|r|r|r|r|r|r|}
\hline
&\textbf{PLA}&\textbf{SOP}&\textbf{SSD}&\textbf{ABM}&\textbf{AEU}&\textbf{AE}&\textbf{DSOP}&\textbf{Espresso -Ddisjoint}\\ \hline
0&al2.pla&103&105&105&105&106&86&121\\ \hline
1&alcom.pla&47&46&46&46&49&47&47\\ \hline
2&alu1.pla&19&19&19&19&19&19&23\\ \hline
3&alu2.pla&91&102&102&98&98&87&138\\ \hline
4&alu3.pla&72&72&72&68&77&68&196\\ \hline
5&apla.pla&134&100&100&78&33&56&112\\ \hline
6&b10.pla&138&121&120&117&116&135&134\\ \hline
7&b11.pla&74&31&30&30&29&35&42\\ \hline
8&b12.pla&431&96&60&60&78&52&302\\ \hline
9&b2.pla&110&111&111&111&119&118&134\\ \hline
10&b3.pla&234&392&343&343&340&288&1043\\ \hline
11&b4.pla&54&63&63&63&116&62&86\\ \hline
12&b7.pla&74&31&30&30&29&35&42\\ \hline
13&b9.pla&123&181&181&181&177&181&288\\ \hline
14&bc0.pla&479&377&335&276&207&365&430\\ \hline
15&bca.pla&301&202&181&181&189&301&301\\ \hline
16&bcb.pla&299&188&160&160&164&299&299\\ \hline
17&bcc.pla&245&163&140&140&146&245&245\\ \hline
18&bcd.pla&243&149&126&126&123&243&243\\ \hline
19&br1.pla&34&20&20&20&21&33&33\\ \hline
20&br2.pla&35&19&15&15&14&35&35\\ \hline
21&check.pla&16&14&12&1&1&4&4\\ \hline
22&check2.pla&16&14&11&1&1&4&4\\ \hline
23&chkn.pla&153&174&174&174&190&168&1511\\ \hline
24&clpl.pla&20&20&20&20&20&20&20\\ \hline
25&dc1.pla&15&19&19&19&12&15&19\\ \hline
26&dc2.pla&58&45&43&43&47&58&58\\ \hline
27&dist.pla&256&179&166&165&134&255&255\\ \hline
28&dk17.pla&93&76&76&40&24&32&57\\ \hline
29&dk27.pla&52&52&52&20&11&14&20\\ \hline
30&dk48.pla&148&142&142&36&26&28&42\\ \hline
31&ex1010.pla&1024&1020&1020&806&899&810&810\\ \hline
32&ex5.pla&256&179&165&165&125&256&256\\ \hline
33&ex7.pla&123&181&181&181&177&181&288\\ \hline
34&example.pla&153&174&174&174&190&168&1511\\ \hline
35&exp.pla&89&74&70&70&76&89&89\\ \hline
36&exps.pla&196&165&143&143&155&193&196\\ \hline
37&f51m.pla&256&256&256&255&76&255&255\\ \hline
38&gary.pla&214&116&116&116&122&121&123\\ \hline
39&ibm.pla&173&376&376&376&394&361&1046\\ \hline
40&in0.pla&138&137&136&133&122&135&135\\ \hline
41&in1.pla&110&111&111&111&119&118&134\\ \hline
42&in2.pla&137&167&167&167&181&179&615\\ \hline
43&in3.pla&75&121&121&121&133&94&308\\ \hline
44&in5.pla&62&172&165&165&171&125&348\\ \hline
45&in6.pla&54&63&63&63&116&61&86\\ \hline
46&in7.pla&84&76&76&76&63&56&1384\\ \hline
47&inc.pla&34&33&33&33&36&34&34\\ \hline
48&intb.pla&664&830&821&821&841&791&2538\\ \hline
49&luc.pla&27&29&29&29&35&28&42\\ \hline
50&m1.pla&32&23&21&21&20&32&32\\ \hline
51&m2.pla&96&64&53&53&58&96&96\\ \hline
52&m3.pla&128&90&73&73&88&128&128\\ \hline
53&m4.pla&256&165&123&123&150&248&256\\ \hline
54&max1024.pla&1024&569&416&416&363&1024&1024\\ \hline
55&max128.pla&128&89&85&85&113&128&128\\ \hline
56&max46.pla&46&46&46&46&46&46&47\\ \hline
57&max512.pla&512&284&208&208&176&512&512\\ \hline
58&misj.pla&48&48&48&48&82&47&48\\ \hline
59&mlp4.pla&256&256&238&225&151&225&225\\ \hline
60&mp2d.pla&123&166&166&166&140&137&166\\ \hline
61&mytest.pla&4&4&4&4&2&4&4\\ \hline
62&mytest3.pla&4&4&4&3&4&3&3\\ \hline
63&p82.pla&24&22&22&22&22&24&24\\ \hline
64&pope.pla&64&61&61&61&91&64&64\\ \hline
65&prom1.pla&502&478&475&475&485&465&502\\ \hline
66&prom2.pla&287&287&287&287&287&287&287\\ \hline
67&risc.pla&74&33&32&32&31&35&42\\ \hline
68&ryy6.pla&112&112&112&112&128&112&112\\ \hline
69&pla&23&26&26&26&27&26&30\\ \hline
70&shift.pla&100&100&100&100&105&100&100\\ \hline
71&soar.pla&529&552&552&552&547&454&805\\ \hline
72&sqn.pla&96&69&65&54&48&72&84\\ \hline
73&sqr6.pla&64&64&64&63&52&63&63\\ \hline
74&t1.pla&865&558&290&256&144&542&860\\ \hline
75&t2.pla&301&262&164&76&63&76&130\\ \hline
76&t3.pla&152&86&46&42&34&148&148\\ \hline
77&t4.pla&516&516&252&38&22&38&38\\ \hline
78&tcheck.pla&3&3&3&3&3&3&3\\ \hline
79&ts10.pla&128&128&128&128&128&128&128\\ \hline
80&vg2.pla&110&207&207&207&207&204&236\\ \hline
81&vtx1.pla&110&213&213&213&213&204&710\\ \hline
82&wim.pla&16&16&15&10&17&10&10\\ \hline
83&x1dn.pla&112&213&213&213&213&204&517\\ \hline
84&x6dn.pla&121&153&152&152&158&142&262\\ \hline
85&x9dn.pla&120&229&229&229&229&218&595\\ \hline
$\Sigma$&&15122&\textcolor{blue}{13799}&\textcolor{blue}{12490}&\textcolor{blue}{11613}&\textcolor{blue}{11394}&\textcolor{blue}{13702}&\textcolor{blue}{24901}\\ \hline
\caption{Srovnávací test - porovnání vybraných metod navrženého algoritmu s cizími dostupnými implementacemi}
\label{tab:tab13}

\end{longtable}


%*****************************************************************************
%*****************************************************************************
%*****************************************************************************
\chapter{Porovnání časů navrženého algoritmu s cizími implementacemi} \label{sec:test_four}

Označení algoritmů:
\begin{description}
\item[] \textbf{SSD} $ $ $ $ SizeSortDec (Algoritmus s řazením termů podle velikosti - sestupně)
\item[] \textbf{ABM} $ $ $ $ A\_BackMerge (Algoritmus \textit{SizeSortDec} s použitím zpětného sloučení termů)
\item[] \textbf{AEU} $ $ $ $ A\_EliminateUndefined (Algoritmus \textit{A\_BackMerge} s eliminací termů nepatřící do ONsetu)
\item[] \textbf{AE} $ $ $ $ A\_Espresso (Algoritmus \textit{A\_EliminateUndefined} s minimalizací vstupních termů pomocí Espressa)
\end{description}
Cizí algoritmy:
\begin{description}
\item[] \textbf{DSOP} $ $ $ $ (Implementace heuristického algoritmu pro ortogonalizaci logické funkce)
\item[] \textbf{Espresso -Ddisjoint} $ $ $ $ (Podprogram Espressa pro ortogonalizaci logické funkce)
\end{description}$\\$
Jednotlivé naměřené hodnoty časů algoritmů jsou v tabulce uvedeny v sekundách.
\\
\begin{longtable}{|p{0.5cm}|p{2cm}|r|r|r|r|r|r|r|}
\hline
&\textbf{PLA}&\textbf{SSD}&\textbf{ABM}&\textbf{AEU}&\textbf{AE}&\textbf{DSOP}&\textbf{Espresso -Ddisjoint}\\ \hline
0&al2.pla&0,2&0,4&0,4&0,4&0,1&0,2\\ \hline
1&alcom.pla&0,5&0,5&0,2&0,6&0,0&0,7\\ \hline
2&alu1.pla&0,1&0,1&0,1&0,3&0,0&0,1\\ \hline
3&alu2.pla&0,2&0,2&0,2&1,1&0,1&0,1\\ \hline
4&alu3.pla&0,0&0,0&0,0&0,2&0,0&0,2\\ \hline
5&apla.pla&1,0&1,0&1,0&0,9&0,0&0,2\\ \hline
6&b10.pla&0,5&0,0&0,0&1,9&0,0&0,1\\ \hline
7&b11.pla&0,2&0,3&0,3&0,7&0,0&0,2\\ \hline
8&b12.pla&0,7&0,4&0,3&0,5&0,1&0,1\\ \hline
9&b2.pla&0,6&0,5&0,5&0,7&0,2&0,4\\ \hline
10&b3.pla&11,1&6,2&5,0&6,6&0,1&0,5\\ \hline
11&b4.pla&0,3&0,9&0,9&1,3&0,0&0,5\\ \hline
12&b7.pla&0,2&0,2&0,2&0,6&0,0&0,1\\ \hline
13&b9.pla&0,4&1,6&1,6&1,4&0,1&0,1\\ \hline
14&bc0.pla&5,1&6,2&10,9&1,1&0,2&0,3\\ \hline
15&bca.pla&2,0&2,6&4,1&1,3&0,1&0,8\\ \hline
16&bcb.pla&0,9&1,1&3,0&1,3&0,1&0,3\\ \hline
17&bcc.pla&1,1&2,2&1,5&1,4&0,1&0,2\\ \hline
18&bcd.pla&1,0&1,1&1,1&1,8&0,1&0,2\\ \hline
19&br1.pla&0,1&0,1&0,0&0,0&0,0&0,2\\ \hline
20&br2.pla&0,0&0,0&0,0&0,1&0,0&0,1\\ \hline
21&check.pla&0,1&0,1&0,1&0,6&0,0&0,1\\ \hline
22&check2.pla&0,0&0,0&0,0&0,8&0,0&0,1\\ \hline
23&chkn.pla&1,2&1,3&1,6&2,6&0,2&0,1\\ \hline
24&clpl.pla&0,7&0,8&0,5&0,8&0,0&0,8\\ \hline
25&dc1.pla&0,0&0,0&0,0&0,1&0,0&0,1\\ \hline
26&dc2.pla&0,0&0,0&0,0&0,1&0,0&0,1\\ \hline
27&dist.pla&1,2&1,4&1,4&1,4&0,0&0,1\\ \hline
28&dk17.pla&0,3&0,5&0,4&0,4&0,0&0,2\\ \hline
29&dk27.pla&0,0&0,0&0,0&0,1&0,0&0,0\\ \hline
30&dk48.pla&0,4&1,3&1,3&0,9&0,0&0,1\\ \hline
31&ex1010.pla&45,9&65,7&46,7&45,8&0,1&0,0\\ \hline
32&ex5.pla&1,1&2,9&1,5&1,0&0,5&0,3\\ \hline
33&ex7.pla&2,4&2,6&1,2&1,1&0,1&1,8\\ \hline
34&example.pla&2,3&3,2&1,3&1,3&0,2&0,3\\ \hline
35&exp.pla&0,2&0,3&0,2&1,1&0,0&0,8\\ \hline
36&exps.pla&2,1&1,6&0,9&0,9&0,1&0,1\\ \hline
37&f51m.pla&2,2&3,6&1,6&0,8&0,0&0,3\\ \hline
38&gary.pla&1,2&2,0&1,3&1,4&0,1&0,2\\ \hline
39&ibm.pla&7,6&5,5&5,5&13,4&0,2&0,2\\ \hline
40&in0.pla&0,3&1,1&1,1&0,9&0,0&0,8\\ \hline
41&in1.pla&0,4&0,5&0,6&0,5&0,1&0,2\\ \hline
42&in2.pla&1,0&1,2&1,2&1,1&0,1&0,3\\ \hline
43&in3.pla&0,4&0,9&1,3&0,9&0,1&0,3\\ \hline
44&in5.pla&1,1&1,1&2,2&1,7&0,0&0,2\\ \hline
45&in6.pla&0,3&0,8&1,0&0,6&0,0&0,2\\ \hline
46&in7.pla&0,4&1,5&0,3&0,6&0,0&0,2\\ \hline
47&inc.pla&0,2&0,2&0,1&0,3&0,0&0,1\\ \hline
48&intb.pla&45,6&63,4&73,5&69,2&1,1&0,1\\ \hline
49&luc.pla&0,1&0,2&0,3&0,2&0,0&3,8\\ \hline
50&m1.pla&0,4&0,4&0,2&0,6&0,0&0,1\\ \hline
51&m2.pla&0,4&0,5&1,5&0,7&0,0&0,1\\ \hline
52&m3.pla&1,2&1,9&0,7&0,8&0,1&0,2\\ \hline
53&m4.pla&0,4&2,6&1,4&1,4&0,1&0,2\\ \hline
54&max1024.pla&22,8&31,1&33,8&8,1&0,2&0,4\\ \hline
55&max128.pla&0,9&1,2&0,4&0,8&0,1&0,8\\ \hline
56&max46.pla&0,4&0,7&0,5&0,5&0,0&0,2\\ \hline
57&max512.pla&3,8&3,3&3,3&1,2&0,1&0,1\\ \hline
58&misj.pla&0,1&0,1&0,1&0,1&0,0&0,3\\ \hline
59&mlp4.pla&1,4&2,8&1,3&1,7&0,0&0,2\\ \hline
60&mp2d.pla&0,4&1,4&1,0&1,4&0,0&0,2\\ \hline
61&mytest.pla&0,2&0,5&0,1&0,4&0,0&0,2\\ \hline
62&mytest3.pla&0,0&0,0&0,0&0,0&0,0&0,0\\ \hline
63&p82.pla&0,0&0,0&0,0&0,0&0,0&0,0\\ \hline
64&pope.pla&0,1&0,2&0,2&0,8&0,1&0,1\\ \hline
65&prom1.pla&5,3&14,6&6,0&6,3&0,0&0,3\\ \hline
66&prom2.pla&1,2&2,1&2,7&2,7&0,2&0,0\\ \hline
67&risc.pla&0,4&0,5&0,8&0,3&0,0&0,6\\ \hline
68&ryy6.pla&1,4&1,6&2,1&2,3&0,1&0,1\\ \hline
69&pla&0,3&0,3&0,3&0,5&0,0&0,3\\ \hline
70&shift.pla&0,4&1,0&0,9&1,6&0,0&0,0\\ \hline
71&soar.pla&28,3&33,2&33,2&27,2&0,5&0,1\\ \hline
72&sqn.pla&0,9&0,9&0,9&0,9&0,0&1,8\\ \hline
73&sqr6.pla&0,2&0,7&0,5&0,7&0,0&0,1\\ \hline
74&t1.pla&17,6&16,5&20,4&2,9&0,1&0,1\\ \hline
75&t2.pla&4,2&5,3&1,4&0,8&0,0&0,3\\ \hline
76&t3.pla&1,7&1,7&0,9&0,3&0,0&0,1\\ \hline
77&t4.pla&14,7&14,7&0,7&0,7&0,0&0,1\\ \hline
78&tcheck.pla&0,1&0,1&0,1&0,6&0,0&0,1\\ \hline
79&ts10.pla&0,3&1,2&0,4&1,3&0,0&0,0\\ \hline
80&vg2.pla&1,4&1,7&2,2&3,6&0,1&0,1\\ \hline
81&vtx1.pla&1,2&1,4&1,4&2,6&0,1&0,5\\ \hline
82&wim.pla&0,4&0,8&0,6&0,6&0,0&0,4\\ \hline
83&x1dn.pla&1,4&2,0&1,4&1,0&0,1&0,0\\ \hline
84&x6dn.pla&0,7&0,2&0,6&0,6&0,1&0,3\\ \hline
85&x9dn.pla&1,3&2,3&2,0&2,5&0,1&0,2\\ \hline
$\Sigma$&&\textcolor{blue}{260,7}&\textcolor{blue}{339,1}&\textcolor{blue}{302,2}&\textcolor{blue}{253,3}&\textcolor{blue}{7,1}&\textcolor{blue}{25,2}\\ \hline

\caption{Srovnávací test - porovnání časů vybraných metod navrženého algoritmu s cizími dostupnými implementacemi}
\label{tab:tab14}
\end{longtable}


%*****************************************************************************
%*****************************************************************************
%*****************************************************************************

\chapter{Ovládání navrženého programu} \label{sec:ovladani_programu}

Program pro ortogonalizaci logické funkce je určen pro platformu Windows.\\
\\\\
\textbf{Spuštění programu v příkazové řádce:}\\
\\
\textit{Orthogonalization.exe} $ $ $ $ [\textit{číslo\_algoritmu}] [\textit{vstupní\_PLA\_soubor}] [\textit{výstupní\_PLA\_soubor}] \\
\\\\
\textbf{Parametr "číslo\_algoritmu":}
\begin{description}
\item[] "\textbf{0}" $ $ $ $ $ $ Základní algoritmus bez průběžného řazení.
\item[] "\textbf{1}" $ $ $ $ $ $ Základní algoritmus s řazením podle velikosti termů (vzestupně).
\item[] "\textbf{2}" $ $ $ $ $ $ Základní algoritmus s řazením podle velikosti termů (sestupně).
\item[] "\textbf{3}" $ $ $ $ $ $ Základní algoritmus s řazením podle počtu protnutí s ostatními termy (vzestupně).
\item[] "\textbf{4}" $ $ $ $ $ $ Základní algoritmus s řazením podle počtu protnutí s ostatními termy (sestupně).
\item[] "\textbf{5}" $ $ $ $ $ $ Základní algoritmus s řazením podle počtu protnutí s ostatními termy (vzestupně) a podle velikosti termů (sestupně).
\item[] "\textbf{6}" $ $ $ $ $ $ Základní algoritmus s řazením podle počtu protnutí s ostatními termy (sestupně) a podle velikosti termů (sestupně).
\item[] "\textbf{7}" $ $ $ $ $ $ Základní algoritmus s řazením podle počtu možností sloučení s ostatními termy. (vzestupně). 
\item[] "\textbf{8}" $ $ $ $ $ $ Základní algoritmus s řazením podle počtu možností sloučení s ostatními termy. (sestupně).
\item[] "\textbf{9}" $ $ $ $ $ $ Algoritmus \textbf{2} s použitím zpětného sloučení termů.
\item[] "\textbf{10}"$ $ $ $ $ $ Algoritmus \textbf{9} s eliminací termů nepatřící do ONsetu.
\item[] "\textbf{11}"$ $ $ $ $ $ Algoritmus \textbf{10} s minimalizací vstupních termů pomocí Espressa.
\end{description}



%*****************************************************************************
%*****************************************************************************
%*****************************************************************************

\chapter{Obsah přiloženého CD} \label{sec:priloha_CD}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5.0cm]{figures/obsahcd}
\caption{Obsah přiloženého CD}
\label{fig:obsahcd}
\end{center}
\end{figure}

\begin{itemize}
\item \textbf{Benchmarks} $ $ $ $ $ $ MCNC testovací úlohy formátu PLA
\item \textbf{Source} $ $ $ $ $ $ Zdrojové soubory navrženého nástroje na ortogonalizaci logické funkce.
\item \textbf{Text} $ $ $ $ $ $ Zdrojové soubory tohoto textu a tištěný formát PDF.
\item \textbf{Tools} $ $ $ $ $ $ Použité nástroje\\
\textbf{ - BOOM} $ $ $ $ $ $ Zdrojové soubory minimalizátoru BOOM 2.7\\
\textbf{ - DSOP} $ $ $ $ $ $ Spustitelný program DSOP [11] na ortogonalizaci logické funkce.\\
\textbf{ - Espresso} $ $ $ $ $ $ Spustitelný program a manuál ESPRESSA 2.3\\
\textbf{ - Ortho} $ $ $ $ $ $ Spustitelný program Ortho pro testování ortogonalizace logické funkce.
\end{itemize}

\end{document}
