差错控制编码

2016-10-26 09:39:06 | 人围观 | 评论:

差错控制编码的原理是：发送方对准备传输的数据进行抗干扰编码，即按某种算法附加上一定的冗余位，构成一个码字后再发送。接收方收到数据后进行校验，即检查信息位和附加的冗余位之间的关系，以检查传输过程中是否有差错发生。差错控制编码分检错码和纠错码两种，检错码是能自动发现差错的编码，纠错码是不仅能发现差错而且能自动纠正差错的编码。计算机网络中常用的差错控制编码是奇偶校验码、循环冗余码和海明校验码。
    1. 奇偶校验码
    奇偶校验码是一种最简单的检错码。其原理是：通过增加冗余位来使得码字中"1"的个数保持为奇数（奇校验）或偶数（偶校验）。例如，偶校验：11010100，11011011
    在实际使用时，奇偶校验可分为以下三种方式。
    (1) 垂直奇偶校验
    (2) 水平奇偶校验
    (3) 水平垂直奇偶校验
    2. 循环冗余码
    循环冗余码又称CRC码（Cyclic Redundancy Code），简称循环码。CRC码检错能力强，且容易实现，是目前最广泛的检错码编码方法之一。在计算机网络和磁盘数据存储中，CRC被广泛采用。
    CRC是一种检错码，其编码过程涉及二进制多项式和模2运算知识。如比特串B7B6B5B4B3B2B1B0的二进制多项式形式是B7*X⁷+ B6*X⁶+B5*X⁵⁷+B4*X⁴+ B3*X³+ B2*X²+ B1*X¹+ B0*X⁰+，若比特串取值为10101110，则该比特串可被表示成二进制多项式X⁷+X⁵+ X³+X²+ 1。
    二进制多项式的加减法运算以2为模，即加减时不进、错位，如同逻辑异或运算，乘除法可看成是多次加减法运算。
    采用CRC校验时，发送方和接收方事先约定一个生成多项式G(X)，并且G(X)的最高项和最低项的系数必须为1。
    CRC编码由两部分组成，如图2-35所示。10101110111信息串编码校验块

    发送端的CRC校验块编码步骤
    (1) 将要发送的二进制数据（k位比特序列），对应一个（k-1）阶多项式K(x)；再选取一个收发双方预先约定的r阶生成码多项式G(x)，即G(x)的最高次幂为r。
    (2) 在原数据比特串尾添加r个0，即，xrK(x)。
    (3) 进行模2除法xrK(x)/G(x)，得到商Q(x)，并求得余数R(x)。R(x)即为校验块。
    (4) 用R(x)替代xrK(x)最后的r个0（即xrK(x) - R(x)），得到待传送的CRC码多项式（数据位加校验位）T(x)。
    3、海明校验码
    首先介绍码距的概念。一个编码系统中任意两个合法编码之间不同的二进制位数叫这两个码字的码距，而整个编码系统中任意两个码字的最小码距就是该编码系统的码距。为了使一个系统能纠正一位差错，码距最小是3。最小距离为3时，或能纠正一位错，或能检测二位错，但不能同时纠正一位错并检测二位错。编码信息纠错和检错能力的提高需要进一步增大编码系统的码距。码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。
    海明校验码是由Richard Hamming于1950年提出，目前还被广泛采用的一种很有效的校验方法，是只要增加少数几个校验位，就能检测出二位同时出错、亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段，后者被称为自动纠错。它的实现原理，是在k个数据位之外加上r个校验位，从而形成一个k+r位的新的码字，使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中，当某一位出错后，就会引起相关的几个校验位的值发生变化，这不但可以发现出错，还能指出是哪一位出错,为进一步自动纠错提供了依据。
    海明不等式
    设N为校验码的位数，K是有效信息位，r是校验位（分成r组作奇偶校验，能产生r位检错信息）
    海明码应满足 N=K＋r≤2^r－1（海明不等式），若r=3 则N=K＋r≤7 所以K≤4

标签：

差错控制编码

相关内容推荐：