94线性分组码 选 1、线性分组码 线性分组码中信息码元和监督码元是用线性方 程联系起来的。线性码建立在代数学群论基础上, 线性码各许用码组的集合构成代数学中的群,因此, 又称群码。 2、主要性质 (1)任意两许用码组之和(模2和)仍为一许 用码组。(封闭性) (2)码的最小距离等于非零码的最小重量。 2021/2/23 海南大学信息学院 Return Next
2021/2/23 海南大学 信息学院 9.4 线性分组码 Return Next 1、线性分组码 （1）任意两许用码组之和（模2和）仍为一许 用码组。（封闭性） （2）码的最小距离等于非零码的最小重量。 线性分组码中信息码元和监督码元是用线性方 程联系起来的。线性码建立在代数学群论基础上， 线性码各许用码组的集合构成代数学中的群，因此， 又称群码。 2、主要性质
94线性分组码 选 3、奇偶监督码—最简单的线性码 偶校验时:S=an1④an2…④a S称为校正子,又称伴随式。S=0无错 S=1有错。 般,由r个监督方程式计算得r个校正子, 可以用来指示2-1种错误,对于一位误码来说, 就可以指示2-1个误码位置。对于(n,k)码,如 果满足27-1≥n则可能构造出纠正一位或一位以 上错误的线性码。 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 一般，由 r 个监督方程式计算得 r 个校正子， 可以用来指示 2 r -1 种错误，对于一位误码来说， 就可以指示 2 r -1 个误码位置。对于(n，k)码，如 果满足 2 r -1≥n 则可能构造出纠正一位或一位以 上错误的线性码。 Return Back Next 9.4 线性分组码 3、奇偶监督码 —— 最简单的线性码 S 称为校正子，又称伴随式。 S = 0 无错， S=1 有错。 偶校验时： S = a n−1 a n−2 a0
94线性分组码 选 例:设分组码(n,k)中k=4,为丝正一 位错码,要求r≥3,则n=k+r=7。 校正子S1S2S3的值与错码位置的对应关系表 3 错码位置 错码位置 001 101 010 110 100 111 011 3 000 无错 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 例：设分组码 （n，k）中k=4，为纠正一 位错码，要求r≥3， 则 n=k+r=7。 S1S2S3 错码位置 S1S2S3 错码位置 0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a5 1 0 0 a2 1 1 1 a6 0 1 1 a3 0 0 0 无错 Return Back Next 9.4 线性分组码 校正子S1S2S3的值与错码位置的对应关系表
94线性分组码 选 4、线性分组码的构造 判断错码位置 a tas ta +as+a3+a1模2加 S3=(6+a4+a3+ao ■计算监督位(无错码时,校正子为0) C、=a.+a.+a 计算监督位 a =a ta. a a =a ta a 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 9.4 线性分组码 S1 = a6 + a5 + a4 + a2 S2 = a6 + a5 + a3 + a1 S3 = a6 + a4 + a3 + a0 a2 = a6 + a5 + a4 a1 = a6 + a5 + a3 a0 = a6 + a4 + a3 计算监督位 模2加 ▪ 判断错码位置 ▪ 计算监督位（无错码时，校正子为0） 4、线性分组码的构造
94线性分组码 选 从而给定信息位后,可直接按上式算出监督 位,构造出线性分组码(见P289表9-5)。 按上述方法构造的纠正单个错误的线性分组 码称为汉明码。 码长n=2r-1信息位k=2r-1-r监督位r 编码效率 k27-1- 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 9.4 线性分组码 按上述方法构造的纠正单个错误的线性分组 码称为汉明码。 码长 n=2r – 1 信息位 k= 2r – 1 – r 监督位r 编码效率= n r r r n k r r r = − − = − − − − = 1 2 1 1 2 1 2 1 从而给定信息位后，可直接按上式算出监督 位，构造出线性分组码（见P289 表9-5）
94线性分组码 选 计算监督位的方程租改写为: 1·an+1·a3+1·a1+0·a3+1·a2+0·a1+0·an=0 1.a+1·a.+0.a.+1.a.+0·a.+1.a.+0·a.=0 1.a+0·a.+1.a.+1.a.+0·a.+0.a.+1 表示成矩阵形式 10100 11P010 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 9.4 线性分组码 计算监督位的方程租改写为： 1 1 1 0 1 0 0 0 a6 + a5 + a4 + a3 + a2 + a1 + a0 = 1 1 0 1 0 1 0 0 a6 + a5 + a4 + a3 + a2 + a1 + a0 = 1 0 1 1 0 0 1 0 a6 + a5 + a4 + a3 + a2 + a1 + a0 = 表示成矩阵形式 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 2 3 4 5 6 a a a a a a a = 0 0 0 P Ir
94线性分组码 选 简记为HA=0或AH=0 H称为监督矩阵,H确定,则编码时监督位 和信息位的关系就完全确定了 P为r×k阶、I为r×r阶单位方阵,具 有[PIr|形式的H矩阵称为典型阵。 1110 还可以写成: 1011 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 9.4 线性分组码 简记为 或 H称为监督矩阵，H确定，则编码时监督位 和信息位的关系就完全确定了。 T T HA = 0 = 0 T AH 0 1 2 a a a = 1 0 1 1 1 1 0 1 1 1 1 0 3 4 5 6 a a a a P为r × k 阶、Ir 为 r × r 阶单位方阵，具 有[ P Ir ]形式的H矩阵称为典型阵。 还可以写成：
94线性分组码 选 或 111 Fla 101 Q Q=Pkx阶 给定信息位后,用信息位的行矩阵乘矩阵Q 就产生出监督位 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 Return Back Next 9.4 线性分组码 或 a2 a1 a0 = a6 a5 a4 a3 0 1 1 1 0 1 1 1 0 1 1 1 6 5 4 3 = a a a a Q Q = P T k r阶 给定信息位后，用信息位的行矩阵乘矩阵Q 就产生出监督位
94线性分组码 选 将Q的左边加上一kxk阶单位方阵就构成矩阵 G: G=[Q]一生成矩阵 I=ae a a, a,]G G 具有G=[4Q]形式的生成矩阵称为典 型生成矩阵 由典型生成矩阵得出的码组A中,信息位不 变,监督位附加其后,这种码称为系统码。 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 由典型生成矩阵得出的码组A中，信息位不 变，监督位附加其后，这种码称为系统码。 Return Back Next 9.4 线性分组码 具有 形式的生成矩阵称为典 型生成矩阵。 G I Q = k G I Q = k — 生成矩阵 6 5 4 3 2 1 0 a a a a a a a 6 5 4 3 = a a a a G 6 5 4 3 A = a a a a G 将Q的左边加上一 kk 阶单位方阵就构成矩阵 G：
94线性分组码 选 5、错误图样与校正子之间的关系 发送码组A在传输过程中可能发生误码,设接 收到的码组为B=[bn1bn2…bl 则 B-A=E E=en1en2…,Col错码行矩阵一错误图样 0当b 1当b≠a 也可写作 B=A+E 2021/2/23 海南大学信息学院 Return Back Next
2021/2/23 海南大学 信息学院 发送码组A在传输过程中可能发生误码，设接 收到的码组为B =[ bn-1 bn-2 … b0 ] E= [ en-1 en-2 … e0 ] 错码行矩阵 — 错误图样 = = i i i i i b a b a e 当 当 1 0 Return Back Next 9.4 线性分组码 5、错误图样与校正子之间的关系 则 B – A = E 也可写作 B = A+E