Lecture 4 线性分组码(2).

Presentation on theme: "Lecture 4 线性分组码(2)."— Presentation transcript:

1 Lecture 4 线性分组码(2)

2 内容 修正的线性码 线性码的重量分布 线性码的纠错性能 扩展码，删余码 增广码，增余删信码 延长码，Reed-Muller码
Singleton bound Hamming (sphere packing) bound Varshamov-Gilbert bound McEliece-Rodemich-Rumsey-Welch upper bound

3 修正的线性码 纠错码的设计码长通常由矩阵或多项式的代数和组合特性决定 线性分组码的设计码长通常不等于理想码长 例如： 修正方法
二进制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码的校验矩阵

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码 延长码 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)码

12 修正的线性码 改变线性码参数n, k, n-k的任意两个 Shorten: 删除信息符号 lengthen: 增加信息符号
Puncture: 删除校验符号 Expand :增加校验符号 Expurgate: 删除码字，增加校验符号 Augment: 增加码字，删除校验符号

13 汉明码的各类修正码之间关系图

14 第四节 线性码的纠错能力(p79) 码的重量分布(p73) 普洛特金限(P限) 汉明限 V-G限

15 一、码重量分布

16 线性码的重量分布 码的性能不仅由码的最小汉明距离决定，还可由码的重量分布有关 定义
设Ai是[n, k ,d]分组码中重量为i的码字数目，则集合{A1, A2, …, An}称为该分组码的重量分布 也可以把码的重量分布写成如下的多项式形式 称A(x)为码的重量估值算子，或简称重量算子 如 [3, 1, 3]重复码的重量分布为{1, 0, 0, 1}，重量算子为

17 马克威伦(MacWilliams)恒等式
设二进制[n, k]线性分组码及其[n, n-k]对偶码的 重量算子分别是 则它们之间有如下关系：

18 线性分组码的不可检错误概率 线性码是同距离分布码 若码字等概发送 平均不可检 错误概率

19 译码错误与译码失败概率 teD译码器正确译码的概率 译码错误概率 译码失败概率 误码率 (参见pp.78)

20 普洛特金（P）限

21 GF(q)上(n,M,d)分组码的最小距离d为：

22 三、汉明限(H限、球包限)

23 长为n纠t个错误的q进制分组码的码字数M为：

24 四、V-G限

25 若码的校验元数目n-k满足 则一定可以构造出一长为n、最小距离为d的[n, k]线性分组码

26 当n时，由P限可推出： 由汉明限可推出： 由V-G限可推出：

27 最大的最小距离存在区间