ch14.7.htm

介绍asci设计的一本书

100011101</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137236">
 </A>
9</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137238">
 </A>
0, 4, 9</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137240">
 </A>
1021</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137242">
 </A>
1000010001</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137246">
 </A>
10</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=137248">
 </A>
0, 3, 10</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137250">
 </A>
2011</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=137252">
 </A>
10000001001</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="5">
<P CLASS="TableFigTitleSide">
<A NAME="pgfId=137258">
 </A>
FIGURE&nbsp;14.27&nbsp;<A NAME="14685">
 </A>
Primitive polynomial coefficients for LFSRs (linear feedback shift registers) that generate a maximal-length PRBS (pseudorandom binary sequence). A schematic for a type 1 LFSR is shown.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=84921">
 </A>
Any primitive polynomial can be written as  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151484">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151486">
 </A>
<SPAN CLASS="EquationVariables">
P(x)</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151488">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=151490">
 </A>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="Subscript">
0</SUB>
 <SPAN CLASS="Symbol">
&#8853; </SPAN>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="Subscript">
1</SUB>
<SPAN CLASS="EquationVariables">
x</SPAN>
<SUP CLASS="Superscript">
1</SUP>
 <SPAN CLASS="Symbol">
&#8853; ... </SPAN>
<SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
<SPAN CLASS="EquationVariables">
x</SPAN>
<SUP CLASS="SuperscriptVariable">
n</SUP>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151492">
 </A>
,</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=151494">
 </A>
(14.15)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=84959">
 </A>
where <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="Subscript">
0</SUB>
 and <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
n</SUB>
 are always one. Thus for example, from <A HREF="CH14.7.htm#14685" CLASS="XRef">
Figure&nbsp;14.27</A>
 for <SPAN CLASS="EquationVariables">
n</SPAN>
 = 3, we see <SPAN CLASS="EquationVariables">
s</SPAN>
 = 0, 1, 3; and thus the nonzero coefficients are <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="Subscript">
0</SUB>
, <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="Subscript">
1</SUB>
, and <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="Subscript">
3</SUB>
. This corresponds to the primitive polynomial <SPAN CLASS="EquationVariables">
P(x)</SPAN>
 = 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>
. There is no easy way to determine the coefficients of primitive polynomials, especially for large <SPAN CLASS="EquationVariables">
n</SPAN>
. There are many primitive polynomials for each <SPAN CLASS="EquationVariables">
n</SPAN>
, but <A HREF="CH14.7.htm#14685" CLASS="XRef">
Figure&nbsp;14.27</A>
 lists the one with the fewest nonzero coefficients. </P>
<P CLASS="Body">
<A NAME="pgfId=84969">
 </A>
The schematic in <A HREF="CH14.7.htm#14685" CLASS="XRef">
Figure&nbsp;14.27</A>
 shows how the feedback taps on a LFSR correspond to the nonzero coefficients of the primitive polynomial. If the<SPAN CLASS="EquationVariables">
 i</SPAN>
th coefficient <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 is 1, then we include a feedback connection and an XOR gate in that position. If <SPAN CLASS="EquationVariables">
c</SPAN>
<SUB CLASS="SubscriptVariable">
i</SUB>
 is zero, there is no feedback connection and no XOR gate in that position.</P>
<P CLASS="Body">
<A NAME="pgfId=84998">
 </A>
The reciprocal of a primitive polynomial, <SPAN CLASS="EquationVariables">
P*(x)</SPAN>
, is also primitive, where  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151707">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=151709">
 </A>
<SPAN CLASS="EquationVariables">
P*(x)</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=151711">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=151713">
 </A>
<SPAN CLASS="EquationVariables">
x</SPAN>
<SUP CLASS="SuperscriptVariable">
n</SUP>
<SPAN CLASS="EquationVariables">
P*(x</SPAN>
<SUP CLASS="Superscript">
&#8211;1</SUP>
) .</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=151715">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=151717">
 </A>
(14.16)</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=85006">
 </A>
For example, by taking the reciprocal of the primitive polynomial <SPAN CLASS="EquationVariables">
P(x)</SPAN>
 = 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>
 from Eq.&nbsp;<A HREF="CH14.7.htm#41493" CLASS="XRef">
14.17</A>
, we can form  </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=152231">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnRight">
<A NAME="pgfId=152233">
 </A>
<SPAN CLASS="EquationVariables">
P*(x)</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnCenter">
<A NAME="pgfId=152235">
 </A>
=</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnLeft">
<A NAME="pgfId=152237">
 </A>
1 <SPAN CLASS="Symbol">
&#8853; </SPAN>
<SPAN CLASS="EquationVariables">
x</SPAN>
<SUP CLASS="Superscript">
3</SUP>
 <SPAN CLASS="Symbol">
&#8853;</SPAN>
 <SPAN CLASS="EquationVariables">
x</SPAN>
<SUP CLASS="Superscript">
4</SUP>
 ,</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqn">
<A NAME="pgfId=152239">
 </A>
&nbsp;</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableEqnNumber">
<A NAME="pgfId=152241">
 </A>
<A NAME="41493">
 </A>
(14.17)</P>
</TD>
</TR>
</TABLE>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=84996">
 </A>
which is also a primitive polynomial. </P>
<P CLASS="Body">
<A NAME="pgfId=85106">
 </A>
This means that there are two possible LFSR implementations for every <SPAN CLASS="EquationVariables">
P(x)</SPAN>
. Or, looked at another way, for every LFSR implementation, the characteristic polynomial can be written in terms of two primitive polynomials, <SPAN CLASS="EquationVariables">
P(x)</SPAN>
 and <SPAN CLASS="EquationVariables">
