Lecture线性分组码.pptVIP

State Key Laboratory of Integrated Services Networks Lecture 4 线性分组码(2) 内容 修正的线性码 扩展码，删余码 增广码，增余删信码 延长码，Reed-Muller码 线性码的重量分布 线性码的纠错性能 Singleton bound Hamming (sphere packing) bound Varshamov-Gilbert bound McEliece-Rodemich-Rumsey-Welch upper bound 修正的线性码 纠错码的设计码长通常由矩阵或多项式的代数和组合特性决定 线性分组码的设计码长通常不等于理想码长 例如： 二进制Hamming码的设计码长为2m-1(7, 15, 31,…) 修正方法 线性分组码三个参数(n, k, n-k): 增大一个参数，降低另一个参数，保持第三个参数不变。 共有6种方法 扩展(Expanded)码 基本原理：对[n, k, d]线性分组码中的每一个码字，增加一个校验元 ，满足： 称为全校验位 若d为偶数， [n, k, d]码变成了[n+1, k, d] 若d为奇数， [n, k, d]码变成了[n+1, k, d+1] 校验矩阵 扩展(Expanded)码 校验矩阵 扩展(Expanded)码 例子： [7,4,3]Hamming码的校验矩阵 增加一个全校验位后得到的[8, 4 , 4]扩展Hamming码的校验矩阵 删余(Punctured)码 基本原理：在原码基础上删去一个校验元，得到[n-1, k]码。是扩展码的逆过程 在软判决译码和纠错纠删码中，将删去的符号看作不可靠符号 最小汉明距离可能比原码小1，也可能不变 例如把上例中的[8, 4, 4]码的最后一个校验位后，便得到了[7, 4, 3]Hamming码。此时删余码的校验矩阵可直接从原码的校验矩阵上删去第1行和最后1列得到 一般的，若删掉的校验位只参与了其中一个校验方程，则在原码校验矩阵中删掉上述校验位对应的行和列，即可得到新码的校验矩阵 增广(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)} 增广(Augmented)码 生成矩阵 最小Hamming重量 增余删信(Expurgated)码 基本原理 在原码基础上删去一个信息元，增加一个校验元。和增广码构造过程相反 基本实现方法 删掉原码生成矩阵G中的一行，得到新矩阵Ge，该矩阵有n列，k-1行，即得到一个[n, k-1, de]码 若[n, k, d]码的最小汉明距离d为奇数，则挑选所有偶数重量的码字，即可构成[n, k-1, d+1]增余删信码 [Recall: 任何[n, k, d]线性分组码，码字的重量或全部为偶数，或者奇数重量的码字数等于偶数重量的码字数] 延长(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)码 修正的线性码 改变线性码参数n, k, n-k的任意两个 Shorten: 删除信息符号 lengthen: 增加信息符号 Puncture: 删除校验符号 Expand :增加校验符号 Expurgate: 删除码字，增加校验符号 Augment: 增加码字，删除校验符号 汉明码的各类修正码之间关系图 第四节 线性码的纠错能力(p79) 码的重量分布(p73) 普洛特金限(P限) 汉明限 V-G限 一、码重量分布 线性码的重量分布 码的性能不仅由码的最小汉明距离决定，还可由码的重量分布有关 定义 设Ai是[n, k ,d]分组码中重量为i的码字数目，则集合{A1, A2, …, An}称为该分组码的重量分布 也可以把码的重量分布写成如下的多项式形式 称A(x)为码的