Lecture 3 线性分组码(1).

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

1 Lecture 3 线性分组码(1)

2 内容 线性分组码基本概念 码的生成矩阵与校验矩阵 对偶码，系统码，缩短码与汉明码 标准阵列译码

3 Hamming距离与重量 汉明（Hamming）距离：给定两个序列C1和C2，它们对应位取值不同的个数称为C1和C2的汉明距离。若C1=10101,C2=01111;则 d(C1,C2)=3 汉明重量：序列C中非零码元的个数 w(C1)=3,w(C2)=4 最小汉明距离：(n, k)分组码中，设任意两个码字之间距离的最小值为d0，则d0定义为该分组码的最小汉明（Hamming）距离 2019/5/4

4 码纠错能力及编码增益 任一(n, k)分组码，若要在码字内： 编码增益： 编码增益=未编码时需要的信噪比(dB) – 编码时需要的
1) 检测e个随机错误，则要求码的最小汉明距离d0>=e+1 2) 纠正t个随机错误，则要求d0>=2t+1 3) 纠正t个随机错误，同时检测e (e>=t)个错误，则要求d0>=e+t+1 4) 纠正t个随机错误和ρ个删除，则要求 d0>=2t+ρ+1 编码增益： 给定性能前提下（pp.15）， 编码增益=未编码时需要的信噪比(dB) – 编码时需要的 信噪比(dB) 2019/5/4

5 线性分组码定义 定义 [n, k]线性分组码是GF(q)上的n维线性空间中的一个k维子空间。该子空间在加法运算下构成Abelian群，所以线性分组码又称群码。若码字的最小距离为d，则记为[n, k, d]码，码率R=k / n；或记为(n, M, d)码，其中M表示可用码字个数，此时码率表示为R= (logqM) / n 2k 2n

6 线性分组码 例子 简单重复码[n, 1, n]； 简单奇偶校验码[n, n-1, 2] [7, 3, 4]码
表1 [7, 3, 4]码字码表 信息组 码字 000 001 010 011 100 101 110 111

7 线性分组码性质 性质 [n, k, d]码中d等于非零码字的最小重量，即
GF(2)上[n, k, d]码中，任何两个码字C1，C2之间有如下关系： w(C1 + C2)=w(C1)+w(C2)-2w(C1 · C2) 或 d(C1, C2) ≤ w(C1)+w(C2) 式中， C1 · C2是两个码字的内积 GF(2)上线性分组码任3个码字C1，C2 ，C3之间的汉明距离满足 d(C1, C3) ≤ d(C1, C2) ＋d(C2, C3) 任何[n, k, d]码，码字的重量或全部为偶数，或者奇、偶重量码字数相等

8 码的生成矩阵 编码问题 利用生成矩阵 给定参数n、k，如何根据k个信息比特来确定对应的n-k个校验比特？ 利用校验矩阵或生成矩阵
由于[n, k, d]线性分组码是一个k维线性空间，因此，必可找到k个线性无关的矢量，能张成该线性空间。设 是k个线性无关的矢量，则对任意的码字C，有 G称为该分组码的生成矩阵

9 码的生成矩阵 Remarks 例子 生成矩阵G中的每一行都是一个码字 任意k个线性独立的码字都可以作为生成矩阵
给定一个[n, k, d]线性分组码，其生成矩阵可有多个 例子 如表1中的[7, 3, 4]码，可从8个码字中任意挑k = 3个线性无关的码字作为码的生成矩阵

10 码的校验矩阵 从线性方程组的角度描述线性分组码 n-k个校验位可用k个已知的信息位表示出来

11 码的校验矩阵 校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k 以校验矩阵的n-k行为基底，可张成一个n-k维线性子空间

12 码的校验矩阵 例子：表1的[7, 3, 4]码(pp.52)的4个校验元可由如下线性方程组求得 因此，校验矩阵为

13 码的校验矩阵 Remarks 校验矩阵和生成矩阵的关系 校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k
校验矩阵的n-k行为基底，可张成一个n-k维线性子空间 任意一个合法码字C均满足 HCT=0T 交换校验矩阵的各列并不影响其纠错能力 校验矩阵和生成矩阵的关系 校验矩阵H与任意一个码字之积为零，因此有 校验矩阵H中各行张成的子空间的零空间即为生成矩阵G各行张成的子空间。

