\chapter{Úvod}\label{sec:Uvod}
V této kapitole se nejprve seznámíme s problematikou, kterou převáděný program řeší.

Jedním z hlavních směrů dnešní vědy je bezesporu oblast výpočetní techniky. V této oblasti dochází k největšímu pokroku od dob vynalezení tranzistoru. Lidé spatřují stále nové a nové možnosti využití zařízení výpočetní techniky. Vzhledem k tomu, že celý obor výpočetní techniky je velice rozsáhlý, začal se dělit na jednotlivá odvětví, na která je třeba se úzce specializovat, protože objem informací v jednotlivých oblastech je veliký a nelze tyto informace všechny vstřebat. Jedním z hlavních směrů je vývoj logických obvodů, které jsou velice úzce spjaty s obvody integrovanými, které jsou další fází ve výrobě. Dnešní integrace polovodičů je stále větší, tj. dnešní stějně veliké integrované obvody mohou mít (a mají) mnohem více funkcí, než měli jejich předchůdci z dob minulých. Se vzrůstající složitostí obvodů vzrůstá i chybovost, která může být způsobena špatným návrhem, ale také nedokonalou technologií při výrobě. Technologie výroby integrovaných obvodů nejsou vůbec dokonalé a obzvláště v malých měřítkách, jako jsou nanometrové technologie. Se vzrůstající chybovostí vzrůstají i požadavky na snížení až odstranění chybovosti v integrovaných obvodech. Jedna z metod jak chybovost IO (Integrovaný Obvod) snížit, je vylepšení technologie výroby, která s sebou nese spousty komplikací a nákladů, které nemusí být akceptovatelné. Druhou metodou jak zvýšit spolehlivost IO je jejich testování a špatné kusy vyřadit. Tímto se zvýší spolehlivost IO pro zákazníky, ale je to jen odstranění důsledků, nikoliv příčiny. Oblast testování logických nebo integrovaných obvodů neustále vzrůstá z důvodu toho, že náklady na testování a ztráty špatných obvodů s sebou nesou nižší náklady než vylepšení vlastní technologie výroby. Rozvíjejí se algoritmy jak rychle a efektivně testovat logické obvody s co nejnižšími náklady a největší rychlostí. Testy těchto obvodů bývají různé a neomezují se jen na prostý výsledek prošel/neprošel. V současné době je potřeba testovat i vnitřní struktury obvodu, aby se zjistilo, kde nastala chyba a případně jaká. Pro oblast testování logických obvodů se vžil termín diagnostika, který byl pro své velmi podobné metody a řešení převzat z oboru lékařství. Tato oblast má několik fází. Po vytvoření struktury logického obvodu, se provede vygenerování testů pro odzkoušení obvodu. Následuje simulace testů, což je kontrola testů zda jsou bezhazardové, úplné a rychlé. Po simulaci následuje fyzické otestování logického obvodu. V prvních dvou fázích není třeba žádný hardware, protože generování testů probíhá pouze na základě informace o struktuře obvodu nebo jeho funkce. To dělí generování testů na dvě oblasti, kde první je generování strukturních testů a druhá je generování funkčních testů. Druhá fáze je simulace, kde není potřeba vlastní testovaná jednotka, protože můžeme použít simulaci číslicovou, která poskytuje nejspolehlivější a nejrychlejší výsledky a umožňuje vytvářet podklady pro údržbu a zejména slovníky poruch. Velmi často jsou obě fáze spojeny a to tak, že po vygenerování testů je provedena jejich simulace. 

Dnešní vývoj v této oblasti je hlavně v automatizaci testování obvodů, který dokáže spolupracovat se systémy CAD (Computer-Aided Design) a systémy CAM (Computer-Aided Manufacturing). Ze systémů CAD se berou výstupy, které obsahují strukturu obvodu, která je načtena do ATPG (Automatic Test Pattern Generator) nástroje, který generuje strukturní testovací vektory a provádí jejich simulaci. Výstupy tohoto nástroje jsou pak následně užity při výrobě logického obvodu, kde po jeho výrobě se na základě informací z ATPG ihned otestuje. Údaje z ATPG zpravidla obsahují seznam testovacích vektorů a seznam poruch. Tímto způsobem dochází k automatizaci procesu. Při fyzickém testování výrobku se vezme seznam vygenerovaných testovacích vektorů, který se postupně posílá na testovaný výrobek a porovnávají se výstupy (odezvy) tohoto výrobku s výstupy správnými.

Je nutné si předem ujasnit názvosloví, které je třeba striktně dodržovat. V problematice generování testů jsou zavedeny pojmy porucha a chyba. Porucha je jev, spočívající v ukončení schopnosti obvodu plnit požadovanou funkci. Chyba je rozdíl mezi správnou a skutečnou hodnotou nějake veličiny, zjištěný měřením nebo pozorováním. Chyba je vždy důsledkem nějaké poruchy, ale porucha se nemusí vždy projevit chybou.

