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

黃莎莉,方 虹

(1.湖北城市建設(shè)職業(yè)技術(shù)學院,武漢 430072;2.華中師范大學圖書館,武漢 430079)

近年來,閃速存儲器(FLASH)廣泛應(yīng)用于移動電子產(chǎn)品中,當FLASH存儲器某個數(shù)據(jù)塊的擦除次數(shù)超過了它允許擦除的最大值,將產(chǎn)生單個電路故障,造成的一位或者相關(guān)多位錯誤。常見文件系統(tǒng)所采用的CRC校驗只能檢錯,不能糾錯;海明碼能發(fā)現(xiàn)數(shù)據(jù)中的2位錯,或糾正1位數(shù)據(jù)錯,滿足不了大容量FLASH存儲設(shè)備的校驗糾錯要求。為此,有研究人員通過對海明碼增加1個校驗位,實現(xiàn)了碼距為4的擴展海明碼編碼方式,能發(fā)現(xiàn)2位錯,并糾正1位錯。

擴展海明碼使用32位的碼字,來存放26位的數(shù)據(jù)信息,其校驗位為P1-P6,數(shù)據(jù)位為D1-D26,從高到低依次排列如表1所示:

表1 擴展海明碼的位排列

擴展海明碼的數(shù)據(jù)存貯效率很高,但文件系統(tǒng)在編碼和解碼時要在26位和32位間進行轉(zhuǎn)換,轉(zhuǎn)換的工作量較大;數(shù)據(jù)校驗中用到了大量邏輯運算,對用軟件實現(xiàn)數(shù)據(jù)校驗工作的常見移動設(shè)備的存取效率有一定影響。另外,大容量的FLASH容易出現(xiàn)單個位錯誤,對于重要的數(shù)據(jù)來說,每32位只允許出錯1位,安全性還有待提高。

鑒于這種情況,本文基于海明碼,提出一種二次校驗策略,并在此基礎(chǔ)上提出二次校驗海明碼方式。與擴展海明碼相比,該編碼方式的編碼和解碼步驟簡化,校驗過程精簡。

1 基于海明碼的二次校驗策略

對擴展海明碼的分析可知,由于擴展海明碼的長度為32位,而常見的海明碼的長度為7位(4位數(shù)據(jù)位,3位校驗位),在編/解碼過程中需運用大量的邏輯運算,影響了讀寫效率。另外,由于擴展海明碼長32位,雖然編碼效率提高了,但出現(xiàn)2位錯或者多位錯的概率也增大了。在容易發(fā)生錯誤的大容量FLASH存儲介質(zhì)上,這種編碼方式還不夠理想。因此,新的海明編碼策略中信息位應(yīng)該縮短。

海明碼每字節(jié)信息位所對應(yīng)的校驗位稱為校驗成本。傳遞相同的信息,編碼中信息位縮短將使總校驗位數(shù)增加,校驗成本上升。對于大容量FLASH存儲介質(zhì)來說,適當增加校驗位數(shù),以存儲空間來換編/解碼時間和糾錯精度是可行的。隨著校驗位增加,校驗位出錯的可能性也增大了,如果恢復單位錯誤的機會浪費在校驗位上將得不償失。因此本文提出二次校驗概念,即把一組校驗位也看成一組數(shù)據(jù)位,由一組特殊的校驗位對其進行校驗。一組特殊的校驗位通?？梢孕ｒ瀮山M或更多組的校驗位,理論上這種二次校驗的方法能夠糾正數(shù)據(jù)位和校驗位都有單錯的2位錯,從而提高海明編碼的糾錯效果。

完整的二次校驗流程為:

①用校驗位和數(shù)據(jù)位進行校驗運算,運算結(jié)果沒錯或者只有一個錯,按照長碼距海明碼的方式處理,流程結(jié)束。當發(fā)現(xiàn)有2位錯誤時,進入步驟①;

②將步驟①中校驗碼看做數(shù)據(jù)位,將它和對應(yīng)的校驗位進行校驗運算;

如結(jié)果沒錯,表明步驟①中的兩個錯都出在數(shù)據(jù)位,無法糾錯,返回信息結(jié)束流程;

如1位錯出在校驗位,無法糾錯,返回信息結(jié)束流程;

如1位錯出在數(shù)據(jù)位(即步驟①的校驗位),糾正錯誤,返回正確的校驗碼;

如2位錯,如有下一次二次校驗,重復步驟②,否則返回信息結(jié)束流程;

③用步驟②得到的正確校驗碼來二次校驗步驟①中數(shù)據(jù)位,并糾正錯誤。

從完整的二次校驗流程可知,當數(shù)據(jù)部分沒有錯誤或只有1個錯誤時,無需進入二次校驗流程,這樣兼顧了二次校驗策略的解碼速度和糾錯能力,是二次校驗策略的優(yōu)點。

