ECE5505 Digital Test and Verification Notes Part I

Introduction

This is the blog for VT ECE5505 digital system test and verification course summary, it is currently working as a draft and not finalized.

test0

test1

Simulations

	Fault Simulation	Logic Sim
Definition	given a circuit, fault model, a test set, determine fault coverage
	determine test set quality ATPG, a vector
	Serial Parallel-fault Parallel-pattern Deductive Fault Simulation Concurrent Critical Path Tracing Statistical Differential Combined	STAFAN
	Non-statistical fault coverage estimation	Indirect Implication

Fault simulation: given a circuit, a fault model and a test set, determine the fault coverage(measure of quality) of the test set.

Faults Type


Untestable fault
Potentially detectable fault	$0 / x$ , $1 / x$
Init fault

Dominance&Equivalence

	Equivalence	Dominance
Definition	$f_{α} \equiv f_{β}$ $f_{α} \to f_{β} \to f_{γ}$	Under $T_{α} \supseteq T_{β}$ ,in $T_{β}$ $f_{α} \equiv f_{β}$
Collapsing	$2 n \to n + 1$	$n + 1 \to n$
test set	same	$T_{α} \supseteq T_{β}$
Fanout	transitivity not work		FOFree comb ckt: Test Set detect PI SA also detect all SA General comb ckt: test set detect PI&checkpint SA also detect all SA Irredundant comb ckt: a vec detects all single SA detects all testable multiple SA

Deductive Fault Simulation

Deductive fault simulation¹, propagate fault sets across combinatinal circuits. Lecture #6, section 10.

write down sets operation equations, then write down the fault list, always check the stems.

Name	Input	Output	$L_{c}$ fault list
OR	$a = 0, b = 0$	$c = 0$	${L_{a} \cup L_{b}} \cup \underset{OR}{c / 1} \underset{NOR}{c / 0}$
OR	$a = 0, b = 1$	$c = 1$	${L_{b} - L_{a}} \cup \underset{OR}{c / 0} \underset{NOR}{c / 1}$
OR	$a = 1, b = 0$	$c = 1$	${L_{a} - L_{b}} \cup \underset{OR}{c / 0} \underset{NOR}{c / 1}$
OR	$a = 1, b = 1$	$c = 1$	${L_{a} \cap L_{b}} \cup \underset{OR}{c / 0} \underset{NOR}{c / 1}$

for NOR,

c / 0 \to c / 1

and

c / 1 \to c / 0

Name	Input	Output	$L_{c}$ fault list
AND	$a = 0, b = 0$	$c = 0$	${L_{a} \cap L_{b}} \cup \underset{AND}{c / 1} \underset{NAND}{c / 0}$
AND	$a = 0, b = 1$	$c = 0$	${L_{a} - L_{b}} \cup \underset{AND}{c / 1} \underset{NAND}{c / 0}$
AND	$a = 1, b = 0$	$c = 0$	${L_{b} - L_{a}} \cup \underset{AND}{c / 1} \underset{NAND}{c / 0}$
AND	$a = 1, b = 1$	$c = 1$	${L_{a} \cup L_{b}} \cup \underset{AND}{c / 0} \underset{NAND}{c / 1}$

for NAND,

c / 0 \to c / 1

and

c / 1 \to c / 0

Name	Stem	Branch	$L_{c}$ fault list
Fanout	$a = 0$	$b = 0, c = 0$	$L_{c} = L_{a} \cup c / 1$ $L_{b} = L_{a} \cup b / 1$
Fanout	$a = 1$	$b = 1, c = 1$	$L_{c} = L_{a} \cup c / 0$ $L_{b} = L_{a} \cup b / 0$

Name	Input	Output	$L_{c}$ fault list
NOT	$a = 0$	$c = 1$	$L_{a} \cup c / 0$
NOT	$a = 1$	$c = 0$	$L_{a} \cup c / 1$

