第5章 差错控制

1、下一页上一页数据通信原理数据通信原理计通学院通信工程系计通学院通信工程系2014年年9月月for 计算机计算机12级级第5章 差错控制与信道编码下一页上一页目的要求l理解差错控制的基本方法和检错、纠错码构成的基本原理。掌握信道编码的基本原理；了解常用检错码的特性；掌握线性分组码的一般特性；掌握汉明码以及循环码的编译码及其实现原理；了解卷积码的基本概念。l本章是本课程的重点。下一页上一页授课内容l5.1 差错控制的基本概念及原理 l5.2 检错和纠错的基本概念 l5.3 基于信道编码的差错控制方式l5.4 常用的简单信道编码 l5.5 汉明码及线性分组码 l5.6 循环码 l5.7 卷积码 返回

2、目录下一页上一页一、差错控制一、差错控制 所谓差错控制是通过某种方法，发现并纠正传输中出现的错误。它是数据通信系统中提高传输可靠性，降低系统传输误码率的有效措施 。5.1 差错控制的基本概念及原理 返回目录下一页上一页二、信道编码的基本概念二、信道编码的基本概念1、基本思路在发送端被传送的信息码序列的基础上，按照一定的规则加入若干“监督码元”后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时，检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则在接收端可以发现传输中的错误，乃至纠正错误。 信息码+监督码=码组，称差错控制编码或纠错编码或信道编码

3、（加的监督码越多，差错控制能力越强）下一页上一页2、编码效率将信息序列按照k位码元的长度分成若干个信息码组M，再将信息码组输入到信道编码器，信道编码器按照一定的算法，产生一个新的n位码字A输出，nk；所谓编码效率是指信道编码后码字中信息码元的数目与码字总码元数目之比 ，记为k/n。下一页上一页3、许用码字和禁用码字信息码组M由k个二进制码元（即比特）组成，所以就有2k个M；A长度为n，n位长度的码字共有2n个，信道编码实质是通过一定 的规则，从2n个长度为n的码字中选择了其中的2k个，每个被选中的码字称为许用码字；未被选中的2n-2k个n长的码字称为禁用码字，反映冗余大小 。下一页上一页4、信

4、道编码的分类按码组的功能分为检错码和纠错码按监督码与信息码元之间的关系分为线性码和非线性码（1）线性码：是指监督码元与信息码元之间的关系是线性关系，即可用一组线性代数方程联系起来（2）非线性码：指的是二者是非线性关系按照对信息码元处理方法的不同分为分组码和卷积码（1）分组码：是将信息划分 为k个码元一组。然后由这k个码元按照一定的规则产生r，从而组成长度n的码组k个信息码元r个监督码元。分组码一般用符号(n,k)表示，；（2）在卷积码中，每组的监督码元不但与本码组的信息码元有关，而且还与前面若干组信息码元有关。即不是分组监督，而是每个监督码元对它的前后码元都实行监督，前后相连，因此有时也称为连

5、环码。按照信息码元在编码后是否保持原形式不变来分为系统码和非系统码（1）系统码：编码后的信息码元保持原样不变（2）非系统码：编码后的信息码元改变了原来的信号形式下一页上一页三、差错分析的基本概念三、差错分析的基本概念危害数据传输的噪声有两类：一类是随机噪声：包括热噪声、散弹噪声以及传输媒介引起的噪声等，引起随机差错；另一类是脉冲噪声：是指突然发生的噪声，包括雷电、开关引起的瞬态变化以及机电交换机的拨号脉冲等，引起突发差错。根据这两类噪声差错可以分为两种类型：随机差错 ，又称独立差错，是指那些独立地、稀疏地和互不相关地发生的差错。（存在这种差错的信道称为随机信道或无记忆信道）产生的原因：随机噪声

6、突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。（存在这种突发错误的信道称为突发信道或有记忆信道）产生的原因：脉冲噪声下一页上一页l错误图样：l假设发送端发送的序列为A，经信道传输后，接收端接收的序列为B，信道的错误图样为E。lE=A+B，实际上是A异或B。因此，在错误图样E中，0表示在传输中未发生错误，1表示在传输中发生了错误，表示错误的码元。l如果已知错误图样，就可确定差错类型。一般来说，错误比较集中（1的密度大）的叫做突发差错；错误比较分散的叫做随机差错。为了便于划分突发差错与随机差错的界限，可以通过错误密度或者突发长度来划分。l突发长度指第一个错误码元与最

