一種非亂序存儲的數據交織加固技術*

王丹寧,劉 勝,李振濤

(國防科技大學計算機學院，湖南 長沙 410073)

1 引言

在現在大多電子系統中，靜態隨機訪問存儲器SRAM(Static Random Access Memory)是必不可少的一部分，廣泛應用于嵌入式專用集成電路中[1]，SRAM存儲的可靠性對電子系統至關重要[2]?？臻g輻射環境中，高能粒子引起的存儲電路中的單粒子翻轉SEU(Single Event Upsets)是集成電路最常見的可靠性問題之一[3,4]。在深亞微米體系下，中子引發的軟錯誤[5]甚至會導致多個物理相鄰的存儲元發生翻轉，即MCU(Multiple Cell Upset)，嚴重時可能導致系統崩潰。通過觀察發現，發生軟錯誤的多個存儲元大多是物理相近的[6]。為了減輕軟錯誤帶來的影響，多采用糾錯碼ECCs(Error Correction Codes)來對存儲器進行加固[7 - 9]。人們發明了漢明碼、循環碼和卷積碼等編碼技術對存儲器進行加固，但這些技術僅在檢測和校正單個差錯和不太長的差錯串時才有效，當產生連續多個誤碼時，漢明碼、循環碼和卷積碼就不能滿足所需的糾錯能力，于是有了交織技術的出現[10]。在對發送的數據進行編碼后，通過交織將原來的順序打亂寫入存儲器，這樣當數據產生連續錯誤時，由于接收端要先進行解交織，連續錯誤就會被打散，有利于解碼模塊進行糾錯[11]。針對漢明碼、循環碼和卷積碼，在無突發干擾時，交織技術對3種典型的信道糾錯編碼性能影響不大；有突發干擾時，交織技術通過改造信道但不增加冗余，有效提高了3種典型的信道糾錯編碼性能[10]。因此，可通過在編碼中融入交織來糾正連續多位錯誤，從而對存儲進行加固。然而，交織也帶來了存儲信息亂序的問題。

針對交織帶來的存儲信息亂序這一問題，本文提出了一種非亂序存儲的數據交織加固技術，通過改進原來的交織編解碼問題，將交織融入編解碼模塊來解決存儲信息亂序問題。最后的驗證結果表明，該技術不但能充分利用交織的優勢，糾正連續多位錯誤，還能保證存儲數據順序與原始數據順序相同。

本文首先在第1節給出引言，然后在第2節提出當前交織編解碼原理及其存在的問題，接著在第3節提出非亂序交織編解碼設計過程，在第4節給出驗證和評估分析結果，最后在第5節進行總結。

2 交織編解碼原理

2.1 當前交織編解碼原理

常用的交織方法有分組交織、卷積交織和隨機交織[10]，本文主要依據分組交織。分組交織的原理是將待交織的輸入數據均勻分成多個碼字，碼字表示進行過糾檢錯編碼的數據，由數據位和校驗位構成，以可以糾一檢二的Hsiao碼為例，m位碼字形式如圖1所示，由k位數據位和m-k位校驗位組成。

假設要進行分組交織的數據能均勻分成n個m位碼字，則該數據可構成一個m行n列的交織矩陣，如下所示：

其中，n為交織深度，m為交織約束長度或寬度。交織的過程為按列寫入，按行讀出。待交織數據以1，2，…,m，m+1，m+2,…,2m,…,(n-1)m+1，(n-1)m+2，…,nm的順序進入交織矩陣，再以1，m+1,…,(n-1)m+1，2,m+2，…,(n-1)m+2，…,m，2m，…,nm的順序從交織矩陣中讀出，這樣就完成了對nm個輸入數據的交織深度為n、交織約束寬度為m的分組交織。作為交織過程的逆過程，解交織的過程為按行寫入，按列讀出，待解交織的數據以1，m+1,…,(n-1)m+1，2,m+2，…,(n-1)m+2，…,m，2m，…,nm的順序進入交織矩陣，再以1，2，…,m，m+1，m+2,…,2m,…,(n-1)m+1，(n-1)m+2，…,nm的順序從m行n列的交織矩陣中讀出，這樣就完成了逆交織，恢復成為交織前的數據。

Figure 1 Codeword form圖1 碼字形式