Name	Input	Output	$L_{c}$ fault list
XOR	$a = 0, b = 0$	$c = 0$	${L_{a} - L_{b}} \cup {L_{b} - L_{a}} \cup c / 1$
XOR	$a = 0, b = 1$	$c = 1$	${L_{a} - L_{b}} \cup {L_{b} - L_{a}} \cup c / 0$
XOR	$a = 1, b = 0$	$c = 1$	${L_{a} - L_{b}} \cup {L_{b} - L_{a}} \cup c / 0$
XOR	$a = 1, b = 1$	$c = 0$	${L_{a} - L_{b}} \cup {L_{b} - L_{a}} \cup c / 1$

for XNOR,

c / 0 \to c / 1

and

c / 1 \to c / 0

, deducted by myself.

Critical Path Tracing&Star Algorithm

Critical Path Tracing

Star Algorithm

definition

sensitive:

a \to z

\overset{―}{a} \to \overset{―}{z}

critial: fault

v / \overset{―}{v}

detected by vec

t

O_{c r i t i c a l} \to I_{s e n s i t i v e} \to I_{c r i t i c a l}

sufficient: Input that can set the output value
Unmarked

\overset{―}{V}

Untestable

stem

stem analysis: for all fanouts, for each fanout, if there exists a sensitive path that connect to the reconvergence gate(no need to be sensitive input), it so cannot traceback to stem.

can track back to stem

AND, NAND

\²

Rule

Equation 1(AND)

Equation 2(OR)

De Morgan’s Laws

\overset{―}{A \cdot B} \equiv \overset{―}{A} + \overset{―}{B}

\overset{―}{A + B} \equiv \overset{―}{A} \cdot \overset{―}{B}

distributive

A \cdot (B + C) = (A \cdot B) + (A \cdot C)

A + B \cdot C = (A + B) \cdot (A + C)

associative

\³

Since D algorithm needs to init with X, frontiers are needed.

Name	Input	Output	Usage
D-Frontier⁴ on their inputs.)) $D / \overset{―}{D} \Rightarrow X$	$D$ (or $\overset{―}{D}$ )	$X$	PODEM: D-Frontier Empty then backtrace Speed up D-Algorithm
J-Frontier⁵ $X \Rightarrow D / \overset{―}{D}$	not justified	Known	Speed up D-Algorithm
E-Frontier⁶ $K n o w n \Rightarrow K n o w n$	$0, 1, X, D, \overset{―}{D}$	$0, 1, X, D, \overset{―}{D}$	PODEM with same E-Frontier, outside E=Frontier could copy PI values

PODEM⁷

Path-Oriented DEcision Making

D algorithm and PODEM finding one vector not in linear way but in binary tree way in the whole vector space, rather than find all in Boolean Differences.

Flowchart

pick objective (excitation or propagation of D)
backtrace from objective to PI that is X, if can’t backtrace, backtrack

objective->backtrace/backtrack->logic simulation
backtrack: reverse decisions
backtrace: tracing backwards

PODEM	D-Algorithm
Decisions on PIs only Values assigned to PIs only No internal value conflicts	Decisions on any gate Values assigned anywhere Possible internal values conflicts

Decision on backtrack BETTER

	output=0	output=1
AND	select easier one	select hard one first then easier one
OR	select hard one first then easier one	select the easier one

Cost to decide which is easier

by distance: distance of gate from PI to PO but cannot guarentee easier

Implications

Make better decisions by checking implications before justify/propagate, implications knowledge as a graph to save storage

contra-positive law for non-trivial logic: if $a \to b$ , then $\overset{―}{b} \to \overset{―}{a}$

Indirect implications, do logic simulation, add new values and implications

Controllability Observability Probability

signals uncorrelated or independent meaning no signal reconvergence, not consider circuit structure, observability computatoin similar to STAFAN. Consider the PI controllability and PO observability to be $0.5$ .

\begin{align} d&=a\cdot b\cdot c\\ P_{d}&=P_{a}\cdot P_{b}\cdot P_{c}\\ P_{\bar{d}}&=1-P_{d} \end{align}

	$C_{x}$	$O_{x}$
