纠错码Lecture5-线性分组码(II)

Lecture5

线性分组码(II)2内容修正的线性码扩展码，删余码增广码，增余删信码延长码，Reed-Muller码线性码的重量分布线性码的纠错能力SingletonboundHamming(spherepacking)boundVarshamov-GilbertboundMcEliece-Rodemich-Rumsey-Welchupperbound3修正的线性码纠错码的设计码长通常由矩阵或多项式的代数和组合特性决定线性分组码的设计码长通常不等于理想码长例如：二进制Hamming码的设计码长为2m-1(7,15,31,…)修正方法线性分组码三个参数(n,k,n-k):增大一个参数，降低另一个参数，保持第三个参数不变。共有6种方法4扩展(Expanded)码基本原理：对[n,k,d]线性分组码中的每一个码字，增加一个校验元，满足：

称为全校验位若d为偶数，[n,k,d]码变成了[n+1,k,d]若d为奇数，[n,k,d]码变成了[n+1,k,d+1]校验矩阵5扩展(Expanded)码校验矩阵6扩展(Expanded)码例子：[7,4,3]Hamming码的校验矩阵增加一个全校验位后得到的[8,4,4]扩展Hamming码的校验矩阵7删余(Punctured)码基本原理：在原码基础上删去一个校验元，得到[n-1,k]码。是扩展码的逆过程在软判决译码和纠错纠删码中，将删去的符号看作不可靠符号最小汉明距离可能比原码小1，也可能不变例如把上例中的[8,4,4]码的最后一个校验位后，便得到了[7,4,3]Hamming码。此时删余码的校验矩阵可直接从原码的校验矩阵上删去第1行和最后1列得到一般的，若删掉的校验位只参与了其中一个校验方程，则在原码校验矩阵中删掉上述校验位对应的行和列，即可得到新码的校验矩阵8增广(Augmented)码基本原理在原码基础上，增加一个信息元，删去一个校验元得到[n,k+1,da]码基本实现方法在原码生成矩阵G的基础上，再选择一个与G中各行都不相关的n维向量，得到新矩阵Ga，该矩阵有n列，k+1行，即得到一个[n,k+1,da]码若原码中没有全1码，可在其G矩阵上增加一组全为1的行，得到增广码的生成矩阵为：且da=min{d,n-dmax(C)}9增广(Augmented)码生成矩阵最小Hamming重量10增余删信(Expurgated)码基本原理在原码基础上删去一个信息元，增加一个校验元。和增广码构造过程相反基本实现方法删掉原码生成矩阵G中的一行，得到新矩阵Ge，该矩阵有n列，k-1行，即得到一个[n,k-1,de]码若[n,k,d]码的最小汉明距离d为奇数，则挑选所有偶数重量的码字，即可构成[n,k-1,d+1]增余删信码[Recall:任何[n,k,d]线性分组码，码字的重量或全部为偶数，或者奇数重量的码字数等于偶数重量的码字数]11延长(Lengthened)码与RM码延长码对增广码再填加一个全校验位得到[n+1,k+1]码，此时码率R=(k+1)/(n+1)>k/n。和缩短(Shortened)码的构造过程相反RM码如果把(2m-1,2m-1-m,3)Hamming码的对偶码，即单纯码(2m-1,m,2m-1)进行延长，就得到一个(2m,m+1,2m-1)码，称之为一阶Reed-Muller码，用RM(1,m)表示。一般，r阶RM码RM(r,m)是[2m,k,2m-r]，其中其对偶码为RM(m-r-1,m)码12RM码Hadamard变换码长为2m

，最小距离为d=2m-r的RM(r,m)码的生成矩阵由中的那些重量大于等于d的行构成13RM码例子：m=3如果以V0到V3的4行作为G矩阵的行，则得到一个RM(1,3)码的生成矩阵若以V0到V2V1的7个矢量作为G矩阵的行，则得到一个RM(2,3)码的生成矩阵14修正的线性码改变线性码参数n,k,n-k的任意两个缩短码Shorten:删除信息符号延长码lengthen:增加信息符号删余码Puncture:删除校验符号扩展码Expand:增加校验符号增余删信码Expurgate:删除码字，增加校验符号增广码Augment:增加码字，删除校验符号修正的线性码[7,3,4]汉明码的各类修正码之间的关系1516线性码的重量分布码的性能不仅由码的最小汉明距离决定，还可由码的重量分布有关定义设Ai是[n,k,d]分组码中重量为i的码字数目，则集合{A1,A2,…,An}称为该分组码的重量分布也可以把码的重量分布写成如下的多项式形式称A(x)为码的重量估值算子，或简称重量算子如[3,1,3]重复码的重量分布为{1,0,0,1}，重量算子为17线性码的纠错能力Singletonbound

[n,k,d]线性分组码的最大可能的最小距离等于n-k+1，

即

若系统码的最小距离满足d=n-k+1,称这类码为极大最小距离可分码，简称MDS码。构造MDS码是编码理论中的一个重要课题。18线性码的纠错能力Plotkinbound

GF(q)上的(n,M,d)分组码的最小距离d满足

19线性码的纠错能力Hammingbound

长为n纠正t个错误的q进制分组码的码字数M满足20线性码的纠错能力Varshamov-Gilbertbound若码的校验元数目n-k满足的最小整数，则一定可以构造出一个长为n，最小距离为d的[n,k]线性分组码。21线性码的纠错能力Plokin限和Hamming限都是必要条件，也就是说任何线性或非线性码都是必需满足的，否则码就构造不出。越接近这个限越有效，等于时码达到最佳。V－G限是充分条件，并限定于线性码，满足这一条件必存在一个最小距离为d的[n,k]线性码。线性码的纠错能力当n→∞时，比较3个限所表示的n、R、d之间的关系（只限于二进制码）当n→∞时由P限可推出由汉明限可