\section{Generování testů}
\subsection{Funkční testy}
Test se označuje jako funčkní, pokud byl sestaven na základě funkce testované jednotky, tj. bez znalosti její struktury. Funkční testy jsou generovány na základě několika metod mezi něž patří booleovská diference nebo tabulky úplných testů. Pro tyto testy se typicky vytvoří model, který je izomorfní se strukturou (má stejnou funkci) testovaného obvodu. Tento model se setatví na základě výše uvedených metod.
\subsection{Strukturní testy}
Strukturní test má za úkol co nejblíže specifikovat místo v obvodu, kde se porucha vyskytla. Při generování tohoto typu testů je nutné znát vnitřní strukturu testovaného obvodu. Testované poruchy jsou typu t0 nebo t1. Anglické označeni těchto poruch je stuck-at x, kde x je 0 nebo 1. Proto se často zaměňuje označení t0 za sa0 a t1 za sa1. Tyto typy poruch v reálu představují hlavně přerušení, kdy se na vstupu logického obvodu objeví logická 1 nebo zkrat, kde zkratem je míňeno zkrat na signálovou zem, kdy se na vstupu logického obvodu objeví logická 0. Tyto poruchy jsou trvalé, tj. s časem nemění svoji hodnotu. Strukturní testy jsou velmi důležité, protože pro technika, který provádí diagnostiku je velice důležité určit v jaké části obvodu se porucha(-y) nachází, aby mohl obvod opravit nebo vyměnit. V technické praxi se velmi praktikuje výměna celého technického celku. Z toho vyplývá, že již dále nezáleží zda se v technickém celku nachází jedna nebo více poruch, protože tento celek bude vyměněn stejně celý.

Při strukturních testech se využívá několik metod. První metodou je zcitlivění cesty. Tato metoda představuje základní kámen pro generování strukturních testů. Aby bylo možné testovat obvod na nějakou poruchu, je potřeba, aby se chyba způsobená touto poruchou projevila na výstupech obvodu. Toho je možné dosáhnout tak, že všechny logické obvody, přes které signál prochází směrem k výstupům obvodu, se musí nastavit tak, aby se změny tohoto signálu přenášely až na výstup(-y) testovaného obvodu. Zkráceně lze říci, pokud poruchový signál prochází logickým členem AND nebo NAND, pak je třeba ostatní vstupy tohoto logického členu nastavit do stavu log. 1 a naopak, pokud signál prochází logickým členem OR nebo NOR, pak je třeba ostatní vstupy tohoto logického členu nastavit do stavu log. 0. Metoda zcitlivění cesty není algoritmická, což znamená, že se nedá naprogramovat. To bylo důvodem vytvoření D-Algoritmu, který tuto metodu algoritmizoval a bylo tak možné provést zcitlivění cesty programově. Pro tento algoritmus byly nalezeny heuristiky, které byly příčinou nových algoritmů s názvy PODEM a FAN. Metoda zcitlivění cesty je použita při generování jednoho kroku testu.

Druhou metodou je generování jednoho kroku testu. Cílem této metody je vygenerování testovacího vektoru, který pokryje co nejvíc poruch. Tuto metodu opakujeme až do té doby než pokryjeme všechny možné poruchy. Nutno podotknout, že ne vždy je možné pokrýt všechny poruchy, protože některé poruchy jsou nedetekovatelné (například u redundatního obvodu). Úplným pokrytím je zde tedy myšleno vygenerování testovacích vektorů pro všechny detekovatelné poruchy.

\section{Simulace}
Simulace provádí kontroly odezev, úplnosti a bezhazardnosti. Každá z kontrol potřebuje jinou modifikaci algoritmu. My se budeme zabývat kontrolou úplnosti, která je z uvedených kontrol nejsložitější. 

Simulace obecně rozdělujeme na tři formy a to: ruční, fyzická a číslicová. Z těchto tří forem nás zajímá ta poslední, která při kontrole testu dává nejrychlejší a nejspolehlivější výsledky.

Metod simulace je několik. První a nejjednodušší je metoda programové injekce poruch do simulovaného obvodu. Zkoumaný obvod při simulaci nějaké poruchy se změní na jiný obvod, který je třeba simulovat v samotném průchodu. Další metoda je paralelní simulace, kde se využívá možnosti zpracování několika bitových operací najednou. Vzhledem k nezávisloti těchto operací a uložení jsou jednotlivé bity do obvodu injektovány najednou, kde každý bit je rezervován pro simulaci jedné poruchy. Další metoda je deduktivní simulace, která je založena na simulaci bezporuchového obvodu a odvozováním detekovaných poruch na jednotlivých vodičích. Další metoda je souběžná simulace, která funguje tak, že každý logický člen obvodu je vybaven seznamem poruch a jejich možných důsledků. Více o těchto metodách v \cite{Skripta}.

