检错纠错的有关概念和实现思路

检错纠错的有关概念和实现思路

　　数据在计算机系统内加工、存取和传送的过程中可能产生错误。为减少和避免这类错误，一方面是精心选择各种电路，改进生产工艺与测试手段，尽量提高计算机硬件本身的可靠性；另一方面是在数据编码上找出路，即采用带有某种特征能力的编码方法，通过少量的附加电路，使之能发现某些错误,甚至能准确地确定出错位置,进而提供自动纠正错误的能力。

　　数据校验码就是一种常用的带有发现某些错误、甚至带有一定自动改错能力的数据编码方法。它的实现原理，是在合法的数据编码之间，加进一些不允许出现的(非法的)编码，使合法数据编码出现某些错误时，就成为非法编码。这样,则可以通过检查编码的合法性来达到发现错误的目的。合理地设计编码规则，安排合法、不合法的编码数量，就可以得到发现错误的能力，甚至达到自动改正错误的目的。这里用到一个码距（最小码距）的概念。码距是指任意两个合法码之间至少有几个二进制位不相同，仅有一位不同，称其（最小码距）为1，例如用四位二进制表示16种状态，则16种编码都用到了，此时码距为1，就是说，任何一个编码状态的四位码中的一位或几位出错，都会变成另一个合法码，此时无检错能力。若用四个二进制位表示8种合法状态，就可以只用其中的8个编码来表示之，而把另8种编码作为非法编码，此时可使合法码的码距为2。一般说来，合理地增大编码的码距,就能提高发现错误的能力，但表示一定数量的合法码所使用的二进制位数要变多，增加了电子线路的复杂性和数据存储、数据传送的数量。在确定与使用数据校验码的时候，通常要考虑在不过多增加硬件开销的情况下，尽可能地发现较多的错误，甚至能自动改正某些最常出现的错误。常用的数据校验码是奇偶校验码、海明校验码、循环冗余校验码等。纠错编码是对检错编码的更进一步的发展和应用。

　　计算机内经常遇到的错误有两大类，随机错误和突发错误。前者指孤立出现的一个错误，后者指连续产生的一批（彼此之间可能有关联）错误。对它们处理的难度和复杂度会有很大不同，在我们的课程中基本不涉及对突发错误的检查与纠正问题，有兴趣者请自行查阅有关资料。对纠错编码的分类方案给在图2.1。


图2.1 纠错码的分类