一種基于擴展?jié)h明碼的動態(tài)糾錯機制

陳天培，吳校生，強小燕

（1.上海交通大學(xué)微米/納米加工技術(shù)國家級重點實驗室，上海 200240；2.中科芯集成電路有限公司，江蘇無錫 214072）

1 引言

存儲器作為儲存大量數(shù)據(jù)的電路元件，對數(shù)據(jù)可靠性的要求很高。提升存儲器可靠性的一種常見手段是通過增加冗余硬件設(shè)計來對工作電路進(jìn)行保護[1]。給數(shù)據(jù)增加糾錯碼（Error Correcting Code, ECC）或檢錯碼（Error Detecting Code, EDC）是冗余硬件設(shè)計的一種思路。常見的ECC 或EDC 包括奇偶校驗碼、CRC校驗、漢明碼、BCH 碼、RS 碼[2-3]等。各種碼的復(fù)雜度不同，糾錯能力也不盡相同。其中，漢明碼最為常見。漢明碼是一種線性分組碼[4]，能夠?qū)崿F(xiàn)一位比特糾錯。在電路中，一位錯誤出現(xiàn)的概率最大[5]，因此漢明碼得到了廣泛的應(yīng)用。

盡管ECC 碼是一種有效的增加存儲器可靠性的保護措施，但同時也帶來了一些負(fù)面影響。增加冗余信息碼會帶來額外的面積開銷、編解碼帶來的功耗提升以及較長的組合邏輯時延。如何進(jìn)行優(yōu)化，研究人員對其進(jìn)行了深入的探索，并得到了大量的研究成果。文獻(xiàn)[6]提出了兩種基于漢明碼的新的編碼機制SEC-DAED 以及SEC-DED-TAED，在不增加校驗位位數(shù)的情況下，前者能夠?qū)崿F(xiàn)一位糾錯、連續(xù)兩位檢錯，后者能夠?qū)崿F(xiàn)一位糾錯、兩位檢錯以及連續(xù)三位檢錯。文獻(xiàn)[7]進(jìn)一步提出了一種可變范圍的連續(xù)位糾錯的編碼機制，同時不增加同等情況下漢明碼的校驗位數(shù)。文獻(xiàn)[8-9]則研究了對糾錯碼編解碼模塊的優(yōu)化。本文基于擴展?jié)h明碼這一編碼機制進(jìn)行了深入的研究，提出了一種動態(tài)糾錯機制。

2 擴展?jié)h明碼原理與設(shè)計

2.1 擴展?jié)h明碼原理

漢明碼的基本思想是將待檢驗的數(shù)據(jù)碼元進(jìn)行分組，再分別對各組碼元進(jìn)行編碼生產(chǎn)對應(yīng)校驗碼。若是某一個數(shù)據(jù)位出現(xiàn)錯誤，則該數(shù)據(jù)位所屬的組校驗碼將無法與當(dāng)前數(shù)據(jù)對應(yīng)，即發(fā)生錯誤。通過計算出校驗碼無法對應(yīng)的分組來確定最終出錯的數(shù)據(jù)位。

漢明碼能夠?qū)崿F(xiàn)一位檢錯與糾錯。以n位數(shù)據(jù)為例，若附加的冗余校驗位位數(shù)為r，對于校驗位來說，需要唯一表示任何一位的出錯情況以及數(shù)據(jù)正確的情況，因此n、r兩者的關(guān)系由式（1）約束：

當(dāng)數(shù)據(jù)位位數(shù)為32 位時，則所需要的冗余位為6位。基于式（1），每當(dāng)數(shù)據(jù)位位數(shù)增加一倍，所需的冗余位位數(shù)增加一位。

普通漢明碼只能夠檢測并修正一位錯誤。通過再增加一位奇偶校驗碼，可以實現(xiàn)兩位錯誤的識別，該碼被稱為擴展?jié)h明碼[4]。

2.2 校驗碼生成算法

