一種非亂序存儲的數(shù)據(jù)交織加固技術(shù)*

王丹寧,劉 勝,李振濤

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

1 引言

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

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

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

2 交織編解碼原理

2.1 當前交織編解碼原理

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

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

其中，n為交織深度，m為交織約束長度或?qū)挾?。交織的過程為按列寫入，按行讀出。待交織數(shù)據(jù)以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個輸入數(shù)據(jù)的交織深度為n、交織約束寬度為m的分組交織。作為交織過程的逆過程，解交織的過程為按行寫入，按列讀出，待解交織的數(shù)據(jù)以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列的交織矩陣中讀出，這樣就完成了逆交織，恢復成為交織前的數(shù)據(jù)。

Figure 1 Codeword form圖1 碼字形式

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

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

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

編碼模塊如圖3所示。

Figure 3 Encoding module圖3 編碼模塊

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

Figure 4 Decoding module圖4 解碼模塊

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

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

(1)

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

按行讀出的交織結(jié)果為：

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

(2)

將交織結(jié)果X′存入存儲器中。若此時產(chǎn)生一個連續(xù)4位錯誤，錯誤位的下標分別為0,8,16,24，使得存儲信息變?yōu)閄″，表示為：

(3)

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

(4)

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

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

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

3 非亂序交織編解碼設(shè)計

3.1 非亂序交織編解碼過程

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

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

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

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

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

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

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

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

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

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

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

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

(5)

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

按列讀出時，每一列數(shù)據(jù)為一組，分別進入內(nèi)部編碼模塊進行編碼，每列數(shù)據(jù)加上如下所示的校驗位的編碼結(jié)果：

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

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

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

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

(6)

將交織結(jié)果Y′存入存儲器中?？梢钥闯觯藭r存入存儲器的數(shù)據(jù)位的順序同待寫入存儲器的數(shù)據(jù)相同。假設(shè)在存儲器中產(chǎn)生連續(xù)的4位錯誤，其下標為0,1,2,3，使得存儲信息變?yōu)閅″，可表示成式(7)所示：

(7)

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

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

(8)

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

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

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

(9)

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

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

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

(10)

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

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

4 驗證和評估分析

4.1 驗證平臺的搭建

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

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

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

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

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

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

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

4.2 驗證結(jié)果

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

功能點的驗證仿真波形如圖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)成立，即后續(xù)算子表達式成立，至此整個斷言表達式成立，因此功能點的斷言成功，驗證完成。

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

5 結(jié)束語

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