x=PI	$0.5$
x=PO		$0.5$ from YouTube $1$ from class
$x = a \cdot b$	$C_{x} = C_{a} \cdot C_{b}$ $C_{\overset{―}{x}} = 1 - C_{a} \cdot C_{b}$	$O_{a} = \underset{Obervability}{\underset{⏟}{O_{x}}} \cdot \underset{Sensitization of a}{\underset{⏟}{C_{b}}}$
$x = a + b$	$C_{x} = 1 - (1 - C_{a}) \cdot (1 - C_{b})$ $C_{\overset{―}{x}} = C_{\overset{―}{a}} \cdot C_{\overset{―}{b}}$	$O_{a} = \underset{Obervability}{\underset{⏟}{O_{x}}} \cdot \underset{Sensitization of a}{\underset{⏟}{(1 - C_{b})}}$
from stem x to a and b	$C_{x} = C_{a} = C_{b}$	$O_{x} = 1 - (1 - O_{a}) \cdot (1 - O_{b})$

Testability COP⁸

Sensitization: similar to boolean diff, so boolean diff is observability, compute P forward and O backwards. Observability similar to STAFAN.

\begin{align} S\left(l\right)=P_{a}\cdot P_{b}\\ O_{l}=O_{m}\cdot S_{l} \end{align}

SCOAP: Controllability/Observability⁹

$C_{1}$ controlability of value to 1, $C_{0}$ controlability of value to 0, $O$ overservability. Values are integer, small values means easy for controllability. $f_{f o} ()$ means fanout penalty according to level or number of fanouts.

	$C_{0}, C_{1}$	$O$
$d = a \cdot b \cdot c$	$C_{0} (d) = min (C_{0} (a), C_{0} (b), C_{0} (c)) + f_{f o} (d)$ Special case¹⁰ $C_{1} (d) = max (C_{0} (a), C_{0} (b), C_{0} (c)) + f_{f o} (d)$	$O (a) = O (d) + C_{1} (b) + C_{1} (c)$
$z = w + x + y$	$C_{0} (z) = max (C_{0} (w), C_{0} (x), C_{0} (y)) + f_{f a n o u t} (z)$ $C_{1} (z) = min (C_{0} (w), C_{0} (x), C_{0} (y)) + f_{f o} (d)$	$O (w) = O (z) + C_{0} (x) + C_{0} (y)$
$a = \bar{b}$	$C_{0} (b) = C_{1} (a) + f_{f o} (b)$ $C_{1} (b) = C_{0} (a) + f_{f o} (b)$	$O (a) = min (O (b), O (c))$

¹¹

	STAFAN
	$d_{f} = P_{f d e t} = C \cdot O$ $P_{f n d e t N} = 1 - (1 - d_{f})^{n}$ $P_{f d e t N 1} = 1 - (1 - (1 - d_{f})^{n})$
	independent fanout free
	controlability: $C$ observability: $O$

probability related concepts

Fanout-oriented TG(FAN)

multiobjective, headlines: singals at the output of fanout-free regions

Dominator

Dominator: gate g of a signal s, whree all paths from signal s to all POs must pass through g.

Can be used to set objectives for a fault, since the $dom (g)$ needs to be $D, \overset{―}{D}, X$ in order to test.

