\chapter{Uvedení do problematiky}

\section{Speed Independent obvody}
\indent \indent Jsou součástí návrhového stylu zabývající se syntézou asynchronních obvodů. Tyto obvody jsou 
bezhazardní v tzv. vstupně-výstupním módu a používají model nevázaného zpoždění. Speed Independent obvody spoléhají na model, který se staví pesimisticky ke zpoždění na hradlech a realisticky předpokládá zpoždění na vodičích. Obvody se neohlížejí na globální omezení vnějším prostředím. Každá vstupní změna je signalizována obvodu, že vnější prostředí je připraveno nastavit další vstupní vzor.  Obvody jsou robustní vzhledem k nepravidelným změnám parametrů jako jsou procesní změny, změny napětí a teploty. Jsou jednodušeji verifikovatelnější než obvody, které jsou založeny na modelu vázaného zpoždění. Nejpopulárnější specifikační styl pro Speed Independent obvody jsou signálově přechodové grafy. Pro získání více informací je vhodné navštívit stránky \cite{od3}.


\subsection{Hazardy}
\indent \indent Pro návrháře obvodu je hazard nechtěný glitch na signálu. Obvod, který je ve stabilním stavu, samovolně neprodukuje hazardy. Hazardy se vztahují k dynamickým operacím v obvodě.  Je to tedy vztah mezi vstupními signály, které se dynamicky mění, hradly a vodiči. Výsledkem snažení návrháře je udělat obvod bezhazardní (hazard-free).
  
Když mluvíme o hazardech musíme vzít v úvahu jaký model zpoždění obvod praktikuje a jaké jsou vytvořeny předpoklady ohledně interakce mezi obvodem a vnějším prostředím. Pro  asynchronní obvody je specifické, že předpokládáme jak zpoždění na hradlech, tak i zpoždění na vodičích. Na základě zpoždění na vodičích a hradlech, pak specifikujeme model zpoždění.  


\subsection{Modely zpoždění (Delay model)}
\indent \indent  Nejednoduší model zpoždění je fixní model zpoždění ( fixed delay model), kde je zpoždění konstantní. Alternativou je min-max model zpoždění, kde zpoždění je neznámé, ale je stanovena dolní a horní hranice 
$t_{min} <= t_{delay} <= t_{max}$. Více pesimistický model je model nevázaného zpoždění (unbounded delay model), kde zpoždění je pozitivní. 
$0 < t_{delay} < \infty$. 
 

\subsection{ Vstupně-výstupní mód (Input-Output mode)}
\indent \indent Předpokládáme, že obvod se nachází ve stabilním stavu, pak je dovoleno vnějšímu prostředí měnit vstupy. Při změně obvod vyprodukuje korespondující výstup a opět je vnějšímu prostředí dovoleno měnit vstup. Neberou se v úvahu interní signály, protože další vstupní změna nastane až obvod bude stabilizován, což je odpověď na předchozí vstupní signál. Změna vstupního signálu není časově vázaná.  

Omezení na vnější prostředí je formulováno jako příčina vztahu mezi vstupními signály přechodů a výstupními signály přechodů. Z tohoto důvodů jsou obvody často popisovány nákresy, které sledují všechny možné sekvence vstupních a výstupních signálů přechodů a které mohou být v obvodu pozorovány. Proto se pro tyto účely nejvíce hodí signálově přechodový graf.


\subsection{Syntéza Speed Independent obvodu}
\indent \indent Je založena na vstupní specifikaci popsaného pomocí signálově přechodového grafu, který splňuje požadavky níže uvedené nebo literatury \cite{od4}. Proto je nezbytné provést analýzu obvodu a zohlednit v ní požadavky Speed Independent obvodů jako jsou bezhazardnost obvodu,  vstupní-výstupní mód a model zpoždění. Pokud je správně vytvořený signálově přechodový graf, mohu přejít k jeho transformaci na stavový graf. Výsledkem transformace je stavový graf, jež dodržuje kompletní zakódování stavů. Jinými slovy, ve stavovém grafu neexistují dva stavy se stejným zakódováním. Splním-li zakódování a vytvořím stavový graf, pak je třeba pro jednotlivé výstupy a interní signály přechodů vytvořit regiony.  Po vytvoření regionů jsem připraven na tvorbu funkcí, které jsou vstupy \hbox{C-elementu}. \hbox{C-element} je předřazen před každý výstup nebo interní signál. Aby asynchronní obvody fungovaly správně, je třeba zajistit bezhazardnost celému obvodu. Pro synchronizaci signálu se používá C-element, bezhazardost C-elementu je zajištěna jeho strukturou.
Pokud se ve funkcích Set nebo Reset vyskytuje více jak jeden minterm a je tedy nezbytné v obvodu použít hradlo OR, pak je třeba zjistit, zda proměnné v mintermu Reset nejsou taky obsaženy  v mintermech Set, jestliže dojde k schodě je potřeba zajistit bezhazardnost.


