7交大通信技术基础课件6a

1、1第六章第六章 差错控制编码差错控制编码第一节差错控制的基本概念第二节检错和纠错的基本概念第三节几种常用的简单差错控制编码第四节 汉明码第五节 线性分组码第六节 循环码2第一节 差错控制的基本概念在中等传输速率（12002400bps）采用一般的调制方法，对于干线有线载波信道误码率Pe大约为10-410-5数量级，对于短波无线信道误码率大约为10-210-3数量级。显然这样的误码率不适应大多数数据通信的要求，比如数字电话Pe为10-4 ，计算机通信Pe为10-6 。为了显著提高误码率指标，除了根据不同的信道条件选择合适的传输方式外，对于乘性干扰引起的码间干扰可以采用均衡的办法纠正；加性干扰的影

2、响则从其他途径解决，如：调制方式、解调方法、发送功率。通常采用上述措施后仍难以满足要求，所以要考虑差错控制措施。31、差错分类从差错控制角度，按加性干扰引起的错码分布规律分类：（1）随机差错又称独立差错：是指独立稀疏互不相关发生的差错。存在这种差错的信道称为无记忆信道或随机信道。（2）突发差错：是指一串串、甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。存在这种差错的信道称为突发信道（3）混合差错：所出现的错误不是单一的，而是随机差错和突发差错并存的。这两类错误形式并存的信道称为混合信道。42、差错控制方式对于不同类型的信道，应采用不同的差错控制技术。（1）前向纠错（FEC）法、（2

3、）反馈重传（ARQ）法、（3）混合纠错（HEC）法、（4）信息反馈（IRQ）法。可以纠正错误的码FEC能够发现错误的码ARQ应答信息信息信号IRQ信息信号能够发现和纠正错误的码HEC应答信息纠错检错纠错检错53、差错控制的基本思想差错控制的基本思想：是通过对信息序列作某种变换，使原来彼此独立、相关性很小的信息码元序列产生某种相关性，从而在接收端有可能依据这种相关的规律来检查，进而识别或纠正传输信息序列的差错。变换的方法不同，就构成了不同的差错控制编码方法（纠错编码）。有的可以纠错、有的仅能检错。纠错编码方法大多是按照某种规律在用户信息序列中插入一定数量的新码元，这些新码元称为监督码元。它们不受

4、用户的控制，最终也不送给接收用户，只是系统在传输过程中为了减少传输差错而采用的一种处理过程。由于监督码元的加入，信道传输速率就要高于原始信息序列速率。由此可见，通过抗干扰编码来提高传输的可靠性，是以牺牲传输的有效性（速率）为代价换取的。6第二节 检错和纠错的基本概念1、检错和纠错的原理、检错和纠错的原理Shannon的信道编码定理指出：对于一个给定的有干扰信道，如信道容量为C，只要发送端以低于C的速率R发送信息（R为编码器输入的二进制码元速率），则一定存在一种编码方法，使编码错误概率随码长的增加按指数下降到任意小的值。Shannon的这一定理为通信的差错控制奠定了理论基础。具体来说，码的检错和

5、纠错能力是用信息量的冗余度来换取的。例如：要传送A和B两个消息1、用“0”码代表A，用“1”码表示B。这种情况下，若传输中产生错码，即“0”错成“l”，或“1”误为“0”，接收端都无从发现，因此，这种编码没有检错和纠错能力。2、分别在“0”和“1”后面附加一个“0”和“1”，变为“00”和“11”，分别表示消息A和B。这时，在传输“00”和“11”时，如果发生一位错码，则变成“01”或“10”，译码器将可判决为有错，7因为没有规定使用“01”或“10”码组。这表明附加一位码（称为监督码）以后码组具有了检出1位错码的能力。但译码器不能判决哪位是错码，所以没有纠错能力。“01”和“10称为禁 用

6、码 组 ， 而 “ 0 0 ” 和 “ 1 1 ” 称 为 许 用 码 组 。3、在信息码之后附加两位监督码，即用“000”代表消息A，“111”表示消息B，“000”和“111”为许用码组，余下的6组均为禁用码组。收端可以判决传输有错，还可以根据“大数”法则来纠正一个错误，即3位码组中如有2个和3个“0”码判为“000”码组（消息A），如有2个和3个“1”码判为“111”码（消息B），所以，此时还可以纠正一位错码。如果在传输中产生两位错码，也将变为上述的禁用码组，译码器仍可判为有错。这说明本例中的码可以检出两位和两位以下的错码以及纠正一位错码的能力。可见，纠错编码之所以具有检错和纠错能力，是