本文進(jìn)行校驗的數(shù)據(jù)位寬為32 位。擴展?jié)h明碼的編碼方式如式(2)～(8)所示。其中bn為校驗位n，an為數(shù)據(jù)位n。可以看到每位校驗位的生成是對特定的數(shù)據(jù)位異或運算后生成的。而增加的一位奇偶校驗位則是對所有的數(shù)據(jù)位進(jìn)行異或運算。

基于上述算法生成的校驗位不僅可以對數(shù)據(jù)進(jìn)行一位糾錯，同時可以對校驗位本身進(jìn)行一位糾錯。其一位錯誤位由以下流程確定：進(jìn)行ECC 校驗時，將儲存的校驗碼以及相應(yīng)數(shù)據(jù)發(fā)至檢查模塊，對數(shù)據(jù)重新生成校驗碼，將原校驗碼與新生成的校驗碼進(jìn)行比較（異或），產(chǎn)生7 位的錯誤編碼；再將錯誤編碼送至譯碼模塊，確定錯誤位置。對于一位錯誤來說，錯誤編碼第7 位必然為1。而對于兩位錯誤，錯誤編碼的第7 位必然為0，此時若剩余6 位錯誤編碼不為0 時，則發(fā)生了兩位或以上的錯誤。一位錯誤及兩位錯誤檢測如圖1 所示，其中syndrome 信號表示錯誤編碼，single_err信號表示一位錯誤，double_err 信號表示兩位錯誤。

圖1 一位錯誤及兩位錯誤檢測

2.3 ECC 糾錯模塊設(shè)計

按照以上算法，本文基于Verilog 語言進(jìn)行了ECC 糾錯模塊的設(shè)計。ECC 糾錯模塊整體分為3 個子模塊：校驗碼生成模塊、檢查模塊和修復(fù)模塊。當(dāng)數(shù)據(jù)要被送入到存儲器前，通過校驗碼生成模塊生成校驗碼，并與數(shù)據(jù)一起送入存儲器中。當(dāng)需要取用數(shù)據(jù)時，則讀出數(shù)據(jù)到檢查模塊，利用生成模塊生成新校驗碼后并得到錯誤編碼，根據(jù)錯誤編碼產(chǎn)生一位以及兩位錯誤信號。如若有一位錯誤，則進(jìn)一步送至修復(fù)模塊對數(shù)據(jù)進(jìn)行修正，ECC 糾錯模塊如圖2 所示。

圖2 ECC 糾錯模塊

3 動態(tài)糾錯機制原理與設(shè)計

3.1 動態(tài)糾錯機制原理簡述

由上述算法可以看出，與奇偶校驗相比，漢明碼校驗各校驗位生成與檢查均需進(jìn)行大量的異或計算。在具體實現(xiàn)上引入了較長的組合邏輯，帶來了更長的延時。同時進(jìn)行數(shù)據(jù)編解碼時，邏輯門頻繁的翻轉(zhuǎn)也導(dǎo)致了更大的動態(tài)功耗。盡管奇偶校驗在功耗與延時上都優(yōu)于漢明碼校驗，但奇偶校驗本身只能檢測一位錯誤，而不能糾正錯誤。擴展?jié)h明碼則能夠糾正一位錯誤，檢測兩位錯誤。為了盡可能利用兩種校驗方式的優(yōu)勢，本文提出了一種動態(tài)糾錯機制，在保證漢明碼糾錯強度的同時，降低糾錯過程的延時與動態(tài)功耗。

其基本原理是在檢查階段，利用奇偶校驗碼對所有數(shù)據(jù)進(jìn)行校驗。而在糾錯階段，則采用漢明碼糾正錯誤。注意到擴展?jié)h明碼最高位本身是所有數(shù)據(jù)的奇偶校驗位，因此對數(shù)據(jù)進(jìn)行奇偶檢驗時，只需對原始校驗碼最高位進(jìn)行計算并檢查。這就使得檢查的邏輯延時縮短。而其他比較邏輯在奇偶校驗期間不會工作，降低了檢查模塊的動態(tài)功耗。