\subsection{Proč jsem použil C-element}
\indent \indent Obvody lze samozřejmě sestavit i z atomických hradel, ale aby takový obvod byl bezhazardní, pak všechny zpoždění musí být formulovány na výstupu posledního hradla pro každý signál sítě. Ovšem, když takový obvod namapujeme do opravdových hradel a zpoždění těchto hradel jsou posuzovány individuálně, pak se v implementaci mohou začít šířit hazardy v důsledku rozdílných rychlostech na cestách. Pokud požaduji, aby se rychlosti synchronizovaly, a tak předešel vzniku šíření hazardů, musím použít prvek, který nějakou dobu drží stejnou hodnotu stavu. Stejnou hodnotu stavu drží tak dlouho, dokud mu nepřijde signál, že může přijmout další stav. Takovým  prvkem v asynchronních obvodech je C-element. C-element přijímá dva vstupní signály, které prvku udávají zda má držet stav nebo nastavit nový stav na výstup . C-element, který budu používat má jeden vstup invertovaný a jedná se o tzv SET-RESET C-element. Struktura C-elementu zajišťuje, že v tomto komplexním prvku nevznikne hazard.



\subsection{Signálově přechodový graf (Signal transition graph, STG)}
\indent \indent Signálově přechodový graf je interpretací Petriho sítí, jehož přechody jsou interpretovány jako rostoucí a  klesající signály. Rostoucí resp. padající hrany jsou označeny v grafu „+“ resp. „-“. STG má dva typy vrcholů: přechody a místa. Místa mohou být označkovány tokenem (obvykle značíme černým puntíkem). Token je označení aktivního místa. Množina všech míst (pozn. $M_{0}$), které jsou aktuálně označené tokenem, označujeme jako \textit{marking}. Přechody jsou aktivní, jestliže všechny místa vstupující do přechodů jsou označeny tokenem. Každý aktivní přechod může být tzv. \textit{„odpálen“}.\textit{ Odpálení } přechodu znamená odebrání tokenu ze všech vstupních míst daného přechodu a přemístit je na místa výstupní daného přechodu.  Místa, jež jsou dosažitelná a označitelná mohou asociovat s určitým binárním kódem signálů. Na základě tohoto poznatku jsme schopni vytvořit určitou souvislost mezi STG a SG. Signál může být buď v jednoduchém cyklu, když má pouze jeden rostoucí a jeden padající přechod, jinak se jedná o více cyklický signál.  Grafické vyjádření dovoluje návrháři uchopit chování asynchronního obvodu  a navíc zde existuje jistá podobnost s časovým diagramem. Více v literatuře \cite{od5}. 
\clearpage
STG je šestice, kde $\left\langle P, T, F, M  _{0}, N,s _{0} ,\lambda _{0}  \right\rangle$
\newline
\newline $P$ je množina míst.
\newline $T$ je množina přechodů.
\newline $F \subseteq (P \times T) \cup (T \times P)$ je množina hran, kde žádná hrana nemůže spojovat dva přechody nebo 				dvě místa.
\newline $N = I \cup O$ je průnik množin signálů, kde I je množina vstupních signálů a O je množina výstupních signálů.
\newline $s_{0}$ je počáteční hodnota pro každý signál v počátečním stavu.
\newline $\lambda_{0} \rightarrow N \times \{+,-\}$ je přechodově označená funkce.
\newline $M_{0}$ je množina míst obsahující token.
\newline \newline Podmínky souvislosti Petriho sítě a STG:

 1.Input free choice: Výběr mezi alternativy musí být kontrolovány navzájem se vylučujícími vstupy.

 2.1-bounded: Na jednom místě se nesmí vyskytovat více než jeden token.

 3.Liveness: V STG se nesmí vyskytovat deadlocky.
\newline
\newline Podmínky STG:
\newline STG je živý(live) a bezpečný(safe):

1.Základ je položen na 1-bounded Petriho sítě.

2.STG je silně souvislý graf

3.Klesající a rostoucí přechody jsou v grafu vystřídány.
\newline 
\newline Jestliže jsou splněny předchozí podmínky můžeme dojít k uspokojení následujících podmínek:
\newline Kompletní  zakódování (CSC)

1.Jestliže každý stav má rozdílný binární kód .

