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.

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.

Iterative Logic array

\text{9 value algebra}\Longrightarrow\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}

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.¹

\text{Comb Ckt}\subset \text{Strongly Balanced}\subset \text{Balanced}\subset \text{Internally Balanced} \subset \text{Acyclic}\subset \text{General}

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.

\underbrace{\text{Phase \textcircled{1}}}_{\substack{\text{cost: }}}\xrightarrow[ \text{assuming one FF changes}]{\text{fault sim,  Excite\&Prop}}\underbrace{\text{Phase \textcircled{2}}}_{\substack{\text{cost: }}}\xrightarrow[ \text{assuming one FF changes}]{\text{fault sim,  Excite\&Prop}}\underbrace{\text{Phase \textcircled{3}}}_{\substack{\text{cost: }}}

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.

f_{a\rightarrow i}\xrightarrow[ \text{assuming one FF changes}]{\text{fault sim,  Excite\&Prop}}
 \begin{matrix}
 FF_{\#1}\\
 \vdots\\
\color{red}{FF_{\#i}}\\
\vdots\\
FF_{\#x} \\
\end{matrix}
\xrightarrow[\text{propagate to a PO}]{\text{Apply Test Seq T}}
 \begin{matrix}
 PO_{\#1}\\
 \vdots\\
\color{red}{PO_{\#j}}\\
\vdots\\
PO_{\#n} \\
\end{matrix}
\xrightarrow[\text{Record, \color{red}{Power with T}}]{\text{Distinguishing Ouput}}
\text{Seq T}
\xrightarrow[\text{}]{\text{GA}}
\text{seq T2}

Targeting fault activation

\textcircled{2}\text{state justification}\xrightarrow[ \text{}]{\text{}}\textcircled{1}\text{single time frame}

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

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

S_{k}/S_{k}^{f}\Rightarrow \text{fault free/faulty state at time frame k for fault f}

Compaction apply for ATPG

Analyze the patterns during compaction.

\text{Extract Weights}\equiv \text{RAND Vecs}\Rightarrow \text{Compact} \Rightarrow \text{Analyze Weights}\Rightarrow \cdots

\text{Copy\&Hold}\equiv \text{RAND Vecs}\Rightarrow\text{Compact}\Rightarrow\text{Select\&Duplicate}\Rightarrow \text{Compact}\Rightarrow \cdots

\text{Correlation}\equiv \text{RAND Vecs}\Rightarrow \text{Compact} \Rightarrow \text{Analyze Spatial\&Temporal Correlation}\Rightarrow \cdots

Untestable Fault Identification

D algorithm – Combinational ATPG in DFT (VLSI)

extened backward implication

\underbrace{\text{z}}_{\substack{z\rightarrow \overline{c}}}\rightarrow \underbrace{\text{sim}\left(\text{impl}(z), \text{impl}(a=0)\right)\cap \text{sim}\left(\text{impl}(z), \text{impl}(b=0)\right)}_{\substack{c=a\cdot b}\text{, extended backward implication for AND gate}}

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.

\begin{aligned}
\underbrace{\text{FIRE}}_{\substack{\text{Fault Independent}\\ \text{REdundency Identification}}}&= 
        \underbrace{\{\{\text{S}_{\color{brown}{a=1}}\} \cap \{\text{S}_{\color{red}{a=0}}\}}_{\substack{\color{blue}{\text{Faults that are requires specific signals}}}}  & \\[4ex]
&=\{\underbrace{\overline{\text{EXCT}_{\color{brown}{a=0}}}}_{\substack{\text{unexcitable faults}\\\text{when } a=0}}\cup\underbrace{\overline{\text{PROP}_{\color{brown}{a=0}}}}_{\substack{\text{unpropagatable faults}\\\text{when } a=0}}\}\cap
\{\underbrace{\overline{\text{EXCT}_{\color{red}{a=1}}}}_{\substack{\text{unexcitable faults}\\\text{when } a=1}}\cup\underbrace{\overline{\text{PROP}_{\color{red}{a=1}}}}_{\substack{\text{unpropagatable faults}\\\text{when } a=1}}\}
\end{aligned}

Size of S_{0} and S_{1} are critical, larger better, size depends on implications.

\begin{aligned}
\underbrace{\text{FIRES}}_{\substack{\text{Seq FIRE}}}&= 
  \underbrace{\{\text{S}_{a=1}\} \cap \{\text{S}_{b=0}\}\cap \{\text{S}_{c=1}\}}_{\substack{\color{blue}{\text{Faults that requires specific unreachable states}}}}\\
%& \\[0ex]
&=\underbrace{\{\overline{\text{S}_{a=0}}\}}_{\substack{\color{blue}{\text{Untestable faults if }a=0}}}\cap \underbrace{\{\overline{\text{S}_{b=1}}\}}_{\substack{\color{blue}{\text{Untestable faults if }b=1}}}\cap\underbrace{\{\overline{\text{S}_{c=0}}\}}_{\substack{\color{blue}{\text{Untestable faults if }c=0}}}\\
%& \\[0ex]
&=\{\underbrace{\overline{\text{EXCT}_{a=0}}}_{\substack{\text{unexci faults}\\\text{when } a=0}}\cup\underbrace{\overline{\text{PROP}_{a=0}}}_{\substack{\text{unprop faults}\\\text{when } a=0}}\}\cap
\{\underbrace{\overline{\text{EXCT}_{b=1}}}_{\substack{\text{unexci faults}\\\text{when } b=1}}\cup\underbrace{\overline{\text{PROP}_{b=1}}}_{\substack{\text{unprop faults}\\\text{when } b=1}}\}
\cap
\{\underbrace{\overline{\text{EXCT}_{c=0}}}_{\substack{\text{unexci faults}\\\text{when } c=0}}\cup\underbrace{\overline{\text{PROP}_{c=0}}}_{\substack{\text{unprop faults}\\\text{when } c=0}}\}
\end{aligned}

\begin{aligned}
\underbrace{\text{MUST}}_{\substack{\text{MUST}}}&=\underbrace{\text{FIRES}}_{\substack{\text{fires or fire}}}\Rightarrow \underbrace{\left\{\begin{matrix}
f_{1} \rightarrow\{a=x_{0}, \cdots, z=x_{k}\} \\
 f_{2}  \rightarrow\{a=x_{0}, \cdots, z=x_{k}\}\\
  \vdots \\
 f_{n}  \rightarrow\{a=x_{0}, \cdots, z=x_{k}\} \\
\end{matrix}\right.}_{\substack{\text{Faults that require signals to have certain values}\\\color{red}{\text{From Fire } a\rightarrow S_{a=x}=\{f,\cdots, f\}\text{ to } f\rightarrow\{a,\cdots, z\}}}}
\Rightarrow 
\underbrace{\left\{\begin{matrix}
\underbrace{\text{CFLT}}_{\substack{\text{Conflict}}}\{\text{impl}(a),\cdots,\text{impl}(z)\} \\
\color{blue}{\cup}\\
\overline{\text{EXCT}}\{\text{impl}(a),\cdots,\text{impl}(z)\}\\
\color{blue}{\cup}\\
\overline{\text{PROP}}\{\text{impl}(a),\cdots,\text{impl}(z)\} \\

\end{matrix}\right.}
_{\substack{\text{check one specific fault with 3 conditions}\\\color{red}{\text{For each undetected fault}}}}
\end{aligned}

Single fault theorem

\underbrace{ |S_{0}|}_{\substack{=2^{n}\text{ FF states}\\\text{fault 1st init}}} \geqslant \underbrace{ |S_{1}|}_{\substack{\leqslant 2^{n}\text{ FF states}}}\geqslant\underbrace{ |S_{2}|}_{\substack{\overline{f(i)}\Rightarrow \overline{f(i+j)}\\\overline{f(i+j)}\nRightarrow\overline{f(i)}}}

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\neq 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.

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 xcan 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.

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

 \left\{\begin{matrix}
 z\left(v_{1}\right)= z\left(v_{2}\right)=1\\
 v_{2}\subseteq v_{1}\\
\color{red}{v_{1}}\xrightarrow[detect]{}fault\end{matrix}\right.
\Rightarrow   z_{f}\left(v_{1}\right)=0
\Rightarrow \color{red}{z_{f}\left(v_{2}\right)=0}
\xrightarrow[\text{prefer } v_{2}]{\text{detect faults by } v_{1}}v_{2}

converse is v_{1} does not detect fault, cannot claim about v_{2}.

maximum false vector

 \left\{\begin{matrix}
 z\left(v_{1}\right)= z\left(v_{2}\right)=0\\
 v_{2}\subseteq v_{1}\\
v_{2}\xrightarrow[detect]{}fault\end{matrix}\right.
\Rightarrow z_{f}\left(v_{2}\right)=1
\Rightarrow \color{red}{z_{f}\left(v_{1}\right)=1}\xrightarrow[\text{prefer } v_{1}]{\text{detect faults by } v_{2}}v_{1}

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.

Flip Flop Selection

testability, cycle-cutting/structure, atpg, hybrid

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.

Memory Test

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

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

\text{MARCH}\Rightarrow\left\{\begin{matrix}
\underbrace{\Uparrow_{0}^{n-1}\left ( w0 \right )}_{\substack{\text{init with }0}}\\
\underbrace{\Uparrow_{0}^{n-1}\left ( r0, w1 \right )}_{\substack{\text{R, check, W}}}
\end{matrix}\right.
\text{MATS}\Rightarrow\left\{\begin{matrix}
\underbrace{\Uparrow_{0}^{n-1}\left ( w0 \right )}_{\substack{\text{init with }0}}\\
\underbrace{\Uparrow_{0}^{n-1}\left ( r0, w1 \right )}_{\substack{\text{check fwd coupling, stuck at}}}\\
\underbrace{\Uparrow_{0}^{n-1}\left ( r1 \right )}_{\substack{\text{verify}}}\\
\end{matrix}\right.
\text{MATS+}\Rightarrow\left\{\begin{matrix}
\underbrace{\Uparrow_{0}^{n-1}\left ( w0 \right )}_{\substack{\text{init with }0}}\\
\underbrace{\Uparrow_{0}^{n-1}\left ( r0, w1 \right )}_{\substack{\text{check fwd coupling}}}\\
\underbrace{\Downarrow_{0}^{n-1}\left ( r1, w0 \right )}_{\substack{\text{check bkwd coupling}}}\\
\end{matrix}\right.

\underbrace{\text{inverse coupling}}_{\substack{\text{problem of MATS+}}}=\left\{\begin{matrix}
w\left(i\right)\rightarrow i+2\\
w\left(i+1\right) \rightarrow i+2
\end{matrix}\right.
\Rightarrow
\left\{\begin{matrix}
\underbrace{\Uparrow_{0, \text{ step 2}}^{n-1}\left ( r0, w1 \right )}_{\substack{\text{even address}}}\\
\underbrace{\Uparrow_{1, \text{ step 2}}^{n-2}\left ( r0, w1 \right )}_{\substack{\text{odd address}}}
\end{matrix}\right.

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[↩]