一種基于海明碼的PROM文件系統(tǒng)軟件校驗方法

孔璇++李斌

摘要：PROM存儲器內(nèi)部80-90%的故障是單個數(shù)據(jù)位錯誤。奇偶校驗碼只能檢錯不能糾錯，海明碼可以發(fā)現(xiàn)并糾正單個數(shù)據(jù)位錯，但對于軟件實現(xiàn)數(shù)據(jù)校驗工作的大容量PROM存儲器來說，計算和存儲的開銷過大，影響了存儲效率。該文提出一種利用奇偶校驗碼進行檢錯，然后利用海明碼進行糾錯的校驗糾錯方法，有效地降低了軟件校驗的運算量，并通過系統(tǒng)仿真，驗證了該方法的優(yōu)越性。

關(guān)鍵詞：PROM；海明碼；奇偶校驗碼；校驗

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）06-0078-04

A Software Checking Method of PROM File System Based on Hamming Code

KONG Xuan， LI Bin

（Xian Aeronautics Computing Technique Research Institute， AVIC， Xian 710065， China）

Abstract： 80%～90% errors in PROM are single-bit errors. Parity check code can detect the error but cannot correct that. Hamming code that can find out and correct one single-bit error is not applicable for checking the large-capacity PROM by software since the storage speed of PROM will be affected by the overhead of the computation and memorization. In this paper， an optimized checking method is proposed which utilizes parity check code on error detection and then uses Hamming code on correction. This method is proved to reduce the calculating overhead efficiently， the result of the system simulation is shown at the end of the paper.

Key words： PROM； Hamming Code； Parity Code； checking

隨著航空電子技術(shù)在軍事飛機應(yīng)用的進步和發(fā)展，航空電子系統(tǒng)的高度綜合化導(dǎo)致總線網(wǎng)絡(luò)專用芯片的集成度越來越高，對存儲器的容量要求也越來越高。在存儲器向大容量、小體積和低功耗發(fā)展的背景下，PROM器件得到了廣泛使用。由于需要存儲大量數(shù)據(jù)，存儲器陣列出現(xiàn)數(shù)據(jù)錯誤的概率也大大增加，當(dāng)PROM存儲器某個數(shù)據(jù)塊的擦除次數(shù)超過了它允許擦除的最大值，存儲器內(nèi)部將產(chǎn)生電路故障，造成數(shù)據(jù)位錯誤。為了提高產(chǎn)品的可靠性，本文提出一種基于海明碼的改進的校驗糾錯方法，在提高存儲效率和節(jié)省開銷的同時，糾正錯誤的數(shù)據(jù)位，延長PROM的使用壽命。

常見的文件系統(tǒng)編碼有奇偶校驗碼、循環(huán)冗余碼、海明碼等，奇偶校驗碼和循環(huán)冗余碼只能檢錯，不能糾錯，不能滿足PROM存儲器的校驗糾錯要求；海明碼具有發(fā)現(xiàn)2位錯或者糾正一位數(shù)據(jù)錯的能力[1]，但是由于每個存儲單元都需要保存一組與其對應(yīng)的糾錯碼，數(shù)據(jù)校驗過程中使用了大量的邏輯運算[2]，對于軟件實現(xiàn)數(shù)據(jù)校驗工作的大容量PROM存儲器來說，計算和存儲的開銷過大，影響了存儲效率。

考慮到PROM存儲器內(nèi)部80-90%的故障是單個數(shù)據(jù)位錯誤[3]，本文針對修復(fù)單個數(shù)據(jù)位故障，提出將奇偶校驗碼應(yīng)用于PROM文件系統(tǒng)的檢錯過程中，當(dāng)檢測到單個位錯誤后，再利用海明碼進行糾錯。這樣一來，改進了單獨使用海明碼的校驗糾錯方法，即只有當(dāng)檢測到存儲單元發(fā)生單個位錯的時候才使用海明碼進行糾正，提高了錯誤檢測效率，降低了軟件校驗的運算量及軟件運行時間。

本文首先介紹了海明碼的校驗原理，然后結(jié)合奇偶校驗碼的檢錯原理，介紹改進的海明碼校驗糾錯步驟，最后通過實際例子，對改進的糾錯方法進行分析，驗證該方法在運算和存儲開銷上的優(yōu)越性。

1 海明碼的糾錯原理

海明碼由Richard Hamming于1950年提出，它的實現(xiàn)原理是在數(shù)據(jù)中加入幾個校驗位，并把數(shù)據(jù)的每個二進制位分配在幾個奇偶校驗組中[4]。當(dāng)某一位出錯時，校驗結(jié)果就會發(fā)生變化，不同數(shù)據(jù)位上的錯誤會得出不同的校驗結(jié)果，從而判斷是否出錯并指出具體的出錯位置，最后通過對錯誤位取反（原來是1就變成0，原來是0就變成1）將其糾正。

1.1 海明碼校驗位數(shù)的確定

假設(shè)有效數(shù)據(jù)位數(shù)為N，校驗碼位數(shù)為r，由數(shù)據(jù)位和校驗位構(gòu)成的海明碼H就可分為r組，構(gòu)成2r中狀態(tài)，其中1中狀態(tài)表示正確，余下2r-1中狀態(tài)表示一位有效數(shù)據(jù)出錯或一位校驗碼出錯，共有N+r種情況，若能表示出所有一位錯誤的情況，則N和r應(yīng)滿足：2r≥N+1，取滿足不等式的最小值。有效數(shù)據(jù)位數(shù)N與校驗碼位數(shù)r的關(guān)系如表1所示。

1.2 海明碼校驗碼位置的確定

海明碼的校驗碼是分開插入到有效數(shù)據(jù)中的，規(guī)則如下：假設(shè)海明碼H的位數(shù)為m，即H=HmHm-1...H2H1，則各校驗位分布在位號為2的冪次方的位置上，記作P1，P2，P3，…，Pr，其余為數(shù)據(jù)位，數(shù)據(jù)位按原順序排列，記作P1，P2，P3，…，Pr。海明碼的每一位Hi都被校驗位P1，P2，P3，…，Pr中的一位或若干位所校驗，其規(guī)律是被校驗位的位號等于校驗位位號之和，以（12，8）海明碼為例，表2給出了每一位海明碼所對應(yīng)的校驗位。