容錯系統中的自校驗技術(shù)及實(shí)現方法

摘要：闡述了自校驗技術(shù)在容錯系統中的作用，給出了自校驗網(wǎng)絡(luò )實(shí)現原理及實(shí)現方法，指出用VHDL語(yǔ)言結合FPGA/CPLD是實(shí)現大規模自校驗網(wǎng)絡(luò )的有效途徑。

關(guān)鍵詞：容錯自校驗完全自校驗VHDLFPGA/CPLD

容錯是容忍錯誤的簡(jiǎn)稱(chēng)，容錯系統是指在發(fā)生硬件故障或存在軟件錯誤的情況下，仍能繼續正確完成指定任務(wù)的系統。設計與分析容錯系統的各種技術(shù)稱(chēng)為容錯技術(shù)。有關(guān)計算機容錯技術(shù)的各種理論及研究已經(jīng)發(fā)展成為計算機學(xué)科的一個(gè)重要分支，稱(chēng)為容錯計算（Fault-tolerantComputing)。設計容錯系統的指導思想是：系統發(fā)生故障時(shí)能自動(dòng)檢出并使系統自動(dòng)恢復正常運行。

為保證系統具有高可靠、長(cháng)壽命和響應迅速，必須采用容錯技術(shù)。從功能上講，一個(gè)容錯系統可用圖１所示框圖來(lái)描述，系統模塊可由若干個(gè)功能相同的子模塊并聯(lián)組成，故障檢測模塊對系統模塊的功能進(jìn)行檢測，檢測到故障后由故障處理模塊對系統模塊進(jìn)行重新配置，使系統在部分模塊失效的情況下，仍能輸出正確結果。在這個(gè)系統中，故障檢測模塊和故障處理模塊起著(zhù)至關(guān)重要的作用，它們往往是系統的薄弱點(diǎn)。因此，容錯系統要有高的可靠性必須保證故障檢測和處理模塊的可靠性，故障檢測系統不僅要檢測系統模塊的故障，而且還要能夠檢測自身的故障，使故障處理模塊得以正確處理所發(fā)生的故障。

自校驗技術(shù)是用于故障快速檢測的一種有效手段，特別是具有完全自校驗性質(zhì)的自校驗裝置，它不僅能及時(shí)檢出系統模塊的差錯，還能檢測出自身的差錯。在容錯系統設計中，將自校驗網(wǎng)絡(luò )置于系統中，可大大提高系統對差錯的反應能力，使差錯潛伏期縮短，有效地防止錯誤傳播。

１自校驗網(wǎng)絡(luò )定義

一個(gè)容錯系統，其所有可能的輸出值組成的集合U（稱(chēng)輸出空間）由S和U-S兩部分組成。當系統中無(wú)故障時(shí)，系統輸出S中的元素，一旦系統發(fā)生故障則輸出U-S中的元素。

如果一個(gè)電路的正常輸出集S是一個(gè)檢錯碼集，則該電路稱(chēng)為自校驗電路。在無(wú)故障發(fā)生的情況下，自校驗電路輸出碼向量；當預定故障發(fā)生時(shí)，則輸出非碼向量。連接在自校驗電路輸出端的校驗器監督電路的輸出，當非碼向量出現時(shí)，校驗器給出差錯指示。自校驗電路與校驗器一起構成了自校驗網(wǎng)絡(luò )，其結構如圖２所示。

下面我們給出自校驗網(wǎng)絡(luò )的幾個(gè)概念，設S(X)是輸入向量空間，

是合法輸入向量空間，

是非法輸入向量空間，S(F)是輸出向量空間，

是合法輸出向量空間，

是非法輸出向量空間，

是組合邏輯網(wǎng)絡(luò )所考慮的單故障集，網(wǎng)絡(luò )的所有輸入取自其合法輸入集。

定義１：組合邏輯網(wǎng)絡(luò )對

是自測試的（簡(jiǎn)稱(chēng)ST），若：對任意故障

存在

，使網(wǎng)絡(luò )輸出

。

該定義是說(shuō)對給定單故障集中的任何一個(gè)故障，總存在一個(gè)合法輸入，它將導致組合邏輯網(wǎng)絡(luò )產(chǎn)生非法輸出，即用該輸入可檢測此故障。

定義２：組合邏輯網(wǎng)絡(luò )對

是故障保險的（簡(jiǎn)稱(chēng)FSE），若：對任意故障

存在

使網(wǎng)絡(luò )輸出

，或者

，其中G(X)是網(wǎng)絡(luò )的正確輸出。

該定義是說(shuō)在合法輸入條件下，對給定單故障集中的任何一個(gè)故障，組合邏輯網(wǎng)絡(luò )將給出一個(gè)合法輸出或一個(gè)非法輸出，但不會(huì )給出同該合法輸入不相對應的另一個(gè)合法輸出。