2 二次校驗海明碼的結(jié)構(gòu)及編碼/解碼算法

二次校驗海明碼長32位,低16位是數(shù)據(jù)部分,高16位是校驗部分。數(shù)據(jù)部分內(nèi)按8位平分兩個數(shù)據(jù)段,校驗組內(nèi)從低到高位,分為2個校驗A段和1個校驗B段。每個校驗A段占5位,負責校驗數(shù)據(jù)部分中對應(yīng)的8個數(shù)據(jù)位,校驗B段占6位,其中參與校驗的是低5位,最高位做解碼標志位,校驗B段負責校驗本組內(nèi)的兩個校驗段A。位排列如下表2。

表2 二次校驗海明碼的位排列

2.1 二次校驗海明碼的編碼

①讀取16位數(shù)據(jù),為這兩個字節(jié)生成校驗段A1和A2;

②將A1和A2合并為10位的二進制數(shù),為其生成校驗段B;

③生成16位的校驗部分,并將其加在高16位,完成編碼。

④設(shè)數(shù)據(jù)段1中從高到低分別為D8-D1,校驗段A1從高到低分別為P5-P1,那么數(shù)據(jù)段1的校驗公式如下(偶校驗):

⑤校驗段A2和校驗段B的生成和校驗段A1的生成類似,在此省略。

⑥按照表2的順序從高位到低位編成32位的二次校驗海明碼。

2.2 二次校驗海明碼的解碼

①讀取校驗部分,將其解碼并分成5位的校驗段A1和校驗段A2;

②用校驗段A1解碼數(shù)據(jù)段1;

③用校驗段A 2解碼數(shù)據(jù)段2;

④如步驟②或③正常解碼,返回正確的16位數(shù)據(jù);否則對16位的校驗部分進行校驗(校驗段B的糾錯標志位為1表示錯誤出在校驗段A1)。設(shè)校驗碼段A1,校驗碼段A2從高到低的位編號為D10-D1,校驗段B從高到低的位編號為P5-P1,則它的校驗表達式為:

⑤根據(jù)校驗表達式和出錯校驗位S的結(jié)果對三種情況(2個錯誤全在初次校驗的數(shù)據(jù)位,單個錯誤在初次校驗的校驗位,2個錯誤都在初次校驗的校驗位)進行歸納:

I當F=0且S=0時,或者當F！=0且X為真時,2個錯誤全在初次校驗的數(shù)據(jù)位,超過了二次校驗海明碼的糾錯能力。

II當F！=0且X為假時,單個錯誤在初次校驗的校驗位。當錯誤狀態(tài)X為假時,錯誤標志位S有校驗偏差B,出錯位實際是S-B位。S＞8表示第S-4位錯;8＞S＞4表示第S-3位錯;4＞S＞2表示第S-2位(第一位)錯。找到出錯位置之后,將其求反即可糾正位錯誤。如果錯誤位置在校驗段A1,則糾錯標志位置1。當數(shù)據(jù)段2出錯時,可以通過讀取糾錯標志位信息來決定是否需要對校驗段A2進行校驗。然后返回糾正后的校驗段。

III當F=0且S！=0,表示校驗部分有兩位數(shù)據(jù)錯,超過了二次校驗海明碼的糾錯能力。

⑥對校驗部分的校驗后返回的是糾正了的校驗段,最后用這個校驗段對對應(yīng)的數(shù)據(jù)段進行二次校驗,得到正確的數(shù)據(jù)位結(jié)果。

3 二次校驗海明碼和擴展海明碼的比較

雖然二次校驗海明碼的信息位只能利用50%,與擴展海明碼81.3%的利用率相差不少,但是在編/解碼的運算和糾錯精度方面,二次校驗海明碼都有較大的優(yōu)勢。表3和表4分別是用擴展海明碼和二次校驗海明碼對100位信息位進行編碼解碼的比較結(jié)果。

表3 兩種方法編碼比較

表4 兩種方法解碼比較

4 結(jié)束語

本文針對FLASH存儲器容易出現(xiàn)單個數(shù)據(jù)位錯的常見問題,提出了基于海明碼的二次校驗編碼方法,相比以往的擴展海明編碼方法,該方法提高了編/解碼的效率和糾錯能力,有利于提高FLASH存儲器的數(shù)據(jù)安全性并延長了FLASH存儲的使用壽命。

[1]周立功,等.ARM 嵌入式系統(tǒng)基礎(chǔ)教程[M].北京:北京航空航天大學出版社,2008.

[2]李 巖.基于S3C44BOX嵌入式uc Linux系統(tǒng)原理及應(yīng)用[M].北京:清華大學出版社,2005.

[3]張 娟,張雪蘭.擴展的海明碼及其在FLASH/EEPROM中的應(yīng)用[J].兵工自動化,2003,(3).