Jelikož je úkolem vytvořit generátor, který generuje 3 odlišné formy logického obvodu, rozhodl jsem se vytvořit 3 oddělené programy. Ty se budou moci specializovat jen na daný problém a tím pádem ho efektivněji řešit. První část problému již řeší program {\bf genpla}, generátor řešící druhou část jsem vytvářel pod názvem {\bf genstate} a poslední generátor se jmenuje {\bf gennetwork}.
Pro spravný návrh všech funkcí programů a hlavně jejich vnitřní implentaci je potřeba důkladně projít všechny požadavky a řádně zvážit všechny možnosti řešení. Proto zde nejprve popíši formáty výstupních souborů, které z nemalé části ovlivnily tuto volbu. 
\section{Formáty výstupních souborů}

Všechny zde popisované a používané formáty jsou textové. To znamená, že jsou při prohlížení souboru pro člověka čitelné bez jakýchkoliv úprav.
\subsection{Formát PLA}

Formát je používán ve výstupu genpla. Popisoval jsem ho již v Bakalářské práci \cite{Bakal}. Jelikož je důležitý i pro pochopení dalšího formátu používaného v genstate, popíši ho i zde. Kompletní popis lze stáhnout ve zdorjovém kódu ESPRESSa na \cite{VLSI}.

PLA tabulka se skládá z klíčových slov počínající tečkou a jedné alfanumerické matice, kde každý řádek odpovídá jednomu termu a každý sloupeček odpovídá jedné vstupní nebo výstupní proměnné. Ve směru zleva do prava jsou nejdřív uvedeny všechny vstupní proměnné, až poté všechny výstupní. 

Symboly užité ve vstupní části matice:
\bitem
\item "0" značí, že P-term obsahuje negovaný korespondující literál
\item	"1" značí, že P-term obsahuje korespondující literál. 
\item	"-" značí, že P-term korespondující literál vůbec neobsahuje. tzv. don't care
\eitem

{\bf Příklad PLA --- 4 vstupy, 2 výstupy, 4 termy:}

\minrad
\begin{verbatim}
.i 4
.o 2
.p 4
.type fr
-011 01
1--0 10
1111 00
100- 10
.e
\end{verbatim}

\normrad
\subsection{Formát KISS}
Formát KISS je rozšíření PLA formátu o sekvenční chování obvodu. Je definován v rámci formátu BLIF pro sekvenční obvody. Jeho úplnou specifikaci nalezneme zde \cite{BLIF}. Jde vlastně o PLA tabulku, kde každý term znamená přechod z jednoho stavu do druhého.

Na počátku souboru je několik klíčových slov uvozených tečkou. Dále se nachází postupně na každém řádku jeden term pro jeden přechod v automatu. Řádek obsahuje:
\bitem 
\item vektor ohodnocení vstupních proměnných --- význam symbolů jako v PLA
\item název stavu ze kterého přecházíme
\item název stavu do kterého přecházíme
\item vektor ohodnocení výstupních proměnných při uskutečněném přechodu --- význam symbolů jako v PLA
\eitem

{\bf Ukázka jednoduchého úplného deterministického automatu ve formátu KISS --- 1 vstup, 2 výstupy, 3 stavy, 6 termů}

\minrad
\begin{verbatim}
.i 1
.o 1
.p 6
.s 3
.r START
0   START  state1 1
1   START  state2 0
1  state1   START 0
0  state1  state1 0
0  state2   START 0
1  state2  state1 1
.e
\end{verbatim}
\normrad
\subsection{Formát BLIF}
Tetno formát již popisuje hierarchii kombinačních bloků a jejich vzájemné propojení v logickém obvodě. Každý blok má definovány názvy vstupů a výstupů a logická funkce bloku je definována jako jeho booleovská funkce. K popisu funkce se používá část již vysvětleného formátu PLA. Úplnou specifikaci nalezneme v \cite{BLIF}. Zde vysvětlím jen \uv{pro nás} důležité věci.

Jako v předchozích případech začíná formát několika klíčovými slovy uvedenými tečkou. Zde jsou uvedeny globální parametry pro celý obvod, včetně názvů všech vstupů a výstupů. Následují postupně vypsané všechny logické bloky v obvodu. Každý blok je uvozen klíčovým slovem ".names", následován na stejném řádku názvy postupně všech spojů, které jsou pro tento blok logickými vstupy a vzápětí i výstupy. Na dalších řádcích je uvedena alfanumerická matice vyjadřující booleovskou funkci daného bloku, jak je uvedeno již ve formátu PLA. Formát je ukončen klíčovým slovem ".end"

{\bf Ukázka jednoduchého logického obvodu ze sítí hradel. Obvod má 3 vstupy, 1 výstup, 2 dvouvstupové hradla (NOR+NAND)}
\minrad
\begin{verbatim}
.model main
.inputs i1 i2 i3
.outputs o1
.names i1 i2 q1
00 1
.names i3 q1 o1
0- 1
-0 1
.end
\end{verbatim}
\normrad

