东北通信原理fjx2011

1、 7.1 引言 7.2 纠错编码的基本原理 7.3 常用的简单编码 7.4 线性分组码 7.5 循环码 7 差错控制编码7.1 引言1) 差错的产生2) 差错控制方法噪声与干扰 检错重发法 前向纠错法 反馈校验法随机噪声与干扰突发噪声与干扰混合噪声与干扰随机信道突发信道混合信道噪声与干扰是通信出现差错的基本原因。不同的噪声与干扰信道，应采用不同的差错控制策略。检错重发法：双向信道工作。接收信息方具有检错能力，收到信息无误，回发肯定应答；有误则不发应答或发否定应答。前向纠错法：单向信道工作。接收信息方具有纠错能力，发现收到信息有误时，确定误码的位置并按规则予以纠正。前向纠错法：双向信道工作。接收

2、信息方简单地将收到信息回传给发送方，由发送方判断前次发送是否无误。7.1 引言3) 检错重发(ARQ)系统 典型ARQ系统组成框图 发送信源终端接收信宿终端编码器、缓冲存储重发控制解码器指令产生输出缓存双 向 信 道正确输出错误删除 ARQ系统主要优点: 1. 只需少量多余码元； 2. 适应不同差错特性； 3. 检错方法简单。 ARQ系统主要缺点: 1. 需要双向信道； 2. 出错率高时，重发降低信道效率； 3. 信息传输实时性差。7.1 引言4) 差错控制编码 在信息码元序列中加入一定数目的监督码元 差错控制编码的检纠错能力 差错控制编码的编码效率 一般说来，差错控制编码的检纠错能力取决于：

3、 在信息码元序列中加入的监督码元的多少。对于一定长度的信息码元序列,加入的监督码元越多，检纠错能力越强。 不同的编码规则与方法。在一定长度信息码元序列中加入监督码元的数目越多, 差错控制编码的编码效率越低。如信息码长为k，监督码长为r,则编码效率为k/(k+r)=k/n。7.2 纠错编码的基本原理 差错控制编码举例 消息 信息位 监督位 晴 0 0 0 云 0 1 1 阴 1 0 1 雨 1 1 0两位信息位后加入一个监督位,使每码组中“1”的个数为偶数, 能够检测出码组中所有单数个误码。为每组信息码后附加若干个监督位构成的码组集合, 称为分组码。分组码用符号(n,k)表示, k是信息位的数目

4、, n是码组总长度, n-k=r是监督位数目。an-1 an-2 ar ar-1 a1 a0k个信息位r个监督位码组总长度 n = k+r (n,k)分组码的结构7.2 纠错编码的基本原理1) 码重与码距概念 一条码组中 “1” 的个数称为该码组的码重。 两码组中不同位的数目称为该两码组的码距。2) 最小码重与最小码距 某码组集合中含 “1” 个数最少的码组的码重, 称该码组集合的最小码重。 某码组集合中不同位数最少的两码组的码距, 称该码组集合的最小码距。码组集合100100100110111011100011101101000111000100码重w=3w=4w=4w=5w=3w=2最小码

5、重 w0=2码重与码距概念举例码距d12=3d13=3d14=4d15=3d16=3d24=1最小码距 d0=17.2 纠错编码的基本原理3) 码距(汉明Hamming距离)概念 码距的几何意义a0a1a2(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1) 如果使用全部8个三位的码组分别表示8种不同信息，由于最小码距d0 =1, 说明某码组的任何一位错误，都可能变为其他合法码组,无检错或纠错能力。 如果使用其中4个三位的码组分别表示4种不同信息，由于最小码距d0 =2, 说明某码组的任何一位错误，都不可能变为其他合法码组,能够检测出

6、单个误码。最小码距d0 衡量差错控制编码系统检错及纠错能力决定性参数7.2 纠错编码的基本原理4) 最小码距d0与检错纠错能力关系（1）只检模式 为检测 e 个误码，要求最小码距 d0 e + 1 AB0123ed0 码距与检错纠错能力的关系（a）只检模式（2）只纠模式 为纠正 t 个误码，要求最小码距 d0 2t + 1 码距与检错纠错能力的关系（b）只纠模式AB0123td0t45677.2 纠错编码的基本原理4) 最小码距d0与检错纠错能力关系（3）先纠后检，纠检结合模式 为纠正 t 个误码, 同时能检出 e 个误码, 要求最小码距 d0 t + e + 1 ( e t ) 码距与检错纠

