數(shù)字電路測(cè)試向量自動(dòng)生成的技術(shù)

1、數(shù)字電路測(cè)試向量自動(dòng)生成技術(shù)摘要數(shù)字電路測(cè)試向量自動(dòng)生成一直是電子測(cè)試領(lǐng)域關(guān)注的焦點(diǎn)，是開(kāi)發(fā)電路板 模塊測(cè)試程序的難點(diǎn)，也是困擾我軍如何高效合理利用現(xiàn)有自動(dòng)測(cè)試設(shè)備和開(kāi)發(fā)測(cè) 試程序組合軟件構(gòu)成具有實(shí)用性的故障診斷系統(tǒng)的關(guān)鍵點(diǎn)。測(cè)試向量生成最關(guān)鍵的技術(shù)是測(cè)試向量實(shí)用化算法的實(shí)現(xiàn)，通過(guò)對(duì)G-F二值算法的分析和研究，設(shè)計(jì)了一種新的方法和策略，采用正向敏化模式按有限回溯策略 推導(dǎo)，凡在回溯次數(shù)內(nèi)未能判明目標(biāo)故障不可測(cè)的測(cè)試生成過(guò)程所產(chǎn)生的測(cè)試碼都 進(jìn)行故障模擬。這種有限回溯策略加速測(cè)試生成，對(duì)提高系統(tǒng)效率起到了決定性的 作用。在 G-F算法確立正反向驅(qū)動(dòng)經(jīng)過(guò)各類功能塊和反饋線的時(shí)幀變化的基礎(chǔ)上， 把推

2、導(dǎo)組合電路目標(biāo)故障測(cè)試碼的方法按迭代組合模型推廣到同步時(shí)序電路，且用 反向追蹤中的時(shí)幀迭代實(shí)現(xiàn)迭代組合模型中的空間迭代。通過(guò)對(duì)同步時(shí)序電路的分析和研究，結(jié)合數(shù)字電路的特點(diǎn)，建立其電路模型和 故障模型，生成了電路的器件庫(kù)，并可對(duì)電路進(jìn)行故障模擬，生成故障字典，生成 的故障字典供測(cè)試系統(tǒng)使用。數(shù)字電路測(cè)試向量自動(dòng)生成的實(shí)現(xiàn)主要以提高數(shù)字電 路測(cè)試向量自動(dòng)生成算法的通用性和效率為主，力爭(zhēng)解決電路板的故障測(cè)試向量生 成問(wèn)題。關(guān)鍵詞：測(cè)試向量集自動(dòng)生成電路板，自動(dòng)測(cè)試設(shè)備測(cè)試程序集 故障模型故障字典1 緒論11研究目的1緒論本課題主要針對(duì)數(shù)字電路測(cè)試程序組合(XPS， Test Program Set)

3、 開(kāi)發(fā)過(guò)程中，人工分析電路結(jié)構(gòu)，手工推導(dǎo)測(cè)試向量造成的開(kāi)發(fā)難度大、周期長(zhǎng)、質(zhì)量無(wú)法評(píng)估的問(wèn) 題，開(kāi)發(fā)出一套測(cè)試向量自動(dòng)生成軟件該軟件能自動(dòng)生成測(cè)試向量、故障字典等 數(shù)據(jù)，提供給測(cè)試設(shè)備使用。12研究背景 在一些測(cè)試過(guò)程中，出現(xiàn)了數(shù)字電路測(cè)試程序開(kāi)發(fā)難度大、周期長(zhǎng)、質(zhì)量無(wú)法 評(píng)估的問(wèn)題，問(wèn)題的根本在于需要人工進(jìn)行分析電路，手工生成測(cè)試激勵(lì)、響應(yīng)數(shù) 據(jù)，診斷信息完全根據(jù)測(cè)試開(kāi)發(fā)人員的經(jīng)驗(yàn)編制。在此背景下迫切需要研制一套數(shù) 字電路自動(dòng)測(cè)試向量生成軟件來(lái)代替人工分析方法，自動(dòng)生成測(cè)試所需的數(shù)據(jù)，降 低測(cè)試程序開(kāi)發(fā)難度，提高開(kāi)發(fā)速度與質(zhì)量，最大限度發(fā)揮測(cè)試系統(tǒng)的效能，最終 提高軍隊(duì)的戰(zhàn)斗保障力。13國(guó)內(nèi)

4、外研究現(xiàn)狀 現(xiàn)代戰(zhàn)爭(zhēng)發(fā)生突然，戰(zhàn)場(chǎng)情況瞬息萬(wàn)變，戰(zhàn)爭(zhēng)環(huán)境條件更加復(fù)雜嚴(yán)酷，機(jī)動(dòng)性 及快速反應(yīng)能力要求高，這一切都更加迫切要求在裝備發(fā)生故障時(shí)能迅速檢測(cè)、隔 離故障，及時(shí)修復(fù)，使戰(zhàn)斗力保持和再生。同時(shí)，現(xiàn)代戰(zhàn)爭(zhēng)投入大量復(fù)雜的電子裝 備或含有電子系統(tǒng)的裝備，而自動(dòng)測(cè)試設(shè)備(ATE， Automatic Test Equipment) 技術(shù)的高度發(fā)展，為滿足迅速檢測(cè)、隔離、修復(fù)，使戰(zhàn)斗力很快再生提供了技術(shù)保證，現(xiàn)已成為世界各軍事強(qiáng)國(guó)電子設(shè)備維修測(cè)試的主要方法和手段【¨。 美國(guó)陸、海、空三軍為適應(yīng)現(xiàn)代戰(zhàn)爭(zhēng)快速保障的需要，分別組織實(shí)旅了“通用 自動(dòng)測(cè)試設(shè)備”計(jì)劃，所有主要武器裝備都裝備了自動(dòng)測(cè)

