PDF《State Key》

9 ? 任何 [ n, k, d ] 码,码字的重量或全部为偶数,或者奇、偶重量码 字数相等 编码与译码 对二进制 ( n, k ) 码,信息数量(或合法码字数)为2k, 对 进制 ( n, k ) 码,信息数量(或合法码字数)为2,可用编码空间的点数为 2n 个. 任一种 2k 信息集合到二进制序列集合 ( 2n ) 的映射都是一 种码因此 总共 能的编码方案有 种如2n??种(n, k ) 码.因此,总共可能的编码方案有 种.如, 共有

1029 种(100, 50) 码.

2 2 n k ? ? ? ? ? ? 共有

10 种(100, 50) 码. 译码运算量:如果直接用最大似然序列译码,对一般性的 编码而言,正比于n* 2k ,对(100,

50 ) 码,则为1017. 几乎是不可能译码的. 2019/5/15

10 State Key Laboratory of Integrated Services Networks y y g 给定参数 n、k 和d如何根据 k 个信息比特来确定对应的 n - k 个校验比特? ――利用校验矩阵 ――利用生成矩阵 2019/5/15

11 State Key Laboratory of Integrated Services Networks y y g

二、码的生成矩阵 ( p.

56 ) ―― 从线性空间的角度描述分组码 2019/5/15

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

kCCC?线性无关的矢量,则对任意的码字 C,有1122kkmmm????CCCC???? ?

1 2

1 2 T k k m m m ? ? C C C mG ? ?

13 ? G 称为该分组码的生成矩阵 码的生成矩阵 Remarks Remarks ? 生成矩阵 G 中的每一行都是一个码字 ? 任意 k 个线性独立的码字都可以作为生成矩阵 ? 给定一个 [ n, k, d ] 线性分组码,其生成矩阵可有多个 ? 给定 个[n, k, d ] 线性分组码,其生成矩阵可有多个 例子 ? 如表1中的 [ 7, 3,

4 ] 码,可从

8 个码字中任意挑 k =

3 个线性无 关的码字作为码的生成矩阵 关的码字作为码的生成矩阵

1 0

0 1

1 1

0 ? ? ? ?

1 1

1 0

1 0

0 ? ? ? ?

0 1

0 0

1 1

1 0

0 1

1 1

0 1 G ? ? ?? ? ? ? ? ?

0 1

0 0

1 1

1 0

0 1

1 1

0 1 G ? ? ??? ? ? ? ? ?

14 0

0 1

1 1

0 1 ? ?

0 0

1 1

1 0

1 ? ? 2019/5/15 State Key Laboratory of Integrated Services Networks y y g

三、码的校验矩阵 ( p.

54 ) ――从线性方程组的角度描述分组码 2019/5/15

15 码的校验矩阵 从线性方程组的角度描述线性分组码 从线性方程组的角度描述线性分组码

1 2

1 2

0 k k k c c c c c c

1 2

1 2

0 n n n k n k n k n k k c c c c c c ? ? ? ? ? ? ? ? ? ? ??????????????????? ????????? ???????????? 个校验位 个信息位 n C k 个校验位可用 k 个已知的信息位表示出来

1 1,

1 1 1,

2 2 1, n k n k n n n k n n n k n k n k c h c h c h c ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

2 2,

1 1 2,

2 2 2, n k n k n n n k n n n k n k n k c h c h c h c ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

0 0,

1 1 0,

2 2 0, n n n n n k n k c h c h c h c ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

16 2019/5/15 码的校验矩阵 ? ?? ? ? ? 1,

1 1,

1 2,

1 2,

2 1

0 0

0 0

1 0

0 n k n n k n k n n k n n k n k n h h c h h c ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ? 2,

1 2,

2 0

0 1

0 n k n n k n k n h h c ? ?? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0,