数据存储中的错误检查和纠正算法设计

1、数据存储中的错误检查和纠正算法设计,00111129,学生：鄂元哲,指导老师：罗明,一、课题背景,?,数据存储的概念,数据存储是数据流在加工过程中产生的临时文件或加工过程中需要查找的信息。,数据以某种格式记录在计算机内部或外部存储介质上。,?,常见的存储介质,1.,硬盘：在平整的磁性表面存储和检索数据,2.,闪存：一般指电子式可清除程序化非易失存储器,3.,光盘：用激光扫描的记录和读出方式保存信息的一种介质,二、国内外研究方向,数据存储中的错误检查与纠正算法是计算机、通信、网络等方面的热点技术，从,上个世纪计算机发明、无线通信应用以来，人们就一直在纠错算法的理论和实现,等方向进行研究工作。并且

2、还极大促进了信息论、编码理论等相关学科的发展。,如今纠错算法中已经有了大量的成熟高效的算法和其软硬件实现方案，下面我们,将从错误检查技术、纠错技术、现有的部分实现方案等方面回顾前人的成果。同,时，通过总结现有方案的优劣来确定我们的思考方向和实现思路。,数据存储错误的特性,数据存储与传输中，有时会发生随机的写入错误。,由于介质的物理特性，在数据保存过程中，由于外界环境影响，可能造成少量数,据在存储过程中发生改变。但是在正常使用时，错误的发生率极低，且分布随机。,实践中数据一般按小区块存储。这样，在每个小区块中，一般只可能发生随机,1bit,错误。本课题主要研究随机,1bit,错误的错误检查与纠错

3、算法实现。,常见的错误检查方法,错误检查和纠错的原理：,数据存储中随机发生的错误就像是数字通信中遇到的随机噪声。根据香农定理，,只要为存储的数据增加冗余度，数学上就存在一种编码方式，可以无差错地传输,和存储信息。,在通信学中，这种增加冗余度来校验和纠错的技术叫做冗余校验。,1.,重复码,通过在发送时重复发送同样的比特流来进行错误检查与纠错。,优势：逻辑简单，有很好的纠错能力,劣势：带宽或者存储空间利用率极低，设想某一系统发送信息时重复三次比,特流，那么带宽利用率仅,1/3,。,2.,奇偶校验法,奇偶校验位是一个表示给定位数的二进制数中,1,的个数是奇数还是偶数的二进,制数。奇偶校验位有两种类型

4、：偶校验位与奇校验位。如果一组给定数据位,中,1,的个数是奇数，那么偶校验位就置为,1,，从而使得总的,1,的个数是偶数。如,果给定一组数据位中,1,的个数是偶数，那么奇校验位就置为,1,，使得总的,1,的个,数是奇数。,优势：算法简单，易于实现,劣势：无法指明错误发生的位置，也无纠错能力。另外，若一串数据中出现,偶数个,bit,位的错误，那么奇偶校验就无法检出。,3.,检验和（,checksum,）,检验和,(checksum),，在数据处理和数据通信领域中，用于校验目的地一组数,据项的和。它通常是以十六进制为数制表示的形式。如果校验和的数值超过,十六进制的,FF,也就是,255.,就要求其

5、补码作为校验和。,4.,循环冗余检查（,CRC,）,循环冗余检查是一种数据传输检错功能，对数据进行多项式计算，并将得到,的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确,性和完整性。,5.,散列函数（,hash,函数）,传输或存储信息时，同时传输或存储原信息和其哈希值（算法事前约定）。,在读取时，计算原信息的哈希值并和接收到的哈希值比较。实际上，检验和,法和循环冗余检查法，甚至是奇偶校验位法都可以视作是特殊的散列函数法，,但它们的散列冲突几率很高。设计优秀的散列函数可以尽可能避免散列冲突。,优势：散列函数类型的纠错码原理都利于理解，其中奇偶校验、检验和与循,环冗余检查实现上比

