1. Introduction

LFSR（linear feedback shift registers）是一個(gè)在數(shù)字電路中很常見的結(jié)構(gòu)，在LBIST中通常使用這類結(jié)構(gòu)作為TPG生成用于生成窮舉測試、偽隨機(jī)測試和偽窮舉測試的test pattern或test sequence。

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

如圖是一個(gè)external-XOR LFSR，由n個(gè)D flip-flops和選定數(shù)量的異或門組成，顯而易見這種結(jié)構(gòu)的LFSR異或邏輯在外部的反饋邏輯上。

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

類似地，對于internal-XOR LFSR，異或門被放置在兩個(gè)相鄰的D flip-flops之間。n位的LFSR內(nèi)部結(jié)構(gòu)可以通過一個(gè)n次的特征多項(xiàng)式來描述，每一項(xiàng)前的系數(shù)為0或者1取決于此處否存在反饋路徑，其中：

設(shè)Si表示初始內(nèi)容S0第i次移位后n級LFSR的內(nèi)容，Si(x)是Si的多項(xiàng)式表示，那么Si(x)是一個(gè)次數(shù)為n-1的多項(xiàng)式，其中：

如果LFSR的周期T=2n-1，則這種LFSR被稱為maximum-length LFSR。如圖兩個(gè)LFSR的特征多項(xiàng)式分別為1+x2+x4和1+x+x4。

兩個(gè)LFSR都從序列{0001}開始，第一組test sequence在6個(gè)周期后開始重復(fù)，而第二組test sequence在15個(gè)周期后重復(fù)，因此它們的周期分別為6和15。這意味著1+x6可以被1+x2+x4整除，1+x15可以被1+x+x4整除。

在galois field GF(2)上定義，一個(gè)多項(xiàng)式對任意整數(shù)i<T，可以被1+xT整除而不能被1+xi整除(T=2n-1)，這種多項(xiàng)式被稱為本原多項(xiàng)式（因?yàn)門=2n-1，所以本原多項(xiàng)式是不可約的）。因此，特征多項(xiàng)式f(x)=1+x+x4是本原多項(xiàng)式，該LFSR也是maximum-length LFSR，令：

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

4. Hybrid LFSR

在GF(2)上定義多項(xiàng)式a(x)=1+b(x)+c(x)，如果b(x)和c(x)沒有公共項(xiàng)且存在整數(shù)j(j>1)使得c(x)=xjb(x)，則稱a(x)是fully decomposable。對于形如此類的多項(xiàng)式：

可以使用它的connection polynomial 構(gòu)造(hybrid) top-bpttom LFSR：

此處，^xj表示j級的LFSR輸出連接到了反饋路徑上而非來自兩個(gè)寄存器之間；類似地，如果f(x)是fully decomposable，形如此類多項(xiàng)式：

則可以利用它的connection polynomial構(gòu)造(hybrid) bottom-top LFSR：

如果存在top-bottom LFSR特征多項(xiàng)式為f(x)，則也必然存在與它的互易多項(xiàng)式r(x)對應(yīng)的bottom-top LFSR。假設(shè)某一internal或external LFSR使用了m個(gè)XOR門（m為奇數(shù)）。如果它的特征多項(xiàng)式f(x)是fully decomposable，則可以只用(m+1)/2個(gè)異或門實(shí)現(xiàn)hybrid LFSR。如圖展示了兩種5位hybrid LFSR。(a)是特征多項(xiàng)式f(x)=1+x2+x3+x4+x5對應(yīng)的connection polynomial?s(x)=1+^x2+x4+x5構(gòu)造的top-bottom LFSR，(b)是特征多項(xiàng)式f(x)=1+x+x2+x3+x5對應(yīng)的connection polynomial?s(x)=1+x2+^x4+x5對應(yīng)的bottom-top LFSR。