数据通信课件第三章(7终)完成2

1、12 了解差错控制的基本概念和基本原理。 掌握差错控制的基本方式及码距与检错纠错能力。 掌握奇偶校验码、汉明码、线性分组码和循环码的编码和解码。 掌握ARQ原理及滑窗协议。3 造成误码的原因主要有：一是信道不理想造成的符号间干扰；二是噪声对信号的干扰。 对于前者通常通过均衡方法可以改善以至消除。后者是造成传输差错的主要原因。差错控制是对后者采取的技术措施，目的是提高传输的可靠性。 1差错控制的基本概念 差错即误码。差错控制的核心是差错控制编码，即在信息码元序列中加入监督码元就称为差错控制编码，也称为纠错编码。4 2差错类型 噪声分为两类：随机噪声和脉冲躁声。随机噪声导致随机差错，脉冲噪声造成突

2、发差错。 随机差错，又称独立差错，是指错码的出现是随机的，且错码之间是统计独立的。存在这种差错的信道称为随机信道，例如，微波接力和卫星转发信道。 突发差错，是指成串集中出现的错码，即在一些短促的时间区内会出现大量错码，而在这些短促的时间区间之间又存在较长的无错码区间。产生突发差错的信道称为突发信道，如短波等信道。 既存在随机差错又存在突发错误，且哪一种都不能忽略不计的信道称为混合信道。53.1.2差错控制方式1. 检错重发（ARQ） ARQ的思路 这种差错控制方式在发送端对数据序列进行分组编码，加入一定监督码元使之具有一定的检错能力，使成为能够发现错误的码组。接收端收到码组后，按一定的规则对其

3、进行有无差错的判断，并把判断结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一边，直到接收端认为已正确收到信息为止。ARQ的重发方式ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。6 ARQ分为停等式ARQ和连续式ARQ，连续式ARQ又分为退回N步ARQ和选择重发ARQ。 1停等式ARQ （1）工作原理 发送方每发完一数据帧，停下来等待接收方应答，同时启动超时定时器，若发送方收到一确认帧，接着发送下一数据帧，若接收到一否认帧或超时定时器到时仍未收到对方应答则重发上一数据帧。 接收方每收到一帧都要给出应答，若收到一正确帧或重发帧，发回确认帧，若收到一错误

4、帧，发回否认帧。 （2）收发示例：如图3-10（a）所示。 （3）特点：传输效率低，但工作原理简单。7 2退回N步ARQ （1）工作原理 发端可不等待应答信号到达连续发送若干个数据帧（N帧），且每发完一帧后，都启动超时定时器，若发方收到第一帧的确认帧，继续发送第（N+1）帧，若接收到一否认帧或超时定时器到时仍未收到对方应答，则重发自该帧起的所有数据帧，即重发前N帧。 接收端接收到若干数据帧后发回应答，确认帧表示正确接收该帧及以前各帧，否认帧表示对当前帧的否认，同时也表示对以前各帧的确认。接收方只能按序接收，若收到乱序的帧，则一律丢弃。 （2）收发示例：如图3-10（b）所示。这里N5。 （3）

5、特点：传输效率较高。但当N较大时，效率会大大下降。8 3选择重传ARQ （1）工作原理 在退回N步ARQ基础上，当一个帧有错时，只发有错的这一帧，其余（N1）个正确帧先接收存储起来，待有错帧经重发正确后，一起再发确认帧，收端将收到的帧重新排序，送给用户。 （2）收发示例： 如图3-10（c）所示。 （3）特点：传输效率最高，但它的成本也最贵，接收端必须有足够的存储空间，把接收到的帧重新排序后送给用户。 可见，选择重传ARQ方式可以接收乱序帧，而退回N步ARQ方式的收端只能按顺接收。 9 图3-10 ARQ差错控制系统的工作方式10 ARQ的重发方式 其中听候重发是发送端每发送一个码组就停下来等