定義３：組合邏輯網(wǎng)絡(luò )對

是完全自校驗的，若它對

是自測試的和故障保險的。

對給定單故障集中的任何一個(gè)故障，完全自校驗的組合邏輯網(wǎng)絡(luò )在合法輸入的情況下，或者產(chǎn)生一個(gè)合法輸出，或者產(chǎn)生一個(gè)非法輸出，且后者在故障存在期間是必然要出現的。這就使得網(wǎng)絡(luò )在不產(chǎn)生不正確合法輸出的同時(shí)，能并發(fā)檢測

中的所有故障，這也正是在線(xiàn)測試對差錯檢測及時(shí)性的要求。

若采用檢錯編碼技術(shù)實(shí)現自校驗邏輯網(wǎng)絡(luò )時(shí)，校驗器的任務(wù)是用來(lái)檢查功能模塊輸出碼字的有效性，它能區分功能模塊輸出是否合法，這種特性被稱(chēng)為碼分離特性，其定義如下。

定義４：一個(gè)邏輯網(wǎng)絡(luò )具有碼分離特性，若滿(mǎn)足：

（１）任給

，有

（合法輸入映射為合法輸出）

（２）任給

，有

（非法輸入映射為非法輸出）

定義５：一個(gè)邏輯網(wǎng)絡(luò )是完全自校驗器，若它具有完全自校驗及碼分離特性。

設組合邏輯網(wǎng)絡(luò )正確輸入矢量為

，則矢量空間

稱(chēng)作錯誤輸入空間，記作

；空間

被稱(chēng)作非法及錯誤輸入空間，記作

。由正確輸入空間

經(jīng)電路G可在S(F)中產(chǎn)生一個(gè)子空間，這個(gè)子空間稱(chēng)為正確輸出空間，記為

。同樣，對于合法輸入

，由組合邏輯網(wǎng)絡(luò )可映射為合法輸出空間

它也是輸出矢量空間S(F)的子集。同樣，空間

被稱(chēng)作錯誤輸出空間，記作

；空間

被稱(chēng)為非法及錯誤輸出空間，表示為

。上述輸出之間有如下關(guān)系：

由上面集合之間的關(guān)系我們可以看出，對于無(wú)故障組合網(wǎng)絡(luò )的正確輸入，其輸出應落入正確輸出空間

中。通過(guò)對網(wǎng)絡(luò )的輸出可部分判定系統工作是否正常（無(wú)法判斷某些故障）。當網(wǎng)絡(luò )發(fā)生故障時(shí)，可分成以下幾種情況：①非法及錯誤輸入被映射成

；②輸入

被映射成為

；③

映入

但已不是正確的映射關(guān)系，也就是說(shuō)輸入輸出關(guān)系發(fā)生了變化。對于一個(gè)高可靠容錯系統來(lái)說(shuō)，必須能夠以比較高的故障覆蓋率來(lái)檢測出以上三類(lèi)差錯（最好在一拍內檢出），使系統及時(shí)采取措施，隔離故障，將其影響減小到最低限度。在三類(lèi)錯誤中，第①類(lèi)和第②類(lèi)與第③類(lèi)相比要好檢測一些，高效檢測第③類(lèi)錯誤是提高系統故障覆蓋率的關(guān)鍵，只有設計出對以上三類(lèi)錯誤檢出率均較高的檢錯系統，才能保證系統有較高的可靠性。

２自校驗網(wǎng)絡(luò )的結構

自校驗網(wǎng)絡(luò )具有在無(wú)任何外加激勵的情況下能自動(dòng)檢測其內部是否存在故障，這些故障或是永久性的或是暫時(shí)性的。設計自校驗網(wǎng)絡(luò )的主要技術(shù)有檢錯編碼技術(shù)，基于自對偶函數的交替邏輯技術(shù)（交織邏輯技術(shù)），基于對偶函數的互補邏輯技術(shù)，還有基于多值邏輯的實(shí)現方法，下面我們主要討論一些實(shí)用的實(shí)現方法。

2.1雙軌碼校驗器

雙軌碼校驗器的原理圖如圖３所示。

輸入矢量為

，其中

，（i=1,2)，輸出矢量為

且滿(mǎn)足：

若

且校驗器無(wú)故障。

利用雙軌碼校驗器的上述特點(diǎn)，設計一對偶組合邏輯網(wǎng)絡(luò )，使其輸出向量

和

恰好反相，將

和

加到雙軌碼校驗器輸入端，根據

就可以判定系統是否發(fā)生故障。

2.2可分碼校驗器

可分碼校驗器的結構如圖４所示。校驗器的輸入矢量為

)，矢量

和

分別對應可分碼的信息分量和校驗分量。其中，信息分量寬度為