5、試設(shè)備。我軍也已開(kāi)始研 制和裝備自動(dòng)測(cè)試設(shè)備 ATE用于武器裝備的測(cè)試。其“硬件”已達(dá)到和接近世界先 進(jìn)水平，但測(cè)試軟件的使用仍受到一定限制，首先是對(duì)操作人員要求高，其次要求 對(duì)裝備設(shè)計(jì)的電路非常熟悉，同時(shí)，人工生成測(cè)試向量難度太大，造成開(kāi)發(fā)一塊電 路板的 TPS相當(dāng)復(fù)雜，部隊(duì)進(jìn)行二次開(kāi)發(fā)難度相當(dāng)大，形成了所需的測(cè)試“軟件” 的“瓶頸”問(wèn)題。如開(kāi)發(fā)一塊中等規(guī)模(幾百個(gè)功能器件 )電路板 TPS為例，在技術(shù)資料齊全的情況下，專業(yè)技術(shù)人員約需2-3 個(gè)月，成本約為 2 3萬(wàn)元人民幣。例如 C一300地空導(dǎo)彈武器系統(tǒng)共有 2700多種電路板，需投入的硬件費(fèi)用約為1000萬(wàn)元左右，而測(cè)試軟件開(kāi)發(fā)周期，

6、在1人l 臺(tái) ATE設(shè)備上要工作 200多年，開(kāi)發(fā)費(fèi)用約為 5400 萬(wàn)元，開(kāi)支費(fèi)用驚人。無(wú)論是開(kāi)發(fā)時(shí)間方面，還是經(jīng)費(fèi)方面都嚴(yán)重制約 了自動(dòng)測(cè)試設(shè)備的廣泛使用。但系統(tǒng)二次開(kāi)發(fā)的能力不夠，即TPS開(kāi)發(fā)難。對(duì)使用者要求較高，開(kāi)發(fā)效率急需大大提高。 TPS開(kāi)發(fā)難的問(wèn)題，實(shí)質(zhì)上是數(shù)字電路測(cè)試向量生成的問(wèn)題如果不采用任何 對(duì)輸入激勵(lì)的選擇技術(shù)，則對(duì)有 n個(gè)輸入的數(shù)字系統(tǒng)，需加 2n組不同的輸入激勵(lì)方 可實(shí)現(xiàn)對(duì)系統(tǒng)的完全測(cè)試，但當(dāng) n較大時(shí)，這是不現(xiàn)實(shí)的。如一個(gè) 32位加法器，有 65個(gè)輸入，如果要加 2舒組輸入激勵(lì)，即使是 lns 加一組，也要 1000年，這是不可 能實(shí)現(xiàn)的由此提出了一個(gè)如何加最少的輸

7、入激勵(lì)也能達(dá)到同樣的檢測(cè)效果的問(wèn)題， 這也正是多年來(lái)人們利用各種算法來(lái)生成所需輸入激勵(lì)的問(wèn)題。也是現(xiàn)有ATE，開(kāi)發(fā)數(shù)字電路板 TPS的難點(diǎn) 12 】。自1966 年羅思 (Roth) 發(fā)表的著名的 D算法以來(lái)，數(shù)字電路測(cè)試?yán)碚摰玫搅搜?速發(fā)展研究者們提出了各種基于用門級(jí)描述數(shù)字電路ATPG的方法。特別是為了較好地解決時(shí)序電路的測(cè)試問(wèn)題，相繼提出了邏輯函數(shù)的多值模擬法，其中比較成 功的有五值和九值布爾模擬。多值布爾模擬中所引入的新的布爾變量，主要是為了 時(shí)序電路中狀態(tài)變量的初值設(shè)置，以及在測(cè)試過(guò)程中某些元件的未知狀態(tài)或隨意狀 態(tài)的表達(dá)問(wèn)題，目前常見(jiàn)的有基于九值邏輯運(yùn)算的九值算法0-41 。D算法

8、從理論上解決了組合邏輯電路的測(cè)試生成問(wèn)題，即任何一非冗余的組合 邏輯電路中任何單故障都可用 D算法來(lái)找到測(cè)試它的測(cè)試向量，但在實(shí)際應(yīng)用中因 其計(jì)算量十分浩大，對(duì)大型電路很難實(shí)施。時(shí)序邏輯電路的測(cè)試主要有三個(gè)方面的 難題：一是時(shí)序邏輯電路中存在反饋，給故障檢測(cè)和診斷帶來(lái)困難；二是時(shí)序邏輯 電路中有存儲(chǔ)元件，因此電路中存在著狀態(tài)變量初態(tài)的隨機(jī)性問(wèn)題；三是時(shí)序邏輯 電路中有時(shí)序元件，尤其是異步時(shí)序元件，對(duì)競(jìng)爭(zhēng)現(xiàn)象是異常敏感，因此產(chǎn)生的測(cè) 試序列，不僅在邏輯功能上要滿足測(cè)試要求，而且要考慮到期競(jìng)爭(zhēng)對(duì)測(cè)試電路的影 響。無(wú)論組合邏輯電路，還是時(shí)序邏輯電路，雖然至今已有部分解決方案來(lái)測(cè)試它 們，但工作量和測(cè)

9、試費(fèi)用都是很大的，尤其是現(xiàn)代裝備的規(guī)模越來(lái)越大，測(cè)試的矛 盾也日益尖銳。據(jù)美國(guó)有關(guān)公司的統(tǒng)計(jì)，當(dāng)今一些PCB板的測(cè)試費(fèi)用已占整個(gè)生產(chǎn)過(guò)程費(fèi)用的 500,6 以上。我國(guó)學(xué)者提出的 G-F二值算法以簡(jiǎn)便的 G-F值分開(kāi)的二值運(yùn)算實(shí)現(xiàn)了九值算法 功能，使進(jìn)行相容性運(yùn)算時(shí)需要執(zhí)行的運(yùn)算規(guī)則由九值算法的45條減少為 12條，大大提高了算法速度。 G-F二值算法對(duì)于有 n個(gè)輸入的功能塊，可以把功能塊的 pdc 表壓縮為 n行，而且它只需存儲(chǔ)相當(dāng)于初始立方 (pc,primitive cube) 表的功能塊的 c立 方表達(dá)式，即根據(jù)需要?jiǎng)討B(tài)生成，因此，處理復(fù)雜功能塊的大型電路比較方便。所 以與D算法、 PO

10、DEM和FAN算法、九值算法相比， G-F二值算法便于處理較復(fù)雜 的功能塊構(gòu)成的電路，便于處理多故障和時(shí)序電路 5-71 。國(guó)際上如 Teradyne 、Synopsys 等大公司研制出了一些用門級(jí)描述的數(shù)字電路測(cè) 試向量自動(dòng)生成 （ATPG， AutomaticTestPatternGeneration）商用軟件，都是針對(duì)規(guī)模、復(fù)雜度不十分大的數(shù)字電路，也主要用于集成電路的設(shè)計(jì)中。據(jù)調(diào)研，國(guó)內(nèi)外都沒(méi) 有成熟的 ATPG商用軟件。80年代后，人們對(duì)測(cè)試研究的戰(zhàn)略思想發(fā)生了重要變化，最有代表性的觀點(diǎn)是 可測(cè)試性設(shè)計(jì)，認(rèn)為邊界掃描技術(shù)使門級(jí)的ATPG問(wèn)題變得相對(duì)容易。但邊界掃描等技術(shù)針對(duì)時(shí)序電路的