2.Nebo když dva nebo více stavů mají identický binární kód  a nevstupní signály přechodu jsou aktivovány, pak se jedná o ty samé.
\newline 
\newline Podmínky pro STG popisující Speed Independet obvod:

1.Konzistence: přechody signálu se musí striktně střídat mezi + a -.

2.Musí být persistentní: Jestliže signál přechodu  je aktivní, tak na vstupním místě přechodu je token a zároveň nemůže být deaktivován jiným signálem. (pozn. Obvod musí garantovat persistenci výstupních a interních signálů, zatímco pro vstupy musí být persistence garantována prostředím).  

\subsection{Stavový graf (State Graph, SG)}
\indent \indent Je binární reprezentace stavů, kde událost je reprezentována signály přechodů. 
\newline Stavový graf je trojice $\left\langle S, \delta ,\lambda_{s} \right\rangle$
\newline $S$ je množina stavů.
\newline $\delta \subseteq S \times T \times S $ je množina přechodů.
\newline $\lambda_{s}: S \rightarrow ( N \rightarrow \{0,1\} )$ je funkce pro označení stavu.
\newline $T$ je množina přechodů Signal Trasition Grafu
\newline $N$ je množina průniku množin vstupních a výstupních množin signálů v Signal Trasition Grafu. 
\newline 
\newline 
Každý stav s je označen vektorem $\left\langle s(0),s(1),...s(n)\right\rangle$, kde s(i) je buď 1 nebo 0., hodnota je indikována funkcí $\lambda_{S}$.

\subsection{Regiony}
\indent \indent Jsou množiny binárních hodnot stavů stavového grafu pro daný výstupní nebo interní signál. Regiony se dělí do dvou základních regionů: excitovaný a ustálený. Stavy se do těchto množin přidělují na základě vztahu binárních hodnot stavů k danému signálu. Význam regionu spočívá ve zjištění stavů, které jsou pro daný signál ve stavu excitace a kolem těchto stavů vytvořit pokrytí za účelem získání funkcí pro vstupy C-elementu. Stavy, které nejsou excitované nemusí být pokryté, jelikož logika, která by vznikla pokrytím neexcitovaných stavů by neměla vliv na C-element, ale hlavně by mohla vést ke vznikům hazardů.


\subsection{ Excitované regiony(Excistation region, ER)}
\indent \indent Stav SG se nachází v ER, jestliže dojde k přechodu z nynějšího stavu do nového stavu pro daný signál v binárním kódu a nastane změna z 0 na 1 resp. z 1 na 0, pak se jedná buď o rostoucí signál a+ resp. o klesající signál a-, kde a je signál. Excitovaný region značíme jako ER+(a) resp. ER-(a) pro daný signál a. 
 

\subsection{ Ustálené regiony (Quiescent region, QR)}
\indent \indent Stav SG se nachází v QR, jestliže po přechodu nynější stav na nový stav zůstane hodnota signálu  v novém stavu nezměněna, pak se jedná buď o setrvání rostoucího signálu a+ nebo o setrvání klesajícího signálu a-, kde a je signál. Ustálený region se značí QR(a+) resp. QR(a-) pro daný signál a.


\subsection{Minimalizace}
\indent \indent Cílem minimalizace je vytvořit funkce s minimálním počtem proměnných pro vstupy \hbox { C-elementu }, kde invertovaný vstup budu nazývat Reset a neinvertovaný Set . Každá binární hodnota v regionu odpovídá jednomu termu a regiony udávají výstupní hodnoty stavů pro daný signál. Hodnotě 1 odpovídají stavy s binárním zakódováním v regionech  ER+(a) a QR+(a). Hodnotě 0 odpovídají stavy v regionech  ER-(a) a QR-(a). Don't care je pro ostatní stavy, které nejsou zahrnuty v regionech. Pro vstup Set se budu snažit najít co největší pokrytí kolem stavu v ER+(a). Pokud je v množině ER+(a) více stavů vytvořím z jejich pokrytí funkci v disjunktivní formě. Pro Set se hledají co největší pokrytí v mapě přes hodnoty 1 a don't care. Naproti tomu pro Reset se hledají co největší pokrytí 0 a don't care kolem ER-(a), popřípadě se opět vytváří funkce v disjunktivní formě. Pokud funkce Reset nebo Set obsahují více jak jeden minterm, pak je potřeba zkontrolovat, zda některý z minterů z funkce Reset není obsažen v mintermech z funkce Set. Pokud zjistím, že některý minterm z funkce Reset je obsažen v jednom z mintermu funkce Set, pak je potřeba tento problém řešit pomocí monotonního pokrytí, které omezuje pokrývání na stavy dosažitelné v obvodu. Dosažitelné stavy obvodu jsou stavy, pro které není výstup don't care. Monotonní pokrytí stačí vytvořit pro jeden z dvojice mintermů, pro které nastala shoda, obvykle se pokrývá minterm z funkce Reset.


