何秉姣，劉 科

(中南民族大學 計算機科學學院，武漢 430074)

數(shù)字系統(tǒng)中的數(shù)據在讀寫操作中出現(xiàn)差錯是不可避免的，采用數(shù)據校驗碼檢查和糾錯可以減少或避免差錯.海明校驗碼是目前被廣泛采用的一種很有效的校驗方法，它是能查錯、糾錯的線性分組碼[1，2].通用的半導體存儲器主要采用SEC-DED海明校驗碼(簡稱SEC-DED校驗碼或SEC-DED碼)進行數(shù)據校驗，它具有發(fā)現(xiàn)2位錯和糾正一位錯的能力.用硬件實現(xiàn)SEC-DED碼的速度更快、更可靠.

FPGA深亞米微米的制造工藝實現(xiàn)了芯片集成成千上萬的查找表和觸發(fā)器，它的容量足以滿足普通系統(tǒng)開發(fā)的需要.另外FPGA具有設計周期短、調試方便、開發(fā)費用低、風險小、與CMOS、TTL電平兼容等特點，使得FPGA芯片在工程項目中得到廣泛應用[3-5].

1 SEC-DED海明校驗碼算法研究

海明碼的基本算法就是將有效數(shù)據按某種規(guī)律分成若干組.每組安排1個校驗位進行奇偶校驗.在1個數(shù)據組中加入幾個校驗位，增大數(shù)據代碼間的碼距，當某一位發(fā)生變化時會引起校驗結果發(fā)生變化，不同數(shù)位上的錯誤會得出不同的校驗結果，從而實現(xiàn)查錯和糾錯.

1.1 SEC-DED校驗位位數(shù)的確定

設有效數(shù)據為n位，校驗位為k位，分成k組做奇偶校驗，這樣能產生k位檢錯信息.k位信息就構成1個指誤字G=GkGk-1…G2G1，可構成2k種狀態(tài)，其中1種狀態(tài)表示無誤，余下2k-1種表示或1位有效數(shù)據位出錯，或校驗位中有1位出錯.因此共有1+k+n種情況，所以要對1位錯的所有結果進行正確表示，則k和n滿足如下關系：1+k+n≤2k.

故當有效數(shù)據位數(shù)有8位時，校驗位至少要4位，一般表示為(12,8)形式.(12,8)海明碼最多可以表示16種狀態(tài)，而單個位出錯情況最多只有12種可能，加上無錯的情況，一共13種.所以16種狀態(tài)表示13種情況足夠.這種碼能檢查并糾正1位錯，或者能發(fā)現(xiàn)2位出錯，稱為單糾錯碼(SEC).SEC-DED海明校驗碼在SEC基礎上增加1位校驗碼，即(13,5),n=8，k=5，能發(fā)現(xiàn)2位出錯，并能檢查和糾正1位錯.

1.2 SEC-DED校驗位值確定

若海明碼的最高位為m，最低位為1，即H=HmHm-1…H2H1.海明碼編碼規(guī)則：位號數(shù)(1,2,3，…，m)為2的冪次方值的那些有效位(即1,2,4，…，2k-1位)，作為奇偶校驗位，并記作P1，P2，P3，…，Pk，余下各位則為有效數(shù)據位.校驗位與有效數(shù)據位之和為m，可令有效數(shù)據M=Mm-kMm-k-1…M2M1.SEC(12,8)相應的海明碼如表1所示.

表1 SEC(12,8)海明碼

其中每1位Hi都被P1，P2，P3，…，Pk中的1位或若干位所校驗.例如H6被P2和P4所校驗，H9被P1和P8所校驗.其規(guī)律：第i位由校驗位位號之和等于i的那些校驗位所校驗.由此可得SEC海明碼每位所占的校驗位，如表2所示.

表2 SEC海明碼每位所占的校驗位

從表2可看到某一位海明碼是由哪幾位校驗位所校驗.反過來，每個校驗位，校驗著它以后的一些確定位置上的海明碼，包括它本身.例如P1校驗著海明碼中的第1、3、5、7、9、11位.歸納起來，SEC每個校驗位所校驗的數(shù)位如表3所示.

