\chapter{Analýza a návrh řešení}

\section{Shrnutí před analýzou a návrhem}
\indent \indent Shrnutí podstatných věcí před analýzou a před vytvořením programu, který bude generovat VHDL kód na základě vstupní specifikace STG. Syntéza bude založena na specifikaci signálově přechodovém grafu, jež popisuje Speed Independent obvody. Podstatou syntézy je přetransformovat signálově přechodový graf do stavového grafu a dodržet podmínky určující správnost grafů. Po transformaci je třeba stanovit regiony pro dané signály a na základě těchto regionů budou přiřazeny výstupní hodnoty. Z hodnot v regionech vytvořit  funkce, jež zohledňují  užití \hbox{C-elementu}. Na základě funkcí vytvoříme logiku zahrnující \hbox{C-elementy}. Některé \hbox{C-elementy} mohou být vypuštěny. Daná kombinační logika zahrnující \hbox{C-element} bude popsána pomocí VHDL kódu.


\section{Implementační jazyk}
\indent \indent Jako implementační jazyk jsem zvolil C++, který nám poskytuje možnost využít tříd a předpřipravených šablon knihovny STL. Navíc je daleko vhodnější pro programy, které nevyužívají grafické rozhraní, tedy pro konzolové aplikace. Můj  program bude konzolová aplikace, jejímž vstupem bude textový soubor a výstupem soubor obsahující VHDL kód, který popisuje logiku. Výsledný program bude exe soubor.  


\section{Vstup programu}
\indent \indent Vstupní specifikací pro syntézu je signálově přechodový graf. Graf lze obecně popsat vhodnou písemnou formou, která bude vyjadřovat patřičné informace a je srozumitelná pro uživatele i pro počítač. 



\section{Reprezentace grafu}
\indent \indent Ze specifikace pro signálově přechodový graf  můžu vyjádřit základní požadavky, které by popisná forma grafu měla mít. Jedná se konkrétně o dvě množiny. Množinu míst a množinu přechodů. Mezi těmito množinami existuje vztah,  že pokud se chci dostat z jednoho z prvku množiny přechodů na jiný prvek téže množiny, musím nejprve přejít přes prvek množiny míst, který je v dané relaci s již zmíněnými prvky množiny přechodů. Stejné pravidlo platí i mezi prvky množiny míst a prvkem množiny přechodů. Z mého pohledu je lépe se držet představy dva přechody a jedno místo. Z toho důvodu se zaměřuji na signály přechodů, zatímco místa jsou pro mě implicitně dodané hodnoty potřebné pro transformaci. Výsledkem tedy je, že pro popsání vztahu přechodů a míst mi stačí znát  vztahy mezi přechody, přičemž se předpokládá s implicitním dodáním míst.


\section{Návrh reprezentace grafu}
\indent \indent Vztah mezi jednotlivými přechody lze vyjádřit jako vztah jednoho přechodu k druhému přechodu nebo k přechodům, do kterých se lze dostat přes místo, do nějž výchozí přechod ústí. Tento vztah lze vyjádřit posloupností výchozího přechodu a dosažitelných přechodů z míst do nichž vyústil výchozí přechod. Abych mohl říct, že tyto posloupnosti jsou opravdu vztahy grafu, je třeba nějakým identifikátorem označit začátek a konec, ve kterých je jejich platnost.


\section{Počáteční zakódování}
\indent \indent Další náležitost, která má charakterizovat signálově přechodový graf je počáteční stavové zakódování. Zakódování je důležité pro přiřazení binárního ohodnocení jednotlivých stavů stavového grafu při transformaci.


\section{Návrh reprezentace počátečního zakódování}
\indent \indent V textovém popisu by se měl vyskytnout identifikátor, podle něho budu moci určit, že se bude jednat o posloupnost znaků, vyjadřující binární zakódování počátečního stavu.