P*(x)</SPAN>
, that are reciprocals of each other. </P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=124221">
 </A>
<IMG SRC="CH14-32.gif" ALIGN="BASELINE">
&nbsp;</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=124224">
 </A>
FIGURE&nbsp;14.28&nbsp;<A NAME="26610">
 </A>
For every primitive polynomial there are four linear feedback shift registers (LFSRs). There are two types of LFSR; one type uses external XOR gates (type 1) and the other type uses internal XOR gates (type 2). For each type the feedback taps can be constructed either from the polynomial P(x) or from its reciprocal, P*(x). The LFSRs in this figure correspond to P(x) = 1 &#8853; x &#8853; x<SUP CLASS="Superscript">
3</SUP>
 and P*(x)=  1 &#8853;  x<SUP CLASS="Superscript">
2</SUP>
 &#8853; x<SUP CLASS="Superscript">
3</SUP>
. Each LFSR produces a different pseudorandom sequence, as shown. The binary values of the LFSR seen as a register, with the bit labeled as zero being the MSB, are shown in hexadecimal. The sequences shown are for each register initialized to '111', hex 7. (a)&nbsp;Type 1, P*(x). (b)&nbsp;Type 1, P(x). (c)&nbsp;Type 2, P(x). (d)&nbsp;Type 1, P*(x).</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=85388">
 </A>
We may also implement an LFSR by using XOR gates in series with each flip-flop output rather than external to the shift register. The <SPAN CLASS="Definition">
external-XOR LFSR</SPAN>
<A NAME="marker=87174">
 </A>
 is called a <SPAN CLASS="Definition">
type 1 LFSR</SPAN>
<A NAME="marker=85046">
 </A>
 and the <SPAN CLASS="Definition">
internal-XOR LFSR</SPAN>
<A NAME="marker=87175">
 </A>
 is called a <SPAN CLASS="Definition">
type 2 LFSR</SPAN>
<A NAME="marker=85052">
 </A>
 (this is a nomenclature that most follow). <A HREF="CH14.7.htm#26610" CLASS="XRef">
Figure&nbsp;14.28</A>
 shows the four different LFSRs that may be constructed for each primitive polynomial, <SPAN CLASS="EquationVariables">
P(x)</SPAN>
.</P>
<P CLASS="Body">
<A NAME="pgfId=84310">
 </A>
There are differences between the four different LFSRs for each polynomial. Each gives a different output sequence. The outputs for the type 1 LFSRs, taken from the Q outputs of each flip-flop, are identical, but delayed by one clock cycle from the previous output. This is a problem when we use the parallel output from an LFSR to test logic because of the strong correlation between the test signals. The type 2 LFSRs do not have this problem. The type 2 LFSRs also are capable of higher-frequency operation since there are fewer series XOR gates in the signal path than in the corresponding type 1 LFSR. For these reasons, the type 2 LFSRs are usually used in BIST structures. The type 1 LFSR does have the advantage that it can be more easily constructed using register structures that already exist on an ASIC.</P>
<P CLASS="Body">
<A NAME="pgfId=84886">
 </A>
<A HREF="CH14.7.htm#12175" CLASS="XRef">
Table&nbsp;14.11</A>
 shows primitive polynomial coefficients for higher values of <SPAN CLASS="EquationVariables">
n</SPAN>
 than <A HREF="CH14.7.htm#14685" CLASS="XRef">
Figure&nbsp;14.27</A>
. Test length grows quickly with the size of the LFSR. For example, a 32-bit generator will produce a sequence with 2<SUP CLASS="Superscript">
32</SUP>
 = 4,294,967,296 <SPAN CLASS="Symbol">
&#170;</SPAN>
 4.3 <SPAN CLASS="Symbol">
&#165;</SPAN>
 10<SUP CLASS="Superscript">
9</SUP>
 bits. With a 100 MHz clock (with 10 ns cycle time), the test time of 43 seconds would be impractical.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="8">
<P CLASS="TableTitle">
<A NAME="pgfId=84695">
 </A>
TABLE&nbsp;14.11&nbsp;<A NAME="12175">
 </A>
Nonzero coefficients of primitive polynomials for LFSRs (linear feedback shift registers) that generate a maximal-length PRBS (pseudorandom binary sequence). </P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84711">
 </A>
<SPAN CLASS="TableHeads">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84713">
 </A>
<SPAN CLASS="TableHeads">
s</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84715">
 </A>
<SPAN CLASS="TableHeads">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84717">
 </A>
<SPAN CLASS="TableHeads">
s</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84719">
 </A>
<SPAN CLASS="TableHeads">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84721">
 </A>
<SPAN CLASS="TableHeads">
s</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84723">
 </A>
<SPAN CLASS="TableHeads">
n</SPAN>
</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84725">
 </A>
<SPAN CLASS="TableHeads">
s</SPAN>
</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84727">
 </A>
1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84729">
 </A>
0, 1</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84731">
 </A>
11</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84733">
 </A>
0, 2, 11</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84735">
 </A>
21</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84737">
 </A>
0, 2, 21</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84739">
 </A>
31</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84741">
 </A>
0, 3, 31</P>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84743">
 </A>
2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84745">
 </A>
0, 1, 2</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">
<A NAME="pgfId=84747">
 </A>
12</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableLeft">
<A NAME="pgfId=84749">
 </A>
0, 3, 4, 7, 12</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="Table">