7、因为在信息码之外附加了监督码。82、码距与检错/纠错能力码重：码组中非零码元的数目； 例如“010”码组的码重为1，“011”码组的码重为2。码距：把两个码组中对应码位上具有不同二进制码元的位数。汉明（Hamming）距离：在一种编码中，任意两个许用码组间的距离的最小值（即码组集合中任意两元素间的最小距离）。 表示为 d0。9码距的几何意义10（1）定理1：为了检测 e 个错码，则要求最小码距 d0e+1 最小码距与编码检错/纠错能力的关系11(2)定理2：为了纠正 t 个错码，要求最小码距 d02t+112(3)定理3：为了纠正 t 个错码，同时检测 e 个错码，要求最小码距 d0t+e+1

8、 (e t)能纠正t个错码、同时能检测e个错码的含义：是指当错码不超过t个时错码能自动予以纠正，而当错码超过t个时，则不可能纠正错误，但仍可检测e个错码。即混合检错纠错的控制方式。13举例：举例： d0=5 检错个数： 纠错个数： 纠错同时检错： 143、差错控制编码的效用分析设在随机信道中发送“O”时的错误概率和发送“1”时的相等，均为 P，且 P1，则在码长为n的码组中恰好发生r个错误的概率为： 当码长 n=7、P=10-3 时，有：rrnrrnnPrnrnPPCrP)!( !)1 ()(371077) 1 (PP527101 . 221)2(PP837105 . 335)3(PP15采用

9、差错控制编码后，即使只能纠正（或检测）这种码组中12个错误，也可以使误码率下降几个数量级，这表明，即使是简单的差错控制编码也具有较大的实用价值。在突发信道中传输，由于错码是成串集中出现的，所以上述只能纠正码组中12个错码的编码，其效用就不像在随机信道中那样明显了，需要采用更为有效的纠错编码：如交织编码等。164、编码效率编码效率：是指一个码组中信息位所占的比重。其中k为信息位长度；n为编码组码元的总数（编码后码组长度）；r为监督码元的数目（监督位长度）。显然，R越大编码效率越高，它是衡量码性能的一个重要参数。对于一个好的编码方案，不但希望它的抗干扰能力高，即检错纠错能力强，而且还希望它的编码效

10、率高，但两方面的要求是矛盾的，在设计中要全面考虑。nkR 175、检错和纠错分类（1）按码组的功能：检错码、纠错码；（2）按监督码与信息码元之间的关系：线性码和非线性码。（3）按对信息码元处理方法不同：分组码和卷积码。 分组码：是将k个信息码元划分为一组，然后由这k个码元按照一定的规则产生r个监督码元，从而组成长度为n=k+r的码组。在分组码中，监督码元仅监督本码组中的信息码元。分组码一般用符号 (n,k)表示。18卷积码：每组的监督码元不但与本码组的信息码元有关，而且还与前面若干组信息码元有关，即不是分组监督，而是每个监督码元对它的前面若干组码元都实行监督，前后相连，因此有时也称为连环码。（

11、4）按照信息码元在编码后是否保持原来的形式不变，可划分为系统码和非系统码。系统码中编码后的信息码元保持原样不变，而非系统码中信息码元则改变了原来的信号形式。系统码的性能大体上与非系统码的相同，但是在某些卷积码中非系统码的性能优于系统码，由于非系统码中的信息位已经改变了原有的信号形式，这对观察和译码都带来麻烦，因此很少应用，而系统码的编码和译码相对比较简单些，所以得到广泛应用。（5）按纠正差错的类型：纠正随机错码、纠正突发错码。（6）按照每个码元取值：二进制码、多进制码。19第三节 几种常用的简单差错控制编码1、奇偶校验码在计算机数据传输中得到广泛应用。规则：发送端将所要传输的数据码元分组，在每

12、组数据后面附加一位监督位，使得该码组连同监督位在内的“1”的个数为偶数（称为偶校验）或奇数（称为奇校验）。接收端按同样规律检查。最小码距：dmin= 2。只能发现单个或奇数个错误，而不能检测出偶数个错误，也不能纠错。设码组长度为n，表示为（an-1an-2.a1a0），其中前n-l位为信息码元，第n位为监督位，则：10121 aaaann00121 aaaann202、水平奇偶校验码 将经过奇偶监督编码的码元序列排成矩阵，每行为一组奇偶监督码，但发送时则按列的顺序传输，接收端仍将码元排列成发送时的矩阵形式，然后按行进行奇偶校验。由于行按进行奇偶校验，因此称为水平奇偶校验码。 采用这种方法可以发

13、现某一行上所有奇数个错误以及所有长度不大于方阵中行数的突发错误。信息码元监督码元1110011000111010011010100001110110001000010011001110111213、水平垂直奇偶校验码 水平垂直奇偶校验码，是将水平奇偶校验码推广到二维奇偶校验码，又称行列校验码和方阵码。 方法：是对水平校验方阵中的每一列再进行奇偶校验。 这种码比水平奇偶校验码有更强的检错能力，它能发现某行或某列上的奇数个错误和长度不大于行数（或列数）的突发错误；还有可能检测出偶数个错码，因为如果每行的监督位不能在本行检出偶数个错误时，则在列的方向上有可能检出；还能纠正一些错码。信息码元监督码元1

14、110011000111010011010100001110110001000010011001110111监督码元01101100011224、恒比码恒比码：每个码组中“1”和“0”数目的比例是恒定的。由于恒比码各码组中的“1”（或“0”）的个数是相同，因而也称等重码。我国电传机传输汉字电码的通信中广泛采用的五单位数字保护电码，是一种五中取三的恒比码。恒比码的主要优点是简单，适于用来传输电传机或其他键盘设备产生的字母和符号，但对于信源来的二进随机数字序列，恒比码就不宜使用了。表 63 我国五单位保护电码表和对应的国际电码阿拉伯数字保护电码国际电码阿拉伯数字保护电码国际电码1010111110

15、161010110101211001110017111001110031011010000801110011004110100101091001100011500111000010011010110123第四节 汉明码汉明码是1950年由美国贝尔实验室汉明提出来的，是第一个设计用来纠正错误的线性分组码，汉明码及其变型已广泛应用于数字通信和数据存储系统中作为差错控制码。在前面讨论奇偶校验时，如按偶校验作为监督方程，而在接收端译码时，实际上是计算：若S = 0，就认为无错；若S = l，则认为有错。称上式为监督方程，S为校正子（校验子），又称伴随式。由于简单的奇偶监督只有一位监督码元，一个监督方程

16、，S只有1和0两种取值，因此只能表示有错和无错两种状态。0121aaaaSnn 24若有r位监督码元，就可构成r个监督方程，计算得到的校正子有r位，可用来指示 2r-1 种误码图样。当只有一位误码时，就可指出 2r-1 个错码位置。一般来说，若码长为n，信息位为k，则监督位为r=n-k。如要求用r个监督位构造出r个监督方程能纠正一位或一位以上错误的线性码，则必需有：2r-1 = n25构造一种(n,k)汉明码 设分组码中信息位k=4，又假设该码能纠正一位误码，这时d03，并要求监督码元位数r3。若取r=3，则n=k+r=7。 用a6a5a4a3a2a1a0表示这7个码元，其中a6a5a4a3表

17、示信息码元， 用S1、S2、S3表示由3个监督方程计算得到的3个校正子。 假设3个校正子构成的码组S1S2S3与错码位置的对应关系：1S2S3S错码位置1S2S3S错码位置0 0 10a1 0 14a0 1 01a1 1 05a1 0 02a1 1 16a0 1 13a0 0 0无错1、(n,k)汉明码的编码/译码26从表的规定可知，当发生一个错码，其位置在a2、a4、a5或a6时，校正子S1为1，否则为0。这表明 a2、a4、a5和a6四个码元构成偶校验关系，即：在发送端编码时， a6、a5、a4、a3为信息码元，由传输的信息决定。而监督码元a2、a1、a0的取值应根据信息位按监督方程来决定

18、，即使上述三个方程中的S1、S2、S3均为0时，表示编码组中无错码，于是有下列方程组；24561aaaaS13562aaaaS03463aaaaS000034635624561aaaaaaaaaaaa27（7,4）编码：已知信息位后，就可直接由上式计算出监督位。346035645621aaaaaaaaaaaa28（7,4）译码 （1）接收端把接收信息按下列方程计算得到校正子S1S2S3： （2）由校正子S1S2S3：查表判决。上述（7，4）汉明码的最小码距 d0 = 3，因此它能纠正一个误码或检测两个误码。24561aaaaS13562aaaaS03463aaaaS29总结：构造总结：构造(n

19、,k)(n,k)汉明码的方法汉明码的方法 根据k确定r，得到n=k+r； 将k位信息码、r位监督码排成n位一排， 监督码位于2i-1（i =1,r-1）位 用除去零的r位二进制数表示上述n位一排的k位信息码、r位监督码。 得到r个校验方程，从而得到r位监督码的表达式。30总结：构造(n,k)汉明码的方法（续）以上述例子为例：1、信息位k=4，监督位r=3，则n=k+r=7。用a6a5a4a3a2a1a0表示这7个码元，其中a6a5a4a3表示信息码元。2、将a6a5a4a3a2a1a0排成一排，得到 a6 a5 a4 a2 a3 a1 a03、 a6 a5 a4 a2 a3 a1 a01 1

20、1 1 0 0 01 1 0 0 1 1 01 0 1 0 1 0 14、 得到346035645621aaaaaaaaaaaa31(15,11)汉明码的编码电路32(15,11)汉明码的译码电路332、汉明码的编码效率编码效率为：对（7，4）码r = 3，R = 57。与码长相同的能纠正一位错码的其他分组码相比，汉明码的效率最高，且实现简单。因此，至今在码组中纠正一个错误的场合中还广泛地使用。通常把码长 n=2r-1 的线性分组码称为汉明码，即： （ 2r-1 ， 2r-1 -r）121rrnrnnkR34第五节 线性分组码线性分组码：是指分组码中信息码元和监督码元是用线性方程联系起来的一种

21、差错控制码。1、校验矩阵（7,4）汉明码的监督方程010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa000034635624561aaaaaaaaaaaa35改写为矩阵的形式：）模2(0001001101010101100101110123456aaaaaaa36H为线性码的校验矩阵。只要校验矩阵H给定，编码时监督码元和信息码元的关系就完全确定了。线性码的主要性质也是由矩阵H的结构决定的。H的行数就是监督方程的个数，即监督码元的位数r，而H的列数就是码长n，这样H为r*n阶矩阵，矩阵中元素“ l”表示相应码元之间

22、存在着偶校验关系，由此各监督码元是共同对整个码组进行校验，称为一致校验。00TTTHAAH或：100110101010110010111H0123456aaaaaaaA 0000 37P为r*k阶矩阵，Ir为r*r阶单位方阵。通常将具有PIr形式的H矩阵称为典型形式的校验矩阵。由线性代数理论得知，H矩阵的各行应该是线性无关的，否则将得不到r个线性无关的校验方程，从而也得不到r个独立的校验码位。由于单位方阵Ir的各行是线性无关的，因此，矩阵若能写成典型矩阵PIr形式，则它的各行一定是线性无关的。rIPH100010001110110110111382、生成矩阵345601211011011011

23、1aaaaaaaTPaaaa3456TPQ 346035645621aaaaaaaaaaaa信息位给定后，用信息位的行矩阵乘矩阵Q就能产生出校验位。1101010111113456012aaaaaaaQaaaa345639可以在矩阵Q的左边加上一个k*k阶单位方阵，形成一个新的矩阵G。G为生成矩阵，因为由它可以产生整个码组A。表明，如果找到了码的生成矩阵G，则编码方法就完全确定。G矩阵亦具有IkQ的形式，故称为典型生成矩阵。1101010111111000010000100001QIGkGaaaaA3456403、H与G的关系生成矩阵G的各行也必定是线性无关的，每行都是一个许用码组，k行许用码组经过运算可以生成 2k 个不同的许用码组，而由它所产生的分组码必定是系统码。QIGkrPIH TPQ 414、校正子和检错一般发送码组A为一个n列的行矩阵，矩阵中n个元素就是码组中的n个码元。