容錯系統中的自校驗技術及實現方法

闡述了自校驗技術在容錯系統中的作用，給出了自校驗網絡實現原理及實現方法，指出用VHDL語言結合FPGA/CPLD是實現大規模自校驗網絡的有效途徑。

??? 關鍵詞： 容錯 自校驗 完全自校驗 VHDL FPGA/CPLD

??? 容錯是容忍錯誤的簡稱，容錯系統是指在發生硬件故障或存在軟件錯誤的情況下，仍能繼續正確完成指定任務的系統。設計與分析容錯系統的各種技術稱為容錯技術。有關計算機容錯技術的各種理論及研究已經發展成為計算機學科的一個重要分支，稱為容錯計算（Fault-tolerant Computing)。設計容錯系統的指導思想是：系統發生故障時能自動檢出并使系統自動恢復正常運行。

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

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

??? １ 自校驗網絡定義

??? 一個容錯系統，其所有可能的輸出值組成的集合U（稱輸出空間）由S和U-S兩部分組成。當系統中無故障時，系統輸出S中的元素，一旦系統發生故障則輸出U-S中的元素。

??? 如果一個電路的正常輸出集S是一個檢錯碼集，則該電路稱為自校驗電路。在無故障發生的情況下，自校驗電路輸出碼向量；當預定故障發生時，則輸出非碼向量。連接在自校驗電路輸出端的校驗器監督電路的輸出，當非碼向量出現時，校驗器給出差錯指示。自校驗電路與校驗器一起構成了自校驗網絡，其結構如圖２所示。

??? 下面我們給出自校驗網絡的幾個概念，設S(X)是輸入向量空間，是合法輸入向量空間，是非法輸入向量空間，S(F)是輸出向量空間，是合法輸出向量空間，是非法輸出向量空間，是組合邏輯網絡所考慮的單故障集，網絡的所有輸入取自其合法輸入集。

??? 定義１：組合邏輯網絡對是自測試的（簡稱ST），若：對任意故障存在，使網絡輸出。

??? 該定義是說對給定單故障集中的任何一個故障，總存在一個合法輸入，它將導致組合邏輯網絡產生非法輸出，即用該輸入可檢測此故障。

??? 定義２：組合邏輯網絡對是故障保險的（簡稱FSE），若：對任意故障存在使網絡輸出，或者，其中G(X)是網絡的正確輸出。

??? 該定義是說在合法輸入條件下，對給定單故障集中的任何一個故障，組合邏輯網絡將給出一個合法輸出或一個非法輸出，但不會給出同該合法輸入不相對應的另一個合法輸出。

??? 定義３：組合邏輯網絡對是完全自校驗的，若它對是自測試的和故障保險的。

??? 對給定單故障集中的任何一個故障，完全自校驗的組合邏輯網絡在合法輸入的情況下，或者產生一個合法輸出，或者產生一個非法輸出，且后者在故障存在期間是必然要出現的。這就使得網絡在不產生不正確合法輸出的同時，能并發檢測中的所有故障，這也正是在線測試對差錯檢測及時性的要求。

??? 若采用檢錯編碼技術實現自校驗邏輯網絡時，校驗器的任務是用來檢查功能模塊輸出碼字的有效性，它能區分功能模塊輸出是否合法，這種特性被稱為碼分離特性，其定義如下。

??? 定義４：一個邏輯網絡具有碼分離特性，若滿足：

??? （１）任給 ，有（合法輸入映射為合法輸出）

??? （２）任給，有（非法輸入映射為非法輸出）

??? 定義５：一個邏輯網絡是完全自校驗器，若它具有完全自校驗及碼分離特性。

??? 設組合邏輯網絡正確輸入矢量為，則矢量空間稱作錯誤輸入空間，記作；空間被稱作非法及錯誤輸入空間，記作。由正確輸入空間經電路G可在S(F)中產生一個子空間，這個子空間稱為正確輸出空間，記為。同樣，對于合法輸入，由組合邏輯網絡可映射為合法輸出空間它也是輸出矢量空間S(F)的子集。同樣，空間被稱作錯誤輸出空間，記作；空間被稱為非法及錯誤輸出空間，表示為。上述輸出之間有如下關系：