7、错能力的关系（c）纠检结合模式ABtet1d07.2 纠错编码的基本原理4) 最小码距d0与检错纠错能力关系(1)只检模式 由d0 e + 1 , 可知系统的检错能力：最多可检出6位误码。(2) 只纠模式 由d0 2t + 1 , 可知系统的纠错能力：最多可检出3位误码。(3) 纠检结合模式 由d0 t + e + 1 ( e t ) , 可知: 若先纠正1位误码，则还可以检出5位以下的误码。例 某差错控制编码系统，码组集合的最小码距d0 = 7 , 试求该编码系统的检纠错能力。ABe6t3t =1e5t =2e4 若先纠正2位误码，则还可以检出4位以下的误码。7.2 纠错编码的基本原理4)

8、最小码距d0与检错纠错能力关系5) 差错控制(纠错)编码的效用AB错2位错5位错3位错4位错1位错6位假设在随机信道中发送“0”和“1”时的出错概率相同，都等于Pe（ Pe 1），则容易证明，在长度为n 的码组中恰好发生r个误码的概率为例码长 n =7 ，Pe = 10-3 时 P7 ( 1 ) 710-3 P7 ( 2 ) 2.110-5 P7 ( 3 ) 3.510-8采用差错控制编码,即使仅能够检出或纠正12个误码，也能使误码率降低几个数量级。7.2 纠错编码的基本原理7.3 常用的简单编码1) 奇偶监督码 偶监督码 信息位附加监督位后，码组中“1”的个数为偶数, 即满足 an-1 an

9、-2 a1 a0 = 0 由k = n-1个信息位 an-1 an-2 a1 和 r = 1个监督位 a0 构成的总长度为n=k+1的 ( k+1, k ) 分组码。 奇监督码 信息位附加监督位后，码组中“1”的个数为奇数, 即满足 an-1 an-2 a1 a0 = 1 监督关系式偶监督码由已知信息位获得监督位的表示式为 a0 = an-1 an-2 a1奇监督码由已知信息位获得监督位的表示式为 a0 = an-1 an-2 a1 1奇偶监督码的编码效率=(n-1)/n9.3 常用的简单编码2) 二维奇偶监督码 二维奇偶监督码有可能检测出偶数个错误, 甚至可能纠正一些错误。 二维奇偶监督码特

10、别适合于检测突发性错误。 二维奇偶监督码的编码效率低于一维奇偶监督码。上例中，= m(n-1)/n(m+1)二维奇偶监督码又称为方阵码。它是将上述的m条偶或奇监督码排成一个方阵，然后沿垂直方向加上垂直监督位构成。a1n-1 a1n-2 a11 a10a2n-1 a2n-2 a21 a20amn-1 amn-2 am1 am0cn-1 cn-2 c1 c0信息位m(n-1)水平监督位m1垂直监督位 1n信息位1 0 0 1 1 0 10 0 1 0 1 1 01 0 1 1 1 0 11 1 0 0 0 1 00 1 0 0 0 0 10 0 0 1 1 1 00 1 0 1 0 1 10000

11、01 0 水平监督位垂直监督位 0 1 1 1 0 1 1 0 例信息位 k = 77 = 49位，监督位 r = 7+8 = 15位，编码效率 = 49/(49+15) = 49/649.3 常用的简单编码2) 二维奇偶监督码3) 恒比码 (等重码)在全部码组集合中，每条码组中包含 “1” 的数目相同 。 我国电传机数字代码字符 保护电码 字符 保护电码 0 01101 5 00111 1 01011 6 10101 2 11001 7 11100 3 10110 8 01110 4 11010 9 10011无法清晰地将信息位与监督位分开。因此一般只适用与传输电传机或键盘设备输入信息编码。