\subsection{Časový diagram (Timing diagram)}
\indent \indent Reprezentuje množinu signálů v časové doméně. Časový diagram obsahuje řádky, ve kterých  je průběh signálů nebo množiny signálů v čase zobrazen. Konvence v časovém diagramu: pokud je signál zakreslen vodorovnou čarou, která se vyskytuje ve vyšší hladině nákresu,  představuje logickou jedničku. Pokud je signál v nižší hladině nákresu, přestavuje logickou nulu. Přechod mezi nulou a jedničkou resp. jedničkou a nulou je naznačen svislou nebo šikmou čarou. Časový diagram je reprezentován obrázkem \ref{fig:stgtim}.

  
\begin{figure}[ht]
\begin{center}
\includegraphics{stgtim}
\caption{Signálově přechodový graf a časový diagram}
\label{fig:stgtim}
\end{center}
\end{figure}
\clearpage

\subsection{Vztah signálově přechodového grafu a časového diagramu}
\indent \indent Přechody signálů z nula na jedna resp. z jedničky na nulu jsou naznačeny v signálově přechodovém grafu plusem resp. mínusem pro daný signál. V časovém diagramu jsou uvedeny odpovídající signály a k ním řádky na níž běží odpovídající průběh signálu. Změna hodnoty signálu v časovém diagramu nastává ve stejný okamžik, kdy dojde k odpálení přechodu v signálově přechodovém grafu. Odpálený přechod signálu ve signálově přechodovém grafu odpovídá změně u stejného signálu v časovém digramu. Vztah je naznačen v obrázku \ref{fig:stgtim}. 
 


\subsection{Matematické vyjádření algoritmu pro transformaci STG na Stavový Graf}
\indent \indent Vstupem algoritmu je STG ve formě $\left\langle P, T, F, M  _{0}, N,s _{0} ,\lambda _{0}  \right\rangle$ a výstupem je SG ve formě $\left\langle S, \delta ,\lambda_{s} \right\rangle$.
Podstata algoritmu je procházení STG, tak dlouho dokud nejsou nalezeny všechny možné kombinace míst, které spolu tvoří stavy stavového grafu. Přechody mezi stavy stavového grafu odpovídají přechodům mezi místy STG, které shlukují jednotlivé stavy. Každý stav má samozřejmě svou binární hodnotu. Jak algoritmus vypadá vidíme níže \ref{fig:alg}, vycházím ze slajdu viz. \cite{od6}. 

\begin{figure}[ht]
\begin{center}
\includegraphics{alg}
\caption{Transformační algoritmus}
\label{fig:alg}
\end{center}
\end{figure}
\clearpage
 
Rozbor jednotlivých řádků:
\begin{enumerate}
\item Inicializace vstupu grafem STG.

\item Kopírování množiny míst $M_{0}$ obsahující token do množiny $M$.

\item Kopírování počátečního zakódování stavu stavového grafu $s_{0}$ do $s$.

\item Vytvoření množiny $Te$, která bude obsahovat všechny přechody z množiny $T$, které 	splňují podmínku. Podmínka udává, že se bude jednat o přechody, které mají na místech, ze 	kterých  se dostaneme do daného přechodu, token.

\item Do množiny $S$ je přiřazena množina $M$, jejíž celek odpovídá jednomu prvku množiny 	$S$. Prvek množiny $S$ je chápán jako jeden stav.

\item Danému prvku množiny $S$ jsme přiřadili označení neboli binární zakódování stavu.

\item Proměnnou $done$ jsme nastavili na false. Done slouží k ukončení cyklu. Pokud je $done$ rovno true.

\item Kontrola podmínky cyklu.

\item Do proměnné $t$ přiřadíme prvek z množiny $Te$.

\item Otestujeme zda množina $Te$, která je  ochuzena o prvek $t$, obsahuje ještě nějaké 	prvky navíc. Pokud ano, uložíme do zásobníku současný stav množiny $M$, proměnou $s$ 	se zakódováním aktuálního stavu stavového grafu a množinu $Te$ bez prvku $t$.

\item V podmínce ověříme, zda množina míst $M$ ochuzená o místa, které obsahují token a 	lze se z nich dostat do přechodu, jež je obsažen v proměnné $t$, dá prázdnou množinu po 	průniku s místy,  které po přechodu tokenu přes přechod $t$ budou obsahovat token. Pokud 	ne, algoritmus vrací informaci, že STG není bezpečný.