7、后一个错误码元之间的码元数目。错误密度是指第一个错误码元至最后一个错误码元之间的错误码元数与他们之间的总码元数之比。下一页上一页例如：A：1 1 1 1 1 1 1 1 1 1B：1 0 0 1 0 0 1 1 1 1E：0 1 1 0 1 1 0 0 0 0则突发长度为5，错误密度为4/5返回下一页上一页5.2 检错和纠错的基本概念一、基本概念一、基本概念1、码长：码字的码元数目，例如(n，k)分组码的码长为n 2、码重：指码字中“1”的数目，记作W(A)。例如：W(110110)=4 3、码距：又称汉明距，两个等长码对应位不同的数目，记作d(A，B)， 例如：A=110110，B=1010

8、11，则d(A，B)=4 4、码距与码重的关系：d(A，B)=W (A+B) 返回目录下一页上一页5、最小码距又称最小汉明距， (n，k)分组码总共有2k个码字，记作Ai（i=0,1,2k-1）,则这些码字两两之间都有一个码距，定义该(n，k)分组码的最小码距为 ：例如：有一码组集合1 0 1 1 11 1 0 0 10 0 0 1 01 1 0 1 0l则该码组的最小码距为2。12 , 2 , 1 , 0; 12 , 2 , 1 , 0),(dmin0 kkjijijiAAd333422下一页上一页二、检错和纠错的基本概念二、检错和纠错的基本概念检错：验证收到的码字是否是需用码字即可发现错误

9、纠错：能判断出错误发生的位置，将其纠正下一页上一页三、（三、（n, k）分组码的纠检错能力）分组码的纠检错能力一个(n，k)分组码的纠检错能力由其最小码距决定 ：1、要在一个码组中检出e个误码，要求 即任一码组产生小于等于e个误码时，都不会变成另一准用码组。C Ci iC Cj je e1 1d dminmin下一页上一页 2、 要在一个码组中能纠正t个误码，要求 d0 2t1 将以t为半径的“球”内所有的禁用码组均判为球心中的准用 码组，可纠正t个以内的错误。C Ci iC Cj jt t1 1t td dminmin下一页上一页 3、 要在一个码组中能纠正t个误码，同时检出e (e t)

10、个误码 d0 et1 当误码数小于等于t时，可纠正误码； 当误码数大于t小于等于e时，不会落入另一码组的纠错范 围内。C Ci iC Cj jt t1 1t td dm mi in ne e返回下一页上一页5.3 基于信道编码的差错控制方式l在数据通信系统中，差错控制方式可以分为四种：反馈纠错（ARQ）、前向纠错（FEC）、混合纠错（HEC）和信息反馈（IRQ）四种。返回目录下一页上一页一、检错重发或反馈纠错（一、检错重发或反馈纠错（ARQ）1、思路这种差错控制方式在发送端对数据序列进行分组编码，加入一定多余码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进

11、行有无错误的判别，并把判决结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。下一页上一页2、重发方式在具体实现检错重发系统时，通常有3 种形式：停止等候重发返回重发选择重发下一页上一页（1）停止等候重发发送端每发送一个码组，就停下来等候，发送端在Tw时间内发送一个码组，然后等候，等候时间为Td，再发送下一个码组，TdTw+反馈时间；收端判断下是否有错，会发送一个应答信号给发送端，发送端收到信号（可以是承认信号也可以是否认信号）后，让发送端在下一个发送时间内发送码组，如果发送无错，则发送应答信号为ACK，让发送端接着发送下一

12、个码组；如果发送出错，则发送应答信号为NAK，要求重发这个出错的码组。示例动画演示下一页上一页（2）返回重发发送端连续发送一个码组，一边发送，一边等候接收端的应答信号。接收端检验，如果发现无错，则发送应答信号ACK，则继续发送码组；如果发现有错，则发送应答信号NAK，如果这个码组出错，那么发送端要求这个错误码组以后已经发送的码组都要重发。比如接收端第2个码组出错，那么接收端返回NAK应答信号时，发送端正在发送第6个码组，等第6个码组发送完，发送端要从这个有错的码组，即第2个码组开始，把已经发送出去的第2、3、4、5、6个码组都要重发。示例动画演示下一页上一页（3）选择重发发送端连续发送一个码组

13、，一边发送，一边等候接收端的应答信号。接收端检验，如果发现无错，则发送应答信号ACK，则继续发送码组；如果发现有错，则发送应答信号NAK，如果这个码组出错，发送端只需要重发这个出错的码组。 示例动画演示下一页上一页3、特点l编码效率比较高，对信道的适应能力强l重发导致信道的有效利用率较低，通信的实时性较差l译码设备较简单4、应用l数据通信系统下一页上一页二、前向纠错（二、前向纠错（FEC）1、思路l前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。下一页上一页2、特点l无需重发，实时性好l编码效率较低，译码设备比较复杂

14、l若错误超出纠错码纠错能力,只好将其抛弃3、应用l移动通信系统 下一页上一页三、混合纠错检错（三、混合纠错检错（HEC） l1、思路l混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。下一页上一页2、特点l集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性3、应用l移动通信系统 ，数据传输系统下一页上一页四、信息反馈（四、信息反馈（IRQ）1、思路l接收端把收到的数

15、据序列全部由反向信道送回发端，发端比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。2、特点l不需要纠错、检错的编译码器，设备简单。l 需要和前向信道相同的反向信道，实时性差。l 发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。返回下一页上一页5.4 常用的简单信道编码l5.4.1 奇偶监督码l5.4.2 行列监督码l5.4.3 恒比码l5.4.4 重复码l5.4.5 正反码返回目录下一页上一页码重为奇数或偶数的(n , n-1)系统分组码)(0)(11010模二偶监督模二奇监督ni

16、iniiaa： ITU-T建议同步数据传输使用偶监督异步数据传输使用奇监督监督关系：假设将（n，n-1）的奇偶监督码的码字记作：an-1,an-2,a1,a0， 其中a0为监督码元，其余为信息码元，则各码元满足：5.4.1 奇偶监督码返回下一页上一页对水平方向(共L行)和垂直方向(共M列) ,同时进行奇偶监督的码，记作（LM+L+M+1 , LM）。(66，50)行列监督码的一个码字 (偶监督)该码具有很强的纠检错能力，常用于短波散射信道等信道干扰比 较严重的通信中。5.4.2 行列监督码返回下一页上一页该码的特点是码字中1，0数目恒定，亦即1，0数目之比恒定。电传通信中普遍采用3：2码，又称

17、5中取3码，如下所示 国际上通用的ARQ电报通信系统中，采用7中取3码。 5.4.3 恒比码下一页上一页恒比码的优点：（1）简单（2）能检测出单个和奇数个错误，还能部分检测出偶数个错误（3）适于传输电传机或其他键盘设备所产生的数字、字母和符号；但不适用于信源来的二进制随机数字序列返回下一页上一页(3，1)重复码两个码字为000和111，其最小码距为3；(n，1)重复码也只有全0码和全1码两个码字，其最小码距为n，却有2n-2个禁用码组，随着码长的增大，其冗余也变得很大；该码随码长增加，具有很强的纠检错能力，但其编码效率的急剧下降；重复码并不是一种优秀的编码方案，仅用于速率很低的数据通信系统中。

18、重复码只有一位信息码元，监督码元是信息码元的重复，所以仅有两个码字；5.4.4 重复码返回下一页上一页该码型多用于10单位码的前向纠错设备中，可以纠正一位错误，发现全部两个以下的错误，以及大部分两个以上的错误，其本质就是五单位码的重复；编码规则：信息码组中1的数目为奇数时，监督码是信息码的重复即正码； 信息码组中1的数目为偶数时，监督码是信息码的反码。例如：M=11001，则对应得码字为1100111001M=11101，则对应得码字为11101000105.4.5 正反码下一页上一页译码规则：首先将收到的码字重的信息位和监督位按对应位作模2运算，得到一个5位码组，若该码字中有奇数个1，则将其

19、作为校验码组，若有偶数个1，则取其反码作为校验码组。然后，按照下表进行纠检错译码。例如：0110101101，则合出码组为00000，信息元中有3个1，奇数，所以检验码组即合成码组00000，对应表，则传输正确。如0101010111，则合成码组为11101，因为信息元有2个1，偶数，所以校验码为合成码组的反码，00010，则对照表，监督元有1位出错，在校验码组中1对应的位置，即监督元10111中斜体1出错。如0111010110，则合成码组为11000，信息元中有3个1，则校验码组等于合成码组，11000，则错误情况判断：传输出错，且错误位数大于1。下一页上一页 正反码错误判决表 校验码组的

20、形式错误情况判断1全“0”传输正确24个“1”，1个“0”信息元有1位出错，在校验码组中“0”对应的位置34个“0”，1个“1”监督元有1位出错，在校验码组中“1” 对应的位置4其它形式传输出错，且错误位数大于1返回下一页上一页5.5 汉明码及线性分组码l5.5.1 线性分组码l5.5.2 汉明码返回目录下一页上一页5.5.1 线性分组码一、线性分组码的定义一、线性分组码的定义l线性码是指信息位和监督位满足一组线性方程的码；分组码是监督码仅对本码组起监督作用，既是线性码又是分组码称为线性分组码。（n, k）线性分组码，其码字通常记作： A=an-1 an-2 a0 1n下一页上一页二、线性分组

21、码的性质二、线性分组码的性质（1）封闭性：指码中任意两许用码组之和仍为一许用码组。（2）线性分组码中必有一个全0码组（3）码的最小距离等于非零码的最小重量例：已知一个线性分组码的码组集合为： 000000，001110，010101，011011，100011，101101，110110，111000求该码组集合的汉明距离。解：根据线性分组码的性质可以求出此码组集合的汉明距离为3。下一页上一页三、线性分组码编码三、线性分组码编码1、生成矩阵对于一个（n, k）线性分组码，其生成矩阵G是k行n列的矩阵，只要有k个线性无关的n元行矢量，都可以构成生成矩阵G，生成矩阵不同，则得到的分组码也不同。nk

22、nkkknnkgggggggggG1, 10, 10, 11, 110101,00100110ggg下一页上一页2、编码原理已知(n, k)线性分组码A=an-1 an-2 a0 1n，其信息码组M=mk-1 mk-2 m1 m0 1k ，则编码过程为：1, 10, 10, 11, 110101,00100021nkkknnkkgggggggggmmmMGA下一页上一页例：假设一个(6，3)分组码生成矩阵为： 101100110010101011G编码过程为： 1011001100101010110121020122012mmmmmmmmmmmmmMGA下一页上一页信息码组M m2 m1 m0

23、码字A a5 a4 a3 a2 a1 a0信息码组M m2 m1 m0码字A a5 a4 a3 a2 a1 a00 0 00 0 10 1 00 1 10 0 0 0 0 00 0 1 1 0 10 1 0 0 1 10 1 1 1 1 01 0 01 0 11 1 01 1 11 1 0 1 0 11 1 1 0 0 01 0 0 1 1 01 0 1 0 1 1根据编码原理，输入信息码组M，得到相应的码字A。该(6，3)码是非系统码，信息元m2、m0、m1分别出现在码字A的第1、3、5位，而2、4、6位是编码器产生的监督码元其码表为：要想得到系统码，即码组A中，信息位不变，监督位附加于其后

24、，则需要将生成矩阵G进行典型化。下一页上一页生成矩阵典型化101100110010101011G101100110010011001G101100110010011001011202012012mmmmmmmmmmmmMGA编码过程下一页上一页(6，3)系统分组码表 监督元与信息元之间的一般关系 信息码组M m2 m1 m0码字A a5 a4 a3 a2 a1 a0信息码组M m2 m1 m0码字A a5 a4 a3 a2 a1 a00 0 00 0 10 1 00 1 10 0 0 0 0 00 0 1 1 0 10 1 0 0 1 10 1 1 1 1 01 0 01 0 11 1 01

25、1 11 0 0 1 1 01 0 1 0 1 11 1 0 1 0 11 1 1 0 0 0011202012012345mmmmmmmmmaaaaaaA下一页上一页注意到系统码中前k位即信息元，将其写成线性方程组的形式034145235aaaaaaaaa监督关系 000034145235aaaaaaaaa0100110010011001101012345aaaaaa下一页上一页监督矩阵 监督关系一般表达 100110010011001101H0THA0TAH或生成矩阵典型阵一般形式nkrkknkrkkkrrQIqqqqqqqqqG1, 11 , 10, 11, 111101, 001001

26、00000100001下一页上一页(n，k)分组码码字可表示为 ：(n，k)码的一般编码过程A =an-1 an-2 an-k ar-1 a1 a0 = mk-1 mk-2 m0 ar-1 a1 a0 对上式两边同时进行矩阵转置得： QIMMGAkTTkTTTMQIMGA下一页上一页即此时的系数矩阵，即监督矩阵为 01000001000010211, 11, 11,01 , 111010, 11000aaaqqqqqqqqqnnrkrrkk1000001000011, 11, 11,01 , 111010, 11000rkrrkkqqqqqqqqqH下一页上一页生成矩阵和监督距阵的关系(n，k

27、)码的一般编码过程0rkrkrrkrkkrkTrTkTQQIQQIIQQIIQQIGH0TGH0THG或 即 根据需要选定一监督关系确定H阵； 求由H距阵和阵的关系确定G阵； 由A=MG生成所有码字。 生成矩阵和监督矩阵是正交下一页上一页3、伴随式与检错原理所谓错误图样E，是由发送码字A和接收码字B进行异或运算得到，若E0，说明传输无错，即码字A与B相同，但是错误图样只能够反映的是信道噪声的情况，接收端是不能依据其来检错。实际上，判断传输是否出错，可以将接收到的码字B跟分组码的码字进行比较，如果B是分组码(n,k)的码字，说明传输无错。因此，这里定义了个伴随式S错码的码字，判决传输出不是该错码

28、的码字，判决传输无是该)(0)(0knBknBBHST，伴随式S和错误图样E的关系 TTTTTEHEHAHHEABHS)(下一页上一页(6，3)分组码的监督矩阵为： 伴随式 100110010011001101H034145235012345012100110010011001101bbbbbbbbbbbbbbbHBsssSTT下一页上一页 (6，3)分组码伴随式计算电路 下一页上一页4、举例（1）已知某线形码监督矩阵为 试列出所有的许用码组下一页上一页（2）设（7，4）线形码的生成矩阵：当信息位为0001时，试求其后的监督位。（3）求上题的监督矩阵。返回下一页上一页5.5.2 汉明码一、概念

29、一、概念汉明距是最早发现的具有纠错能力的码，是一种编码效率较高的分组码，也是一种线性码。对于任何的整数，必存在一个(n，k) 汉明码，码长n和监督元数目r=n-k满足n=2r-1下一页上一页二、特点二、特点1、可以纠正一位传输错误，且d0=32、码长和监督元的关系：n=2r-1记为：（n，k）（ 2r-1，2r-1-r ） 汉明码的编码效率：rrrnk212下一页上一页将监督矩阵记成列矢量的形式，H=h0 h1 hn-2 hn-1，则 0111, 11, 11,01 , 111010, 110000121100000100001eeeeqqqqqqqqqHEssssSrknnrkrrkkTrr

30、T10211201nnnnTeeeeShhhh单个错误（所有的ei只有一位为1）时的伴随式恰好与H的一个列矢量对应，只要H的各个列矢量不为0矢量，且各不相同，则可以纠正单个错误。三、伴随式和错误图样的关系三、伴随式和错误图样的关系下一页上一页四、实例分析四、实例分析(7，4)汉明码汉明码 首先其监督矩阵，此时监督矩阵为H37， 3位二进制码元的组合有8种： 000、001、010、011、100、101、110、111其中不全为零的7个正好可用作监督矩阵的列,可得到监督矩阵： 下一页上一页任意调换监督矩阵各列位置并不影响码的纠错能力，将其转化成典型阵的形式，并由其可以得到生成矩阵G 10101

31、0111001101111000H100110101010110010111H1101000101010001100101110001G由A=MG得到其所有的码字，如下表所示： 下一页上一页假设发送端的码字是A15=1111111，传输过程中第4位a3出现了错误，即接收的码字是B=1110111 此时对应的伴随式为： 信息码组Mm3 m2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a0信息码组Mm3 m2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a00 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 0

32、0 0 0 00 0 0 1 0 1 10 0 1 0 1 0 10 0 1 1 1 1 00 1 0 0 1 1 00 1 0 1 1 0 10 1 1 0 0 1 10 1 1 1 0 0 01 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 11 0 0 0 1 1 11 0 0 1 1 0 01 0 1 0 0 1 01 0 1 1 0 0 11 1 0 0 0 0 11 1 0 1 0 1 01 1 1 0 1 0 01 1 1 1 1 1 1下一页上一页下表给出了该（7，4）汉明码单个错误的错误图样与其对应的伴随式，可以发现

33、伴随式正是监督矩阵的每一列，且该列的位置恰好是码元出错的位置。 由于S不是全零，可判断传输出错，而ST=0 1 1T，是监督矩阵H的第4列,这正是错误码元发生的位置,因此可以得到错误图样为E=0001000，进而按B+E即可纠错。 1101110111100110101010110010111TTHBS下一页上一页错误位置错误图样Ee6 e5 e4 e3 e2 e1 e0伴随式Ss2 s1 s0无错0 0 0 0 0 0 00 0 0b00 0 0 0 0 0 10 0 1b10 0 0 0 0 1 00 1 0b20 0 0 0 1 0 01 0 0b30 0 0 1 0 0 00 1 1b

34、40 0 1 0 0 0 01 0 1b50 1 0 0 0 0 01 1 0b61 0 0 0 0 0 01 1 1返回下一页上一页5.6 循环码一、概念一、概念循环码是一类重要的线性分组码，若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组： (an-2 an-3 a0 an-1) (an-3 an-4 an-1 an-2) (a0 an-1 a2 a1)仍然是该编码中的码组。 返回目录下一页上一页一个(7，3)系统循环码 码表如下所示：信息码组Mm2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a0信息码组Mm2 m1 m0码字Aa6 a5 a4 a3 a2 a

35、1 a00 0 00 0 10 1 00 1 10 0 0 0 0 0 00 0 1 0 1 1 10 1 0 1 1 1 00 1 1 1 0 0 11 0 01 0 11 1 01 1 11 0 0 1 0 1 11 0 1 1 1 0 01 1 0 0 1 0 11 1 1 0 0 1 0表中第表中第2 2码组向右移一位即得到第码组向右移一位即得到第5 5码组；第码组；第5 5码组向右移一码组向右移一位即得到第位即得到第7 7码组。码组。 下一页上一页二、循环码特点二、循环码特点（1）封闭性：指码中任意两许用码组之和仍为一许用码组（2）线性分组码中必有一个全0码组（3）码的最小距离等于非

36、零码的最小重量（4）循环性：循环码中任一许用码字经循环移位后，得到的新码字仍为它的一个许用码字。 下一页上一页三、循环码的数学表示法三、循环码的数学表示法1、码多项式(n，k)循环码中，为了便于描述与计算，经常使用n-1次码多项式来表示码字，码字A =an-1 an-2 a1 a0 ，它对应的码多项式为：上式中x 的值没有任何意义，仅用它的幂代表码元的位置01222211)(axaxaxaxaxAnnnn下一页上一页例如A4=0111001，对应的码多项式为 ：11001110)(345234564xxxxxxxxxxAA4向左循环移1位得A7=1110010，这相当于将A4(x)乘以x，即

37、xxxxxxAxA45647)()(25677)(xxxxxxAA7向左循环移1位得A6=1100101，但若将A7(x)乘以x得到多项式为 对于(7，3)循环码的码多项式，其最高次数不能超过6，解决该问题的办法是对上式作模x7+1运算得余作为码多项式 下一页上一页2、整数的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1 + 1 = 2 0 (模2),1 + 2 = 3 1 (模2),2 3 = 6 0 (模2)。一般说来，若一个整数m可以表示为式中，Q为整数，则在模n运算下，有m p (模n)所以，在模n运算下，一个整数m等于它被n除得的余数。npnpQnm,下一页上一页3、码多

38、项式的按模运算若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则在按模N(x)运算下，有这时，码多项式系数仍按模2运算。例1：x3被(x3 + 1)除，得到余项1，即 例2：因为 x x3 + 1 x4 +x2 + 1 x4 + x x2 +x +1 )()()()(xRxQxNxF）（模)()()(xNxRxF）（模) 1(133xx）（模) 1(113224xxxxx下一页上一页4、循环码的数学表示法在循环码中，设A(x)是一个长度为n的码组，即若则A (x)也是该编码中的一个码组。 例： 一循环码为1100101，即 若给定 i =

39、3，则有 上式对应的码组为0101110，它正是A(x)向左移3位的结果。结论：一个长为n的循环码必定为按模(xn + 1)运算的一个余式。 ）（模) 1()( )(nixxAxAx012211)(axaxaxaxAnnnn1)(256xxxxA）（模) 1()(723535893xxxxxxxxxxTx下一页上一页其计算过程如下 ：)() 1(1)(672567xAxxxxxxA模1111256725677xxxxxxxxxxxxxxA4567)(例如：下一页上一页四、生成多项式和生成矩阵四、生成多项式和生成矩阵1、生成多项式如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该

40、码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如(7,3)循环码中， 1)()(2341xxxxAxg)()()(0)(270 xgxxAxgxA其它码多项式都是g(x)的倍式， 即 下一页上一页在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(nk)次多项式，而且这个g(x)还是这种(n, k)码中次数为(nk)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组

41、，且此码组多项式的次数将小于(nk)，即连续“0”的个数多于(k1)。显然，这是与前面的结论矛盾的。我们称这唯一的(nk)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n, k)循环码就被确定了。下一页上一页因此，一个多项式为(n,k)循环码的生成多项式g(x)必须符合以下三个条件：（1）g(x)是xn-1的一个因式； （2）g(x)是一个n-k次多项式； （3）g(x)多项式中必有一个常数项1。 下一页上一页g(x) 、xg(x)、x2g(x)、xk-1g(x)是(n，k)循环码的k个线性无关的码字，所以可得其生成距阵G，用码多项式表示G的各行： 2、生成矩阵若信息码组M=

