\chapter{Implementace}

\section{Všeobecné informace k implementaci}
\indent \indent Modulární systém, který byl naznačen v analýze a návrhu, budu řešit třídami implementovanými v jazyce C++. O provádění jednotlivých úkonů syntézy se budou starat metody daných tříd. Veškeré  grafové reprezentace a regiony jsou řešeny přes datové struktury. Z knihovny STL budu používat šablonu vector pro uchovávání množin grafů ve strukturách. Metody tříd, které budou pracovat s množinami pro jejich uchovaní, využívají šablonu fronta. Veškeré metody tříd jsou nainlajnované v hlavičkách tříd, proto je jen jeden soubor \textit{.cpp}, ve které je main funkce.

\section{Vstup programu}
\indent \indent Vstupem programu je textový soubor. Soubor obsahuje textově popsaný signálově přechodový graf. Vstupní popis grafu je popsán v příloze.



\section{Třída FromFile}
\indent \indent Slouží k načtení souboru, čtení jednotlivých řádků, dekódování příkazů a odesílání argumentů příkazů ke zpracování. Příkaz a argumenty jsou po pársováním vkládány do fronty. Prvky fronty se postupně odebírají a interpretují.

\section{Třída DoCommand}
\indent \indent Třída obsahuje metody, které převedou informace naparsovaného vstupního textu do datových struktur, reprezentujících STG v programu. Vstupem této třídy je datová struktura fronta, ve které jsou informace v textových řetězcích. Výstupem třídy je struktura reprezentující STG.


\section{Třída Prikaz}
\indent \indent Účelem této třídy je, podle zadaného příkazu, rozeznat příkaz a přiřadit mu číslo, které  při výběru bude volat metodu při jeho zpracování.

\section{STG v programu}
\indent \indent Místa v STG jsou tvořena pomocí struktury \textit{Place}. Ve struktuře \textit{Place}  se uchovávají informace, zda je místo označené tokenem a na jaký přechod ukazuje. Schematické naznačení \ref{fig:stgstr}


\begin{verbatim}
  struct Place{
  char token;  
  int indexTran;       
  };
\end{verbatim}

Data o přechodu jsou uchovávány ve struktuře \textit{Tran}, jež nese informace o ukazatelích na místa \textit{indexPlace} a počet ukazatelů na místa \textit{numOfip}. Jestli je přechod rostoucí nebo klesající udává proměnná \textit{riseOrFall}, do které se nastaví + nebo – podle přechodu. 
 
 

\begin{verbatim}
  struct Tran{
  int stavInd;
  char riseOrFall;
  int* indexPlace;
  int numOfip;       
  };
\end{verbatim}

Celkový graf STG je uložen ve struktuře pojmenované \textit{Stg}.
 
\begin{verbatim}
  struct Stg {
        int sizeCode;            	 //velikost binárního kódu
        char *initCode ;          	// počáteční kod
        vector<Place*>  place;    	//vektor míst
        vector<Tran*>   tran;     	//vektor přechodu
        int pocetPlace;           	//počet míst ve vektoru
        int pocetTran;            	//počet přechodu ve vektoru
        int* vyP;                 	// index výstupu
        int pocetVyP;             	// počet výstupu
        vector<string>  nazvy;	//názvy signálu
        vector<int>  nazvyp;	//identifikator signálu
        string nameFile;		//jméno souboru
  };
\end{verbatim}

\begin{figure}[hp]
\begin{center}
\includegraphics{stgstr}
\caption{Struktura STG}
\label{fig:stgstr}
\end{center}
\end{figure}

\clearpage

\section{Třída MakeSG}
\indent \indent Základním kamenem celého programu je tato třída, protože je zde realizována transformace signálově přechodového grafu na stavový graf. Transformační algoritmus je založen na matematickém algoritmu pro transformaci STG na SG popsanou výše. Parametry, které tato třída přijímá jsou struktury \textit{Stg}a textit{SG}.  Ve struktuře textit{Stg} je uložen datový obraz STG. 
 \newline
Metody třídy MakeSG:

	find\_SG