\item Do množiny $M'$ překopírujeme sjednocení množiny $M$ ochuzeného o místa , které 	obsahují token a lze se z nich dostat do přechodu, jež je obsažen v proměnné $t$ a místy,	které po přechodu tokenu přes přechod $t$ budou obsahovat token.

\item Překopírování zakodování uložíme v $s$ do $s'$.

\item Jestliže přechod roste, jinými slovy by měl jít z nuly na jedničku, jež bývá označeno +, 	pak v proměnné $s'$, kde je uloženo zakódování nastavíme na danou pozici pro daný signál 	binární 1.

\item Jestliže přechod klesá, jinými slovy by měl jít z jedničky do nuly, jež bývá označeno -, 	pak v proměnné $s'$, kde je uloženo zakódování nastavíme na danou pozici pro daný signál 	binární 0.

\item Jestliže množina $M'$, je chápána jako jeden prvek a není obsažena v množině $S$, 	představující množinu stavů stavového grafu, pak dojde k vykonání následujících řádků 	( 17. až 22. ).

\item Do množiny $S$ přidáme množinu $M'$, která představuje jeden prvek množiny $S$.	

\item Prvku množiny $S$, který odpovídá množině $M'$, přidáme označení binární 	zakódování stavu.

\item Do množiny $\delta$, která představuje množinu přechodu ve Stavovém Grafu, 	přidáme přechod mezi prvky množiny $S$, tedy $M$ a $M'$.

\item Nastavení množiny $M$ na $M'$.

\item Nastavení proměnné $s$ na $s'$.

\item Viz. řádek 4..

\item Pokud podmínka na řádku 15. neprojde, budou se provádět následující řádky 		( 24. až 26.).

\item Pokud se nebude shodovat zakódování v $s'$ se zakódováním prvku množiny $S$ 	odpovídajícímu prvku $M'$, pak algoritmus skončí s nekonzistentním zakódováním. 

\item Jestliže, zásobník není prázdný, pak se nastaví množina $M$ , proměnná $s$ a $Te$, 	podle konfigurace uložené na vrcholu zásobníku, a pak se tato konfigurace zahodí. 

\item Jestliže podmínka v řádku 25. neprojde nastaví se $done$ na true.

\item Konec algoritmu, návratová hodnota je stavový graf.
\end{enumerate}

\subsection{Muller C-element}
\indent \indent Muller \hbox{C-element}, též často nazýván jako \hbox{C-element} nebo \hbox{C-hradlo}. Obvykle se vyskytuje v asynchronním návrhu, kde se používá při synchronizací událostí nebo jako prvek držící stav. \hbox{C-element} není atomické hradlo, ale jedná se o komplexní prvek, tvořen několika atomickými hradly.
Chování \hbox{C-elementu} je popsáno pravdivostní tabulkou \ref{tab:tab1}. 
 
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\bf{Set} & \bf{Reset} & \bf{C} \\
\hline
$0$ & $0$ & $0$\\
\hline
$0$ & $1$ & $C_{n-1}$\\
\hline
$1$ & $0$ & $C_{n-1}$\\
\hline
$1$ & $1$ & $1$\\
\hline
\end{tabular}
\end{center}
\caption{Ukázka tabulky}
\label{tab:tab1}
\end{table}


Pokud jsou vstupy Set a Reset na 0, pak na výstupu je 0. Pokud jsou vstupy Set a Reset na 1, pak na výstupu je 1. Pokud jsou vstupy rozdílné, pak na výstupu je $C_{n-1}$, který odpovídá starému stavu. Starý stav je po nezbytnou dobu uložen v \hbox{C-elementu}.  
  
\begin{figure}[hp]
\begin{center}
\includegraphics{celem}
\caption{Vnitřní reprezentace C-elementu}
\label{fig:celem}
\end{center}
\end{figure}
\clearpage
\hbox{C-element} ukládá předchozí stav za pomocí dvou protichůdných invertorů. Jeden z invertorů je slabší, než zbytek obvodu a tak může být přetlačen spínací a rozpínací sítí (pull-up and pull-down networks). 
Jestliže oba vstupy jsou 0, pak se spínací síť (pull-up network ) mění latch stav a výstup \hbox{C-elementu} je 0. Jestliže vstupy jsou 1, pak rozpínací síť ( pull-down network ) mění latch stav a  na výstup přichází jedna. V ostatních případech není spojení mezi $V_{dd}$ nebo zemí, slabý invertor převládá a latch stav výstupu kopíruje předchozí stav.
Daný popis je znázorněn na obrázku \ref{fig:celem}.
\begin{figure}[hp]
\begin{center}
\includegraphics{c1}
\caption{C-elementu typ 1}
\label{fig:c1}
\end{center}
\end{figure}

