基於逐次逼近法的編碼壓縮方法
2023-05-04 00:35:21 2
專利名稱：基於逐次逼近法的編碼壓縮方法
技術領域：
本發明涉及一種集成電路測試技術，特別是對系統晶片(System-on-a-Chip,SoC)的外建自測試(Built-Out Self-Test, B0ST)方法中測試數據壓縮方法。
背景技術：
隨著集成電路技術的發展，單個晶片上集成的IP核越來越多，而每個IP核廠商為了達到較高的故障覆蓋率和測試硬故障而引入高質量的測試向量，從而給出的測試數據量會很大，因此SoC測試的測試數據量也越來越大。電路集成度的提高導致測試電路所需的測試數據量過大，這是導致測試成本增加的一個重要因素。而SoC的測試時間主要取決於其測試數據量、數據傳輸的速度和最大掃描鏈長度，所以當測試數據量過大時，晶片測試的時間會過長。由於測試數據量的急劇增多，大量的測試數據需要存儲在自動測試設備ATE中， 並傳送到被測電路，這導致傳統ATE設備的存儲容量不夠用，故需要擴大存儲器的容量。但是大容量的ATE設備更加昂貴，從而使得測試成本增大，而且即使將ATE的存儲容量擴容至足夠大，當測試模式數增加和掃描鏈長度增長時，測試時間也會延長。擴容ATE設備非常昂貴，對測試數據量進行壓縮是解決測試數據量過大問題的有效方法。測試壓縮方法首先要有大幅降低測試數據容量的能力，具有高壓縮率和很好的適用性；其次壓縮後的數據要能夠通過解壓電路完整的還原，並且解壓電路的開銷要在可以接受的範圍之內，避免以另一種方式增加測試成本。除此之外，壓縮方法應該具有良好的擴展性，以滿足不同的需求。測試數據壓縮的基本原理是，使用無損數據壓縮的方法對測試數據進行壓縮，將壓縮後的測試數據存到離線的ATE上，這樣降低了被測晶片的負擔，再通過被測晶片上的解壓器進行解壓，得到被測試電路的原始測試數據，因而減少存儲需求和測試時間。良好的壓縮方法，能降低對ATE性能的要求。目前，測試數據壓縮技術主要分為兩大類一類是基於線性解壓結構的方案，它是通過線性方程的擴展來實現解碼過程。然而，無論是LFSR、X0R網絡，還是Illinois掃描結構，都存在一定的線性相關性，可能造成向量的不編碼性，雖然可以在ATPG中加入相應約束來保證向量的可編碼性，但結果往往會增加測試向量的個數，不利於測試數據壓縮和測試時間的減少，同時解壓結構依賴確定測試集的特徵，因此測試移植性不強。另一類是採用編碼的方案，它是把原始測試集進行不同的劃分，用較短的碼字表示這些劃分。常見的編碼方案有FDR編碼，EFDR編碼，交替連續編碼，9C編碼，混合性編碼。編碼壓縮技術的優點是在不降故障覆蓋率的情況下，降低了對ATE性能的要求，能有效地保護智慧財產權，其被測晶片上的解壓模塊可以重用，因此，該種技術得到廣泛應用。在編碼壓縮技術中，根據對測試集劃分策略的不同，測試集可以分為等長劃分或以某一特點變長劃分，劃分對應的碼字也可以是變長或者是定長。因此，可以將編碼方法劃分為四類定長-定長的編碼方法，如字典編碼；定長-變長的編碼方法，如Huffman編碼；變長-定長的編碼方法，如遊程編碼；變長-變長的編碼方法，如FDR碼、EFDR碼等。定長-定長的編碼方法和壓縮協議簡單，但壓縮效果不是很好；定長-變長編碼方法的壓縮效果較前者好些，但一般硬體開銷比較大。Huffman編碼隨著Huffman樹的增大，其解壓結構也越來越複雜，硬體開銷大；變長-變長的編碼方法可以取得很好的壓縮效果，但該類方法控制協議也比較複雜。定長-變長編碼和變長-定長編碼在壓縮效果和硬體開銷方面處於前定長-定長的編碼方法和變長-變長的編碼方法之間。
發明內容
本發明要解決的技術問題是提供一種新的基於逐次逼近法的編碼壓縮方法，是一種新穎的定長-變長編碼壓縮方法，編碼方法和壓縮協議簡單，同時可以取得很好的壓縮效果。本發明採用以下技術方案解決上述技術問題的基於逐次逼近法的編碼壓縮方法的的具體步驟為a、採用自動測試模式生成工具ATPG，生成確定的完全測試集T。b、將所有測試向量級聯，即將一個向量的尾部接另一個向量的首部，記為S。C、取測試集的前η位，按照4位一組轉換成16進位，在第I位數後添加小數點，形成一個16進位浮點數f。d、求 W=f 對應的整數 X、r。I)首先計算/2，取 bot=|_/2」，t0P=bot+l，r=2 ；2)計算,若其值等於f,則記錄x=top, r並轉步驟e ；3) bot = Lbot* r^bot」，
top= [top* φ ρ I r=r+l ；4)取mid= L(bot+top)/2」，計算、·/，若其值等於 f，則記錄
x=mid, r並轉步驟e ;若其值大於f,則top=mid_l ;若其值小於f,則bot=mid+l。重複步驟 4),直到 bot>top,轉步驟 5) ;5)若 top 小於 mid,貝丨J bot=top, top=mid,否貝丨J top=bot,
bot=mid,重複步驟d,直到找到整數x、r,使^ =f，轉步驟e。e、編碼。將X、r進行編碼,將S除去前η位,重複步驟C、d,此過程直到S為空。更具體的，可以將x、r按現有廣泛應用的偶數位標記編碼(CEBM)。本發明的優點在於本發明提供了一種將浮點數轉換為形如仏(其中X，r為整數)的無理數的方法，
能以較快的速度找到對應的被開方數和開方次數的最優解，從而保證使用該方法進行編碼壓縮時可以取得很好的壓縮效果。並且本發明具有如下三個特點(1)開方次數從2開始計算，逐次遞增，可以保證找到的被開方數和開方次數是最優解；(2)定位被開方數區間的下界和上界較為準確，同時採取二分查找的方法，降低了時間複雜度。(3)在二分查找中，對中間數的運算過程中，全部為整數，可以降低運算複雜度，減少運行時間，加快運算進程。
圖I是本發明基於逐次逼近法的編碼壓縮方法的流程圖。
具體實施例方式本發明方法提出一種基於逐次逼近法的定長-變長編碼壓縮方法，將整個測試集的存儲轉換成對一組或若干組被開方數和開方次數的存儲，請參閱圖I所示，該基於逐次逼近法的編碼壓縮方法的的具體步驟為a、採用自動測試模式生成工具ATPG，生成確定的完全測試集T。b、將所有測試向量級聯，即將一個向量的尾部接另一個向量的首部，記為S。C、取測試集的前η位，按照4位一組轉換成16進位，在第I位數後添加小數點，形成一個16進位浮點數f。d、二分無理數區間，逐次逼近f，:j對應的整數x、r。I)首先計算/2，取bot= L/2」，top=bot+l, r=2 ；2)計算，若其值等於f,則記錄x=top, r並轉步驟e ；3) bot = Lbot* r4boi」，top=「top* φορ I，r=r+l ；4)取mid=丨_(bot+top)/2」，計算 ，
若其值等於f，則記錄x=mid, r並轉步驟e ;若其值大於f,則top=mid_l ;若其值小於f,則bot=mid+l。重複步驟 4),直到 bot>top,轉步驟 5);5)若 top 小於 mid,則 bot=top, top=mid,
否則top=bot, bot=mid,重複步驟d,直到找到整數x、r,使&=f，轉步驟e。該步驟中，對
中間數mid的運算過程中，mid全部為整數，可以降低運算複雜度，減少運行時間，加快運算進程。e、編碼。將x、r按現有廣泛應用的偶數位標記編碼(CEBM)，當然也可以按照其他的現有方式編碼，即為對應編碼；將S除去前η位，重複步驟c、d，此過程直到S為空。其中，偶數位標記編碼方式如表I所示。表I偶數位標記編碼編碼表
—長度組數奇數位偶數位代碼字
0OI01
1Ai_ I~ι--η-
2__PO_I 01_ 01_
3_ AQl_I 01_ 11_
4_ 210_I01__10 01_
_5___11_I01__IOJJ__6__000_I1__00 00 01
_7__1__001__ PO 11
............A3..............................
12_ 110__001__10 10 01
13___m__001__10 ο 11CEBM使用了變長到變長的編碼方式，第一列是遊程長度，第二列是組數，第三列和第四列是代碼字的奇數位和偶數位，最後一列是對應代碼字。偶數位標記編碼的特點是偶數位表示代碼字是否結束，奇數位表示遊程的長度信息。代碼字的偶數位如果為0，表示代碼字繼續；偶數位如果為1，則表示本代碼字結束。而長度信息僅含在奇數位。這樣解壓可以根據偶數位判斷代碼字是否結束，根據奇數位判斷代碼字的長度。如長度為7的編碼為000011，其中偶數位為001，奇數位為001。解碼時，只用監控偶數位的數據，如果為0，表示代碼字繼續；如果為1，則表示本代碼字結束。在奇數位(001)前增加一位數據1，即得到1001，其對應的十進位值為9，比其代表的長度7多2，因此自減計數時，讓計算器的結束值為2即可。偶數位標記編碼因易於解碼，硬體開銷小，得到廣泛應用。為了方便描述，舉一例進行說明。不失一般性，設原始測試集T= {00011010，11101000,10011111,10011001,01011010,11010011,11101001, …}，將其級聯後劃分成長度為48的等長序列，則數據流為000110101110100010011111100110010101101011010011 11101001…，其前48位可轉換成16進位浮點數f=l.AE89F995AD3。I)首先計算 f2= 2. D413CCCFE7551FCA6F09E9, bot=L/2」=2，
top=bot+l=3, r=2 ；2)計算.BB67AE8584C，其值不等於 f，
轉步 驟 3 ) ; 3 ) bot = L bot* VW J = L 2 * V2 J = L2 .D413 CCCFE76 J =2,
ορ=[ ορ*^1 = Γ3*ν3 1= [5.32370B908E4l=6, r = r + I = 3 ； 4 )取
mid= L(bot+top)/2 J，計# 4mid 4其值等於f，則記錄x=mid, r並轉步驟e ;若其值大於
f,則 top=mid-l ;若其值小於 f,則 bot=mid+l。重複步驟 4),直到 bot=5, top=4, bot>top,轉步驟 5);5)若 top 小於 mid,則 bot=top，top=mid，否則 top=bot, bot=mid ;則 bot=4，top=5，
重複步驟3)、4)、5)，此時有r=4，x=8，使洳=1.AE89F995AD3，所以對數據流000110101
110100010011111100110010101101011010011 11101001 …前 48 位的存儲就可以轉化為對
被開方數8和開方次數4的存儲。請參見下表2，為採用本發明壓縮方法的實驗結果。使用的是Mintest測試集中的6個時序電路，第一列為電路名稱，第二列為原測試集數據位數，第三列為壓縮後的數據位數，第四列為壓縮效果。表2實驗數據
電路名稱原測試集
__數據位數壓縮率
S5378__23754__9868__58. 46%S9234__39273__16157__58. 86%
S13207 — 165200 —2499884.87%
S15850 — 76986 —2255570.70%
S3841716473881611— 50.46%
S38584__199104__56981__71.38%
平均 I丨I 65.79%以上所述僅為本發明創造的較佳實施例而已，並不用以限制本發明創造，凡在本發明創造的精神和原則之內所作的任何修改、等同替換和改進等，均應包含在本發明創造的保護範圍之內。
權利要求
1.一種基於逐次逼近法的編碼壓縮方法，其特徵在於包括下述步驟 a、採用自動測試模式生成工具ATPG，生成確定的完全測試集； b、將所有測試向量級聯，即將一個向量的尾部接另一個向量的首部，記為S； C、取測試集的前η位，按照4位一組轉換成16進位，在第I位數後添加小數點，形成一個16進位浮點數f ； d、求!^=f對應的整數 X、r, I)首先計算 /2，取 bot=L/2」，top=bot+l, r=2 ；2)計算,若其值等於f,則記錄x=top, r並轉步驟e ;3) bot = Lbot* \fbot」，top= [topr^iop I，r=r+l ；4)取mid= L(bot+top)/2」，計算 Wmid，若其值等於 f，則記錄x=mid, r並轉步驟e ;若其值大於f,貝丨J top=mid_l ;若其值小於f,貝丨J bot=mid+l,重複步驟 4),直到 bot>top,轉步驟 5) ；5)若 top 小於 mid,貝丨J bot=top, top=mid,否貝丨J top=bot,bot=mid,重複步驟d,直到找到整數1、1',使^^=￡1，轉步驟e ； e、編碼，將x、r進行編碼，將S除去前η位，重複步驟C、d，此過程直到S為空。
2.如權利要求I所述的基於逐次逼近法的編碼壓縮方法，其特徵在於x、r按偶數位標記編碼。
全文摘要
本發明提供了一種基於逐次逼近法的編碼壓縮方法，包括下述步驟採用自動測試模式生成工具，生成確定的完全測試集；將所有測試向量級聯，即將一個向量的尾部接另一個向量的首部；取測試集的前n位，按照4位一組轉換成16進位，在第1位數後添加小數點，形成一個16進位浮點數；用逐次逼近法將浮點數轉換成(x、r為整數)的形式，存儲被開方數x和開方次數r的編碼即可，的值可以通過計算得出。本發明的優點在於開方次數從2開始計算，逐次遞增，保證找到的被開方數和開方次數是最優解；定位被開方數區間的下界和上界較為準確，同時採取二分查找的方法，降低了時間複雜度。
文檔編號H03M7/30GK102904579SQ20121041511
公開日2013年1月30日 申請日期2012年10月25日 優先權日2012年10月25日
發明者吳海峰, 蘇本躍, 程一飛, 詹文法, 劉桂江 申請人:吳海峰