是校驗分量的寬度，且1+K=n,n=‖Y‖。校驗位生成電路根據信息位

重新生成校驗位W，由雙軌碼校驗器比較W與

的一致性，在無(wú)故障的情況下，校驗器的輸出

指示輸入矢量的有效性。下面的定理給出了圖４完全自校驗可分碼校驗器的構造條件。

定理：圖４所示的可分碼校驗器是完全自校驗的，若校驗位生成器是一個(gè)無(wú)冗余的組合邏輯網(wǎng)絡(luò )，且比較器是完全自校驗的。

2.3互補邏輯網(wǎng)絡(luò )

利用互補邏輯也可以構成自校驗電路，如果某一邏輯網(wǎng)絡(luò )其輸入輸出關(guān)系為

,則可構造一互補邏輯網(wǎng)絡(luò )，使其輸入輸出關(guān)系為

其中ｆ和ｆ是互補的，在無(wú)故障的情況下，其輸出是互補的；若發(fā)生輸出相同，則兩個(gè)邏輯電路中必定有存在故障的情況?；パa邏輯網(wǎng)絡(luò )實(shí)現原理比較直觀(guān)，但對較復雜的系統，有許多故障它是檢測不出來(lái)的。

2.4交織邏輯網(wǎng)絡(luò )

交織邏輯網(wǎng)絡(luò )是基于自對偶函數的自校驗邏輯網(wǎng)絡(luò )。一個(gè)二進(jìn)制變量是交替的，記作

若x在兩個(gè)連續的時(shí)間間隔內所取的值互補。

對任意一個(gè)開(kāi)關(guān)函數

，若假設

是交替二進(jìn)制變量，且它們是同步交替的，則ｇ的輸入矢量可表示為

，其輸出可表示為

，要使輸出變量也是交替的，必須滿(mǎn)足

，顯然，g必須是自對偶函數。利用交織邏輯網(wǎng)絡(luò )的這個(gè)特點(diǎn)，可以檢測出系統的一部分故障。

３自校驗網(wǎng)絡(luò )實(shí)現方法

對于一些比較簡(jiǎn)單的應用場(chǎng)合，利用數字邏輯方法進(jìn)行設計，使用SSI及MSI集成電路即可方便地構成自校驗網(wǎng)絡(luò )。但實(shí)際容錯系統非常復雜，涉及大量邏輯設計，若仍采用傳統的數字邏輯設計方法，不僅工作量大、容易出差錯，而且修改和功能仿真都不方便。使用電子設計硬件描述語(yǔ)言VHDL（或VerilogHDL對電路功能進(jìn)行描述，用FPGA或CPLD器件實(shí)現自校驗網(wǎng)絡(luò )是比較現實(shí)的，對于大批量生產(chǎn)，可將VHDL描述的電路送半導體器件廠(chǎng)進(jìn)行批量生產(chǎn)，VHDL硬件描述語(yǔ)言實(shí)現自校驗網(wǎng)絡(luò )的步驟如下：

①建立自校驗網(wǎng)絡(luò )的功能模型。對系統的輸入／輸出、狀態(tài)轉換、信號傳遞等進(jìn)行詳細的說(shuō)明。

②用VHDL語(yǔ)言或VerilogHDL語(yǔ)言對電路功能進(jìn)行描述。對復雜系統可采用自上而下的設計方法，將系統分解成不同層次的、功能較簡(jiǎn)單的模塊，利用VHDL語(yǔ)言對系統功能進(jìn)行分層描述，減少系統描述造成的錯誤。

③對不同層次的模塊進(jìn)行功能仿真，以檢驗各模塊設計的正確性，最后對整個(gè)系統進(jìn)行功能仿真，及早排除系統設計中的錯誤。

④用VHDL或VerilogHDL綜合編譯器對設計好的系統進(jìn)行編譯，經(jīng)過(guò)邏輯化簡(jiǎn)及綜合布線(xiàn)，生成可對FPGA或CPLD編程的數據文件。

⑤將數據文件通過(guò)編程器寫(xiě)入FPGA或CPLD，進(jìn)行實(shí)際測試，若測試數據滿(mǎn)足設計要求，則開(kāi)發(fā)工作完成；否則，轉①重新進(jìn)行檢查和設計。

采用自校驗技術(shù)后，可有效地提高容錯系統的可靠性，隨著(zhù)集成電路技術(shù)的飛速發(fā)展，可將一些自校驗功能模塊進(jìn)行封裝，作為標準單元使用，在模塊級上提高容錯系統的可靠性。采用高級語(yǔ)言和FPGA或CPLD開(kāi)發(fā)容錯系統具有重要的現實(shí)意義，可有效縮短開(kāi)發(fā)周期，降低開(kāi)發(fā)成本，提高系統可靠性，應在工程設計中加以推廣應用。