6、候接收端的应答信号，若收到确认信号ACK，则接着发下一个码组；若收到否认信号NAK，则重新发送刚才发送的码组。这种方式在发送两个码组之间有停顿时间，使得传输效率受到影响，但是由于工作原理简单，在数据通信中人得到应用。 返回重发其是在发送端无停顿地送出一个个连续码组，不再等待接收端返回的ACK信号，但一旦接收端发现错误并返回NAK信号，则发送端从出错码组开始重新发送前一段N组码组，N的大小取决于信号的处理及传输所带来的时延。这种返回重发系统的传输效率比停发等候重发系统有很大的改进，在许多数据传输系统中得到应用。 选择重发也是连续不断地发送码组，接收端检测到错误后发回NAK信号。与返回重发系统不同

7、的是，发送端不是重发前面的所有N个码组，而是只重发有错误的那一个码组。显然选择重发系统的传输效率最高，但它的成本也最贵，因为它要求比较复杂的控制，在发送端和接收端都要求有数据缓存器。1112ARQ的优缺点在检测到错误时需反向信道回传NAK信号，实时性差。ARQ方式在信息码后面所加的监督码不多，所以信息传输效率较高。译码设备较简单。13（2）前向纠错（FEC） FEC的思路 前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码字，接收端的译码器根据编码规律检验出错误的位置并自动纠正。14FEC的优缺点不需要反向信道，由于能够自动纠错，不要求重发，因而时延比较小，实时性好。缺点是

8、所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；为了纠正较多的错码，译码设备复杂；而要求附加的监督码也较多，传输效率就低。15 (3)混合纠错检错（HEC） HEC的思路 混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码组，接收端收到码组后，检查错误情况，如果错误在纠错能力范围内，则自动纠正；如果错误很多，超出纠正能力的范围，则经过反相信道要求发送端重发。 16 HEC的优缺点 混合纠错检错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，因而近年来，在数据通信系统中采用较多。17(4)信息反馈（IRQ）

9、IRQ的思路 IRQ又称为回程校验，这种方式在发送端不进行纠错编码，接收端把收到的数据序列全部由反向信道送回发送端，发送端自己比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原数据序列再次传输指导发送端没有发现错误为止。18IRQ的优缺点这种方式的优点是不需要纠错、检错的编译器，设备简单。缺点是需要和前向信道相同的反向信道，实时性差。发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。而且这种方式还可能导致原本没有错误的码组在回传的过程中出错。所以其一般用在传输速率低，数据信道差错率较低，且具有双向传输线路及控制简单的系统中。

10、19图3-1 差错控制的基本类型201.差错控制编码的分类(1)按码组的功能分，有检错码和纠错码两类。依据是编码后的码字是具有检错能力还是具有纠错能力。 (2)按码组中监督码元与信息码元之间的关系分，有线性码和非线性码两类,依据是信息码元与监督码元之间是否存在线性关系。 (3)按照信息码元与监督码元的约束关系，又可分为分组码和卷积码两类。 依据是信息码元与监督码元之间的关系是否局限在一个码字内，是就是分组码，否就是卷积码。 (4)按照信息码元在编码前后是否保持原来的形式不变，可划分为系统码和非系统码。 依据码字中的信息位与监督位是否分开，分开就是系统码，否就是非系统码。 (5)按纠正差错的类型

11、可分为纠正随机错误的码和纠正突发错误的码。(6)按照每个码元取值来分，可分为二进制码与多进制码。3.2差错控制的基本原理21 1差错控制的基本原理 差错控制的核心是差错控制编码，不同的编码方法，有不同的检错或纠错能力，有的编码只能检错，不能纠错。一般，付出的代价越大，检（纠）错的能力就越强。 纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码。监督码不载荷信息，它的作用是用来监督信息码在传输中有无差错，对用户来说是多余的，但它提高了传输的可靠性。但是，监督码的引入，降低了信道的传输效率。 因此，通过纠错编码所提高的可靠性是以牺牲信道利用率为代价换取的。一般说来，引入监督码越多，码

12、的检错、纠错能力越强，但信道的传输效率下降也越多。221、有关名词 纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，即码的检错和纠错能力是用信息量的冗余度来换取的。 加入监督码越多，码的检错、纠错能力越强，但信息传输效率下降也越多。 信息码元：指编码之前原始的数字码元。 监督码元：指为了纠检错而在信息码元后增加的多余码元。 码字（码组）：由信息码元与监督码元组成的一定长数字序列。 码集：所有许用码字集合。 232基本概念 码重：码组中非零码元的数目为码组的重量，简称码重。例如，“010”码组的码重为1，“011”码组的码重为2。 码距：把两个码组中对应码位上具有不同二进制码元