存儲器復(fù)位之后，開啟奇偶校驗。當(dāng)?shù)谝淮我晃诲e誤出現(xiàn)時，動態(tài)糾錯模塊將在下一個時鐘周期對同一數(shù)據(jù)進(jìn)行漢明碼校驗，以修正錯誤。同時開啟讀請求計數(shù)，若在設(shè)定的次數(shù)內(nèi)不再發(fā)生一位錯誤，則可認(rèn)為該一位錯誤是偶發(fā)錯誤，糾錯模塊將繼續(xù)用奇偶校驗對數(shù)據(jù)進(jìn)行檢查。若在設(shè)定的次數(shù)內(nèi)再次發(fā)生一位錯誤，則可以認(rèn)為工作環(huán)境發(fā)生了變化，糾錯模塊將持續(xù)開啟漢明碼校驗。在持續(xù)開啟漢明碼校驗的階段，每次新發(fā)生的一位錯誤將重置讀請求計數(shù)。若在讀請求計數(shù)達(dá)到設(shè)定值前都未發(fā)生錯誤，動態(tài)糾錯模塊將重新切換至奇偶校驗。圖3 為動態(tài)糾錯機制的基本控制流程圖。

圖3 動態(tài)糾錯機制控制流程

3.2 動態(tài)糾錯機制模塊設(shè)計

動態(tài)糾錯模塊由一個ECC 監(jiān)控模塊以及ECC 糾錯模塊組成。ECC 糾錯模塊的一位錯誤輸出信號將被送至監(jiān)控模塊。監(jiān)控模塊則基于上文所述邏輯對ECC糾錯模塊進(jìn)行控制。監(jiān)控模塊自身采用一個有限狀態(tài)機實現(xiàn)狀態(tài)轉(zhuǎn)移。圖4 和5 分別為動態(tài)糾錯模塊功能框圖以及狀態(tài)轉(zhuǎn)移圖。狀態(tài)轉(zhuǎn)移圖中，fe（first error）指示第一次出現(xiàn)錯誤，pe（parity error）指示奇偶校驗錯誤，ce（count end）指示計數(shù)完畢。該狀態(tài)機所有狀態(tài)位均為高有效。

圖4 動態(tài)糾錯模塊功能框圖

模塊啟動后，狀態(tài)機處于idle（空閑）狀態(tài)，并開啟奇偶校驗。當(dāng)檢測到奇偶校驗錯誤時，pe 置1，此時狀態(tài)機切換至first_cnt（第一次計數(shù)）狀態(tài)，模塊將進(jìn)行一次糾錯。pe 在計數(shù)時置0，fe 置1。在計數(shù)過程中，若再次發(fā)生錯誤，pe 置1，狀態(tài)機切換到second_cnt（第二次計數(shù)）狀態(tài)。若未發(fā)生錯誤，則計數(shù)完畢后ce 置1，狀態(tài)機回到idle 狀態(tài)。在second_cnt 狀態(tài)下，動態(tài)糾錯機制模塊將持續(xù)開啟漢明碼校驗。若在第二次計數(shù)過程中發(fā)生錯誤，則重置計數(shù)器。若不發(fā)生錯誤，狀態(tài)機返回idle 狀態(tài)。

圖5 動態(tài)糾錯模塊狀態(tài)機

4 功能驗證

基于上述模塊搭建仿真環(huán)境，并進(jìn)行驗證。動態(tài)糾錯機制的主要功能點包括兩個部分，第一個部分為底層ECC 糾錯邏輯；第二個部分為奇偶校驗與擴展?jié)h明碼校驗間的切換。

4.1 ECC 糾錯模塊的驗證