12、恒比码不适合信源随机信息的编码。4) 正反码正反码中信息位数目和监督位数目相同。当信息位中“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, 表示

13、“无错”, S = 1, 表示“有错”。无法确定误码的位置进行纠正。增加监督位的数量，可以建立监督位和信息位关系（监督关系）的多个监督关系式。在接收端，由收到整个码组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的码组中，一个单个误码的位置。 若码组

14、的总长度n满足 n = 2r 1 或 2r = n + 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 校正子与误码位置的对应关系S1S2S3 误码位置 S1S2S3 误码位置

15、0 0 0 无错 0 1 1 a3 0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6仅当1位误码位置在a2 、a4 、a5或a6时，校正子S1为1；否则S1为0。这意味着a2 、a4 、a5、a6 4个码元构成偶监督关系 S1 = a6 a5 a4 a2 同理可得到关于S2、S3的偶监督关系，有 S1 = a6 a5 a4 a2 S2 = a6 a5 a3 a1 S3 = a6 a4 a3 a07.4 线性分组码 校正子与误码位置的对应关系S1S2S3 误码位置 S1S2S3 误码位置 0 0 0 无错 0 1 1 a3 0 0 1 a

16、0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6编码时，给信息位加入监督位应使得S1 = S2 = S3 = 0，即满足 a6 a5 a4 a2 = 0 a6 a5 a3 a1 = 0 a6 a4 a3 a0 = 07.4 线性分组码由监督关系式（方程组） a6 a5 a4 a2 = 0 a6 a5 a3 a1 = 0 a6 a4 a3 a0 = 0整理可得到已知信息位求监督位的关系式 a2 = a6 a5 a4 a1 = a6 a5 a3 a0 = a6 a4 a3 对于信息位 k=4 情况，共有 24=16 种信息码组合，求出每种信息组合所附加的

17、监督位，进而得到全部 24=16 条完整码组。 (7,4) 汉明码的全部码组S1S2S3 误码位置 S1S2S3 误码位置 0 0 0 无错 0 1 1 a3 0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6例如：接收到码组“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位

18、误码的位置在a3 处，正确的码组应该为“0001011”，它就是第2条码组。7.4 线性分组码如果 1 条码组在传输过程中确实产生了 1 位错误，前述的(7,4)汉明码就能无误地指出误码位置以进行纠正。7.4 线性分组码汉明码的全部码组可以看到，这种码的最小码距 (数值上和非全零码的最小码重相等) d0=3，用于检错可检测出 e=2 位以下的误码，用于纠错只可纠正 t=1 位误码 。这种码的编码效率= k/n = 4/7。汉明码是能够纠正1位误码，其编码效率在同码长的编码中是最高的。具有11位误码纠正能力的 (7,4)、(15,11)、(31,26)、(63,57)、. 都是汉明码。汉明码的编