\section{Vstupy, výstupy a interní signály}
\indent \indent Pro VHDL kód, jež by měl být výstupem a pro generování přechodových rovnic je nezbytné, aby byly v textu rozlišeny vstupní, výstupní a interní signály. Měl bych poznamenat, že signál se může vyskytovat jen pod jednou identifikací, jinými slovy není možné, aby signál zároveň patřil mezi vstupy a výstupy nebo mezi jiné možné kombinace.


\section{Návrh reprezentace vstupů, výstupů a interních signálů}
\indent \indent Opět by bylo vhodné do textu zařadit identifikátor, jež by oznamoval počátek  posloupnosti pojmenování a  identifikoval by sounáležitost signálu s danou sortou. A to konkrétně zařazení do sorty vstupních, výstupní nebo interních signálů. 


\section{Marking}
\indent \indent Aby graf měl všechny náležitosti a počítač měl všechny údaje potřebné pro transformaci, je potřeba dodat tokeny na správná místa. Místa s tokeny jsou uloženy v množině \textit{marking}.  Místa jsou v programu implicitně generována. Označení místa tokenem se tedy musí provádět za pomocí dvojice přechodů, mezi nimiž se místo nachází.


\section{Návrh přidělování tokenů}
\indent \indent Začátek řádku bude identifikován identifikátorem za nímž bude následovat posloupnost znaků udávající místa obsahující token . V posloupnosti se budou vyskytovat dvojice přechodů, které budou označovat místa s tokenem. První přechod dvojice bude vstupní přechod místa, druhý přechod dvojice bude výstupní přechod daného místa.


\section{Modul zpracování textu}
\indent \indent Je třeba vytvořit třídu nebo skupinu tříd, které se budou starat o zpracovaní vstupního textu. Ve vstupním textu se obvykle vyskytuje identifikátor, jež označuje začátek posloupnosti označení, obvykle oddělených mezerou. \hbox{Vycházíme-li} z předpokladu, že identifikátor je jistý druh příkazu, pak můžeme identifikátor označit za příkaz a posloupnost znaků označení za argumenty příkazu. 
Existuje jeden případ, kdy argumenty nejsou uvedeny příkazem. Jedná se o samotné vztahy přechodů, kterými se takto popisuje graf. Abych mohl samotné argumenty použít, je potřeba jej povolit samostatným příkazem. 



\section{Návrh modulu pro zpracování textu}
\indent \indent Bylo by vhodné, aby třídy obsahovaly metody pro pársování textu, jež by byly schopny naparsovat příkaz i z jeho argumenty do nějaké STL šablony, nejlépe fronty. První položka by signalizovala příkaz a ostatní položky argumenty. Jednotlivé dílčí fronty, obsahující příkaz a argumenty, by na základě příkazu, byly schopny  předat argumenty ke zpracování a vytvořily by datovou strukturu reprezentující signálově přechodový graf.


\section{Modul pro zpracování příkazů}
\indent \indent Mělo by se jednat o třídu, která bude zpracovávat jednotlivé příkazy přicházející z modulu pro zpracování textu. Metody, které by odpovídaly jednotlivým příkazům, by zpracovávaly jednotlivé argumenty podle požadavku příkazu. Cílem tohoto modulu by mělo být vytvoření datového obrazu signálově přechodového grafu. Metody by se měly starat o ukládání informací, o  jaké signály jde, jestli vstupní, výstupní nebo interní, do dané datové struktury. Dále by měly ukládat do struktury data o přechodech a místech a vztahy mezi nimi. Měly by označovat místa tokenama.


