信息论与编码原理：第五章 循环码

《信息论与编码原理》系统地讲述了信息论与编码的基本理论，共11章，内容包括：信息的基本概念、信源及其信息量、信道及其容量、信息率失真函数、信源编码和信道编码定理、网络信息论以及信源编码和信道编码的理论与方法。这是循环码的内容，后续还会发布。

第五章 循环码

• 特性
  • 码集中码字具有循环移位的特性
  • 是一种特殊的线性分组码，也是目前研究最透彻的一类码，有很高的使用价值
  • 与线代有密切联系，使得我们可以通过数学工具来编码
  • 优点：可以使用简单的移位寄存器来实现
• 生成多项式
  • 
  • 其中x仅表示位置，在物理意义上仅为占位
  • 循环左移k位的话仅乘以x的k次方就行
  • 定理一
    • 
  • 定理二
    • 定理二(n，k）循环码的码多项式中存在且仅有一个非零的最低次多项式,该多项式称为生成多项式g(x)，其他所有许用码字均可以表示成c(x)=u(x )g(x)。
  • 定理三
    • 
  • 性质
    • 任意码多项式c（x）都是生成多项式g（x）的倍式
    • 生成多项式g(x)是的一个因式
  • 
• 校验多项式
  • 
  • 
  • 
  • 因为g(x)是(n-k)次多项式，以g(x)为生成多项式，则生成一个(n,k)循环码
  • 若以h(x)为生成多项式，则生成一个(n,n-k)循环码，这两个循环码互为对偶码
• 生成矩阵变换
  • 通过线性变换可以变换成系统码生成矩阵，即可用C=M*G得到所有码字
  • 编码步骤
    • 1、确定(n,k)循环码的生成多项式:将xn-1分解因式，从中选择一个r次的因子作为g(x)。
    • 2、直接编码方法:①根据信息K，由计算出它的监督位;由信息位＋监督位直接写出编码C。
    • 3、间接编码方法:由g(x)得到一个码字，循环移位得到k个码字;写出生成矩阵，通过线性变换得到系统码生成矩阵G;由生成方程C=K·G求出相应码字。
  • 注意：由此得不到全部的许用码字的编码，只有n个
  • 每组循环码的所有许用码字内部编码是有多套循环码字
• CRC
  • 多种标准
    • CRC-12
      • 传送6-bit字符串
    • CRC-16
      • 传送8-bit字符串
    • CRC-32
      • 应用于P2P的同步传输中
  • 特点
    • 检错能力强
    • 开销小
    • 易于实现
  • 
  • 检错能力
    • 检出所有奇数个错
    • 检出所有单比特和双比特的错
    • 检出所有小于等于校验码长度n-k的突发错误
    • 对于n-k+1位的突发错误，查出概率为
    • 对于多于n-k+1位的突发性错误，查出概率为
    • 结论：只要选择合适的冗余校验位，可以使漏检率减到任意小
  • 纠错能力
    • 拥有纠错但一般不使用，检出错误后要求重发
    • 循环冗余校验码编译过程通常采用硬件实现，因为除法运算易于用移位寄存器和模二加法器实现，可达到较高处理速度
    • 循环冗余码的产生和校验均有集成电路产品，发送端自动产生CRC码，接受端可自动校验，速度大大提高