利用交織對存儲進行加固的主要過程如圖2所示，當需要將數據寫入存儲器時，先將待寫入存儲器的數據分組，并對每組數據用編碼模塊進行糾檢錯編碼，如糾一檢二碼、糾一檢二糾相鄰碼等；然后以分組數作為交織深度、編碼后的數據位數作為交織

Figure 2 Interleaving process with encoding and decoding圖2 交織編解碼過程

約束寬度對編碼后的數據進行交織，每組碼字為交織矩陣的一列，將交織結果寫入存儲器。當從存儲器讀出存儲字后，將其按行寫入交織矩陣進行解交織，然后分組進行解碼，輸出解碼結果。

編碼模塊如圖3所示。

Figure 3 Encoding module圖3 編碼模塊

解碼模塊如圖4所示，其中，可糾錯誤類型表示錯誤為可以糾正的錯誤，解碼后的數據為正確的數據，可糾錯誤比特位置表示當錯誤為可糾錯類型時的出錯比特位置，不可糾錯誤類型表示錯誤不可被糾正。

Figure 4 Decoding module圖4 解碼模塊

若數據有24位，要通過交織編解碼來對存儲進行加固，若編碼模塊可對6位數據進行糾一檢二編碼，校驗位數為2位，則可將原數據分成4組，每組數據位數為6位分別進行編碼，編碼后每組數據為8位，共32位。然后對編碼后數據進行深度為4、約束寬度為8的交織后寫入存儲器。這32位數據可表示如式(1)所示：

X=(x0,x1,x2,x3，…,x29,x30,x31)

(1)

交織時，將X按列寫入如下所示的8*4的交織矩陣中：

按行讀出的交織結果為：

X′=(x0,x8,x16,x24,…,x15,x23,x31)

(2)

將交織結果X′存入存儲器中。若此時產生一個連續4位錯誤，錯誤位的下標分別為0,8,16,24，使得存儲信息變為X″，表示為：

(3)

在進行讀操作時，將其從存儲器讀出后，先進行解交織，即將其按行寫入如下所示的8*4的交織矩陣中：

(4)

可見，經過交織矩陣與解交織矩陣的變換后，原來X′的連續4位錯，就變成了X″中的隨機獨立差錯，通過每8位進行糾一檢二的糾錯，可以分別將4位錯糾正。所以，交織結合糾檢錯編碼可以糾正連續多位錯。

2.2 當前交織編解碼存在的問題

從2.1節的交織編碼例子可以看出，由于進行了交織，當交織結果存入存儲器后，存儲信息是亂序存放的，也就是說，當前用交織編解碼進行存儲加固存在存儲數據亂序問題。這雖然對芯片本身不構成影響，但在進行硬件調試時，數據信息亂序會給硬件調試時的數據訪問帶來不便，進而影響硬件調試，降低硬件調試效率。所以，將存儲信息調整為正確的順序是有必要的。為了既能發揮交織地糾正連續多位錯的優勢，又能確保存儲信息的正常順序，本文設計了一種非亂序存儲的數據交織加固技術。

3 非亂序交織編解碼設計

3.1 非亂序交織編解碼過程

本文對交織編解碼過程進行了改進，提出非亂序交織編解碼過程，如圖5所示，同之前的交織編解碼過程相比，本交織編解碼過程將交織融入編解碼過程，提出非亂序交織編碼和非亂序交織解碼。

Figure 5 Non-out-of-order interleaving encoding and decoding process圖5 非亂序交織編解碼過程

3.2 非亂序交織編碼模塊和非亂序交織解碼模塊

通過對原交織編解碼過程進行分析不難看出，導致存儲數據亂序的主要原因是交織，若要讓數據恢復成正常的順序，就需對其解交織。所以，可以在將數據存入存儲器前，對其進行一次交織和一次解交織操作，使得存入存儲器的數據順序不發生改變。于是，本文提出了非亂序交織編碼模塊，將原先的編碼模塊與交織融合到一起，采用逆交織、編碼、交織的方法來保證存入存儲器的數據為正常的順序。非亂序交織編碼模塊如圖6所示。

Figure 6 Non-out-of-order interleaving encoding module圖6 非亂序交織編碼模塊

圖6中，虛線框表示將編碼與交織進行封裝，框內整體作為非亂序交織編碼模塊，框外為模塊的輸入輸出，后面的非亂序交織解碼模塊同理。

