西工大通信原理(期末复习、考研、求职必备)-第9章 差错控制编码

1、第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-21通通 信信 原原 理理 电电 子子 教教 案案第第9 9章章 差错控制编码差错控制编码 西西 北北 工工 业业 大大 学学 （2008.3）第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-22研究的问题研究的问题 9.1 9.1 引言引言 9.2 9.2 纠错编码的基本原理纠错编码的基本原理 9.3 9.3 常用的简单编码常用的简单编码 9.3 9.3 线性分组码线性分组码 9.4 9.4 循环码循环码 9.5 9.5 卷积码卷积码 9.6 9.6 网格编码调制网格编码调制 第第9 9章章 差错控制

2、编码差错控制编码现代通信系统原理2021-8-23干扰干扰乘性：均衡乘性：均衡加性：调制解调体制、发送功率、最佳接收加性：调制解调体制、发送功率、最佳接收9.1 9.1 引言引言一、编码问题的提出一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响，使由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能发生错判。码元波形变坏，故传输到接收端后可能发生错判。信道信道译码译码检检/纠错编码纠错编码若还不行，则需差错控制编码。若还不行，则需差错控制编码。目的：目的：在数字通信系统中，为了提高数字信号传输的有效在数字通信系统中，为了提高数字信号传输的有

3、效性而采取的编码称为性而采取的编码称为信源编码信源编码；为了提高数字通信的可靠；为了提高数字通信的可靠性而采取的编码称为性而采取的编码称为信道编码信道编码。差错可控差错可控第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-24二、错误的类型二、错误的类型1.1. 随机性错误随机性错误 （白噪声引起）（白噪声引起）特点：特点：单个错，错误之间不相关。主要出现在无记忆信道。单个错，错误之间不相关。主要出现在无记忆信道。2. 2. 突发性错误突发性错误 ( (脉冲干扰引起）脉冲干扰引起）特点：特点：成串错，错误之间有相关性成串错，错误之间有相关性。主要出现在有记忆信。主要出现在有

4、记忆信道。错误传播。道。错误传播。3. 3. 混合性错误混合性错误第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-25三、差错控制的方式三、差错控制的方式1. 检错重发检错重发(ARQ)收收发发可检错的码可检错的码: : 1）双向通道）双向通道 2）通信效率低）通信效率低 3）不适于实时通信）不适于实时通信 4）编、译码设备简单）编、译码设备简单 5）编码效率高）编码效率高总码元总码元 (n bit)= 信元信元 (k bit)+ 督元督元 (r bit )。kRn只检不纠，有错自只检不纠，有错自动要求重发。动要求重发。第第9 9章章 差错控制编码差错控制编码现代通信系统

5、原理2021-8-262. 2. 前向纠错前向纠错 (FEC)(FEC)收收发发可纠错的码可纠错的码 1）只需单向信道）只需单向信道省信道！省信道！ 2）通信效率高；）通信效率高； 3）适于实时传输；）适于实时传输； 4) 译码设备复杂。译码设备复杂。检错并纠错检错并纠错第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-273. 3. 反馈检验法反馈检验法收收发发原理：原理：收端将信码原封不动地转发回发端，并与原发送信收端将信码原封不动地转发回发端，并与原发送信码相比较：发现错重发；否则：码相比较：发现错重发；否则：PASSPASS特点特点: : 需要双向通道；需要双向通道

6、；收发设备简单；收发设备简单；传输效率低（最低）。传输效率低（最低）。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-289.2 9.2 纠错编码的基本原理纠错编码的基本原理一一. . 基本思想基本思想信元信元督元督元信元信元督元督元信元和督元有一的函数关系，插入督元的过程就是一种编码的信元和督元有一的函数关系，插入督元的过程就是一种编码的过程，接收端可检错纠错。显然，过程，接收端可检错纠错。显然，传输效率传输效率（引入冗余码）（引入冗余码）例：例：天气预报天气预报 信元信元 督元督元 0 0 0 晴晴 0 1 1 云云 1 0 1 阴阴 1 1 0 雨雨三位码元有三位码

7、元有23=8 8种组合，实际使种组合，实际使用了用了2 22 2=4=4种种许用码组。许用码组。其余其余 001，010，100，111 为为禁禁用码组用码组。检错能力：检错能力：可检错奇数个错；可检错奇数个错；纠错能力：纠错能力：无。无。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-29例：例：天气预报，可预报天晴天气预报，可预报天晴信元信元 督元督元 0 0 0 1 1 1冗余量加大，禁用码组比例提高。冗余量加大，禁用码组比例提高。检错能力：检错能力：检检2；纠错能力：纠错能力：纠纠1 1。许用码组许用码组2个，禁用码组个，禁用码组6个个晴晴阴阴第第9 9章章 差错

8、控制编码差错控制编码现代通信系统原理2021-8-210二二. . 纠错编码的分类纠错编码的分类1. 线性码线性码和非线性码和非线性码2. 分组码分组码、卷积码和循环码、卷积码和循环码3. 系统码系统码和非系统码和非系统码三三. . 分组码分组码定义定义: :将信息码将信息码分组分组，为每信息码附加若干个监督码编码，称，为每信息码附加若干个监督码编码，称为分组码。为分组码。特点特点: : 在分组码中，监督码元仅监督本码组中的信息码元。在分组码中，监督码元仅监督本码组中的信息码元。符号符号: : ( n , k ) , r = n k码字码字: :结构结构: :an-1an-2 arar-1a0

9、k个信元个信元r个督元个督元码长码长n1210nnrrAaaa aa第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2114码组的重量和码距及纠错能力码组的重量和码距及纠错能力1. 1. 重量重量 码组中非码组中非0元素的个数元素的个数 例例: : A= ( 10110 ) 码重码重 = 32. 2. 码距码距 两两码组对应位上数值不同的个数，记为两两码组对应位上数值不同的个数，记为d。最小码距最小码距: : 某种编码中各个码组间距离某种编码中各个码组间距离 的最小值，记做的最小值，记做d0 d0=dmin码距的几何意义码距的几何意义: : (n=3) 各顶点各顶点沿立方

10、体各边行走的几何距离。沿立方体各边行走的几何距离。码元值：码元值：每一码组的三个码元值，每一码组的三个码元值，就是此立方体各顶点的座标（就是此立方体各顶点的座标（a2a1a0）最小码距最小码距: : 1第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-212前例中：前例中：天气预报天气预报 信元信元 督元督元 0 0 0 晴晴 0 1 1 云云 1 0 1 阴阴 1 1 0 雨雨四个许用码组之间的距离均为四个许用码组之间的距离均为2。Why?摈弃摈弃d=1的码禁用码组。的码禁用码组。许用码组最小码距愈大，抗干扰许用码组最小码距愈大，抗干扰能力愈强！能力愈强！确定最小码距的目

11、的：确定最小码距的目的：决定编码的检纠错能力。决定编码的检纠错能力。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2133. d0与纠检错能力与纠检错能力1) 若要求检测若要求检测e个错个错,则则 d0e+12) 若要求纠正若要求纠正t个错个错,则则 d02t+13) 若要检测若要检测e纠正纠正t 个错个错(同时同时),则则 d0e+t+1, 且且et码距与检错和纠错能力的关系如图：码距与检错和纠错能力的关系如图：第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-214d0图图9-4第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8

