《东北大学-通信原理7课件》由会员分享，可在线阅读，更多相关《东北大学-通信原理7课件（48页珍藏版）》请在金锄头文库上搜索。
1、,7.1 引言 7.2 纠错编码的基本原理 7.3 常用的简单编码 7.4 线性分组码 7.5 循环码,7 差错控制编码,7.1 引言,1) 差错的产生,2) 差错控制方法,噪声与干扰,检错重发法：双向信道工作。接收信息方具有检错能力，收到信息无误，回发肯定应答；有误则不发应答或发否定应答。,前向纠错法：单向信道工作。接收信息方具有纠错能力，发现收到信息有误时，确定误码的位置并按规则予以纠正。,前向纠错法：双向信道工作。接收信息方简单地将收到信息回传给发送方，由发送方判断前次发送是否无误。,7.1 引言,3) 检错重发(ARQ)系统, ARQ系统主要优点: 1. 只需少量多余码元； 2. 适应
2、不同差错特性； 3. 检错方法简单。, ARQ系统主要缺点: 1. 需要双向信道； 2. 出错率高时，重发降低信道效率； 3. 信息传输实时性差。,7.1 引言,4) 差错控制编码,在信息码元序列中加入一定数目的监督码元, 差错控制编码的检纠错能力, 差错控制编码的编码效率,一般说来，差错控制编码的检纠错能力取决于： 在信息码元序列中加入的监督码元的多少。对于一定长度的信息码元序列,加入的监督码元越多，检纠错能力越强。 不同的编码规则与方法。,在一定长度信息码元序列中加入监督码元的数目越多, 差错控制编码的编码效率越低。如信息码长为k，监督码长为r,则编码效率为k/(k+r)=k/n。,7.2
3、 纠错编码的基本原理,为每组信息码后附加若干个监督位构成的码组集合, 称为分组码。分组码用符号(n,k)表示, k是信息位的数目, n是码组总长度, n-k=r是监督位数目。,7.2 纠错编码的基本原理,1) 码重与码距概念, 一条码组中 “1” 的个数称为该码组的码重。 两码组中不同位的数目称为该两码组的码距。,2) 最小码重与最小码距, 某码组集合中含 “1” 个数最少的码组的码重, 称该码组集合的最小码重。 某码组集合中不同位数最少的两码组的码距, 称该码组集合的最小码距。,码组集合 1001001 0011011 1011100 0111011 0100011 1000100,码重 w
4、=3 w=4 w=4 w=5 w=3 w=2,码重与码距概念举例,7.2 纠错编码的基本原理,3) 码距(汉明Hamming距离)概念,最小码距d0 衡量差错控制编码系统检错及纠错能力决定性参数,7.2 纠错编码的基本原理,4) 最小码距d0与检错纠错能力关系,（1）只检模式 为检测 e 个误码，要求最小码距 d0 e + 1,（2）只纠模式 为纠正 t 个误码，要求最小码距 d0 2t + 1,7.2 纠错编码的基本原理,4) 最小码距d0与检错纠错能力关系,（3）先纠后检，纠检结合模式 为纠正 t 个误码, 同时能检出 e 个误码, 要求最小码距 d0 t + e + 1 ( e t ),
5、7.2 纠错编码的基本原理,4) 最小码距d0与检错纠错能力关系,(1)只检模式 由d0 e + 1 , 可知系统的检错能力：最多可检出6位误码。,(2) 只纠模式 由d0 2t + 1 , 可知系统的纠错能力：最多可检出3位误码。,(3) 纠检结合模式 由d0 t + e + 1 ( e t ) , 可知: 若先纠正1位误码，则还可以检出5位以下的误码。, 若先纠正2位误码，则还可以检出4位以下的误码。,7.2 纠错编码的基本原理,4) 最小码距d0与检错纠错能力关系,5) 差错控制(纠错)编码的效用,例码长 n =7 ，Pe = 10-3 时 P7 ( 1 ) 710-3 P7 ( 2 )
6、 2.110-5 P7 ( 3 ) 3.510-8,采用差错控制编码,即使仅能够检出或纠正12个误码，也能使误码率降低几个数量级。,7.2 纠错编码的基本原理,7.3 常用的简单编码,1) 奇偶监督码, 偶监督码 信息位附加监督位后，码组中“1”的个数为偶数, 即满足 an-1 an-2 a1 a0 = 0, 奇监督码 信息位附加监督位后，码组中“1”的个数为奇数, 即满足 an-1 an-2 a1 a0 = 1,奇偶监督码的编码效率=(n-1)/n,9.3 常用的简单编码,2) 二维奇偶监督码, 二维奇偶监督码有可能检测出偶数个错误, 甚至可能纠正一些错误。 二维奇偶监督码特别适合于检测突发
7、性错误。 二维奇偶监督码的编码效率低于一维奇偶监督码。 上例中，= m(n-1)/n(m+1),二维奇偶监督码又称为方阵码。它是将上述的m条偶或奇监督码排成一个方阵，然后沿垂直方向加上垂直监督位构成。,例,信息位 k = 77 = 49位，监督位 r = 7+8 = 15位，编码效率 = 49/(49+15) = 49/64,9.3 常用的简单编码,2) 二维奇偶监督码,3) 恒比码 (等重码),在全部码组集合中，每条码组中包含 “1” 的数目相同 。,无法清晰地将信息位与监督位分开。因此一般只适用与传输电传机或键盘设备输入信息编码。恒比码不适合信源随机信息的编码。,4) 正反码,正反码中信息
8、位数目和监督位数目相同。当信息位中“1”为奇数时，监督位与信息位相同; 当信息位中“1”为偶数时，监督位与信息位相反。正反码的编码效率= 1/2, 是具有纠错能力的编码。,9.3 常用的简单编码,7.4 线性分组码,前述的偶监督码，n-1个信息位附加1个监督位，构成整个码组中“1”的个数为偶数, 唯一的监督关系满足 an-1 an-2 a1 a0 = 0,在接收端，由收到整个码组an-1 an-2 a1 a0 ，计算校正子S S = an-1 an-2 a1 a0 单个校正子S的取值只有两种可能，“0”或“1”。若S = 0, 表示“无错”, S = 1, 表示“有错”。无法确定误码的位置进行
9、纠正。,增加监督位的数量，可以建立监督位和信息位关系（监督关系）的多个监督关系式。在接收端，由收到整个码组an-1 an-2 a1 a0 ，计算多个校正子S1、S2 、 Sr 。组合取值有2r 种可能，一种表示“无错”, 其他2r -1种可以用来确定误码的位置以进行纠正。,7.4 线性分组码,若由信息位和监督位构成的整个码组的总长度n满足 n 2r 1 或 2r n + 1 = k + r + 1 则除一种状态表示“无错”外，校正子S1、S2 、 Sr 组合的其他2r -1种状态,至少可以确定长度为n的码组中，一个单个误码的位置。,若码组的总长度n满足 n = 2r 1 或 2r = n +
10、1 这时r个校正子组合的2r 种状态,恰好可以表示出“无错”和n位码组当中的1位误码位置。作为能够纠正1位误码的一种编码，其编码效率是最高的, 称为汉明(Hamming)码。,能够纠正1位误码的 (7,4)、(15,11)、(31,26)、(63,57)、. ，其编码效率在同码长的编码中都是最高的, 都是汉明码。,7.4 线性分组码,通过（7, 4）分组码例子说明汉明码的监督关系式构造。 信息位(k=4): a6 a5 a4 a3 监督位(r=3) : a2 a1 a0,仅当1位误码位置在a2 、a4 、a5或a6时，校正子S1为1；否则S1为0。这意味着a2 、a4 、a5、a6 4个码元构
11、成偶监督关系 S1 = a6 a5 a4 a2,同理可得到关于S2、S3的偶监督关系，有 S1 = a6 a5 a4 a2 S2 = a6 a5 a3 a1 S3 = a6 a4 a3 a0,7.4 线性分组码,7.4 线性分组码,例如：接收到码组“0000011”,该码组确实是表中某码组传输中产生了1位误码所致。分别计算3个校正子，有 S1 = a6 a5 a4 a2 = 0 0 0 0 = 0 S2 = a6 a5 a3 a1 = 0 0 0 1 = 1 S3 = a6 a4 a3 a0 = 0 0 0 1 = 1 根据校正子与误码位置对应关系，可以确定1位误码的位置在a3 处，正确的码组
12、应该为“0001011”，它就是第2条码组。,7.4 线性分组码,如果 1 条码组在传输过程中确实产生了 1 位错误，前述的(7,4)汉明码就能无误地指出误码位置以进行纠正。,7.4 线性分组码,汉明码的全部码组可以看到，这种码的最小码距 (数值上和非全零码的最小码重相等) d0=3，用于检错可检测出 e=2 位以下的误码，用于纠错只可纠正 t=1 位误码 。这种码的编码效率= k/n = 4/7。,7.4 线性分组码,并可表示为矩阵形式,9.4 线性分组码,9.4 线性分组码,对已知信息位a6 a5 a4 a3 求监督位a2 a1 a0的关系扩充，变为已知信息位a6 a5 a4 a3 求整个
13、码组a6 a5 a4 a3 a2 a1 a0的关系式,a2 = a6 a5 a4 a1 = a6 a5 a3 a0 = a6 a4 a3,7.4 线性分组码, 线性分组码具有封闭性。它是指一种线性分组码的任意两条合法码组相异或，得到的结果仍然是该线性分组码的一条合法码组。, 线性分组码的两个重要性质, 线性分组码的最小码重（全零码除外），就是该线性分组码的最小码距。这是因为，任一码组中“1”的个数（码重），都是某两条码组不相同位的数目（码距）。,7.5 循环码,循环码是一种简单、重要、常用的线性分组码。除了具有线性分组码的一般性质外，还具有循环性，即码组集合中任一码组循环左移或右移若干位，得到
14、的结果仍然为该码组集合中的一条合法码组。,7.5.1 循环码原理,本例中，只要知道一条非全零码组,通过移位就可求出全部码组。,1) 码的多项式表示 对于码组an-1 an-2 a1 a0 ，若将各码元作为多项式系数，则可得到码组的多项式表示 T(x) = an-1 xn-1 + an-2 xn-2 + + a1 x + a0 对于前例的 (7, 3)码, 任一码组都可表示为 T(x) = a6 x6 + a5 x5 + a4 x4 + a3 x3 + a2 x2 + a1 x + a0 而其中的第7条码组“1 1 0 0 1 0 1”可表示为多项式 T7 (x) = x6 + x5 + x2
15、+ 1,7.5 循环码,7.5.1 循环码原理,2) 码多项式的按模运算,7.5.1 循环码原理,重要结论: 在循环码中，若 T(x) 是一个长度为 n 的码组，则xi T(x) 在按模 xn+1 运算下，也是该循环码的一个许用码组。,2) 码多项式的按模运算,7.5.1 循环码原理,例 T(x)= x 4 + x2 + x + 1 是一个长度为 7 的合法码组, 可以证明 T(x) = x 3 T(x) = x7 + x5 + x4 + x3 按模 x7 +1运算,其结果为 T(x) x5 + x4 + x3 + 1 也是一个长度为 7 的合法码组。,2) 码多项式的按模运算,7.5.1 循环码原理,3) 循环码生成矩阵和生成多项式,生成矩阵G用于由给定信息位生成完整码组，它由 k 行n列构成，其每一行都是彼此线性无关的合法码组。 在循环码中, 一个(n,k)码有2k种不同码组。现用g(x)表示前(k-1)位皆为“0”的码组,则g(x)、xg(x) 、 x2g(x)、 xk-1g(x) 是k个彼此线性无关的合法码组, 可用来构成循环码的生成矩阵,可证, 除全零码外, g(x) 前(k-1)位皆为 “0” 是唯一前面连续“0”最多的码组, 且常数项一定为“1”, 否则经若干次循环移位后
