1、1通信原理第第8章差错控制编码章差错控制编码 2第8章差错控制编码l8.1 概述概述 差错控制编码即纠错编码，或信道编码。n信道分类：从差错控制角度看u随机信道：错码的出现是随机的 u突发信道：错码是成串集中出现的u混合信道：既存在随机错码又存在突发错码 n差错控制技术的种类u 检错重发u前向纠错 u反馈校验u检错删除 3第8章差错控制编码n差错控制编码：常称为纠错编码纠错编码u监督码元：监督码元：上述4种技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。 u不同的编码方法，有不同的检错检错或纠错纠错能力。u多余度多余度：就是指
2、增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。u编码效率编码效率(简称码率码率) ：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。u冗余度：冗余度：监督码元数(n-k) 和信息码元数 k 之比。u理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。4第8章差错控制编码p分组码的码重和码距码重：把码组中“1”的个数目称为码组的重量，简称码重码重。码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距码距。码距又称汉明距离汉明距离。例如，“000”晴，“011”云，“101”阴，“110”雨，4个码
3、组之间，任意两个的距离均为2。最小码距：把某种编码中各个码组之间距离的最小值称为最小码距最小码距(d0)。例如，上面的编码的最小码距d0 = 2。5第8章差错控制编码u码距和检纠错能力的关系p一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力p为检出e个错码，要求最小码距 d0 e + 1p为纠正t个错码，要求d02t+1p为纠正t个错码，同时检测e个错码，要求最小码距)(10teted6第8章差错控制编码l8.2 线性分组码线性分组码n基本概念u代数码代数码：建立在代数学基础上的编码。u线性码线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着
4、的。u线性分组码线性分组码：按照一组线性方程构成的分组码 。现以汉明码为例引入线性分组码的一般原理。7第8章差错控制编码n汉明码汉明码能够纠正1位错码且编码效率较高的一种线性分组码u汉明码的构造原理。p在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：在接收端解码时，实际上就是在计算若S = 0，就认为无错码；若S = 1，就认为有错码。现将上式称为监督关系式监督关系式，S称为校正子校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。 0021aaann021aaaSnn8第8章差错控制编码p若监督位增加一位，即变成两位
5、，则能增加一个类似的监督关系式。由于两个校正子的可能值有4种组合： 00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r个监督关系式能指示1位错码的(2r 1)个可能位置。p一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求下面通过一个例子来说明如何具体构造这些监督关系式。1212rknrr或9第8章差错控制编码p例：设分组码分组码(n, k)中k = 4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r = 3，则n
6、= k + r = 7。我们用a6 a5 a0表示这7个码元，用S1、S2和S3表示3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：S1 S2 S3错码位置S1 S2 S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码10第8章差错控制编码由表中规定可见，仅当一位错码的位置在a2 、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2 、a4、a5和a6四个码元构成偶数监督关系：同理， a1、a3、a5和a6构成偶数监督关系：以及a0、a3、a4 和a6构成偶数监督关系24561aaaaS13562
7、aaaaS03463aaaaS11第8章差错控制编码在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：上式经过移项运算，解出监督位给定信息位后，可以直接按上式算出监督位， 结果见下表：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa12第8章差错控制编码信息位a6 a5 a4 a3监督位a2 a1 a0信息位a6 a5 a4 a3监督位a2 a1 a000000001000111
8、0001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111113第8章差错控制编码接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。 p按照上述方法构造的码称为汉明码。表中所列的(7, 4)汉明码的最小码距d0 = 3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n = (n
9、 - r) /n =1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。 14第8章差错控制编码n线性分组码的一般原理u线性分组码的构造pH矩阵上面(7, 4)汉明码的例子有现在将上面它改写为上式中已经将“”简写成“+”。 000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa15第8章差错控制编码上式可以表示成如下矩阵形式：上式还可以简记为H AT = 0T 或A HT = 0010011010010101100010111012345601
10、234560123456aaaaaaaaaaaaaaaaaaaaa）（模20001011001110101011101000123456aaaaaaa16第8章差错控制编码H AT = 0T 或A HT = 0式中 A = a6 a5 a4 a3 a2 a1 a00 = 000右上标“T”表示将矩阵转置。例如，HT是H的转置，即HT的第一行为H的第一列，HT的第二行为H的第二列等等。将H称为监督矩阵监督矩阵。 只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。 101100111010101110100H17第8章差错控制编码H矩阵的性质： 1) H的行数就是监督关系式的数目，它等于
11、监督位的数目r。H的每行中“1”的位置表示相应码元之间存在的监督关系。例如，H的第一行1110100表示监督位a2是由a6 a5 a4之和决定的。H矩阵可以分成两部分，例如 式中，P为r k阶矩阵，Ir为r r阶单位方阵。我们将具有P Ir形式的H矩阵称为典型阵典型阵。rPIH00110110101101100111018第8章差错控制编码2) 由代数理论可知，H矩阵的各行应该是线性无关的，否则将得不到 r个线性无关的监督关系式，从而也得不到 r个独立的监督位。若一矩阵能写成典型阵形式P Ir，则其各行一定是线性无关的。因为容易验证Ir的各行是线性无关的，故P Ir的各行也是线性无关的。pG矩
12、阵： 上面汉明码例子中的监督位公式为也可以改写成矩阵形式：346035614562aaaaaaaaaaaa3456012101111011110aaaaaaa19第8章差错控制编码或者写成式中，Q为一个k r阶矩阵，它为P的转置，即 Q = PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。3456012101111011110aaaaaaaQ34563456012011101110111aaaaaaaaaaa20第8章差错控制编码我们将Q的左边加上1个k k阶单位方阵，就构成1个矩阵G G称为生成矩阵生成矩阵，因为由它可以产生整个码组，即有或者因此，如果找到了码的生成矩
13、阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码称为系统码系统码。 0110001101001011001001111000QGkI I G34560123456aaaaaaaaaaaGA3456aaaa21第8章差错控制编码G矩阵的性质：1) G矩阵的各行是线性无关的。因为由上式可以看出，任一码组A都是G的各行的线性组合。G共有k行，若它们线性无关，则可以组合出2k种不同的码组A，它恰是有k位信息位的全部码组。若G的各行有线性相关的，则不可能由G生成2k种不同的码组了。2) 实
14、际上，G的各行本身就是一个码组。因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。22第8章差错控制编码p错码矩阵和错误图样 一般说来，A为一个n列的行矩阵。此矩阵的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。若设接收码组为一n列的行矩阵B，即则发送码组和接收码组之差为B A = E (模2)它就是传输中产生的错码错码行矩阵矩阵 式中0121bbbbnnB0121eeeennEiiiiiababe当当, 1, 023第8章差错控制编码因此，若ei = 0，表示该接收码元无错；若ei =
15、1，则表示该接收码元有错。 B A = E 可以改写成 B = A + E例如，若发送码组A = 1000111，错码矩阵E = 0000100，则接收码组B = 1000011。错码矩阵有时也称为错误图样错误图样。24第8章差错控制编码p校正子S当接收码组有错时，E 0，将B当作A代入公式(A H T = 0)后，该式不一定成立。在错码较多，已超过这种编码的检错能力时，B变为另一许用码组，则该式仍能成立。这样的错码是不可检测的。在未超过检错能力时，上式不成立，即其右端不等于0。假设这时该式的右端为S，即B H T = S将B = A + E代入上式，可得S = (A + E) H T = A
16、 H T + E H T由于A HT = 0，所以S = E H T式中S称为校正子。它能用来指示错码的位置。S和错码E之间有确定的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。25第8章差错控制编码u线性分组码的性质p封闭性：封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。这就是说，若A1和A2是一种线性码中的两个许用码组，则(A1+A2)仍为其中的一个码组。这一性质的证明很简单。若A1和A2是两个码组，则有A1 HT = 0,A2 HT = 0将上两式相加，得出A1 HT + A2 HT = (A1 + A2) HT = 0所以(A1 + A2)也是一个码组
17、。由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1 + A2)的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。26第8章差错控制编码l8.3 循环码循环码n8.3.1 循环码原理u循环性循环性：循环性是指任一码组循环一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。在下表中给出一种(7, 3)循环码的全部码组。例如，表中的第2码组向右移一位即得到第5码组；第6码组向右移一位即得到第3码组。 码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0
18、100000005100101120010111610111003010111071100101401110018111001027第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. 码多项式p码组的多项式表示法把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成例如，上表中的任意一个码组可以表示为其中第7个码组可以表示为这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中
19、a6、a5、a2和a0为“1”，其他均为0。因此我们并不关心x的取值。 012211)(axaxaxaxTnnnn012233445566)(axaxaxaxaxaxaxT11010011)(25623456xxxxxxxxxxT29第8章差错控制编码p 码多项式的按模运算在整数运算中，有模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,30第8章差
20、错控制编码在码多项式运算中也有类似的按模运算。若一任意多项式F(x)被一 n 次多项式N (x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为这时，码多项式系数仍按模2 运算，即系数只取 0 和1。例如，x3被(x3 + 1)除，得到余项1。所以有同理因为)()()()(xRxQxNxF）（模)()()(xNxRxF）（模)1(133xx）（模) 1(113224xxxxx xx3 + 1 x4 +x2 + 1 x4 + x x2 +x +1应当注意，由于在模2运算中，用加法代替了减法，故余项不是x2 x + 1，而是x2 + x + 1。31第8章差错控制编码2. 循环码的生成
21、矩阵Gp由公式可知，有了生成矩阵G，就可以由k个信息位得出整个码组，而且生成矩阵G的每一行都是一个码组。例如，在此式中，若a6a5a4a3 = 1000，则码组A就等于G的第一行；若a6a5a4a3 = 0100，则码组A就等于G的第二行；等等。由于G是k行n列的矩阵，因此若能找到k个已知码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的，否则给定的信息位与编出的码组就不是一一对应的。p在循环码中，一个(n, k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关
22、的。因此它们可以用来构成此循环码的生成矩阵G。GA3456aaaa32第8章差错控制编码p因此，循环码的生成矩阵G可以写成 p例：在上表所给出的(7, 3)循环码中，n = 7, k = 3, n k = 4。由此表可见，唯一的一个(n k) = 4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式（即生成多项式生成多项式）g(x) = x4 + x2 + x + 1。将此g(x)代入上式，得到或)()()()()(21xgxxgxgxxgxxkkG)()()()(2xgxxgxgxxG001011101011101011100)(xG33第8章差错控制编码由于上式不符合G =
23、 IkQ的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。我们可以写出此循环码组，即上式表明，所有码多项式T(x)都可被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。需要说明一点，两个矩阵相乘的结果应该仍是一个矩阵。上式中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是T(x)。为了简洁，式中直接将乘积写为此元素。)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG34第8章差错控制编码3. 如何寻找任一(n, k)循环码的生成多项式 由上式可知，任一
24、循环码多项式T(x)都是g(x)的倍式，故它可以写成T(x) = h(x)g(x)而生成多项式g(x)本身也是一个码组，即有 T (x) = g(x)由于码组T (x)是一个(n k)次多项式，故xk T (x)是一个n次多项式。由下式可知，xk T (x)在模(xn + 1)运算下也是一个码组，故可以写成）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx35第8章差错控制编码上式左端分子和分母都是n次多项式，故商式Q(x) = 1。因此，上式可以化成将T(x)和T(x)表示式代入上式，经过化简后得到上式表明，生成多项式g(x)应该是(xn + 1)的一个因子。这一
25、结论为我们寻找循环码的生成多项式指出了一条道路，即循环码的生成多项式应该是(xn +1)的一个(n k)次因式。例如，(x7 + 1)可以分解为为了求(7, 3)循环码的生成多项式g(x)，需要从上式中找到一个(n k) = 4次的因子。不难看出，这样的因子有两个，即1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx36第8章差错控制编码以上两式都可作为生成多项式。不过，选用的生成多项式不同，产生出的循环码码组也不同。1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx37第8章差错控
26、制编码n8.3.2 循环码的编解码方法1. 循环码的编码方法p编码原则在编码时，首先要根据给定的(n, k)值选定生成多项式g(x)，即从(xn + 1)的因子中选一个(n - k)次多项式作为g(x)。由于所有码多项式T(x)都可以被g(x)整除。根据这条原则，就可以对给定的信息位进行编码：设m(x)为信息码多项式，其次数小于k。用xn - k乘m(x)，得到的xn-k m(x)的次数必定小于n。用g(x)除xn - k m(x)，得到余式r(x)，r(x)的次数必定小于g(x)的次数，即小于(n k)。将此余式r(x)加于信息位之后作为监督位，即将r(x)和xn - k m(x)相加，得到
27、的多项式必定是一个码多项式。因为它必须能被g(x)整除，且商的次数不大于(k 1)。38第11章差错控制编码p编码步骤：用xn - k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。例如，信息码为110，它相当于m(x) = x2 + x。当n k = 7 3 = 4时，xn - k m(x) = x4 (x2 + x) = x6 + x5，它相当于1100000。用g(x)除xn - k m(x)，得到商Q(x)和余式r(x)，即例如，若选定g(x) = x4 + x2 + x + 1，则 上式相当于)()()()()(xgxrxQxgxmxkn11) 1(1)()(2422
28、2456xxxxxxxxxxxxgxmxkn1011110111110111110000039第11章差错控制编码编出的码组T(x)为T(x) = xn - k m(x) + r(x) 在上例中，T(x) = 1100000 + 101 = 1100101，它就是上表中的第7码组。40第8章差错控制编码2. 循环码的解码方法p解码要求：检错和纠错。p检错解码原理：由于任意一个码组多项式T(x)都应该能被生成多项式g(x)整除，所以在接收端可以将接收码组R(x)用原生成多项式g(x)去除。当传输中未发生错误时，接收码组与发送码组相同，即R(x) = T(x)，故接收码组R(x)必定能被g(x)整
29、除；若码组在传输中发生错误，则R(x) T(x)，R(x)被g(x)除时可能除不尽而有余项，即有因此，就以余项是否为零来判别接收码组中有无错码。需要指出，有错码的接收码组也有可能被g(x)整除。这时的错码就不能检出了。这种错误称为不可检错误。不可检错误中的误码数必定超过了这种编码的检错能力。)(/ )()()(/ )(xgxrxQxgxR41第8章差错控制编码p纠错解码原理：为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。因为只有存在上述一一对应的关系时，才可能从上述余式唯一地决定错误图样，从而纠正错码。因此，原则上纠错可按下述步骤进行：用生成多项式g(x)除接收码组R
30、(x)，得出余式r(x)。按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)；例如，通过计算校正子S和查表，就可以确定错码的位置。从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。p通常，一种编码可以有几种纠错解码方法，上述解码方法称为捕错解码法。 u目前多采用软件运算实现上述编解码运算。42第8章差错控制编码l8.4 卷积码卷积码n非分组码概念：u卷积码是一种非分组码。通常它更适用于前向纠错，因为对于许多实际情况它的性能优于分组码，而且运算较简单。u卷积码在编码时虽然也是把k个比特的信息段编成n个比特的码组，但是监督码元不仅和当前的k比特信息段有关，而且还同前面m
31、 = (N 1)个信息段有关。所以一个码组中的监督码元监督着N个信息段。通常将N称为编码约束度，并将nN称为编码约束长度。一般说来，对于卷积码，k 和 n 的值是比较小的整数。我们将卷积码记作(n, k, N)。码率则仍定义为k / n。 43第8章差错控制编码n8.3.1 卷积码的基本原理u编码器原理方框图编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周44第8章差错控制编码u例： (n, k, N) = (3, 1, 3)卷积码编码器p方框图p设输入信息比特序列是bi-2 bi-1 bi bi+1，则当输入bi时，此编码器输出3比特ci di ei，输入和输出的关系如下：bi-2bi输入bibi-1编码输出dicieiM2M3M121 2iiiiiiiiibbbebbdbc45ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt输入输出第8章差错控制编码在下图中用虚线示出了信息位bi的监督位和各信息位之间的约束关系。这里的编码约束长度nN等于9。 46第8章差错控制编码n8.4.2 卷积码的代数表述上式表示卷积码也是一种线性码。一个线性码完全由一个监督矩阵H或生成矩阵G所确定。 卷积码的几何表述47第8章差错控制编码本章考点本章考点