??? 由上面集合之間的關系我們可以看出，對于無故障組合網絡的正確輸入，其輸出應落入正確輸出空間中。通過對網絡的輸出可部分判定系統工作是否正常（無法判斷某些故障）。當網絡發生故障時，可分成以下幾種情況：①非法及錯誤輸入被映射成；②輸入被映射成為；③映入但已不是正確的映射關系，也就是說輸入輸出關系發生了變化。對于一個高可靠容錯系統來說，必須能夠以比較高的故障覆蓋率來檢測出以上三類差錯（最好在一拍內檢出），使系統及時采取措施，隔離故障，將其影響減小到最低限度。在三類錯誤中，第①類和第②類與第③類相比要好檢測一些，高效檢測第③類錯誤是提高系統故障覆蓋率的關鍵，只有設計出對以上三類錯誤檢出率均較高的檢錯系統，才能保證系統有較高的可靠性。

??? ２ 自校驗網絡的結構

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

??? 2.1 雙軌碼校驗器

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

??? 輸入矢量為，其中，（i=1,2)，輸出矢量為且滿足：

??? 若且校驗器無故障。

??? 利用雙軌碼校驗器的上述特點，設計一對偶組合邏輯網絡，使其輸出向量和恰好反相，將和加到雙軌碼校驗器輸入端，根據就可以判定系統是否發生故障。

??? 2.2 可分碼校驗器

??? 可分碼校驗器的結構如圖４所示。校驗器的輸入矢量為)，矢量和分別對應可分碼的信息分量和校驗分量。其中，信息分量寬度為是校驗分量的寬度，且1+K=n, n=‖Y‖。校驗位生成電路根據信息位重新生成校驗位W，由雙軌碼校驗器比較W與的一致性，在無故障的情況下，校驗器的輸出指示輸入矢量的有效性。下面的定理給出了圖４完全自校驗可分碼校驗器的構造條件。

??? 定理：圖４所示的可分碼校驗器是完全自校驗的，若校驗位生成器是一個無冗余的組合邏輯網絡，且比較器是完全自校驗的。

??? 2.3 互補邏輯網絡

??? 利用互補邏輯也可以構成自校驗電路，如果某一邏輯網絡其輸入輸出關系為,則可構造一互補邏輯網絡，使其輸入輸出關系為其中ｆ和ｆ是互補的，在無故障的情況下，其輸出是互補的；若發生輸出相同，則兩個邏輯電路中必定有存在故障的情況。互補邏輯網絡實現原理比較直觀，但對較復雜的系統，有許多故障它是檢測不出來的。

??? 2.4 交織邏輯網絡

??? 交織邏輯網絡是基于自對偶函數的自校驗邏輯網絡。一個二進制變量是交替的，記作若x在兩個連續的時間間隔內所取的值互補。

??? 對任意一個開關函數，若假設是交替二進制變量，且它們是同步交替的，則ｇ的輸入矢量可表示為，其輸出可表示為，要使輸出變量也是交替的，必須滿足，顯然，g必須是自對偶函數。利用交織邏輯網絡的這個特點，可以檢測出系統的一部分故障。

??? ３ 自校驗網絡實現方法

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

??? ①建立自校驗網絡的功能模型。對系統的輸入／輸出、狀態轉換、信號傳遞等進行詳細的說明。

??? ②用VHDL語言或Verilog HDL語言對電路功能進行描述。對復雜系統可采用撟隕隙?聰的設計方法，將系統分解成不同層次的、功能較簡單的模塊，利用VHDL語言對系統功能進行分層描述，減少系統描述造成的錯誤。

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

??? ④用VHDL或Verilog HDL綜合編譯器對設計好的系統進行編譯，經過邏輯化簡及綜合布線，生成可對FPG A或CPLD編程的數據文件。

??? ⑤將數據文件通過編程器寫入FPGA或CPLD，進行實際測試，若測試數據滿足設計要求，則開發工作完成；否則，轉①重新進行檢查和設計。

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