\section{Testování logických obvodů}

Na začátek bych rád předeslal, že tento text si v žádném případě
neklade za cíl čtenáře dopodrobna seznámit s problematikou testování
logických obvodů, která je navíc vyčerpávajícím způsobem popsána
například v
\cite{HLAV98}
a v řadě dalších odborných publikací, ale jeho hlavním cílem je úvod
do této problematiky v rozsahu nezbytně nutném pro účely této práce
jako takové.

\subsection{Prostředky vestavěné diagnostiky}

Jak již bylo v úvodu práce zmíněno, v dnešní době, tj. k první
polovině roku 2007, se běžně vyrábějí zařízení obsahující logické
obvody s řádově desítkami až stovkami miliónů transistorů. Taková
zařízení jsou standardními prostředky ATE testovatelná jen velice
obtížně, a to vždy za cenu vysokých nákladů na testování v podobě
velkého množství času a komplikovaného testovacího zařízení, které
je k tomu účelu potřeba.

Výrobci takových zařízení se tento problém snaží řešit začleněním
prostředků vestavěné diagnostiky (BIST) přímo do návrhu zařízení
samotných. Takto navržená zařízení pak k vlastnímu testování
zpravidla nevyžadují součinnost s ATE, a pokud tomu tak přeci jen
je, bývají nároky na ATE výrazně nižší, než je tomu v případech, kdy
zařízení BIST část zcela postrádají.

Bylo vypracováno mnoho metodik pro návrh BIST, z nichž většina se
spoléhá na
\emph{generátor pseudonáhodných vektorů}
(angl. Pseudo-random Pattern Generator, dále jen
\emph{PRPG})
pro testování lehce detekovatelných poruch, které často představují
zhruba 90\% z celkového počtu všech možných poruch testovaného
obvodu
\cite{FISER_PT}.
Zbývající poruchy jsou pak testovány deterministicky sestavenou
posloupností testovacích vektorů, kterou generuje buď samotný BIST,
nebo externí ATE.

Jako generátoru pseudonáhodných vektorů se ponejvíce využívá
\emph{lineárního zpětnovazebního posuvného registru}
(angl. Linear Feedback Shift Register, dále jen
\emph{LFSR}) a
\emph{celulárního automatu}
(angl. Cellular Automaton, dále jen
\emph{CA}).
Tyto obvody jsou používány především z důvodů jejich jednoduché
struktury, s tím souvisejících nízkých prostorových nároků a dobrého
\emph{diagnostického pokrytí},
které vyjadřuje percentuální podíl poruch detekovaných testovací
posloupností získanou z takového generátoru ku celkovému počtu
detekovatelných poruch testovaného obvodu
\cite{HLAV98}.

Schéma základní struktury BIST je uvedeno na obrázku
\ref{fig:theory-bist_scheme}.
Samotný BIST se skládá z
\emph{generátoru testovacích vektorů}
(angl. Test Pattern Generator, dále jen
\emph{TPG}),
který produkuje testovací vektory postupně přiváděné na vstupy
\emph{testovaného obvodu}
(angl. Circuit Under Test, dále jen
\emph{CUT}) a
\emph{příznakový analyzátor}
(angl. Response Evaluator, dále jen
\emph{RE}),
který má za úkol vyhodnotit odezvu testovaného obvodu na takto
získané testovací vektory
\cite{FISER_PT}.
Z výše uvedeného je zřejmé, že TPG je realizován pomocí PRPG, který
může být dále upraven za účelem zlepšení jeho vlastností.

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.3\textwidth]{figs/bist_scheme}
\caption{Obecné schéma BIST}
\label{fig:theory-bist_scheme}
\end{center}
\end{figure}

Design TPG hraje v návrhu BIST klíčovou roli z hlediska jeho
výsledných vlastností, především pak dosahovaného diagnostického
pokrytí a prostorových nároků části obvodu implementující samotný
generátor. U strukturně jednoduchých TPG je zpravidla dosti obtížné
dosáhnout dostatečného pokrytí, a tak je ve většině případů výhodné
základní strukturu generátoru modifikovat způsobem, o kterém se
zmíníme dále v textu.

