ECE5505 Digital Test and Verification Notes Part II

This blog serves as the 2nd and last part for the class ECE5505 Digital Test and Verification. The first part of the notes can be found here.

№ 12 Oct 15	№ 13 Oct 15, Oct 24	№ 14 Oct 24, Oct 29	№ 15 Oct 29, Oct 31
№ 16 Oct 31, Nov 05, Nov 07	№ 17 Nov 07, Nov 12	№ 18 Nov 12, Nov 14	№ 19 Nov 14, Nov 19
№ 20 Nov 19, Nov 21	№ 21 Nov 21, Dec 03	№ 22 Dec 03	№ 23 № 24 Dec 05

Sequential Circuit

D Flip Flop

Delay/Data flip flop: The flip flop remains in its current state until its receives a signal like clock that switches it to opposite state. The clock single required for the synchronous version of D flip flops but not for the asynchronous one.

Clock	$Q(n)$	$D(n)$	$Q(n+1)$	state
$\uparrow \gg 0$	0	0	0	hold
	0	1	1	reset
	1	0	0	reset
	1	1	1	hold

$\overline{PR}$	$\overline{CLR}$	$CLK$	$D$	$Q$	$\bar{Q}$
0	1	X	X	1	0
1	0	X	X	0	1
0	0	X	X	X	X
1	1	$\uparrow$	1	1	0
1	1	$\uparrow$	0	0	1
1	1	0	X

Iterative Logic array

Step	Time Frame	Procedure	optimization
$1$	$0$	PI=PI+FF PO=PO+FF PODEM for PIs	reduce flip flop state vars
$2$	$⩾1$	Propagate to actual PO frame by frame TG for frames $⩾1$backwards states could be unjustifiable, find alternative Additional constraints on TF$0$	reduce propagate frame nums detect illegal/unreachable states
$3$	$-1$	input seq with FF states (x) to justify TF$0$ justify FF states at time frame $0$ states could be unjustifiable, find alternative	illegal/unreachable state 0 justify from unknown state could have long sequence

Sequential circuit with Drivability $\text{D()}$ in addition to observability, controllability, drivability means drive to D or -D from g with respect to controllability.

S-Graph: vertices are FFs, edges means combinational path in between, if acylic(not going back to itself), faulty state is always initializable, $d_{seq}$, num of FFs on the longest path in s-graph, non-FF fault in acyclic circuit has at most $d_{seq}+1$ vectors.¹

Balanced model is used in cyclic sequential circuits.

Fault simulation Based Sequential ATPG

CONTEST

each phase has a specific cost function, to init FFs, to detect faults, to activate and propgate.

DIGATE

FF specific, faults propagates to a specific FF, power means if T could distinguish states for lots of faults; distinguishing seq are not useful if fault not activated, meaning excite&prop to one FF.

Targeting fault activation

state justfication of the reLaxed state

a particular ff set/reset, conflics when justifying several FFs at the same time.

pseudo-register justificaiton

a group of ffs

STRATEGATE²

state-traversal based: targeting entire state

State Justification of relaxed state	justification fault sim
Pseudo-Register	justification
STRATEGATE	justification

Logic-simulation based sequential atpg

For logic-simulation based sequential atpg, it is about how many states visited, how to visit new states.

RNG, reward new state, reward by state diff, STRATEGATE

Sequential Circuit Test Set Compaction