\newline Základní metoda pro hledání stavového grafu ze signálově přechodového grafu. Postupuje se v ní podle popsaného algoritmu.


Metody, které využívá metoda find\_SG pro hledání stavového grafu:

  selectTe
\newline Metoda slouží k vybrání přechodu, přes který se bude následně přecházet. Přechod musí splňovat požadavek ,že na jeho vstupních místech se nachází token nebo tokeny.
\newline Asymptotická složitost metody: $O(nx)$ 
\newline n - počet prvků v množině $Te$,   
\newline x - počet míst v STG  

	doM
\newline Metoda slouží k naplnění množiny \textit{M}. \textit{M} obsahuje prvky ze structury \textit{Place}, ve kterých se nacházejí tokeny. Množina \textit{M} je tvořena C++ šablonou fronta.
\newline Asymptotická složitost metody: $O(n)$
\newline n - je počet míst v STG

	makeTe
\newline Metoda naplní množinu \textit{Te}  přechody, které jsou reprezentovány strukturou \textit{Tran} v \textit{Stg}. Metoda vybírá pouze ty přechody, které mají na místech, ze kterých se dostaneme do daného přechodu, token.
\newline Asymptotická složitost metody: $\Theta (n)$ 
\newline n - je počet prvků v množině $M$
	
	doS
\newline Slouží k přidání množiny \textit{M} do množiny \textit{S}. Celá množina \textit{M} představuje v množině \textit{S} jeden prvek. Prvek množiny \textit{S} odpovídá stavu ve stavovém grafu.
\newline Asymptotická složitost metody: $\Theta (n)$ 
\newline n - je počet míst k sjednocení	

	changToken
\newline Metoda provádí přemístění tokenů ve struktuře \textit{Stg}. Přemísťují se pouze tokeny, které jsou na vstupních místech vybraného přechodu \textit{t}. Přes vybraný přechod se dá vždy přejít.
\newline Asymptotická složitost metody: $\Theta (n+x)$	
\newline n - počet míst v STG
\newline x - počet míst vycházejících z vybraného přechodu 

	comperM
\newline Vytvoří průnik mezi množinou míst vycházejí z vybraného přechodu \textit{t} a množinou \textit{M}, která je ochuzena o místa vstupující do přechodu \textit{t}. Pokud výsledek průniku není prázdná množina, pak metoda vrátí true.
\newline Asymptotická složitost metody: $\Theta (n) + O (x)$ 
\newline n - počet prvků množiny $M$ 
\newline x- počet míst vycházejících z vybraného přechodu
\newline

	isIndcludeS
\newline Porovnává obsah prvku množiny \textit{S} s množinou \textit{M}. Prvek množiny \textit{S} je tvořen množinou míst STG. Pokud se obsah prvku množiny \textit{S} schoduje se všemi prvky množiny \textit{M}, pak metoda vrátí false. 
\newline Asymptotická složitost metody: $\Theta (n) +  O(xnn) + O(n)$
\newline n - počet prvků množiny $M$
\newline x - počet stavů v SG


	sjednoceni
\newline Do množiny \textit{M} se překopíruje množina \textit{M} ochuzená o vstupní místa vybraného přechodu \textit{t} sjednocenou s výstupními místy vybraného přechodu \textit{t}.
\newline Asymptotická složitost metody: $\Theta (n)$
\newline n - počet míst vycházejících z vybraného přechodu
	
	changCode
\newline Nastaví proměnnou obsahující binární kód aktuálního stavu stavového grafu. Dalším jejím účelem je přenastavit zakódovaní podle vybraného přechodu, buď na jedna pokud aktuální přechod je rostoucí nebo na nula pokud je klesající.
\newline Asymptotická složitost metody: $O(1)$	

	transition
\newline Vytváří přechod mezi stavy stavového grafu, jinými slovy vytváří vztah mezi prvky  množiny \textit{S}. Přechod je fyzicky umístěn v prvku z nějž vychází.
\newline Asymptotická složitost metody: $O(n+1)$ 	
\newline n - aktuální počet přechodů stavu
\newline 1 - přidáni nového přechodu 	