Typický TPG je ve své podstatě jednoduchý sekvenční logický obvod,
který generuje slova cyklického kódu definovaného
\emph{generujícím polynomem}.
Tato jsou přiváděna na vstup testovaného obvodu buď přímo, nebo po
modifikaci kombinační logikou. V takovém případě pak
z pochopitelných důvodů při návrhu usilujeme o to, aby byla tato
přidaná kombinační logika co možná nejjednodušší, a tedy co nejméně
náročná z hlediska plochy potřebné k její realizaci.%Navíc musíme
%v tomto případě vždy počítat s jistou výkonovou penalizací, která
%je způsobena zpožděním signálu při průchodu kombinační logikou.

\vfill\pagebreak

Na výše popsaném principu doplnění TPG kombinační logikou je
postaven tzv.
\emph{mixed-mode BIST}
\cite{FISER_PT}.
Takto navržený BIST pracuje ve dvou fázích:

\begin{enumerate}
\item{
Pseudonáhodné testovací vektory jsou z TPG přiváděny přímo na vstup
testovaného obvodu, aby tak testovaly co nejvíce lehce
detekovatelných poruch.
}

\item{
Vektory z TPG jsou modifikovány přidanou kombinační logikou tak,
aby testovaly poruchy nepokryté v první fázi. Někdy je za tímto
účelem namísto kombinační logiky použita přímo tabulka
předgenerovaných vektorů uložená buď v paměti BIST nebo ATE. Takové
řešení je výhodné pouze v případě, kdy je vektorů potřebných ve
druhé fázi relativně malý počet.
}
\end{enumerate}

\subsection{Lineární zpětnovazební posuvné registry}
\label{chap:theory-lfsr}

Jedna varianta struktury lineárního zpětnovazbního posuvného
registru, LFSR-I, je uvedena na obrázku
\ref{fig:theory-lfsr_scheme}.

\begin{figure}[hbp]
\begin{center}
\includegraphics[width=0.75\textwidth]{figs/lfsr_scheme}
\caption{Základní struktura LFSR}
\label{fig:theory-lfsr_scheme}
\end{center}
\end{figure}

LFSR-I se skládá z klopných obvodů typu D, které slouží k uchování
stavu celého registru, a z interních logických hradel typu XOR
tvořících zpětnou vazbu
\cite{FISER_PT}.
Počáteční stav klopných obvodů se nazývá
\emph{seed}
a jednoznačně určuje podobu posloupnosti stavů, kterými registr dané
struktury postupně prochází.

\emph{Paralelní výstupy registru}
odpovídají přímo výstupům jeho klopných obvodů a odebírají se z nich
testovací vektory.

Jako
\emph{sériový výstup}
je vyveden výstup posledního klopného obvodu. Sériové vstupy
a výstupy se při testování často používají z důvodu velice omezeného
počtu vývodů na čipu použitelných k tomuto účelu a umožňují
relativně snadnou inicializaci registrů a jejich pozdější čtení.
Navíc se tyto vstupy a výstupy dají použít pro propojení více
registrů do jednoho dlouhého řetězce, což má za následek další
úsporu použitých vývodů.

Sekvence kódových slov produkovaných takovým registrem je dána
\emph{generujícím polynomem}
nad Galoisovým polem $GF(2^n)$

\begin{equation}
g(x) = x^n + c_{n - 1}x^{n - 1} + ... + c_1x^1 + 1,
\end{equation}

kde koeficienty $c_1$ až $c_{n-1}$ vyjadřují, jestli je do vstupu
odpovídajícího klopného obvodu přivedena zpětná vazba a $n$ je
délka registru
\cite{FISER_PT}.

Pokud je navíc takový polynom
\emph{primitivní},
LFSR jím popsané struktury má maximální periodu $2^n - 1$, tj. je
schopen generovat celkem $2^n - 1$ různých testovacích vektorů
\cite{FISER_PT}.

Druhá varianta registru, LFSR-II, se od toho prvního liší ve způsobu
uzavření zpětné vazby. V tomto případě nejsou hradla XOR přidružena
k jednotlivým klopným obvodům, ale jsou soustředěna u vstupu
prvního klopného obvodu. Můžeme je pak nahradit jediným hradlem
o odpovídajícím počtu vstupů, které budou buzeny výstupy klopných
obvodů tak, jak to popisuje generující polynom.

\subsection{Celulární automaty}
\label{chap:theory-ca}

Celulární automaty (CA) používané jako generátory testovacích
vektorů mají obdobnou strukturu jako LFSR, ale používají zcela
jinak utvořenou zpětnou vazbu, která je v tomto případě silně
lokálního charakteru (viz obr.
\ref{fig:theory-ca_scheme})
\cite{FISER_PT}.

