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

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

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

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

4、如果给定一组数据位中1的个数是偶数，那么奇校验位就置为1，使得总的1的个数是奇数。优势：算法简单，易于实现劣势：无法指明错误发生的位置，也无纠错能力。另外，若一串数据中出现偶数个bit位的错误，那么奇偶校验就无法检出。3.检验和（checksum）检验和(checksum)，在数据处理和数据通信领域中，用于校验目的地一组数据项的和。它通常是以十六进制为数制表示的形式。如果校验和的数值超过十六进制的FF,也就是255. 就要求其补码作为校验和。4.循环冗余检查（CRC）循环冗余检查是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的

5、正确性和完整性。5.散列函数（hash函数）传输或存储信息时，同时传输或存储原信息和其哈希值（算法事前约定）。在读取时，计算原信息的哈希值并和接收到的哈希值比较。实际上，检验和法和循环冗余检查法，甚至是奇偶校验位法都可以视作是特殊的散列函数法，但它们的散列冲突几率很高。设计优秀的散列函数可以尽可能避免散列冲突。优势：散列函数类型的纠错码原理都利于理解，其中奇偶校验、检验和与循环冗余检查实现上比较方便，但是带来了比较严重的散列冲突。精心设计一个散列冲突低，散列值变化幅度大的散列函数可以帮助我们避免散列冲突导致的误判，但是会带来实现难度的上升，并导致更多的性能开销。劣势：由于散列函数一般有单向性，

6、难以根据散列函数值计算输入值。因此这几种方法一般用于错误检查，难以定位错误具体位置。也无法用于纠错。关于错误检测算法的总结：常见的错误检测算法主要是考虑到减少性能开销和降低实现的复杂度。它们在数据存储的错误检查上效果非常显著。因此在生活中也有很多应用：例如，身份证上的校验码、数字证书与签名系统、下载时的MD5值等等。但是，数据存储不仅要求能检查出存储的数据是否出错，很多时候，我们还希望能够恢复已经出错的数据。因此，人们除了对算法的检查性能有要求以外，还希望算法有着定位错误位置、修正小错误的能力，这就需要我们研究纠错算法。常见的纠错方法重传、重读（后向纠错）通过接收方请求发送方重传出错的数据来恢

7、复数据的方法叫后向纠错。优势：后向纠错易于理解，并且当误码率低时开销比较小。劣势：后向纠错要求接收方与发送方可以即时通信请求重传。对于不方便通信的场合，或者是数据存储这种接收方和发送方时间上分离的场合无法应用。前向纠错编码前向纠错（英语：Forward error correction,缩写FEC）是一种在单向通信系统中控制传输错误的技术，通过连同数据发送额外的信息进行错误恢复，以降低误码率（bit error rate, BER）。优势：前向纠错在信道误码率较小时，可以只凭收到的信息还原出原值，无需联系发送方，这使它能应用于数据存储等场合。劣势：增大了开销，增加系统实现的复杂度。混合使用前向

8、纠错与后向纠错有的场合，发送方和接收方既便于联系又不存在严格的性能与复杂度限制，这时可以混合采用前向纠错与后向纠错技术，以便于利用两种方法的优势。比如在Internet上的数据传输和存储，前向纠错和后向纠错就混合使用。在TCP等协议的作用下，错误的数据可以被重传。在某些传输设备和应用层的部分应用中，也存在前向纠错编码的设计以保护数据。三、对纠错算法需求的分析和方案设计纠错算法需要满足的要求结合前面所了解的资料和课题的情况，我们对纠错算法有如下要求：1.具有检查出1bit错误和定位错误bit的基本功能。2.尽可能有一定健壮性，因为纠错码本身也是需要存储的数据，需要防止1bit错误出现在纠错码中导

9、致无法检查确定数据的正确性。3.尽可能使用数电上的常见逻辑，便利硬件实现。预期成果：我的毕设项目是一个软硬件结合项目。在项目的进行过程中，我需要对纠错编码的编解码原理进行学习和掌握，并且根据自己的理解进行算法的设计和实现。因此，我的成果将体现在两个方面：1.利用软件对算法进行模拟仿真，验证其可行性与性能。2.利用FPGA的设计软件，设计仿真编解码模块。检错纠错流程图：写入时： 检查与纠错时：开始计算ECC校验码，写入数据流中结束 开始提取原始信息，重算ECC。 原始ECC是否等于重 算值？是否原始数据无误计算错误bit位置，反转错误bit结束检查与定位错误bit的方案：现在的存储软硬件实现上，

10、我们很多时候使用的是二维的数据结构。因此，我们可以想到，我们可以按二维数据的行和列分别放置和计算校验码，这样根据行和列的校验码的变化，就能唯一确定发生了1bit错误的错误位。并且这样的设计便于理解，也容易进行软件和硬件上的实现。同时，这也有助于提高算法的健壮性，因为某一位信息位出错必然同时引起两方面校验码的改变，有利于防止校验码发生1bit错误时引起的麻烦。校验码的计算：计算机中使用二进制表达数据，对于二进制有种特殊算符为按位异或，它具有几个特殊的性质：1.异或运算的数学性质：可以被认为是不进位的加法。这可以保证变换前后数据的位数不变。2.异或运算的效果与奇偶校验等同。（易于理解）3.异或是种

11、基本数电逻辑。（易于实现）ECC编码的实现方法根据前述分析。我们有一种ECC的实现方案：每256字节原始数据生成3字节ECC校验数据，这三字节共24比特分成两部分：6比特的列校验和16比特的行校验，多余的两个比特置1。以列校验为例子，我们可以按下述算式生成6位的列校验码。：其中（+）代表异或运算P3=D7(+)D6(+)D5(+)D4P3=D3(+)D2(+)D1(+)D0P2=D7(+)D6(+)D3(+)D2P2=D5(+)D4(+)D1(+)D0P1=D7(+)D5(+)D3(+)D1P1=D6(+)D4(+)D2(+)D0容易看出，无论是哪一位发生错误，其对应的3个校验位必发生改变。在

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

13、且，它对纠错码的放置位置没有要求，可以进行集中化放置，便于理解，也便于管理。但是，它与我们前面提到的汉明码相比，对于ECC码本身出现1bit错误的健壮性变低。在这样的ECC编码实现中，一旦ECC编码本身出现1bit错误，算法就会混乱。但是集中化放置可以使得我们采取其他方式保护ECC码，例如，使用我们所了解的重复码技术。四、项目的软件原型实现对于我们的课题，由于matlab有很多现成的函数和功能可用，我们以matlab平台为例子进行编程。考虑到编码和解码需要复用，并且逻辑上也是分开的步骤，我们将其提取出来作为两个子函数进行编写，也便于硬件上分开实现。五、阶段性成果展示和分析借助教授的指导，结合教授提供的资料和我所查阅的资料，我实现了一个可以实现256字节ECC校验的matlab程序。该程序目前可以做到对任意256字节的数据进行ECC校验以防止1bit错误破坏数据。其计算时需要略大于原始数据量三倍大小的临时空间，但保存时只比原始数据量稍大。根据matlab的运行计时，对示例数据可以在0.08s左右完成一次编码和检错纠错循环。如图所示，我生成了一个共256项，每项8个字节的一串数据作为原始数据，计算出其ECC值，随后把其中一项（第19项）原值18改成50。（即00010010改成01010010）以此模拟发生的单bit错误。结果