第6章线性分组码

第6章线性分组码第6章线性分组码6.1线性分组码的基本原理6.2线性分组码矩阵表述6.3线性分组码的编码及译码6.4汉明码及其它纠错码第6章线性分组码纠错码的分类：•按功能分：检错码、纠错码•按监督码元与信息码元的关系分：线性码、非线性码•按对信息码元的处理方法分：分组码、卷积码其中分组码又包括循环码和非循环码•按信息码元编码后是否保持原形分为：系统码、非系统码•按纠错类型分：纠正随机错误码、纠正突发错误码、纠正混合错误码、纠正同步错误码等•按码元的取值分：二进制码、多进制码第6章线性分组码•(n，k)线性分组码：把信息序列按一定长度分成若干信息码组，每组由相继的k位信息数字组成；然后，编码器按照预定的线性运算规则(可由线性方程组来规定)把信息码组变换成n(nk)重码字，如图所示。6.1.1基本概念6.1线性分组码的基本原理第6章线性分组码（1）如果(n，k)线性分组码的数域为GF(p)，即每一个码元可能有p种取值，则信源可发出pk种不同的消息组；（2）线性码的校检位与信息位之间呈线性关系；（3）由pk个信息码组编成的码字集合称为(n,k)码许用码字,由pn-pk个除了许用码字之外的码字集合称为禁用码字。注：第6章线性分组码•码矢：一个n重的码字C可以用矢量C=［cn-1cn-2…c1c0］来表示，所以码字又称为码矢。•码率：对(n，k)线性码，用R＝k／n表示码字中信息位所占的比重，叫做编码效率或编码速率，简称码率。它说明了信道利用效率，所以也叫做传信率。注：R是衡量码性能的一个重要参数（1）R越小，冗余度就越大，检错和纠错的能力越强，但也降低了传输信息的实际速率。（2）R越大，码的效率也就越高或传信率越高。第6章线性分组码例如，信息分组长度k＝3，在每一信息组后加上4个监督元，构成(7，3)线性分组码。设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为信息元；c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ci∈GF(2)。监督元按下面方程组计算：0101210122023uucuucuuucuuc（6－１）•监督方程（校验方程）：是线性方程组，它确定了由信息元得到监督元的规则式(6－1)为监督方程或校验方程第6章线性分组码利用监督方程或校验方程。每给出一个3位的信息组，就可编出一个码字，如表6－1所示。表6-1（７，３）分组码编码表消息码字消息码字00000000001001001110001001110110110100110100100111110110100101101110101111110100第6章线性分组码1.汉明（Hamming)重量（码重）：码字中非零码元的数目例如“010”码字的码重为1，“011”码字的码重为2。2.汉明距离（码距）：两个码字之间对应码位上具有不同二元码元的位数。3.最小汉明距离，用dmin表示：在一种编码中，任意两个许用码字间距离的最小值，即码字集合中任意两码字间的最小距离；4.最小汉明重量：在非零码字中，重量最小者称为该码的最小汉明重量。6.1.2码的重量和码的距离第6章线性分组码5.通常用d(C1，C2)表示两个n重C1、C2之间的汉明距离;6.汉明距离的性质(1)对称性：d(C1，C2)＝d(C2，C1)；(2)非负性：d(C1，C2)≥0；(3)满足距离三角不等式：d(C1，C2)≤d(C1，C3)＋d(C3，C2)。第6章线性分组码7.最小距离dmin与码率R是码的两个最主要的参数，dmin表示了码的纠错能力。注：纠错码的基本任务之一就是构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码。8.MDS码：(n，k，d)线性分组码的最小距离dmin≤n－k＋1。若系统码的最小距离dmin＝n－k＋1，则称此码为极大最小距离可分码，简称MDS码。第6章线性分组码1.若一个码组内能检测e个错码，则要求最小码距为dmin≥e＋1注：若一种编码的最小距离为dmin，则它最多能检出dmin-1个错码。6.1.3码的检错及纠错能力第6章线性分组码图6－2码距与检错、纠错能力的关系第6章线性分组码2.若一个码组内能纠正t个错码，则要求最小码距为dmin≥2t＋1(6－3)注：若一种编码的最小码距为dmin，则它最多能纠正（dmin－1）/2个错码。第6章线性分组码3.若在一个码组内能纠正t个错码，同时也能检测e(et)dmin≥e＋t＋1(et)(６-4)注：能纠正t个错码，同时能检测e个错码的含义是：当错码不超过t个时，码组能自动予以纠正；而当错码超过t个时，则不可能纠正错误，但仍可检测e个错码，这正是混合检错、纠错的控制方式。第6章线性分组码4.若一个码组内能纠正t个错误和P个删除，则要求最小码距为12minPtd(6－5)注：删除是指已知错误产生的位置，但不知错误值的大小。第6章线性分组码【例6－1】已知GF(2)中一个码组的全部码字为如果将此码用于检错,能检出几位错码?如果将此码用于纠错,能纠出几位错码?如果将此码同时用于检错和纠错,能检出几位错码?纠出几位错码?000000,001110,010101,011011,100011,101101,110110第6章线性分组码解：由8个码字可得码组的最小汉明距离dmin=3。若检测e个错码，则要求最小码距：dmin≥e＋1，则e≤2，此码最多可以检出2位错码；若纠正t个错码，则要求最小码距：dmin≥2t＋1，则t≤1，此码最多可以纠出1若既能纠正t个错码，同时又能检测e(et)个错码，则要求最小码距：dmin≥e＋t＋1(et)，则e=2，t=0，此码只能检错，不能纠错。第6章线性分组码•线性分组码具有下述性质：(1)两个属于该码组码字的和仍是一个属于该码组的码字。(2)全零码字总是码组中的一个码字。(3)一个线性码组中两个码字之间的最小距离等于任何非零码字的最小重量。注：如果两个码字的和是另外一个码字，该两个码字的差也将仍然是一个合法码字。例如，若C1、C2和C3是码字，且C1+C2=C3，那么有C3-C1=C2。所以，对一个线性分组码，全零码字必为一个合法码字。6.1.4线性分组码的性质第6章线性分组码【例6－2】已知GF(2)中码组C=｛0000,1010,0101,1111｝是一个分组长度n=4的线性分组码。观察码字之间所有十种可能的和：0000+0000=0000,0000+1010=1010,0000+0101=0101,0000+1111=1111,1010+1010=0000,1010+0101=1111,1010+1111=0101,0101+0101=0000,0101+1111=1010,1111+1111=0000它们都在C中，全零码字也在C中。该码组的最小距离为dmin=2。为了验证这个线性码的最小距离，可计算所有码字对（共6对）之间的距离:2)1111,0101(,2)1111,1010(,4)0101,1010(4)1111,0000(,2)0101,0000(,2)1010,0000(dddddd显然这个码组的最小距离为2。第6章线性分组码（1）设S为一个长度为n且分量在GF(p)上的向量集合。S中所有向量的线性组合构成的集合称为S的线性扩张，记为〈S〉。（2）线性扩张是由S生成的GF(pn)的一个子空间。（3）给定GF(pn)的任意子集S，可以得到一个由S生成的线性码C=〈S〉，它恰好包含下列码字：①全零码字;②S中所有的码字;③S中两个或两个以上的字的所有线性组合。•S的线性扩张第6章线性分组码【例6－3】设GF(2)中S=｛1100,0100,0011｝，S的所有可能线性组合为:1100+0100=1000，1100+0011=1111，0100+0011=0111，1100+0100+0011=1011。因此，C=〈S〉={0000，1100，0100，0011，1000，1111，0111，1011}。该码组的最小距离dmin=1。第6章线性分组码在（n，k）线性分组码中，n表示码长，k表示信息位的维数，将n个码字位和k个信息位之间的关系写成矩阵形式,即C＝UG(6－6)6.2线性分组码矩阵表述6.2.1生成矩阵第6章线性分组码式中:];[011uuuUk];[011ncccCG为该线性分组码（n，k）码的生成矩阵，即knkknngggggggggG212222111211（6－7）第6章线性分组码（1）G建立了消息与码矢间的一一对应关系，它起着编码器的变换作用。因此C的每一位数字都是消息数字的线性组合。（2）一个子空间的基底矢量的选择不是惟一的，所以生成矩阵G的选择也不是惟一的。注：第6章线性分组码【例6－4】已知(7，3)线性分组码，设该码的码字为C=［c6c5c4c3c2c1c0］，其中c6、c5、c4为信息元;c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ci∈GF(2)。监督元可按式(6－1)方程组计算。求生成矩阵。解因为信息位分别为u2、u1、u0，则码元为:c6=u2c5=u1c4=u0c3=u2+u0c2=u2+u1+u0c1=u2+u1c0=u1+u0第6章线性分组码又因为C=[c6c5c4c3c2c1co]，U=[u2u1u0]，由C=UG，所以101110011100100111001G第6章线性分组码【例6－5】已知GF(2)中码生成矩阵分别为：0001111010111101011G1011001100100110012G求：G1和G2分别对应的码字空间？第6章线性分组码表6－2用不同的生成矩阵得到的线性码消息用G1得到的（6，3）码用G2得到的（6，3）码000000000000000001111000001101010110101010011011001101011110100101011100110101010011101011110011110110101111100110111000第6章线性分组码在线性分组码（n，k）中，若设CT、0T及HT分别为C、0、H的转置矩阵，则每个码字中r个监督元和信息元之间的关系为HCT＝0T或CHT＝0（6－8）H称为(n,k)线性码的一致监督矩阵，即rnrrnnhhhhhhhhhH212222111211式中：C＝[cn—1cn—2...clc0]。6.2.2监督矩阵第6章线性分组码【例6－6】已知(7，3)线性分组码，设该码的码字为C=［c6c5c4c3c2c1c0］,其中c6、c5、c4为信息元;c3、c2、c1、c0为监督元，每个码元ci∈GF(2)。监督元可按式(6－1)方程组计算。求监督矩阵。c6=u2c5=u1c4=u0解：因为第6章线性分组码则由监督方程得c3＝u2＋u0＝c6＋c4c2＝u2＋u1＋u0＝c6＋c5＋c4c1＝u2＋u1＝c6＋c5c0＝u1＋u0＝c5＋c4得：1000110010001100101110001101H第6章线性分组码1.等价码如果一个线性P元码可由另一个通过下面一种或两种运算得到，则称它们为等价码。该运算为：(1)用非零常量去乘它的分量；(2)对码的位置做置换。6.2.3等价码及系统码第6章线性分组码定理6－1两个k×n矩阵，若一个可以由另一个通过一系列下述变换得到，则它们生成的GF(p)上的(n，k)线性码等价：（1）对行置换；（2）对行乘以一个非零常量；（3）把一行乘以一个常量然后加到另一行上；（4）对列置换；（5）对任意列乘以一个非零常量。第6章线性分组码（1）编码后信息元保持不变的码为系统码。（2）例6－5中G2生成的码，因其前k位与消息完全相同，为系统码，该码的编码器仅需存储k×(n-k)个数字(非系统码要存储k×n个数字)，译码时仅需对