\subsection{Formát BENCH}
Podobně jako BLIF, tento formát popisuje zapojení jednotlivých logických bloků v rámci celé sítě. Ovšem zde se za bloky berou pouze jednoduchá hradla a to AND, NAND, OR, NOR, XOR, XNOR a BUF. Formát je proto velmi jednoduchý a skládá se pouze z názvů vstupů a výstupů obvodu a seznamu hradel s jejich zapojením. 

Každý vstup je uveden na nové řádce, kde je jeho název uzavřen v kulatých závorkách za klíčovým slovem "INPUT". Podobně je každý výstup uveden v závorkách za slovem "OUTPUT". Každé hradlo je zapsáno na samostatném řádku kdy jeho výstupu přiřazujeme výslednou funkční hodnotu jeho vstupů. Jako název funkce je uveden název hradla. Nejlépe to bude vidět na následjícím příkladu.
  
{\bf Ukázka jednoduchého logického obvodu ze sítí hradel. Obvod má 3 vstupy, 1 výstup, 2 2-vstupové hradla (NOR+NAND) --- stejný příklad jako u formátu BLIF}

\minrad
\begin{verbatim}
INPUT(i1)
INPUT(i2)
INPUT(i3)
OUTPUT(o1)
q1 = NOR(i1, i2)
o1 = NAND(i3, q1)
\end{verbatim}
\normrad

\subsection{Formát SLIF}
Do programu jsem se rozhodl zavést ještě tento formát, který je velmi podobný formátu BLIF, avšak místo PLA matice k popisu booleovských funkcí daného bloku, používá jejich logický zápis. Konec řádku se zde ukončuje středníkem. Negace se v zápisu logické funkce vyjadřuje jako apostrof za negovaným výrazem.

{\bf Ukázka jednoduchého logického obvodu ze sítí hradel. Obvod má 3 vstupy, 1 výstup, 2 2-vstupové hradla (OR+NAND) --- stejný příklad jako u formátu BLIF}

\minrad
\begin{verbatim}
.model main ;
.inputs i1 i2 i3 ;
.outputs o1 ;
q1 = ( i1 + i2 )' ;
o1 = ( i1 i2 )' ;
.end
\end{verbatim}
\normrad
\section{Použité technologie}
Konzolovou aplikaci, jako je navrhovaný generátor bez jakéhokoliv grafického výstupu, lze vytvářet pomocí mnoha procedurálních i objektových programovacích jazyků. Poněvadž byl k vytvoření původního generátoru použit jazyk C++ s prostředím Borland C++ Bulider 6.0, takže výběr jiného jazyka (bez použití stávajícího kódu) se stal téměř nemožným. Zvolil jsem proto neměnit vývojový jazyk a psal jsem v něm oba generátory. Jelikož mi vývojové prostředí Borland není tak blízké, rozhodl jsem se pro vývojové prostředí Microsoft Visual studio 2005. Volba mezi objektovým nebo procedurálním programováním pro mě nebyla moc složitá, poněvadž přínos objektového programování na tak specifický úkol by nebyl nikterak výrazný v porovnání se zvětšením zdrojových kódů při zapouzdřování objektů. Navíc je mé osobě bližší procedurální přístup. Tudíž z vlastností C++ a objektů je použito jen minimum.
V projektech genpla a genstate byli použity některé knihovny a zdrojové kódy z minimalizátoru BOOM se svolením ing. Fišera. Projekt gennetwork byl vytvořen bez přídavných nestandartních knihoven, poněvadž všechny jeho datové struktury a algoritmy jsou implementovány přímo na míru.

Všechny tři generátory jsou tudíž vytvářeny programovacím jazykem C++ v prostředí Microsoft Visual studio 2005.

Jako další pomocné technologie jsem použil programy Rational od firmy IBM. Šlo především o program Purify, který za běhu kontroluje přístupy do paměti a hledá zápisy mimo alokovanou paměť a její správnou dealokaci. Používal jsem ho na předejití závažných těžko objevitelných chyb a především na kontrolu genpla.  

\section{genpla --- booleovská funkce}

U 1. genrátoru byly požadavky jasné a srozumitelné. Nejprve bylo nutné přenést hotový program do nově zvoleného prostředí a pomocí zvolené technologie, na analyzování paměti IBM Rational Purify, najít a odstranit nečekané pády programu.
 
Dalším úkolem k vyřešení bylo přidání kontroly duplicitních termů. Zde se nevyskytoval žádný zádrhel a proto bylo zvoleno řešení, které při zapnutí přepínače bude volat další kontrolní metodu, která otestuje přidávaný term vůči již hotovým na duplicitu. Pokud nastane duplicita, tak se term zahodí a zkusí se vygenerovat nový náhodný term.