13、的位数定义为两码组的距离，简称码距。例如，（00）与（01）码距为1，（110）与（101）码距为2。 汉明距离：在一种编码中，任意两个码组间距离的最小值，称为这一编码的最小码距或称为这一编码的汉明（Hamming）距离，以dmin表示。如，在3位码组中，若8种码组都作为许用码组时，任意两码组间的最小距离为1，记作dmin=1。对于 的编码组，可以在三维空间中说明码距的几何意义。如图3-2所示。3n24 2码距与纠检错能力 （1）为检测e个错码，要求最小码距 dmine+1（3-1） （2）为纠正t个错码，要求最小码距 dmin2t+1（3-2） （3）为纠正t个错码，同时检测e（et）个错码

14、，要求最小码距 dmin e+t+1（3-3） 上述三式可以分别用图3-3（a）、 （b）和（c）来加以说明。 纠检结合：在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作；同时对一些错码数较多的码组，在超过该码的纠错能力后，能自动按检错重发方式工作，以降低系统的总误码率。这种方式就是“纠检结合”。25图3-2 码距的几何解释图3-3 码距与检错纠错能力的关系26 编码效率是指一个码组中信息位所占的比重，用R来表示。即 （3-4） 其中，k为信息码元的数目（信息位长度）；n为编码组码元的总数（编码后码组长度：n=k+r）；r 为监督码元的数目（监督位长度）。 显然，R越大编

15、码效率越高。nkR 27 （1）按码组的功能分，有检错码和纠错码两类。 在译码器能够检测出错码，但不知道错码的准确位置的码，称为检错码，它没有自动纠正错误的能力。 在译码器中不仅能发现错误，而且知道错码的准确位置，自动进行纠正错误的码，则称为纠错码。 （2）按码组中监督码元与信息码元之间的关系分，有线性码和非线性码两类。 线性码是指监督码元与信息码元之间的关系呈线性关系，即可用一组线性代数方程联系起来；非线性码指的是二者是非线性关系，目前很少使用。28 （3）按照信息码元与监督码元的约束关系，又可分为分组码和卷积码两类。 分组码是将信息序列以每k个码元分组，通过编码器在每k个码元后按照一定的规

16、则产生r 个监督码元，组成长度为n=k+r 的码组，每一码组中的r 个监督码元仅监督本码组中的信息码元，而与别组无关。分组码一般用符号（n，k）表示，其结构规定为图3-4的形式。分组码又可分为循环码和非循环码两类。 卷积码是把信源输出的信息序列，以每k0个码元分段，通过编码器输出长为n0（n0k0）的一段码。但该段码的（n0 k0）个监督码元不仅与本段码信息码元有关，而且还与前面m1段的信息码元有关，前后形成了约束关系。一般用（ n0, k0 ,m）表示。29 （4）按照信息码元在编码前后是否保持原来的形式不变，可划分为系统码和非系统码。 系统码的信息码元和监督码元在分组内有确定的位置，而非系

17、统码中信息码元则改变了原来的信号形式。系统码的编码和译码相对比较简单些，得到广泛应用。 （5）按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码。 （6）按照每个码元取值来分，可分为二进制码与多进制码。 图3-5示出了各种抗干扰编码的类型。30 图3-2 系统码与非系统码k位k位n位（其中k位信息码元）信息码元监督码元n-k位n-k位31图3-5 抗干扰码的分类图3-4 分组码的结构32 常用的差错控制编码有： 奇偶校验码 行列监督码 恒比码 重复码 正反码33 奇偶校验码是一种检错码，又称奇偶监督码，属于分组码。 1一般奇偶校验码 奇偶校验码分奇校验码和偶校验码，两者构成原理是一样的。

18、 （1）基本原理 在奇偶校验码中，无论信息位有多少位，校验位只有一位。 编码规则：先将所要传输的数据码元分组，在分组数据后面附加一位校验位，使得该组码连同校验位在内的码组中的“1”的个数为偶数（称为偶校验）或奇数（称为奇校验），在接收端按同样的规律检查，如发现不符就说明产生了差错，但是不能确定差错的具体位置，即不能纠错。34 在偶检验时，满足下式条件 （3-5） 在奇校验时，满足下式条件 （3-6） 表3-1是按偶校验规则插入监督位的。 （2）纠错能力 只能发现单个或奇数个错误，而不能检测出偶数个错误。被用于以随机错误为主的计算机通信系统。此方法难于对付突发错。0021aaann1021aaa

