高可靠性SRAM中縮短漢明碼EDAC電路的失效分析

劉 鑫 ，趙發展,劉夢新，韓鄭生

（中國科學院 微 電子研究所，北京100029）

盡管包括BCH碼和LDPC碼在內糾正多位錯誤的編碼已經被廣泛使用于通信系統中，但由于其較多的校驗位，硬件冗余較大以及電路設計的復雜性，很少使用在抗單輻射存儲器之中。M.Y.Hsiao通過在能夠糾正一位錯誤的漢明碼基礎上增加一位冗余校驗位，提出了一種能夠糾正一個錯誤并且檢測兩個錯誤（single-error-correcting and double-error detecting，SECDED）的Hsiao碼[1-3]。不過部分抗輻射高可靠性存儲器采取周期性的回寫策略，并不需要一個探測信號觸發。最近，一系列處理連續多字節翻轉的改進漢明碼被提出來[4-5]，但是并沒有得到大規模的應用。就目前而言，傳統的糾正單個錯誤的漢明碼因其較高的碼率和較少的冗余校驗位，仍然是被廣泛應用于存儲器可靠性的編碼[6-10]。但是關于存儲器單個字節內多翻轉導致采用漢明碼的糾錯電路失效的研究并不多。

1 縮短漢明碼的構造

假設漢明碼的碼字長度為n而信息位的長度為k，因此校驗位數目m(m≥3)為m=n-k，其中n和k可以用m來表示為：

因為存儲器字節長度是2的整數次冪，因此需要從k為信息位中刪除l位。縮短后漢明碼的碼字和信息位長度分別為n’和k’，令k’等于小于 k的最大2的整數次冪，有：

因此縮短漢明碼的n’和k’均可由m表示出來。縮短漢明碼距離t=3，糾錯能力依然為1。

在編碼時，待編碼的信息位向量u乘以生成矩陣G編碼得到碼字v=(uGT,u)。在譯碼階段，讀出的碼字r乘以校驗矩陣H的轉置，乘得的結果成為校正子。根據校正子就可以確定是哪一位發生了錯誤。縮短漢明碼的校驗矩陣H是由(n,k)漢明碼的校驗矩陣刪除l個列向量得到的。例如（15,11）漢明碼的校驗矩陣為：

其中，黑色粗體列向量恰好等于2的整數次冪，對應漢明碼碼字中的校驗位；后面的列向量對應于信息位。如果最終計算出的校正子等于H中的黑色粗體列向量，則認為是對應校驗位發生了翻轉；反之則認為是對應信息位發生了翻轉。為了構造（12,8）縮短漢明碼，從H中刪除含有1個數最多的最后面4列，使硬件復雜度降至最低。因為校驗矩陣中1的個數越多，表示在硬件實現中，需要的模二加法器，即異或門越多[11]。根據校驗矩陣H以及其和生成矩陣G的關系，我們可以得到（12,8）縮短漢明碼生成矩陣G的表示形式為：

Q′矩陣轉置得到P矩陣，In表示n維單位矩陣。

2 引理

首先介紹3個在推到概率分布的過程中將會用到的引理。

引理1如果一個列向量的重量為N并且滿足N≥3，則有N種方式將它表示成為一個校驗位對應的列向量和一個十進制表示較小的列向量的模2和。其中重量是指一個GF(2)上的向量中等于1的個數。

證明:校驗位對應的列向量重量為1而信息位對應的列向量重量大于等于2。我們可以將引理中較大的列向量中的某個“1”置為“0”。假設這個“1”在第 i位上，對應于 2 的 i-1次冪。由于原來的向量重量大于等于3，這樣新生成的列向量的重量必然大于等于2，仍然是一個信息位對應的列向量，并且小于原來的列向量。這樣就把原來的向量分解成一個較小的信息位列向量和第i-1個校驗位列向量之和。

引理 2讓n′展開成為2的冪和形式：

其中

q(r)是最大的非零冪指數。

則對于任意m維向量，表示成十進制小于n′并且重量等于w(2≤w≤m)的列向量的數目為：

其中r是非零冪指數的數目。比如,15可以被表示成為15=23+22+21+20，其中 r=4，q(4)=3，q(3)=2,q(2)=1 和 q(1)=0。