6、较方便，但是带来了比较严重的散列冲突。精心设计一,个散列冲突低，散列值变化幅度大的散列函数可以帮助我们避免散列冲突导,致的误判，但是会带来实现难度的上升，并导致更多的性能开销。,劣势：由于散列函数一般有单向性，难以根据散列函数值计算输入值。因此,这几种方法一般用于错误检查，难以定位错误具体位置。也无法用于纠错。,关于错误检测算法的总结：,常见的错误检测算法主要是考虑到减少性能开销和降低实现的复杂度。它们,在数据存储的错误检查上效果非常显著。因此在生活中也有很多应用：例如，,身份证上的校验码、数字证书与签名系统、下载时的,MD5,值等等。但是，数,据存储不仅要求能检查出存储的数据是否出错，很多时

7、候，我们还希望能够,恢复已经出错的数据。因此，人们除了对算法的检查性能有要求以外，还希,望算法有着定位错误位置、修正小错误的能力，这就需要我们研究纠错算法。,常见的纠错方法,?,重传、重读（后向纠错）,通过接收方请求发送方重传出错的数据来恢复数据的方法叫后向纠错。,优势：后向纠错易于理解，并且当误码率低时开销比较小。,劣势：后向纠错要求接收方与发送方可以即时通信请求重传。对于不方便通信的场合，,或者是数据存储这种接收方和发送方时间上分离的场合无法应用。,?,前向纠错编码,前向纠错（英语：,Forward error correction,缩写,FEC,）是一种在单向通信系,统中控制传输错误的技

8、术，通过连同数据发送额外的信息进行错误恢复，以,降低误码率（,bit error rate, BER,）。,优势：前向纠错在信道误码率较小时，可以只凭收到的信息还原出原值，无,需联系发送方，这使它能应用于数据存储等场合。,劣势：增大了开销，增加系统实现的复杂度。,?,混合使用前向纠错与后向纠错,有的场合，发送方和接收方既便于联系又不存在严格的性能与复杂度限制，,这时可以混合采用前向纠错与后向纠错技术，以便于利用两种方法的优势。,比如在,Internet,上的数据传输和存储，前向纠错和后向纠错就混合使用。在,TCP,等协议的作用下，错误的数据可以被重传。在某些传输设备和应用层的,部分应用中，也存

9、在前向纠错编码的设计以保护数据。,三、对纠错算法需求的分析和方案设计,纠错算法需要满足的要求,结合前面所了解的资料和课题的情况，我们对纠错算法有如下要求：,1.,具有检查出,1bit,错误和定位错误,bit,的基本功能。,2.,尽可能有一定健壮性，因为纠错码本身也是需要存储的数据，需要防止,1bit,错误出现在,纠错码中导致无法检查确定数据的正确性。,3.,尽可能使用数电上的常见逻辑，便利硬件实现。,预期成果：,我的毕设项目是一个软硬件结合项目。在项目的进行过程中，我需要对纠错编码,的编解码原理进行学习和掌握，并且根据自己的理解进行算法的设计和实现。因,此，我的成果将体现在两个方面：,1.,利

10、用软件对算法进行模拟仿真，验证其可行性与性能。,2.,利用,FPGA,的设计软件，设计仿真编解码模块。,检错纠错流程图：,写入时：,开始,是,计算,ECC,校验码，,写入数据流中,原始数据,无误,结束,开始,检查与纠错时：,提取原始信息，,重算,ECC,。,否,原始,ECC,是否等于重,算值？,计算错误,bit,位置，反转,错误,bit,结束,检查与定位错误,bit,的方案：,现在的存储软硬件实现上，我们很多时候使用的是二维的数据结构。因此，我们,可以想到，我们可以按二维数据的行和列分别放置和计算校验码，这样根据行和,列的校验码的变化，就能唯一确定发生了,1bit,错误的错误位。并且这样的设计