\begin{figure}[hbp]
\begin{center}
\includegraphics[width=0.75\textwidth]{figs/ca_scheme}
\caption{Struktura homogenního CA používajícího pravidlo 90}
\label{fig:theory-ca_scheme}
\end{center}
\end{figure}

Tyto automaty jsou ve své podstatě matematické idealizace přírodních
systémů, které se vyznačují tou vlastností, že jejich komplexita je
výsledkem dlouhodobě opakované aplikace jednoduchých pravidel.
Původním účelem CA bylo modelování takových systémů a biologických
procesů v nich probíhajících
\cite{CORNO02}.

Typický CA se skládá z konečného počtu
\emph{buňek},
které mohou nabývat konečného počtu hodnot, resp. 
\emph{stavů}. Funkce, která popisuje stav jednotlivých buňek
v závislosti na čase, je definována jako

\begin{equation}
S: CA \times T \rightarrow \Sigma,
\end{equation}

kde $CA = {C_i}$ je množina všech buňek, $T$ je množina diskrétních
časových kroků a $\Sigma$ je konečná abeceda symbolů
reprezentujících stavy buňek
\cite{CORNO02}.

Dá se říci, že každá buňka automatu představuje určitou část
modelovaného systému, ať už se jedná o část fyzickou nebo čistě
logickou. Žádná buňka v automatu přitom neexistuje sama o sobě
a její stav závisí převážně na stavu buňek v jejím
\emph{okolí}.
Toto je popsáno funkcí

\begin{equation}
N: CA \rightarrow CA^n,
\end{equation}

kde $n$ je počet buňek. Velikost takového okolí, tj. počet
sousedních buňek, je zpravidla pro každou buňku stejná. Budeme ji
značit jako $k = |N(C_i)|$
\cite{CORNO02}.

Vývoj buňek automatu v diskrétním čase je určen pevně danou sadou
\emph{pravidel}
popisujících chování jednotlivých buňek. Stav každé buňky
v následujícím časovém kroce je jednoznačně určen jí přiřazeným
pravidlem na základě stavu buňek v jejím okolí. Pravidla mají obecně
tvar

\begin{equation}
R: CA \times \Sigma^k \rightarrow \Sigma,
\end{equation}

kde $k$ je už dříve zmíněná velikost okolí buňek
\cite{CORNO02}.

CA lze dělit podle dvou základních kritérií
\cite{CORNO02}:

\begin{itemize}
\item{
podle
\emph{počtu unikátních pravidel} na
\emph{automaty hybridní} a
\emph{uniformní}.
Pokud je automat uniformní, všechny jeho buňky se řídí stejným
pravidlem.
}

\item{
podle
\emph{typu pravidel} na
\emph{automaty lineární} a
\emph{nelineární}.
Lineární automaty obsahují pouze lineární pravidla, tj. pravidla,
která je možná popsat lineární kombinací dílčích pravidel.
}
\end{itemize}

Automaty, které jsou jak hybridní tak lineární, jsou zpravidla
v literatuře označovány jako LHCA
\cite{CORNO02}.

Pro účely testování se nejčastěji používají jednodimenzionální
LHCA automaty s cyklickými hranicemi, kde levý soused první buňky
je poslední buňka a naopak. Samotné automaty jsou pak implementovány
logickými obvody složenými, obdobně jako LFSR, z klopných obvodů
typu D a logických hradel typu XOR.

Strukturu CA, jehož buňky mohou nabývat pouze dvou logických
hodnot, můžeme obecně popsat jedním ze dvou následujících způsobů:

\begin{itemize}
\item{
\emph{výčtem pravidel},
kterými se jednotlivé buňky CA řídí.

Pravidla popisující chování buňek jsou ve své podstatě boolské
funkce okolí popisovaných buňek, které je možné vyjádřit ve formě
pravdivostní tabulky s $2^k$ řádky, kde $k$ je velikost okolí těchto
buňek. Každý řádek takové tabulky tedy přiřazuje popisované buňce
nový stav v závislosti na stavu buňek v jejím okolí.

Pokud se na poslední sloupec tabulky, který představuje samotný
výstup pravidla pro různé stavy okolí popisované buňky, budeme dívat
jako na číslo zapsané v binárním kódu, můžeme pak pravidlo vyjádřené
touto tabulkou reprezentovat oním číslem převedeným do dekadické
soustavy (viz tab.
\ref{tab:theory-ca_rules},
která obsahuje linearizované pravdivostní tabulky některých
pravidel).

To nám pak umožní se na pravidlo jednoduchým způsobem odkazovat,
viz např. pravidlo 90, které nastaví buňku do logické jedničky
právě tehdy, když má tuto hodnotu pouze jeden z jejích sousedů
($S(C_{i - 1}) \oplus S(C_{i + 1})$ pro buňku $C_i$).

\begin{table}[hbp]
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{Smysl pravidla} &
\multicolumn{8}{|c|}{Stav okolí} &
\multirow{2}{*}{Číslo pravidla} \\
\cline{2-9}
& 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000 & \\
\hline
\hline
$S(C_{i - 1})$ &
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 &
240 \\
\hline
$S(C_{i - 1}) \oplus S(C_i)$ &
0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 &
60 \\
\hline
$S(C_{i - 1}) \oplus S(C_{i + 1})$ &
0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 &
90 \\
\hline
$S(C_{i - 1}) \oplus S(C_i) \oplus S(C_{i + 1})$ &
1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 &
150 \\
\hline
\end{tabular}
\end{center}
\caption{Příklad pravidel CA}
\label{tab:theory-ca_rules}
\end{table}

V případě popisu CA výčtem pravidel chování jednotlivých buňek
automatu lze získat nový stav libovolné buňky jako funkční hodnotu
pravidla pro aktuální stav buňek v okolí uvažované buňky.
}

\item{
\emph{charakteristickou maticí CA}.

Tato matice je čtvercového tvaru, kde počet řádků i sloupců odpovídá
celkovému počtu buňek CA. Každý její řádek popisuje okolí jedné
z buňek a hodnoty jeho prvků udávají přítomnost vazeb mezi
uvažovanou buňkou a buňkami odpovídajícími jednotlivým prvkům řádku.
Jednotková hodnota prvku znamená, že tato vazba existuje a pro
nulovou hodnotu platí opačné tvrzení.

Příklad takové matice pro CA tvořený šesti buňkami se strukturou
odpovídající obrázku
\ref{fig:theory-ca_scheme}
představuje obrázek
\ref{fig:theory-ca_matrix}.

\begin{figure}[hbp]
\begin{center}
\begin{tabular}{|cccccc|}
1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 \\
\end{tabular}
\end{center}
\caption{Příklad charakteristické matice CA}
\label{fig:theory-ca_matrix}
\end{figure}
}

V případě popisu CA jeho charakteristickou maticí lze získat nový
stav libovolné buňky automatu tak, že po určení okolí uvažované
buňky z příslušného řádku matice provedeme součet modulo 2 stavů
všech buňek tvořících toto okolí. Výsledná hodnota pak odpovídá
novému stavu uvažované buňky.
\end{itemize}

\subsection{Srovnání celulárních automatů s LFSR}

Pokud používáme LFSR pro generování pseudonáhodných testovacích
vektorů ve smyslu kapitoly
\ref{chap:theory-lfsr},
kde vektory odebíráme přímo z paralelních výstupů registru, takto
získaná posloupnost vektorů bude vykazovat poměrně výrazné znaky
pravidelnosti. Ty budou obvzláště patrné v případě, že struktura
registru bude popsána primitivním polynomem.

Takové chování je projevem korelace bitových posloupností tvořených
v čase stavy jednotlivých klopných obvodů registru
\cite{HORT90}.

Oproti LFSR mají CA tu výhodu, že jimi produkované posloupnosti
vektorů mají více náhodný charakter. To je důsledek podstatně
redukované korelace bitových posloupností klopných obvodů, za kterou
však zaplatíme zkrácením periody automatu
\cite{HORT90}.

Za účelem porovnání vlastností CA a LFSR z hlediska vhodnosti
jako generátoru testovacích vektorů v rámci BIST byla vypracována
celá řada studií, kromě
\cite{HORT90}
se jedná např. o
\cite{FISER_CM},
\cite{FISER_PT}
a další.

Na obrázku
\ref{fig:theory-ca_vs_lfsr}
převzatém z
\cite{FISER_PT}
je uveden výsledek jednoho takového měření srovnávajícího vlastnosti
CA a LFSR pro obvod c3540.

