第九章差错控制编码sxq

第9章

差错控制编码南京航空航天大学信息科学与技术学院通信原理教研组引言1纠错编码的基本原理2常用的简单编码3线性分组码4循环码5第9章差错控制编码67卷积码网格编码调制2copyright信息科学与技术学院通信原理教研组9.1引言信道解调信源编码加密调制解密译码信宿噪声同步系统信源编码信道编码差错控制ASKFSKPSKDPSK数字通信的组成A/D数据压缩3copyright信息科学与技术学院通信原理教研组采用信道编码在通信过程中，会受到各种外来干扰，如脉冲干扰，随机噪声干扰，人为干扰及通信线路传输性能的限制都将使信号失真。由于以上原因，引起数据信息序列产生错误，称之为差错。

随机性错误：前后出错位之间无一定关系，随机、离散出现。突发性错误：差错成串出现，且有一定相关性。差错的两大类型：

合理的设计基带信号时域/频域均衡都能有效的提高传输可靠性。发射功率的提高4copyright信息科学与技术学院通信原理教研组数字通信中的编码信道编码：信源编码：为提高信号传输的有效性而采取的措施。为提高信号传输的可靠性而采取的措施,亦称差错控制编码。在发送端利用信道编码器在数据信息中增加一些监督信息，使不带规律性或规律性不强的原始数字信号变为带规律性或加强了规律性的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进行错误纠正。差错控制5copyright信息科学与技术学院通信原理教研组

1、差错控制方法（1）前向纠错法FEC

所发码具有纠错能力，收端接收后自动纠错，无需反向信道。实时性好，但译码设备复杂，传输效率↓。信源FEC编码信道FEC译码信宿6copyright信息科学与技术学院通信原理教研组（2）信息反馈法IF信息信号信息信号发端收端

方法和设备简单，无需纠检错编译系统。但需要双向信道，传输效率↓、实时性差。7copyright信息科学与技术学院通信原理教研组(3)检错重发法ARQ

所发码具有检错能力，收端接收后判决是否出错，通过反向信道发送判决结果，发端据此决定是否重发。译码设备简单，对突发错误有效，要求有反馈信道。信源编码器正向信道译码器信宿缓存器重发控制器反向信道重发判决器工作过程：发送——检测——回复——重发或发送新的数据8copyright信息科学与技术学院通信原理教研组①停止等待方式

3221221ACKACKNACK发送端接收端

ARQ的三种实现方式：

特点：半双工工作，简单，要求的缓存量小，但等待时间较长，传输效率↓

9copyright信息科学与技术学院通信原理教研组

②连续重发方式

6543254321065432543210ACK0ACK1NACK2ACK2ACK3退N步方式：从出错帧开始重发优缺点：传输效率↑，但重发的N帧中，大部分为正确，所以仍有浪费。发端缓存必须可存N帧。

10copyright信息科学与技术学院通信原理教研组2987654321029876543210ACK0ACK1NACK2ACK3ACK4ACK5ACK2ACK6

只对出错信息重发，因此传输效率大大提高。但收发两端都要有足够的存储空间。

③选择重发方式

11copyright信息科学与技术学院通信原理教研组反馈信道ARQFEC

编码器正向信道FEC

译码器ARQ

编码既有纠错能力也有检错能力，收端收到信息码组后在收端进行检测。在纠错范围内：纠正；超出范围：通过ARQ方式进行重发。

(4)混合方式12copyright信息科学与技术学院通信原理教研组（1）根据各码组信息码和监督码的关系分：

线性码，非线性码根据监督码元是否仅与本组信息元有关

分组码，卷积码（2）根据纠错码组中信息元是否隐蔽分：

系统码，非系统码（3）纠错码的分类13copyright信息科学与技术学院通信原理教研组根据码的用途分：

检错码，纠错码（4）根据码元的取值：

二进制码，多进制码（5）根据构造编码的数学方法：