\begin{aligned} \text{dom}(g) &= \begin{cases} \underbrace{\{\text{succ}(g)\} \cup \text{dom}(\text{succ}(g))}_{\substack{\color{blue}{\text{Include successor and its domain}}}} , & \text{if } \underbrace{\#\text{fanout}(g) = 1}_{\substack{\color{green}{\text{one successor}}}} \\[4ex] \underbrace{\bigcap_{\forall succ(g)} \text{dom}(\text{succ}(g))}_{\substack{\color{red}{\\\text{Intersection for all successor}}}} , & \text{if } \underbrace{\#\text{fanout}(g) > 1}_{\substack{\color{green}{\text{multiple successors}}}} \end{cases} \end{aligned}

Dynamic dominator: when some PIs are assigned, existing X-paths reduce, more dominators possible.

Satisfiability-Based ATPG

SAT: given a formula f, derive a value assignment that will satisfy f.

\begin{align} a\rightarrow b &\equiv \overline{a}+b\\ b\rightarrow a &\equiv \overline{b}+a \end{align}

\begin{align} \underset{\color{red}{z=x\cdot y}}{\text{SAT}}&=(xy\rightarrow z)\cdot (z\rightarrow xy)\\ &=(\overline{xy}+z)\cdot (\overline{z}+xy)\\ &=(\overline{x}+\overline{y}+z)\cdot (\overline{z}+x)\cdot(\overline{z}+y) \end{align}

\begin{align} \underset{\color{red}{z=x+y}}{\text{SAT}}&=(x+y\rightarrow z)\cdot (z\rightarrow x+y)\\ &=(\overline{x+y}+z)\cdot (\overline{z}+x+y)\\ &=(\overline{x}\cdot\overline{y}+z)\cdot(\overline{z}+x+y)\\ &=(\overline{x}+z)\cdot(\overline{y}+z)\cdot(\overline{z}+x+y) \end{align}

\begin{align} \underset{\color{red}{x=\overline{y}}}{\text{SAT}}&=(x\rightarrow \overline{y})\cdot (\overline{y}\rightarrow x)\\ &=(\overline{x}+\overline{y})\cdot (x+y) \end{align}

\begin{align} \underset{\color{red}{z=x\oplus y}}{\text{SAT}}&=(x\oplus y\rightarrow z)\cdot (z\rightarrow x\oplus y)\\ &=(\overline{x\oplus y}+z)\cdot (\overline{z}+x\oplus y)\\ &=(\overline{x}+y+z)\cdot(x+\overline{y}+z)\cdot (\overline{x}+\overline{y}+\overline{z})\cdot (x+y+\overline{z}) \end{align}

\begin{bmatrix} \overset{\text{\textcolor{red}{0}}}{\phantom{a_{11}}} & \overset{\textcolor{red}{D}}{\phantom{a_{12}}} & \overset{\text{elements}}{\phantom{a_{13}}} \\[-1ex] \color{red}{0/0} & \textcolor{red}{1/0} & \textcolor{green}{X/0} \\[2ex] \overset{\text{middle}}{\phantom{a_{21}}} & \overset{\textcolor{red}{1}}{\phantom{a_{22}}} & \overset{\text{entries}}{\phantom{a_{23}}} \\[-1ex] \textcolor{green}{0/X} & \textcolor{red}{1/1} & \textcolor{green}{X/0} \\[2ex] \overset{\textcolor{red}{\overline{D}}}{\phantom{a_{31}}} & \overset{\text{row}}{\phantom{a_{32}}} & \overset{\textcolor{red}{X}}{\phantom{a_{33}}} \\[-1ex] \textcolor{red}{0/1} & \textcolor{green}{1/X} & \textcolor{red}{X/X} \end{bmatrix}

Glossary

eBook

Lec 6: Fault Simulation[]
a=0)\cdot (b= 0) \rightarrow c=0/1\)
$(\overset{∙}{a = 0}) \cdot (b = 1) \to c = 0 / 1$
$(a = 1) \cdot (\overset{∙}{b = 0}) \to c = 0 / 1$
$(\overset{∙ b o t h}{a = 1}) \cdot (\overset{∙ b o t h}{b = 1}) \to c = 1 / 0$

(\overset{* e i t h e r}{a = 0}) \cdot (\overset{* e i t h e r}{b = 0}) \to c = 0 / 1

(\overset{*}{a = 0}) \cdot (b = 1) \to c = 0 / 1

(a = 1) \cdot (\overset{*}{b = 0}) \to c = 0 / 1

(\overset{* b o t h}{a = 1}) \cdot (\overset{* b o t h}{b = 1}) \to c = 1 / 0

OR, NOR

(\overset{∙ b o t h}{a = 0}) + (\overset{∙ b o t h}{b = 0}) \to c = 0 / 1

(a = 0) + (\overset{∙}{b = 1}) \to c = 1 / 0

(\overset{∙}{a = 1}) + (b = 0) \to c = 1 / 0

(a = 1) + (b = 1) \to c = 1 / 0

NOT

(\overset{∙}{a = 1}) \to c = 0

(\overset{∙}{a = 0}) \to c = 1

XOR, XNOR

(\overset{∙ b o t h}{a = 0}) \oplus (\overset{∙ b o t h}{b = 0}) \to c = 0 / 1

(\overset{∙ b o t h}{a = 0}) \oplus (\overset{∙ b o t h}{b = 1}) \to c = 1 / 0

(\overset{∙ b o t h}{a = 1}) \oplus (\overset{∙ b o t h}{b = 0}) \to c = 1 / 0

