1. Introduction

LFSR（linear feedback shift registers）是一个在数字电路中很常见的结构，在LBIST中通常使用这类结构作为TPG生成用于生成穷举测试、伪随机测试和伪穷举测试的test pattern或test sequence。

2. External-XOR LFSR (many-to-one)

如图是一个external-XOR LFSR，由n个D flip-flops和选定数量的异或门组成，显而易见这种结构的LFSR异或逻辑在外部的反馈逻辑上。

3. Internal-XOR LFSR (one-to-many)

类似地，对于internal-XOR LFSR，异或门被放置在两个相邻的D flip-flops之间。n位的LFSR内部结构可以通过一个n次的特征多项式来描述，每一项前的系数为0或者1取决于此处否存在反馈路径，其中：

设Si表示初始内容S0第i次移位后n级LFSR的内容，Si(x)是Si的多项式表示，那么Si(x)是一个次数为n-1的多项式，其中：

如果LFSR的周期T=2n-1，则这种LFSR被称为maximum-length LFSR。如图两个LFSR的特征多项式分别为1+x2+x4和1+x+x4。

两个LFSR都从序列{0001}开始，第一组test sequence在6个周期后开始重复，而第二组test sequence在15个周期后重复，因此它们的周期分别为6和15。这意味着1+x6可以被1+x2+x4整除，1+x15可以被1+x+x4整除。

在galois field GF(2)上定义，一个多项式对任意整数i<T，可以被1+xT整除而不能被1+xi整除(T=2n-1)，这种多项式被称为本原多项式（因为T=2n-1，所以本原多项式是不可约的）。因此，特征多项式f(x)=1+x+x4是本原多项式，该LFSR也是maximum-length LFSR，令：

其中，r(x)是f(x)的互易多项式，由于本原多项式的互易多项式也是本原多项式，因此，f(x)=1+x+x4的互易多项式f(x)=1+x3+x4也是本原多项式。

4. Hybrid LFSR

在GF(2)上定义多项式a(x)=1+b(x)+c(x)，如果b(x)和c(x)没有公共项且存在整数j(j>1)使得c(x)=xjb(x)，则称a(x)是fully decomposable。对于形如此类的多项式：

可以使用它的connection polynomial 构造(hybrid) top-bpttom LFSR：

此处，^xj表示j级的LFSR输出连接到了反馈路径上而非来自两个寄存器之间；类似地，如果f(x)是fully decomposable，形如此类多项式：

则可以利用它的connection polynomial构造(hybrid) bottom-top LFSR：

如果存在top-bottom LFSR特征多项式为f(x)，则也必然存在与它的互易多项式r(x)对应的bottom-top LFSR。假设某一internal或external LFSR使用了m个XOR门（m为奇数）。如果它的特征多项式f(x)是fully decomposable，则可以只用(m+1)/2个异或门实现hybrid LFSR。如图展示了两种5位hybrid LFSR。(a)是特征多项式f(x)=1+x2+x3+x4+x5对应的connection polynomial s(x)=1+^x2+x4+x5构造的top-bottom LFSR，(b)是特征多项式f(x)=1+x+x2+x3+x5对应的connection polynomial s(x)=1+x2+^x4+x5对应的bottom-top LFSR。