一种基于海明码的FLASH文件系统的校验编码方法

黄莎莉,方 虹

(1.湖北城市建设职业技术学院,武汉 430072;2.华中师范大学图书馆,武汉 430079)

近年来,闪速存储器(FLASH)广泛应用于移动电子产品中,当FLASH存储器某个数据块的擦除次数超过了它允许擦除的最大值,将产生单个电路故障,造成的一位或者相关多位错误。常见文件系统所采用的CRC校验只能检错,不能纠错;海明码能发现数据中的2位错,或纠正1位数据错,满足不了大容量FLASH存储设备的校验纠错要求。为此,有研究人员通过对海明码增加1个校验位,实现了码距为4的扩展海明码编码方式,能发现2位错,并纠正1位错。

扩展海明码使用32位的码字,来存放26位的数据信息,其校验位为P1-P6,数据位为D1-D26,从高到低依次排列如表1所示:

表1 扩展海明码的位排列

扩展海明码的数据存贮效率很高,但文件系统在编码和解码时要在26位和32位间进行转换,转换的工作量较大;数据校验中用到了大量逻辑运算,对用软件实现数据校验工作的常见移动设备的存取效率有一定影响。另外,大容量的FLASH容易出现单个位错误,对于重要的数据来说,每32位只允许出错1位,安全性还有待提高。

鉴于这种情况,本文基于海明码,提出一种二次校验策略,并在此基础上提出二次校验海明码方式。与扩展海明码相比,该编码方式的编码和解码步骤简化,校验过程精简。

1 基于海明码的二次校验策略

对扩展海明码的分析可知,由于扩展海明码的长度为32位,而常见的海明码的长度为7位(4位数据位,3位校验位),在编/解码过程中需运用大量的逻辑运算,影响了读写效率。另外,由于扩展海明码长32位,虽然编码效率提高了,但出现2位错或者多位错的概率也增大了。在容易发生错误的大容量FLASH存储介质上,这种编码方式还不够理想。因此,新的海明编码策略中信息位应该缩短。

海明码每字节信息位所对应的校验位称为校验成本。传递相同的信息,编码中信息位缩短将使总校验位数增加,校验成本上升。对于大容量FLASH存储介质来说,适当增加校验位数,以存储空间来换编/解码时间和纠错精度是可行的。随着校验位增加,校验位出错的可能性也增大了,如果恢复单位错误的机会浪费在校验位上将得不偿失。因此本文提出二次校验概念,即把一组校验位也看成一组数据位,由一组特殊的校验位对其进行校验。一组特殊的校验位通常可以校验两组或更多组的校验位,理论上这种二次校验的方法能够纠正数据位和校验位都有单错的2位错,从而提高海明编码的纠错效果。

完整的二次校验流程为:

①用校验位和数据位进行校验运算,运算结果没错或者只有一个错,按照长码距海明码的方式处理,流程结束。当发现有2位错误时,进入步骤①;

②将步骤①中校验码看做数据位,将它和对应的校验位进行校验运算;

如结果没错,表明步骤①中的两个错都出在数据位,无法纠错,返回信息结束流程;

如1位错出在校验位,无法纠错,返回信息结束流程;

如1位错出在数据位(即步骤①的校验位),纠正错误,返回正确的校验码;

如2位错,如有下一次二次校验,重复步骤②,否则返回信息结束流程;

③用步骤②得到的正确校验码来二次校验步骤①中数据位,并纠正错误。

从完整的二次校验流程可知,当数据部分没有错误或只有1个错误时,无需进入二次校验流程,这样兼顾了二次校验策略的解码速度和纠错能力,是二次校验策略的优点。

2 二次校验海明码的结构及编码/解码算法

二次校验海明码长32位,低16位是数据部分,高16位是校验部分。数据部分内按8位平分两个数据段,校验组内从低到高位,分为2个校验A段和1个校验B段。每个校验A段占5位,负责校验数据部分中对应的8个数据位,校验B段占6位,其中参与校验的是低5位,最高位做解码标志位,校验B段负责校验本组内的两个校验段A。位排列如下表2。

表2 二次校验海明码的位排列

2.1 二次校验海明码的编码

①读取16位数据,为这两个字节生成校验段A1和A2;

②将A1和A2合并为10位的二进制数,为其生成校验段B;

③生成16位的校验部分,并将其加在高16位,完成编码。

④设数据段1中从高到低分别为D8-D1,校验段A1从高到低分别为P5-P1,那么数据段1的校验公式如下(偶校验):

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

⑥按照表2的顺序从高位到低位编成32位的二次校验海明码。

2.2 二次校验海明码的解码

①读取校验部分,将其解码并分成5位的校验段A1和校验段A2;

②用校验段A1解码数据段1;

③用校验段A 2解码数据段2;

④如步骤②或③正常解码,返回正确的16位数据;否则对16位的校验部分进行校验(校验段B的纠错标志位为1表示错误出在校验段A1)。设校验码段A1,校验码段A2从高到低的位编号为D10-D1,校验段B从高到低的位编号为P5-P1,则它的校验表达式为:

⑤根据校验表达式和出错校验位S的结果对三种情况(2个错误全在初次校验的数据位,单个错误在初次校验的校验位,2个错误都在初次校验的校验位)进行归纳:

I当F=0且S=0时,或者当F！=0且X为真时,2个错误全在初次校验的数据位,超过了二次校验海明码的纠错能力。

II当F！=0且X为假时,单个错误在初次校验的校验位。当错误状态X为假时,错误标志位S有校验偏差B,出错位实际是S-B位。S＞8表示第S-4位错;8＞S＞4表示第S-3位错;4＞S＞2表示第S-2位(第一位)错。找到出错位置之后,将其求反即可纠正位错误。如果错误位置在校验段A1,则纠错标志位置1。当数据段2出错时,可以通过读取纠错标志位信息来决定是否需要对校验段A2进行校验。然后返回纠正后的校验段。

III当F=0且S！=0,表示校验部分有两位数据错,超过了二次校验海明码的纠错能力。

⑥对校验部分的校验后返回的是纠正了的校验段,最后用这个校验段对对应的数据段进行二次校验,得到正确的数据位结果。

3 二次校验海明码和扩展海明码的比较

虽然二次校验海明码的信息位只能利用50%,与扩展海明码81.3%的利用率相差不少,但是在编/解码的运算和纠错精度方面,二次校验海明码都有较大的优势。表3和表4分别是用扩展海明码和二次校验海明码对100位信息位进行编码解码的比较结果。

表3 两种方法编码比较

表4 两种方法解码比较

4 结束语

本文针对FLASH存储器容易出现单个数据位错的常见问题,提出了基于海明码的二次校验编码方法,相比以往的扩展海明编码方法,该方法提高了编/解码的效率和纠错能力,有利于提高FLASH存储器的数据安全性并延长了FLASH存储的使用寿命。

[1]周立功,等.ARM 嵌入式系统基础教程[M].北京:北京航空航天大学出版社,2008.

[2]李 岩.基于S3C44BOX嵌入式uc Linux系统原理及应用[M].北京:清华大学出版社,2005.

[3]张 娟,张雪兰.扩展的海明码及其在FLASH/EEPROM中的应用[J].兵工自动化,2003,(3).