Celková asymptotická složitost transformace je součet všech asymptotických složitostí metod, z čehož plyne, že výsledná složitost bude $O(xn^2)$.  Výsledek vychází ze složitosti metody isIncludes, ve které je potřeba použít tři cykly, abych byl schopen porovnat všechny množiny míst ve stavech stavového grafu s množinou míst, která by mohla tvořit nový stav.  


\section{Stuktura stavového grafu}
\indent \indent Struktura se skládá ze dvou částí: \textit{SGelem} a \textit{SG}. Kde \textit{SGelem} představuje informace o samotném stavu. \textit {SG} je nosná konstrukce pro prvky typu \textit {SGelem}. Schéma struktury je na obrázku \ref{fig:sgstr}.



SGelem
\newline Nese informace o zakódování stavu v proměnné \textit{code}. V ukazateli \textit{pole} jsou uloženy indexy, které udávají vztah k danému prvku v SG poli \textit{sg}. \textit{lenPole} udává počet odkazů. Informace o přechodu jsou v \textit{t} a \textit{p}.


\begin{verbatim}
  struct SGelem{
  int* pole;
  int lenPole; 
  char* code;
  int num;
  int* t;
  int* p;              
  };
\end{verbatim}

SG
\newline Nosná konstrukce obsahuje šablonu vector, ve které jsou uloženy jednotlivé elementy typu \textit{SGelem}, dále obsahuje proměnnou udávající počet prvků ve vectoru.

\begin{verbatim}
  struct SG {
  int pocet;
  vector<SGelem*> sg;
  };
\end{verbatim}

\begin{figure}[hp]
\begin{center}
\includegraphics{sgstr}
\caption{Struktura SG}
\label{fig:sgstr}
\end{center}
\end{figure}
\clearpage

\section{Třída Region}
\indent \indent Cílem třídy je vytvoření regionů, které se budou uchovávat ve struktuře \textit{RegStavBuf}.
Vstupem třídy je stavový graf, který je reprezentován strukturou \textit{SG}. Třída má metody, které postupně projdou celou strukturu \textit{SG} a pro jednotlivé vstupy, výstupy a interní signály rozřadí zakódování stavů do jednotlivých regionů. Cílem třídy je naplnit \textit{RegStavBuf} vybranými daty z \textit{SG}.



\section{Třída KMap}
\indent \indent Třída zpracovává strukturu \textit {RegStavBuf}, struktura obsahuje ER a QR pro jednotlivé signály. ER obsahuje kódy stavů, které nabývají výstupní hodnotu jedna. QR obsahuje kódy stavů, které nabývají hodnoty nula. Pokud se nějaký kód nenachází v QR nebo v ER, pak se nachází v don't care a pro nás je nedůležitý. Na základě regionu poté probíhá minimalizace úplných mintermů. Mintermy jsou výchozí body pro vytvoření funkcí pro vstupy \hbox{C-elementu}. Minimalizace se provádí metodou fceExpanze.


fceExpanze
\newline \newline Metoda porovnává řetězec z ER- resp. ER+   s regiony z QR + a ER+ resp. QR- a ER-. Postup jak dochází k porovnávání a k minimalizaci je popsán v kapitole 4. v části Algoritmus minimalizace.


Asymptotická složitost metody, která se stará o minimalizaci je $O(xn)$. Kde $n$ je počet proměnných v termu a $x$ je počet termů v ER+ $\cup$ QR+ resp. ER- $\cup$ QR-.

\section{Třída  MakeCorLog}
\indent \indent Cílem této  třídy je převést získané funkce, ze třídy KMap pro\hbox{C-elementy}, do VHDL kódu. Třída vkládá do \textit{entitiní} části výstupní a vstupní signály a přidá  ke jménům signálů \textit{in} nebo \textit{out} podle typu signálu. Dále třída předdefinovává pomocné signály, které mají stejná jména jako signály ve vstupním souboru , přidává pomocné signály pro Set a Reset daného \hbox{C-elementu} a provádí  naportování signálu na \hbox{C-element}.