\section{Návrh modulu pro zpracování příkazů}
\indent \indent Struktura, která by měla reprezentovat signálově přechodový graf v počítači, by měla obsahovat dvě pole  STL vektory. V jednom by se měly ukládat ukazatele na struktury obsahující informace o místech a v druhém poli ukazatele nesoucí informace o přechodech. Vzájemné vztahy přechodů a míst by měly být vyjádřeny přes indexy polí, ukazující z pole přechodů do pole míst a naopak. Nosná struktura by měla dále nést informaci o zakódování počátečního stavu a název signálu. Metody, které budou v daném modulu, se budou starat o naplňování jednotlivých proměnných a jejich inicializaci. Konkrétně hovořím o vytváření struktur místa a přechodů a jejich začlenění do nosné konstrukce a vyjádření jejich vztahu přes pole nosné konstrukce. 


\section{Modul pro transformaci}
\indent \indent Vstupem modulu je struktura popisující signálově přechodový graf. Cílem transformace by mělo být naplnění struktury daty, které reprezentují stavový graf. Modul by měl obsahovat algoritmus transformace signálově přechodového grafu na stavový graf. Algoritmus je založen na matematickém vyjádření, o kterém byla již řeč. V matematickém modelu, není implicitně naznačeno posouvání tokenu, proto bude třeba se o tento problém postarat. 


\section{Návrh modulu pro transformaci}
\indent \indent Je třeba stanovit reprezentaci množin vyskytující se v algoritmu pro transformaci. Pro většinu množin bude vhodné použít STL šablonu a to konkrétně frontu. Pro zásobník opět použijeme STL šablonu, ale tentokrát by se mělo jednat o šablonu pro zásobník tzv. Stack. Do zásobníku by se měla umísťovat struktura. Tato struktura by měla nést data o binárním zakódování stavu, množině míst obsahující tokeny a množinu vybraných přechodů. Struktury v zásobníku nesou informace, které jsou důležité pro větvení grafu a dávání jednotlivých míst dohromady.  
Bude potřeba metoda pro posouvání tokenu ve struktuře popisující signálově přechodový graf.
Dále bude potřeba vybírat aktivní přechod, vytvořit množinu obsahující přechody, které na vstupních místech mají tokeny. Dále inicializovat množinu míst s tokeny.  Výsledkem transformace má být stavový graf, proto je potřeba vytvořit struktury, ve kterých se budou nést příslušné data o grafu. Stavový graf by se měl skládat ze dvou základních struktur. Jedné nosné struktury, která by nesla struktury reprezentující jednotlivé stavy. Druhé struktury nesoucí informace o jednom stavu stavového grafu. Stav by měl minimálně obsahovat následující informace: zakódování stavu,  vztah k ostatním stavům a informace o přechodech. Důležitou metodou třídy by měla být metoda pro porovnávání stavů stavového grafu se stavem, který má byt přidán. Pokud se porovnávaný stav ve stavech vyskytuje, měla by metoda tuto skutečnost oznámit. 


\section{Modul pro vytvoření regionů}
\indent \indent Cílem modulu regionů je vytvořit čtyři základní regiony pro každý vstupní a interní signál. Do regionů budou vkládány binární zakódovaní stavů stavového grafu. Binární zakódování stavu představuje jeden term. Jedna z proměnných v termu představuje hodnotu vybraného signálu. Pokud se se hodnota signálu v následujícím stavu změní, pak binární zakódování výchozího stavu vložíme do ER, jinak binární zakódování vložíme do QR-.



\section{Návrh modulu pro vytváření regionů}
\indent \indent Je třeba projít všechny stavy stavového grafu pro daný signál. Informaci o stavech nese struktura reprezentující stavový graf. Při procházení grafu bude docházet k přidávání binárních zakódování do příslušných regionů . Dále je potřeba naimplementovat metodu starající se o jednoznačnost přiřazení stavů do regionu, jinými slovy, aby ve všech čtyřech regionech bylo zakódování stavu pouze jednou. Struktura, která bude nést informace o regionech, by se měla dělit do dvou částí. Jedna struktura by měla být nosná a druhá struktura by měla nést informace pro daný signál. Struktura pro daný signál by měla obsahovat minimálně 4 pole odpovídající jednotlivým regionům, v nichž by mělo být umístěno zakódovaní jednotlivých stavů. Nosná struktura by měla nést pole struktur pro jednotlivé signály. Pokud hovořím o jednotlivých signálech, pak se jedná o signály výstupní a interní. Výsledkem tohoto modulu bude struktura nesoucí informace o signálech a regionech s nimiž jsou spojené.