ECC 糾錯模塊的驗證分為一位數(shù)據(jù)的糾錯以及二位數(shù)據(jù)的檢錯。為測試所有出錯的可能性，依次翻轉(zhuǎn)原始數(shù)據(jù)的每一位，并送至糾錯模塊。圖6 和7 分別為一位錯誤情況和兩位錯誤情況。信號data_in[31:0]為原始數(shù)據(jù)，data_to_ip[31:0]為正確數(shù)據(jù)，data_from_ip[38:0]中低32 位為翻轉(zhuǎn)后的數(shù)據(jù)，高7 位則為校驗碼。data_correct_out[31:0]為修正后的數(shù)據(jù)。r 則指示一位錯誤，fatal_error 指示兩位錯誤。當(dāng)發(fā)生一位錯誤時，singlebit_error 置1，同時糾錯模塊將修正后的數(shù)據(jù)送出。當(dāng)發(fā)生兩位錯誤時，fatal_error 置1，同時糾錯模塊將原始數(shù)據(jù)送出。

圖6 一位錯誤

圖7 兩位錯誤

4.2 奇偶校驗與擴展?jié)h明碼校驗切換

根據(jù)上文所述流程，當(dāng)?shù)谝淮纬霈F(xiàn)錯誤時，動態(tài)糾錯機制將執(zhí)行一次漢明碼糾錯。當(dāng)一段時間內(nèi)第二次出現(xiàn)錯誤時，動態(tài)糾錯機制將持續(xù)開啟漢明碼糾錯。奇偶校驗與漢明碼校驗切換如圖8 所示，當(dāng)指示奇偶校驗錯誤的信號parity_err 第一次出現(xiàn)且讀請求rd_req 拉高時，使能信號ecc_en 置1，漢明碼糾錯執(zhí)行一次。同時計數(shù)器開始計數(shù)，當(dāng)計數(shù)器達(dá)到設(shè)定值而未出現(xiàn)第二次錯誤時，計數(shù)器停止計數(shù)，first_err 置0，等待下一次奇偶校驗錯誤。當(dāng)計數(shù)器未到達(dá)設(shè)定值而出現(xiàn)第二次錯誤時，second_err 信號置1，同時計數(shù)器置0，漢明碼糾錯常開。當(dāng)?shù)谌五e誤出現(xiàn)時，計數(shù)器再次歸0，重新計數(shù)。若后續(xù)再無錯誤出現(xiàn)且計數(shù)器達(dá)到設(shè)定值，first_err 以及second_err 置0，動態(tài)糾錯機制重新回到奇偶校驗狀態(tài)并等待下一次錯誤信號。圖8中還驗證了當(dāng)計數(shù)器正好達(dá)到設(shè)定值時出現(xiàn)錯誤的情況，可以看到，設(shè)計的模塊能夠正常工作。

圖8 奇偶校驗與漢明碼校驗切換

5 綜合結(jié)果與分析

使用Synopsys 公司的綜合工具Design Compiler在中芯國際（SMIC）55 nm 工藝庫下對設(shè)計進(jìn)行綜合。表1 列出了采用擴展?jié)h明碼校驗與采用動態(tài)糾錯機制的關(guān)鍵路徑延時與動態(tài)功耗。從表中可以看出，動態(tài)糾錯機制在延時上降低了7.49%，在動態(tài)功耗上則降低了22.09%。延時上的降低是因為動態(tài)糾錯機制將擴展?jié)h明碼校驗中的奇偶校驗與漢明碼校驗分開到兩個時鐘周期進(jìn)行。而動態(tài)功耗上的降低則是因為動態(tài)糾錯機制僅在ECC 使能時才開啟漢明碼校驗。

表1 綜合結(jié)果

6 結(jié)論

本文提出了一種基于擴展?jié)h明碼的動態(tài)糾錯機制，能夠有效提高ECC 校驗檢錯階段的效率，減少無效檢錯。本文主要對擴展?jié)h明碼的原理進(jìn)行了闡述，并設(shè)計了基于擴展?jié)h明碼的ECC 糾錯模塊。同時進(jìn)一步闡明了動態(tài)糾錯機制的原理，完成模塊設(shè)計，最后對設(shè)計進(jìn)行了仿真與分析。綜合結(jié)果表明，相比傳統(tǒng)擴展?jié)h明碼校驗，該機制在延時與動態(tài)功耗上有明顯降低。