ch14.7.htm

介绍asci设计的一本书

&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151145">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151147">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151149">
 </A>
2<SPAN CLASS="EquationVariables">
L</SPAN>
 &#8211; <SPAN CLASS="EquationVariables">
R</SPAN>
 &#8211; 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=135472">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=135474">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151178">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151151">
 </A>
<SPAN CLASS="EquationVariables">
p</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151153">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151155">
 </A>
&#8211;&#8211;&#8211;&#8211;&#8211;&#8211;&#8211;&#8211;&#8211;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151137">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=151139">
 </A>
(14.12)</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151180">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151157">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151159">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151161">
 </A>
2<SPAN CLASS="EquationVariables">
L</SPAN>
 &#8211; 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151141">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151143">
 </A>
&nbsp;</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=87030">
 </A>
Thus, for the example in <A HREF="CH14.7.htm#11447" CLASS="XRef">
Figure&nbsp;14.25</A>
, <SPAN CLASS="EquationVariables">
L</SPAN>
 = 7 and <SPAN CLASS="EquationVariables">
R</SPAN>
 = 3, and the probability of aliasing is <SPAN CLASS="EquationVariables">
p</SPAN>
 = (2<SUP CLASS="Superscript">
(7</SUP>
 <SUP CLASS="Superscript">
&#8211;</SUP>
 <SUP CLASS="Superscript">
3)</SUP>
 &#8211; 1) / (2<SUP CLASS="Superscript">
7</SUP>
 &#8211; 1) = 15 / 127 = 0.118, as we have just calculated. This is a very high probability of error and we would not use such a short test sequence and such a short signature register in practice. </P>
<P CLASS="Body">
<A NAME="pgfId=84077">
 </A>
For <SPAN CLASS="EquationVariables">
L</SPAN>
 &gt;&gt; <SPAN CLASS="EquationVariables">
R</SPAN>
 the error probability is  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151212">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151214">
 </A>
<SPAN CLASS="EquationVariables">
p</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151216">
 </A>
<SPAN CLASS="Symbol">
&#170;</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=151218">
 </A>
2<SUP CLASS="SuperscriptVariable">
&#8211;R </SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151220">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=151222">
 </A>
(14.13)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=83558">
 </A>
For example, if <SPAN CLASS="EquationVariables">
R</SPAN>
 = 16, <SPAN CLASS="EquationVariables">
p</SPAN>
 <SPAN CLASS="Symbol">
&#170;</SPAN>
 0.0000152 corresponding to an <SPAN CLASS="Definition">
error coverage</SPAN>
<A NAME="marker=83858">
 </A>
 (1 &#8211; <SPAN CLASS="EquationVariables">
p</SPAN>
) of approximately 99.9984 percent. Unfortunately, these equations for error coverage are rather meaningless since there is no easy way to relate the error coverage to fault coverage. The problem lies in our assumption that all bad-circuit bit-streams are equally likely, and this is not true in practice (for example, bit-stream outputs of all ones or all zeros are more likely to occur as a result of faults). Nevertheless signature analysis with high error-coverage rates is found to produce high fault coverage.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=15407">
 </A>
14.7.5&nbsp;<A NAME="36532">
 </A>
LFSR Theory</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=84326">
 </A>
The operation of LFSRs is related to the mathematics of <A NAME="marker=113917">
 </A>
polynomials and <A NAME="marker=113916">
 </A>
Galois-field theory. The properties and behavior of these polynomials are well known and they are also used extensively in coding theory. Every LFSR has a <SPAN CLASS="Definition">
characteristic polynomial</SPAN>
<A NAME="marker=85524">
 </A>
 that describes its behavior. The characteristic polynomials that cause an LFSR to generate a maximum-length PRBS are called <SPAN CLASS="Definition">
primitive polynomials. </SPAN>
<A NAME="marker=85512">
 </A>
Consider the primitive polynomial  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151289">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151291">
 </A>
<SPAN CLASS="EquationVariables">
P(x)</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151293">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=151295">
 </A>
1 <SPAN CLASS="Symbol">
&#8853; </SPAN>
<SPAN CLASS="EquationVariables">
x</SPAN>
<SUP CLASS="Superscript">
1</SUP>
 <SPAN CLASS="Symbol">
&#8853;</SPAN>
 <SPAN CLASS="EquationVariables">
x</SPAN>
<SUP CLASS="Superscript">
3</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151297">
 </A>
,</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=151299">
 </A>
(14.14)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=137135">
 </A>
where<SPAN CLASS="EquationVariables">
 </SPAN>
a <SPAN CLASS="Symbol">
&#8853;</SPAN>
 b represents the exclusive-OR of <SPAN CLASS="EquationVariables">
a</SPAN>
 and <SPAN CLASS="EquationVariables">
b</SPAN>
. The order of this polynomial is three, and the corresponding LFSR will generate a PRBS of length 2<SUP CLASS="Superscript">
3</SUP>
 &#8211; 1 = 7. For a primitive polynomial of order <SPAN CLASS="EquationVariables">
n</SPAN>
, the length of the PRBS is 2<SPAN CLASS="EquationVariables">
n</SPAN>
 &#8211; 1. <A HREF="CH14.7.htm#14685" CLASS="XRef">
Figure&nbsp;14.27</A>
 shows the nonzero coefficients of some primitive polynomials [<A NAME="Golomb et al., 1982">
 </A>
Golomb et al., 1982].</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137143">
 </A>
<SPAN CLASS="TableHeads">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137145">
 </A>
<SPAN CLASS="TableHeads">
s</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137147">
 </A>
<SPAN CLASS="TableHeads">
Octal</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137149">
 </A>
<SPAN CLASS="TableHeads">
Binary</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137151">
 </A>
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137153">
 </A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137155">
 </A>
0, 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137157">
 </A>
    3</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137159">
 </A>
11</P>
</TD>
<TD ROWSPAN="10" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137161">
 </A>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;For <SPAN CLASS="EquationVariables">
n</SPAN>
 = 3 and s = 0, 1, 3: c<SPAN CLASS="EquationVariables">
0</SPAN>
 = 1, c<SUB CLASS="Subscript">
1</SUB>
 = 1, c<SUB CLASS="Subscript">
2</SUB>
 = 0, c<SUB CLASS="Subscript">
3</SUB>
 = 1<SPAN CLASS="EquationVariables">
</SPAN>
</P>
<DIV>
<IMG SRC="CH14-31.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137166">
 </A>
2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137168">
 </A>
0, 1, 2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137170">
 </A>
    7</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137172">
 </A>
111</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137176">
 </A>
3</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137178">
 </A>
0, 1, 3</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137180">
 </A>
   13</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137182">
 </A>
1011</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137186">
 </A>
4</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137188">
 </A>
0, 1, 4</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137190">
 </A>
    3</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137192">
 </A>
10011</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137196">
 </A>
5</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137198">
 </A>
0, 2, 5</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137200">
 </A>
   45</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137202">
 </A>
100101</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137206">
 </A>
6</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137208">
 </A>
0, 1, 6</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137210">
 </A>
  103</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137212">
 </A>
1000011</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137216">
 </A>
7</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137218">
 </A>
0, 1, 7</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137220">
 </A>
  211</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137222">
 </A>
10001001</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137226">
 </A>
8</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137228">
 </A>
0, 1, 5, 6, 8</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137230">
 </A>
  435</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137232">
 </A>