《大连理工通信原理幻灯片-第8章》由会员分享，可在线阅读，更多相关《大连理工通信原理幻灯片-第8章（47页珍藏版）》请在金锄头文库上搜索。
1、1,通信原理,第8章差错控制编码,2,第8章差错控制编码,8.1 概述 差错控制编码即纠错编码，或信道编码。 信道分类：从差错控制角度看 随机信道：错码的出现是随机的 突发信道：错码是成串集中出现的 混合信道：既存在随机错码又存在突发错码 差错控制技术的种类 检错重发 前向纠错 反馈校验 检错删除,3,第8章差错控制编码,差错控制编码：常称为纠错编码 监督码元：上述4种技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。 不同的编码方法，有不同的检错或纠错能力。 多余度：就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码
2、元就添加一个监督码元，则这种编码的多余度为1/3。 编码效率(简称码率) ：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。 冗余度：监督码元数(n-k) 和信息码元数 k 之比。 理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。,4,第8章差错控制编码,分组码的码重和码距 码重：把码组中“1”的个数目称为码组的重量，简称码重。 码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。 例如，“000”晴，“011”云，“101”阴，“110”雨，4个码组之间，任意两个的距离均为2。 最小码距：把某种编码中各个码组之间距离的最小值称
3、为最小码距(d0)。例如，上面的编码的最小码距d0 = 2。,5,第8章差错控制编码,码距和检纠错能力的关系 一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力 为检出e个错码，要求最小码距 d0 e + 1 为纠正t个错码，要求d02t+1 为纠正t个错码，同时检测e个错码，要求最小码距,6,第8章差错控制编码,8.2 线性分组码 基本概念 代数码：建立在代数学基础上的编码。 线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。 线性分组码：按照一组线性方程构成的分组码 。 现以汉明码为例引入线性分组码的一般原理。,7,第8章差错控制编码,
4、汉明码 能够纠正1位错码且编码效率较高的一种线性分组码 汉明码的构造原理。 在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式： 在接收端解码时，实际上就是在计算 若S = 0，就认为无错码；若S = 1，就认为有错码。现将上式称为监督关系式，S称为校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。,8,第8章差错控制编码,若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有4种组合： 00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示
5、一个错码的3种不同位置。同理，r个监督关系式能指示1位错码的(2r 1)个可能位置。 一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求 下面通过一个例子来说明如何具体构造这些监督关系式。,9,第8章差错控制编码,例：设分组码(n, k)中k = 4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r = 3，则n = k + r = 7。我们用a6 a5 a0表示这7个码元，用S1、S2和S3表示3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：,10,第8章差错控
6、制编码,由表中规定可见，仅当一位错码的位置在a2 、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2 、a4、a5和a6四个码元构成偶数监督关系： 同理， a1、a3、a5和a6构成偶数监督关系： 以及a0、a3、a4 和a6构成偶数监督关系,11,第8章差错控制编码,在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）： 上式经过移项运算，解出监督位 给定信息位后，可以直接按上式算出监督位， 结果见下表：,12,第8章
7、差错控制编码,13,第8章差错控制编码,接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。 按照上述方法构造的码称为汉明码。表中所列的(7, 4)汉明码的最小码距d0 = 3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n = (n - r) /n =1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。,14,第8章差错控制编码,线性分组码的一般原理 线性分组码的构造 H矩阵 上面(7,
8、4)汉明码的例子有 现在将上面它改写为 上式中已经将“”简写成“+”。,15,第8章差错控制编码,上式可以表示成如下矩阵形式： 上式还可以简记为 H AT = 0T 或 A HT = 0,16,第8章差错控制编码,H AT = 0T 或 A HT = 0 式中 A = a6 a5 a4 a3 a2 a1 a0 0 = 000 右上标“T”表示将矩阵转置。例如，HT是H的转置，即HT的第一行为H的第一列，HT的第二行为H的第二列等等。 将H称为监督矩阵。 只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。,17,第8章差错控制编码,H矩阵的性质： 1) H的行数就是监督关系式的数目，它
9、等于监督位的数目r。H的每行中“1”的位置表示相应码元之间存在的监督关系。例如，H的第一行1110100表示监督位a2是由a6 a5 a4之和决定的。H矩阵可以分成两部分，例如 式中，P为r k阶矩阵，Ir为r r阶单位方阵。我们将具有P Ir形式的H矩阵称为典型阵。,18,第8章差错控制编码,2) 由代数理论可知，H矩阵的各行应该是线性无关的，否则将得不到 r个线性无关的监督关系式，从而也得不到 r个独立的监督位。若一矩阵能写成典型阵形式P Ir，则其各行一定是线性无关的。因为容易验证Ir的各行是线性无关的，故P Ir的各行也是线性无关的。 G矩阵： 上面汉明码例子中的监督位公式为 也可以改
10、写成矩阵形式：,19,第8章差错控制编码,或者写成 式中，Q为一个k r阶矩阵，它为P的转置，即 Q = PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。,20,第8章差错控制编码,我们将Q的左边加上1个k k阶单位方阵，就构成1个矩阵G G称为生成矩阵，因为由它可以产生整个码组，即有 或者 因此，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码称为系统码。,21,第8章差错控制编码,G矩阵的性质： 1) G矩阵的各行是线性无关的。因为由上式可以看
11、出，任一码组A都是G的各行的线性组合。G共有k行，若它们线性无关，则可以组合出2k种不同的码组A，它恰是有k位信息位的全部码组。若G的各行有线性相关的，则不可能由G生成2k种不同的码组了。 2) 实际上，G的各行本身就是一个码组。因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。,22,第8章差错控制编码,错码矩阵和错误图样 一般说来，A为一个n列的行矩阵。此矩阵的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。 若设接收码组为一n列的行矩阵B，即 则发送码组和接收码组之差为 B A = E
12、 (模2) 它就是传输中产生的错码行矩阵 式中,23,第8章差错控制编码,因此，若ei = 0，表示该接收码元无错；若ei = 1，则表示该接收码元有错。 B A = E 可以改写成 B = A + E 例如，若发送码组A = 1000111，错码矩阵E = 0000100，则接收码组B = 1000011。 错码矩阵有时也称为错误图样。,24,第8章差错控制编码,校正子S 当接收码组有错时，E 0，将B当作A代入公式(A H T = 0)后，该式不一定成立。在错码较多，已超过这种编码的检错能力时，B变为另一许用码组，则该式仍能成立。这样的错码是不可检测的。在未超过检错能力时，上式不成立，即其
13、右端不等于0。假设这时该式的右端为S，即 B H T = S 将B = A + E代入上式，可得 S = (A + E) H T = A H T + E H T 由于A HT = 0，所以 S = E H T 式中S称为校正子。它能用来指示错码的位置。 S和错码E之间有确定的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。,25,第8章差错控制编码,线性分组码的性质 封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。 这就是说，若A1和A2是一种线性码中的两个许用码组，则(A1+A2)仍为其中的一个码组。这一性质的证明很简单。若A1和A2是两个码组，则有 A1 HT
14、 = 0, A2 HT = 0 将上两式相加，得出 A1 HT + A2 HT = (A1 + A2) HT = 0 所以(A1 + A2)也是一个码组。 由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1 + A2)的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。,26,第8章差错控制编码,8.3 循环码 8.3.1 循环码原理 循环性：循环性是指任一码组循环一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。在下表中给出一种(7, 3)循环码的全部码组。 例如，表中的第2码组向右移一位
15、即得到第5码组；第6码组向右移一位即得到第3码组。,27,第8章差错控制编码,一般说来，若(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) 也是该编码中的码组。,28,第8章差错控制编码,1. 码多项式 码组的多项式表示法 把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成 例如，上表中的任意一个码组可以表示为 其中第7个码组可以表示为 这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中a6、a5、a2和a0为“1”，其他均为0。因此我们
16、并不关心x的取值。,29,第8章差错控制编码,码多项式的按模运算 在整数运算中，有模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 除得的余数。,30,第8章差错控制编码,在码多项式运算中也有类似的按模运算。 若一任意多项式F(x)被一 n 次多项式N (x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即 则写为 这时，码多项式系数仍按模2 运算，即系数只取 0 和1。例如，x3被(x3 + 1)除，得到余项1。所以有 同理 因为,应当注意，由于在模2运算中，用
