自動測試圖樣生成

自動測試圖樣生成（ATPG, Automatic Test Pattern Generation）係指電子元件測試方法中嘅一個環節，即針對啲元件嘅邏輯電路結構生成輸入圖樣、等最終好檢得到啲元件嘅內部錯誤。

模型同簡化原理

電路模型

一塊芯片嘅邏輯電路可以好複雜，不過佢都可以睇做係由啲基本模型鬭埋而成嘅，譬如話組合邏輯電路同埋序向邏輯電路。前者係一種邏輯電路、之佢穩態輸出衹跟佢嗰陣時得到嘅輸入相關。後者就係輸出唔單止跟嗰陣嘅輸入、仲跟上一陣嘅輸入有關。照慣例，輸入通常表示為x，輸出通常表示為y，內部信號通常表示為z，貯存器通常表示為s。

故障類型

對於系統、特別係電路系統佢啲結構或者操作產生嘅故障，大體上可以分成以下幾種：

硞kak1定故障（Stuck-at fault）：啲信號硞定喺邏輯「0」、邏輯「1」或者高阻態嘅故障。種故障都係ATPG常用嘅模擬故障類型、之攞嚟模擬實際生產中嘅芯片故障噶。具體個信號硞定喺乜嘢二進制可以用「信號/0」或者「信號/1」表示。以輸入x₀為例，佢硞定喺0、1就分別表示成x₀/0、x₀/1。
晶體管故障：類似硞定故障，晶體管都可能硞定喺通態（短路）或者喺斷態（唔傳電）。
橋接故障：兩條信號路之間短路就喊做橋接故障。一般嚟講，橋接故障都用開與/或邏輯嚟表示。對於一條路嘅驅動主導另一條嘅情況，就用到主導與/或邏輯，即係主導信號路維持自己啲信號、而捱主導嘅信號路嘅輸出就係主導路同自己兩家輸出嘅與/或邏輯結果。特殊情況下，假如條路橋接到V_DD抑或係V_SS嗰陣時，佢就相當於硞定故障（見故障㘝疊）。
開路故障
延遲故障：隻信號係啱邏輯嘅，但係就係慢過或者快過正常信號。

簡化

對於一隻有n個輸入、m個輸出嘅組合邏輯電路嚟講，要逐個逐個測啲接腳有冇出錯需要2ⁿ次測試；而對於仲帶埋s個貯存器嘅序向邏輯電路嚟講，s相當於下一次嘅輸入，總共就要到2^n+s次測試。所以精簡啲測試數目落嚟就好有必要。簡化之前，需要定義幾樣嘢：

測試x_ν：一項測試即係一條代表輸入x₀到x_max取乜具體值嘅矢量。例如對於二進制三輸入x₀、x₁、x₂系統，佢其中一項測試x₂就可以寫成x₂=[x₂，x₁，x₀]^T=[0，1，0]^T
故障組F_ν：由一項測試x_ν測得出嘅所有故障佮成嘅一組，一般作為行
測試組T_μ：由測得出某個故障f_μ嘅所有測試佮成嘅一組，一般作為迾
測試集T_c：測得澌啲故障嘅測試組。使最少測試嘅測試集就係最細測試集T_cmin
故障覆蓋：有幾多比例嘅故障可以喺一摣故障組當中揾到（百分百陣時即所有故障都揾得到，即冇一迾測試組係空寥嘅，即冇故障捱略過）
等價故障：有啲故障f_μ、f_κ，佢哋無論喺乜嘢測試條件x_ν下啲輸出y_i都一樣，即 $y_{\mu }(x_{\nu })\oplus y_{\kappa }(x_{\nu })=0$ ，其中y_μ、y_κ分別代表有故障f_μ、f_κ陣時嘅輸出
主導故障：對於故障f_μ、f_κ，所有測得到f_μ嘅測試都測得到f_κ，即使佢哋唔係等價故障都好
主導故障組F_i^D：對於所有測試x_ν，滿足 $F_{i}\supseteq F_{\nu }$ ；即F_i冇辦法俾任意其他故障組F_ν包含到，即F_i係啲唔可以由佢哋代表到嘅各條最大組
主導測試x_ν^D：某個故障f_μ衹能由佢測到
主導測試組T_j^D：對於所有故障f_μ，滿足 $T_{\mu }\supseteq T_{j}$ ；即T_j冇辦法將任意其他測試組T_μ包含到，即T_j係啲唔可以由佢哋代表到嘅各條最細組