11、測(cè)試有效，還需要額外增加20甚至 300,6 的硬件開(kāi)銷，增大了芯片的面積和電路的復(fù)雜性，而且測(cè)試時(shí)間變長(zhǎng)，在一定程度上限制了這些技術(shù) 的適用范圍。但現(xiàn)有的裝備中，由于種種原因，很多引進(jìn)設(shè)備，沒(méi)有提供維修的詳 細(xì)維修資料，有的甚至連電原理圖都沒(méi)有，大部分的電路并不符合可測(cè)試性標(biāo)準(zhǔn) （1149 ， 1） ，國(guó)產(chǎn)電子裝備出于成本和性能 （主要是速度 ）的考慮，在批量不大的情 況下，多數(shù)還是選擇非掃描設(shè)計(jì)。所以，本項(xiàng)目不以可測(cè)試性設(shè)計(jì)為基礎(chǔ)，而是從 2 提高數(shù)字電路 ATPG算法的通用性和效率為主，力爭(zhēng)解決電路板的故障測(cè)試向量生 成闖題。測(cè)試向量自動(dòng)生成一直是電子測(cè)試領(lǐng)域關(guān)注的焦點(diǎn)，是開(kāi)發(fā)電子電路板

12、模塊 測(cè)試程序的難點(diǎn)，也是困擾我軍如何高效合理利用現(xiàn)有自動(dòng)測(cè)試設(shè)備ATE和開(kāi)發(fā)測(cè)試程序組合 TPS軟件構(gòu)成具有實(shí)用性的故障診斷系統(tǒng)的關(guān)鍵點(diǎn)。測(cè)試診斷能否達(dá)到 所期望的故障覆蓋率和故障分辨率，主要取決于測(cè)試向量生成系統(tǒng)所提供的測(cè)試向 量和故障字典的質(zhì)量。人工開(kāi)發(fā)澳 I 試向量的方法已無(wú)法滿足需要，如果不及早研究 測(cè)試向量的自動(dòng)生成，并在短時(shí)間內(nèi)將其實(shí)用到已裝備的ATE，勢(shì)必會(huì)嚴(yán)重影響電子裝備的作戰(zhàn)能力及裝備的技術(shù)保障。我軍電子裝備現(xiàn)有的大部份電路板由于沒(méi)有有效的測(cè)試手段作保證， 一方面大部分只能靠返 回生產(chǎn)廠家 （ 有的到國(guó)外生產(chǎn)廠 ）修理；另一方面是同一種電路板為 防止短缺，占用大量資金，加大

13、器材備件儲(chǔ)備量。這種保障方式，戰(zhàn)時(shí)既滿足不了 快速保障需要，技術(shù)保障工作還時(shí)時(shí)處于被動(dòng)的局面，平時(shí)也容易使器材備件大量 積壓，造成了經(jīng)費(fèi)的緊張和資源的浪費(fèi)。該課題從提高數(shù)字電路 ATPG算法的通用性和效率為主，力爭(zhēng)解決電路板的故 障測(cè)試向量生成問(wèn)題。14研究工作 本課題主要功能塊數(shù)字電路測(cè)試生成算法，建立數(shù)字電路組合電路和同步時(shí)序 電路的電路模型和故障模型，并對(duì)電路進(jìn)行故障模擬，生成故障字典主要研究?jī)?nèi) 容如下：1）完成數(shù)字電路測(cè)試向量生成軟件的總體設(shè)計(jì)；2）完成測(cè)試向量生成算法理論實(shí)用化研究；3）開(kāi)發(fā)出數(shù)字電路測(cè)試向量自動(dòng)生成軟件，具備自動(dòng)生成測(cè)試碼，故障模擬， 故障覆蓋率統(tǒng)計(jì)以及故障字典建立

14、等功能；4）利用現(xiàn)有的 ATE利用生成的數(shù)據(jù)文件對(duì)被測(cè)電路進(jìn)行故障檢測(cè)和診斷。42數(shù)字電路自動(dòng)測(cè)試生成系統(tǒng)模型 本測(cè)試生成系統(tǒng)的系統(tǒng)模型，是從被測(cè)對(duì)象的基本特征中抽象出來(lái)的，主要包 括數(shù)字電路模型和故障模型。21數(shù)字電路模型211組合電路模型和時(shí)序電路模型1) 兩種模型的主要區(qū)別 如果被測(cè)電路 (CUT。 Circuit Under Test) 中沒(méi)有任何存儲(chǔ)狀態(tài)元件，也沒(méi)有反饋回 路，則可采用組合電路模型；反之，如果CUT中有任何一種存儲(chǔ)狀態(tài)元件，或者有反饋回路，則需要采用時(shí)序電路模型。 由于組合電路的輸出狀態(tài)唯一地由當(dāng)前的輸入狀態(tài)決定，因此，對(duì)組合電路的 測(cè)試生成來(lái)說(shuō)，在進(jìn)行正反向驅(qū)動(dòng)時(shí)，

15、歸根結(jié)底只考慮不同變量之間的邏輯關(guān)系， 不需考慮它們之問(wèn)的時(shí)間關(guān)系。對(duì)時(shí)序電路則不然，由于時(shí)序電路當(dāng)前的輸出狀態(tài) 不僅與當(dāng)前時(shí)幀的輸入有關(guān)，還與前一時(shí)幀電路的狀態(tài)有關(guān)；前一時(shí)幀的狀態(tài)又與 前一幀的電路輸入及再前一幀的電路狀態(tài)有關(guān)，因此，在生成時(shí)序電路的測(cè)試時(shí)， 既要考慮不同引線在同一時(shí)幀的邏輯關(guān)系，又要考慮不同引線變量在不同時(shí)幀的狀 態(tài)轉(zhuǎn)換關(guān)系，也要考摩同一引線變量在不同時(shí)幀的狀態(tài)變化關(guān)系?？傊瑢?duì)時(shí)序電 路生成測(cè)試時(shí)，既要考慮邏輯關(guān)系，又要考慮時(shí)間 (幀) 關(guān)系。因此比生成組合電 路的測(cè)試要復(fù)雜得多。另一方面，由于生成組合電路測(cè)試時(shí)所遇到的各種問(wèn)題，在 求時(shí)序電路測(cè)試時(shí)也會(huì)出現(xiàn)，所以用于測(cè)試