代数码，几何码，算术码（6）本课程主要讨论纠随机错误的二进制线性分组码。14copyright信息科学与技术学院通信原理教研组纠错码的发展概况通信的数学理论，Shannon(1948)汉明码，Hamming(1950)级连码，Forney(1966)卷积码及有效译码，(60年代)RS码及有效译码，(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo码，Berrou(1993)LDPC码，Gallager(1963),Macky(1996)空时编码,Tarokh(2000)15copyright信息科学与技术学院通信原理教研组9.2纠错编码的基本原理1、几个术语码长：码组中码元的数目，常用n表示；码距：两等长码字C1、C2对应位上取值不同的数目，又称为汉明(Hamming)距离，记为d(c1,c2)。码重：码组中非零码元的数目，记为W；16copyright信息科学与技术学院通信原理教研组n=3时，码距的几何说明：（a2a1

a0

）a2a1a0（110）（011

）d=2110011（111）（000

）d=3000111最小码距：在分组码(n,k)中，任意两个码字之间汉明距离的最小值，记为dmin。最小码距的大小关系到编码的检纠错能力。01010110000117copyright信息科学与技术学院通信原理教研组发送序列C:(1111011000)接收序列R:(0110010110)比较C和R，可写出另一个序列E：1001001110R=C+E

序列E定义为错误图样(ErrorPattern)错误图样：18copyright信息科学与技术学院通信原理教研组A、B两消息，可用一位二进制数表示，A=1、B=0出错时无法判定增加一个监督位，取11→A、00→B再增加一个监督位，取111→A、000→B许用码组：00，11禁用码组：01，10若收到01或10时，可知发生了错误，但不能纠正错误。许用码组：000，111禁用码组：001,010,100,011,101,110如一位错能够纠正错误；若两位错，则只能发现不能纠错2、纠错或检错的原理19copyright信息科学与技术学院通信原理教研组因此这种（3,1）码，能纠正一个错，发现两个错。

但是(3,1)码中，数据位仅为1位，监督位为两位，传输效率↓↓

可以看出：差错控制是以牺牲传输效率为代价而换取了传输质量的提高的。纠检错能力与加入的监督元方式和数目有关。20copyright信息科学与技术学院通信原理教研组分组码的三个参数码长n，信息位k，最小距离d0，

用符号(n,k,d0)表示k个信息元an-1an-2……arar-1……

a0r个监督元码长：n=k+rR=k/n为编码效率，d0一定(纠错能力一定)时，k/n大，效率高。

对被传输的信息序列分组，每组为k个信息元，对每组按某种关系附加(n-k)个监督码元(校验)，形成为n位的码字。这种方法构成的码组称为分组码。3、分组码21copyright信息科学与技术学院通信原理教研组4、分组码的纠(检)错能力与最小码距d0的关系

任一（n，k）分组码，若要在码字内能：

1/检测e个随机错误，则要求：

d0≥e+1

2/纠正t个随机错误，则要求：

d0≥2t+1

3/纠正t个同时检测e(e>t)个随机错误，则要求：d0≥e+t+122copyright信息科学与技术学院通信原理教研组1纠（检）错能力的几何解释

A1

d0eA2（a）

A1

A2

d0et（c）

A1

d0tA2（b）A2t1123copyright信息科学与技术学院通信原理教研组[例9-1]一个码集，只有两个许用码：0000、1111，试求其纠、检错能力和编码效率。24copyright信息科学与技术学院通信原理教研组解：根据码距的定义，则该码集d0=4，1/用于检错，e≤d0

–1=3，即可检3个错误；2/用于纠错，t≤(d0–1)/2=3/2，取整，即可纠1个错误；3/同时用于纠、检错，d0≥

e+t+1（e＞t）取：e=2，t=1，则可满足上式，即可检2个错误同时纠一个错；R=k/n=1/4编码效率：25copyright信息科学与技术学院通信原理教研组4、对纠错编码的要求纠、检错能力强，编码效率高，码长短，编码规律简单。26copyright信息科学与技术学院通信原理教研组5.差错控制编码的效用

假设在随机信道中，发送“0”和“1”的错误概率相等，都等于p，且p＜＜1，在码长为n的码组中，发生r个错误的概率为：27copyright信息科学与技术学院通信原理教研组例如：当n=7，p=10-³时，则有：

由此可见，即使仅能纠正1-2个错误，也可使误码率下降几个数量级。所以差错控制编码具有较大的实际应用价值。28copyright信息科学与技术学院通信原理教研组6.有扰信道编码定理（Shannon第二定理）

对于给定的有扰信道，若信道容量为C，只要发送端以低于C的信息速率Rb发送信息，则一定存在一种编码方法，使得译码错误概率P随着码长n的增加，按指数下降至任意小的值，表示为Pe-nE(Rb)E(Rb)为误差指数，Rb<C时，E(Rb)>0。Rbmax=C=Blog2(1+S/N)（bit/s）29copyright信息科学与技术学院通信原理教研组

1.码长n和信息速率Rb一定时，随C误差指数E(Rb)P↓随指数下降。其中C=Blog2(1+S/N)（bit/s）

2.在C和Rb一定时(Rb<C)，随码长nP随指数下降(P0)。数字传输系统中，无误码传输的最高信息速率

Rbmax=C=Blog2(1+S/N)（bit/s）

两个结论：30copyright信息科学与技术学院通信原理教研组编码性能举例未采用纠错编码时， 若接收信噪比等于

7dB，编码前误码率 约为810-4，图中A

点，在采用纠错编码 后，误码率降至约4

10-5，图中B点。这样，增大发送功率,就能降低误码率约一个半数量级。10-610-510-410-310-210-1编码后PeAB信噪比(dB)31copyright信息科学与技术学院通信原理教研组由图还可以看出，若保持误码率在10-5，图中C点，未采用编码时，约需要信噪比Eb/n0=9.5dB。在采用这种编码时，约需要信噪比7.5dB，图中D点。可以节省功率2dB。通常称这2dB为编码增益。上面两种情况付出的代 价是带宽增大。10-610-510-410-310-210-1PeCD信噪比(dB)编码后32copyright信息科学与技术学院通信原理教研组传输速率和Eb/n0的关系对于给定的传输系统式中，RB为码元速率。 若希望提高传输速率， 由上式看出势必使信噪比下降，误码率增大。假设系统原来工作在图中C点，提高速率后由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。10-610-510-410-310-210-1编码后PeCDE信噪比(dB)33copyright信息科学与技术学院通信原理教研组9-3常用的简单编码1、奇偶监督码：

k=n-1,r=1的线性码。特点：码组中的1个数是奇数（奇监督码）或偶数（偶监督码）。偶监督时，要满足：奇监督时，要满足：两者的校验能力相同，均只能检测出奇数个错误。R=k/n=n-1/n=1-1/n编码效率：34copyright信息科学与技术学院通信原理教研组

码长5的偶监督码序码字序码字号信息码元监督元号信息码元监督元

a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110

35copyright信息科学与技术学院通信原理教研组

偶监督码编码器a4a3a2a1+信息组a0a1a2a3a4码字36copyright信息科学与技术学院通信原理教研组b3b0b1b2b4+接收码组BS检错信号偶监督码的检错电路37copyright信息科学与技术学院通信原理教研组[例9-2]：一数据序列：

{11100

10111

01101

10001

10101}试对其进行（6，5）偶校验编码，写出码序列并分析其抗干扰能力∣∣∣

∣38copyright信息科学与技术学院通信原理教研组一数据序列：

{11100

10111

01101

10001

10101}试对其进行（6，5）偶校验编码，写出码序列并分析其抗干扰能力解：（6，5）,将数据序列每5码元分组，并作：的运算可得出编码数据序列：{111001∣101110∣011011∣100010∣101011}只能检测出奇数个错误，不能发现偶数个错误，也不能纠错。∣∣∣

∣39copyright信息科学与技术学院通信原理教研组2、水平垂直奇偶校验码：

又称行列监督码或二维奇偶监督码。特点：对水平方向和垂直方向的码元同时实施奇偶监督。110010100000100001101001111000011100111000001010101010111000111100行列监督码40copyright信息科学与技术学院通信原理教研组适于监测突发错误：逐行传输时，能检测长度bM+1的突发错误;逐列传输时,能检测长度bL+1的突发错误；还能纠正一些仅在一行中的单个错误。110010100000100001101001111000011100111000001010101010111000111100L＝5，M＝10的行列监督码其中M为列数，L为行数41copyright信息科学与技术学院通信原理教研组3、恒比码：

又称等重码或定1码。特点：码组中0，1的个数保持不变。若码长为n，码重为w，则此码的码字个数为：Cnw，禁用码字个数为：2n-Cnw码字的个数C53=10检错能力较强，可检出所有奇数和部分偶数错误。检错能力较强，可检出所有奇数和部分偶数错误。适用于传输电报或其他键盘设备产生的字母或符号，但不适合信源发出的是二进制随机数字序列的场合。42copyright信息科学与技术学院通信原理教研组数字码字0123456789011010101111001101101101000111101011110001110100113:2恒比码如：我国的电报，每个汉字用四个10进制数表示，每位10进制数就采用3：2恒比码构成的5位码组来表示。码字的个数C53=1043copyright信息科学与技术学院通信原理教研组作业：4、正反码：

简单的可纠错编码，信元数等于监督元数特点：信息位中，有奇数个1时，监督位重复信息位；信息位中，有偶数个1时，监督位取信息位的反码；可纠一位、检测所有两位错和部分两位以上的错误。例：11001→11001∣1100110001→10001∣01110(n,k)其中k=n/2编码效率：R=k/n=1/244copyright信息科学与技术学院通信原理教研组9.4线性分组码9.4.1基本概念

可用线性方程组表述码的规律性的分组码称为线性分组码。线性码建立在代数学群论基础上，线性码各许用码的集合构成代数学中的群，因此，又称为群码。45copyright信息科学与技术学院通信原理教研组

1.含有全零码字。

2.任意两个许用码字之和仍是一个许用码字。（封闭性）

3.最小码距d0等于非零码字的最小重量即d0=Wmin

（由此性质可以方便的确定出线性分组码的最小码距，进而明确其纠错能力。）在群中只有一种运算，就是模2和。线性分组码的性质：46copyright信息科学与技术学院通信原理教研组

奇偶监督码是一种最简单的线性码，我们曾经作了偶校验的例子。称为监督方程。接收时，为了检测传输时是否有错，还要做同样的计算：这里S称为校正子，上式也称伴随式。奇偶监督码中只有一位监督码，因此只能表示有否错误。47copyright信息科学与技术学院通信原理教研组当监督位增加，则监督方程增加，校正子增加。r位监督码除了用全“0”表示无错外，可表示种错误图样。(n,k)码可纠错的错误图样数为：

我们把接收码组R与发射码组C的差称为错误图样，用E表示：E=C-R，或者C=R+E

(n,k)中，信息码为k位，可传输M=2k种信息，当增加r位的监督位后，有2n种状态，但只取2k种为许用状态，其他为禁用，(n,k)码可检测的错误图样数为2n-2k2n-k-1=2r-1不可检测的错误图样数为2k-148copyright信息科学与技术学院通信原理教研组2n-k-1++……+=对于能纠正t个错误的线性分组码(n,k)应满足：是错i位的个数。如果满足，则有可能构造出纠正一位或一位以上的线性码。i=1时，

即对于码组长度为n，信息码元k位，监督元r，49copyright信息科学与技术学院通信原理教研组

思考：[例9-3]设(n，k)中，k=4，要求能纠一位错，取r=？50copyright信息科学与技术学院通信原理教研组

解：

(n，k)线性分组码，k=4，要求能纠一位错，现取r=3，可指示23-1=7种错误，码长n=4+3=7，表示为：C=[C6C5C4C3C2C1C0]其中C6C5C4C3为信息码元，C2C1C0为监督元由r=3，可有三个监督方程和校正子，设为s1s2s3恰好满足,故可纠一位错。51copyright信息科学与技术学院通信原理教研组设s1s2s3三位校正子与误码位置的对应关系为：000001010100011101110111误码位置无错

C0C1C2C3C4C5C6S1S2S3于是监督码元C2C1C0应由以下监督方程决定。C2=C6+C5+C4C1=C6+C5+C3C0=C6+C4+C3←监督元与信息元之间的线性方程组s1=C2+C6+C5+C4=0s2=C1+C6+C5+C3=0s3=C0+C6+C4+C3=052copyright信息科学与技术学院通信原理教研组于是得到(7，4)线性分组码如下：

序码字号信息元

监督元

8100011191001100101010010111011001121100001131101010141110100151111111

序码字号信息元

监督元

000000001000101120010101300111104010011050101101601100117011100053copyright信息科学与技术学院通信原理教研组9.4.2监督矩阵将前面的监督方程改写成矩阵的形式，

C=[C6C5C4C3C2C1C0]可看成为编码矢量，于是有：记做：监督方程54copyright信息科学与技术学院通信原理教研组H--监督矩阵

不满足以上关系的为非典型矩阵，典型矩阵和非典型矩阵之间可以转换。2/H矩阵各行是线性无关的。行数---监督元的个数r列数---码组长度nIr为r阶单位阵1/当有H=[PIr]时称为典型矩阵，55copyright信息科学与技术学院通信原理教研组利用监督方程，我们可以对线性码的封闭性加以证明即H阵与编码码字的转置乘积为0，可用来作为判断接收码组是否错的依据。56copyright信息科学与技术学院通信原理教研组

设监督方程A1、A2均为线性码集合中的许用码组，因此有令两许用码组相加

A1+A2带入监督方程，有：因此，A1+A2亦为许用码组。57copyright信息科学与技术学院通信原理教研组9.4.3生成矩阵

当给出信息组后，如何方便迅速地求出整个编码码组，即如何生成编码矢量？C2=C6+C5+C4C1=C6+C5+C3C0=C6+C4+C3由监督元与信息元之间的关系：或者可以写成：58copyright信息科学与技术学院通信原理教研组令则有：给Q的左边，加一个k×k阶的单位矩阵，则构成：G=[IkQ]称为生成矩阵，且为典型形式。典型G矩阵行数----信息元的个数k列数----码组长度n每行本身就是一个许用码组于是有：矩阵和非典型矩阵之间可以转换。59copyright信息科学与技术学院通信原理教研组码字的前面k位为信息位，后面位为监督位一般情况，定义线性分组码的码字有如下形式：信息码元监督位信息位编码码字系统形式的线性分组码

编码

60copyright信息科学与技术学院通信原理教研组设信息组生成矩阵编码码组61copyright信息科学与技术学院通信原理教研组1）由G和信息组即可产生全部码字.通过典型生成矩阵产生的一定是系统码。62copyright信息科学与技术学院通信原理教研组

（1）试确定(n,k)，并求H；

(2)写出监督元与信息元的关系式及该（n,k）码的全部码字；

(3)确定最小码距及检错能力。[例9-4]设已知63copyright信息科学与技术学院通信原理教研组解：求H，需确定P，应将已知的那个G转换成典型形式，求出Q，再利用求出G。H=[PIr]=64copyright信息科学与技术学院通信原理教研组

(2)

设C=于是有：监督元与信息元的关系式65copyright信息科学与技术学院通信原理教研组用三位二进制数的所有8种状态带入，可得到所有码字如右表。

序号码字

00000001001011201011030111014100101510111061100117111000(3)确定最小码距及检错能力所以有：d0=3可用于检两位错或纠一位错。利用性质知：最小码距d0等于非零码字的最小重量即d0=wmin66copyright信息科学与技术学院通信原理教研组9.4.4校正子S发送端经过编码后给出：接收端收到的码组为：两者的差记为：表示第i位无错表示第i位有错E称为错误图样。共有2n个错误图样。当E为全零错误图样时，R=C没有传输错误;67copyright信息科学与技术学院通信原理教研组可利用E检出或纠正错误；传输中的错误超出了可纠错的范围。可能有两种情况：(n,k)可检测的错误图样数为2n-2k(n,k)可纠错的错误图样数为2n-k-1这时的错误图样称为不可检测的错误图样一般来讲，E=0，则R=C，可满足监督方程E≠0，则R≠C，不满足监督方程检错：当S=0时，认为E=0，当S0时，认为E0,校正子S的计算即校正子只与错误图样E有关。68copyright信息科学与技术学院通信原理教研组标准阵列表排列方法陪集陪集首69copyright信息科学与技术学院通信原理教研组陪集陪集首70copyright信息科学与技术学院通信原理教研组构造标准阵列的一般方法如下：1）用概率译码确定各伴随式S对应的差错图案E，共对；2）表格为列，行，先确定第一行和第一列，第一行为个码字，第一列为；3）各列对应的元素为第一列的和该列的之和；陪集首

译码时，计算伴随式S，查表获得错误图样E，最后恢复出发送码字C＝E＋R。71copyright信息科学与技术学院通信原理教研组[例9-5]

已知监督矩阵：若接收为：R=[0000011]，试确定是否错误，若接收错误，试进行纠错。72copyright信息科学与技术学院通信原理教研组R=[0000011]，解：计算校正子73copyright信息科学与技术学院通信原理教研组000001010100011101110111误码位置无错

C0C1C2C3C4C5C6S1S2S3错误图样：

E=[0001000]对照校正子与误码位置，确定错误图样：74copyright信息科学与技术学院通信原理教研组于是：R`=R+E=[0000011]+[0001000]由于，当只发生一位错码时，矩阵E中只有一个非零元素，与H的转置相乘的结果是选出其中的一列，即校正子与H矩阵的哪一列相同，则该列即为码元发生错误的位置。

=[0001011]75copyright信息科学与技术学院通信原理教研组(n，k)线性分组码编、译码过程小结：

编码过程：设线性分组码为(n，k)，信息码为：1)根据生成矩阵或监督矩阵，2)由C=MG0

求出所有码字，且为系统码。H0=[PIr]G0=[IkQ]求出典型生成矩阵；76copyright信息科学与技术学院通信原理教研组译码过程：1）由收到的码组R计算校正子S；2）由S判决是否有错并通过找出错误图样；3）按照R+E=C计算并还原C；4）将码组C还原成原信息组M。77copyright信息科学与技术学院通信原理教研组9.4.5汉明码汉明码是用于纠一位错误的线性分组码。特点：最小码距：

纠错能力：编码效率：78copyright信息科学与技术学院通信原理教研组[例9-6]n=15的汉明码，其监督位为多少？编码效率为多少？79copyright信息科学与技术学院通信原理教研组解：于是其信息位有15-4=11位此汉明码为（15，11）码编码效率：其监督位有15-11=4位80copyright信息科学与技术学院通信原理教研组

汉明码是线性分组码，因此其监督矩阵同样有n列、r行，当监督位数给定后，即可构造出汉明码。例，r=3

H矩阵的n列由除了全零以外的个r位码构成，每码组出现一次且全部出现。（H不唯一）构造81copyright信息科学与技术学院通信原理教研组得到的汉明码如下所示：信息位监督位信息位监督位a6a5a4a300000001001000110100010101100111a2a1a0000011101110110101011000a6a5a4a310001001101010101100110111101111a2a1a011110001000100101010011182copyright信息科学与技术学院通信原理教研组（7，4）汉明码编码器a6a5a4a3信息组a0a1a2a3a4码字++a5a6+83copyright信息科学与技术学院通信原理教研组完备码

纠正单个错误的汉明码中，r位校正子码组与误码图样一一对应，最充分地利用了监督位所能提供的信息。

在一般情况下，对于能纠正t个错误的线性分组码(n，k)，应满足以下不等式：

因此，汉明码也是纠一位错的线性分组码中，编码效率最高的。84copyright信息科学与技术学院通信原理教研组

上式取等号时，校正子与误码不超过t个的所有图样一一对应，监督码元得到最充分的利用，这种线性分组码即完备码。

除汉明码外，迄今为止，找到的唯一能纠正多个错误的完备码为(23，12)戈雷码。t=3汉明码就是一种完备码。

该式亦称为汉明界，它给出已知k和t时，所需要的监督位数。85copyright信息科学与技术学院通信原理教研组

但此时构成的则非汉明码。

通常选择码重最小的矢量优先。[例9-6]试构造一个k=5的可纠一个错的线性分组码1/计算最短的码长；2/构造H；3/求生成矩阵G；4/求信息组为(10101)的编码码字C。86copyright信息科学与技术学院通信原理教研组解：1/因为t等于1,且要求k=5,可用试探法确定n设：n-k=3，则不满足纠错要求；

设：n-k=4，则满足纠错要求；于是取n=9，此时r=n-k=4，(9,5)线性分组码87copyright信息科学与技术学院通信原理教研组2/r=4，四位码共有种状态，除全零外都可用于构造H矩阵。

为了构造典型矩阵，选1000，0100，0010，0001四码组，然后从其余的11个码组中，再选出5个，通常按照码重从小到大选择。PIr实际只需9个88copyright信息科学与技术学院通信原理教研组4/M=[1010

1]C=MG=[101010110]Q3/求生成矩阵已知

Ik于是有：89copyright信息科学与技术学院通信原理教研组9.5循环码9.5.1循环码原理

循环码是线性分组码的一个重要子类，也是目前研究最成熟的一类码。它不仅有封闭性，且还有循环性。(n，k)码组则将所有码元向左循环一位，得到的：也是许用码组是许用码组。即90copyright信息科学与技术学院通信原理教研组

若线性分组码的任一码组循环移位所得码组仍在该码组集中，则此码为循环码。（7，3）循环码序号码字

0000000010011101201001113011101041001110510100116110100171110100循环码的循环圈数≥2W=00W=42156734

同一循环圈内，码字的重量相同91copyright信息科学与技术学院通信原理教研组序号码字

00000001001001201001030110114100100510110161101107111111（6，3）循环码W=00W=2124W=4536W=6792copyright信息科学与技术学院通信原理教研组★由于具有循环性，编译码设备较简单；★可以用代数的方法分析和设计编码。10-5-2循环码的多项式表示已知码组：设x为一个任意的实变量，其幂次代表移位的次数，以Ci作为多项式的系数，则可以得到码多项式：循环码的特点93copyright信息科学与技术学院通信原理教研组每循环一位，相当于码多项式乘以x，仍为许用码组01110101、生成多项式与生成矩阵

循环码中次数最低的多项式（全0码字除外）称为生成多项式g(x)。0011101例：即：94copyright信息科学与技术学院通信原理教研组那么，都是许用码组，而这k个码组是线性无关的。于是用它们组成的矩阵则为生成矩阵设信息码组为：其对应多项式为：95copyright信息科学与技术学院通信原理教研组则编码码组为：由上式可看出：用G(x)生成的码字，都是g(x)的倍式，都可以被g(x)整除。96copyright信息科学与技术学院通信原理教研组如何寻找生成多项式？已知编码码组为：生成多项式是一个n-k次的多项式，且本身也是一个许用码组：为一个n次多项式，它是在模运算下的一个许用码组，即：分子分母均为n次，故Q(x)=1于是上式成为：97copyright信息科学与技术学院通信原理教研组有就是说：g(x)的三个特性：也就是说，寻找g(x)的过程，就是对进行因式分解的过程。98copyright信息科学与技术学院通信原理教研组[例9-8]

为了寻找(7，3)循环码的生成多项式，只需找出(n-k)=(7-3)=4次的因式即可。两者均可，但将产生出不同的编码码组。(7，6)码：(7，1)码：(7，4)码：99copyright信息科学与技术学院通信原理教研组9.5.2循环码的编、译码方法1、循环码的编码方法首先根据给定的(n,k)选定生成多项式g(x)并求出G(x)；由C(x)=MG(x)可以生成所有码字，但不是系统码；生成系统码的步骤如下：1/

做，即在信息码后附加n-k个零；如：m=110，n-k=7-3=4时，相当于：1100000100copyright信息科学与技术学院通信原理教研组2/用g(x)除得到商Q(x)和余式r(x)

余式r(x)的次数必小于g(x)的次数n-k，将此余式加于信息位之后，成为编码多项式。3/编出码组

它必能被g(x)整除。101copyright信息科学与技术学院通信原理教研组[例9-9]（7，3）码，选定解：m=110，试编码。编出码组为：1100101102copyright信息科学与技术学院通信原理教研组2、循环码的译码方法设接收码组为：对应多项式为R(x)1/用生成多项式g(x)除R(x)，当传输无错时，必能整除。

因此，当r’(x)=0，则R(x)无错。如果仅是检错，可给出结论。103copyright信息科学与技术学院通信原理教研组2/如果用于纠错，需进一步按余式r’(x)用查表法或运算求出错误图样E(x)；3/根据错误图样做：C’(x)=R(x)-E(x)完成纠错。例：（7，3）码，选定接收码组为：0010101，是判断是否有错？解：r’(x)=111，传输有错误。104copyright信息科学与技术学院通信原理教研组9.5.3截短循环码截短目的：在设计纠错编码方案时，常常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。这时，可以采用将码长截短的方法，得出满足要求的编码。截短方法：设给定一个(n,k)循环码，它共有2k种码组，现使其前i(0<i<k)个信息位全为“0”，于是它变成仅有2k-i种码组。然后从中删去这i位全“0”的信息位，最终得到一个(n–i,k–i)的线性码。将这种码称为截短循环码。截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。例：要求构造一个能够纠正1位错码的(13,9)码。这时可以由(15,11)循环码的11种码组中选出前