PDF《State Key》

State Key Laboratory of Integrated Services Networks y y g Lecture

3 线性分组码(1) 线性分组码(1)

1 2019/5/15 内容 线性分组码基本概念 码的生成矩阵与校验矩阵 对偶码,系统码,缩短码与汉明码 标准阵列译码 标准阵列译码

2 2019/5/15 State Key Laboratory of Integrated Services Networks y y g 线性分组码基本概念

一、线性分组码基本概念 ( pp

52 C

54 ) ( pp.

52 54 ) 2019/5/15

3 Hamming距离与重量 g 汉明(Hamming)距离 给定两个序列C1和C2 它们对应位取 汉明(Hamming)距离:给定两个序列C1和C2,它们对应位取 值不同的个数称为C1和C2的汉明距离.若C1 = 10101, C2 = 01111;

则d(C1, C2 ) =

3 汉明重量:序列 C 中非零码元的个数 w ( C1 ) = 3,w ( C2 ) =

4 最小汉明距离:(n, k) 分组码中,设任意两个码字之间距离的最小值 最小汉明距离:(n, k) 分组码中,设任意两个码字之间距离的最小值 为d0,则d0 定义为该分组码的最小汉明(Hamming)距离 2019/5/15

4 码纠错能力及编码增益 任一 (n, k) 分组码,若要在码字内: 任(n, k) 分组码,若要在码字内: ? 1) 检测 e 个随机错误,则要求码的最小汉明距离d0 >

= e +

1 ? 2) 纠正 t 个随机错误 则要求d 2t

1 ? 2) 纠正 t 个随机错误,则要求d0>

= 2t +

1 ? 3) 纠正 t 个随机错误,同时检测e (e>

=t)个错误,则要求d0 >

= e + t +

1 ? 4) 纠正 t 个随机错误和ρ个删除,则要求 d0 >

=

2 t+ρ+

1 编码增益: ? 给定性能前提下(p.15), p 编码增益 = 未编码时需要的信噪比(dB) C 编码时需要的信噪比(dB) 2019/5/15

5 信道编码的作用 信道编码的作用:在资源、可靠性和传信量之间选择一个 好的 作点 有时还要考虑 时 好的工作点(有时还要考虑延时). 资源指的提供信息传输所付出的代价 ? 包括频率、时间、空间、功率等等.但不包括实现复杂度 ? 个好的编码就是要充分利用资源 传递尽可能多的信息 ? 一个好的编码就是要充分利用资源,传递尽可能多的信息 2019/5/15

6 线性分组码定义 定义 定义 ? [ n, k ] 线性分组码是 GF( q ) 上的 n 维线性空间中的一个 k 维 子空间 该子空间在加法运算下构成 群 所以线性分 子空间.该子空间在加法运算下构成 Abelian 群,所以线性分 组码又称群码.若码字的最小距离为 d,则记为 [ n, k, d ] 码, 码率 R = k / n;

或记为 ( n, M, d ) 码,其中 M 表示可用码字个 数,此时码率表示为 R = (log M) / n 数,此时码率表示为 R (logq M) / n 2k 2n

7 2019/5/15 线性分组码 例子 ? 简单重复码 [ n, 1, n ]

1 2 c c i n ? ? ? 表1 [

7 3

4 ] 码字码表 , 1,2, , i c c i n ? ? 信息组 码字 表1. [ 7, 3,

4 ] 码字码表 ? 简单奇偶校验码 [ n, n-1,

2 ]

1 2

0 c c c ? ? ? ? ?

000 001

010 0000000

0011101 0100111

1 2

0 n c c c ? ? ?

010 011

100 0100111

0111010 1001110 ? [ 7, 3,

4 ] 码100

101 110

111 1001110

1010011 1101001

1110100 111

1110100 8 2019/5/15 线性分组码性质 性质 ? [ n, k, d ] 码中d 等于非零码字的最小重量,即min ( ) i d w C ? ? GF(2)上[n, k, d ] 码中,任何两个码字 C1,C2 之间有如下关系: [ , ] ( ) i i C n k ? w (C1 + C2) = w (C1) + w (C2) - 2w (C1 ・ C2) 或d(C C ) ≤ w (C ) + w (C ) 或d(C1, C2) ≤ w (C1) + w (C2) 式中, C1 ・ C2是两个码字的内积 式中

1 2是两个码字的内积 ? GF(2)上线性分组码任3个码字C1,C2 ,C3之间的汉明距离满足 d (C1, C3) ≤ d (C1, C2) +d (C2, C3) ? 任何 [ n k d ] 码 码字的重量或全部为偶数 或者奇 偶重量码