㘝疊

為唨達到使最少嘅測試可以覆蓋澌啲故障邇個目標，跟尾就要進行㘝jaap3疊（collapsing），其中分為故障㘝疊同埋測試㘝疊。故障㘝疊即係保留啲等價故障之一、保留啲主導測試同埋主導測試組對應嘅故障，剔除其他故障，嚟減少要測嘅故障數；測試㘝疊即係保留啲主導故障組對應嘅測試，剔除其他測試，嚟儘量使到最少測試數。

Boolean導數法

作為生成測試圖樣嘅基本方法，Boolean導數法係早時應用喺非自動化計算輸入矢量嘅，但係佢並唔適用喺電腦自動化上邊。

Boolean導數嘅定義係噉：

$y_{z}={dy \over dz}=y(z=0)\oplus y(z=1)$

代表z取唔同值陣時y對應嘅輸出是否有差。

以z/1，即z硞定喺1做例，成個方法嘅主要過程係：

計出中間變量z同埋輸入x對應輸出y嘅函數式： $y(z,x_{1},x_{2},\ldots x_{n})$
通過導數嘅公式計出個Boolean導數： $y_{z}=y(z=0)\oplus y(z=1)$
計出 $y_{z}(x_{\nu })\cdot {\overline {z(x_{\nu })}}=1$ （輸出有差同埋z反而取0）對應嘅輸入x₀，x₁……方程
寫出各種可能嘅輸入矢量 $x_{\nu }=[x_{n},\ldots x_{2},x_{1},x_{0}]^{T}$ 嘅具體值，其中x₀，x₁……可以係0，1抑或X（是但）

D演算法

D演算法係第一種實質上可以應用喺電腦自動化嘅測試圖樣生成演算法。佢係通過引入一個D標記_，嚟同時標明某個輸入x嘅正常情況/故障情況，再按照D標記同01嘅運算規則嚟引導至輸出y。對於x嚟講， $D$ 對應嘅係「正常情況下1/故障情況下0」，而 ${\overline {D}}$ 就反之。

D標記滿足以下公式：

$D\cdot 1=D$ ， $D+0=D$
噉就可以在序向邏輯電路入便將輸入嘅 $D$ 遞到輸出作為 $D$ 一係 ${\overline {D}}$ 輸出（睇在中間有幾多非門）。

具體過程有：

故障厏定（Fehlerbelegung）：揀取要檢測嘅信號同埋佢上高厏定嘅故障類型（ $D$ 定係 ${\overline {D}}$ ），噉樣做下游就體現為 $D$ / ${\overline {D}}$ 信號、上游就體現為對應嘅正常信號；

致敏（Sensibilisierung）：每當 $D$ / ${\overline {D}}$ 信號遇上與或邏輯門嗰陣時，通過 $D\cdot 1=D$ ， $D+0=D$ 公式嚟決定另一條路上嘅信號、嚟保證佢傳得到下游；

藴涵（Implikation）：根據邏輯門真值表計算上下游信號真值；

可選分配（Optionale Zuweisung）：計算 $a+b=1$ 、 $a\cdot b=0$ 藴涵情況嗰陣時， $a$ 、 $b$ 取值會有多種組合，要列澌啲組合出嚟，並根據佢哋列出輸入向量表。若果組合嘅信號仲會藴涵到其他信號，就要從中揀取啲真值組合出嚟、啲唔會同啲經已藴涵過、致敏過嘅信號真值有衝突嘅，再根據佢哋列出輸入向量表。