19、nn表3-1 偶校验监督码消 息信息位监督位消 息信息位监督位晴000阴101云011雨11035)(0)(11010模二偶监督模二奇监督niiniiaa： ITU-T建议同步数据传输使用偶监督异步数据传输使用奇监督3.3.1 奇偶监督码返回36 2垂直奇偶校验码 （1）基本原理 垂直奇偶校验是在b7位表示字符的数据位后再附加第b8位校验位，表3-2以ASCII码的数字09为例说明垂直奇偶校验的编码。 接收端根据收到的b1 b7重新计算奇偶校验码元，将此与收到的b8相比较。如相同则无错，否则存在错误。 （2）纠错能力 垂直奇偶校验编码，无论是采用偶校验还是奇校验，将检出全部奇数个差错，而出现的

20、全部偶数个差错均不能发现。37 表3-2垂直奇偶校验字符位0123456789b10101010101b20011001100b30000111100b40000000011b51111111111b61111111111b70000000000b8（校验）011010011038 3水平奇偶校验码 （1）基本原理 将要进行奇偶校验的码元序列按行排成方阵，每行为一组奇偶校验码（见表3-3），但发送时则按列的顺序传输，接收端仍将码元排成发送时的方阵形式，然后按行进行奇偶校验。 （2）纠错能力 可发现某一行上所有奇数个错误及所有长度方阵中行数的突发错。表3-3水平奇偶校验码信 息 码 元校验码元1

21、11001100011101001101010000111011000100001001100111011139 4二维奇偶校验码 （1）基本原理 二维奇偶校验码又称行列校验码或方阵码。其方法是水平监督的基础上对表3-3方阵中每一列再进行奇偶校验，就可得到表3-4所示的方阵。发送是按列序顺次传输。表3-4二维奇偶校验码信 息 码 元校验码元1110011000111010011010100001110110001000010011001110111校验码元0110110001140 （2）纠错能力 能发现某行或某列上的奇数个错误和长度不大于行数（或列数）的突发错误。 有可能检测出偶数个错码。因

22、为如果每行的监督位不能在本行检出偶数个错误时，则在列的方向上有可能检出。当然，在偶数个错误恰好分布在矩阵的4个顶点时，这样的偶数个错误检测不出来。 可以纠正一些错误。例如，当某行某列均不满足监督关系而判定该行该列交叉位置的码元有错，从而纠正这一位上的错误。 检错能力强，又有一定纠错能力，且实现容易得到广泛应用。41该码的特点是码字中1，0数目恒定，亦即1，0数目之比恒定。电传通信中普遍采用3：2码，又称5中取3码，如下所示 国际上通用的ARQ电报通信系统中，采用7中取3码。 3.3.2 恒比码42恒比码的优点：（1）简单（2）能检测出单个和奇数个错误，还能部分检测出偶数个错误（3）适于传输电传

23、机或其他键盘设备所产生的数字、字母和符号；但不适用于信源来的二进制随机数字序列返回43(3，1)重复码两个码字为000和111，其最小码距为3；(n，1)重复码也只有全0码和全1码两个码字，其最小码距为n，却有2n-2个禁用码组，随着码长的增大，其冗余也变得很大；该码随码长增加，具有很强的纠检错能力，但其编码效率的急剧下降；重复码并不是一种优秀的编码方案，仅用于速率很低的数据通信系统中。重复码只有一位信息码元，监督码元是信息码元的重复，所以仅有两个码字；3.3.3 重复码返回44该码型多用于10单位码的前向纠错设备中，可以纠正一位错误，发现全部两个以下的错误，以及大部分两个以上的错误，其本质就

24、是五单位码的重复；编码规则：信息码组中1的数目为奇数时，监督码是信息码的重复即正码； 信息码组中1的数目为偶数时，监督码是信息码的反码。例如：M=11001，则对应得码字为1100111001M=11101，则对应得码字为11101000103.3.4 正反码45译码规则：首先将收到的码字重的信息位和监督位按对应位作模2运算，得到一个5位码组，若该码字中有奇数个1，则将其作为校验码组，若有偶数个1，则取其反码作为校验码组。然后，按照下表进行纠检错译码。例如：0110101101，则合出码组为00000，信息元中有3个1，奇数，所以检验码组即合成码组00000，对应表，则传输正确。如010101

25、0111，则合成码组为11101，因为信息元有2个1，偶数，所以校验码为合成码组的反码，00010，则对照表，监督元有1位出错，在校验码组中1对应的位置，即监督元10111中斜体1出错。如0111010110，则合成码组为11000，信息元中有3个1，则校验码组等于合成码组，11000，则错误情况判断：传输出错，且错误位数大于1。46 正反码错误判决表 校验码组的形式错误情况判断1全“0”传输正确24个“1”，1个“0”信息元有1位出错，在校验码组中“0”对应的位置34个“0”，1个“1”监督元有1位出错，在校验码组中“1” 对应的位置4其它形式传输出错，且错误位数大于1返回47 1汉明码 汉

26、明码是一种能够纠正一位错码且编码效率较高的线性分组码。 （1）基本原理 奇偶校验时，如按偶校验，由于使用了一位监督位a0，故它就能和信息an1 an2 a1一起构成一个代数式，如式（3-5）所示。在接收端解码时，实际上就是在计算 （3-7） 若S=0，就认为无错；若S=1，则认为有错。上式称为监督关系式，S 称为校正子。一个校正子S只有0和1两种取值，只能代表有错和无错两种信息，而不能指出错码的位置。021aaaSnn48 如果监督位增加一位，即变成两位，则将增加一个类似于式（3-7）的监督关系式，接收时按照两个监督关系式就可计算出两个校正子，记作S1和S2。 S1 ，S2共有4种组合：00，

27、01，10，11，故能表示4种不同信息。若用其中一种表示无错，则其余221=3种就有可能用来指示一位错码的3种不同位置。 同理，若有r位监督位，就可构成r个监督关系式，计算得出的校正子有r 位，可用来指示一位错码的2r1个可能位置。 一般来说，若码长为n，信息位数为k，则监督位数r=nk。若用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求 2r1n或2r k+r+1 （3-8） 上式是汉明码的必要条件。49 （2）编码示例 设分组码（n，k）中k=4。为了纠正一位错码，由式（3-8）可知，要求监督位数r3。 若取r =3，则n=k+r=7。用a6a5a0表示这7个码元，用S

28、1，S2 ，S3 表示3个监督关系式中的校正子，则S1，S2 ，S3 的值与错码位置的对应关系可以规定如表3-5所列。表3-5校正子与错码的位置S1 S2 S3错码位置S1 S2 S3错码位置S1 S2 S3错码位置S1 S2 S3错码位置0 0 10 1 0a0a11 0 00 1 1a2a31 0 11 1 0a4a51 1 10 0 0a6无错50 由表3-5的规定可知，仅当发生一个错码，其位置在a2 ，a4 ，a5或a 6， 校正子S1为1，否则为0。这就意味着a2 ，a4， a5和a 6 四个码元构成偶数监督关系，即 （3-9）同理 a1 ，a3 ，a5和a 6及a0 ，a3 ，a4

29、和a 6 也分别构成偶数监督关系 （3-10） （3-11） 发送端编码时，监督位应使上3式中的S1，S2，S3均为0，于是有： 24561aaaaS13562aaaaS03463aaaaS（3-12） 解出000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa（3-13） 已知信息位，就可算出监督位。由此得出如表3-6所示许用码组。51 接收端收到每个码组后，先按式（3-9），式（3-10）和式（3-11）计算出S1，S2和S3，如不全为0，再按表3-5确定误码的位置，然后加以纠正。例如，若接收码组为0100101，按式计算可得： S1 =0，

30、 S2 =1， S3 =1，由表3-5可知在a3位有一错码。表3-6 （7，4）汉明码的许用码组信 息 位监 督 位信 息 位监 督 位a6 a5 a4 a3a2 a1 a0a6 a5 a4 a3a2 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 00 1 11 0 11 1 01 1 01 0 10 1 10 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 1 11 0 00 1 00 0 10 0 10 1 01 0 01 1 152

31、 （3）纠检错能力 按上述方法构成的码称为汉明码。表3-6所列的（7，4）汉明码的最小码距dmin=3，因此，根据式（3-1）和式（3-2）可知，这种码能纠正一个错码或检测两个错码。 （4）编码效率 汉明码有着较高的编码效率，它的效率为 当n很大时，编码效率接近1，可见汉明码是一种高效码。nrrrnkRrrr1121121253 一线性分组码的定义及特点1、线性分组码定义 线性分组码就是既是线性码又是分组码的编码。线性码就是指监督码元与信息码元之间满足一组线性方程的码组；分组码就是监督码元，仅与本码组中的信息码有关。2、线性分组码满足的特点（1）封闭性：分组码中任意两码组的模2和仍为其一码组；

32、（2）有零元：分组码中有一个码组的码元为全零；（3）最小码距等于码集中非零码的最小码重。这是因为：故： CWBAWBAd, CWBAWBAd, CWBAdminmin,54 (1)线性分组码的编码过程 以 分组码为例， ，其中 为信息码元， 为监督码元。根据前面的知识其能够纠正一位错码，或者是检测两位错码。第一步，首先通信双方得知道由信息码元所产生监督码元的关系式，例如有下述关系式： （3-13）将上式还原为下式： 4 , 70123456aaaaaaaA 3456aaaa012aaa034613562456aaaaaaaaaaaa55 （3-12）进步将对于有码元存在的地方用表示，将没有码元

33、的地方用表示，将用替换，则将上式可以改写为下述的线性方程组：式（3-12）现将它改写成 （3-14） 上式中已将“ ”简写为“+”，仍表示“模2”加。 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa000034613562456aaaaaaaaaaaa56 式（3-14）也可以写成矩阵形式 （模2）（3-15） 简记为 HA T=0T或AH T=0 （3-16） 其中H = A=a6 a5 a4 a3 a2 a1 a0 0=0 0 00001001101010101100101110123456aaaaaaa

34、100110101010110010111H 称为线性码的监督矩阵。H 给定，监督位和信息位的关系就定了。57 从式（3-14）和式（3-15）都可看出，H 的行数就是监督关系式的数目，它等于监督码元的数目r，而H 的列数就是码长n，这样H 为rn 阶矩阵。 式（3-15）中的矩阵H 可以分成两部分 （3-17） 式中P为rk阶矩阵，Ir为rr 阶单位方阵。将具有PIr形式的H 矩阵称为典型形式的监督矩阵。rkrIPH10001000111011011011144447658 （2）生成矩阵 类似于式（3-12）改变成式（3-15）中矩阵形式那样，式（3-13）也可以改写成 （3-18） 比较

35、式（3-17）和式（3-18），可以看出式（3-18）右式前部矩阵即为P。对式（3-18）两侧作矩阵转置，得 Q （3-19）3456012110110110111aaaaaaa3456T34563456012110101011111aaaaPaaaaaaaaaaa59 式中Q为一kr 阶矩阵，它为矩阵P的转置，即 Q=P T （3-20） 式（3-19）表明，信息位给定后，用信息位的行矩阵乘矩阵Q就可计算出各监督位。 要得到整个码组，将Q的左边加上一个kk阶单位方阵，就构成一个新的矩阵G，即 （3-21） G 称为生成矩阵，因为由它可以产生码组，即有A=a6a5a4a3a2a1a0=a6a5

36、a4a3G （3-22）1101000101010001100101110001QIGk60 上式表明，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵。 其中 是信息码组，其按照自然编码进行编码。经运算 线性分组码的所有许用码组如下： 3456aaaa4 , 761假设发送端的码字是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

37、 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 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

38、 1 0 01 1 1 1 1 1 162(3)校正子和检错6364S与E的关系（举例）6566任意调换监督矩阵各列位置并不影响码的纠错能力，将其转化成典型阵的形式，并由其可以得到生成矩阵G 100110101010110010111H1101000101010001100101110001G67下表给出了该（7，4）汉明码单个错误的错误图样与其对应的伴随式，可以发现伴随式正是监督矩阵的每一列，且该列的位置恰好是码元出错的位置。 由于S不是全零，可判断传输出错，而ST=0 1 1T，是监督矩阵H的第4列,这正是错误码元发生的位置,因此可以得到错误图样为E=0001000，进而按B+E即可纠错。

39、 1101110111100110101010110010111TTHBS68错误位置错误图样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 1b40 0 1 0 0 0 01 0 1b50 1 0 0 0 0 01 1 0b61 0 0 0 0 0 01 1 1返回69四、举例1、例：设一线性分组码的生成矩阵为： 011010101001110100G（1）求出监督矩阵，确定码中

40、n=?，k=?（2）写出监督位的关系式，单个错误图样相应的伴随式，试求码的所有码字。（3）检验011101,101101是否为该码的码字，若不是予以纠正。70解：（1）由从 中得到 ， 。（2）监督位关系式为 伴随式 所有码组011010101001110100G100101010110001011H6n3k035134245aaaaaaaaaTEHS 00011111001110100101110110111001101011010000000001234534560123456aaaaaaGaaaaaaaaaaaA71（3）对 时， ，故无错误。 对 时， ，故有错误。 比较得 ,故 。

41、0111011B00011THBS0111012B01122THBSTEH011001000E1001001EBA723.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)仍然是该编码中的码组。 返回目录73一个(7，3)系统循环码 码表如下所示：信息码组Mm2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a0信息码组Mm2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a00 0 00 0