12、-2159.3 9.3 常用的简单编码常用的简单编码属于分组码一类。简单、实用。属于分组码一类。简单、实用。一一. . 奇偶监督码奇偶监督码满足满足: 1231010nnnaaaaa 督元信元奇数监督码偶数监督码偶监督码：偶监督码：码组中码组中1的个数为偶数；的个数为偶数；奇监督码：奇监督码：码组中码组中1的个数为奇数。的个数为奇数。检错能力检错能力: : 所有奇数个错。所有奇数个错。一半！应用非常多。一半！应用非常多。编码效率编码效率: :1,!,knRnnnk高码长信元数第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2162二维奇偶监督码二维奇偶监督码进行横、纵向监

13、督进行横、纵向监督例例: :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) 可纠正一些错码可纠正一些错码 适于检测突发性错误适于检测突发性错误第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-217例例: 码重为码重为3许用码组许用码组: 禁用码组禁用码组: 可检测所有奇数个码元的错可检测所有奇数个码元的错 和部分偶和部分偶数个码元的错数个码元的错,但

14、但 不能检测码组中不能检测码组中“1”变为变为“0” 与与“0”变为变为“1”的错码数目相同的那些偶数错码的错码数目相同的那些偶数错码325log0.66CRn第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-218例：例： 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 接受端的检测接受端的检测信息位监督位合成码组编码规则编码规则:信息位信息位(n/2)中有中有数个数个“1”,则监督位