14 对偶码，系统码与缩短码 对偶码 系统码 缩短码
设[n, k, d]线性分组码C的生成矩阵为G，校验矩阵为H，以H作为生成矩阵，G为对应的校验矩阵，可构造另一个[n, n-k, d’]线性分组码C1，我们称C1为C的对偶码 系统码 缩短码 从[n, k, d]线性分组码的所有码字中，把前面i位全为零的码字挑选出来构成一个新的子集，该子集即为[n, k, d]的缩短码。传输时，仅传输后面的n-i位码元，记为[n-i, k-i, d]码，其纠错能力至少与原[n, k, d]码相同

15 缩短码 例子： 表1的[7, 3, 4]码： ， ， ， ， ， ， ， [6, 2, 4]缩短码为： ，011101，100111，111010 原码和缩短码的生成矩阵分别为 去掉G的第一列第一行，就得到缩短码的生成矩阵Gs

16 缩短码 原码和缩短码的校验矩阵分别为 对系统码而言，去掉G的前i列和前i行就可得到缩短码的生成矩阵Gs。去掉校验矩阵的前i列，可得到缩短码的校验矩阵Hs

17 最小汉明距离 定理: [n, k, d]线性分组码最小汉明距离等于d的充要条件是：H的任意d-1列线性无关 (pp.61)
Proof . [hint: 必要性：采用反证法；充分性：将H中某些d列线性相关的列的系数作为码字中对应的非0分量] 推论: [n, k, d]线性分组码的最大可能的最小汉明距离为n-k+1 Proof: 由于校验矩阵H的n-k行是线性无关的，也就是说H的行秩为n-k，从而可推出H的列秩最大是n-k，即H最多有任意n-k列线性无关，由定理得到n-k≥d-1,有d≤n-k+1

18 汉明码 定义 例子： 码长： n=2m-1 信息位长度： k=2m-1-m 码率： R=(n-m) / n 最小汉明距离：d=3
校验矩阵有 m行，2m-1列，取互不相同的m重构成 例子： GF(2)上的[7,4,3]汉明码，8个3重为001, 010, 011, 100, 101, 110, 111, 000校验矩阵为：

19 线性分组码的译码 伴随式 设发送码字 接收序列 根据错误图样的概念，R=C+E
S是校验矩阵H中某几列数据的线性组合，因而是n-k维向量，有2n-k种可能 错误图样E是n维向量，共有2n种可能，因而每2k种错误图样对应一种伴随式。

20 伴随式 例子 [7,3,4]码的校验矩阵H为 错误图样及其相应的伴随式 E1=(1000000) S1T=HE1T =(1110)T

21 标准阵列译码 标准阵列步骤 标准阵列基本原理 1): 由接收到的序列R，计算伴随式S=RHT ；
2): 若S=0，正确接收；若S不为零，寻找错误图样； 3): 由错误图样解出码字C=R-E。 标准阵列基本原理 根据许用码字将禁用码字进行分类，分类的依据是错误图样。 关键问题在于如何选择错误图样，使错误概率尽可能小 在错误概率p<0.5的BSC信道条件下，应首先选择重量最轻的错误图样。

22 标准阵列译码 C1 C2 …Ci … E2 E3 C2+E2 C2+E3 Ci+E3 Ci+E2 C2+ Ci+ 码字 禁用码字
(陪集首)

23 标准阵列译码 发送端经过[7,3,4]码编码后的码字序列，通过有噪信道后，在接收端观测到的序列为R=( )。采用标准阵列译码估计相应的信息序列。 当E1=( )时 S1T=HE1T =(1110)T 因此，C=R+E1= ( )

24 完备译码与限定距离译码 完备译码 [n, k, d]线性分组码的所有2n-k个伴随式，在译码过程中若都用来纠正所有小于等于 个随机错误，以及部分大于t的错误图样，则这种译码方法称为完备译码 限定距离译码 任一[n, k, d]码，能纠正 个随机错误。如果在译码时，仅纠正t’ < t个错误，而当错误个数大于t’时，译码器不进行纠错而仅指出发生了错误，称这种译码方法为限定距离译码。