ch14.5.htm
来自「介绍asci设计的一本书」· HTM 代码 · 共 1,043 行 · 第 1/3 页
HTM
1,043 行
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML EXPERIMENTAL 970324//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="Adobe FrameMaker 5.5/HTML Export Filter">
<TITLE> 14.5 Automatic Test-Pattern Generation</TITLE></HEAD><!--#include file="top.html"--><!--#include file="header.html"-->
<DIV>
<P>[ <A HREF="CH14.htm">Chapter start</A> ] [ <A HREF="CH14.4.htm">Previous page</A> ] [ <A HREF="CH14.6.htm">Next page</A> ]</P><!--#include file="AmazonAsic.html"--><HR></DIV>
<H1 CLASS="Heading1">
<A NAME="pgfId=53405">
</A>
14.5 <A NAME="41037">
</A>
Automatic Test-Pattern Generation</H1>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=79045">
</A>
In this section we shall describe a widely used algorithm, PODEM, for <A NAME="marker=79041">
</A>
<SPAN CLASS="Definition">
automatic test-pattern generation</SPAN>
(<A NAME="marker=79042">
</A>
<SPAN CLASS="Definition">
ATPG</SPAN>
<A NAME="marker=79043">
</A>
) or <A NAME="marker=79044">
</A>
<SPAN CLASS="Definition">
automatic test-vector generation</SPAN>
(<A NAME="marker=79046">
</A>
<SPAN CLASS="Definition">
ATVG</SPAN>
<A NAME="marker=79047">
</A>
). Before we can explain the PODEM algorithm we need to develop a shorthand notation and explain some terms and definitions using a simpler ATPG algorithm.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=79823">
</A>
<IMG SRC="CH14-18.gif" ALIGN="BASELINE">
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=79826">
</A>
FIGURE 14.17 <A NAME="22253">
</A>
The D-calculus. (a) We need a way to represent the behavior of the good circuit and the bad circuit at the same time. (b) The composite logic value D (for detect) represents a logic '1' in the good circuit and a logic '0' in the bad circuit. We can also write this as D = 1/0. (c) The logic behavior of simple logic cells using the D-calculus. Composite logic values can propagate through simple logic gates if the other inputs are set to their enabling values.</P>
</TD>
</TR>
</TABLE>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=74065">
</A>
14.5.1 The D-Calculus</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=81288">
</A>
<A HREF="CH14.5.htm#22253" CLASS="XRef">
Figure 14.17</A>
(a) and (b) shows a shorthand notation, the <SPAN CLASS="Definition">
D-calculus</SPAN>
<A NAME="marker=81289">
</A>
, for tracing faults. The D-calculus was developed by Roth [<A NAME="Roth, 1966">
</A>
1966] together with an ATPG algorithm, the <SPAN CLASS="Definition">
D-algorithm</SPAN>
<A NAME="marker=81290">
</A>
. The symbol <A NAME="marker=81292">
</A>
D (for detect) indicates the value of a node is a logic '0'<SPAN CLASS="BodyComputer">
</SPAN>
in the good circuit and a logic '1' in the bad circuit. We can also write this as D = 0/1. In general we write <SPAN CLASS="EquationVariables">
g/b, </SPAN>
a <SPAN CLASS="Definition">
composite logic value</SPAN>
<A NAME="marker=81293">
</A>
, to indicate a node value in the good circuit is <SPAN CLASS="EquationVariables">
g</SPAN>
and <SPAN CLASS="EquationVariables">
b</SPAN>
in the bad circuit (by convention we always write the good circuit value first and the faulty circuit value second). The complement of D is <SPAN CLASS="Overline">
D</SPAN>
= 1/0 (<SPAN CLASS="Overline">
D</SPAN>
is rarely written as D' since <SPAN CLASS="Overline">
D</SPAN>
is a logic value just like '1' and '0'). Notice that <SPAN CLASS="Overline">
D</SPAN>
does not mean <SPAN CLASS="Emphasis">
not</SPAN>
detected, but simply that we see a '0' in the good circuit and a '1' in the bad circuit. We can apply Boolean algebra to the composite logic values D and <SPAN CLASS="Overline">
D</SPAN>
as shown in <A HREF="CH14.5.htm#22253" CLASS="XRef">
Figure 14.17</A>
(c). The composite values 1/1 and 0/0 are equivalent to '1' and '0' respectively. We use the unknown logic value 'X' to represent a logic value that is one of '0', '1', D, or <SPAN CLASS="Overline">
D</SPAN>
, but we do not know or care which.</P>
<P CLASS="Body">
<A NAME="pgfId=79808">
</A>
If we wish to <SPAN CLASS="Definition">
propagate</SPAN>
<A NAME="marker=79807">
</A>
a signal from one or more inputs of a logic cell to the logic cell output, we set the remaining inputs of that logic cell to what we call the <SPAN CLASS="Definition">
enabling value</SPAN>
<A NAME="marker=79809">
</A>
. The enabling value is '1' for AND and NAND gates and '0' for OR and NOR gates. <A HREF="CH14.5.htm#22253" CLASS="XRef">
Figure 14.17</A>
(c) illustrates the use of enabling values. In contrast, setting at least one input of a logic gate to the <SPAN CLASS="Definition">
controlling value</SPAN>
<A NAME="marker=79813">
</A>
, the opposite of the enabling value for that gate, forces or <SPAN CLASS="Definition">
justifies</SPAN>
<A NAME="marker=79814">
</A>
the output node of that logic gate to a fixed value. The controlling value of '0' for an AND gate justifies the output to '0' and for a NAND gate justifies the output to '1'. The controlling values of '1' justifies the output of an OR gate to '1' and justifies the output of a NOR gate to '0'. To find controlling and enabling values for more complex logic cells, such as AOI and OAI logic cells, we can use their simpler AND, OR, NAND, and NOR gate representations.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=79836">
</A>
</P>
<DIV>
<IMG SRC="CH14-19.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=79839">
</A>
FIGURE 14.18 <A NAME="27794">
</A>
A basic ATPG (automatic test-pattern generation) algorithm for A'B + BC. (a) We activate a fault, U2.ZN stuck at 1, by setting the pin or node to '0', the opposite value of the fault. (b) We work backward from the fault origin to the PIs (primary inputs) by recursively justifying signals at the output of logic cells. (c) We then work forward from the fault origin to a PO (primary output), setting inputs to gates on a sensitized path to their enabling values. We propagate the fault until the D-frontier reaches a PO. (d) We then work backward from the PO to the PIs recursively justifying outputs to generate the sensitized path. This simple algorithm always works, providing signals do not branch out and then rejoin again.</P>
</TD>
</TR>
</TABLE>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=79265">
</A>
14.5.2 A Basic ATPG Algorithm</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=80519">
</A>
A basic algorithm to generate test vectors automatically is shown in <A HREF="CH14.5.htm#27794" CLASS="XRef">
Figure 14.18</A>
. We detect a fault by first <SPAN CLASS="Definition">
activating</SPAN>
<A NAME="marker=79300">
</A>
(or <SPAN CLASS="Definition">
exciting</SPAN>
<A NAME="marker=79301">
</A>
the fault). To do this we must drive the faulty node to the opposite value of the fault. <A HREF="CH14.5.htm#27794" CLASS="XRef">
Figure 14.18</A>
(a) shows a stuck-at-1 fault at the output pin, ZN, of the inverter U2 (we call this fault U2.ZN.SA1). To create a test for U2.ZN.SA1 we have to find the values of the PIs that will justify node U2.ZN to <SPAN CLASS="BodyComputer">
'0'</SPAN>
. We work backward from node U2.ZN justifying each logic gate output until we reach a PI. In this case we only have to justify U2.ZN to <SPAN CLASS="BodyComputer">
'0'</SPAN>
, and this is easily done by setting the PI A = '0'. Next we work forward from the fault origin and <A NAME="marker=79263">
</A>
<SPAN CLASS="Definition">
sensitize</SPAN>
a path to a PO (there is only one PO in this example). This propagates the fault effect to the PO so that it may be <SPAN CLASS="Definition">
observed</SPAN>
<A NAME="marker=95612">
</A>
. To propagate the fault effect to the PO Z, we set U3.A2 = '1' and then U5.A2 = '1'. </P>
<P CLASS="Body">
<A NAME="pgfId=80504">
</A>
We can visualize fault propagation by supposing that we set all nodes in a circuit to unknown, 'X'. Then, as we successively propagate the fault effect toward the POs, we can imagine a wave of D’s and <SPAN CLASS="Overline">
D</SPAN>
’s, called the <SPAN CLASS="Definition">
D-frontier</SPAN>
<A NAME="marker=79596">
</A>
, that propagates from the fault origin toward the POs. As a value of D or <SPAN CLASS="Overline">
D</SPAN>
reaches the inputs of a logic cell whose other inputs are 'X', we add that logic cell to the D-frontier. Then we find values for the other inputs to propagate the D-frontier through the logic cell to continue the process.</P>
<P CLASS="Body">
<A NAME="pgfId=79287">
</A>
This basic algorithm of justifying and then propagating a fault works when we can justify nodes without interference from other nodes. This algorithm breaks down when we have <A NAME="marker=79278">
</A>
<SPAN CLASS="Definition">
reconvergent fanout</SPAN>
. <A HREF="CH14.5.htm#19191" CLASS="XRef">
Figure 14.19</A>
(a) shows another example of justifying and propagating a fault in a circuit with reconvergent fanout. For direct comparison <A HREF="CH14.5.htm#19191" CLASS="XRef">
Figure 14.19</A>
(b) shows an irredundant circuit, similar to part (a), except the fault signal, B stuck at 1, branches and then reconverges at the inputs to gate U5. The reconvergent fanout in this new circuit breaks our basic algorithm. We now have two sensitized paths that propagate the fault effect to U5. These paths combine to produce a constant '1' at Z, the PO. We have a <SPAN CLASS="Definition">
multipath sensitization</SPAN>
<A NAME="marker=80828">
</A>
problem.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=79284">
</A>
</P>
<DIV>
<IMG SRC="CH14-20.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=79286">
</A>
FIGURE 14.19 <A NAME="19191">
</A>
Reconvergent fanout. (a) Signal B branches and then reconverges at logic gate U5, but the fault U4.A1 stuck at 1 can still be excited and a path sensitized using the basic algorithm of <A HREF="CH14.5.htm#27794" CLASS="XRef">
Figure 14.18</A>
. (b) Fault B stuck at 1 branches and then reconverges at gate U5. When we enable the inputs to both gates U3 and U4 we create two sensitized paths that prevent the fault from propagating to the PO (primary output). We can solve this problem by changing A to '0', but this breaks the rules of the algorithm illustrated in <A HREF="CH14.5.htm#27794" CLASS="XRef">
Figure 14.18</A>
. The PODEM algorithm solves this problem.</P>
</TD>
</TR>
</TABLE>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=80516">
</A>
14.5.3 The PODEM Algorithm</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=53425">
</A>
The <SPAN CLASS="Definition">
path-oriented decision making</SPAN>
<A NAME="marker=79641">
</A>
(<SPAN CLASS="Definition">
PODEM</SPAN>
<A NAME="marker=79642">
</A>
<A NAME="marker=79643">
</A>
) algorithm solves the problem of reconvergent fanout and allows multipath sensitization [<A NAME="Goel81">
</A>
Goel, 1981]. The method is similar to the basic algorithm we have already described except PODEM will retry a step, reversing an incorrect decision. There are four basic steps that we label: <SPAN CLASS="Emphasis">
objective</SPAN>
, <SPAN CLASS="Emphasis">
backtrace</SPAN>
, <SPAN CLASS="Emphasis">
implication</SPAN>
, and <SPAN CLASS="Emphasis">
D-frontier</SPAN>
. These steps are as follows:</P>
<OL>
<LI CLASS="NumberFirst">
<A NAME="pgfId=79756">
</A>
Pick an <SPAN CLASS="Emphasis">
objective</SPAN>
to set a node to a value. Start with the fault origin as an objective and all other nodes set to 'X'.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=79757">
</A>
<SPAN CLASS="Emphasis">
Backtrace </SPAN>
to a PI and set it to a value that will help meet the objective. </LI>
<LI CLASS="NumberList">
<A NAME="pgfId=80604">
</A>
Simulate the network to calculate the effect of fixing the value of the PI (this step is called <SPAN CLASS="Emphasis">
implication</SPAN>
). If there is no possibility of sensitizing a path to a PO, then retry by reversing the value of the PI that was set in step 2 and simulate again.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=79763">
</A>
Update the <SPAN CLASS="Emphasis">
D-frontier</SPAN>
and return to step 1. Stop if the D-frontier reaches a PO.</LI>
</OL>
<P CLASS="Body">
<A NAME="pgfId=79849">
</A>
<A HREF="CH14.5.htm#15623" CLASS="XRef">
Figure 14.20</A>
shows an example that uses the following iterations of the four steps in the PODEM algorithm:</P>
<OL>
<LI CLASS="NumberFirst">
<A NAME="pgfId=80390">
</A>
We start with activation of the fault as our objective, U3.A2 = '0'. We backtrace to J. We set J = '1'. Since K is still 'X', implication gives us no further information. We have no D-frontier to update.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=80391">
</A>
The objective is unchanged, but this time we backtrace to K. We set K = '1'. Implication gives us U2.ZN = '1' (since now J = '1' and K = '1') and therefore U7.ZN = '1'. We still have no D-frontier to update.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=80392">
</A>
We set U3.A1 = '1' as our objective in order to propagate the fault through U3. We backtrace to M. We set M = '1'. Implication gives us U2.ZN = '1' and U3.ZN = D. We update the D-frontier to reflect that U4.A2 = D and U6.A1 = D, so the D-frontier is U4 and U6.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=80393">
</A>
We pick U6.A2 = '1' as an objective in order to propagate the fault through U6. We backtrace to N. We set N = '1'. Implication gives us U6.ZN = <SPAN CLASS="Overline">
D</SPAN>
. We update the D-frontier to reflect that U4.A2 = D and U8.A1 = <SPAN CLASS="Overline">
D</SPAN>
, so the D-frontier is U4 and U8.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=80400">
</A>
We pick U8.A1 = '1' as an objective in order to propagate the fault through U8. We backtrace to L. We set L = '0'. Implication gives us U5.ZN = '0' and therefore U8.ZN = '0' (this node is Z, the PO). There is then no possible sensitized path to the PO Z. We must have made an incorrect decision, we retry and set L = '1'. Implication now gives us U8.ZN = D and we have propagated the D-frontier to a PO.</LI>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="5">
<P CLASS="TableFirst">
<A NAME="pgfId=79888">
</A>
</P>
<DIV>
<IMG SRC="CH14-21.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFirst">
<A NAME="pgfId=79947">
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?