19、码效率随着码组总长 n 的增加而增加。因为码组越长，信息位所占比例越大，监督位所占比例越小。 当码长n很大时，编码效率接近于1。汉明码 2r=n+17.4 线性分组码改写监督关系式（方程组） a6 a5 a4 a2 = 0 a6 a5 a3 a1 = 0 (9. a6 a4 a3 a0 = 0为 1a6 + 1a5 + 1a4 + 0a3 + 1a2 + 0a1 + 0a0 = 0 1a6 + 1a5 + 0a4 + 1a3 + 0a2 + 1a1 + 0a0 = 0 1a6 + 0a5 + 1a4 + 1a3 + 0a2 + 0a1 + 1a0 = 0为简化将“”改写为“+”, 均表示模2加

20、。并可表示为矩阵形式 111010011010101011001a6 a5a4a3 a2 a1a0000简记为H AT=OT 或 A HT=O(9.4-10)rn监督矩阵a6 a5 a4 a3 a2 a1 a01n码组向量 0 0 0 1r零向量9.4 线性分组码 式中的监督矩阵是一个 r行n列的矩阵，内容可以分为两部分其中P为 rk 阶矩阵，Ir为 r r 阶单位矩阵。具有PIr形式的监督矩阵称为典型监督矩阵。111010011010101011001PIr H1110 1001101 0101011 001上式改写可得到已知信息位a6 a5 a4 a3 求监督位a2 a1 a0的矩阵关系式

21、a2 a1a0111011011011a6 a5a4a3或(9.4-12)a2a1a0a6a5a4a3111110101011Prk Qkr其Q为 kr 阶, 它是 P 的转置矩阵Q = PT 9.4 线性分组码对已知信息位a6 a5 a4 a3 求监督位a2 a1 a0的关系扩充，变为已知信息位a6 a5 a4 a3 求整个码组a6 a5 a4 a3 a2 a1 a0的关系式a2 = a6 a5 a4 a1 = a6 a5 a3a0 = a6 a4 a3a6 = a6a5 = a5a4 = a4 a3 = a3矩阵形式a6 a5a4a3a6 a5a4a3a2 a1a0100001000010

22、0001111011011011简记为 A=a6 a5 a4 a3 G G10001110100110001010100010111000 1110100 1100010 1010001 011IkQGTkk 阶单位矩阵Ikkr阶矩阵Q典型生成矩阵生成矩阵7.4 线性分组码 线性分组码具有封闭性。它是指一种线性分组码的任意两条合法码组相异或，得到的结果仍然是该线性分组码的一条合法码组。 线性分组码的两个重要性质 线性分组码的最小码重（全零码除外），就是该线性分组码的最小码距。这是因为，任一码组中“1”的个数（码重），都是某两条码组不相同位的数目（码距）。性质1（线性分组码的封闭性）给我们提供了

23、利用某些已知码组获得一些未知码组的一条可能的途径。性质2（最小码距=最小码重）给我们提供了从码组获得最小码距，并判断检错纠错能力的便捷方法。7.5 循环码循环码是一种简单、重要、常用的线性分组码。除了具有线性分组码的一般性质外，还具有循环性，即码组集合中任一码组循环左移或右移若干位，得到的结果仍然为该码组集合中的一条合法码组。7.5.1 循环码原理 (7, 3)循环码举例 码组 信息位 监督位 编号 a6 a5 a4 a3 a2 a1 a0 1 0 0 0 0 0 0 0 2 0 0 1 0 1 1 1 3 0 1 0 1 1 1 0 4 0 1 1 1 0 0 1 5 1 0 0 1 0 1

24、 1 6 1 0 1 1 1 0 0 7 1 1 0 0 1 0 1 8 1 1 1 0 0 1 0循环m位循环左移3位循环左移2位本例中，只要知道一条非全零码组,通过移位就可求出全部码组。循环右移3位 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

25、1 0 1”可表示为多项式 T7 (x) = x6 + x5 + x2 + 1对于码长为n的码组，码多项式的最高次数为xn-1 。多项式系数取值是模2的，即只能是“1”或“0”。7.5 循环码7.5.1 循环码原理2) 码多项式的按模运算 整数的按模运算对整数m按模n运算, 将整数m除以整数n, 商为整数Q, 余数为p ( p n ), 即整数m按模n运算之结果为 m p (模n) 多项式的按模运算对任意多项式F(x)被另一个n次多项式N(x) 除，得到一商式Q(x)和一个次数小于n的余式R(x) , 即 F(x) = N(x) Q(x) + R(x) 多项式F(x) 按模N(x) 运算之结果

26、为 F(x) R(x) (模N(x)(9.5-6)(9.5-7)7.5.1 循环码原理 例 x3 按模 (x3+1)运算，结果为 x3 1 (模 x3+1) x4 + x2 +1 按模 (x3+1)运算，结果为 x4 + x2 +1 x2 + x +1 (模 x3+1)x3+1x4 + x2 +1xx4 + xx2 + x +1注意: 多项式系数是模2的,取值只能是“1”或“0” , 这也是余式为x2 + x +1 ,而不为 x2 - x +1 的原因。重要结论: 在循环码中，若 T(x) 是一个长度为 n 的码组，则xi T(x) 在按模 xn+1 运算下，也是该循环码的一个许用码组。2)