15、与信息位则监督位与信息位 信息位信息位(n/2)中有中有数个数个“1”,则监督位是信息位的则监督位是信息位的第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2199.4 9.4 线性分组码线性分组码定义：定义：若分组码（若分组码（n,k）,督元与信元的关系可用一线性方程组督元与信元的关系可用一线性方程组来描述，则该分组码（来描述，则该分组码（n,k）称为线性分组码。）称为线性分组码。一、汉明码一、汉明码 能纠一位错的线性分组码。能纠一位错的线性分组码。定义：定义：是一种是一种能纠正一位错能纠正一位错码，且编码效率较高的线性分组码，且编码效率较高的线性分组码。码。最小码距：

16、最小码距：d0=31. 构造原理构造原理考察：考察：定义一个监督方程（监督关系式、偶监督）：定义一个监督方程（监督关系式、偶监督）：1231001nnnaaaaaS 校正子督元信元无错有错由于一位由于一位校正子校正子只有两种取值，故只能表示有错或无错，不只有两种取值，故只能表示有错或无错，不能指出错码的位置。能指出错码的位置。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-220推想推想: :如果监督位增加一位（即变成两位），则可增加一个类似如果监督位增加一位（即变成两位），则可增加一个类似于上式的监督关系，即可获得两个校正子，于是可有于上式的监督关系，即可获得两个校正子

17、，于是可有0 00 11 0 1 1无错无错可指示一个错码可能出现的可指示一个错码可能出现的位置，共有位置，共有22-1=3 个位置。个位置。1231001nnnaaaaaS 校正子督元信元无错有错第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-221再推广再推广: :0 0 . 00 0 . 11 1 .1 1无错无错2r-1 个错的个错的可能位置可能位置显然：显然：要求要求 2r-1n（n=k+r），则可指示（仅一位错时），则可指示（仅一位错时）任一错码的位置包括信元、督元。任一错码的位置包括信元、督元。或：或： 2rk+r+1112rSrrrSSS 对应对应对应对应

18、一个督元一个监督方程一个校正子:个督元个监督方程个校正子: 、可指示一个错码可能出现的可指示一个错码可能出现的2r-1个位置。个位置。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2222. 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 信元督元第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-223（2）写出校正子的编码表）写出校正子的编码表 r = 3 共有共有3个校正子个校正子

19、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 时时, 即无错得即无错得校验方程校验方程:偶监督关系第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-224得得校验方程校验方程: :6542653164

20、30000aaaaaaaaaaaa即实际上确定了即实际上确定了督元和信元之间的关系督元和信元之间的关系:265416530643aaaaaaaaaaaa校验方程督信关系有了校正子编码表，督元不是随便选的！有了校正子编码表，督元不是随便选的！（4） 给定了信元给定了信元a6a5a4a3,可由可由“督信关系”确定督元确定督元全部全部( 7,4 ) 码组。码组。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-225（4） 给定了信元给定了信元a6a5a4a3,可确定督元全部可确定督元全部( 7,4 ) 码组码组265416530643aaaaaaaaaaaa第第9 9章章 差错

21、控制编码差错控制编码现代通信系统原理2021-8-226二二. . 线性分组码线性分组码1. 1. 线性方程组和监督方程线性方程组和监督方程654321065432106543210111010001101010011110110aaaaaaaaaaaaaaaaaaaaa 写成矩阵式写成矩阵式:1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6a5a4a3a2a1a0 00000TTTHAA H记为或第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-227:0HA 其中码组的行距阵零矩阵监督矩阵可见：可见：H一旦确定，督元和信元之间的关

22、系也就确定了。一旦确定，督元和信元之间的关系也就确定了。若若: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记为或第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2282. 2. 生成矩阵生成矩阵265416530643aaaaaaaaaaaa督信关系矩阵形式矩阵形式: 经由生成矩阵生由信元生成：成线性码组从督信方程入手从督信方程入手由由6251403111011011011aaaaPa

23、aa 第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-229写成行阵形式写成行阵形式:21065436543111110101011aa aaaaaaaaaQQ 其中其中 Q = PT。上式表明：上式表明：信息位给定后，就产生了监督位！信息位给定后，就产生了监督位！进一步，令进一步，令生成矩阵生成矩阵 G = Ik Q 则，码组行阵则，码组行阵 A = a6a5a4a3 G 6251403111011011011aaaaPaaa 第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-230例：例：生成矩阵生成矩阵讨论：讨论：由具有由具有 Ik Q 形式的生

24、成矩阵称为形式的生成矩阵称为典型生成阵典型生成阵。由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位不变，监督位附中，信息位不变，监督位附加其后这种码称为加其后这种码称为系统码系统码。21065436543111110101011a 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 aaaaaaaaaaaaa