Insertion	switch order		expensive
Omission	Omitted Flag		expensive
selection			expensive
Inert Subseq Removal	$\{\begin{array}{c}{S}_1\equiv S_3,T_2\text{ between}\\ \text{no faults det in }{T}_2\end{array}$ excitation 3 cases
state-recurrence subseq removal	$\{\begin{array}{c}{S}_1\equiv S_3,T_2\text{ between}\\ \text{some faults det in }{T}_2\end{array}$ if faults det later
inertstate-re cucurrence
Relaxed subseq Removal	$S_1\Rightarrow S_2$ $S_1^{\ast }\Rightarrow S_2$ relax backwards $S_n\Rightarrow S_{n-1}^{\ast }\cdots$compatible: $S_i^{\ast }\equiv S_{i+1}^{\ast }$
Reduce cost of compaction	don’t compact seq covers most faults. compact seqs covers small part of faults. $T_k+T_z=80$ $T_k\Rightarrow T_k$ $T_z\Rightarrow T_z^c$
Vector Restoration	move $m\to n$ to front after init seq $n-(m-k)$		expensive

Compaction apply for ATPG

Analyze the patterns during compaction.

Untestable Fault Identification

D algorithm – Combinational ATPG in DFT (VLSI)

extened backward implication

Extended Backward Implication³

forward implication: if all input values are known or one is controlling value, the output can be determined.

backward implication: calculate input implication by the output value.

if output=1, implicates all gate inputs are 1, add implications of setting these inputs to 1.

if ouput=0, implicates at least one of the input is 0, need to add implications of setting each of these inputs to 0 and then union to make sure at least one of inputs is 0. It is trying to constrain the implication than to conclude in case where implication to one input is 0 and implication to another input is 1. Perhaps this is because implication of only input to 0 cannot guarantee the output to be 0. Implications needs to be propagated through gates like deductive fault simulation.

Size of $S_0$ and $S_1$ are critical, larger better, size depends on implications.

Single fault theorem

$f(i)$ must be excited at a time frame before it can propagated. $\overline{f(i)}\Rightarrow \overline{f(i+j)}$, untestable fault $\overline{f(i)}$ cannot be tested in later time frames because it is not excited; $\overline{f(i+j)}\nRightarrow \overline{f(i)}$, later time frame untestable faults may be testable in previous time frames because later time frames FFs state could be more constrained.

Bridging Faults

$a$ and $b$ are before bridging faults, $a^{\prime }$ and $b^{\prime }$ are after bridging faults. $a\ne b$ to excite the bridge, for feedback bridge, it is better to set the gate value that is closer to PO, otherwise there will be cycle. Issues: byzantine, dynamic CMOS gates. Feedback bridges may cause infinite cycle due to sensitized values.

type	fault	domination	testing
AND-Bridge	$a^{\prime }=b^{\prime }\Leftarrow \text{AND}(a,b)$	0 dominants	$\text{TEST}(b/0;a=0)||\text{TEST}(a/0;b=0)$
OR-Bridge	$a^{\prime }=b^{\prime }\Leftarrow \text{OR}(a,b)$	1 dominants	$\text{TEST}(b/1;a=1)$
a-dominant	$a^{\prime }=b^{\prime }\Leftarrow a$	a dominants	$\text{TEST}(b/0;a=0)\mathrm{\&}\mathrm{\&}\text{TEST}(b/1;a=1)$
b-dominant	$a^{\prime }=b^{\prime }\Leftarrow b$	b dominants	$\text{TEST}(a/0;b=0)\mathrm{\&}\mathrm{\&}\text{TEST}(a/1;b=1)$
feedback bridge			$\text{TEST}(b/0;a=0)$ only test gate that is closer to PO.

Delay Path Fault

Non-Robust test may not propagate the transition, in non-robust test, off path do not delay.

Validatable non-robust PDF: if $g_i$ side input with value $x$can invalidate non-robust test, if ensure paths through $x$ are not faulty/late, non-robust test is validated. Validate through generate robust test, if not possible, generate non robust test.

Gate Type	Fault Type	Non-Robust	Robust
AND	$\uparrow$	$01\cdot x1:01/00$	$01\cdot x1:01/00$
AND	$\downarrow$	$10\cdot x1:x0/x1$	$10\cdot 11:10/11$
OR	$\uparrow$	$01+x0:x1/x0$	$01+00:01/00$
OR	$\downarrow$	$10+x0:10/11$	$10+x0:10/11$

skewed Load: PI same, $S_2$ is the shifted version of $S_1$.

Boradside: PI different, $S_2$ is the justified version of $S_1$.

Enhanced Scan: $S_1$ and $S_2$ are totally different, each state will use its own vector from PI.

Finite State Machine

Initialization Sequence: takes current state of a circuit to a desired/specific state.

Distinguishing Sequence: a sequence that produces a unique output depending on the current state.

shortest transfer sequence back to the same starting state.

C-testable: if it has an iterative logic array structre and has a constant number of test vectors independent of the number of cells in iteraive logic array. Every block has seen all 8 vectors.

Universal test set: detect all detectable faults regardless of impementaion of comnbinationa function; covering $V_1\subseteq V_2\Rightarrow 0011\subseteq 0111$; unate only one type and binate with value and its inversed value. union of minimal true vector and maximum false vector.

If no unate variables, universal test set becomes exhaustive test set.

True or false vector: make output z to 1, otherwise; minimal true vector: does not cover other vectors.

Monotone: if circuit does not have inverters, $v_2\subseteq v_1\Rightarrow z(v_2)\subseteq z(v_1)$

minimal true vector

converse is $v_1$ does not detect fault, cannot claim about $v_2$.

maximum false vector

Register Transfer Level

global data path constraints extraction: simulate and obtain relationships that could be used in atpg.

transparent channel: path from PI exists that can provide required value to Mudule Under Test, as well as one that bridges the MUT output to global PO=>design for testability

Reemove the irrelevant blocks(program slicing, identify the variables and statements): slicing, remove irrelevant/independent statements, resynthesize, ATPG(removed PIs are don’t care). Input of new design is subset of the original design.

Behavior-level ATPG: test case~input vector, lines being executed, statement coverage, condition coverage, path coverage.

Design for Testability

modified circuit must retain original circuit functionality

test point insertion: controlability for 1 is low, using mux with mux input tied to 1, eliminating a testing pin; for the algorithm: add one testing point; recompute for highest controllability and observability; add to another hardest gate; control pins could be reduced with encoder, assuming control one point at a time.

scan design: scanned FFs connected in a chain; shift register; force values to FFs; shift out to observe.

Scan FFs on critical path: no longer works at the designated frequency, the frequency would reduce since additional muxes are added.

	specs
full scan	$\text{cycles}=n+1$ $\text{pattern}=n+m$ $m\Rightarrow \text{num of PIs}$	combinational atpg area, test time, storage shift in lower speed
multiple scan chains	$\text{cycles}=n/k$	shift in parallel $k$ more pins
Illinois Scan		series mode broadcast mode with same value per chain test data volume reduced in broadcast mode atpg constained in broadcast mode
partial scan		critical path, area avoid chaining congested area test time, test data volume seq atpg, validation of vectors are complicated.
partial reset	jumps to different state	avoid chaining
direct load	load value from PI to multiple FF directly $PI(k)\Rightarrow FF(a,b,\cdots ,z)$	area

Flip Flop Selection

testability, cycle-cutting/structure, atpg, hybrid

testability	calculate scoap selecte highest $\text{C0}/\text{C1}/\text{O}$ scan the FF$\text{C0}=\text{C1}=\text{O}=0$ repeat	approximation, SCOAP assumes no correlation greedy
structure	S graph node, edge break cycles by scan a FF exclude self cycles
atpg	seq ATPG examine faults that aborted4
structure+atpg	cycle density: FF states being reached, valid states testability of FF: density of all cycles involving the FF
structure+atpg	used aborted states
testability+atpg	$C_0,C_1$ FFs can reach most # of aborted states
WANT atpg	make aborted states reachable from easy-to-reach states
Random Access Scan

high level dft: scan registers that are hard to observe and control; behavior modification

Built-in Self Test

ATE: automatic test equipment

storage: vectors and responses, instead of responses store signatures and compare with vectors, use 1/2 of the storage.

Name Type		Pros	Cons	Misc
Signature Output, parity	XOR		$P_1=0.5$ $P_n=1-{\frac{1}{2}}^n$
Counter Output/Transition	$\left(\begin{array}{c}\underset{\begin{array}{c}\text{Total Num}\end{array}}{\underbrace{N}}\\ \underset{\begin{array}{c}\text{Num of 1s}\end{array}}{\underbrace{\text{k}}}\end{array}\right)$ $\frac{1}{\sqrt{\pi m}}$ with n POs.		Expensive because of FFs
Coding Theory	decoding: div LFSR Mod 2 div quotient/ouput out, remainng values are remainder
LFSR5 I OR O	quotient remainder	Fewer FFs than counter alising small	more expansive than parity for each PO
MISR6 Output ORA	POs connect to XORs of LSFR $N_{FF}=2.5n$ $N_{XOR}=n-1$	FFs nums are significantly smaller low prob of aliasing
TPG7	on-chip TPG: on ROM $n\times m$ Exhaustive: counter Pseudo exhaustive: each part Pseudo random: LSFR		large area for on-chip TPG
PRPG8 Input LSFR	Output of LSFR to circuit input PRPG Weighted PRPG	randomness
BIST9 ORA10 TPG7		no ATEs place TPG	fault coverage low determine exact fault coverage diagnose	delay fault bist: low power bist: shift groups of 0s and 1s.
STUMPS11	SRSG is LSFR Full scan BIST	better coverage due to full scan	1 misr signature, difficult to diagnose$\Rightarrow$compute parity
BILBO12	convert regs to BILBO regs test in pipeline BILBO reg: 2 control bits with n bits reg. testing blocks with input reg as LSFR and output reg as MISR

Memory Test

components: RW control, addr decoder, data reg, cell array.

cell-array faults: stuck-at, transition, coupling, pattern sensitive; march test;

Test Word-Oriented Memories: intra-word coupling, coupling on the same row, m-out-of-n codes, $C_n^m$, hamming distance.

Pattern sensitive faults: using hamming distance graph traversal to minimize num of writes.

SoC testing: cannot test all components at the same time, allocate by power and testing time for each component.

Compress data:

Defects, Diagnosis

inductive failure analysis:

region based diagnosis: force output of region to $x$, check the the faulty PO to see if $x$ is propagated. If not, that region does not have defects.

Glossary

№ 14 Oct 24, 2024~Oct 29, 2024

Test Set Compaction Fundamentals: sequential circuit test set compaction, test application time reduction, test data volume reduction, fault-free/faulty state notation (Sk/Sk^f), fault detection principles, fault simulation requirements, and basic state traversal concepts; Primary Compaction Methodologies: compaction by insertion for sequence manipulation, compaction by omission using flagged vectors, compaction by selection with covering algorithms, compaction by subsequence removal focusing on state patterns, and compaction by vector restoration through fault simulation; Sequence and State Analysis: test sequence management, vector sequence optimization, subsequence identification, state recurrence patterns, inert subsequence characteristics (where start/end states are identical with no fault detection), state-recurrence subsequence properties (where start/end states match but faults may be detected), and state relaxation concepts; Implementation and Optimization Techniques: fault coverage measurement, distinction between hard and easy faults, fault partitioning strategies, fault detection point analysis, excitation point identification, covering algorithm application, and computational cost considerations.

Sequential Circuit Test Compaction Foundations: motivation to reduce test application time and data volume, sequential vs combinational test set differences, state notation using Sk/Sk^f format, and problem of sequence disruption when removing vectors; Compaction Techniques and Algorithms: compaction by omission using vector flags and fault simulation, compaction by subsequence removal exploring state repetitions, inert subsequence identification where start/end states match without fault detection, state-recurrence subsequence where faults may be detected within, and relaxed subsequence removal considering state variables; State and Fault Analysis: state traversal concepts, fault excitation and detection points, fault partitioning focusing on hard faults versus easy faults (approximately 10% are hard faults), state comparison and matching, and fault simulation without fault dropping; Cost and Performance Considerations: computational expense of early techniques, comparison of technique effectiveness, improvement through targeting groups of flip-flops (pseudo registers), state reachability analysis, and the significance of fault detection coverage; Vector Restoration and State Management: computing detection time for each fault, fault restoration procedures, vector sequence analysis, investigation of state traversal patterns, and optimization through state space exploration.

№ 15 Oct 29, 2024~Oct 31, 2024

Untestable Fault Identification Foundations: motivation to reduce ATPG time spent on untestable faults, classification into combinational and sequential untestable faults, fault-dependent analysis approach per individual fault, fault-independent analysis based on circuit structure; FIRE Algorithm and Key Components: Fault Independent Redundancy identification, computation of S0 and S1 sets for conflicting value requirements, implementation of extended backward implications, analysis of constant nodes, and effectiveness based on implication count; Sequential Circuit Extensions: extending FIRE to sequential circuits, handling illegal/unreachable states as conflicts, incorporation of sequentiality into implication graphs with edge weights, identification of sequential conflicts; Graph Management and Optimization: managing implication graph size (2 x n nodes), handling exponential edge growth, periodic graph trimming through transitive reduction and equivalent node elimination, identification of strongly-connected components (SCCs), using representative nodes to achieve approximately 50% node reduction; Fault Analysis Algorithms and Theorems: fault-dependent untestable fault identification using necessary value lists, sequential circuit fault analysis with time-frame consideration, single fault theorem for combinational algorithm application to sequential circuits, and proof that combinationally untestable faults are also sequentially untestable.

№ 16 Oct 31, 2024~Oct 05, 2024, Nov 07, 2024

Clock gating; Bridging: testing bridging faults, feedback bridges, bridging fault issues; transition fault: slow to rise, slow to fall, critical path->longest propagation path, scan-based design->seq circuit to load; transition fault testing: broadside, skewed, enhanced scan; path-delay fault: static sensitization(single path), non-robust, robust, validatable no-robust,

№ 17 Nov 07, 2024, Nov 12

false paths: untestable stuck at fault indicate untestable delay path; find unsensitizable segments; testing for signal integrity: crosstalk, capacitive coupling; functional testing; Finite State Machine; FSM based testing; universal test set: minimal true vector, maximum false vector;

№ 18 Nov 12, Nov 14

Register Transer Level: instruction change, register change; hierarchical test generation: call atpg for individual blocks, they are justified to derive the test set for the entire chip; global data-path constraints extraction; high-level metrics for atpg; slicing; behavoir level atpg;

№ 19 Nov 14

muxes: test point insertion for controlability and observability; scan design: scan cell design, level sensitive scan design; full scan¹³, multiple scan chains; partial scan¹⁴; illinois scan; partial reset, direct load; select FFs for scan and load; flip flop selection for loading: SCOAP, structure based, atpg, random access scan;

№ 20 Nov 19, Nov 21

hybrid: stucture+atpg, testability+atpg, WANT; high level dft

№ 23 № 24 Dec 05

defects: systematic failures/defects; inductive failure analysis; material density; design for yield; diagnosis: static/dictionary-based diagnosis; dynamic diagnosis: cone intersection, diagnosis by sensitization¹⁵; diagnostic test generation; region based diagnosis;

1. Resarch Tip: sit down and think deep, go into deep water to get good results.[]
2. []
3. Zhao, J-K., Elizabeth M. Rudnick, and Janak H. Patel. “Static logic implication with application to redundancy identification.” In Proceedings. 15th IEEE VLSI Test Symposium (Cat. No. 97TB100125), pp. 288-293. IEEE, 1997.[]
4. FFs that are assigned[]
5. Linear Feedback Shift Register[]
6. Multiple-Input Signature Register[]
7. test pattern gen[][]
8. Pseudo Random Patten Generator[]
9. Built-in Self Test[]
10. Output Response Analyzer[]
11. Self-Testing Using MISR and Parallel SRSG[]
12. Built-In Logic Block Observation[]
13. full scan is all FFs are scannable[]
14. due to critical path and area[]
15. check the primary input ordered from cone intersection with flipping values[]