V rámci tohoto měření byly porovnávány CA s náhodně generovaným
seedem a kompletně náhodně vytvářené LFSR, u kterých byl kromě seedu
náhodně stanoven i generující polynom. V obou případech bylo takto
získanými CA a LFSR generováno 500 testovacích vektorů, které byly
posléze aplikovány na testovaný obvod a byl zaznamenán počet
nedetekovaných poruch. Celý proces se pak opakoval celkem
10000-krát.

Na obrázku samotném je znázorněno srovnání dosaženého pokrytí poruch
testovaného obvodu oběma generátory. Je z něj dobře patrné, že
rozdělení počtu nedetekovaných poruch oběma generátory má stejnou
střední hodnotu, ale v případě CA má menší standardní odchylku.
%Z toho plyne, že nahrazením LFSR za CA sice v průměru nebudme
%schopni detekovat více poruch, ale stoupne pravděpodobnost, že
%testovací vektory z CA pokryjí více poruch.

\begin{figure}[hbp]
\begin{center}
\includegraphics[width=0.4\textwidth]{figs/ca_vs_lfsr.png}
\caption{Porovnání pokrytí dosahovaného CA a LFSR}
\label{fig:theory-ca_vs_lfsr}
\end{center}
\end{figure}

\subsection{Celulární automaty s rozváženým seedem}
\label{chap:theory-unbalanced_ca}

V předchozí kapitole jsme uvažovali generátory pseudonáhodných
testovacích vektorů realizované pomocí CA a LFSR, jejichž seed byl
stanoven zcela náhodně a výskyt nul a jedniček v takovém seedu se
řídil rovnoměrným rozložením pravděpodobnosti. Takové generátory
jsou díky svým dobrým vlastnostem pro testování obvodů vhodné pro
použití v BIST.

V některých případech však bývá testování obvodů komplikováno
výskytem relativně malého počtu
\emph{těžce detekovatelných poruch},
kterých bývá typicky kolem 10\% z celkového počtu všech
detekovatelných poruch testovaného obvodu
\cite{FISER_PT}.
Tyto poruchy lze detekovat pouze a jedině jedním nebo několika málo
specifickými testovacími vektory. Až dosud uvažované generátory však
generují různé testovací vektory se stejnou pravděpodobností.
S přihlédnutím k tomuto faktu a vzhledem k mohutnosti prostoru
testovacích vektorů, je u takových generátorů šance na vygenerování
posloupnosti vektorů obsahující těchto několik konkrétních vektorů
velice nízká. U obvodů obsahujících takové poruchy je tedy nutné
sáhnout po upraveném způsobu testování, tzv.
\emph{váženém testování}
\cite{HORT90}.

Podstata tohoto způsobu testování spočívá ve změně rozložení
pravděpodobnosti výskytu nul a jedniček v různých částech
generovaných testovacích vektorů. Toho se dá kromě modifikace
vektorů přidanou kombinační logikou, jako je tomu například
v případě mixed-mode BIST, dosáhnout také vhodnou volbou seedu
jejich generátoru
\cite{HORT90}.
Takto nastavený generátor má pak výrazně vyšší pravděpodobnost
vygenerování vektorů, potřebných k detekci těžce detekovatelných
poruch.

Jeden možný způsob, jak takový seed zvolit je popsán v
\cite{FISER_PT}.
V rámci experimentu byly porovnávány CA a LFSR s náhodně vytvořeným
seedem a tytéž generátory s
\emph{rozváženým seedem},
tvořeným samými nulami a jednou, náhodně umístěnou jedničkou.
Výsledky celkem čtyř měření, během kterých bylo na obvod s838
aplikováno 500 testovacích vektorů získaných z takto nastavených
generátorů, jsou uvedeny na obrázku
\ref{fig:theory-unbalanced_ca}.

\begin{figure}[hbp]
\begin{center}
\includegraphics[width=0.4\textwidth]{figs/unbalanced_ca.png}
\caption{Pokrytí dosahované rozváženými CA a LFSR}
\label{fig:theory-unbalanced_ca}
\end{center}
\end{figure}

Z obrázku je patrné, že v některých případech dosahovaly rozvážené
CA podstatně lepšího pokrytí poruch testovaného obvodu než stejným
způsobem rozvážené LFSR. Z toho vyplývá, že pokud se pro testovaný
obvod povede zvolit ten správný seed, pak takové CA dosahují
vynikajících výsledků.