25、a 信息位不变督位附后， ， ，码组行阵：码组行阵：第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-231一般形式一般形式: : A = an-1an-2ar G 3. G 和和 H 的关系的关系由由 Q = PT 或或 P = QT 则则 : H = P Ir G = Ik Q 综上：综上：线性分组码的编码，就是根据其监督阵线性分组码的编码，就是根据其监督阵H或生成阵或生成阵G将将长为长为k的信息码编成长为的信息码编成长为n的码组。的码组。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2324. 4. 线性分组码的纠错译码过程线性分组码的纠错译码

26、过程怎样由含有错误的接收码组中的接收码组中恢复正确。怎样由含有错误的接收码组中的接收码组中恢复正确。 （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 0,1,iiiiibaeba，说明无错，说明有错第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-233（2 2）校正子（或称译码伴随式）校正子（或称译码伴随式）

27、0)TTBAAHBHS零矩阵无错（非零矩阵有错 代入上式，得代入上式，得0TTTTTBHAE HAHEHEHS结论：结论：校正子校正子S仅于错误图案有关，与发送码组无关。仅于错误图案有关，与发送码组无关。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-234由收到的码组由收到的码组B，按式：，按式：BHT=SS由由 S=ET E按按B+E=A A由由A 原始信息原始信息（3 3）纠错译码过程）纠错译码过程 第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2355. 5. 线性分组码的重要性线性分组码的重要性（1 1）封闭性）封闭性 设：设： A1、A

28、2 分别为一线性分组码的任意两个许用码组。分别为一线性分组码的任意两个许用码组。 则：则：A1+A2 仍为该线性分组码的许用码组。仍为该线性分组码的许用码组。证：证：由假设知由假设知A1HT=0、A2HT=0 所以所以A1HT+A2HT=（A1+A2）HT0 即即A1+A2也是一个码组。也是一个码组。结论：结论：线性码组中任意两个码字之和，仍为该线性码组之码字。线性码组中任意两个码字之和，仍为该线性码组之码字。（2 2）线性分组码的最小码距）线性分组码的最小码距即为该码的最小重量即为该码的最小重量:d0=Wmin（除全（除全0码组）码组）证：证：由封闭性得，两个码组之间的距离（之差），必是另一

29、码由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！组的重量。故最小码距即是码的最小重量！第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2369.5 9.5 循环码循环码 仍属于线性分组码仍属于线性分组码特点特点: : 编译码设备简单，检纠错能力强。编译码设备简单，检纠错能力强。9.5.1 9.5.1 循环码的原理循环码的原理具有线性分组码的所有性质之外，还具有循环性：具有线性分组码的所有性质之外，还具有循环性：循环码中任循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。一许用码组经过循环移位后，所得到的码组仍然是许用

30、码组。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2371. 码多项式码多项式 T(x)（1）定义）定义为了利用代数理论研究循环码，可以将码组用代数多项是为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。来表示，这个多项式被称为码多项式。设：设：许用循环码许用循环码A=(an-1 an-2 a1 a0)，则：则：它的码多项式表示为：它的码多项式表示为： 121210nnnnT xaxaxa xa其中：其中：x仅是码元位置的标记。仅是码元位置的标记。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-238例例: :

