集成電路的發展已進入SoC時代，可將各種不同類型的IP芯核集成在一塊芯片上，構成一個完整的系統，既能加快開發進度，又能提高系統整體性能。但集成電路的測試卻面臨越來越多的挑戰，如不同類型的IP核測試方法不同，使得集成電路測試的復雜性大大提高。此外受芯片引腳數目的限制，IP芯核的I/O端口缺乏可觀性和可測性。芯片的頻率普遍高于自動測試設備(ATE)的頻率，芯片的全速測試變得困難。內建自測試(BIST)是解決集成電路測試的有效方法之一。BIST將測試模式生成器、測試過程控制和測試響應評價功能模塊嵌入在被測電路(CUT)上，擺脫了對ATE的依賴。這不僅是解決SoC測試問題的有效方法之一，也是SoC測試發展的方向^[1]。
　　從測試模式生成器的角度，可將BIST分為偽隨機測試^[2]、確定測試^[3]和混合模式測試^[4]。偽隨機測試是硬件開銷最少的BIST測試方法，目前最流行的偽隨機測試序列生成器是線性反饋移位寄存器(LFSR)。LFSR是由一系列D觸發器經反饋線連接而成。LFSR有兩類，兩類LFSR互為對偶，如圖1所示。圖1所示LFSR都可用特征多項式1+h₁x¹+…+h_n-1x^n-1+xⁿ表示。若h_i=1表示第x_i個觸發器的輸出經反饋線連接到異或門。

　　圖1所示LFSR也可用矩陣M和D來表示。M為第一類LFSR的伴隨矩陣，D為第二類LFSR的伴隨矩陣。容易證明，MT=D-1^[5]。
　　
　　通過伴隨矩陣，可以得到經過某個時鐘周期后LFSR的狀態。考慮第一類LFSR，設其值為V₀=(x₁，x₂，…，x_n)，則經過P個時鐘周期后，其值V_P＝V₀×M^P，即由LFSR狀態V₀向前模擬P個時鐘周期可得到V_P。由上式可得V₀＝V_P×M^-P,也可稱為由LFSR狀態VP向后模擬P個時鐘周期得到V₀。
　　在集成電路可測試性設計中，為節省測試時間，一般采用多掃描鏈的設計。若僅采用LFSR做為偽隨機序列" title="偽隨機序列">偽隨機序列生成器，不同掃描鏈間的數據存在很大的相關性，如圖2所示。

相鄰的兩個掃描鏈間的數據只差一個相位，大大降低了偽隨機測試的故障覆蓋率" title="故障覆蓋率">故障覆蓋率。為降低數據間的相關性，通常在LFSR和多掃描鏈間加上由異或門組成的移相器，這種結構稱為STUMPS結構，如圖3所示。

?

　　相移器打破了掃描鏈間數據的高度相關性，使相鄰掃描鏈中的數據相差多個相位，提高了偽隨機測試的故障覆蓋率。因此，相移器的設計對偽隨機測試的成功有著至關重要的作用。
　　文獻[5]、文獻[6]提出了相移器的設計算法，但此算法設計的相移器要求LFSR的某幾位有很高的扇出，在實際的設計中，要增加反相器來增強這些節點的驅動能力，造成芯片的面積和時延增大。本文在分析和研究此算法的基礎上，對其缺點進行了改進。通過增加一個偽隨機數生成函數選擇相移器的通道，使得LFSR節點扇出分布相對均勻。實驗結果表明本算法是一種高效、實用的相移器設計算法。
1 相移器理論推導及算法
　　由圖3可知相移器的通道輸出都是LFSR某幾位的異或，為描述通道的輸出值，引入了相移器選擇矢量。如圖3通道2的選擇矢量為S=(0110)，表示LFSR第2個節點和第3個節點的異或值作為通道2的輸出。設某一時刻LFSR的值為V=(v₁，v₂，v₃，v₄)，則經過P個時鐘脈沖" title="時鐘脈沖">時鐘脈沖后，通道2的輸出值可表示為OUT2=V×M^P×S^T。S^T表示S的轉置。芯片實現時通常要求相移器有較小時延和面積，因此相移器的每個通道最多為 3 個節點的異或，即每一個通道選擇矢量最多有 3 位為“1”。且為了打破不同掃描鏈間數據的相關性，任意兩個通道之間的相位要大于等于某個確定的值。構建n個通道的相移器的問題等價于從LFSR的值域中選擇n個值作為選擇矢量，每一個選擇矢量中的“1”的個數不大于3，且任意兩個通道之間的相位要大于等于確定的值P。
　　設計相移器的關鍵問題是選擇通道，使不同的通道輸出之間的相位大于等于某一個確定的值P，這主要利用LFSR的性質。本文對此性質給出證明。
　　定理1：設有通道選擇矢量S_i和S_j，若將S_i做為第二類(第一類)LFSR的初始值，經過P 個時鐘脈沖后LFSR值變為S_j，則以其對偶的LFSR為偽隨機序列發生器，以S_i和S_j作為通道選擇矢量構造的相移器的兩個通道i和j輸出序列相差P個相位。
　　下面以第一類LFSR作為偽隨機序列發生器來證明此定理。
　　證明： 設第一類LFSR 的伴隨矩陣為M，第二類LFSR的伴隨矩陣為D。