16、生成的時(shí)序電路模型實(shí)際上將包含組合 電路模型。2) 組合電路模型中的特殊情況 由于電路類型和所用元件的不同，組合電路中也有許多需要專門處理的特殊情 況：(1) 三態(tài)門：它使一條引線具有 0，l 和高阻三個(gè)邏輯狀態(tài)，如不進(jìn)行特殊處理，只用傳統(tǒng)的 (o'l ，× )三值邏輯是描述不了的。(2) 雙向端：一條引線既能作輸出，又能作輸入，當(dāng)然，一次只起一種作用。但 當(dāng)它分別被用做輸入和輸出時(shí)，對(duì)電路的邏輯關(guān)系是有不同影響的。有的雙向端是 對(duì)功能塊而言的，有的是對(duì)整個(gè) CUT而言。(3) 線邏輯：在電路的同一個(gè)或者不同的基本邏輯單元 ( 門功能塊，宏單元，組件 ) 中，有兩條以上的輸出

17、線直接相連，便形成線邏輯。對(duì)正邏輯為線與，對(duì)負(fù)邏輯為 線或。這是一種不需要基本邏輯元件，僅通過(guò)連線直接實(shí)現(xiàn)的邏輯變換。(4) PLA ：可編程邏輯陣列 PLA雖然也是一種組合邏輯，但又不能象一般組合邏輯 那樣可化成門級(jí)電路來(lái)處理，因此它是一個(gè)不可分割的整體。此外，PLA中具有的觸點(diǎn)消失和觸點(diǎn)增生故障，也是一般組合電路中所沒(méi)有的。(5) CMOS組合電路：由于 CMO電S 路中存在使組合門變成時(shí)序元件的固定開(kāi)路 故障 SOP，因此，對(duì) CMOS電路來(lái)說(shuō)，完全的組合電路模型已經(jīng)不存在了。3) 時(shí)序電路模型的一般處理方法 欲生成大型時(shí)序電路的測(cè)試序列，比較可行的方法是采用迭代組合模型。這是 因?yàn)?，?/p>

18、一，迭代組合模型既能如實(shí)地描述時(shí)序電路中信號(hào)線之間的邏輯關(guān)系，又 能描述它們之間的時(shí)間關(guān)系；第二，該模型便于把組合電路中成熟的各種算法推廣 到時(shí)序電路中去。 G F二值算法通過(guò)用時(shí)幀布爾表達(dá)式描述時(shí)序電路中的功能塊， 并對(duì)反饋線進(jìn)行適當(dāng)處理之后， 可以把迭代組合模型中的空間迭代自動(dòng)變化成測(cè)試生成過(guò)程 中的時(shí)序迭代。這種變換不僅給測(cè)試生成帶來(lái)方便，而且更符合迭代的實(shí) 際情況網(wǎng)。22故障模型 221門級(jí)單固定故障模型 假設(shè) cur,- 次只有一個(gè)門的一個(gè)輸入或輸出發(fā)生 s一口一 o , 一a一 1故障，不考 慮門內(nèi)部晶體管的故障這是實(shí)際應(yīng)用中所能考慮的最細(xì)的故障模型。分析表明， 門級(jí)的一個(gè)單故障可

19、以代表實(shí)現(xiàn)該門的晶體管電路中的多個(gè)故障。對(duì)于ECL和TTL 電路來(lái)說(shuō)，晶體管電路中的短路和開(kāi)路故障，除少部分屬于延遲故障外，一般都可 6等效為門的輸入，輸出的 s一口一 os a一 1故障。這種事實(shí)說(shuō)明門級(jí)單固定故障模型具 有很高的真實(shí)性。 - 由于在集成電路工藝中，門是最小的邏輯單元，因此，芯片級(jí)測(cè) 試一般都要求考慮門級(jí)故障，采用門級(jí)故障模型 19 。222功能塊級(jí)單固定故障模型假設(shè) CUT中一次只有一個(gè)功能塊的一條輸入或輸出引腿發(fā)生j ao , 一al 故障，不考慮功能塊的內(nèi)部故障。此故障模型有時(shí)也叫功能塊引腿故障模型，它適合 于插件級(jí)測(cè)試。此模型的前提是組件內(nèi)部的故障應(yīng)在IC 測(cè)試中解決

20、，組件在裝入插件之前已經(jīng)過(guò)嚴(yán)格篩選。23本章小結(jié) 本章主要主要闡述數(shù)字電路模型研究和故障模型。自動(dòng)測(cè)試生成的系統(tǒng)模型， 應(yīng)從應(yīng)用且標(biāo)，即被測(cè)對(duì)象的基本特征中抽象出來(lái)。建立模型的基本出發(fā)點(diǎn)是：在 滿足對(duì)被測(cè)對(duì)象故障檢測(cè)要求的前提下，應(yīng)盡可能地使測(cè)試生成系統(tǒng)得到簡(jiǎn)化。3數(shù)字電路自動(dòng)測(cè)試生成系統(tǒng)結(jié)構(gòu) 一個(gè)完整的自動(dòng)測(cè)試生成系統(tǒng)，至少包括以下五個(gè)模塊：診斷數(shù)據(jù)庫(kù)、電路描述、 預(yù)處理、測(cè)試生成、故障模擬。自動(dòng)測(cè)試生成系統(tǒng)的系統(tǒng)流程圖如圖3 1所示·31診斷數(shù)據(jù)庫(kù) 圖31自動(dòng)測(cè)試生成流程圖31 1標(biāo)準(zhǔn)單元庫(kù)標(biāo)準(zhǔn)單元庫(kù)存放著構(gòu)成 cur 的硬件最小單元和軟件定義的基本邏輯單元功能塊的聯(lián)系和對(duì) 應(yīng)信