證明：用排列組合的知識來證明這個引理。我們需要在長度為m的向量中放置w個“1”并且使它表示成十進制要小于n’。假如一個“1”占據了q(r)的位置，那么就從0到q(r-1)中選取w-1個“1”來放置。如果第二個1已經占據了q(r-1)的位置，那么剩下的w-2個“1”必須占據0到q(r-1)的位置，以此類推。如果沒有“1”來占據q(r)的位置，那么剩下的w個“1”必須用來占據從0到q(r)-1的位置。

引理3.在縮短漢明碼校驗矩陣H中，任意兩個列向量的模二和的重量大于等于2的組合數為：

證明：選擇中任意兩個列向量，并減去生成向量重量等于1的組合數。可以把3個在GF(2)上模二和封閉的列向量組成一個三元組，然后在剔除任何涉及到重量等于1的校驗位列向量的三元組即可。其實也是將一個信息位向量分解成兩個信息位向量的個數。

3 縮短漢明碼錯誤輸出模式的概率分布

采用傳統漢明碼的EDAC只能糾正一位錯，因此單字節多位翻轉會失效。假設SRAM中一個存儲單元（bitcell）內在一定的時間內發生翻轉的概率p是相等并且相互獨立的。令A表示最終糾錯電路輸出的結果有誤，一個字節內發生了i位翻轉可以用事件Bi表示，則有：

一個存儲單元在一段時間內積累一個錯誤的概率p非常小，近似有：

因此，我們主要關注一個字節內的兩位翻轉導致的錯誤輸出的情況。

1)單字節內發生兩位翻轉，最終卻輸出正確：

只有一種情況：兩個翻轉均位于校驗位上，生成的校正子對應于縮短漢明碼校驗矩陣H中的一位被刪除的列向量。可以得到：

2)單字節內發生兩位翻轉，輸出有1位錯誤：

有兩種情況，第一種是一個翻轉是在信息位，另一個翻轉是在校驗位，生成的校正子對應于校驗位或者被刪除。從對應于信息位和校驗位的列向量中各選取一個，減去生成的校正子是其他信息位的情況，運用引理得到：

第二種是兩個翻轉都位于校驗位，生成的校正子對應于一個信息位。概率為：

將以上兩者相加，得到總的概率為：

3)單字節內發生兩位翻轉，輸出有2位錯誤：

有兩種情況：第一種是兩個翻轉一個在信息位，一個在校驗位，生成的校正子對應于信息位。運用引理3可以得到其概率為：

第二種情況是兩個翻轉都在信息位，生成的校正子對應于校驗位，或者被刪除。

4)單字節內發生兩位翻轉，輸出有3位錯誤：

只有一種情況，兩位翻轉都在信息位，生成的校正子也對應于信息位。任選兩個對應于信息位的列向量，減去生成的校正子對應校驗位和刪除列向量的情況，計算出概率等于：

根據上述公式，計算出的概率分布用origin繪出圖1。如圖1所示，若一個字節內發生兩位翻轉，采用縮短漢明碼的EDAC電路的輸出可以出現1位錯，2位錯，3位錯和沒有錯誤。當m增加使碼子的長度增加時，輸出1位錯和輸出3位錯的概率分別逐漸降低和增加；而輸出2位錯的概率先有所增加，然后減小。對于m=7而言，輸出3位錯的概率已經占據接近60%，因為對于較長的碼字信息位個數所占的比重就越大。從趨勢圖中可以預見，如果碼字越長，則失效時輸出的3位錯誤的概率就越大。一個字節內翻轉兩位而EDAC電路輸出沒有錯誤的情況始終只占很小的一部分。采用MATLAB軟件進行模擬，結果如圖2所示。比較理論和計算機試驗所得的結果，可以看出兩者僅存在極其細微的差別，理論推導的結論在可接受范圍內。

圖1 理論概率分布圖2試驗概率分布Fig.1 Probability distribution of theory

圖2 試驗概率分布Fig.2 Probability distribution of trial

4 一種將較長碼字分成兩部分分別編譯碼的方案

將一個長度為k1的信息向量分成長度相等的兩部分，采用縮短漢明碼編碼得到碼字和信息位長度分別為（n2,k2）的兩個碼字，其中k2=k1/2。根據前面的存儲單元失效概率p的假設，未分裂碼字時效性的概率為：

分裂之后的編譯碼系統失效的概率，等于用1減去兩個子碼都正常工作的概率：