Jestliže se vstupy schodují, pak se kopíruje na výstup, jinak se drží předchozí stav. Obrázek \ref{fig:c1}.
\begin{figure}[hp]
\begin{center}
\includegraphics{c2}
\caption{C-elementu typ 2}
\label{fig:c2}
\end{center}
\end{figure}

Jestliže se vstupy schodují, pak na výstup jde invertovaný výstup, jinak se drží předchozí stav. Obrázek \ref{fig:c2}.
\begin{figure}[hp]
\begin{center}
\includegraphics{c3}
\caption{C-elementu typ 3}
\label{fig:c3}
\end{center}
\end{figure}

Jestliže jsou vstupy rozdílné, pak se kopíruje neinvertovaný na výstup, jinak se drží předcházející.
Jedná se o tzv. SET-RESET C-element. Tento C-element se nejčastěji využívá pro syntézu asynchronních obvodů. Obrázek \ref{fig:c3}.




\subsection{C-element ve VHDL }
\indent \indent C-element ve VHDL
Implementoval jsem C-element jako komponentu ve VHDL. Komponenta bude sloužit jako komplexní hradlo v obvodu popsaném ve VHDL kódu. Na jeho vstupy pojmenované Set a Reset se namapuje vstupní logika vygenerovaná programem, výstup se přes portování spojí s patřičným signálem.
\newline
\newline Naimportované knihovny kódu VHDL.
\newline \textit {library IEEE;
\newline use IEEE.STD\_LOGIC\_1164.ALL;
\newline use IEEE.STD\_LOGIC\_ARITH.ALL;
\newline use IEEE.STD\_LOGIC\_UNSIGNED.ALL;
}
\newline
\newline V entitě jsou nadefinovány vstupy \textit {S }a\textit { R} , představující Reset a Set. Výstup C-elementu je pojmenován \textit {out\_c}.
\newline \textit {entity cm is
    \newline Port ( S : in  STD\_LOGIC;
\newline               R : in  STD\_LOGIC;
\newline               out\_c : out  STD\_LOGIC);
\newline end cm;
\newline }
\newline Architektuře označuje, že v jeho těle bude charakterizováno chování obvodu.
\newline \textit {architecture Behavioral of cm is}
\newline 
\newline Předdefinované pomocné signály pro interní výstupy v C-elementu.
\newline \textit {	signal lev1a : std\_logic;
	\newline signal lev1c : std\_logic;
	\newline 
	\newline signal lev2a : std\_logic;
	\newline signal lev2b : std\_logic;
	\newline signal lev2c : std\_logic;	
\newline 	
	\newline signal lev3or : std\_logic;		
\newline }
\newline \textit {Begin} označuje začátek těla architektury, ve které probíhá vlastní definice obvodu.
\newline \textit {begin}
\newline 
\newline Do pomocných proměnných \textit {lev2a, lev2b, lev2c} přiřadíme výsledek z prvních třech ANDů. 
\newline \textit {	lev2a <= lev1a and S;
	\newline lev2b <= S and not R;
	\newline lev2c <= not R and lev1c;}
\newline 
\newline Výsledek ORů z pomocných signálů   \textit {lev2a, lev2b, lev2c} přiřadíme do lev3or, který se následně předá n výstup C-elementu \textit {out\_c}. Pomocí \textit {lev1a a lev2c} vytvoříme zpětnou vazbu do ANDů.
\newline \textit {   lev3or <= lev2a or lev2b or lev2c;
	\newline lev1a  <= lev3or;
	\newline lev1c  <= lev3or;
	\newline out\_c <= lev3or;
\newline 
\newline end Behavioral;
\newline }


\section{Fundamentální mód}
\indent \indent Většinou označovaný v literatuře jako Huffmanuv mód.
U fundamentálního módu předpokládáme, že obvod se nachází ve stavu , kde jsou všechny vstupní, výstupní a interní signály stabilní. V tomto stavu je dovoleno vnějšímu prostředí měnit jeden vstupní signál. Po změně signálu vnějším prostředím nesmí dojít ke změně vstupního signálu do té doby, dokud vstupy nejsou opět stabilní. Interní signály udávající stav proměnných  jsou pro vnější prostředí neznámé a proto je třeba spočítat nejdelší zpoždění v obvodu. Po vnějším prostředí je pak požadováno, aby drželo vstupní signály stabilní přinejmenším po vypočítanou dobu zpoždění. Zpoždění na hradlech a vodičích je tedy v těchto obvodech vázané a omezení na vnější prostředí je formulováno jako absolutní časový požadavek. Obrázek \ref{fig:huff} vyjadřuje představu o fundamentálním módu. Šipky na zpětné vazbě obvodu na obrázku představují vypočítané zpoždění, po jehož uplynutí bude obvodu opět dovoleno přijmout vstupní signál. 
 

