《差错控制编码_7课件》由会员分享，可在线阅读，更多相关《差错控制编码_7课件（37页珍藏版）》请在金锄头文库上搜索。
1、第九章 差错控制编码,2019/4/19,2,基本内容,引言 纠错编码原理 常用简单编码 线性分组码 循环码,2019/4/19,3,9.1 引言,码间干扰可以用均衡的办法来纠正,但不可能很彻底；至于加性干扰则是不可避免的； 当误码不可避免时，可以考虑差错控制编码； 根据错码分布规律的不同，将信道分为三类：,2019/4/19,4,9.1 引言,差错控制方法： 检错重发(ARQ)；前向纠错(FEC)； 反馈校验法； 混合纠错(HEC)； 差错删除法； 差错控制编码：在信息码中加入监督码；以降低信息传输速率为代价来换取传输可靠性的提高。 多余度：增加的码元数目除以总码元数目；,2019/4/19
2、,5,9.2 纠错编码的基本原理,分组码：每组信息码附加若干监督码的编码集合。在分组码中，监督码元仅监督本码组中的信息码元。用(n，k)表示 。,码重：码组中非零码元的数目。 码距：两码组中对应码位上具有不同二进制码元的位数。,2019/4/19,6,最小码距的有关结论：,在一个码组内检测e个误码，要求最小码距,在一个码组内纠正t个误码，要求最小码距,在一个码组内纠正t个误码，同时检测e个误码(et)，要求最小码距,2019/4/19,7,差错编码的效果,假设随机信道发送0时的错误概率和发送1时的错误概率相等，均为p1，则在码长为N的码组中发生r个错误的概率为：,当n=7，p=0.001，有：
3、,2019/4/19,8,9.3 常用的简单编码,奇偶监督码： 偶校验： 奇校验：,特点：奇偶校验只能发现单个或奇数个错码，而不能检测出偶数个错码。所以检错能力不高，奇偶校验的最小码距dmin=2。,适应于检测随机错误。,2019/4/19,9,二维奇偶监督码（水平垂直奇偶监督位）：,特点：可能检测出偶数个错码。有些偶数错码不可能检测出，如构成矩形的4个错码。 适应于检测突发错码。,2019/4/19,10,恒比码： 定义：从某确定码长的码组中排选那些“1”和“0”的比例为恒定值的码组作为许用码组。 7中取3 5中取3 特点：能发现所有单个错误和奇数个错误。,正反码：是一种简单的能够纠正错误的
4、编码。其中的监督位数目=信息位数目。监督码元与信息码元相同或者相反，由信息码中“1”的个数而定。,2019/4/19,11,（1）当信息位中有奇数个“1”时，监督码为正码。 （2）当信息位中有偶数个“1”时，监督码为反码。,（1）信息位+监督位=合成码组（产生校验码组）。 （2）接收码组的信息位中有奇数个“1”，则合成码组=校验码组；接收码组的信息位中有偶数个“1”，则合成码组的反码=校验码组； （3）观察校验码组中“1”的个数，可知错码情况。,接收端译码方法：,2019/4/19,12,正反码举例,1100111001 正确 1000111001 左边第二位为错码 1100101001 监督
5、位中第一位为错码 1001111001 错码多于一个 特点：这种长度为10的正反码具有纠正一位错码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。,2019/4/19,13,9.4 线性分组码,定义：信息码元与监督码元由线性方程联系起来。,性质： （1）封闭性：任意两许用码组之和仍为一许用码组； （2）最小码距=非零码的最小重量。,一、简单线性分组码（奇偶监督码）,2019/4/19,14,监督码元的位数要求,关于校正子S,如果只有一位，则只能用来判断对或者错，无法纠正； 如果有两位校正子，则有四种组合，除了一种表示没有错误之外，还有三种可以表示以为错误的三个可能位置。 因此，假设码
6、长为n，监督位数为r，则可以纠正一位错码时，必须满足：,2019/4/19,15,二、（7，4）线性分组码（奇偶监督码）,2019/4/19,16,给定信息位，可直接按上式计算出监督位（P289表9-5）。根据监督位可判断错码情况。如：收到码组为0000011；因为s1s2s3=011，故a3位有错码。,（7，4）汉明码的最小码距d0=3，所以能纠正一位错码或检测两个错码。汉明码是一种高效码。,2019/4/19,17,三、监督矩阵,分组码的监督方程 矩阵形式,2019/4/19,18,由典型形式监督矩阵及信息码元很容易算出各监督码元。即用信息位的行矩阵乘Q矩阵得到监督位。,2019/4/19
7、,19,四、生成矩阵,2019/4/19,20,典型生成矩阵：具有IkQ形式的生成矩阵。 系统码：信息位不变，监督位附加于其后的纠错编码。,2019/4/19,21,G矩阵性质,与H矩阵类似，要求G矩阵的各行是线性无关的。 G矩阵的各行本身就是一个码组。因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余的码组。,2019/4/19,22,五、校正子,2019/4/19,23,线性码的性质,封闭性：任意一种线性码中的任意两个码组之和仍为这种码组之中的一个码组。 因此，两个码组之间的距离必是另一码组的重量。 线性码又称为群码。,2019/4/19,24,六、汉明码：(纠正单
8、个错误的线性分组码),特点： 码长： 最小码距：d=3 信息码位： 纠错能力：t=1 监督码位：r=n-k 给定r，即可构造出具体的汉明码(n，k)。,2019/4/19,25,9.5 循环码,一、循环码的特点：,（1）封闭性：任意两许用码组之和仍为一许用码组； （2）循环性：循环码中任意许用码组经循环移位后得到的码组仍为一许用码组。不论左移或右移，移位位数多少，其结果均为循环码组。,二、循环码的原理：,1 多项式按模运算,2019/4/19,26,注意：码多项式系数按模2运算，即只取0、1；模2运算中，加法代替减法。,结论：一个长为n的循环码，它必为按模 运算的一个余式。,2019/4/19
9、,27,2 循环码的生成矩阵,首先找到码生成多项式g(x)：g(x)是唯一一个(n-k)次多项式；g(x)的常数项不为零；g(x)是xn+1的一个因式。,2019/4/19,28,生成矩阵G的性质,这个时候的G往往不是典型的，但是可以通过线性变换化为典型的。 此时：,可见，所有码多项式T(x)都可被g（x）整除，而且任一次数不大于（k-1）的多项式乘以g（x）都是码多项式。,2019/4/19,29,3 如何寻找任意(n，k)循环码的生成多项式。,结论：生成多项式g(x)是xn+1的一个(n-k)次因式。,2019/4/19,30,三、循环码编、解码方法：,编码：,2019/4/19,31,译
10、码比编码复杂 译码三步 校正子s的计算 由s得到错误图样 纠正,发送码组 接收码组 误差码组 校正子只与 E 有关，译码的根本在于计算校正子,2019/4/19,32,校正子S的计算,生成多项式 g(x)去除接收码字B(x),2019/4/19,33,四、缩短循环码：,(n,k) (n-i, k-i) 如 (15,11) (12,8) 监督矩阵 Hi 是将原 H 的前 3 列 去掉 缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。,2019/4/19,34,BCH 码,定义: 一类能纠正多个随机错误的循环码。分为本原BCH码和非本原BCH码。,2019/4/19,35,纠正 3
11、个错误，码长为15的BCH码 解：n=15, m=5 查表9-8得， 2467 这是(15,5)码。,2019/4/19,36,表99中最重要的BCH码是(23,12)，称为格雷码，码间为7，能纠正3个错误。 生成多项式 在实际通信系统中，所要求的n、k并不是码表中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。,重要的BCH码 (23,12),2019/4/19,37,里德-索洛蒙码（RS）,RS码的生成多项式为：,RS码的应用： 第一，由于采用了q进制，所以它是多进制调制时的自然和方便的编码手段 第二，RS码也被应用在计算机存储系统中，以克服系统中存在的差错串。,