11、便,于理解，也容易进行软件和硬件上的实现。同时，这也有助于提高算法的健壮性，,因为某一位信息位出错必然同时引起两方面校验码的改变，有利于防止校验码发,生,1bit,错误时引起的麻烦。,校验码的计算：,计算机中使用二进制表达数据，对于二进制有种特殊算符为按位异或，它具有几,个特殊的性质：,1.,异或运算的数学性质：可以被认为是不进位的加法。这可以保证变换前后数据,的位数不变。,2.,异或运算的效果与奇偶校验等同。（易于理解）,3.,异或是种基本数电逻辑。（易于实现）,ECC,编码的实现方法,根据前述分析。我们有一种,ECC,的实现方案：,每,256,字节原始数据生成,3,字节,ECC,校验数据，

12、这三字节共,24,比特分成两部分：,6,比特的列校验和,16,比特的行校验，,多余的两个比特置,1,。,以列校验为例子，我们可以按下述算式生成,6,位的列校验码。：其中（,+,）代表异或运算,P3=D7(+)D6(+)D5(+)D4,P2=D7(+)D6(+)D3(+)D2,P1=D7(+)D5(+)D3(+)D1,P3=D3(+)D2(+)D1(+)D0,P2=D5(+)D4(+)D1(+)D0,P1=D6(+)D4(+)D2(+)D0,容易看出，无论是哪一位发生错误，其对应的,3,个校验位必发生改变。在此例,子中，假设,D5,发生错误，那么,P3,，,P2,P1,必然发生翻转。,如何解出错

13、误位呢？我们通过理论分析和实际测试可以知道，若发生了单,bit,错误，那当我们对原,ECC,值与变化后的,ECC,值按位异或后，每一对校验码,（比如,P3,和,P3,）必然不相等（一个为,0,，一个为,1,）。另外，容易看出，由于,编码时候的规律性，,5,恰好是二进制的,101,。于是我们很容易看出，我们将,P3P2P1,按顺序排列成一二进制数字。并且将异或后,P3P2P1,的值带入该数字，,得出的,101,就是出错列的列号。行号可以以此为例加以生成。,编码放置的位置,由前文所述的,ECC,编码的实现原理可以知道，这样编码出的,ECC,码可以很好地对,原始数据进行,1bit,错误的检错纠错。而

14、且，它对纠错码的放置位置没有要求，可,以进行集中化放置，便于理解，也便于管理。但是，它与我们前面提到的汉明码,相比，对于,ECC,码本身出现,1bit,错误的健壮性变低。在这样的,ECC,编码实现中，,一旦,ECC,编码本身出现,1bit,错误，算法就会混乱。但是集中化放置可以使得我们,采取其他方式保护,ECC,码，例如，使用我们所了解的重复码技术。,四、项目的软件原型实现,对于我们的课题，由于,matlab,有很多现成的函数和功能可用，我们以,matlab,平台,为例子进行编程。考虑到编码和解码需要复用，并且逻辑上也是分开的步骤，我,们将其提取出来作为两个子函数进行编写，也便于硬件上分开实现

15、。,五、阶段性成果展示和分析,借助教授的指导，结合教授提供的资料和我所查阅的资料，我实现了一个可以实,现,256,字节,ECC,校验的,matlab,程序。该程序目前可以做到对任意,256,字节的数据,进行,ECC,校验以防止,1bit,错误破坏数据。其计算时需要略大于原始数据量三倍大,小的临时空间，但保存时只比原始数据量稍大。根据,matlab,的运行计时，对示例,数据可以在,0.08s,左右完成一次编码和检错纠错循环。,如图所示，我生成了一个共,256,项，每项,8,个字节的一串数据作为原始数据，,计算出其,ECC,值，随后把其中一项（第,19,项）原值,18,改成,50,。（即,00010010,改成,01010010,）以此模拟发生的单,bit,错误。