表3 SEC中每個校驗位所校驗的數(shù)位

綜合起來，可以得到指誤字與出錯情況的對應關系，如表4所示.

表4 SEC碼指誤字與出錯情況對應關系

表4對12位海明碼字分成了4組，若某組中G的1位發(fā)生錯誤，那么該組對應的那些位就發(fā)生變化，可以根據該組對應的指誤位Gi的值是否為1，來判斷奇偶性是否發(fā)生了變化，從而確定該組中是否發(fā)生了1位錯誤.從表4可以看出，每一個有效數(shù)據位至少參與兩組奇偶校驗位的生成，例如M3與第2組(P2)和第3組(P3)有關.

分組后，就可對每組采用相應的奇(偶)校驗，得到相應的校驗位.SEC海明碼采用偶校驗，校驗位與有效數(shù)據位之間關系如下：

(1)

SEC海明碼中，如果2個數(shù)據有1位不同，那么由于該位至少要參與2組校驗位的生成，因而至少引起2個校驗位的不同，再加上數(shù)據位本身1位的不同，所以碼距為3.碼距為3的海明碼具有發(fā)現(xiàn)2位出錯，或者具有對單個錯誤定位和糾錯的功能.要想同時具有發(fā)現(xiàn)2位錯誤和糾正1位錯的能力，碼距需擴大到4，在SEC基礎上，增加1位校驗位P5，將P5排列在碼字的最前面，即H=P5M8M7M6M5P4M4M3M2P3M1P2P1，并使得有效數(shù)據中的每1位都參與3個校驗位的生成，從方程組(1)可看出，除了M4和M7外，其余都只參與了2個校驗位的生成.因此P5可按下式求出：

P5=M8⊕M6⊕M5⊕M3⊕M2⊕M1.

(2)

求SEC-DED校驗位值的公式由方程組(1)和(2)式組合求得：

(3)

這樣當任意1個數(shù)據位發(fā)生錯誤，必然引起3個校驗位發(fā)生變化，所以碼距為4.

1.3 SEC-DED校驗方程及出錯定位與糾正

引入P5后，指誤字G也增加1位，即G=G5G4G3G2G1，根據表4得到方程組(4)，可求出G中各位的值.

(4)

根據G5G4G3G2G1的取值情況，就可按照如下規(guī)則發(fā)現(xiàn)2位錯并糾正1位錯.

(1) 當G5,G4,G3,G2,G1全為0時，表明無錯.

(2) 當G5,G4,G3,G2,G1中僅1位不為0 時，表明由G指定位置上的那個Pi出錯，或是在Hi中有3位同時出錯，但后面這種情況可能性非常小，所以一般認為發(fā)生了前一種情況.

(3) 當G5,G4,G3,G2,G1中有2位不為0時，表明Hi中有2位同時出錯，此時只能發(fā)現(xiàn)這種錯誤，但無法確定哪兩位出錯.

(4) 當G5,G4,G3,G2,G1中有3位不為0時，表明由1個Mi發(fā)生了錯誤，或是3個Pi同時錯誤，但后面這種情況可能性非常小，所以一般認為發(fā)生了前一種情況.此時，出錯位置由G4G3G2G1的數(shù)值確定.

(5) 當G5,G4,G3,G2,G1中有4位或5位不為0時，表明出錯情況嚴重，系統(tǒng)可能出現(xiàn)故障，應檢查系統(tǒng)硬件的正確性.

2 SEC-DED海明校驗碼FPGA的實現(xiàn)

基于FPGA的SEC-DED海明校驗碼實現(xiàn)系統(tǒng)包括編碼器和譯碼器兩部分，如圖1所示.

圖1 SEC-DED海明校驗碼編譯碼框圖

結合案例解釋編碼器和譯碼器的功能.在控制電路的控制下，發(fā)送端發(fā)送8位M=11001011，據方程組(3)由編碼器生成P=10110，則H=1110001011110，存入存儲器.當讀出該數(shù)據時，據方程組(4)由譯碼器生成G.如果無錯，G=00000，否則有錯.如讀出數(shù)據H′=1100001011110，其中M′=10001011，P′=10110，則G=01011，由此定位第11位出錯，并由糾正電路將其取反即可糾正.其它錯誤予以報警處理.下面給出基于Multisim 11.0的SEC-DED海明校驗碼編碼器譯碼器的FPGA實現(xiàn)[6-9].