如圖6所示，在數據存入存儲器前，先對其進行逆交織，按行寫入交織矩陣；然后讀出的每一列作為一組，對每組分別進行糾檢錯編碼，如糾一檢二、糾一檢二糾相鄰等；然后將編碼后的數據進行拼接，再進行交織，最后將交織結果存入存儲器。解交織和交織的交織深度相同，根據輸入數據位數d和內部編碼模塊輸入的數據位數s來確定交織深度n，確定方法為：n=d/s，交織約束寬度不同，解交織約束寬度為m=d/n，交織約束寬度為m=s+r，r為內部編碼模塊輸入的數據位數為s時的校驗位數。

作為編碼模塊的逆過程，非亂序交織解碼模塊將解碼過程與交織融合，采用交織、解碼、逆交織的順序，就可以對讀出的數據進行解碼糾錯。非亂序交織解碼模塊如圖7所示。

LMPP方法根據功能函數的非線性程度及目標可靠度確定局部采樣區域的大小，但由于未能考慮Kriging近似的誤差，導致局部采樣區域過小而遺漏某些重要樣本點。如圖3所示，f(x)為真實的功能函數約束邊界，為由克里金近似擬合出來的約束函數邊界。外邊的圓圈是本文提出的局部采樣區域，里面的圓圈是LMPP方法的局部采樣區域?？梢钥闯?，利用LMPP方法進行采樣時，由于未能充分考慮克里金近似的誤差，導致對真實的功能函數約束邊界f(x)影響較大的樣本點A未被采樣，降低了采樣效率。為提升LMPP方法的采樣效率，本文在功能函數非線性程度及目標可靠度的基礎上，進一步考慮Kriging近似的誤差，計算模型如下：

Figure 7 Non-out-of-order interleaving decoding module圖7 非亂序交織解碼模塊

若待寫入存儲的數據Y為32位，進行深度為4的交織，則圖6中的每個編碼模塊需要對8位數據進行編碼，假設進行糾一檢二編碼，每8位數據需要5位校驗位。待寫入存儲器的數據Y可表示如式(5)所示：

Y=(y0,y1,y2,…,y29,y30,y31)

(5)

對數據Y進行交織深度為4、交織約束寬度為8的逆交織，即將其按行寫入如下所示的8*4的交織矩陣中：

按列讀出時，每一列數據為一組，分別進入內部編碼模塊進行編碼，每列數據加上如下所示的校驗位的編碼結果：

其中，r1～r5表示交織矩陣第1列的8位數的校驗位，其它3列以此類推。

在編碼后進行交織，交織矩陣深度仍為4，但交織約束寬度變為8+5=13，13*4的交織矩陣如下所示：

按行讀出交織結果Y′如式(6)所示：

Y′=(y0,y1,y2,…,r1,r6,…,r15,r20)

(6)

將交織結果Y′存入存儲器中?？梢钥闯?，此時存入存儲器的數據位的順序同待寫入存儲器的數據相同。假設在存儲器中產生連續的4位錯誤，其下標為0,1,2,3，使得存儲信息變為Y″，可表示成式(7)所示：

(7)

將Y″從存儲器讀出后進行交織深度為4、交織約束寬度為13的逆交織，交織矩陣如下所示：

按列讀出逆交織結果Y?如式(8)所示：

(8)

每一列為一組，對每組數據進行糾一檢二解碼，由于每組均產生了1位錯，為可糾錯類型，用4個解碼模塊對各列進行解碼，4個錯誤均可以得到糾正，所以解碼后的沒有校驗位的數據Y″″如式(9)所示：

Y″″=(y0,y4,…,y24,y28,y1,y5,…,y25,y29,

y2,y6,…,y26,y30,y3,y7,…,y27,y31)

(9)

對解碼后的數據進行交織深度為4、交織約束寬度為8的交織，交織矩陣如下所示：

按行讀出的交織結果Y″″′如式(10)所示。

Y″″′=(y0,y1,y2,…,y29,y30,y31)

(10)

由于錯誤得到糾正，所以Y″″′=Y。

可見，經過交織矩陣與解交織矩陣的變換后，原來X′的連續4位錯也得到了糾正，而且存儲器的數據信息也沒有亂序。所以，非亂序交織編解碼過程既能發揮交織地糾正連續多位錯的優勢，又能確保存儲信息的正常順序。

4 驗證和評估分析

4.1 驗證平臺的搭建