V poslední řadě bylo za úkol optimalizovat kód. Zde jsem po důkladném prozkoumaní zjistil, že všechny kontroly, zda vygenerovaný term zařadit do výsledku, probíhají postupně. Tudíž se všechny již zařazené termy procházejí několikrát, podle toho které kontroly jsou zapnuté či nikoliv. Řešením tedy bylo veškeré kotroly zahrnout do jednoho průchodu již vytvořenými termy. Poněvadž se kontroly používají při každém vygenerovaném termu a jsou časově úměrné termům již vygenerovaným, tak se zdá, že by tato úprava mohla výrazně zvýšit efektivitu programu.

\section{genstate --- konečný automat}

\subsection{Definice}

Podle analýzy výstupního formátu jsem zjistil, že budeme generovat Mealyho synchronní konečný automat. Tzn. že výstup automatu je závislý pouze na vstupních proměnných a stavu ve kterém se automat nachází. Opakem je Mooreův automat kdy výstup automatu je závislý čistě jen na předchozím stavu automatu.

\subsubsection*{Ekvivalentní stavy}

Dále si vysvětlíme co je to ekvivalentní stav. Podle definice jsou dva stavy Q1 a Q2 automatu A ekvivalentní, pokud všechny možné posloupnosti různých kombinací vstupních proměnných, aplikované na automat A v počátečním stavu Q1, produkují na výstupu tytéž odezvy, jako kdyby byly aplikovány na automat A v počátečním stavu Q2. Skupiny ekvivalentních stavů tvoří tzv. třídy ekvivalence. Je zřejmé, že pokud třída ekvivalence obsahuje $n$ stavů, tak je $n-1$ stavů redundantních a tudíž je můžeme vyřadit. Všechny přechody do vyřazených stavů přepíšeme na přechod do stavu, který nám zbyl jako jediný v třídě ekvivalence.
Je jasné, že když tento postup otočíme tak budeme schopni vygenerovat libovolný počet tříd s libovolným počtem redundantních stavů. Tímto byl vyřešen problém s generováním ekvivalentních stavů.



\subsubsection*{Determinismus a úplnost}

Úplný automat je takový, který má v každém svém stavu definován přechod pro všechny kombinace nastavení vstupních proměnných.\\
Pod pojmem deterministický automat se myslí úplný automat, který nemá v rámci jednoho stavu 2 přechody, které odpovídají stejnému nastavení vstupních proměnných a zároveň mají nastaven odlišný následující stav. \\
Avšak v rámci této diplomové práce jsem od deterministického automatu nevyžadoval jeho úplnost. Vždy když budu mít na mysli úplný deterministický automat, tak to řádně uvedu.

\subsection{Grafové algoritmy}

Předem uvedu, že stavový automat se dá představit jako orieontovaný graf, kde jedntolivé stavy automatu jsou uzly grafy a přechody mezi nimi jsou reprezentovány jako orientované hrany grafu.\\
Při této představě můžeme požadovanou spojitost a jiné parametry automatu úspěšně řešit pomocí znamých grafových algoritmů. Graf úplného deterministického automatu zaobrazuje pro názornost obrázek~\ref{fig:stavautomat}

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=10cm]{stavautomat}
  \caption{Graf stavového automatu} 
  \label{fig:stavautomat}
\end{center}
\end{figure}


\subsubsection*{Spojitost}

Neorientovaný graf je spojitý, pokud se lze z libovolného uzlu grafu pomocí posloupnosti přechodů po jeho hranách, dostat do všech ostatních uzlů grafu.

U orientovaného grafu se analogicky definuje silná spojitost a ta je definována. Orientovaný graf je silně spojitý, pokud se lze mezi všemi uzly grafu pomocí posloupnosti přechodů po jeho orientovaných hranách, dostat do všech ostatních uzlů grafu a zpět.

Spojitost stavového automatu uvedená v požadavcích byla myšlena jako dosažitelnost libovolného stavu ze stavu počátečního. Tudíž nám postačí neorientovaný graf stavů a zajistit jeho spojitost. Jelikož v generátoru musí jít nastavit i počet přechodů, je potřeba zajistit spojitost s co nejmenším možným počtem přechodů. Proto jsem došel k závěru, že bych mohl využít algoritmů pro tvorbu kostry grafu. Tím získám spojitý automat s pouze $n-1$ počtem přechodů, kde $n$ je počet jeho stavů.

Triviální algoritmus na spojení všech prvků náhodnými spoji mi přišel velmi jednoduchý a málo náhodný. Algoritmus pracuje asi takto: Nejprve se utvoří prázdná množina uzlů $Q$ a množina všech uzlů $V$. Do množiny $Q$ se budou zařazovat již spojené uzly, v množině $V$ jsou doposud nespojené uzly. Algoritmus vždy vybere náhodný prvek z množiny $V$ a vytvoří mezi ním a náhodným prvkem z množiny $Q$ spoj. Poté přeřadí uzel z množiny $V$ do množiny $Q$. Pokud je množina $Q$ prázdná algoritmus končí. 

Vymýšlel jsem proto i jiná řešení založená na předgenerování spojitého grafu trivialním automatem s nadbytkem hran, jejich ohodnocením a poté puštěním algoritmu na tvorbu minimální kostry grafu.