27、码多项式的按模运算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 的合法码组。 (7, 3)循环码举例 码组 信息位 监督位 编号 a6 a5 a4 a3 a2 a1 a0 1 0 0 0 0 0 0 0 2 0 0 1 0 1 1 1 3 0 1 0 1 1 1 0 4 0 1 1 1 0 0 1 5 1 0 0 1 0 1 1 6 1 0 1 1 1 0 0

28、7 1 1 0 0 1 0 1 8 1 1 1 0 0 1 02) 码多项式的按模运算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)g(x)xg(x)xk-1g(x)xk-2g(x)可证, 除全零码外, g(x) 前(k-1)位皆为 “0” 是唯一前面连续“0”最多的码

29、组, 且常数项一定为“1”, 否则经若干次循环移位后会得到一个信息位全零的“非全零”码组，而这是不可能的。7.5.1 循环码原理 (7, 3)循环码举例 码组 信息位 监督位 编号 a6 a5 a4 a3 a2 a1 a0 1 0 0 0 0 0 0 0 2 0 0 1 0 1 1 1 3 0 1 0 1 1 1 0 4 0 1 1 1 0 0 1 5 1 0 0 1 0 1 1 6 1 0 1 1 1 0 0 7 1 1 0 0 1 0 1 8 1 1 1 0 0 1 0例g(x) 对应前(k-1)位皆为 “0” 是唯一前面连续“0”最多的码组, 因此，除全零码外， g(x)是一个次数最低的

30、码多项式。是一个常数项不为零的(n-k)次多项式。g(x) = x 4 + x2 + x + 1 G(x)g(x)xg(x)x2g(x)(9.5-16)G001 0111010 1110101 1100(9.5-17)非典型阵典型化线性变换G001 0111010 1110100 1011典型阵 G = IkQ3) 循环码生成矩阵和生成多项式7.5.1 循环码原理4) 如何寻找(n,k)码的生成多项式生成多项式 g(x) 是循环码的最关键因素。由它可容易地获得生成矩阵G , 并根据信息位产生全部码组。 由(n,k) 循环码的全部条码组寻找 g(x) (7, 4)循环码举例码组 信息位 监督位

31、编号 a6 a5 a4a3 a2 a1 a0 1 0 0 0 0 0 0 0 2 0 0 0 1 0 1 1 3 0 0 1 0 1 1 0 4 0 0 1 1 1 0 1 5 0 1 0 0 1 1 1 6 0 1 0 1 1 0 0 7 0 1 1 0 0 0 1 8 0 1 1 1 0 1 0 码组 信息位 监督位 编号 a6 a5 a4a3 a2 a1 a0 9 1 0 0 0 1 0 1 10 1 0 0 1 1 1 0 11 1 0 1 0 0 1 1 12 1 0 1 1 0 0 0 13 1 1 0 0 0 1 0 14 1 1 0 1 0 0 1 15 1 1 1 0 1 0

32、 0 16 1 1 1 1 1 1 1前(k-1)位皆为 “0” 的码组，也是信息位为“001”的码组。g(x)= x3 + x + 110110000101100 00101100001011G =7.5.1 循环码原理 由(n,k) 循环码的部分码组寻找 g(x)10110000101100 00101100001011G = (7, 4)循环码举例码组 信息位 监督位编号 a6 a5 a4a3 a2 a1 a0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 16

33、1 1 1 1 1 1 1循环左移3位，得到前(k-1)=3位皆为 “0” 的码组 “ 0001011”，对应 g(x)= x3 + x + 1线性变换典型化10001010100111 00101100001011G =1000 1010100 111 0010 1100001 011IkQ4) 如何寻找(n,k)码的生成多项式7.5.1 循环码原理 (7, 4)循环码举例码组 信息位 监督位编号 a6 a5 a4a3 a2 a1 a0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 16 1 1