21、息。主要包括：11硬單元信息(1) 硬單元名稱、功能、引腿總數(shù)、輸出數(shù)、輸出引腿號(hào)、輸入數(shù)、輸入引腿號(hào)。(2) 硬單元特殊引腿說(shuō)明 給出正、負(fù)脈沖端、電源端、接地端、三態(tài)輸出端、三態(tài)控制端、雙向端等特 殊引腿的引腿號(hào)。(3) 硬單元?jiǎng)澐终f(shuō)明 一個(gè)硬單元，例如一塊組件，常由幾個(gè)功能獨(dú)立的邏輯塊構(gòu)成。2)功能塊信息(1) 功能塊結(jié)構(gòu)信息結(jié)構(gòu)信息的圖形表示 功能塊信息可以用圖形表示，圖形表示比較直觀，于程序設(shè)計(jì)師查詢 .結(jié)構(gòu)信息的文本描述 把一個(gè)組件劃分成幾個(gè)功能塊所得的功能塊結(jié)構(gòu)信息，可以用文本描述出來(lái)。(2) 結(jié)構(gòu)信息的功能信息 功能信息主要是指描述功能塊邏輯功能的布爾表達(dá)式。在內(nèi)存中用C立方形

22、式存儲(chǔ)。312 CUT信息庫(kù)CUT信息庫(kù)中存放著 CUT的邏輯圖、連線表和可供自動(dòng)測(cè)試生成的測(cè)試生成、故障模擬直接訪問(wèn)的鏈表結(jié)構(gòu)的拓?fù)潆娐贰＿壿媹D一般 mCAD系統(tǒng)的邏輯圖輸入程序提供，亦可從連線表自動(dòng)生成。連線 表可以在邏輯圖輸入過(guò)程中自動(dòng)提取，也可以從CAD系統(tǒng)的布線結(jié)果加工得來(lái)，還可以由用戶按照描述語(yǔ)言要求人工寫成并輸入機(jī)器。拓?fù)潆娐肥亲詣?dòng)測(cè)試生成的電 路描述程序?qū)?Cul鏈線表編譯的結(jié)果，要不要存入 CUT信息庫(kù)應(yīng)根據(jù)具體情況決定。 313庫(kù)操作程序庫(kù)操作程序完成庫(kù)信息的自動(dòng)產(chǎn)生和數(shù)據(jù)格式的自動(dòng)轉(zhuǎn)換。 9數(shù)據(jù)庫(kù)中有的信息時(shí)需要人工形成的，例如硬單元信息、功能塊劃分和結(jié)構(gòu)信 息等。但數(shù)多

23、信息是可以用庫(kù)操作程序自動(dòng)產(chǎn)生和轉(zhuǎn)換的。32電路描述 電路描述的任務(wù)是把用邏輯圖或連線表或某種機(jī)器內(nèi)部表格描述的被測(cè)電路的 結(jié)構(gòu)信息，轉(zhuǎn)換成機(jī)器內(nèi)部鏈表結(jié)構(gòu)的拓?fù)潆娐?，并?duì)不同性質(zhì)的引線變量給出不 同的標(biāo)記。電路描述程序既可以歸到庫(kù)操作程序中，也可以作為一個(gè)獨(dú)立模塊受自 動(dòng)測(cè)試生成系統(tǒng)調(diào)用。321面向結(jié)構(gòu)的電路描述語(yǔ)言電路描述程序的輸入信息是描述 CUI邏輯結(jié)構(gòu)的連線表。如果輸入信息是 CUT的邏 輯圖，則電路描述程序要從邏輯圖中自動(dòng)提取連線表；如果CUT的結(jié)構(gòu)信息來(lái) flCAD系統(tǒng)的自動(dòng)布線結(jié)果，則電路描述要把布線用的工程化信息加工成邏輯結(jié)構(gòu)信息，這些 信息供測(cè)試生成使用【 lIl 。一般采

24、用面向結(jié)構(gòu)的電路描述語(yǔ)言描述CUT的邏輯結(jié)構(gòu)信息，這種語(yǔ)言用結(jié)構(gòu)描述語(yǔ)言 (sDL ， Structural Descdption LaIlg 蚰ge) 就夠了。從滿足需要考慮，電路描述 語(yǔ)言至少要包括以下幾方面的語(yǔ)言：11描述 CUT物理信息的語(yǔ)句(1) 電路名語(yǔ)句；(2) 硬單元名稱與物理位置對(duì)照語(yǔ)句21描述 CUT的I O信息的語(yǔ)句(1) 初級(jí)輸入語(yǔ)句；(2) 初級(jí)輸出語(yǔ)句；(3) 脈沖 I O語(yǔ)句；(4) 接地I O語(yǔ)句；(5) 電源 I O語(yǔ)句。3)描述 CUr內(nèi)部特殊信號(hào)線語(yǔ)句(1) 反饋線語(yǔ)句；(2) 特殊測(cè)試點(diǎn)語(yǔ)句；(3) 固定電平線語(yǔ)句；“) 線邏輯語(yǔ)句；(5) 三態(tài)線語(yǔ)句；

25、(6) 雙向線語(yǔ)句。4) 描述 CUT基本硬單元互連關(guān)系的連線表語(yǔ)句322電路描述語(yǔ)言編譯器 電路描述語(yǔ)言編譯器一般采用多遍掃描方式。第一遍專門進(jìn)行語(yǔ)法規(guī)則檢查。 對(duì)于非自動(dòng)產(chǎn)生的連線表，這一遍至關(guān)重要。第二遍按隨機(jī)順序把CUT中各個(gè)硬單元連接起來(lái)，初步形成 CUT的鏈表結(jié)構(gòu)。第三遍掃描通過(guò)處理反饋線給功能塊定級(jí)， 按自動(dòng)測(cè)試生成系統(tǒng)要求標(biāo)志某些引線變量的特殊屬性等操作，最后形成以功能塊141。為基本邏輯單元的、按邏輯級(jí)從低到高順序排列的鏈表結(jié)構(gòu)的拓?fù)潆娐穮f(xié)323 CUT的鏈表拓?fù)浣Y(jié)構(gòu)CUT的鏈表結(jié)構(gòu)要設(shè)計(jì)得緊湊，使用方便，既要省內(nèi)存，又要查詢速度快。下 面給出的 TB， T取的鏈表結(jié)構(gòu)經(jīng)實(shí)際