(\overset{∙ b o t h}{a = 1}) \oplus (\overset{∙ b o t h}{b = 1}) \to c = 0 / 1

ATPG

Automatic test pattern generation

Boolean Difference

Expensive for large circuits, regarding time and space. D-algorithm and PODEM are used since one vector is enough for testing.

\begin{align} \underset{\color{green}{\text{Boolean Diff}}}{B_{\alpha/x}}&= \underset{\color{red}{\text{fault}\:\alpha\: \text{st}\: x}}{\alpha\left ( x \right )} \cdot \underset{\color{blue}{\text{PO }z\text{ Val Diff}}}{\frac{\mathrm{d} f_{z}\left(\alpha\right)}{\mathrm{d} \alpha\left ( x \right )}}\\ &=\alpha\left(x\right) \cdot \left(f_{z}\left( \alpha=0 \right)\right)\oplus \left(f_{z}\left( \alpha=1 \right)\right)\\ &= \alpha\left(x\right) \cdot \left[ f_{z}\left( \alpha=0 \right)\cdot \overline{ f_{z}\left( a=1 \right)}+\overline{f_{z}\left( a=0 \right)}\cdot f_{z}\left( a=1 \right)\right] \end{align}

\begin{aligned} \underbrace{B_{\alpha/x}}_{\substack{\color{green}{\text{Boolean Diff}\\}}} &= \underbrace{\alpha(x)}_{\substack{\color{red}{\text{Fault }\alpha\\\text{ st }x}}} \cdot \underbrace{\frac{\mathrm{d}f_z\Big[\alpha(x)\Big]}{\mathrm{d}\alpha(x)}}_{\substack{\color{blue}{\text{PO }z \text{ Val Diff}}}} \\[2ex] &= \underbrace{\alpha(x)}_{\substack{\color{red}{\text{Excite fault}}}} \cdot \Big[\underbrace{f_z(\alpha=0) \oplus f_z(\alpha=1)}_{\color{blue}{\text{XOR of output values}}}\Big] \\[2ex] &= \underbrace{\alpha(x)}_{\substack{\color{red}{\text{Excite fault}}}} \cdot \Big[\underbrace{f_z(\alpha=0) \cdot \overline{f_z(\alpha=1)} + \overline{f_z(\alpha=0)} \cdot f_z(\alpha=1)}_{\color{blue}{\text{Expanded XOR operation: sensitize difference for propagation}}}\Big] \end{aligned}

\begin{align} \frac{d x}{da}&= \left(x\left( a=0 \right)\right)\oplus \left(x\left( a=1 \right)\right)\\ &= x\left( a=0 \right)\cdot \overline{ x\left( a=1 \right)}+\overline{x\left( a=0 \right)}\cdot x\left( a=1 \right) \end{align}

Boolean Algebra

Boolean Algebra(([]

AB)C=A(BC)\)

(A + B) + C = A + (B + C)

Boolean Algebra

D Algorithm

Init with X, Justify recursively to PI and Propagate by recursively backtrack

Frontiers((D-Algorithm[]
All gates whose output values are X, but have $D$ (or \(\overline{D}\[]
Justification Frontier: All gates whose output values are known (implied by problem requirements) but are not justified by their gate inputs.[]
Evaluation, input and output are known[]
Combinational ATPG, PODEM[]
6 3 Testability COP[]
SCOAP: Sandia Controllability Observability Analysis Program[]
$C_{0} (g) = l e v e l (g)$ in fanout free circuits if circuit contains only AND gates[]
6 1 Testability Intro[]

ECE5505 Digital Test and Verification Notes Part I

Introduction

Simulations

Faults Type

Dominance&Equivalence

Deductive Fault Simulation

Critical Path Tracing&Star Algorithm

PODEM7

Decision on backtrack BETTER

Implications

Controllability Observability Probability

SCOAP: Controllability/Observability9

Fanout-oriented TG(FAN)

Dominator

Satisfiability-Based ATPG

Glossary

ATPG

Boolean Difference

Boolean Algebra

D Algorithm

Comments

One response to “ECE5505 Digital Test and Verification Notes Part I”

Leave a Reply Cancel reply

PODEM⁷

SCOAP: Controllability/Observability⁹