34、 1 1 1 1 110110000101100 00101100001011G =线性变换典型化10001010100111 00101100001011G =1000 1010100 111 0010 1100001 011IkQ两条码组模2加后，循环左移1位，得到前(k-1)=3位皆为 “0” 的码组 “ 0001011”，对应g(x)= x3 + x + 1如何寻找 g(x) ？ 由(n,k) 循环码的部分码组寻找 g(x)4) 如何寻找(n,k)码的生成多项式7.5.1 循环码原理 无已知条件下，求(n,k) 循环码的 g(x)如何寻找 g(x) ？ 生成多项式 g(x) 是(xn

35、+ 1)的一个因式。可以通过对(xn + 1)分解因式获得g(x) 。 (xn + 1)的因式可能有多个，只有那些常数项不为零的n-k次因式才可作为(n , k)循环码的生成多项式 g(x) 。例 为获得 (7, 4) 循环码的生成多项式 g(x) ，分解 (x7 + 1)得 (x7 + 1) = ( x + 1) ( x3 + x2 + 1) ( x3 + x + 1)g1(x)和g2(x)都可作为(7 , 4)循环码的生成多项式 。g1(x)g2(x)同理, (7 , 4)循环码的生成多项式也是分解(x7 + 1)所得 g2(x) = x4 + x3 + x2+ 1 g1(x) = x4

36、+ x2 + x + 1 ( x + 1) ( x3 + x2 + 1)( x + 1) ( x3 + x + 1)4) 如何寻找(n,k)码的生成多项式7.5.1 循环码原理7.5.2 循环码的编解码方法1) 编码步骤(1) 用信息码多项式m(x)乘以xn-k ，该运算相当于给信息码后加(n- k)个“0”。 例如，信息码为“110”, 相当于m(x)= x2 + x 。当n- k=7-3=4 时， xn-k m(x) = x4 (x2 + x ) = x6 + x5，相当于“1100000” 。 (2) 用xn-k m(x)除以g(x) , 得到商Q(x)和余式r(x) , 既 xn-k

37、m(x) = g(x) Q(x) + R(x) 若取g(x)= x4 + x2 + x +1 ，对于上例可得 相当于 1100000 10111 101 10111= 111 +(3) 编出码组T(x)为 T(x) = xn-k m(x) + r(x) T(x) = 1100000 + 101 = 1100101 a b c d S e f m信息码输入编码输出 (7, 3) 循环码编码器7.5.2 循环码的编解码方法1) 编码步骤2) 解码步骤(1) 用接收码组 R(x) = T(x) + E(x)除以生成多项式g(x) , 得到余式 r(x) 。(2) 根据余式 r(x)用查表方法或运算得

38、到错误图样E(x) , 就可确定误码位置。(3) 从R(x)中减去E(x) , 就可得到已经纠正错误的原始发送码组T(x) 。解码信息输出 (7, 3) 循环码纠错解码器 a b c d 与 门 缓冲移位寄存器接收编码输入7.5.2 循环码的编解码方法7.6 卷积码 (连环码)分组码在编码时，各长度为n的码组进行分别编码。即对于给定的k个信息位，附加上仅仅与这k个信息位有关的r个监督位，形成长度为n的码组。各个码组之间没有任何约束关系，因此在译码时各个码组也是分别独立地进行。卷积码在编码时，长度为n的码组由k个信息位附加上r个监督位，形成长度为n的码组。但是这r个监督位不仅仅与当前的k个信息位

39、有关，还和前面的(N-1)个码组中的信息位有关。这样若干个(N)码组形成一种约束关系。卷积码的约束长度:以码组为单位时为N, 以码元为单位时为nN 。码组长度为n , 信息位组长度为k , 约束长度为N个码组的卷积码记为 (n , k , N)卷积码 , 卷积码的编码效率为Rc=k/n。7.6.1 卷积码的图形表示M3 M2 M1输入序列m1, m2 , , mj , 输出序列m1 y21 y31,m2 y22 y32, (3,1,3)卷积码编码原理 m1 m2 m3 m4 m5输入tm1 y21 y31 m2 y22 y32 m3 y23 y33 m4 y24 y34 m5 y25 y35输出t (3,1,3)卷积码编码器输入-输出关系信息位监督位7.6 卷积码 (连环码)1) 树状图 (3,1,3)卷积码的树状图0 0 01 1 1baa0 0 00 0 11 1 0dbc1 1 10 1 11 0 0bca0 0 10 1 01 0 1ddc1 1 00 0 01 1 1baa0 1 10 0 11 1 0d