1、 7.1 引言引言 7.2 纠错编码的基本原理纠错编码的基本原理 7.3 常用的简单编码常用的简单编码 7.4 线性分组码线性分组码 7.5 循环码循环码 7 7 差错控制编码差错控制编码7.1 引言引言1)差错的产生差错的产生2)差错控制方法差错控制方法噪声与干扰噪声与干扰 检错重发法检错重发法 前向纠错法前向纠错法 反馈校验法反馈校验法随机噪声与干扰随机噪声与干扰突发噪声与干扰突发噪声与干扰混合噪声与干扰混合噪声与干扰随机信道随机信道突发信道突发信道混合信道混合信道噪声与干扰是通信出噪声与干扰是通信出现差错的基本原因。现差错的基本原因。不同的不同的噪声与噪声与干扰信干扰信道，应道，应采用不
2、采用不同的差同的差错控制错控制策略。策略。检错重发法检错重发法：双向信道工作。接收信息方：双向信道工作。接收信息方具有检错能力，收到信息无误，回发肯定具有检错能力，收到信息无误，回发肯定应答；有误则不发应答或发否定应答。应答；有误则不发应答或发否定应答。前向纠错法前向纠错法：单向信道工作。接收信息方：单向信道工作。接收信息方具有纠错能力，发现收到信息有误时，确具有纠错能力，发现收到信息有误时，确定误码的位置并按规则予以纠正。定误码的位置并按规则予以纠正。前向纠错法前向纠错法：双向信道工作。接收信息方：双向信道工作。接收信息方简单地将收到信息回传给发送方，由发送简单地将收到信息回传给发送方，由发
3、送方判断前次发送是否无误。方判断前次发送是否无误。7.1 引言引言3)检错重发检错重发(ARQ)系统系统 典型典型ARQ系统组成框图系统组成框图 发送信源终端接收信宿终端编码器、缓冲存储重发控制解码器指令产生输出缓存双 向 信 道正确输出错误删除 ARQ系统主要优点系统主要优点:1.只需少量多余码元；只需少量多余码元；2.适应不同差错特性；适应不同差错特性；3.检错方法简单。检错方法简单。ARQ系统主要缺点系统主要缺点:1.需要双向信道；需要双向信道；2.出错率高时，重发降低信道效率；出错率高时，重发降低信道效率；3.信息传输实时性差。信息传输实时性差。7.1 引言引言4)差错控制编码差错控制
4、编码 在信息码元序列中加入一定数目的监督码元在信息码元序列中加入一定数目的监督码元 差错控制编码的检纠错能力差错控制编码的检纠错能力 差错控制编码的编码效率差错控制编码的编码效率 一般说来，差错控制编码的检纠错能力取决于：一般说来，差错控制编码的检纠错能力取决于：在信息码元序列中加入的监督码元的多少在信息码元序列中加入的监督码元的多少。对于一定长度。对于一定长度的信息码元序列的信息码元序列,加入的监督码元越多，检纠错能力越强。加入的监督码元越多，检纠错能力越强。不同的编码规则与方法不同的编码规则与方法。在一定长度信息码元序列中加入监督码元的数目越多在一定长度信息码元序列中加入监督码元的数目越多
5、,差错控差错控制编码的编码效率越低。如信息码长为制编码的编码效率越低。如信息码长为k，监督码长为，监督码长为r,则编则编码效率为码效率为k/(k+r)=k/n。7.2 纠错编码的基本原理纠错编码的基本原理 差错控制编码举例差错控制编码举例 消息消息 信息位信息位 监督位监督位 晴晴 0 0 0 云云 0 1 1 阴阴 1 0 1 雨雨 1 1 0两位信息位后加入一个监督位两位信息位后加入一个监督位,使使每码组中每码组中“1”的个数为偶数的个数为偶数,能够能够检测出码组中所有单数个误码。检测出码组中所有单数个误码。为每组信息码后附加若干个监督为每组信息码后附加若干个监督位构成的码组集合位构成的码
6、组集合,称为称为分组码分组码。分组码用符号分组码用符号(n,k)表示表示,k是信息是信息位的数目位的数目,n是码组总长度是码组总长度,n-k=r是监督位数目。是监督位数目。an-1 an-2 ar ar-1 a1 a0k个信息位个信息位r个监督位个监督位码组总长度码组总长度 n=k+r (n,k)分组码的结构分组码的结构7.2 纠错编码的基本原理纠错编码的基本原理1)码重与码距概念码重与码距概念 一条码组中一条码组中“1”的个的个数称为该码组的数称为该码组的码重码重。两码组中不同位的数目两码组中不同位的数目称为该两码组的称为该两码组的码距码距。2)最小码重与最小码距最小码重与最小码距 某码组集
7、合中含某码组集合中含“1”个数最少的码组的码重个数最少的码组的码重,称该码组集合的称该码组集合的最小码重最小码重。某码组集合中不同位数某码组集合中不同位数最少的两码组的码距最少的两码组的码距,称称该码组集合的该码组集合的最小码距最小码距。码组集合码组集合100100100110111011100011101101000111000100码重码重w=3w=4w=4w=5w=3w=2最小码重最小码重 w0=2码重与码距概念举例码重与码距概念举例码距码距d12=3d13=3d14=4d15=3d16=3d24=1最小码距最小码距 d0=17.2 纠错编码的基本原理纠错编码的基本原理3)码距码距(汉明
8、汉明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,说明某说明某码组的任何一
9、位错误，都不码组的任何一位错误，都不可能变为其他合法码组可能变为其他合法码组,能够能够检测出单个误码。检测出单个误码。最小码距最小码距d0 衡量差错控制编码系统衡量差错控制编码系统检错及纠错能力检错及纠错能力决定性参数决定性参数7.2 纠错编码的基本原理纠错编码的基本原理4)最小码距最小码距d0与检错纠错能力关系与检错纠错能力关系（1）只检模式）只检模式 为检测为检测 e 个误码，要求最小码距个误码，要求最小码距 d0 e+1 AB0123ed0 码距与检错纠错能力的关系码距与检错纠错能力的关系（a）只检模式）只检模式（2）只纠模式）只纠模式 为纠正为纠正 t 个误码，要求最小码距个误码，要求
10、最小码距 d0 2t+1 码距与检错纠错能力的关系码距与检错纠错能力的关系（b）只纠模式）只纠模式AB0123td0t45677.2 纠错编码的基本原理纠错编码的基本原理4)最小码距最小码距d0与检错纠错能力关系与检错纠错能力关系（3）先纠后检，纠检结合模式）先纠后检，纠检结合模式 为纠正为纠正 t 个误码个误码,同时能检出同时能检出 e 个误码个误码,要求最小码距要求最小码距 d0 t+e+1 (e t)码距与检错纠错能力的关系码距与检错纠错能力的关系（c）纠检结合模式）纠检结合模式ABtet1d07.2 纠错编码的基本原理纠错编码的基本原理4)最小码距最小码距d0与检错纠错能力关系与检错纠
11、错能力关系(1)只检模式只检模式 由由d0 e+1,可知系统的检错能力：最多可检出可知系统的检错能力：最多可检出6位误码。位误码。(2)只纠模式只纠模式 由由d0 2t+1,可知系统的纠错能力：最多可检出可知系统的纠错能力：最多可检出3位误码。位误码。(3)纠检结合模式纠检结合模式 由由d0 t+e+1 (e t),可知可知:若先纠正若先纠正1位误码，则还可以检出位误码，则还可以检出5位以下的误码位以下的误码。例例 某差错控制编码系统，码组集合的最小码距某差错控制编码系统，码组集合的最小码距d0=7,试求该试求该编码系统的检纠错能力。编码系统的检纠错能力。ABe6t3t=1e5t=2e4 若先
12、纠正若先纠正2位误码，则还可以检出位误码，则还可以检出4位以下的误码位以下的误码。7.2 纠错编码的基本原理纠错编码的基本原理4)最小码距最小码距d0与检错纠错能力关系与检错纠错能力关系5)差错控制差错控制(纠错纠错)编码的效用编码的效用AB错错2位位错错5位位错错3位位错错4位位错错1位位错错6位位假设在随机信道中发送假设在随机信道中发送“0”和和“1”时的出错概率相同，都等于时的出错概率相同，都等于Pe（Pe 1），则容易证明，在长度为），则容易证明，在长度为n 的码组中恰好发生的码组中恰好发生r个个误码的概率为误码的概率为rernerernnPrnrnPPCrP)!(!)1()(例例码长
13、码长 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-2 a1 a0=0 由由k=n-1个信息位个信息位 an-1 an-2 a1 和和 r=1个监督位个监督
14、位 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)二维奇偶监督码二维奇偶
15、监督码 二维奇偶监督码有可能检测出偶数个错误二维奇偶监督码有可能检测出偶数个错误,甚至可能纠正一甚至可能纠正一些错误。些错误。二维奇偶监督码特别适合于检测突发性错误。二维奇偶监督码特别适合于检测突发性错误。二维奇偶监督码的编码效率低于一维奇偶监督码。二维奇偶监督码的编码效率低于一维奇偶监督码。上例中，上例中，=m(n-1)/n(m+1)二维奇偶监督码又称为二维奇偶监督码又称为方阵码。它是将上述的方阵码。它是将上述的m条偶或奇监督码排成条偶或奇监督码排成一个方阵，然后沿垂直一个方阵，然后沿垂直方向加上垂直监督位构方向加上垂直监督位构成。成。a1n-1 a1n-2 a11 a10a2n-1 a2n
16、-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 1000001 0 水平监督位水平监督位垂直监督位垂直监督位 0 1 1 1 0 1 1 0 例例信息位信息位 k=77=49位，监督位位，监督位 r=7+8=15位，编码效率位，编码效率 =49/(49+15)=49/649.3 常用的简单编码
17、常用的简单编码2)二维奇偶监督码二维奇偶监督码3)恒比码恒比码(等重码等重码)在全部码组集合中，每在全部码组集合中，每条码组中包含条码组中包含“1”的的数目相同数目相同。我国电传机数字代码我国电传机数字代码字符字符 保护电码保护电码 字符字符 保护电码保护电码 0 01101 5 00111 1 01011 6 10101 2 11001 7 11100 3 10110 8 01110 4 11010 9 10011无法清晰地将信息位与监督位分开。因此一般只适用与传输电无法清晰地将信息位与监督位分开。因此一般只适用与传输电传机或键盘设备输入信息编码。恒比码不适合信源随机信息的传机或键盘设备输入
18、信息编码。恒比码不适合信源随机信息的编码。编码。4)正反码正反码正反码中信息位数目和监督位数目相同。当信息位中正反码中信息位数目和监督位数目相同。当信息位中“1”为奇为奇数时，监督位与信息位相同数时，监督位与信息位相同;当信息位中当信息位中“1”为偶数时，监督为偶数时，监督位与信息位相反。位与信息位相反。正反码的编码效率正反码的编码效率=1/2,是具有是具有纠错能力纠错能力的编码。的编码。详见讲义（略）详见讲义（略）9.3 常用的简单编码常用的简单编码7.4 线性分组码线性分组码前述的偶监督码，前述的偶监督码，n-1个信息位附加个信息位附加1个监督位，构成整个码组个监督位，构成整个码组中中“1
19、”的个数为偶数的个数为偶数,唯一的监督关系满足唯一的监督关系满足 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,表示表示“有错有错”。无法确定误码的位置进行。无法确定误码的位置进行纠正。纠正。增加监督位的数量，可以建立监督位和信息位关系（监督关系）增加监督位的数量，可以建立监督位和信息位关系（监督关系）的多个监督关系式。在接收端，由收到整个码组
20、的多个监督关系式。在接收端，由收到整个码组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种状态种状态,至少可以确定长度为至少可以确
21、定长度为n的码组中，一个单个的码组中，一个单个误码的位置。误码的位置。若码组的总长度若码组的总长度n满足满足 n=2r 1 或或 2r=n+1这时这时r个个校正子校正子组合的组合的2r 种状态种状态,恰好可以表示出恰好可以表示出“无错无错”和和n位码组当中的位码组当中的1位误码位置。作为能够纠正位误码位置。作为能够纠正1位误码的一种编码，位误码的一种编码，其编码效率是最高的其编码效率是最高的,称为称为汉明汉明(Hamming)码码。能够纠正能够纠正1位误码的位误码的(7,4)、(15,11)、(31,26)、(63,57)、.，其编码效率在同码长的编码中都是最高的其编码效率在同码长的编码中都是
22、最高的,都是都是汉明码汉明码。7.4 线性分组码线性分组码 通过（通过（7,4）分组码例子说明汉明码的监督关系式构造。）分组码例子说明汉明码的监督关系式构造。信息位信息位(k=4):a6 a5 a4 a3 监督位监督位(r=3):a2 a1 a0 校正子与误码位置的对应关系校正子与误码位置的对应关系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仅当仅当1位误码位置在位误码位置在a2、a4、a5或或a6时，校正子时，校正子S1为为1；
23、否则；否则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 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6编码时，给
24、信息位加入监督位应使得编码时，给信息位加入监督位应使得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 种信息码组合，求出每种种信息码组合，求出每种信息组合所附加的监
25、督位，进而得到全部信息组合所附加的监督位，进而得到全部 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
26、 a3 a1=0 0 0 1=1 S3=a6 a4 a3 a0=0 0 0 1=1根据校正子与误码位置对应关系，可以确定根据校正子与误码位置对应关系，可以确定1位误码的位置在位误码的位置在a3 处，正确的码组应该为处，正确的码组应该为“0001011”，它就是第，它就是第2条码组。条码组。7.4 线性分组码线性分组码如果如果 1 条码组在传输过程中确实产生了条码组在传输过程中确实产生了 1 位错误，前述的位错误，前述的(7,4)汉明码就能无误地指出误码位置以进行纠正。汉明码就能无误地指出误码位置以进行纠正。7.4 线性分组码线性分组码汉明码的全部码组可以看到，这种码的最小码距汉明码的全部码组可
27、以看到，这种码的最小码距 (数值上和数值上和非全零码的最小码重相等非全零码的最小码重相等)d0=3，用于检错可检测出，用于检错可检测出 e=2 位以位以下的误码，用于纠错只可纠正下的误码，用于纠错只可纠正 t=1 位误码位误码。这种码的编码效。这种码的编码效率率=k/n=4/7。汉明码汉明码是能够纠正是能够纠正1位误码，其编码效率在同码长的编码中是位误码，其编码效率在同码长的编码中是最高的。具有最高的。具有11位误码纠正能力的位误码纠正能力的(7,4)、(15,11)、(31,26)、(63,57)、.都是都是汉明码汉明码。汉明码的编码效率随着码组总长。汉明码的编码效率随着码组总长 n 的增加
28、而增加。因为码组越长，信息位所占比例越大，监的增加而增加。因为码组越长，信息位所占比例越大，监督位所占比例越小。督位所占比例越小。当码长当码长n很大时，编码效率接近于很大时，编码效率接近于1。nnnrnnk)1(log12汉明码汉明码 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
29、为简化将为简化将“”改写改写为为“+”,均表示模均表示模2加。加。并可表示为矩阵形式并可表示为矩阵形式 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形式形式的监
30、督矩阵称为的监督矩阵称为典型监督矩阵典型监督矩阵。111010011010101011001PIr H1110 1001101 0101011 001上式改写可得到已知信息位上式改写可得到已知信息位a6 a5 a4 a3 求监督位求监督位a2 a1 a0的矩阵关的矩阵关系式系式a2 a1a0111011011011a6 a5a4a3或或(9.4-12)a2a1a0a6a5a4a3111110101011Prk Qkr其其Q为为 kr 阶阶,它是它是 P 的转置矩阵的转置矩阵Q=PT 9.4 线性分组码线性分组码对已知信息位对已知信息位a6 a5 a4 a3 求监督位求监督位a2 a1 a0的关
31、系扩充，变为已知的关系扩充，变为已知信息位信息位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 a1a01000010000100001111011011011简记为简记为 A=a6 a5 a4 a3 G G10001110100110001010100010111000 1110100 1100010 1010001 011IkQGTkk 阶单位矩阵阶单位矩阵Ikkr阶矩阵阶
32、矩阵Q典型典型生成生成矩阵矩阵生成矩阵生成矩阵7.4 线性分组码线性分组码 线性分组码具有封闭性。它是指一种线性分组码的任意两条线性分组码具有封闭性。它是指一种线性分组码的任意两条合法码组相异或，得到的结果仍然是该线性分组码的一条合法合法码组相异或，得到的结果仍然是该线性分组码的一条合法码组。码组。线性分组码的两个重要性质线性分组码的两个重要性质 线性分组码的最小码重（全零码除外），就是该线性分组线性分组码的最小码重（全零码除外），就是该线性分组码的最小码距。这是因为，任一码组中码的最小码距。这是因为，任一码组中“1”的个数（码重），的个数（码重），都是某两条码组不相同位的数目（码距）。都是某
33、两条码组不相同位的数目（码距）。性质性质1（线性分组码的封闭性）（线性分组码的封闭性）给我们提供了利用某些已知码给我们提供了利用某些已知码组获得一些未知码组的一条可组获得一些未知码组的一条可能的途径。能的途径。性质性质2（最小码距（最小码距=最小码重）最小码重）给我们提供了从码组获得最小给我们提供了从码组获得最小码距，并判断检错纠错能力的码距，并判断检错纠错能力的便捷方法。便捷方法。7.5 循环码循环码循环码循环码是一种简单、重要、常用的线性分组码。除了具有线性是一种简单、重要、常用的线性分组码。除了具有线性分组码的一般性质外，还具有循环性，即码组集合中任一码组分组码的一般性质外，还具有循环性
34、，即码组集合中任一码组循环左移或右移若干位，得到的结果仍然为该码组集合中的一循环左移或右移若干位，得到的结果仍然为该码组集合中的一条合法码组。条合法码组。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循环循环m位位循环左移循环左移3位位
35、循环左移循环左移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条码组条码组
36、“1 1 0 0 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)npnpQnm,多项式的按模运算多
37、项式的按模运算对任意多项式对任意多项式F(x)被另一个被另一个n次多项式次多项式N(x)除，得到一商式除，得到一商式Q(x)和一个次数小于和一个次数小于n的余式的余式R(x),即即 F(x)=N(x)Q(x)+R(x)多项式多项式F(x)按模按模N(x)运算之结果为运算之结果为 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+x
38、x2+x+1注意注意:多项式系数是模多项式系数是模2的的,取取值只能是值只能是“1”或或“0”,这也是这也是余式为余式为x2+x+1,而不为而不为 x2-x+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)
39、=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 7 1 1 0 0 1 0 1 8 1 1 1 0 0 1 02)码多项式的按模运算码多项式的按模运算7.5.1 循环码原理循
40、环码原理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
41、)xk-2g(x)可证可证,除全零码外除全零码外,g(x)前前(k-1)位皆为位皆为“0”是唯一前面连续是唯一前面连续“0”最多的码组最多的码组,且常数项一定为且常数项一定为“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
42、 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)是一个次数最低的码多项式。是一个是一个次数最低的码多项式。是一个常数项不为零的常数项不为零的(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)非典型阵非典型阵典型化线性变换线性
43、变换G001 0111010 1110100 1011典型阵典型阵 G=IkQ3)循环码生成矩阵和生成多项式循环码生成矩阵和生成多项式7.5.1 循环码原理循环码原理4)如何寻找如何寻找(n,k)码的生成多项式码的生成多项式生成多项式生成多项式 g(x)是循环码的最关键因素。由它可容易地获得生是循环码的最关键因素。由它可容易地获得生成矩阵成矩阵G,并根据信息位产生全部码组。并根据信息位产生全部码组。由由(n,k)循环码的全部条码组寻找循环码的全部条码组寻找 g(x)(7,4)循环码举例循环码举例码组码组 信息位信息位 监督位监督位 编号编号 a6 a5 a4a3 a2 a1 a0 1 0 0
44、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 0 16 1 1 1 1 1 1 1
45、前前(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
46、 0 1 1 1 0 1 0 16 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
47、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 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)循环码的部分码组寻找循
48、环码的部分码组寻找 g(x)4)如何寻找如何寻找(n,k)码的生成多项式码的生成多项式7.5.1 循环码原理循环码原理 无已知条件下，求无已知条件下，求(n,k)循环码的循环码的 g(x)如何寻找如何寻找 g(x)？生成多项式生成多项式 g(x)是是(xn+1)的一个因式。的一个因式。可以通过对可以通过对(xn+1)分解因式获得分解因式获得g(x)。(xn+1)的因式可能有多的因式可能有多个，只有那些常数项不为零的个，只有那些常数项不为零的n-k次因式才可作为次因式才可作为(n,k)循环码循环码的生成多项式的生成多项式 g(x)。例例 为获得为获得(7,4)循环码的生成多项式循环码的生成多项式
49、 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+x2+x+1 (x+1)(x3+x2+1)(x+1)(x3+x+1)4)如何寻找如何寻找(n,k)码的生成多项式码的生成多项式7.5.1 循环码原理循环码原理7.5.2 循环码的编解码方法循环码的编解码方法1)编码步骤编码步骤(1)用信息码多项式用
50、信息码多项式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 m(x)=g(x)Q(x)+R(x)若取若取g(x)=x4+x2+x+1，对于上例可得，对于上例可得 相当于相当于 11)1(1)()(24222456xxxxxxxxxxxxgxmxkn1100