\begin{figure}[hp]
\begin{center}
\includegraphics{huff}
\caption{Huffmanuv mód}
\label{fig:huff}
\end{center}
\end{figure}


\subsection{Syntéza podle fundamentálního módu}
\indent \indent Je taky známa jako Huffmanuv návrhový styl. Vnějšímu prostředí je dovoleno změnit jeden vstup za vypočítaný čas. Jako odpověď na změnu vstupu, kombinační logika vyprodukuje nový výstup a taky zpětnou vazbu viz \ref{fig:huff}. Předpokládá se, že zpětnovazební signál je natolik zpožděn, že vstupy budou ve stabilizovaném stavu dříve než  dorazí zpětnovazební signál. Důvodem zpoždění je kombinační logika, kterou musí signál projít než nastane nový výstup. Nakonec se přes sekvenci jednotlivých signálů přechodů v obvodu dosáhne stabilizovaného stavu a poté může vnější prostředí vyprodukovat další jeden signál. Vstup syntézy podle fundamentálního módu je specifikován asynchronním konečným automatem, který je velmi podobný vstupní specifikací u synchronních sekvenčních obvodů.  
  

\subsection{Nevýhody oproti Vstupně-výstupnímu módu}
\indent \indent Může se měnit pouze jeden vstupní signál.
Musíme brát v úvahu zpoždění na interních signálech.
Zpoždění interních signálů ovlivňuje vnější prostředí.


\section{Příklad postupu syntézy }
\indent \indent Pro příklad jsem zvolil syntézu asynchronního řadiče, na kterém chci objasnit postup syntézy v naimplementovaném programu.
 Na rozdíl od klasického synchronního sekvenčního řadiče zde nemusím pro uchování stavů používat klopné obvody typu D. Asynchronní řadič bude používat \hbox{C-elementy}. Vstupní signály jsou označeny \textit{dsr} a \textit{ldtack}, výstupní signály jsou \textit{lds} a textit{d}. Interní signál značíme textit{csc0}. 
Jednotlivé události, které v čase nastanou jsou popsány pomocí signálově přechodového grafu viz. \ref{fig:stg}. Chování řadiče je naznačeno v časovém diagramu viz. \ref{fig:tim}. 
 
\begin{figure}[hp]
\begin{center}
\includegraphics{tim}
\caption{Časový diagram}
\label{fig:tim}
\end{center}
\end{figure}
\clearpage

Bílé kružnice na obrázku \ref{fig:stg} znázorňují místa v signálově přechodovém grafu. Černé puntíky v těchto místech jsou tzv. tokeny. Místa obsahující token tvoří množinu míst tzv. \textit{marking}. Nápisky s plusem nebo mínusem představují přechody signálů. Přes přechod v signálově přechodovém grafu lze přejít, pokud jsou ve všech místech, které vedou do přechodu, obsaženy tokeny (směr je naznačen šipkami). Přes přechod se prochází následovně. Vyjmou se všechny tokeny z příchozích míst a přemístí se na místa, které vycházejí z daného přechodu. Přecházení odpovídá šipkám v časovém diagramu. Místa v signálově přechodovém grafu jsou označeny P*, kde * je číslo.

\begin{figure}[hp]
\begin{center}
\includegraphics{stg}
\caption{Signálově přechodový graf}
\label{fig:stg}
\end{center}
\end{figure}
\clearpage

Transformace spočívá ve seskupení míst ze signálově přechodového grafu do jednoho stavu   stavového grafu. Seskupování míst probíhá následovně. Jeden stav stavového grafu odpovídá jednomu místu, ve kterém je právě token, v signálově přechodovém grafu. Pokud dojde k rozvětvení v STG, rozdělí se taky token a pak jeden stav SG odpovídá kombinaci místa, obsahující token, se všemi místy, kterými projdou ostatní tokeny. Kombinace míst trvá tak dlouho, dokud nedojde opět ke spojení tokenů v jeden. Přechody ve stavovém grafu jsou identické s přechody v STG, které jsou mezi místy, jež tvoří stavy SG. Stav má binární kódové označení, které vyjadřuje pro daný signál, zda se nachází v logické nule nebo jedničce. Při přechodu mezi stavy v SG, dochází ke změně pro daný signál v kódovém označení. Ve stavovém grafu jsou naznačeny kombinace míst ze signálově přechodového grafu pomocí P*, kde * je číslo. Výsledek transformace je vidět na obrázku \ref{fig:sg}.