26、證明效果較好，可以作為一種參考結(jié)構(gòu)。1)TB，TB是 CUT的總信息說(shuō)明和鏈表目錄。具體包括以下信息：(1) CUT名稱；(2) TB ：記錄名稱及記錄數(shù)；(3) T 臣記錄名稱及記錄數(shù)；(4) TB4 記錄名稱及記錄數(shù)；(5) TB ，記錄名稱及記錄輸；(6) CUT總信息記錄。包括 PI 總數(shù)、 PO總數(shù)、反饋線總數(shù)、功能塊總數(shù)、引線變 量總、最高邏輯級(jí)數(shù)、最高時(shí)序級(jí)數(shù)2)B2TB，是 CUT的引線變量表。自動(dòng)測(cè)試生成給引線編號(hào)的規(guī)則是：對(duì)每個(gè)功能塊 的每條輸出線編一個(gè)號(hào)，此號(hào)稱為引線號(hào)或引線變量號(hào)。輸入線不另編號(hào)，與其先 行輸出線共用一個(gè)變量號(hào)。 PI 線按虛擬功能的輸出對(duì)待。虛擬功能塊

27、是指虛設(shè)的、 輸出個(gè)數(shù)為 l 、輸入個(gè)數(shù)為 0的功能塊，在 TB2中一個(gè)引線變量占一個(gè)記錄，記錄號(hào) 與變量號(hào)相同。一個(gè)記錄包括以下信息：(1) 引線所屬硬單元的位置及引線的引腿號(hào)；(2) 引線在功能塊中的輸出端號(hào)；(3) 引線扇出個(gè)數(shù)；(4) 引線所屬功能塊的說(shuō)明信息在 TB：中的記錄號(hào)；(5) 引線的后繼說(shuō)明信息在 TB。的記錄號(hào)；(6) 引線特殊屬性標(biāo)志位。3)TB3TB，是 CuT的功能塊說(shuō)明信息表。每個(gè)功能塊在 TB，中占一個(gè)記錄，記錄號(hào)即是 功能塊在 CUT中的序號(hào)。一個(gè)記錄包括以下信息；(1) 功能塊類型編碼；(2) 功能塊輸出個(gè)數(shù)和輸入個(gè)數(shù)；(3) 功能塊邏輯級(jí)別；(4) 功能塊

28、的輸出說(shuō)明：按輸出端號(hào)從小到大順序，逐個(gè)說(shuō)明功能塊每個(gè)輸出的 引線變量號(hào)，并給出每個(gè)輸出的后繼信息在TB4的記錄號(hào)；(5) 功能塊輸入說(shuō)明：按輸入端號(hào)從小到大順序，逐個(gè)說(shuō)明功能塊每個(gè)輸入的引 腿號(hào)及對(duì)應(yīng)的引線變量號(hào)。在功能塊輸出，輸入說(shuō)明欄目中，每個(gè)輸出，輸入后面都附加一個(gè)標(biāo)志域。標(biāo)志域 中動(dòng)態(tài)記錄樹(shù)標(biāo)記和引線跳變標(biāo)記信息。輸入標(biāo)志域中還給出該輸入是否反饋線的 標(biāo)記。4)TB, TB4是CUT的后繼信息說(shuō)明表。一個(gè)引線變量的后繼說(shuō)明占一個(gè)記錄。一個(gè)記 3)錄包含下列信息：(1) 引線毛的后繼功能塊在 TB3中的記錄號(hào)；(2) 后繼功能塊與鼉相連的輸入端號(hào)。鼉有幾個(gè)后繼，在 TB4中便有幾個(gè)記錄

29、。最后給出記錄結(jié)束標(biāo)志。5) TB5TB。是 CUT的初級(jí)輸出列表。表中把可做為測(cè)試回收點(diǎn)的特殊測(cè)試點(diǎn)也做為PO給出。每 +PO在 TB5中占一個(gè)記錄。一個(gè)記錄包括下列內(nèi)容：(1) 初級(jí)輸出的引線變量號(hào)；(2) 初級(jí)輸出的插腳名或管腿號(hào)；(3) 初級(jí)輸出的特殊屬性標(biāo)志，是否脈沖輸出和特殊測(cè)試點(diǎn)等。33預(yù)處理 隨著自動(dòng)測(cè)試生成系統(tǒng)功能的日趨完善，處理能力的不斷提高，預(yù)處理技術(shù)的 地位顯得越來(lái)越重要。它不僅可為加速測(cè)試生成提供啟發(fā)引導(dǎo)信息，而且，許多在 測(cè)試生成過(guò)程中要反復(fù)用到的信息，在預(yù)處理階段一次性生成，有利于提高自動(dòng)測(cè) 試生成的執(zhí)行效率。331生成 CUT的目標(biāo)故障表之所以把生成 CUT的目

30、標(biāo)故障表歸到預(yù)處理技術(shù)中，是因?yàn)樗壬婕鞍炎詣?dòng)測(cè)試生成采用的 故障模型具體化的問(wèn)題，又涉及到根據(jù)故障等價(jià)原理對(duì)模型故障進(jìn)行 等價(jià)歸并得技術(shù)。既要達(dá)到故障模型要求，又要盡量精簡(jiǎn)目標(biāo)故障數(shù)，以減小自動(dòng) 測(cè)試生成的計(jì)算量是本程序的目標(biāo)。1)模擬故障的等價(jià)歸并(1) 基本門的等價(jià)故障與( 與非 )門用輸出的 0(1) 故障代替所有輸入的 0故障；或 (或非 ) 門用輸出的1(O) 故障代替所有輸入的 1故障非門和驅(qū)動(dòng)門只需設(shè)輸出的墨一 a一 0肛一口一 l 故 障。(2) 電路中的等價(jià)故障 如圖 3 2所示。功能塊 BI 的輸出與 B2的輸入的 0，1故障是不可區(qū)分的，只需設(shè) B1的輸出線葺 j 一口

31、一 0， Ja l 二個(gè)故障即可【 1卦。圖3 2等價(jià)故障示意圖 1 如圖 33所示， B1的輸出扇出到 B2和B3，這 3條線要設(shè) 6個(gè)模型故障。但由于這34k線與地短路的故障是不可區(qū)分的，只需設(shè) 體來(lái)說(shuō)，功能塊 B1的輸出屬于扇出源，要設(shè) 入屬于扇出分線，只需各設(shè)一個(gè)開(kāi)路故障，對(duì) $-a-0 故障。1個(gè)即可，因此共設(shè) 4個(gè)故障就夠了。具Sa一0，Ja一1兩個(gè)故障， B：和 B，的輸TTL電路設(shè) j a一1，對(duì) ECL電路設(shè)圖 33等價(jià)故障示意圖 2 統(tǒng)計(jì)結(jié)果表明，進(jìn)行上述等價(jià)歸并之后， CUT中的目標(biāo)故障大約只有模型故障 數(shù)的三分之二。當(dāng)然，還可以根據(jù)電路的邏輯關(guān)系做進(jìn)一步的精簡(jiǎn)，但要從性

