1、第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-191通通 信信 原原 理理 电电 子子 教教 案案第第1111章章 差错控制编码差错控制编码 西西 北北 工工 业业 大大 学学（2008.6）第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-192研究的问题研究的问题: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
2、11.7 卷积码卷积码 11.8 Turbo11.8 Turbo码码 11.9 11.9 低密度奇偶校验码低密度奇偶校验码 11.10 11.10 网格编码调制网格编码调制 第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-193干扰干扰乘性：均衡乘性：均衡加性：调制解调体制、发送功率、最佳接收加性：调制解调体制、发送功率、最佳接收11.1 11.1 引言引言一、编码问题的提出一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响，使由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能码元波形变坏，故传输到接收端后可能发
3、生错判发生错判。信道信道译码译码检检/纠错编码纠错编码若还不行，则需差错控制编码。若还不行，则需差错控制编码。目的：目的：在数字通信系统中，为了提高数字通信的可靠性而采在数字通信系统中，为了提高数字通信的可靠性而采取的编码称为取的编码称为信道编码信道编码。差错可控差错可控之前：之前：为了提高数字信号传输的有效性而采取的编码称为为了提高数字信号传输的有效性而采取的编码称为信信源编码源编码。模型：模型：第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-194二、错误的类型二、错误的类型1.1.随机性错误随机性错误 （白噪声引起）（白噪声引起）特点：特点：单个错，错误之间不
4、相关。主要出现在无记忆信道。单个错，错误之间不相关。主要出现在无记忆信道。2.2.突发性错误突发性错误 (脉冲干扰引起）脉冲干扰引起）特点：特点：成串错，错误之间有相关性成串错，错误之间有相关性。主要出现在有记忆信。主要出现在有记忆信道。错误传播。道。错误传播。3.3.混合性错误混合性错误第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-195三、差错控制的方式三、差错控制的方式1.检错重发检错重发(ARQ)收收发发可检错的码可检错的码:1）双向通道）双向通道 2）通信效率低）通信效率低 3）不适于实时通信）不适于实时通信 4）编、译码设备简单）编、译码设备简单 5）
5、编码效率高）编码效率高总码元总码元(n bit)=信元信元(k bit)+督元督元(r bit)。kRn只检不纠，有错自只检不纠，有错自动要求重发。动要求重发。督元长度低！督元长度低！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1962.2.前向纠错前向纠错 (FEC)(FEC)收收发发可纠错的码可纠错的码 1）只需单向信道）只需单向信道省信道！省信道！2）通信效率高；）通信效率高；3）适于实时传输；）适于实时传输；4)译码设备复杂；译码设备复杂；5)编码效率低。编码效率低。检错并纠错检错并纠错督元变长！督元变长！第第11 11章章 差错控制编码差错控制编码现代
6、通信系统原理2022-12-1973.3.反馈检验法反馈检验法收收发发原理：原理：收端将信码原封不动地转发回发端，并与原发送信收端将信码原封不动地转发回发端，并与原发送信码相比较：发现错重发；否则：码相比较：发现错重发；否则：PASS特点特点:1）需要双向通道；）需要双向通道；2）收发设备简单；）收发设备简单；3）传输效率低（最低）。）传输效率低（最低）。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19811.2 11.2 纠错编码的基本原理纠错编码的基本原理一一.基本思想基本思想信元信元督元督元信元信元督元督元信元和督元有一的函数关系，插入督元的过程就是一种编
7、码的信元和督元有一的函数关系，插入督元的过程就是一种编码的过程，接收端可检错纠错。显然，过程，接收端可检错纠错。显然，传输效率传输效率（引入冗余码）（引入冗余码）例：例：天气预报天气预报 信元信元 督元督元 0 0 0 晴晴 0 1 1 云云 1 0 1 阴阴 1 1 0 雨雨三位码元有三位码元有23=8种组合，实际使种组合，实际使用了用了22=4=4种种许用码组。许用码组。其余其余 001，010，100，111 为为禁禁用码组用码组。检错能力：检错能力：可检错奇数个错；可检错奇数个错；纠错能力：纠错能力：无。无。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1
8、99例：例：天气预报，可预报天晴天气预报，可预报天晴信元信元 督元督元 0 0 0 1 1 1冗余量加大，禁用码组比例提高。冗余量加大，禁用码组比例提高。检错能力：检错能力：检检2；纠错能力：纠错能力：纠纠1 1。纠检不兼得！纠检不兼得！许用码组许用码组2个，禁用码组个，禁用码组6个个晴晴阴阴第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1910二二.纠错编码的分类纠错编码的分类1.线性码线性码和非线性码和非线性码2.分组码分组码、卷积码和循环码、卷积码和循环码3.系统码系统码和非系统码和非系统码三三.分组码分组码定义定义:将信息码将信息码分组分组，为每信息码附加
9、若干个监督码编码，称，为每信息码附加若干个监督码编码，称为分组码。为分组码。特点特点:在分组码中，监督码元仅监督本码组中的信息码元。在分组码中，监督码元仅监督本码组中的信息码元。符号符号:(n,k),r=n k码字码字:结构结构:an-1an-2 arar-1a0k个信元个信元r个督元个督元码长码长n1210nnrrAaaa aa第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19114码组的重量和码距及纠错能力码组的重量和码距及纠错能力1.1.重量重量 码组中非码组中非0元素的个数元素的个数 例例:A=(10110)码重码重=32.2.码距码距 两两码组对应位上数
10、值不同的个数，记为两两码组对应位上数值不同的个数，记为d。最小码距最小码距:某种编码中各个码组间距离某种编码中各个码组间距离 的最小值，记做的最小值，记做d0 d0=dmin码距的几何意义码距的几何意义:(n=3)各顶点各顶点沿立方体各边行走的几何距离。沿立方体各边行走的几何距离。码元值：码元值：每一码组的三个码元值，每一码组的三个码元值，就是此立方体各顶点的座标（就是此立方体各顶点的座标（a2a1a0）最小码距最小码距:1第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1912前例中：前例中：天气预报天气预报 信元信元 督元督元 0 0 0 晴晴 0 1 1 云云
11、 1 0 1 阴阴 1 1 0 雨雨四个许用码组之间的距离均为四个许用码组之间的距离均为2。Why?摈弃摈弃d=1的码禁用码组。的码禁用码组。许用码组最小码距愈大，抗干扰许用码组最小码距愈大，抗干扰能力愈强！能力愈强！确定最小码距的目的：确定最小码距的目的：决定编码的检纠错能力。决定编码的检纠错能力。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19133.d0与纠检错能力与纠检错能力1)若要求检测若要求检测e个错个错,则则 d0e+12)若要求纠正若要求纠正t个错个错,则则 d02t+13)若要检测若要检测e纠正纠正t 个错（同时），则个错（同时），则 d0e+
12、t+1,且且et码距与检错和纠错能力的关系：码距与检错和纠错能力的关系：第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1914d0第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-191511.4 11.4 常用的简单编码常用的简单编码属于分组码一类。简单、实用。属于分组码一类。简单、实用。11.4.1 11.4.1 奇偶监督码奇偶监督码满足满足:1231010nnnaaaaa 督元信元奇数监督码偶数监督码偶监督码：偶监督码：码组中码组中1的个数为偶数；的个数为偶数；奇监督码：奇监督码：码组中码组中1的个数为奇数。的个数为奇数。检错能力检
13、错能力:所有奇数个错。所有奇数个错。一半！应用非常多。一半！应用非常多。编码效率编码效率:1,!,knRnnnk高码长信元数第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-191611.4.2 二维奇偶监督码二维奇偶监督码进行横、纵向监督进行横、纵向监督例例:1 0 0 0 0 11 1 1 0 1 02 1 0 0 1 10 1 0 1 0 00 0 0 0 1 13 0 1 0 1 10 1 0 1 0横横向向监监督督纠检错能力纠检错能力:1)仍可检错奇数个错仍可检错奇数个错2)还可检错偶数个错还可检错偶数个错3)可纠正一些错码可纠正一些错码 适于检测突发性错误
14、适于检测突发性错误第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-191711.4.3 11.4.3 横比码横比码(等重码等重码)主要用在电传机主要用在电传机编码特点：编码特点：每个码组中每个码组中“1”与与“0”的比值是恒定的。的比值是恒定的。例例:码重为码重为3许用码组许用码组:禁用码组禁用码组:检错能力：检错能力：可检测所有奇数个码元的错和部分偶数个码元可检测所有奇数个码元的错和部分偶数个码元的错，但不能检测码组中的错，但不能检测码组中“1”变为变为“0”与与“0”变为变为“1”的的错码数目相同的那些偶数错码。错码数目相同的那些偶数错码。编码效率：编码效率：3
15、25log0.66CRn第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1918例：例：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 正反码
16、正反码编码规则编码规则:信息位信息位(n/2)中有中有奇奇数个数个“1”，则监督位与信息位，则监督位与信息位相同；相同；信息位信息位(n/2)中有中有偶偶数个数个“1”，则监督位是信息位的，则监督位是信息位的反码。反码。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1919例：例：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
17、0 0 1 0 0 0 接收端的检测接收端的检测 （合成码合成码）校验码：校验码：信息位中有奇数个信息位中有奇数个1：校验码合成码：校验码合成码 信息位中有偶数个信息位中有偶数个1：校验码合成码的反码：校验码合成码的反码信息位监督位合成码组编码规则编码规则:信息位信息位(n/2)中有中有奇奇数个数个“1”，则监督位与信息位，则监督位与信息位相同；相同；信息位信息位(n/2)中有中有偶偶数个数个“1”，则监督位是信息位的，则监督位是信息位的反码。反码。错码的位置：错码的位置：校验码中：校验码中：1）4个个“1”，一个，一个“0”，信息位错一个，位置信息位错一个，位置“0”处；处；2）4个个“0”
18、，一个，一个“1”，监督位错一个，位置监督位错一个，位置“1”处；处；3）其他：错不止一个。其他：错不止一个。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-192011.5 11.5 线性分组码线性分组码定义：定义：若分组码（若分组码（n,k）,督元与信元的关系可用一线性方程组督元与信元的关系可用一线性方程组来描述，则该分组码（来描述，则该分组码（n,k）称为线性分组码。）称为线性分组码。11.5.1 11.5.1 汉明码汉明码 能纠一位错的线性分组码。能纠一位错的线性分组码。定义：定义：是一种是一种能纠正一位错能纠正一位错码，且编码效率较高的线性分组码，且编码效
19、率较高的线性分组码。码。最小码距：最小码距：d0=31.构造原理构造原理考察：考察：定义一个监督方程（监督关系式、偶监督）：定义一个监督方程（监督关系式、偶监督）：1231001nnnaaaaaS 校正子督元信元无错有错由于一位由于一位校正子校正子只有两种取值，故只能表示有错或无错，不只有两种取值，故只能表示有错或无错，不能指出错码的位置。能指出错码的位置。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1921推想：推想：如果监督位增加一位（即变成两位），则可增加一个类如果监督位增加一位（即变成两位），则可增加一个类似于上式的监督关系，即可获得两个校正子，于是可有
20、似于上式的监督关系，即可获得两个校正子，于是可有0 00 11 0 1 1无错无错可指示一个错码可能出现的可指示一个错码可能出现的位置，共有位置，共有22-1=3 个位置。个位置。1231001nnnaaaaaS 校正子督元信元无错有错第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1922再推广：再推广：0 0 .00 0 .11 1.1 1无错无错2r-1 个错的个错的可能位置可能位置显然：显然：要求要求 2r-1n（n=k+r），则可指示（仅一位错时），则可指示（仅一位错时）任一错码的位置包括信元、督元。任一错码的位置包括信元、督元。或：或：2rk+r+111
21、2rSrrrSSS 对应对应对应对应一个督元一个监督方程一个校正子:个督元个监督方程个校正子:、可指示一个错码可能出现的可指示一个错码可能出现的2r-1个位置。个位置。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19232.2.例例:构造构造k=4 k=4 的汉明码的汉明码（1）确定）确定 r由由 2r k+r+1 得得 r=3，则，则 n=k+r=7(7,4)分组码分组码6543210Aa a a aa a a 信元督元（2 2）写出校正子的编码表）写出校正子的编码表第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1924（2）写出
22、校正子的编码表）写出校正子的编码表 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）由校正子编码表得由校正子编码表得监督方程组监督方程组校正子和哪些码元构成偶校正子和哪些码元构成偶监督关系监督关系124562135630346SaaaaSaaaaSaaaa若若 S1S2S3=000 时时,即无错得即无错得校验方程校验方程:偶监督关系校正子编码表不是唯校正子编码表不是唯一的一的。第第11 11
23、章章 差错控制编码差错控制编码现代通信系统原理2022-12-1925得得校验方程校验方程:654265316430000aaaaaaaaaaaa即实际上确定了即实际上确定了督元和信元之间的关系督元和信元之间的关系:265416530643aaaaaaaaaaaa校验方程督信关系有了校正子编码表，督元不是随便选的！有了校正子编码表，督元不是随便选的！（表的编制不是唯一的）（表的编制不是唯一的）（4）给定了信元给定了信元a6a5a4a3,可由可由“督信关系”确定督元确定督元全部全部(7,4)码组。码组。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1926（4）给定
24、了信元给定了信元a6a5a4a3,可确定督元全部可确定督元全部(7,4)码组码组265416530643aaaaaaaaaaaa第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-192711.5.2 11.5.2 线性分组码线性分组码一般性讨论一般性讨论1.1.线性方程组和监督方程线性方程组和监督方程从校验方程入手从校验方程入手654321065432106543210111010001101010011110110aaaaaaaaaaaaaaaaaaaaa 写成矩阵式写成矩阵式:1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6
25、a5a4a3a2a1a0 00000TTTHAA H记为或654265316430000aaaaaaaaaaaa校验方程来自编码表第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1928:0AH 其中码组的行距阵零矩阵监督矩阵可见：可见：H一旦确定，督元和信元之间的关系也就确定了。一旦确定，督元和信元之间的关系也就确定了。若若:H1rrkrrP则称则称H为为典型阵典型阵，一般，一般，H总可以化为典型阵。总可以化为典型阵。1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6a5a4a3a2a1a0 00000TTTHAA H记为或第
26、第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19292.2.生成矩阵生成矩阵265416530643aaaaaaaaaaaa督信关系矩阵形式矩阵形式:经由生成矩阵生由信元生成：成线性码组从督信方程入手从督信方程入手由由6251403111011011011aaaaPaaa 第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1930写成行阵形式写成行阵形式:21065436543111110101011aa aaaaaaaaaQQ 其中其中 Q=PT。上式表明：上式表明：信息位给定后，就产生了监督位！信息位给定后，就产生了监督位！进一步，令
27、进一步，令生成矩阵生成矩阵 G=Ik Q 则，码组行阵则，码组行阵 A=a6a5a4a3 G 6251403111011011011aaaaPaaa Q能生成督元能生成督元G才生成线性分组码才生成线性分组码如何装配：信元督元？如何装配：信元督元？第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1931例：例：生成矩阵生成矩阵讨论：讨论：由具有由具有 Ik Q 形式的生成矩阵称为形式的生成矩阵称为典型生成阵典型生成阵。由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位不变，监督位附中，信息位不变，监督位附加其后这种码称为加其后这种码称为系统码系统码。2106
28、5436543111110101011a a aa a a aa a a a Q1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1kGI Q6543654365436546536431 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1Aa a a a Ga a a aaaaaaaaaaaaaa 信息位不变督位附后，码组行阵：码组行阵：督元由相应的信息位决定！督元由相应的信息位决定！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1932一般形式一般形式:A=an
29、-1an-2ar G 3.G 和和 H 的关系的关系由由 Q=PT 或或 P=QT 则则:H=P Ir G=Ik Q 综上：综上：线性分组码的编码，就是根据其监督阵线性分组码的编码，就是根据其监督阵H或生成阵或生成阵G将将长为长为k的信息码编成长为的信息码编成长为n的码组。的码组。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19334.4.线性分组码的纠错译码过程线性分组码的纠错译码过程怎样由含有错误的接收码组中的接收码组中恢复正确。怎样由含有错误的接收码组中的接收码组中恢复正确。（1 1）错误图样）错误图样设：设：发码组为发码组为A,接受码组为接受码组为B 则
30、则 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 0,1,iiiiibaeba，说明无错，说明有错第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1934（2 2）校正子（或称译码伴随式）校正子（或称译码伴随式）0)TTBAAHBHS零矩阵无错（非零矩阵有错 代入上式，得代入上式，得0TTTTTBHAE HAHEHEHS结论：结论：校正子校正子S仅于错误图案有关，与发送码组无关。仅于错误图案有关，与发送码组无关。第第1
31、1 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1935由收到的码组由收到的码组B，按式：，按式：BHT=SS由由 S=EHT E按按B+E=A A由由A 原始信息原始信息（3 3）纠错译码过程）纠错译码过程 第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19365.5.线性分组码的重要性质线性分组码的重要性质（1 1）封闭性）封闭性 设：设：A1、A2 分别为一线性分组码的任意两个许用码组。分别为一线性分组码的任意两个许用码组。则：则：A1+A2 仍为该线性分组码的许用码组。仍为该线性分组码的许用码组。证：证：由假设知由假设知A1HT=0、
32、A2HT=0 所以所以A1HT+A2HT=（A1+A2）HT0 即即A1+A2也是一个码组。也是一个码组。结论：结论：线性码组中任意两个码字之和，仍为该线性码组之码字。线性码组中任意两个码字之和，仍为该线性码组之码字。（2 2）线性分组码的最小码距）线性分组码的最小码距即为该码的最小重量即为该码的最小重量:d0=Wmin（除全（除全0码组）码组）证：证：由封闭性得，两个码组之间的距离（之差），必是另一码由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！组的重量。故最小码距即是码的最小重量！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022
33、-12-193711.6 11.6 循环码循环码 仍属于线性分组码仍属于线性分组码特点特点:编译码设备简单，检纠错能力强。编译码设备简单，检纠错能力强。11.6.1 11.6.1 循环码的原理循环码的原理具有线性分组码的所有性质之外，还具有循环性：具有线性分组码的所有性质之外，还具有循环性：循环码中任循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。一许用码组经过循环移位后，所得到的码组仍然是许用码组。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19381.码多项式码多项式 T(x)（1）定义）定义为了利用代数理论研究循环码，可以将码组用代数多项是
34、为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。来表示，这个多项式被称为码多项式。设：设：许用循环码许用循环码A=(an-1 an-2 a1 a0)，则：则：它的码多项式表示为：它的码多项式表示为：121210nnnnT xaxaxa xa其中：其中：xi仅是码元位置的标记。仅是码元位置的标记。码字与码多项式一一对应！码字与码多项式一一对应！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1939例例:设设(7,3)循环码组为循环码组为 (0 1 1 1 0 0 1)则相应则相应码多项式为：码多项式为：65432065432106
35、5432054301110011T xa xa xa xa xa xa xa xxxxxxxxxxx反之，由码多项式易得出码组：反之，由码多项式易得出码组：(0 1 1 1 0 0 1)可由码组直接写出。可由码组直接写出。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1940（2 2）码多项式的按模运算）码多项式的按模运算1）整数的按模运算）整数的按模运算若一个整数若一个整数m可以表示为可以表示为:5122251(2)模,mpQpnQnn是整数则在模则在模n运算下，有运算下，有mp（模（模n）。）。例：例：同样对于多项式而言，也有类似按模运算。同样对于多项式而言，
36、也有类似按模运算。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1941 TxR xQ xNxNxTxR x其中：其中：商商Q(x)为多项式，余数为多项式，余数R(x)的幂次低于的幂次低于N(x)的幂次。的幂次。例例:求求 x4+x2+1 按模按模 x3+1 运算的余式运算的余式 R(x)2 2）码多项式的按模运算）码多项式的按模运算若若则则4223342231111111xxxxxxxxxxxx+（模）第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1942 3 3）循环性）循环性在循环码中，若在循环码中，若T(x)是一个长为是一个长
37、为n的许用码组，则的许用码组，则xiT(x)在按在按模模xn+1运算下运算下，亦是，亦是一个许用码组。即一个许用码组。即设：设：T(x)是长为是长为n的许用码组多项式的许用码组多项式()()x1)inx T xTx(模则：则：仍为该码组中的一个码多项式。仍为该码组中的一个码多项式。3985398535322773532()()11()0101110 x T xxxxxxxxxxxxxxxxxx T xxxxx （7，3）码）码T(x)=x6+x5+x2+1 ()前码组循环左移前码组循环左移3位！位！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1943由此类推由此
38、类推()()x()()iix T xT xiT xT xi左 移 位右 移 位可见：可见：一个长为一个长为n的循环码，必为按模（的循环码，必为按模（xn+1）运算的一个余）运算的一个余式。式。“模模”运算过了。运算过了。()()x1)inx T xT x(模第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19442.生成多项式生成多项式g(x)（1 1）存在性）存在性 (n，k)循环码中循环码中有且仅有有且仅有一个一个g(x)g(x)=xn-k+1特点特点:最高的次数最高的次数:n-k=r；最高最高次项和次项和常数常数项系数必为项系数必为1 。11-110-1000
39、 11nrrrkrrkaaaaa a 个在循环码中，除了全在循环码中，除了全0码组码组外，再也没有连续外，再也没有连续k位均为位均为0的码组。即连的码组。即连0长度最多长度最多为为k-1位！位！这唯一的这唯一的n-k次多项式称为次多项式称为生成多项式生成多项式，记为，记为g(x)！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1945（2）生成多项式）生成多项式 g(x)与生成矩阵与生成矩阵 G(x)的关系的关系12()()()()()kkxg xxg xG xxg xg xA=an-1ar GG=Ik Q 生成矩阵生成矩阵G的每一行都的每一行都是一个码组；是一个
40、码组；G是是k行行n列列矩阵，矩阵，只要找到只要找到k个已知码组，个已知码组，就能构成生成矩阵就能构成生成矩阵G！生成多项式确定后，则生成多项式确定后，则g(x)、x g(x)、xk-1 g(x)都是码组，都是码组，且这且这k个码组信息无关，因此可以用来构成生成矩阵。个码组信息无关，因此可以用来构成生成矩阵。g(x)确定了确定了G(x)也就确定了也就确定了整个码组即确定！整个码组即确定！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1946例例:(7，3)循环码，循环码，g(x)=x4+x2+x+1 求求 典型生成矩阵典型生成矩阵解解:6643225532420(
41、)1011100()010 1110()001 01111xxxxxx g xxGxg xxxxxg xxxxx(x)典型阵典型阵:100 1011010 1110001 0111kGI Q可方便地直接写成码组形式可方便地直接写成码组形式第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1947（3）生成多项式生成多项式g(x)与与 码多项式码多项式T(x)的关系的关系（7，3）26546542654()()()()()()()()x g xT xa a a G xa a axg xg xa xa xag xh x g x12()()()()()kkxg xxg xG
42、 xxg xg x表明：表明：所有所有T(x)都可以被都可以被g(x)整除，而且任一次数不大于整除，而且任一次数不大于(k-1)的的多项式乘以多项式乘以g(x)都是码多项式。都是码多项式。h(x)为不大于为不大于(k-1)的多项式！的多项式！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1948依据依据:g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。证：证：任一循环多项式任一循环多项式T(x)都是都是g(x)的倍式，即的倍式，即()()()T xh x g x()()T xg x()()ix T xTx而生成而生成多
43、项式多项式g(x)本身也是一个码组，即有本身也是一个码组，即有由于码组由于码组T(x)为一为一（n-k）次次多项式，故多项式，故xkT(x)为一为一n次多次多项式。由项式。由知，知，xkT(x)在模在模（xn+1）的运算下，亦的运算下，亦为一码组，故可写成为一码组，故可写成 11knnx TxT xQ xxx（4）如何寻找如何寻找g(x)第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1949上式左端分子和分母都是上式左端分子和分母都是n次多项式，故商次多项式，故商Q(x)1，因此上，因此上式可化成即式可化成即()(1)()knx T xxT x1()()nkxg
44、x xh x 将将T(x)=h(x)g(x)、T(x)=g(x)代入，并化简，得代入，并化简，得 11knnx TxT xQ xxx表明表明:g(x)应该是应该是xn+1的一个因式！的一个因式！结论结论:g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1950（4）如何寻找如何寻找g(x)依据依据:g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。如如 第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1
45、951（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=(x3+x+1)+x7+1=(x3+1)+仅有仅有 为生成多项式为生成多项式 第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-195211.6.211.6.2 循环码的编码方法循
46、环码的编码方法1.(n，k)循环码的编码步骤循环码的编码步骤 设设:已选好已选好g(x)，给定信息码组，给定信息码组m(x):（1）作）作xn-km(x)实际上是把信息码后附加上（实际上是把信息码后附加上（n-k）个）个“0”。（2）作）作 n kn kT xxm xr xxm xr xQ xg xg xg xg x xgxrxQxgxmxkn（3）编码输出系统循环码多项式）编码输出系统循环码多项式T(x)为：为：()()()n kT xxm xr x得到了得到了r(x)。由于循环码多项式由于循环码多项式T(x)都可被都可被g(x)整除，也就是：整除，也就是：第第11 11章章 差错控制编码差
47、错控制编码现代通信系统原理2022-12-1953例例:(7，3)循环码，选循环码，选 g(x)=x4+x2+x+1 设设 m(x)=x2+x+1(1 1 1)解解:4654465424242654()1110000()()()11()()()()1110010n kx m xxxxx m xxxxxxxg xxxxxxxr xxT xxm xr xxxxx（1）（）（2）（3）（）2.2.编码的电路编码的电路4243243210()11g xxxxgxgxgxgxg 第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1954上述三步编码过程，在硬件实现时，可以利用除
48、法电路（曹上述三步编码过程，在硬件实现时，可以利用除法电路（曹志刚志刚p344348）来实现。）来实现。编码的电路编码的电路4243243210()11g xxxxgxgxgxgxg 10mg，有反馈，无第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-1955工作过程：工作过程：信息输入时，开关合信息输入时，开关合2：输入码一方面输入除法器，另一方面输入码一方面输入除法器，另一方面直接输出，在信息位全部进入除法器后直接输出，在信息位全部进入除法器后开关合开关合1：输出端接到移位寄存器，将移位寄存器中存储的余输出端接到移位寄存器，将移位寄存器中存储的余项依次输出，同时切断反馈线。项依次输出，同时切断反馈线。系统码！系统码！第第11 11章章 差错控制编码差错控制编码现代通信系统原理2022-12-19562 2、译码过程、译码过程循环码的译码可以分三步进行：循环码的译码可以分三步进行：（1）由接收到的码多项式）由接收到的码多项式B(x)计算校正子（伴随式）多项式计算校正子（伴随式）多项式S(x)；（2）由校正子）由校正子S(x)确定错误图样确定错误图样E(x)；（3）将错误图样）将错误图样E(x)与与B(x)相加，纠正错误。相加，纠正错误。