2.1 SEC-DED海明校驗碼編碼器設計

基于方程組(3)在Multisim 11.0的平臺下設計SEC-DED海明校驗碼編碼電路.電路主要由5個多輸入的異或門組成，將8位有效數(shù)據M，按方程組(3)連接構成.8位有效數(shù)據M，經過編碼得到5位校驗碼P，合成海明碼H存入存儲器，其實驗結果如圖2 所示.

圖2給出了字發(fā)生器模擬發(fā)送4組M，經過編碼得到4組P，用邏輯分析儀仿真時序關系.當M=11001011時，邏輯分析儀的140 ms后1個周期內P=10110，當M=01101100時，邏輯分析儀中150 ms后的P=00010.與方程組(3)所求值相符.

圖2 SEC-DED編碼時序仿真

2.2 SEC-DED海明校驗碼譯碼器設計

(1) 指誤碼G產生電路.SEC-DED海明校驗碼譯碼器分指誤碼電路和糾錯電路.基于方程組(4)在Multisim 11.0的平臺下設計SEC-DED海明校驗碼譯碼電路.電路同樣由5個多輸入異或門組成，但結構與編碼器電路不同.由字發(fā)生器XWG1模擬從存儲器讀出13位SEC-DED海明碼H，經過譯碼得到5位指誤碼G，其實驗結果如圖3所示.

圖3 SEC-DED譯碼時序仿真

圖3給出了XWG1模擬發(fā)送5組正誤對比H′，經過譯碼得到5組G，用邏輯分析儀XLA1仿真時序關系.如XWG1中當H′=H時，XLA1的310 ms后1個周期內G=00000，表示無誤.當H=1110001011010時，XLA1中350 ms后的G=10011，表明H3出錯，再用糾錯電路取反即可.與方程組(4)所求值相符.

(2) 糾錯電路.根據邏輯量同或運算法則：HΘ0=H的非，HΘ1=H.將H′中M′與G對應的8種(如表2)有效情況進行同或運算，即可得到正確的M.其驗證結果如圖4所示.

圖4 SEC-DED碼指誤字時序仿真

圖4清楚給出Mi的8種1位出錯都可糾正，其中隱含當M′=M時，無誤情況.

3 結語

本文提出了基于FPGA實現(xiàn)SEC-DED海明校驗碼的硬件實現(xiàn)方案，基于Multisim 11.0軟件將編碼、譯碼和糾錯3部分整合成一個系統(tǒng)，經過仿真、驗證，對確定的FPGA編譯配置后，該系統(tǒng)占用資源少，校驗可靠、高速.該系統(tǒng)自成一體，用戶只需對接口進行操作.因此，它即可獨立使用，亦可配合其它系統(tǒng)作為其校驗模塊使用.

[1]Robert H M.糾錯編碼的藝術[M].2版.張立軍,譯.北京:北京交通大學出版社，2007:8-30.

[2]Whitman M E,Mattord H J.信息安全原理[M].北京：清華大學出版社,2003.

[3]潘 松，黃繼業(yè).EDA技術與VHDL[M].3版.北京：清華大學出版社，2010:182-210.

[4]呂志鵬.16位微處理器在FPGA上的設計與原理實現(xiàn)[D].北京：清華大學，2004.

[5]常海天,胡 鑒.基于FPGA的CRC并行算法研究與實現(xiàn)[J].微處理機，2010(2)：45-48.

[6]王冠華.Multisim 11電路設計及應用[M].北京：國防工業(yè)出版社，2010:140-159.

[7]Davide P,Scott T.Practical FPGA programming in C[M].Boston:Prentice Hall PTR，2007:45-60.

[8]王文劍，熊永中，唐良義.基于ISE和Modelsim的漢明碼設計[J].自動化技術與應用，2010,29(3)：54-57.[9]王習東，陳重江，陳志勇.基于FPGA的線陣CCD驅動電路設計[J].三峽大學學報：自然科學版，2010(3)：77-79.