差错控制的基本原理

    1.差错控制的原理
    纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，即码的检错和纠错能力是用信息量的冗余度来换取的。
    加入监督码越多，码的检错、纠错能力越强，但信息传输效率下降也越多。
    在纠错编码中将信息传输效率也称为编码效率，定义为
             
    2.汉明距离与检错和纠错能力的关系
    （1）几个概念
    码长：码组或码字中编码的总位数为码组的长度。
    码重：码组中非零码元的数目为码组的重量。
    例如“11010”的码长为5，码重为3。
    码距：两个等长码组中对应码位上具有不同二进制码的数目称为码距。
    例如：码组1 11010
    码组2 01101
    码距：d₀=4
    汉明距离：在一种编码中，任意两个许用码组间距离的最小值，称为这一编码的汉明距离，以d_min表示。
    （2）汉明距离与检错和纠错能力的关系
    a) 为了检测e位错码，要求最小码距
         
    b) 为了检测t位错码，要求最小码距
         
    c) 为了纠正t位错码，同时检测e(e>t) 个错码，要求最小码距
         
    显然，要想纠错和检测，就必须增加码距，只有保证最小汉明距离符合上面三个公式的要求，才能具有检测或纠错能力。如何保证满足要求呢？一般方法是：按照某种规律对原来的码组（信息码组）添加一些新的码元，这些码元称为“监督码元”。作用是监督该码组在传输过程中是否发生错误，以便检错或纠错。添加监督码元的方法不同，就形成了不同的编码方法。
    3.纠错编码的分类
    (1)按码组的功能分，有检错码和纠错码两类。
    一般认为，能在译码器中发现错误的，称为检错码。如在译码器中不仅能发现错误，又能确定错码位置（即能自动进行纠错）的，称为纠错码。
    (2)按码组中监督码元与信息码元之间的关系分，有线性码和非线性码两类。
    线性码是指监督码与信息码之间呈线性关系，可用一组线性代数方程联系起来；
    非线性码值得是监督码元与信息码元之间是非线性关系。
    (3)按照信息码元与监督码元的约束关系，又可分为分组码和卷积码两类。
    分组码是将 个信息码元划分为一组，然后由这k个码元按照一定的规则产生r个监督码元，从而组成长度为n=k+r 的码组。在分组码中，监督码元仅监督本码组中的码元，或者说监督码元仅与本码组的信息码元有关。分组码一般用(n,k) 表示，结构如图所示，图中前面 k位为信息位，后面附加r个监督位。
        
             图 分组码的结构
    在卷积码中，每组的监督码元不但与本组的信息码元有关，而且还与前面若干组信息码元有关，即不是分组监督，而是每个监督码元对它的前后码元都实行监督，前后相连，因此有时也称连环码。
    (4)按照信息码元在编码前后是否保持原来的形式不变，可划分为系统码和非系统码。
在差错控制编码中，通常信息码元和监督码元在分组内有确定的位置；而非系统码中信息码元则改变了原来的信号形式。
    (5)按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码。
    (6)按照每个码元取值来分，可分为二进制码与多进制码。