\subsubsection*{Minimální kostra grafu}

Pro minimální kostru grafu jsou nejznámější 3 lišící se algortimy.

{\bf Kruskalův algoritmus}

Jde o trivialní algoritmus, budem postupně tvořit množinu hran H s pomocí vzestupně seřazené množiny všech hran $E$ podle ohodnocení.\\ Postup je v následujících krocích:
\bitem 
\item vyjme se z množiny $E$ nejméně ohodnocená hrana $k$ a vloží se do množiny $H$
\item pokud množina $H$ obsahuje kružnici tak se hrana $k$ vyřadí z množiny $H$
\eitem Tento proces se opakuje dokud v množině $H$ není $N-1$ hran, kde $N$ je počet uzlů grafu. Množina $H$ spolu se všemi uzly grafu tvoří minimální kostru.

{\bf Jarníkův alglritmus}

Zde se vytvoří $N$ množin pojmenovaných $Q1..QN$, kde každá obsahuje právě jeden uzel grafu. Potřebujeme ještě seřazenou množinu hran $E$ podle ohodnocení a jednu prázdnou množinu $M$. Algoritmus probíhá takto.

\bitem
\item vyjmeme z množiny $E$ první hranu $k$. Hrana $k$ spojuje uzly $U$ a $V$
\item pokud $U$ a $V$ leží v jiné množině, tak množiny spojíme a hranu $k$ zařadíme do množiny $M$
\eitem
Algoritmus pokračuje dokud nám nezbude pouze jedna neprázdná množina $Qn$. Kostra grafu je určena množinou hran $M$ se všemi uzly původního grafu.

{\bf Borůvkův algoritmus}

Je velice podobný Jarníkovu algoritmu, ovšem v každé iteraci hledá nejméně ohodnocené hrany, které vedou z každé neprázdné množiny $Qi$ do jiné neprázdné množiny $Qj$. Poté všechny množiny, mezi kterými byla nalezena hrana, spojí dohromady a všechny tyto hrany přidá do výsledku. Algoritmus pokračuje dokud nezůstane pouze jediná neprázdná množina $Qn$.

{\bf Volba algoritmu}

Všechny 3 algoritmy, podávají stejný výsledek a používají seznam řazených hran. Rozdíl je akorát v tom, jakým způsobem hledají hrany na přidání a jak kontrolují, aby se nepřidala přebytečná hrana. Nejvhodnější pro počítačovou implementaci je Jarníkův algoritmus, poněvadž spojování množin je jednodušší, než hledat kružnici z hran. O proti Borůvkovu algoritmu nemusí složitě kontrolovat více hran zároveň. Proto budu implementovat Jarníkův algoritmus.  

\subsubsection*{Koncovost a Dostupnost}

Problém, aby do každého stavu a z každého stavu vedl alespoň jeden přechod v celém automatu, je celkem triviální. Nejlepším řešením je projít všechny stavy a doplnit náhodně chybějící přechody. 

\subsection{Generování PLA pro přechody}

Ve výstupním formátu jsou přechody automatu definovány rozšířenou PLA tabulkou, proto bude vhodné použít již hotovou 1.část generátoru na generování tabulky, kterou pak doplníme o přechody. Budeme muset generovat $N$ tabulek, kde $N$ je počet generovaných stavů. V případě ekvivalentních stavů, budou tabulky (až na ono doplnění o přechody) identické.

\section{gennetwork --- síť logických hradel}
 
Ze zadaných požadavků je jasné, že nějaká přímo řízená syntéza obvodu, která by generovala obvod se všemi požadovanými parametry, je nemožná. Proto je jasné, že použijeme některé optimalizační metody na dosažení kýžených parametrů obvodu. Při všech optimalizačních metodách je však potřeba vycházet z nějakého již hotového řešení a toto řešení různými metodami modifikovat a zušlechťovat jeho parametry. Proto bylo důležité analyzovat i tvorbu triviálního řešení.  

\subsection{Triviální obvod}

Nejprve bylo důležité rozhodnout, které parametry budeme optimalizačními algortimy přizpůsobovat a které budou v průběhu neměnné. Volba těchto pevných parametrů úzce souvisí s volbou optimalizačního algoritmu a obráceně. Generátor by měl umět pracovat s těmito parametry:
\bitem 
\item počet vstupů
\item počet výstupů
\item počet hradel
\item typy generovaných hradel
\item maximální fan-in jednotlivých hradel
\item maximální větvení spojů
\item pravděpodobnsot výskytu jednotlivých hradel
\item počet úrovní hradel
\item celková řiditelnost
\item celková pozorovatelnost
\item celková testovatelnost
\eitem

Parametry jsou seřazeny podle jednoduchosti jejich kotroly při syntéze triviálního obvodu. Počet vstupů lze velmi jednoduše kontrolovat a dodržet v průběhu syntézy, nežli globální parametry jako je testovatelnost, které nemohou být známé dokud není celý obvod zapojen.