可以證明在存儲單元失效概率p非常小的假設下，有Porigin>Psplit,因此分裂后的碼字同樣采用縮短漢明碼，失效的概率更低。因為在兩個子碼中分別只有1位翻轉的情況是可以糾正的，而對于原來的編譯碼系統卻是導致錯誤輸出。根據前面討論，分裂后的碼字在失效狀態下輸出錯誤信息中含有3位翻轉的概率大大降低，因此降低了輸出錯誤率。此外，由于編譯碼的碼字較短，編譯碼硬件邏輯深度更小，所以速度較原來的更快。表I中給出了不同的差錯控制編碼之間特性的比較[12]。

表1 SEC,SEC-DED,DEC和分裂SEC之間校驗位數目的比較Tab.1 Comparison of the number of check bits between SEC,SEC-DED and DEC

通過將長度為16的信息位分成兩個長度為8的信息向量分別采用SEC編譯碼，冗余校驗位從5位增加至8位，不過仍然小于采用DEC的10位冗余校驗位。此外，對于較短的碼字EDAC電路的邏輯深度要低一些。因此可以加快電路的編譯碼速度。

ISSI公司已經在其不同容量的抗輻射SRAM中采用分裂SEC的EDAC電路用了，如圖3所示，ISSI公司所設計的SRAM在讀取操作過程中，首先通過地址譯碼器找到需要讀出的24位字節（包括冗余校驗位），讀出兩個分裂后的（12,8）子碼，然后分別進入EDAC電路分別糾錯，最終將輸出的兩個8位信息向量組成一個16位的字節一并輸出。

圖3 ISSI 512K x 16 bit帶EDAC高速異步SRAM的譯碼流程圖Fig.3 Decoding flow diagramof 512K x 16 high-speedasynchronous SRAM with EDAC

5 結論

文中推導了其在單字節多位翻轉導致的失效狀態下，輸出具有0位錯，1位錯，2位錯和3位錯的概率分布。經過公式和計算機試驗所得到結果的比較，認為兩者基本一致。從分析中可以看出，對于較長的碼字，在EDAC系統失效時輸出3位錯的概率較大；而對于較短的碼字，輸出一般只有1位和2位錯。最后本文分析了一種將較長信息位分成相同長度然后分別采用SEC編譯碼的方案。這種方案相對于傳統的縮短漢明碼而言，增加了冗余校驗位，但是降低了失效概率以及輸出3 bit翻轉的概率；相對于能夠糾正兩個錯誤的DEC而言，具有較少的冗余校驗位。因此可以作為一種SEC和DEC之間的一種折中方案。

[1]M Y Hsiao.A class of optimal minimum odd-weight-column SEC-DED codes[J].IBM Journal of Research and Development,1970,14(4):395-401.

[2]Lin Shu,Costello D J.Error Control Coding[M].北京：機械工業出版社，2007.

[3]Gherman V,Evain S,Seymour N,et al.Generalized Parity-Check Matrices for SEC-DED Codes with Fixed Parity[C]//IEEE 17th International On-Line Testing Symposium.2011:198-201.

[4]Sánchez-Macián A,Reviriego P，Maestro JA.Hamming SECDAED and extended hamming SEC-DED-TAED codes through selective shortening and bit placement[J].IEEE Transactions on Device and Material Reliability,2012,99:1-3.

[5]Richter M,Oberlaenderz K,Goessel M.New linear SEC-DED codes with reduced triple error miscorrection probability[C]//14th IEEE International On-Line Testing Symposium,2008:37-42.

[6]Fujiwara T,Kasami T,Kitai A,et al.On the undetected error probability for shortened hamming codes[J].IEEE Transactions on Communications,1985,33(6):570-574.

[7]Leung-Yan-Cheong S K,Hellman M E.Concerning a Bound on Undetected Error Probability[C]//IEEE Transactions on Information Theory,1976:235-237.

[8]Hamada M.The burst weight distributions of maximum-hamming-distance-separable codes[J].IEEE Transactions on Information Theory,2001,47(1):404-406.

[9]Kasamit T.Optimum shortened cyclic codes for burst-error correction [J].IEEE Transactions on Information Theory,1963,9(2):105-109.

[10]Demidenko S,Ivanyukovich A,Makhist L.Analysis and Generation of Test Sequences Based on Hamming Code and its Modifications[C]//IEEE Instrumentation and Measurement Technology Conference,2006:229-234.

[11]Nicolaidis M.Soft Errors in Modern Electronic Systerms[M].Berlin:Springer,2011.

[12]Naseer R,Draper J.DEC ECC Design to Improve Memory Reliability in Sub-100nm Technologies[C]//15th IEEE International Conference on Digital Object Identifier,2008:586-589.