\section{Modul pro minimalizaci}
\indent \indent Cílem modulu je nalézt nejjednodušší vyjádření logické funkce.  Aby byla funkce co nejvíce minimální musí mít minimální počet proměnných v každém termu.  Funkce, které chci získat by měly být v disjunktivní formě. Vstupem modulu jsou regiony pro dané signály. Pro daný signál se snažím najít  funkci, která pokrývá jedničky, tak i funkci, která pokrývá nuly. Logika získaná z těchto funkcí bude předřazena před vstupy \hbox{C-elementu}. Konkrétně pro vstup Set 
\hbox{C-elementu} bude použita logika získaná z funkce pokrývající jedničkové stavy a don't care a pro vstup Reset \hbox{C-element} bude použita logika získaná z funkce pokrývající nuly a don't care. Pokud po minimalizaci budou funkce obsahovat jednu proměnou v termu a proměnná se pro funkci  Reset bude lišit negací od proměnné ve funkci Set, pak mohu \hbox{C-element} vynechat . Term se vždy minimalizuje kolem stavů z excitovaných regionů pro daný signál. Funkci pro Set resp. Reset,  pak tvoří součet termů získaných po minimalizaci z ER+(a) resp ER-(a). Pokud funkce  Set a Reset obsahují více jak jeden minterm, je potřeba prověřit, zda mintermy z jedné funkce nejsou obsaženy v mintermech druhé vstupní funkce. Jestliže dojde ke shodě, musím tento problém odstranit, jinak by mohlo dojít k neočekávanému nastavení nového stavu na \hbox{C-elementu}. Odstranění provedu pomocí monotonního pokrytí. Výsledkem modulu by měly být dvě množiny, ve kterých jsou uchovány mintermy pro Reset a pro Set pro daný signál.

\section{Důvody použití vlastního minimalizačního algoritmu}
\indent \indent Pro minimalizaci budu používat vlastní algoritmus, jelikož program je implementovaný v jazyce C++  a nebylo by vhodné, abych musel připravovat pro každý term v excitovaném regionu výstupní soubor jako vstup pro externí minimalizátor. Navíc bych musel získávat data zase zpět do programu, přičemž bych musel rozdělit celistvost implementace programu na dvě části. Nezbytnou součástí programu by musel být externí minimalizátor, čímž by se porušila kompaktnost programu a přenositelnost. Posledním důvodem, proč se nevyplatí používat externí minimalizátor je, že pro zhruba 20 vstupních proměnných jsem schopen postupnou expanzí dosáhnout přibližně stejných výsledků jako u externích minimalizátorů. Vycházím-li z grafů, které jsou na ATACS, pak průměrný počet vstupních proměnných se pohybuje okolo 10.

\section{Algoritmus minimalizace}
\indent \indent Algoritmus je založen na porovnání termů z ER+(a) resp. ER-(a) s termy v ER-(a) a QR-(a) resp. ER+(a) a QR+(a). Nejprve vyberu term z ER+, který budu porovnávat s termy z ER- a QR-. Vybraný term porovnávám s porovnávanými termy následovně. Postupně vynechám jednu proměnnou ve vybraném termu a zbývající proměnné porovnám s odpovídajícími proměnnými v porovnávaných termech. Vynechávání se provádí od levé proměnné termu. Pokud pro vybraný term s vynechanou proměnnou narazím na shodu všech zbývajících proměnných v některém termu, pak vynechanou proměnou nemohu vynechat. V opačném případě mohu proměnou vypustit pro další  porovnání. Nevynechané proměnné na konci algoritmu tvoří minterm. Porovnávací proces provádím pro všechny termy z ER+. Stejný postup aplikuji pro prvky z ER-, které porovnávám s prvky z ER+ a QR+.