\begin{figure}[hp]
\begin{center}
\includegraphics{sg}
\caption{Stavový graf}
\label{fig:sg}
\end{center}
\end{figure}
\clearpage

Po přetransformování STG je třeba vytvořit regiony pro každý výstupní a interní signál. Každý signál má čtyři regiony, do kterých se vkládají kódové označení stavů podle toho, zda signál ve stavu v SG je na nule resp. na jedničce a v následujícím stavu zůstane na nule resp. na jedničce, pak dojde k zařazení stavu do ustáleného regionu (QR), konkrétně do QR+(a) resp. QR-(a), kde \textit{a} je daný signál. Pokud však při přechodu do budoucího stavu dojde ke změně pro daný signál z nuly na jedna resp.z jedné na nulu, pak se konkrétní stav zařadí do excitovaného regionu, konkrétně do ER+(a) resp. ER-(a). Pokud se stav vyskytuje zároveň v ER a QR,  pak je třeba tento   stav z QR oddělat.

\begin{figure}[hp]
\begin{center}
\includegraphics{reg}
\caption{Regiony naznačení}
\label{fig:reg}
\end{center}
\end{figure}


Popis obrázku \ref{fig:reg}. Pro signál vyznačený obdélníkem by stav s označením 10101 v první případě s přechodem ldtack+ patřil do region QR+. V druhém případě pro vyznačený signál by došlo k zařazení stavu s označením 01111 do ER-. 

Příklad konkrétního přiřazení do jednotlivých regionů. Binární ohodnocení stavu je převedeno do dekadických hodnot v závorkách.
\newline 
\newline ER+(csc0) = { 16 }
\newline ER-(csc0) = { 15 }
\newline QR+(csc0) ={  17, 21, 29, 31, }
\newline QR-(csc0) = { 14, 12, 10, 28, 8, 2, 24, 0 }
\newline 
\newline ER+(lds) = { 17 }
\newline ER-(lds) = { 14, 12, 28 }
\newline QR+(lds) = { 21, 29, 31, 15 }
\newline QR-(lds) = { 10, 8, 24, 2, 0, 16, }
\newline 
\newline ER+(d) ={ 29 }
\newline ER-(d) = { 14, 10, 2 }
\newline QR+(d) = { 31, 15 }
\newline QR-(d) = { 12, 8, 0, 28, 24, 16, 17, 21 }
\newline 
\newline \newline Po vytvoření regionu následuje část minimalizace, za účelem získání rovnic pro vstupy \hbox{C-elementu}  tedy pro vstup nazývaný Set resp. Reset. Rovnice se připravují pro každý výstupní a interní signál. Výstup \hbox{C-elementu} odpovídá danému výstupu nebo internímu signálu. Regiony udávají výstupní hodnotu. Binární ohodnocení stavu odpovídá úplnému mintermu. Minterm má hodnotu 1, jestliže patří do  ER+(a) sjednoceno s QR+(a). Minterm má hodnotu 0, jestliže patří do ER-(a) sjednoceno s QR-(a). Pro názornost minimalizace použiji Karnaughovu mapu pro vybraný signál \textit{csc0} viz \ref{fig:map}. Pro ostatní zbývající signály dodám jen výsledky, postup by byl stejný. Mintermy, které se nevyskytují v regionech považuji za don't care. Hledám co největší pokrytí kolem mimtermu ze ER+(a) resp. kolem ER-(a). Pokrytí kolem ER+(a) bude odpovídat vstupní funkci pro Set, ER-(a) bude odpovídat  Resetu. V našem konkrétním případě se snažím získat co největší pokrytí kolem okénka označeného 16 pro Set a pro Reset kolem okénka 15. Pokrytí je naznačeno na obrázku \ref{fig:map}.

\begin{figure}[hp]
\begin{center}
\includegraphics{map}
\caption{Karnaughova mapa}
\label{fig:map}
\end{center}
\end{figure}

Výstupní rovnice csc0 pro Set je f = dsr and not ldtack, pro Reset f =  not dsr.
Pro signál d jsou pro Set f = ldtack and csc0, pro Reset f =  not csc0.
Pro signál lds jsou pro Set f =  csc0, pro Reset f =  not csc0.
Za povšimnutí stojí i fakt, že funkce obsahují pouze jeden minterm, proto není potřeba srovnání mintermů a provádění monotónního pokrytí. 

\begin{figure}[hp]
\begin{center}
\includegraphics{log}
\caption{Výsledná logika}
\label{fig:log}
\end{center}
\end{figure}
\clearpage
