第8章 线性分组码

第8章线性分组码重庆交通大学信息科学与工程学院通信工程系黄大荣本章节教学内容、基本要求、重点与难点1.教学内容：线性分组码的概念。一致监督方程、一致监督矩阵和线性分组码的生成矩阵。线性分组码的最小距离、检错和纠错能力。线性分组码的编码方法与译码。线性分组码的性能分析。汉明码。2.教学基本要求：掌握线性分组码的编码方法和译码方法。了解一致监督方程和一致监督矩阵的求法。理解最小距离与检错和纠错能力的关系。了解汉明码的特点。3.重点与难点：监督矩阵和生成矩阵。线性分组码的最小距离、检错和纠错能力。译码的性能。什么是分组？为什么要分组？分组编码的任务：选择一个k维n重子空间作为码空间确定k维k重信息空间到k维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码的不同映射方法，就构成了分组码的不同。线性分组码的构造方法就是构造子空间的方法，存在三个问题：1）码集C能否构成n*n矢量空间的一个k*n重子空间？2）如何寻找最佳的码空间？3）2k个信息元组以什么算法一一映射到码空间。基本思维线性分组码的编码过程分为两步：把信息序列按一定长度分成若干信息码组，每组由k位组成；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成n重(nk)码字，其中(n－k)个附加码元是由信息码元的线性运算产生的。信息码组长k位，有2k个不同的信息码组，则应该有2k个码字与它们一一对应。概念线性分组码：通过预定的线性运算将长为k位的信息码组变换成n位的码字(nk)。由2k个信息码组所编成的2k个码字集合，称为线性分组码。码矢：一个n重的码字可以用矢量来表示C=(Cn－1,Cn－1,…,C1,C0)所以码字又称为码矢。(n,k)线性码：信息位长为k，码长为n的线性码。编码效率/编码速率/码率/传信率：R=k/n。它说明了信道的利用效率，R是衡量编码性能的一个重要参数。一致监督方程：编码就是给已知信息码组按预定规则添加监督码元，以构成码字。在k个信息码元之后附加r(r=n－k)个监督码元，使每个监督元是其中某些信息元的模2和。例k=3,r=4构成(7,3)线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”监督元可按下面方程组计算一致监督方程和一致监督矩阵4505614562463CCCCCCCCCCCCC一致监督方程/一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。由于一致监督方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。信息码组(101)，即C6=1,C5=0,C4=1由线性方程组得：C3=0,C2=0,C1=1,C0=1即信息码组(101)编出的码字为(1010011)。其它7个码字如表。(7,3)分组码编码表信息组对应码字000000000000100111010100100111011011101010010011101011010011110110100111111101004505614562463CCCCCCCCCCCCC00000000000000000000451562456346CCCCCCCCCCCCC一致监督矩阵：将监督方程写成矩阵形式，得：HCT=0T或CHT=0CT、HT、0T分别表示C、H、0的转置矩阵。1000110010001100101110001101H00000C0000100011001000110010111000110101234560123456CCCCCCCCCCCCCC令系数矩阵H的后四列组成一个(4×4)阶单位子阵，用I4表示，H的其余部分用P表示43437434IPH1000010000100001I110011111101P),(所以推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定000022110222212101212111ChChChChChChChChChrnnrnrnnnnnn令系数矩阵为H，码字行阵列为C一致监督方程和一致监督矩阵矩阵。线性分组码的一致监督为称或则：),(H0HC0CHCH11110211212222111211knCCChhhhhhhhhrTrnnTrTnnrnnnrnrrnnnr一致监督矩阵特性:对H各行实行初等变换，将后面r列化为单位子阵，于是得到下面矩阵(行变换所得方程组与原方程组同解)。监督矩阵H的标准形式：后面r列是一单位子阵的监督矩阵H。H阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的模2和为0。100010001H212222111211rnrrkknrpppppppppH的标准形式还说明了相应的监督元是由哪些信息元决定的。例如(7,3)码的H阵的第一行为(1011000)，说明此码的第一个监督元等于第一个和第三个信息元的模2和，依此类推。H阵的r行代表了r个监督方程，也表示由H所确定的码字有r个监督元。为了得到确定的码，r个监督方程（或H阵的r行）必须是线性独立的，这要求H阵的秩为r。若把H阵化成标准形式，只要检查单位子阵的秩，就能方便地确定H阵本身的秩。线性码的封闭性:线性码的封闭性：线性码任意两个码字之和仍是一个码字。[证明]：若U和V为线性码的任意两个码字，故有HUT=0T，HVT=0T那么H(U+V)T=H(UT+VT)=HUT+HVT=0T即U+V满足监督方程，所以U+V一定是一个码字。一个长为n的二元序列可以看作是GF(2)(二元域)上的n维线性空间中的一点。长为n的所有2n个矢量集合构成了GF(2)上的n维线性空间Vn。把线性码放入线性空间中进行研究，将使许多问题简化而比较容易解决。(n,k)线性码是n维线性空间Vn中的一个k维子空间Vk。线性分组码的生成矩阵线性分组码的生成矩阵:在由(n,k)线性码构成的线性空间Vn的k维子空间中，一定存在k个线性独立的码字：g1,g2,…,gk,。码CI中其它任何码字C都可表示为这k个码字的线性组合，即阶矩阵。是一个是待编码的信息组。写成矩阵形式得其中：nkmmmmmmkimmmmkknkkkkknikkkGmGmgggC1,1,0),2(GFgggC021121021102211G中每一行gi=(gi1,gi2,…,gin)都是一个码字；对每一个信息组m，由矩阵G都可以求得(n,k)线性码对应的码字。生成矩阵：由于矩阵G生成了(n,k)线性码，称矩阵G为(n,k)线性码的生成矩阵。(n,k)线性码的每一个码字都是生成矩阵G的行矢量的线性组合，所以它的2k个码字构成了由G的行张成的n维空间Vn的一个k维子空间Vk。knkknnknkggggggggg21222211121121gggG显然：线性系统分组码:通过行初等变换，将G化为前k列是单位子阵的标准形式knjqmqmqmCkimC,mmmCCCqqqqqqqqqkjjkjkjknikinnkkknnnrkkknkkkknknnk,,2,1,,2,1G),,,(),,,(CQI100010001G02211)(0210211)(21)(22221)(11211得将上式代入线性系统分组码：用标准生成矩阵Gk×n编成的码字，前面k位为信息数字，后面r=n－k位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。当生成矩阵G确定之后，(n,k)线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样解决了。系统码的码字结构信息数字校验数字例:(7,4)线性码的生成矩阵为)1010011(11010000110100111001010100010101GmC)1010(m1101000011010011100101010001G7441714174，则若rTrkSrkkSkrTrkTkrrkrkrkTkrrTkrrkkTrkrrkkTSSrkrSrkkSI)Q(HQIGP)Q()P(Q0Q)P(I)P(QIIPQIHGIPHQIG或所以，生成矩阵与一致监督矩阵的关系:由于生成矩阵G的每一行都是一个码字，所以G的每行都满足Hr×nCTn×1=0Tr×1，则有Hr×nGTn×k=0Tr×k或Gk×nHTn×r=0k×r线性系统码的监督矩阵H和生成矩阵G之间可以直接互换。例:已知(7,4)线性系统码的监督矩阵为(7,3)(7,4)1110100H0111010110100110001010100111G00101100001011可直接写出它的生成矩阵对偶码：一个(n,k)线性码CI，如果以G作监督矩阵，而以H作生成矩阵，可构造另一个(n,n－k)线性码CId，称码CId为原码的对偶码。(7,3)码的监督矩阵H(7,3)是(7,4)码的生成矩阵G(7,4)(7,4)码的监督矩阵H(7,4)是(7,3)码的生成矩阵G(7,3))3,7()4,7(G101110011100100111001100101101011100010111H标准形式)3,7()4,7(H10001100100011001011100011011101000011010011100101010001G标准形式(n,k)线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n(nk)的码字。利用监督矩阵构造(7,3)线性分组码的编码电路：设码字矢量为C=(C6C5C4C3C2C1C0)码的监督矩阵为线性分组码的编码4505614562463)3,7(1000110010001100101110001101CCCCCCCCCCCCCTT得由0HCH根据方程组可直接画出(7,3)码的并行和串行编码电路。m0m1m2C6C5C4C3C2C1C0C0C1C2C3C4C5C6mC(a)并行编码电路（b）串行编码电路(7,3)线性编码电路汉明距离、汉明重量和汉明球汉明距离：在(n,k)线性码中，两个码字U、V之间对应码元位上符号取值不同的个数，称为码字U、V的汉明距离。例：(7,3)码的两个码字U=0011101,V=0100111之间第2、3、4和6位不同。因此，码字U和V的距离为4。线性分组码的一个码字对应于n维线性空间中的一点，码字间的距离即为空间中两对应点的距离。因此，码字间的距离满足一般距离公理：10)(),(niiivudVU线性分组码的最小距离、检错和纠错能力三角不等式③对称性②