\section{Návrh pro modul minimalizace}
\indent \indent Je třeba vytvořit metody, které budou zpracovávat strukturu nesoucí data o signálech a jejích regionech, a taky metody, které budou realizovat algoritmus minimalizace termů.  Je potřeba realizovat procházení celé struktury nesoucí informace o regionech signálu. Pro každý signál, vzít excitované regiony a jejich termy nechat projít algoritmem pro minimalizaci termů. Výsledek pak přidat do struktury nesoucí informace o Reset a Set množině pro dané výstupní nebo interní signály. Proto potřebuji zavést dvě struktury, kde jedna bude nést informace o jednom signálu a druhá struktura bude nosná. Struktura, která bude nést data pro jeden signál musí obsahovat minimálně množiny Reset a Set, kde se budou ukládat minimalizované termy. Všechny termy v dané množině, budou tvořit funkci disjunktivní formy. Další metoda, která by se měla v modulu vyskytovat, je metoda pro porovnání mintermů a pro vytvoření monotonního pokrytí.


\section{Návrh algoritmu}
\indent \indent Vytvořím metodu, která bude provádět výše zmíněný algoritmus pro minimalizaci. 
Metoda by měla umět signalizovat vynechání proměnných v termu. Pro nejpravější proměnnou je potřeba projít zbytek termu v opačném směru expanze.


\section{Výstup programu}
\indent \indent Výstupem programu by měl být soubor obsahující VHDL kód. Kód, který mám vygenerovat by měl zohledňovat vstupy a výstupy, které by se měly objevit na entitě VHDL, jež popisuje vstupy. Interní signály by měly být předefinované ještě před popisem celého těla architektury VHDL. Tělo architektury ve VHDL kódu by mělo obsahovat vztahy mezi vstupy, výstupy a interními signály. Tyto vztahy mohou obsahovat popis přiřazení signálu, popis logiky mezi, kterou mají signály projít a naportování  signálu na komponentu popisující chování \hbox{C-elementu}. 


\section{Návrh výstupu programu}
\indent \indent Pro entitu VHDL popisující signály, které patří mezi vstupní či výstupní, budu přidávat před dané signály \textit{in} nebo \textit{out} jako součást názvu. Všechny signály vstupní, výstupní nebo interní nadefinuji před samotné tělo architektury uvozeným begin a navíc přidám ještě pomocné signály, které budou vstupní hodnotou pro Set a Reset C-elementu pro daný signál. V samotném těle architektury ve VHDL kódu budou popsány vztahy jednotlivých hradel ,   instance C-elementu, portace. 


\section{Modul pro generování VHDL }
\indent \indent Vstupem modulu bude struktura nesoucí informace o signále a s nimi spjaté množiny Set a Reset pro daný signál. Modul by měl nejprve vygenerovat vstupní a výstupní signály pro entitu. Měl by vygenerovat pomocné signály a následně přejít ke generování popisu logiky a vztahu signálů, mělo by dojít k naportování na \hbox{C-element}. Výsledkem bude výstupní soubor  obsahující VHDL kód, jež je popsán výše.


\section{Návrh modulu pro generování VHDL}
\indent \indent Modul by měl obsahovat metody tříd, které jsou schopny vygenerovat kód pro popis vstupu a výstupu. Metody by měly generovat pomocné a interní signály. Musí obsahovat metody pro procházení struktur nesoucí informace o signálech a regionech a generovat kód pro případné naportování na \hbox{C-element}.\hbox{C-elementy} budou vytvářeny jako instance ve VHDL kódu, instance bude vycházet z předlohy, jež je uložena v souboru cm.vhd. Musí obsahovat metodu pro zápis kódu do souboru.