Od začátku jsem se snažil generovat triviální obvod podle co nejvíce kritérií, abych optimalizačnímu algortimu co nejvíce snížil dimenzi prohledávaného prostoru. Zvolil jsem proto všechny parametry v seznamu, až po maximální větvení spojů-včetně, za pevné. A všechny triviální obvody je museli splňovat. Zároveň byl vybrán a upraven genetický algortimus takový, který by tyto parametry ve svém průběhu již neměnil. 

Tím ovšem vznikl problém, že ne všechny kombinace parametrů vytvoří jakkoliv zapojitelný obvod. Uvedu extrémní případ: pro kombinaci 10-ti vstupů, 1 výstupu a 3 dvouvstupových hradel nelze vytovřit obvod. U tohoto případu je to očividné. Ovšem u případů, kde se bude zadávat maximální větvení spojů na nízké hodnoty, již to tak očividné není. V tomto případě nastane při větším počtu hradel problém, že je nebudeme mít kam zapojit. Těchto případů je ovšem tak mizivé množství, že výhody které přinese méně proměnlivých parametrů při optimalizaci, tuto nevýhodu vynahradí. Správné nastavení těchto parametrů bylo přenecháno na rozumu uživatele. Generátor v případě nelogicky zadaných parametrů může uváznout v nekonečné nesplnitelné smyčce, nebo se může ukončit bez výsledky a v ojedinělých případech může vyvolat vyjímku a ukončit se. Toto záleží v jaké části se objeví při generování problém.

Triviální obvod se také generuje s ohledem na pravděpodobnost výskytu jednotlivých hradel, avšak už je striktně nekontroluje. Možnost kontroly je ponechána optimalizaci. 

Při nezadání jiných parametrů na vstupu generátoru, než výše zmíněných pevných paramterů, tak se optimalizační část vůbec nepouští. Použije se přímo vygenerovaný triviální obvod. 

\subsection{Optimalizační algoritmy}

Všechny druhy optimalizace jsou založeny na hledání globálního maxima nějaké ohodnocovací funkce, která je závislá na všech optimalizačních kritériích. Počet takto zvolených kritérií nazýváme dimenze stavového prostoru optimalizace. Všechny platné kombinace oněch kritérií vytvářejí celý stavový prostor, ve kterém se hledá nejlepší řešení daného problému. Je vhodné se snažit udržet dimenzi stavového prostoru co nejmenší, poněvadž prostor roste s jeho dimenzí zpravidla exponencionálně. Protože neznáme a ani nejsme schopní dopředu určit které stavy jsou řešením, můžeme vyloučit algoritmy, které systematicky procházejí stavový prostor. Budeme se věnovat jen algoritmům inspirovanými přírodními procesy.
Algorimty se vzájemně liší především způsobem procházení tohoto prostoru tzv. pohybem v prostoru. Tyto pohyby se uskutečňují především aplikací nějakých jednoduchých operací na již vytvořená řešení. 

Při výběru jsem zvažoval tyto algoritmy :
\bitem
\item Simulované žíhání
\item Genetické algoritmy
\item Mravenčí kolonie
\eitem

Při výběru bylo nejdůležitější jestli vůbec dokážeme splnit nároky na procházení stavovým prostorem kladené jednotlivými algoritmy. Simulované žíhání, stejně jako Mravenčí kolonie, klade nároky na tvorbu řešení v pevně zadaném okolí problému, což nemůžeme při tvorbě obvodů nikterak kloudně splnit. Zůstal nám tedy pouze genetický algoritmus, který ovšem klade nároky na schopnost jednoznačně převést --- zakódovat řešení problému na jistou posloupnost znaků --- tzv chromosom.

\subsection{Genetické algoritmy}

Genetický algoritmus je pokročilá metoda optimalizace založená na principu genetiky, především na přírodním výběru. Jejím principem je udržovat si konstantně velkou sadu řešení --- tzv populaci a opakovaným aplikovaním různých metod docílit její evoluci. Rozlišení kvality jedince v rámci populace se provádí fitness funkcí, která převede všechny otpimalizační kritéria na jednorozměrnou proměnnou, která určuje míru splnění těchto kritérií. Nejdůležitější metodou k evoluci populace je selekce silných jedinců. Jejich vzájemným křížením vniká nový jedinec, který má velkou pravděpodobnost, že bude alespoň stejně kvalitní jako jeho rodiče. Dalším důležitým prvkem je přežití nejsilnějších jedinců do další generace. Důležitým aspektem je fakt, že pro správný chod algoritmu, musíme mít hotovou jednu populaci jedinců, kteří řeší problém alespoň triviálním způsobem. Celý algoritmus probíhá asi takto:

\benum
\item vygenerování triviální populace 
\item zakódování jedinců do podoby chromozomu
\item selekce silných jedinců
\item křížení vybraných jedinců
\item mutace vytvořených jedinců
\item nahrazení původní populace nově vytvořenými jedinci
\item pokud není splněno ukončující kritérium opakuj od bodu 2.
\eenum

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=8cm]{evol1}
  \caption{Průběh genetického algoritmu} 
  \label{fig:evol1}