本節基于驗證需求，搭建了一個層次化且高效的驗證平臺。此驗證平臺中包含隨機激勵、約束、黃金模型和斷言表達式等，目的是實現自動產生帶約束的激勵與自動地進行比對驗證。

本文基于某商業公司的RTL模擬環境來進行驗證，驗證程序用SystemVerilog編寫。本次驗證的原始數據位數為32位，交織深度為4，每8位數據位需要5位校驗位，共需要4*5=20位校驗位。驗證平臺的搭建主要有以下2個方面：

(1)定義功能點和激勵：驗證糾錯后的數據和參考模型中正確的數據是否一致。由于驗證中的激勵主要是不斷地在不同地址的數據中的不同位置加入連續多位錯，激勵類型比較單一，所以本次測試用例由加過約束條件后的rand類型變量自動產生，提高了效率。在進行功能點驗證時，由5個rand類型變量來控制錯誤的插入，rand類型變量is_add_err表示是否要插入錯誤，rand類型變量whichbit_1、whichbit_2、whichbit_3和whichbit_4分別表示是否給連續4位錯的第1/2/3/4位插入錯誤。因此，會有如下幾種出錯情況：無錯以及有1/2/3/4位錯，然后每次通過比較存儲器返回數據與黃金存儲模型golden_ram中的數據是否一致來確定錯誤是否得到糾正。

(2)驗證平臺的搭建如圖8所示，待測設計DUT(Design Under Test)的周圍即為驗證平臺，驗證平臺將生成的激勵添加給待測設計，同時捕捉待測設計的響應。主要步驟如下：定義激勵;將激勵添加到待測設計;捕捉待測設計的響應;檢查結果是否正確。

Figure 8 Schematic diagram of verification platform and design under test圖8 驗證平臺與待測設計示意圖

Figure 9 Comparison of data before non-out-of-order interleaving encoding and when storing in memory圖9 非亂序交織編碼前與存入存儲器時的數據比較

Figure 10 Function point verification圖10 功能點驗證

4.2 驗證結果

非亂序交織編碼前與存入存儲器時的數據比較的仿真波形如圖9所示。由圖9可知，在TimeA=131120000 ps時，存儲使能ME(Memory Enable)和存儲寫使能WE(Write Enable)均有效，此時，非亂序交織編碼前的數據data_before_enc為0xc1b08c88，非亂序交織編碼后的數據data_after_enc為0x97be9c1b08c88，待寫入存儲器的數據D為0x97be9c1b08c88。從數據對比可以看出，非亂序交織編解碼前后的數據順序沒有發生改變，從而寫入存儲器的數據順序也沒有發生改變。

功能點的驗證仿真波形如圖10所示。從圖10中可以看出TimeA和TimeB都處于時鐘上升沿，TimeB比TimeA快了1個時鐘周期即快了1拍，用TimeB= 216598000 ps為基準表示當前時刻，用TimeA表示前一拍。斷言在時鐘上升沿需滿足：(req&&!rdwrt)|=>(rtn_data==$past(golden_ram[addr],1))；由上式可知，此時|=>的左邊，req=1，rdwrt=0，所以滿足先行算子表達式；而|=>的右邊，在TimeB時刻rtn_data=0x45ac49b5，$past(,1)表示前一拍，而此時addr=0xc，golden_ram[0xc]前一拍的值即TimeA時刻的值也等于0x45ac49b5。所以，此時rtn_data== $past(golden_ram[addr],1)成立，即后續算子表達式成立，至此整個斷言表達式成立，因此功能點的斷言成功，驗證完成。

由驗證結果可知，一方面，非亂序交織編解碼前后的數據順序沒有發生改變，從而寫入存儲器的數據順序也沒有發生改變；另一方面，驗證糾錯后的數據和參考模型中正確的數據一致。因此，非亂序交織編解碼過程既能發揮交織地糾正連續多位錯的優勢，又能確保數據順序不被打亂。與原交織編解碼相比，非亂序交織編解碼僅增加了1次交織和1次解交織。

5 結束語

存儲加固引入交織可提高存儲可靠性，交織會帶來存儲數據信息亂序的問題，進而影響硬件調試時的數據訪問，降低硬件調試效率。本文提出一種非亂序存儲的數據交織加固技術，通過對原交織編解碼過程、編解碼模塊進行改進，提出了非亂序交織編解碼過程和非亂序交織編解碼模塊，不但能充分利用交織的優勢，還可將存儲數據轉換成非亂序。