32、能價(jià) 格比的角度考慮是否合算。2) 目標(biāo)故障的表示方法目標(biāo)故障在內(nèi)存中有兩種表示方法：位表示法和字符表示法(1) 位表示法這種表示法是：一個(gè)功能塊的故障表在內(nèi)存中占一個(gè)單元。功能塊的輸出O s口一 1及輸入故障分別用該單元不同的位表示，該位為 1，表示該故障存在， 為0表示該故障不存在這種表示法便于自動(dòng)測(cè)試生成系統(tǒng)從目標(biāo)故障表中取故障和 根據(jù)故障模擬結(jié)果對(duì)目標(biāo)故障表進(jìn)行故障覆蓋，即把已被檢測(cè)的故障從目標(biāo)故障表 中刪除。(2) 字符表示法 與位表示法相對(duì)應(yīng)的還有一種用字符表示法存儲(chǔ)的目標(biāo)故障表，它給出了每個(gè) 目標(biāo)故障在 CUT中的物理位置。具體格式是：硬單元坐標(biāo)，引腿號(hào)故障值。33 2從簡(jiǎn)到繁對(duì)

33、 CUT的測(cè)試樹(shù)頭排序 確定性測(cè)試生成的一般做法是按測(cè)試樹(shù)頭 ( 即測(cè)試回收點(diǎn)，它包括 PO和特殊回 收點(diǎn) )把CUT劃分成若干測(cè)試區(qū)，按從簡(jiǎn)到繁原則逐個(gè)測(cè)試區(qū)地生成測(cè)試碼、覆蓋 故障。對(duì)各測(cè)試區(qū)重迭部分的故障不搞重復(fù)覆蓋，這樣可以較大地降低自動(dòng)測(cè)試生 成的計(jì)算復(fù)雜性。這里的關(guān)鍵是對(duì)測(cè)試區(qū)從簡(jiǎn)到繁排序，也就是對(duì)測(cè)試樹(shù)頭排序。 實(shí)踐表明，如果把樹(shù)頭順序搞反了，則測(cè)試生成時(shí)間將成倍甚至按數(shù)量級(jí)增長(zhǎng) f ”。33 3生成樹(shù)標(biāo)記及各引線的樹(shù)頭級(jí)距上 h1)樹(shù)標(biāo)記得作用 用于自動(dòng)測(cè)試生成對(duì)大型 CUT的處理一般都是按樹(shù)或者說(shuō)按測(cè)試區(qū)進(jìn)行的，因 此，首先對(duì)當(dāng)前測(cè)試樹(shù)所含的功能塊和引線變量給出樹(shù)標(biāo)記，將后續(xù)

34、程序帶來(lái)許多 方便。(1) 生成樹(shù)故障表 樹(shù)故障表是當(dāng)前樹(shù)的測(cè)試生成和故障模擬所用的目標(biāo)故障表它是從CUT的總目標(biāo)故障表中，把那些有樹(shù)標(biāo)記得功能塊的輸出和輸入引線所對(duì)應(yīng)的故障位分離出 來(lái)構(gòu)成的。(2) 生成模擬功能塊表 把有樹(shù)標(biāo)記得功能塊按級(jí)別從低到高排列或者按故障模擬自行規(guī)定的順序排列 起來(lái)，便形成模擬功能塊表。故障模擬只需對(duì)表內(nèi)功能塊依次驅(qū)動(dòng)計(jì)算，這樣可以 避免對(duì)樹(shù)外進(jìn)行的無(wú)效計(jì)算。(3) 打跳變標(biāo)記 即給出從故障線到當(dāng)前樹(shù)頭所經(jīng)過(guò)的所有引線可能發(fā)生的跳變標(biāo)記。有了樹(shù)標(biāo) 記之后，只需分析有樹(shù)標(biāo)記得引線可能發(fā)生的跳變。(4) 確定故障敏化路徑測(cè)試生成需要確定敏化路徑， DRFM測(cè)度計(jì)算中需要

35、確定從故障線到樹(shù)頭的所有 敏化路徑上的必要敏化條件，上述操作都是限制在當(dāng)前樹(shù)內(nèi)進(jìn)行的。有了樹(shù)標(biāo)記， 可以防止敏化路徑向樹(shù)外延伸。(5) 識(shí)別會(huì)聚型扇出點(diǎn) 電路中的扇出點(diǎn)有會(huì)聚型和發(fā)散型兩類，許多測(cè)試生成算法和可測(cè)性分析方法 都考慮了會(huì)聚型扇出點(diǎn)的影響。要區(qū)分這兩類扇出需要進(jìn)行復(fù)雜的搜索判斷。但是， 有了樹(shù)標(biāo)記就方便得多了。一個(gè)扇出源只要有兩個(gè)以上扇出分支有樹(shù)標(biāo)記，則一定 是會(huì)聚型扇出源，否則就是發(fā)散型扇出源【 1s-20l 。2)生成樹(shù)標(biāo)記的方法 給出樹(shù)標(biāo)記的基本做法是反復(fù)查詢 TB表和 DB中的功能塊連通矩陣。先從樹(shù)頭開(kāi) 始，由 TB，中的樹(shù)頭變量號(hào)找到 TB：相應(yīng)的記錄，查出樹(shù)頭所屬功能塊

36、在 TB，中的記錄號(hào)，從 TB3中查得樹(shù)頭功能塊的類型編碼，由類型編碼可至IJDB 中找到有關(guān)的連通矩陣，從中可確定與樹(shù)頭有邏輯連通關(guān)系的功能塊的所有的輸入，再回到TB3中確定這些輸入的變量號(hào)，然后根據(jù)每個(gè)變量號(hào)重復(fù)上述1B，一 TB3-DB TB，的查詢過(guò)程，一直 NPI為止對(duì)上述過(guò)程中查到的 TB，中的功能塊及其有關(guān)輸出、輸入線都在TB，的標(biāo)志域中給出樹(shù)標(biāo)記。3) 引線的樹(shù)頭級(jí)距 k(1) 引線的樹(shù)頭級(jí)距的定義 電路中引線墨按信號(hào)傳播方向到達(dá)樹(shù)頭 Y所經(jīng)功能塊的最少級(jí)數(shù)，稱為薯的樹(shù) 頭級(jí)距，記為 k“) (2) 引線的樹(shù)頭級(jí)距的計(jì)算法則 引線的樹(shù)頭級(jí)距的初值是：當(dāng)置是故障線，其值為0；否則