42、mk-1 mk-2 m0，则：)()()()()(21xgxxgxgxxgxxGkk)()()()()()(012211xgmxxgmxgxmxgxmxMGxAkkkk)()()(012211xgxMxgmxmxmxmkkkk下一页上一页例如：上表中的编码为(7, 3)循环码，n = 7, k = 3, n k = 4，其中唯一的一个(n k) = 4次码多项式代表的码组是第二码组0010111，与它对应的码多项式即生成多项式为：g(x) = x4 + x2 + x + 1。 码组编码组编号号信息位信息位监督位监督位码组编码组编号号信息位信息位监督位监督位A6a5a4a3a2a1a0a6a5a

43、4A3a2a1a01000000051001011200101116101110030101110711001014011100181110010下一页上一页将此g(x)代入上矩阵，得到上式不符合G = Ik Q形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。将该矩阵典型化之后，再按照A=MG编码才能得到(7，3)系统循环码；实际应用中，系统循环码的编译码通常是由g(x)经过简单的代数运算来实现。 1110100011101000111011)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG下一页上一页3、举例说明已知循环码的生成多项为 ，当信息位

44、为1000时，写出它的监督位和整个码组。解：由生成多项式可知n-k=3，而k=4，所以n71)(3xxxg1)()()()()()()()()(3242353462321xxxxxxxxxxxxgxxgxgxxgxxgxxgxgxxgxxGkk下一页上一页0001001001011011G011110100000 第1行+第3行+第4行 第1行0001001001011000G011110100101 第2行+第4行 第2行 0001001001001000G011110111101 非典型典型当信息位为1000时，整个码组为下一页上一页10003456GaaaaA00010010010010

45、000111101111011000101监督位为 101下一页上一页系统 (n，k)循环码码字： 编码原理用码多项式来表示为： 五、循环码的编码五、循环码的编码A =an-1 an-2 an-k ar-1 a1 a0 = mk-1 mk-2 m0 ar-1 a1 a0 01112211)(axaxaxaxaxaxArrknknnnnn011102211)(axaxaxmxmxmrrknkkkk)()(xrxxMkn下一页上一页式中M(x)是信息码组码多项式，所以只需要确定r(x) 已知循环码的所有码字都能够被g(x)整除，r(x)可由下式确定：(n，k)循环码的生成多项式为： )x(g)()(模knxxMxr 编码器1)(12211 xgxgxgxxgrrr其