\end{center}
\end{figure}

Opakující se fáze je znázorněna na obrázku~\ref{fig:evol1}. Počáteční populace je vygenerována s pomocí triviálních obvodů popsaných výše.

\subsubsection*{Kódování jedinců}
Problém genetických algoritmů je v tom, že musíme mít popsáno řešení daného problému tzv. chromozómem. Nejlépe se v počítačích prezentuje chromozóm, jako binární pole stejné délky pro všechna řešení. Různá řešení se liší v jednotlivých bitech tohoto chromozómu --- genech. V praxi ale nemusí být zakódování tak úplně přesné, pokud k tomu upravíme i zbylé části algoritmu. Za geny tak můžeme volit libovolné prvky, které dohromady reflektují určité řešení problému a mají v rámci různých řešení stejný význam.

Při konkrétní aplikaci na problém zapojení obvodů, bylo na snadě volit za geny hradla v obvodu a jako pořadí genu v chromozómu zvolit úroveň odpovídajícího hradla. Tím nám vzniknul chromozóm s pevnou délkou reprezentující pořadí hradel v obvodu, avšak nereprezentoval jejich vzájemné zapojení. Zde může nastat otázka zda to vadí nebo ne. Vadit by to mohlo v části křížení a mutace,kde uvedu konkrétní řešení tohoto problému.

\subsubsection*{Ohodnocení jedinců}

V průběhu genetického algortimu je nutné nějak jednoznačně určit jak moc je jedinec \uv{dobrým} řešením. Na tom stojí celé fungovaní genetických algoritmů a je proto důležité vymyslet vhodnou funkci, která převede množinu všech kladených požadavků na jedince na jednorozměrnou proměnou. Funkce má buď omezený obor hodnot a tudíž víme na kolik splňuje daný jedinec požadavky. Nebo může mít nedefinovaný obor hodnot, v tom případě dokážeme pouze posoudit který ze dvou jedinců je splňuje více.

Rozhodl jsem se implementovat verzi, kdy zhruba máme představu z hodnoty funkce, jak si jedinec vede. Funkce bude volena jako vážený součet všech slože, které budou počítány z jednotlivých kladených optimalizačních kritérií. Podrobněji v kapitole implementace~\ref{imp:fitness}
 
\subsubsection*{Selekce jedinců}

Selekce jedinců, nebo-li výběr jedinců ke křížení, může probíhat několika způsoby. Většina se z nich řídí teorii Darwinovské evoluce -  \uv{nejlepší přežijí a stvoří potomky}. Zde nastíním několik základních přístupů:
\bitem
\item turnaj z $n$ --- náhodně se zvolí $n$ jedinců z populace a nejsilnější z nich je vybrán za vítěze, turnaj se opakuje dokud nemáme požadovaný počet jedinců
\item ruletový výběr --- pravděpodobnost výběru jednotlivých jedinců se volí v závislosti na jejich \uv{síle} v populaci, náhodně se poté vybere požadovaný počet jedinců podle jejich určené pravděpodobnosti
\item další metody zaměřené na neopakujícím se výběru jedinců apod.
\eitem

Nejčastěji se použivá metoda turnaje jedinců, kde můžeme volbou $n$ dobře volit požadovaný selekční tlak. Selekčním tlakem se myslí pravděpodobnost výběru silnějších jedinců. Proto jsem se rozhodl implementovat metodu turnaj ze dvou. Pro náš problém totiž nepotřebujeme velký selekční tlak. Chceme spíše zachovat rozmanitost populace, než rychlou konvergenci k lokálnímu extrému ohodnocovací funkce.

V rámci selekce dochází také k elitismu. To je metoda která přenese několik nejsilnějších jedinců do nové populace. Tímto způsobem si ponecháváme v algortimu doposud nejlepší řešení daného problému.

\subsubsection*{Křížení jedinců}
Páry vybraných jedinců postupují do fáze křížení, kde se jejich geny v chromozomech vzájemně vymění. Metody křížení ovlivňují, jakým způsobem se to provede. Na obrázku~\ref{fig:krizeni} jsou graficky zobrazeny 3 základní typy křížení na binárním genetickém algoritmu. Jednotlivé bity představují geny v chromozómu. V jednobodovém křížení se oba rodiče rozdělí ve stejném místě, a prohodí si rozdělenou část chromozómu. Podobně je to i ve vícebodovém křížení. Zde se chromozóm rozdělí na n částí a rodiče si navzájem prohodí sudé části. Uniformní křížení je založeno na prohození náhodných genů. Křížením vzniknou dva noví potomci které se umístí do nové generace jedinců.

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=14cm]{krizeni}
  \caption{Různé druhy křížení} 
  \label{fig:krizeni}
\end{center}
\end{figure}