31、设设 ( 7,3 ) 循环码组为循环码组为 ( 0 1 1 1 0 0 1 )则相应则相应码多项式为：码多项式为： 654320654321065432054301110011T xa xa xa xa xa xa xa xxxxxxxxxxx反之，由码多项式易得出码组：反之，由码多项式易得出码组：( 0 1 1 1 0 0 1 )可由码组直接写出。可由码组直接写出。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-239（2 2）码多项式的按模运算）码多项式的按模运算1）整数的按模运算）整数的按模运算若一个整数若一个整数m可以表示为可以表示为:)2(1521225按按模模

32、 ,mpQpnQnn是整数则在模则在模n运算下，有运算下，有mp（模（模n）。）。例：例：同样对于多项式而言，也有类似按模运算。同样对于多项式而言，也有类似按模运算。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-240 TxR xQ xNxNxTxR x其中：其中：商商Q(x)为多项式，余数为多项式，余数R(x)的幂次低于的幂次低于N(x)的幂次。的幂次。例例: : 求求 x4+x2+1 按模按模 x3+1 运算的余式运算的余式 R(x)2 2）码多项式的按模运算）码多项式的按模运算若若则则4223342231111111xxxxxxxxxxxx +（模）第第9 9章章

33、 差错控制编码差错控制编码现代通信系统原理2021-8-241 3 3）循环性）循环性在循环码中，若在循环码中，若T(x) 是一个长为是一个长为n的许用码组，则的许用码组，则xiT(x) 在按在按模模xn+1运算下运算下，亦是，亦是一个许用码组。即一个许用码组。即设：设： T(x) 是长为是长为n的许用码组多项式的许用码组多项式( )( )x1)inx T xTx(模则：则： 仍为该码组中的一个码多项式。仍为该码组中的一个码多项式。3985398535322773532( )()11( )0101110 x T xxxxxxxxxxxxxxxxxx T xxxxx （7，3）码）码T(x) =

34、 x6+x5+x2+1 ( )前码组循环左移前码组循环左移3位！位！第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-242由此类推由此类推( )( )x( )( )iix T xT xiT xT xi左 移 位右 移 位可见：可见：一个长为一个长为n的循环码，必为按模（的循环码，必为按模（xn+1）运算的一个余）运算的一个余式。式。( )( )x1)inx T xT x(模第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-2432. 生成多项式生成多项式g(x)（1 1）存在性）存在性 ( n，k ) 循环码中循环码中有且仅有有且仅有一个一个g(x)

35、g(x)=xn-k+1特点特点: : 最高的次数最高的次数: n-k=r； 最高最高次项和次项和常数常数项系数必为项系数必为1 。 11-110-1000 11nrrrkrrkaaaaa a 个在循环码中，除了全在循环码中，除了全0码组码组外，再也没有连续外，再也没有连续k位均为位均为0的码组。即连的码组。即连0长度最多长度最多为为k-1位！位！这唯一的这唯一的n-k次多项式称为次多项式称为生成多项式生成多项式，记为，记为g(x)！第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-244（2） g(x) 与生成矩阵与生成矩阵 G(x) 的关系的关系12( )( )( )(

36、)( )kkxg xxg xG xxg xg xA = 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)也就确定了也就确定了整个码组即确定！整个码组即确定！第第9 9章章 差错控制编码差错控制编码现代通信系统原理202

37、1-8-245例例: : ( 7，3 )循环码，循环码， g(x) = x4+x2+x+1 求求 典型生成矩阵典型生成矩阵解解:6643225532420( )1011100( )010 1110( )001 01111xxxxxx g xxGxg xxxxxg xxxxx(x)典型阵典型阵: :100 1011010 1110001 0111kGI Q可方便地直接写成码组形式可方便地直接写成码组形式第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-246（3） g(x) 与与 T(x) 的关系的关系（7，3）26546542654( )( ) ( )( )( )( )(

38、) ( )x g xT xa a a G xa a axg xg xa xa xag xh x g x12( )( )( )( )( )kkxg xxg xG xxg xg x表明：表明：所有所有T(x)都可以被都可以被g(x)整除，而且任一次数不大于整除，而且任一次数不大于(k-1)的的多项式乘以多项式乘以g(x)都是码多项式。都是码多项式。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-247依据依据: : g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。证：证：任一循环多项式任一循环多项式T(x)都是都是g(x)的倍式，

39、即的倍式，即( )( ) ( )T xh x g x( )( )T xg x( )( )ix T xTx而生成而生成多项式多项式g(x)本身也是一个码组，即有本身也是一个码组，即有由于码组由于码组T(x)为一为一（n-k）次次多项式，故多项式，故xkT(x) 为一为一n次多次多项式。由项式。由知，知，xkT(x)在模在模（xn+1）的运算下，亦的运算下，亦为一码组，故可写成为一码组，故可写成 11knnx TxT xQ xxx（4） 如何寻找如何寻找g(x)第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-248上式左端分子和分母都是上式左端分子和分母都是n次多项式，故商次

40、多项式，故商Q(x)1，因此上，因此上式可化成即式可化成即( )(1)( )knx T xxT x1( )( )nkxg x xh x 将将T(x)=h(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)次的因子，且常数项不为零。次的因子，且常数项不为零。第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-249（4） 如何寻找如何寻找g(x)依据依据: : g(x)是是xn+1的一个的一个(n-k)次的因子，且常数项不为零。次的因子，且常数项不为零。如如 第第9 9章章 差错控制编码差错控制编码现代通信系统原理2021-8-250 （7，3）循环码有多项式如下，找出（循环码有多项式如下，找出（7，3）码的生成）码的生成多项式多项式g(x)。 （1） x4+x3+x （2） x3+x2+1 （3） x+1 （4） x4+x2+x+1 （5） x4+