　　比較式(1)和式(4)，可知通道i和j的輸出序列相差P個相位。
　　下面舉例來說明定理1。如圖4所示的第二類LFSR，若其初始值S_i為(0110)，經過15個脈沖后，其狀態變為(1100)，記為S_j。則可驗證圖3所示的通道2和通道3相差15個相位，其中S_i和S_j為通道2和通道3的選擇矢量。

　　文獻[5]、文獻[6]提出了兩種相移器的綜合算法，這里介紹執行速度快的算法(以第一類LFSR作為偽隨機序列生成器構建相移器)，記為算法A：
　　(1)生成“1”的個數不大于3的LFSR值的被選列表，令變量i=1，且將選擇矢量列表清空；
　　(2)從被選列表中取第i個值，利用該值為第二類LFSR的初始值，然后前向仿真 P個時鐘脈沖，后向仿真P個時鐘脈沖；
　　(3)如仿真中出現的值與選擇矢量列表中的值重復，則拋棄這次選擇的值，否則將其加入選擇矢量列表；
　　(4)如果選擇矢量個數達到要求即停止，否則i加1，從第2步開始運行。
　　通過第2步與第3步就能保證選擇出來的通道至少相差P個相位。通過一個4階LFSR的實例來說明其綜合過程。第1步生成的被選列表為：
　　{(1)，(2)，(3)，(4)，(1，2)，(1，3)，(1，4)，(2，3)，(2，4)，(3，4)，(1，2，3)，(1，2，4)，(1，3，4)，(2，3，4)}
　　如列表中(1，2，3)代表的是選擇矢量(1110)。被選列表中第1個值(1)是符合條件的，將其添加到選擇矢量列表中，然后再按照順序判斷(2)、(3)、(4)、(1，2)、(1，3)等組合是否滿足條件。
　　從上述過程可看出此算法存在的缺點：產生的相移器對LFSR的某幾位輸出要求很高的扇出。這是因為每次該算法都是按照被選列表中值的順序來選擇符合條件的矢量，一旦選擇矢量個數達到要求，算法就停止，后面符合條件的選擇矢量沒有得到利用。集成電路設計中，扇出過大，將會造成芯片面積增大，信號的建立時間過長等問題，最終可能導致設計的失敗。本文采用的算法沒有按照被選列表中值的順序來選擇符合條件的選擇矢量，而是通過一個偽隨機數生成函數來選擇被選列表中的值，記為算法B，其算法如下：
　　(1)生成“1”的個數不大于3的LFSR值的被選列表，記列表中值的個數為k。令變量i=1，且將選擇矢量列表清空；
　　(2)從被選列表中取第i個值，利用該值為第二類LFSR的初始值，然后前向仿真P個時鐘脈沖，后向仿真P個時鐘脈沖；
　　(3)如仿真中出現的值與選擇矢量列表中的值重復，則拋棄這次選擇的值，否則將其加入選擇矢量列表；
　　(4)如果選擇矢量個數達到要求即停止，否則i＝rand()%k+1，從第2步開始運行。
　　其中rand()為產生偽隨機的非負整數的函數。其函數實現如下：
　　int rand()
　　　　{next=next*1103515245+12345；
　　　 　return((unsigned int)(next/65536)%32768)；
　　　　}
　　next為無符號長整型靜態變量，初始值為1。rand()函數輸出一系列在0～32 767之間均勻分布的偽隨機數值，產生的序列是可重現的，即程序每次運行都產生同樣的一系列隨機數。“%”為取余運算。在實際的設計中，為減小芯片面積，LFSR度數為48時，就可滿足百萬門規模的設計需要。此時被選列表中元素的個數為，因此rand()函數返回值可取得被選列表中的所有值。從后面實驗結果可看出，本算法構建的相移器不僅克服了LFSR某幾位扇出過大的問題，而且通過此相移器生成的偽隨機序列在電路的故障覆蓋率方面也有所提高。
2 實驗結果及分析
　　表1為兩種算法構建相移器時，對LFSR扇出的比較。選取第一類LFSR為基礎構建相移器，度數為24，特征多項式為x²⁴+x⁴+x³+x+1，相移器的通道數為100，兩通道間的相位差p為1024。

　　第1、3、5列為LFSR觸發器的編號，其余列為兩種算法扇出系數的比較。逗號前為算法A生成的相移器所需LFSR各位觸發器的扇出系數，逗號后為本算法的扇出系數。從表1可看出，本算法LFSR各觸發器扇出要求相比算法A要均勻。如算法A對第1個觸發器的輸出是100，而本算法為13。
　　混合模式的BIST首先對電路進行偽隨機測試，然后對偽隨機測試未測試到的故障采用自動測試模式生成算法(ATPG)，對確定的測試向量進行測試。這里對國際上標準的ISCAS-89^[8]部分電路做了實驗，這些電路在10 000個偽隨機模式之后仍有不可測試的故障。表2是LFSR通過兩種算法設計的相移器生成10 000個偽隨機模式對電路故障覆蓋率的比較。選取LFSR度數為24，電路掃描鏈數量為48，LFSR初始值為(1010…10)。第1列為電路名，第2列為算法A設計的相移器生成的偽隨機序列達到的故障覆蓋率，第3列為本算法的故障覆蓋率。