Pro náš problém bude nejlepší metoda jednobodového křížení. Poněvadž nemáme v chromozómu veškeré informace o jedinci, snažíme se udržet co nejvíce genů u sebe, abychom mohli informaci reprodukovat. Celou metodu jsme museli upravit tak, aby do potomků vložila co nejvíce nezakódovaných informací z rodičů (ohledně zapojení hradel) a zničenou část informace co nejvhodněji doplnila.

Celé to funguje tak, že se obvody obou rodičů rozpojí v náhodně zvoleném bodě a v potomcích je druhá část obvodu prohozena. Poté se snaží obě části propojit přes zbylé nezapojené vstupy a výstupy hradel. Pokud se to nepodaří, je potomek vyřazen z nové populace.

\subsubsection*{Mutace}

Standartní mutace je definována jako náhodná změna genu za jiný. Je určena většinou globální pravděpodobností, zda na nově vzniklém potomkovi dojde k mutaci či nikoliv. Mechanizmus mutace zaručuje určitou rozmanitost jedinců a zabraňuje možnosti degenerace populace.

V našem případě kódování jedinců, jsme museli rošířit působnost mutace nejen na náhodnou změnu genu, ale i na náhodnou změnu zapojení hradel. Všechny přístupy které jsem implementoval jsou uvedeny v kapitole~\ref{impl.mutace}

\subsubsection*{Ukončují kritérium} 

Genetický algoritmus je iterativní a tudíž se stále snaží zlepšovat výsledek dokud nenastane ukončující kritérium. Ty jsou zpravidla 3 druhy:
\bitem
\item statické kritérium --- je určen pevný limit po kterém se algoritmus ukončí, běžně se používá počet generací
\item dynamické kritérium kvality --- nejsilnější jedinec dosáhne zadané kvality řešení
\item dynamické kritérium času --- nejlepší řešení problému se nezmění po určitou dobu
\eitem

Je výhodné implementovat alespoň jedno statické a jedno dynamické kritérium a používat obě současně. Mohla by totiž nastat situace, že dané dynamické kritérium nejde splnit, a proto se používá zároveň i statické, abychom těmto situacím předešli. Po kladném vyhodnocení ukončujících podmínek je jako výstup z algoritmu dán nejsilnější jedinec v aktuální populaci. 

\subsection{Testovatelnost}

Obecně je testovatelnost definována jako schopnost obvodu být lépe (levněji,důkladněji) testován na jeho poruchy. Testovatelnost nejvíce ovlivňují dvě složky:
\bitem
\item řiditelnost
\item pozorovatelnost
\eitem

Řiditelnost spoje v obvodu je chápána jako schopnost ovlivnit jeho hodnotu pomocí různého ohodnocení vstupů. Pozorovatelností spoje se myslí schopnost zjistit jeho hodnotu na výstupech ovlivňováním pouze vstupů. Za úkol máme provést kvalitativní ohodnocení obvodu číslem, které bude určovat jeho snadnou testovatelnost resp. řiditelnost a pozorovatelnost. Obecně se dá testovatelnost rozdělit na kombinační a sekvenční. V této práci se budu věnovat jen kombinační části. Sekvenční část u metod vynecháme. 

Existují metody navržené pro obvody popsané od úrovně hradel až po vyšší úrovně popisu obvodu. Nás budou zajímat ty nejpodrobnější, řešící problém na úrovni logických hradel. 

\subsubsection*{Metoda SCOAP}
SCOAP \cite{clanek} je jedna z nejznámejších metod pro výpočet testovatelnosti. Metoda používá tzv. míry řiditelnosti a pozorovatelnosti. Ty reflektují obtížnost ovládání resp. pozorování konkrétních hodnot na vnitřních spojích obvodu. Vyšší hodnoty řiditelnosti resp. pozorovatelnosti indikují větší obtížnost této činnosti.
Pro každý spoj v obvodu jsou vypočteny tři hodnoty vyjadřujících míru jeho řiditelnosti a pozorovatelnosti:
\bitem
\item řiditelnost nuly na spoji x --- CC0(x)
\item řiditelnost jedničky na spoji x --- CC1(x)
\item pozorovatelnost spoje x --- CO(x)
\eitem

Tyto míry vyjadřují kolik je zhruba potřeba nastavit spojů v obvodě, abychom změnili resp. pozorovali hodnotu na daném spoji. Řiditelnost spojů se pohybuje  v rozmezí 1 (nejsnadněji) až nekonečno (nejtěžší) a Pozorovatelnost v mezích 0 (nejlehčí) až nekonečno (nejtěžší). Na obrázku~\ref{fig:scoap1} a \ref{fig:scoap2} jsou zobrazeny výpočty pro jedntolivá hradla. 


\begin{figure}[ht]
\begin{center}
  \includegraphics[width=12cm]{scoap1}
  \caption{SCOAP: Výpočet řiditelnosti} 
  \label{fig:scoap1}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=12cm]{scoap2}
  \caption{SCOAP: Výpočet pozorovatelnosti} 
  \label{fig:scoap2}