37、其值為一。如果功能塊的輸出為 x，與 x邏輯相關(guān)的輸入是，屯， ，則'k( 力=Inink)+1(i=1 ，2，¨，喲 如果毛，吃， ，是 x小的扇出分線，則 k( 功=minLh(x ，)+10=1,2 ，”)(3) 引線的樹(shù)頭級(jí)距的用途 引線的樹(shù)頭級(jí)距是選擇最短敏化路徑的極好的引導(dǎo)函數(shù)，它具有計(jì)算簡(jiǎn)便、引 導(dǎo)準(zhǔn)確的特點(diǎn)。用 CUT的鏈表 TB， TB；中的現(xiàn)成信息，例如功能塊級(jí)別進(jìn)行引導(dǎo)行 不行呢 ?答案是否定的。因?yàn)榧词乖诮M合電路中，級(jí)別高的功能塊也不一定就離PO近，時(shí)序電路就更不用說(shuō)了。對(duì)于反饋線較多的時(shí)序電路，特別是閉環(huán)電路，選擇 敏化路徑的矛盾十分突出，而用三。

38、引導(dǎo)， 可以保證每次都能選擇較短的敏化路徑。 4) 生成 引線跳變標(biāo)記和各引線的故障級(jí)距三。(1) 何謂引線跳變標(biāo)記 引線苫，的跳變標(biāo)記指的是目標(biāo)故障確定之后，分析如果要從x ，傳播故障信號(hào)的話， z，可能發(fā)生的跳變。跳變標(biāo)記分 0-1 ，l 一0，0-1 1-0( 雙跳變 ) 和0-0 ( 無(wú)跳變 ) 四類，在 TB，的標(biāo)志域中分別用 01lO ，1001， 1111和0000表示。(2) 引線跳變標(biāo)記得作用 從測(cè)試生成角度看，在一個(gè)電路中設(shè)定了目標(biāo)故障鼉s ao之后，它中間的引線可以分為兩類：一類在邏輯上受薯的影響，一類不受葺的影響。前者稱為故障相關(guān) 線，后者稱為故障無(wú)關(guān)線不管采用那種算法

39、求測(cè)試，故障無(wú)關(guān)線都只需要(o，1，× )三個(gè)值即可描述。因此，把故障無(wú)關(guān)線區(qū)分出來(lái)有利于簡(jiǎn)化求測(cè)試的運(yùn)算過(guò)程。另一方面， 對(duì)故障相關(guān)線，通過(guò)跳變分析，排除不可能產(chǎn)生的故障信號(hào)，也可以簡(jiǎn)化相容性操作。(3) 引線跳變標(biāo)記得生成方法方法流程a) 從 CUT的目標(biāo)故障標(biāo)中取一位；b) 把此位翻譯成拓?fù)潆娐返墓收希?對(duì)功能塊輸出端故障， 給出故障引線變量號(hào)和故障值； 對(duì) 功能塊輸入故障，給出故障功能塊在 TB3的記錄號(hào)及故障線的輸入端號(hào)；c) 查故障功能塊 ( 對(duì)輸入故障 ) 的連通矩陣，確定與故障輸入端有邏輯連通關(guān) 系的輸出端的端號(hào)及其跳變；d) 從 TB，中確定上述輸出端的引線變量號(hào)及

40、其后繼TB。的記錄號(hào)；e) 由 TB。中查后繼功能塊 TB，記錄號(hào)及相應(yīng)的輸入端號(hào)； 0逐個(gè)查上述后繼功能塊的連通矩陣，由輸入跳變確定有邏輯連通關(guān)系的輸出 端的跳變：g)重復(fù) d) f) ，直到 PO為止。從輸入跳變確定輸出跳變的算法 設(shè)輸入跳變 A=100I 0110，連通矩陣中描述輸出與輸入邏輯連通關(guān)系的兩位 B=(hi,b2) ，其中 6l ， b2 (o ， 1) ，把占擴(kuò)展成邏輯字 C和D，其中 C=(blblblbl),D=(b2626262) 則描述輸出跳變的邏輯運(yùn)算都是按位操作。(4) 引線的故障級(jí)距工。 引線的故障級(jí)距的定義 電路中引線五按信號(hào)傳播的逆方向到達(dá)故障線，所經(jīng)功能

41、塊的最少級(jí)數(shù)，稱為薯 的故障級(jí)距，記為 k( 薯)。引線的故障級(jí)距的計(jì)算法則a) 引線的故障級(jí)距的初值是：當(dāng)薯是故障線，其值為0；否則其值為 oo。b) 如果功能塊的輸出為 x，與 x邏輯相關(guān)的輸入是毛， X2，則 k(功=mint_ ，( 五)+l O=l， 2， ?，按上述法則完成計(jì)算之后，凡與故障線邏輯無(wú) 關(guān)的引線的 k=一，其他線 k是 一個(gè)有限的正整數(shù)。引線的故障級(jí)距的用途a) 當(dāng)采用從 PO至t 故障線，或者說(shuō)從上到下的反向故障敏化策略時(shí)，工?？勺鰹?建立最短敏化路徑的引導(dǎo)函數(shù)。b)當(dāng)采用 G F二值公式， 用縱向回推法求測(cè)試時(shí)， 通過(guò)工。引導(dǎo)， 可以保證盡快回推到故障 線。做法也是從樹(shù)頭的一種 DRFM測(cè)度較低的跳變開(kāi)始，每次都從 (3- F二值公式的積之和展開(kāi)式中優(yōu)先選取 k較小的輸入變量的跳變向下展開(kāi)，直到故 障線為止c) 上。可作為從目標(biāo)故障選擇距離最近的樹(shù)頭的引導(dǎo)函數(shù)。測(cè)試生成的實(shí)踐表 明，一個(gè)目標(biāo)故障，總是在離它較近的PO上被檢測(cè)的可能性較大當(dāng)已知電路中各引線的 k之后，可把所有的 PO按三。從 4,N 大排序