通信原理第11章-差错控制编码课件

第第1111章章 差错控制编码差错控制编码现代通信系统原理通通 信信 原原 理理 电电 子子 教教 案案第第1111章章 差错控制编码差错控制编码 西西 北北 工工 业业 大大 学学（2008.6）7/27/20241第第1111章章 差错控制编码差错控制编码现代通信系统原理研究的问题研究的问题:11.1 11.1 概述概述11.2 11.2 纠错编码的基本原理纠错编码的基本原理 11.3 11.3 纠错编码的纠错编码的性能性能11.4 11.4 常用的简单编码常用的简单编码 11.5 11.5 线性分组码线性分组码 11.6 11.6 循环码循环码 11.7 11.7 卷积码卷积码11.8 Turbo11.8 Turbo码码11.9 11.9 低密度奇偶校验码低密度奇偶校验码11.10 11.10 网格编码调制网格编码调制 7/27/20242第第1111章章 差错控制编码差错控制编码现代通信系统原理干扰干扰乘性：均衡乘性：均衡加性：调制解调体制、发送功率、最佳接收加性：调制解调体制、发送功率、最佳接收11.1 11.1 引言引言一、编码问题的提出一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响，使由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能码元波形变坏，故传输到接收端后可能发生错判发生错判。信道信道译码译码检检/纠错编码纠错编码若还不行，则需差错控制编码。若还不行，则需差错控制编码。目的：目的：在数字通信系统中，为了提高数字通信的可靠性而采取在数字通信系统中，为了提高数字通信的可靠性而采取的编码称为的编码称为信道编码信道编码。差错可控差错可控之前：之前：为了提高数字信号传输的有效性而采取的编码称为为了提高数字信号传输的有效性而采取的编码称为信源信源编码编码。模型：模型：7/27/20243第第1111章章 差错控制编码差错控制编码现代通信系统原理二、错误的类型二、错误的类型1.1.随机性错误随机性错误 （白噪声引起）（白噪声引起）特点：特点：单个错，错误之间不相关。主要出现在无记忆信道。单个错，错误之间不相关。主要出现在无记忆信道。2.2.突发性错误突发性错误 (脉冲干扰引起）脉冲干扰引起）特点：特点：成串错，错误之间有相关性成串错，错误之间有相关性。主要出现在有记忆信。主要出现在有记忆信道。错误传播。道。错误传播。3.3.混合性错误混合性错误7/27/20244第第1111章章 差错控制编码差错控制编码现代通信系统原理三、差错控制的方式三、差错控制的方式1.检错重发检错重发(ARQ)收收发发可检错的码可检错的码特点特点特点特点:1）双向通道）双向通道 2）通信效率低）通信效率低 3）不适于实时通信）不适于实时通信 4）编、译码设备简单）编、译码设备简单 5）编码效率高）编码效率高总码元总码元(n bit)=信元信元(k bit)+督元督元(r bit)。只检不纠，有错自只检不纠，有错自动要求重发。动要求重发。督元长度低！督元长度低！7/27/20245第第1111章章 差错控制编码差错控制编码现代通信系统原理2.2.前向纠错前向纠错(FEC)(FEC)收收发发可纠错的码可纠错的码特点：特点：特点：特点：1）只需单向信道）只需单向信道省信道！省信道！2）通信效率高；）通信效率高；3）适于实时传输；）适于实时传输；4)译码设备复杂；译码设备复杂；5)编码效率低。编码效率低。检错并纠错检错并纠错督元变长！督元变长！7/27/20246第第1111章章 差错控制编码差错控制编码现代通信系统原理3.3.反馈检验法反馈检验法收收发发原理：原理：收端将信码原封不动地转发回发端，并与原发送信收端将信码原封不动地转发回发端，并与原发送信码相比较：发现错重发；否则：码相比较：发现错重发；否则：PASS特点特点:1）需要双向通道；）需要双向通道；2）收发设备简单；）收发设备简单；3）传输效率低（最低）。）传输效率低（最低）。7/27/20247第第1111章章 差错控制编码差错控制编码现代通信系统原理11.2 11.2 纠错编码的基本原理纠错编码的基本原理一一.基本思想基本思想信元信元督元督元信元信元督元督元信元和督元有一的函数关系，插入督元的过程就是一种编码的信元和督元有一的函数关系，插入督元的过程就是一种编码的过程，接收端可检错纠错。显然，过程，接收端可检错纠错。显然，传输效率传输效率（引入冗余码）（引入冗余码）例：例：天气预报天气预报 信元信元 督元督元 0 0 0 晴晴 0 1 1 云云 1 0 1 阴阴 1 1 0 雨雨三位码元有三位码元有23=8种组合，实际使种组合，实际使用了用了22=4=4种种许用码组。许用码组。其余其余 001，010，100，111 为为禁禁用码组用码组。检错能力：检错能力：可检错奇数个错；可检错奇数个错；纠错能力：纠错能力：无。无。7/27/20248第第1111章章 差错控制编码差错控制编码现代通信系统原理例：例：天气预报，可预报天晴天气预报，可预报天晴信元信元 督元督元 0 0 0 1 1 1冗余量加大，禁用码组比例提高。冗余量加大，禁用码组比例提高。检错能力：检错能力：检检2；纠错能力：纠错能力：纠纠1 1。纠检不兼得！纠检不兼得！许用码组许用码组2个，禁用码组个，禁用码组6个个晴晴阴阴7/27/20249第第1111章章 差错控制编码差错控制编码现代通信系统原理二二.纠错编码的分类纠错编码的分类1.线性码线性码和非线性码和非线性码2.分组码分组码、卷积码和循环码、卷积码和循环码3.系统码系统码和非系统码和非系统码三三.分组码分组码定义定义:将信息码将信息码分组分组，为每信息码附加若干个监督码编码，称，为每信息码附加若干个监督码编码，称为分组码。为分组码。特点特点:在分组码中，监督码元仅监督本码组中的信息码元。在分组码中，监督码元仅监督本码组中的信息码元。符号符号:(n,k),r=n k码字码字:结构结构:an-1an-2 arar-1a0k个信元个信元r个督元个督元码长码长n7/27/202410第第1111章章 差错控制编码差错控制编码现代通信系统原理四四.码组的重量和码距及纠错能力码组的重量和码距及纠错能力1.1.重量重量 码组中非码组中非0元素的个数元素的个数 例例:A=(10110)码重码重=32.2.码距码距 两两码组对应位上数值不同的个数，记为两两码组对应位上数值不同的个数，记为d。最小码距最小码距:某种编码中各个码组间距离某种编码中各个码组间距离 的最小值，记做的最小值，记做d0 d0=dmin码距的几何意义码距的几何意义:(n=3)各顶点各顶点沿立方体各边行走的几何距离。沿立方体各边行走的几何距离。码元值：码元值：每一码组的三个码元值，每一码组的三个码元值，就是此立方体各顶点的座标（就是此立方体各顶点的座标（a2a1a0）最小码距最小码距:17/27/202411第第1111章章 差错控制编码差错控制编码现代通信系统原理前例中：前例中：天气预报天气预报 信元信元 督元督元 0 0 0 晴晴 0 1 1 云云 1 0 1 阴阴 1 1 0 雨雨四个许用码组之间的距离均为四个许用码组之间的距离均为2。Why?摈弃摈弃d=1的码禁用码组。的码禁用码组。许用码组最小码距愈大，抗干扰许用码组最小码距愈大，抗干扰能力愈强！能力愈强！确定最小码距的目的：确定最小码距的目的：决定编码的检纠错能力。决定编码的检纠错能力。7/27/202412第第1111章章 差错控制编码差错控制编码现代通信系统原理3.d0与纠检错能力与纠检错能力1)若要求检测若要求检测e个错个错,则则 d0e+12)若要求纠正若要求纠正t个错个错,则则 d02t+13)若要检测若要检测e纠正纠正t 个错（同时），则个错（同时），则4)d0e+t+1,且且et码距与检错和纠错能力的关系：码距与检错和纠错能力的关系：t t 1 1 t te e7/27/202413第第1111章章 差错控制编码差错控制编码现代通信系统原理0 1 2 30 1 2 3A BA Bd d0 00 1 2 3 4 50 1 2 3 4 5A BA Bt td0A BA Bt 1 1 te e7/27/202414第第1111章章 差错控制编码差错控制编码现代通信系统原理11.4 11.4 常用的简单编码常用的简单编码属于分组码一类。简单、实用。属于分组码一类。简单、实用。11.4.1 11.4.1 奇偶监督码奇偶监督码满足满足:偶监督码：偶监督码：码组中码组中1的个数为偶数；的个数为偶数；奇监督码：奇监督码：码组中码组中1的个数为奇数。的个数为奇数。检错能力检错能力:所有奇数个错。所有奇数个错。一半！应用非常多。一半！应用非常多。编码效率编码效率:7/27/202415第第1111章章 差错控制编码差错控制编码现代通信系统原理1.11.4.2 二维奇偶监督码二维奇偶监督码进行横、纵向监督进行横、纵向监督例例:10 0 0 0 121 1 1 0 1 031 0 0 1 140 1 0 1 0 050 0 0 0 1 160 1 0 1 170 1 0 1 0横横向向监监督督纵纵纵纵 向向向向 监监监监 督督督督纠检错能力纠检错能力:1)仍可检错奇数个错仍可检错奇数个错2)还可检错偶数个错还可检错偶数个错3)可纠正一些错码可纠正一些错码 适于检测突发性错误适于检测突发性错误7/27/202416第第1111章章 差错控制编码差错控制编码现代通信系统原理1.1.11.4.3 11.4.3 横比码横比码(等重码等重码)主要用在电传机主要用在电传机编码特点：编码特点：每个码组中每个码组中“1”与与“0”的比值是恒定的。的比值是恒定的。例例:码重为码重为31.0 1 0 1 11.0 1 0 1 12.2.1 1 0 0 1 1 1 0 0 13.3.1 0 1 1 0 1 0 1 1 0许用码组许用码组:C C3 35 5=10=10禁用码组禁用码组:2 25 5-10=22-10=22检错能力：检错能力：可检测所有奇数个码元的错和部分偶数个码元可检测所有奇数个码元的错和部分偶数个码元的错，但不能检测码组中的错，但不能检测码组中“1”变为变为“0”与与“0”变为变为“1”的错码数目相同的那些偶数错码。的错码数目相同的那些偶数错码。编码效率：编码效率：7/27/202417第第1111章章 差错控制编码差错控制编码现代通信系统原理例：例：n=10,则则 k=5信元码信元码 监督码监督码 合成码合成码 校验码校验码1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 01 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 接收端的检测接收端的检测 （合成码合成码）校验码：校验码：信息位中有奇数个信息位中有奇数个1：校验码合成码：校验码合成码 信息位中有偶数个信息位中有偶数个1：校验码合成码的反码：校验码合成码的反码11.4.4 11.4.4 正反码正反码编码规则编码规则:信息位信息位(n/2)中有中有奇奇数个数个“1”，则监督位与信息位，则监督位与信息位相同；相同；信息位信息位(n/2)中有中有偶偶数个数个“1”，则监督位是信息位的，则监督位是信息位的反码。反码。7/27/202418第第1111章章 差错控制编码差错控制编码现代通信系统原理例：例：n=10,则则 k=5信元码信元码 监督码监督码 合成码合成码 校验码校验码1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 01 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 11 0 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 接收端的检测接收端的检测 （合成码合成码）校验码：校验码：信息位中有奇数个信息位中有奇数个1：校验码合成码：校验码合成码 信息位中有偶数个信息位中有偶数个1：校验码合成码的反码：校验码合成码的反码编码规则编码规则:信息位信息位(n/2)中有中有奇奇数个数个“1”，则监督位与信息位，则监督位与信息位相同；相同；信息位信息位(n/2)中有中有偶偶数个数个“1”，则监督位是信息位的，则监督位是信息位的反码。反码。错码的位置：错码的位置：校验码中：校验码中：1）4个个“1”，一个，一个“0”，信息位错一个，位置，信息位错一个，位置“0”处；处；2）4个个“0”，一个，一个“1”，监督位错一个，位置，监督位错一个，位置“1”处；处；3）其他：错不止一个。其他：错不止一个。7/27/202419第第1111章章 差错控制编码差错控制编码现代通信系统原理11.5 11.5 线性分组码线性分组码定义：定义：若分组码（若分组码（n,k）,督元与信元的关系可用一线性方程组督元与信元的关系可用一线性方程组来描述，则该分组码（来描述，则该分组码（n,k）称为线性分组码。）称为线性分组码。11.5.1 11.5.1 汉明码汉明码 能纠一位错的线性分组码。能纠一位错的线性分组码。定义：定义：是一种是一种能纠正一位错能纠正一位错码，且编码效率较高的线性分组码，且编码效率较高的线性分组码。码。最小码距：最小码距：d0=31.构造原理构造原理考察：考察：定义一个监督方程（监督关系式、偶监督）：定义一个监督方程（监督关系式、偶监督）：由于一位由于一位校正子校正子只有两种取值，故只能表示有错或无错，不只有两种取值，故只能表示有错或无错，不能指出错码的位置。能指出错码的位置。7/27/202420第第1111章章 差错控制编码差错控制编码现代通信系统原理推想：推想：如果监督位增加一位（即变成两位），则可增加一个类如果监督位增加一位（即变成两位），则可增加一个类似于上式的监督关系，即可获得两个校正子，于是可有似于上式的监督关系，即可获得两个校正子，于是可有S S1 1 S S2 20 00 11 0 21 1无错无错可指示一个错码可能出现的可指示一个错码可能出现的位置，共有位置，共有22-1=3 个位置。个位置。7/27/202421第第1111章章 差错控制编码差错控制编码现代通信系统原理再推广：再推广：S S1 1 S S2 2 S Sr r0 0 .00 0 .11 1.1 1无错无错2r-1 个错的个错的可能位置可能位置显然：显然：要求要求 2r-1n（n=k+r），则可指示（仅一位错时），则可指示（仅一位错时）任一错码的位置包括信元、督元。任一错码的位置包括信元、督元。或：或：2rk+r+1可指示一个错码可能出现的可指示一个错码可能出现的2r-1个位置。个位置。7/27/202422第第1111章章 差错控制编码差错控制编码现代通信系统原理2.2.例例:构造构造k=4 k=4 的汉明码的汉明码（1）确定）确定 r由由 2r k+r+1 得得 r=3，则，则 n=k+r=7(7,4)分组码分组码（2 2）写出校正子的编码表）写出校正子的编码表7/27/202423第第1111章章 差错控制编码差错控制编码现代通信系统原理（2）写出校正子的编码表）写出校正子的编码表 r=3 共有共有3个校正子个校正子 S1 S2 S3 错码位置错码位置 S1 S2 S3 错码位置错码位置0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a51 0 0 a2 1 1 1 a6 0 1 1 a3 0 0 0 无错无错（3）由校正子编码表得由校正子编码表得监督方程组监督方程组校正子和哪些码元构成偶监校正子和哪些码元构成偶监督关系督关系若若 S1S2S3=000 时时,即无错得即无错得校验方程校验方程:偶监督关系校正子编码表不是唯校正子编码表不是唯一的一的。7/27/202424第第1111章章 差错控制编码差错控制编码现代通信系统原理得得校验方程校验方程:即实际上确定了即实际上确定了督元和信元之间的关系督元和信元之间的关系:校验方程督信关系有了校正子编码表，督元不是随便选的！有了校正子编码表，督元不是随便选的！（表的编制不是唯一的）（表的编制不是唯一的）（4）给定了信元给定了信元a6a5a4a3,可由可由“督信关系”确定督元确定督元全部全部(7,4)码组。码组。7/27/202425第第1111章章 差错控制编码差错控制编码现代通信系统原理（4）给定了信元给定了信元a6a5a4a3,可确定督元全部可确定督元全部(7,4)码组码组7/27/202426第第1111章章 差错控制编码差错控制编码现代通信系统原理11.5.2 11.5.2 线性分组码线性分组码一般性讨论一般性讨论1.1.线性方程组和监督方程线性方程组和监督方程从校验方程入手从校验方程入手写成矩阵式写成矩阵式:1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6a5a4a3a2a1a0校验方程来自编码表7/27/202427第第1111章章 差错控制编码差错控制编码现代通信系统原理可见：可见：H一旦确定，督元和信元之间的关系也就确定了。一旦确定，督元和信元之间的关系也就确定了。若若:则称则称H为为典型阵典型阵，一般，一般，H总可以化为典型阵。总可以化为典型阵。1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6a5a4a3a2a1a07/27/202428第第1111章章 差错控制编码差错控制编码现代通信系统原理2.2.生成矩阵生成矩阵矩阵形式矩阵形式:从督信方程入手从督信方程入手由由7/27/202429第第1111章章 差错控制编码差错控制编码现代通信系统原理写成行阵形式写成行阵形式:其中其中 Q=PT。上式表明：上式表明：信息位给定后，就产生了监督位！信息位给定后，就产生了监督位！进一步，令进一步，令生成矩阵生成矩阵 G=Ik Q 则，码组行阵则，码组行阵 A=a6a5a4a3 G Q能生成督元能生成督元G才生成线性分组码才生成线性分组码如何装配：信元督元？如何装配：信元督元？7/27/202430第第1111章章 差错控制编码差错控制编码现代通信系统原理例：例：生成矩阵生成矩阵讨论：讨论：由具有由具有 Ik Q 形式的生成矩阵称为形式的生成矩阵称为典型生成阵典型生成阵。由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位不变，监督位附中，信息位不变，监督位附加其后这种码称为加其后这种码称为系统码系统码。码组行阵：码组行阵：督元由相应的信息位决定！督元由相应的信息位决定！7/27/202431第第1111章章 差错控制编码差错控制编码现代通信系统原理一般形式一般形式:A=an-1an-2ar G 3.G 和和 H 的关系的关系由由 Q=PT 或或 P=QT 则则:H=P Ir G=Ik Q 综上：综上：线性分组码的编码，就是根据其监督阵线性分组码的编码，就是根据其监督阵H或生成阵或生成阵G将将长为长为k的信息码编成长为的信息码编成长为n的码组。的码组。7/27/202432第第1111章章 差错控制编码差错控制编码现代通信系统原理4.4.线性分组码的纠错译码过程线性分组码的纠错译码过程怎样由含有错误的接收码组中的接收码组中恢复正确。怎样由含有错误的接收码组中的接收码组中恢复正确。（1 1）错误图样）错误图样设：设：发码组为发码组为A,接受码组为接受码组为B 则则 B A=E (模模 2)错误行阵或错误行阵或错误图样错误图样：E=en-1en-2e0 例例:A=1 1 1 1 1 1 1 B=1 0 0 1 1 0 1 则则 E=0 1 1 0 0 1 0 7/27/202433第第1111章章 差错控制编码差错控制编码现代通信系统原理（2 2）校正子（或称译码伴随式）校正子（或称译码伴随式）B B=A A+E E 代入上式，得代入上式，得结论：结论：校正子校正子S仅于错误图案有关，与发送码组无关。仅于错误图案有关，与发送码组无关。7/27/202434第第1111章章 差错控制编码差错控制编码现代通信系统原理由收到的码组由收到的码组B，按式：，按式：BHT=SS由由 S=EHT E按按B+E=A A由由A 原始信息原始信息（3 3）纠错译码过程）纠错译码过程 7/27/202435第第1111章章 差错控制编码差错控制编码现代通信系统原理5.5.线性分组码的重要性质线性分组码的重要性质（1 1）封闭性）封闭性 设：设：A1、A2 分别为一线性分组码的任意两个许用码组。分别为一线性分组码的任意两个许用码组。则：则：A1+A2 仍为该线性分组码的许用码组。仍为该线性分组码的许用码组。证：证：由假设知由假设知A1HT=0、A2HT=0 所以所以A1HT+A2HT=（A1+A2）HT0 即即A1+A2也是一个码组。也是一个码组。结论：结论：线性码组中任意两个码字之和，仍为该线性码组之码字。线性码组中任意两个码字之和，仍为该线性码组之码字。（2 2）线性分组码的最小码距）线性分组码的最小码距即为该码的最小重量即为该码的最小重量:d0=Wmin（除全（除全0码组）码组）证：证：由封闭性得，两个码组之间的距离（之差），必是另一码由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！组的重量。故最小码距即是码的最小重量！7/27/202436第第1111章章 差错控制编码差错控制编码现代通信系统原理11.6 11.6 循环码循环码 仍属于线性分组码仍属于线性分组码特点特点:编译码设备简单，检纠错能力强。编译码设备简单，检纠错能力强。11.6.1 11.6.1 循环码的原理循环码的原理具有线性分组码的所有性质之外，还具有循环性：具有线性分组码的所有性质之外，还具有循环性：循环码中任循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。一许用码组经过循环移位后，所得到的码组仍然是许用码组。7/27/202437第第1111章章 差错控制编码差错控制编码现代通信系统原理1.码多项式码多项式 T(x)2.（1）定义）定义为了利用代数理论研究循环码，可以将码组用代数多项是为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。来表示，这个多项式被称为码多项式。设：设：许用循环码许用循环码A=(an-1 an-2 a1 a0)，则：则：它的码多项式表示为：它的码多项式表示为：其中：其中：xi仅是码元位置的标记。仅是码元位置的标记。码字与码多项式一一对应！码字与码多项式一一对应！7/27/202438第第1111章章 差错控制编码差错控制编码现代通信系统原理例例:设设(7,3)循环码组为循环码组为 (0 1 1 1 0 0 1)则相应则相应码多项式为：码多项式为：反之，由码多项式易得出码组：反之，由码多项式易得出码组：(0 1 1 1 0 0 1)可由码组直接写出。可由码组直接写出。7/27/202439第第1111章章 差错控制编码差错控制编码现代通信系统原理（2 2）码多项式的按模运算）码多项式的按模运算1）整数的按模运算）整数的按模运算若一个整数若一个整数m可以表示为可以表示为:则在模则在模n运算下，有运算下，有mp（模（模n）。）。例：例：同样对于多项式而言，也有类似按模运算。同样对于多项式而言，也有类似按模运算。7/27/202440第第1111章章 差错控制编码差错控制编码现代通信系统原理其中：其中：商商Q(x)为多项式，余数为多项式，余数R(x)的幂次低于的幂次低于N(x)的幂次。的幂次。例例:求求 x4+x2+1 按模按模 x3+1 运算的余式运算的余式 R(x)2 2）码多项式的按模运算）码多项式的按模运算若若则则7/27/202441第第1111章章 差错控制编码差错控制编码现代通信系统原理 3 3）循环性）循环性在循环码中，若在循环码中，若T(x)是一个长为是一个长为n的许用码组，则的许用码组，则xiT(x)在按在按模模xn+1运算下运算下，亦是，亦是一个许用码组。即一个许用码组。即设：设：T(x)是长为是长为n的许用码组多项式的许用码组多项式则：则：T(x)T(x)仍为该码组中的一个码多项式。仍为该码组中的一个码多项式。例例例例:（7，3）码）码T(x)=x6+x5+x2+1 (1 1 0 0 1 0 11 1 0 0 1 0 1)前码组循环左移前码组循环左移3位！位！7/27/202442第第1111章章 差错控制编码差错控制编码现代通信系统原理由此类推由此类推可见：可见：一个长为一个长为n的循环码，必为按模（的循环码，必为按模（xn+1）运算的一个余）运算的一个余式。式。“模模”运算过了。运算过了。7/27/202443第第1111章章 差错控制编码差错控制编码现代通信系统原理2.生成多项式生成多项式g(x)（1 1）存在性）存在性 (n，k)循环码中循环码中有且仅有有且仅有一个一个g(x)g(x)=xn-k+1特点特点:最高的次数最高的次数:n-k=r；最高最高次项和次项和常数常数项系数必为项系数必为1 。在循环码中，除了全在循环码中，除了全0码组码组外，再也没有连续外，再也没有连续k位均为位均为0的码组。即连的码组。即连0长度最多长度最多为为k-1位！位！这唯一的这唯一的n-k次多项式称为次多项式称为生成多项式生成多项式，记为，记为g(x)！7/27/202444第第1111章章 差错控制编码差错控制编码现代通信系统原理（2）生成多项式）生成多项式 g(x)与生成矩阵与生成矩阵 G(x)的关系的关系A=an-1ar GG=Ik Q 生成矩阵生成矩阵G的每一行都的每一行都是一个码组；是一个码组；G是是k行行n列列矩阵，矩阵，只要找到只要找到k个已知码组，个已知码组，就能构成生成矩阵就能构成生成矩阵G！生成多项式确定后，则生成多项式确定后，则g(x)、x g(x)、xk-1 g(x)都是码组，都是码组，且这且这k个码组信息无关，因此可以用来构成生成矩阵。个码组信息无关，因此可以用来构成生成矩阵。g(x)确定了确定了G(x)也就确定了也就确定了整个码组即确定！整个码组即确定！7/27/202445第第1111章章 差错控制编码差错控制编码现代通信系统原理例例:(7，3)循环码，循环码，g(x)=x4+x2+x+1 求求 典型生成矩阵典型生成矩阵解解:典型阵典型阵:可方便地直接写成码组形式可方便地直接写成码组形式7/27/202446第第1111章章 差错控制编码差错控制编码现代通信系统原理（3）生成多项式生成多项式g(x)与与 码多项式码多项式T(x)的关系的关系（7，3）表明：表明：所有所有T(x)都可以被都可以被g(x)整除，而且任一次数不大于整除，而且任一次数不大于(k-1)的的多项式乘以多项式乘以g(x)都是码多项式。都是码多项式。h(x)为不大于为不大于(k-1)的多项式！的多项式！7/27/202447第第1111章章 差错控制编码差错控制编码现代通信系统原理依据依据:g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。证：证：任一循环多项式任一循环多项式T(x)都是都是g(x)的倍式，即的倍式，即而生成而生成多项式多项式g(x)本身也是一个码组，即有本身也是一个码组，即有由于码组由于码组T(x)为一为一（n-k）次多项式，故次多项式，故xkT(x)为一为一n次多次多项式。由项式。由知，知，xkT(x)在模在模（xn+1）的运算下，亦的运算下，亦为一码组，故可写成为一码组，故可写成（4）如何寻找如何寻找g(x)7/27/202448第第1111章章 差错控制编码差错控制编码现代通信系统原理上式左端分子和分母都是上式左端分子和分母都是n次多项式，故商次多项式，故商Q(x)1，因此上，因此上式可化成即式可化成即将将T(x)=h(x)g(x)、T(x)=g(x)代入，并化简，得代入，并化简，得表明表明:g(x)应该是应该是xn+1的一个因式！的一个因式！结论结论:g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。7/27/202449第第1111章章 差错控制编码差错控制编码现代通信系统原理（4）如何寻找如何寻找g(x)依据依据:g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。如如(x x7 7+1)=(+1)=(x x+1)(+1)(x x3 3+x x2 2+1)(+1)(x x3 3+x x+1)+1)n n=7=7（7 7，4 4）：）：）：）：x x3 3+x x2 2+1+1、x x3 3+x x+1+1（7 7，3 3）：）：）：）：(x x+1)(+1)(x x3 3+x x2 2+1)+1)、(x x+1)(+1)(x x3 3+x x+1)+1)（7 7，6 6）：）：）：）：x x+1+17/27/202450第第1111章章 差错控制编码差错控制编码现代通信系统原理例例例例:（7，3）循环码有多项式如下，找出（循环码有多项式如下，找出（7，3）码的生成）码的生成多项式多项式g(x)。（1）x4+x3+x（2）x3+x2+1 （3）x+1 （4）x4+x2+x+1 （5）x4+x+1解解解解:依据依据 r=7-3=4，常数项不为零，有，常数项不为零，有 （4）x4+x2+x+1 （5）x4+x+1还须证其是不是还须证其是不是xn+1=x7+1的因子的因子?x7+1=(x x4 4+x x2 2+x+1)+x+1)(x3+x+1)+0 0 x7+1=(x x4 4+x x+1)+1)(x3+1)+(x x2 2+x x)故故故故:仅有仅有 x x4 4+x x2 2+x x+1+1 为生成多项式为生成多项式 g g(x x)。7/27/202451第第1111章章 差错控制编码差错控制编码现代通信系统原理11.6.211.6.2 循环码的编码方法循环码的编码方法1.(n，k)循环码的编码步骤循环码的编码步骤 设设:已选好已选好g(x)，给定信息码组，给定信息码组m(x):（1）作）作xn-km(x)实际上是把信息码后附加上（实际上是把信息码后附加上（n-k）个）个“0”。（2）作）作（3）编码输出系统循环码多项式）编码输出系统循环码多项式T(x)为：为：得到了得到了r(x)。由于循环码多项式由于循环码多项式T(x)都可被都可被g(x)整除，也就是：整除，也就是：7/27/202452第第1111章章 差错控制编码差错控制编码现代通信系统原理例例:(7，3)循环码，选循环码，选 g(x)=x4+x2+x+1 设设 m(x)=x2+x+1(1 1 1)解解:2.2.编码的电路编码的电路7/27/202453第第1111章章 差错控制编码差错控制编码现代通信系统原理上述三步编码过程，在硬件实现时，可以利用除法电路（曹上述三步编码过程，在硬件实现时，可以利用除法电路（曹志刚志刚p344348）来实现。）来实现。编码的电路编码的电路7/27/202454第第1111章章 差错控制编码差错控制编码现代通信系统原理工作过程：工作过程：信息输入时，开关合信息输入时，开关合2：输入码一方面输入除法器，另一方面输入码一方面输入除法器，另一方面直接输出，在信息位全部进入除法器后直接输出，在信息位全部进入除法器后开关合开关合1：输出端接到移位寄存器，将移位寄存器中存储的余输出端接到移位寄存器，将移位寄存器中存储的余项依次输出，同时切断反馈线。项依次输出，同时切断反馈线。系统码！系统码！7/27/202455p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings结束语讲师：XXXXXX XX年XX月XX日