\end{center}
\end{figure}

Metoda postupuje asi takto:
\bitem
\item všem vstupům obvodu nastav CC0 = CC1 = 1, všem ostatním spojům CC0 = CC1 = ∞
\item postupně procházej obvod od vstupů obvodu a počítej řiditelnost pomocí rovnic na obrázku~\ref{fig:scoap1}
\item všem výstupům obvodu nastav CO = 0, ostatním spojům CO = ∞
\item postupuj od výstupů obvodu směrem ke vstupům a počítej pozorovatelnost pomocí rovnic na obrázku~\ref{fig:scoap2} 
\eitem

Časová složitost analýzy testovatelnosti pomocí SCOAP je lineární funkcí počtu hradel, to
z metody SCOAP činí atraktivní nástroj pro posuzování testovatelnosti.

\subsubsection*{CAMELOT}
\label{anal.CAMELOT}
CAMELOT \cite{CAM} je metodou založenou na hradlových koeficientech. Pro každý výstup hradla je předpočítána konstanta, kterou se násobí vstupní řiditelnosti resp. výstupní pozorovatelnosti. Metoda používá 3 složky, které  danému spoji x přiřazují jeho řiditelnost --- CY(x), pozorovatelnost --- CO(x) a testovatelnost --- T(x). Všechny složky jsou v intervalu $<0;1>$, kde 0 znamená, že odpovídající spoj není testovatelný (řiditelný, pozorovatelný), 1 znamená, že je testovatelný velmi jednoduše. 

Jedotlivé koeficienty hradel jsou počítány takto:
\bitem
\item CTF(y) je koeficient řiditelnosti výstupu y a je pro každé hradlo počítán zvlášť podle pravidla $$ CTF(y) = 1- |\frac{N(0)-N(1)}{N(0)+N(1)}|$$ N(0) resp. N(1) jsou počty vstupních kombinací, pro které výstup y nabývá hodnoty 0 resp. 1
\item OTF(x-y) je koeficient určující snadnost propagace hodnoty ze vstupu x na výstup y. 
$$ OTF(x-y) = \frac{N(SP:x-y)}{N(SP:x-y)+N(IP:x-y)} $$ 
kde N(SP:x-y) resp. N(IP:x-y) je počet citlivých nastavení vstupních kombinací kdy dochází k šíření resp. blokaci poruchy ze vstupu x na výstup y. 
\eitem  

Jednotlivé složky CY(x), OY(x) a T(x) se počítají:
$$ CY(y) = CTF(y) \times f(CY(x_1), . . . ,CY(x_k)) $$ kde $x_1$ ... $x_k$ jsou vstupy na kterých je výstup y závislý.
$$ OY(x) = OTF(x−y) \times OY(y) \times g(x_1, . . . , x_k) $$ kde $x_1$ ... $x_k$ jsou vstupy ns kterých je závislá propagace poruchy ze vstupu x na výstup y. 
$$ TY(x) = CY(x) \times OY(x)$$
 
Algoritmus probíhá v těchto krocích.
\bitem
\item příprava koeficientů v každém hradle, vstupům obvodu nastaví $CY(x) = 1$ ostaním spojům na 0, výstupům obvody nastaví $OY(x)=1$ ostatním spojům na 0 
\item postupujeme od vstupů k výstupům a počítáme hodnoty CY.
\item postupujeme od výstupů ke vstupům a počítáme OY a TY.
\item vypočteme celkové hodnoty CY, OY a TY pro obvod jako průměr příslušných hodnot ze všech spojů v obvodě.
\eitem

\subsubsection*{Normalizovaná metoda}
Poslední zajímavou metodu jsem objevil na internetu a je jím nedávno vyvinutá metoda ing. Strnadelem \cite{STRN2}. Od počátku je navrhována jako normalizovaná, tudíž kvalitativní výsledky jsou v oboru hodnot $<0;1>$. Metoda je navržena na úrovni meziregistrových přenosů, ale lze ji použít i na úroveň logických hradel. Stejně jako v předchozí metodě se používají tři složky-(řiditelnost, pozorovatelnost a testovatelnost). Počítají se obdobným způsobem a to procházením obvodu postupně od vstupů k výstupům a opačně. Zde se ovšem při počítání složek uvažují veškeré cesty kterými je možné ovlivnit resp. pozorovat poruchu. Dokáže tak reflektovat nedetekovatelné poruchy a měla by tudíž podávat kvalitnější výsledek, avšak za cenu spojitou s výrazně vyšší výpočetní náročností.

\subsection*{Výběr metody}
Implementovaná metoda, bude pravděpodobně výrazně ovlivňovat schopnost genetického algoritmu produkovat jedince se zadanou testovatelností. Rozhodl jsem se proto implementovat více metod a až z testů určit, která metoda je vhodná. Avšak z důvodů implementace jiných částí generátoru jsem se nakonec rozhodl pro metodu CAMELOT.