42、 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码组。码组。 74二、循环码特点二、循环码特点（1）封闭性：指码中任意两许用码组之和仍为一许用码组（2）线性分组码中必有一个全0码组（3）码的最小距离等于非零码的最小重量（4）循环性：循环

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

44、(xxxxxxAA7向左循环移1位得A6=1100101，但若将A7(x)乘以x得到多项式为 对于(7，3)循环码的码多项式，其最高次数不能超过6，解决该问题的办法是对上式作模x7+1运算得余作为码多项式 772、整数的按模运算在整数运算中，有模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,783、码多项式的按模运算若任意一个多项式F(x)被一个n次多项式N(x)除

45、，得到商式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(113224xxxxx794、循环码的数学表示法在循环码中，设A(x)是一个长度为n的码组，即若则A (x)也是该编码中的一个码组。 例： 一循环码为1100101，即 若给定 i = 3，则有 上式对应的码组为0101110，它正是A(x)向左移3位的结果。

46、结论：一个长为n的循环码必定为按模(xn + 1)运算的一个余式。 ）（模)1()( )(nixxAxAx012211)(axaxaxaxAnnnn1)(256xxxxA）（模) 1()(723535893xxxxxxxxxxTx80其计算过程如下 ：)() 1(1)(672567xAxxxxxxA模1111256725677xxxxxxxxxxxxxxA4567)(例如：81四、生成多项式和生成矩阵1、生成多项式如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如(7,3)循环码中， 1)()(

47、2341xxxxAxg)()()(0)(270 xgxxAxgxA其它码多项式都是g(x)的倍式， 即 82在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(nk)次多项式，而且这个g(x)还是这种(n, k)码中次数为(nk)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(nk)，即连续“0”的个数多于(k1)。显然，这是与前面的结论矛盾的。我们称这唯一的(nk)次

48、多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n, k)循环码就被确定了。83因此，一个多项式为(n,k)循环码的生成多项式g(x)必须符合以下三个条件：（1）g(x)是xn+1的一个因式； （2）g(x)是一个n-k次多项式； （3）g(x)多项式中必有一个常数项1。 84g(x) 、xg(x)、x2g(x)、xk-1g(x)是(n，k)循环码的k个线性无关的码字，所以可得其生成距阵G，用码多项式表示G的各行： 2、生成矩阵若信息码组M= mk-1 mk-2 m0，则：)()()()()(21xgxxgxgxxgxxGkk)()()()()()(012211xgmxxgmxgx

49、mxgxmxMGxAkkkk)()()(012211xgxMxgmxmxmxmkkkk85例如：上表中的编码为(7, 3)循环码，n = 7, k = 3, n k = 4，其中唯一的一个(n k) = 4次码多项式代表的码组是第二码组0010111，与它对应的码多项式即生成多项式为：g(x) = x4 + x2 + x + 1。 码组编码组编号号信息位信息位监督位监督位码组编码组编号号信息位信息位监督位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a010000000510010112001011161011100301011107110010140111001811100108

50、6将此g(x)代入上矩阵，得到上式不符合G = Ik Q形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。将该矩阵典型化之后，再按照A=MG编码才能得到(7，3)系统循环码；实际应用中，系统循环码的编译码通常是由g(x)经过简单的代数运算来实现。 1110100011101000111011)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG87五、监督多项式和监督矩阵五、监督多项式和监督矩阵 1、监督多项式： 例如前面讲述的循环码对应监督多项式 11111xhxhxxgxxhkkkn 1113247xxxxxxxh882、监督矩阵 监督矩阵的产生有两

51、种方法：n（1）由生成矩阵产生，这种方法跟前面讲述的线性分组码的编码时由生成矩阵产生监督矩阵方法一样。例如循环码的监督矩阵为：1000101010011100101100001011H89n（2）由监督多项式生成首先由监督多项式 生成 ： （6-5）即 除 与1前面系数，其余各多项式依次颠倒位置。例如在 循环码中， 故则有监督多项式所对应的矩阵为： xh xh* 1111*xhxhxxhkkk xh*kx3 , 7 11111xhxhxxgxxhkkkn 123*xxxh 1010001111001001101001101000000110100110100110100110100002313

52、42453561xxxxxxxxxxxxxhxxhxhxxHr注：生成矩阵与监督矩阵结果不唯一，但是将其化为标准型是唯一的。 90 纠错译码原理确定循环码的纠错能力;根据 模g(x)计算伴随式，若S(x)则判定传输出错。 根据 模g(x)找到伴随式对应的错误图样由A(x)=B(x)+E(x)纠错。)()(xBxS)()(xExS返回关于循环码在接收端的检错有两种方法： 第一，与前面讲述的线性分组码检错方法一样，利用监督矩阵进行检错。第二，用接收到码组多项式除以生成多项式，若能够除尽说明无错，若是余式不为零表示传输中出错。91六、举例说明六、举例说明已知(7,4)循环码的生成多项为 ，求（1）生

53、成矩阵 （2）监督矩阵 （3）码集中全部码组写出它的监督位和整个码组。解：（1）由生成多项式可知n-k=3，而k=4，所以n71)(3xxxg1)()()()()()()()()(3242353462321xxxxxxxxxxxxgxxgxgxxgxxgxxgxgxxgxxGkk920001001001011011G011110100000 第1行+第3行+第4行 第1行0001001001011000G011110100101 第2行+第4行 第2行 0001001001001000G011110111101 非典型典型93 （2）由生成矩阵可以得到监督矩阵为 （3）生成的全部码组为1101

54、00101110101110100HGaaaaaaaaaaaA3456012345694从中可以看到上述码组有三个循环：第一：编号为0和15的自循环；第二：含有3个1的循环；第三：含有4个1 的循环。码组编号码组编号信息位信息位监督位监督位码组编号码组编号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0000000008100010110001011910011102001011010101001130011101111011000401001111211000105010110013110100160110001141110100701110101511111

55、11181261152139410131473953.8.1 卷积码一、定义一、定义卷积码通常记作(n，k，m)，其中k为一次移入编码器的比特数目， n为对应于k比特输入的编码输出，m为约束长度。 卷积码有记忆的特性：卷积编码器的输出不仅和当前输入的k比特信息有关，而且还依赖于之前输入的m-1组k比特信息。定义卷积码的编码效率为k/n，可以将其理解为同一时刻，编码器有k位比特信息输入，有n位编码比特输出。 返回目录96二、编码器结构二、编码器结构卷积码的编码器由移位寄存器和加法器组成。 输入移位寄存器有m段， 每段有k级， 共mk位寄存器， 主要负责存储每段的k个信息码元； 各信息码元通过n个模2加法器相加， 产生每个输出码组的n个码元， 并寄存在一个n级的移位寄存器中移位输出。 编码过程是输入信息序列与由移位寄存器和模2加法器之间连接所决定的另一个序列的卷积， 因此称为卷积码。 97 (n，k，m)卷积编码器结构 98 卷积码又称连环码，是一种非分组码，主要应用于前向纠错（FEC）数据通信系统中。 1基本概念 卷积码是在任何一段规定时间内编码器产生的n个码元，不仅取决于这段时间中的k个信息码元，而且还取决于前N1段规定时间内的信息码元。这时，监督位监督着这N