PDF《第十章》

31 10.4 线性分组码 ? 概念 ? 监督码只监督本码组的码元 ? 信息码与监督码之间可用一组线性方 程来表示 ? 特点 ? 具有较大的汉明距,纠/检错能力强 ? 监督码元数相对较少,编码效率较高

32

一、编码 ? 任务 ? 找到监督码与信息码之间的变换关系 ? 构造编码表,列出所有可用码组 编码器 k bit 信息码 n bit 分组码 编码规则

33 ? (n, k)线性分组码 ? 信息码为D,分组码为C,满足线性方 程式 其中: 表示模2和若,当 时,称为系统 分组码 ∑ = = k j j ij i d h c

1 n i L

2 ,

1 = ∑ i i d c = k i L

2 ,

1 =

34 ? 生成矩阵G ? 设矢量 设矩阵G用于由D生成C,即:C=D*G ? ,其中 Ik 为k阶单位阵, Q为k*r 阶矩阵,具有单位阵形式的矩 阵G称为典型生成矩阵 ( ) r k k k c c c c C + + = L L

1 1 , ( ) k d d D L

1 = n k k Q I G * = ] [

35 ? 监督矩阵H ? 由 ,可令 ? 或 称为监督方程 H 称为系统分组码的典型监督矩阵 ? 若已知 G 或H,则可得到编码表 n k kQ I G * = ] [ n r r T I Q H * = ] [ T T C H

0 = ?

0 = ? T H C

36 ? 例:(7, 3)线性分组码,构造编码表, 已知典型生成矩阵 ? ? ? ? ? ? ? ? ? ? =

1 0

1 1

1 0

0 1

1 1

0 0

1 0

0 1

1 1

0 0

1 G

37 ? 生成矩阵G和监督矩阵H的特点 ? 编码方法完全由G确定,H确定了编码时 监督码元与信息码元的关系 ? k bit信息码与n bit分组码一一对应 ? G和H的各行必须是线性无关的 ? G的每行本身就是一个可用码组 ? 若给定G不是典型阵,需要变换为典型阵

38 ? 线性分组码的性质 ? 封闭性 ? 任意两个可用码组之和仍为可用码组,即 线性分组码对模2加运算具有封闭性 ? 是群码 ? 封闭性、单位元素、逆元素、结合律成立 ? 汉明距d0 = 非零码的码重最小值 ? 码距是两个码组模2和的码重

39

二、译码 ? 以汉明码为例 译码器 n bit 分组码 k bit 可能信息码 检/纠错

40 ? 汉明码概念 ? 能够纠正一位错码的线性分组码,可 具有较大的编码效率 ? (n, k)汉明码, ,满足 ? 编码效率 n r ≥ ?1

2 L

4 ,

3 ,

2 = r

1 2

1 1 ? ? = ? = = r r n r n k R

3 1

2 0 = + ≥ t d

41 ? 译码方法 ? 利用 G 或H,建立校验子 S 和错码位 置的对应关系,形成校验方程,每个 校验子只参与一个校验方程 ? 根据校验方程构造错误图样表 ? 查表译码

42 ? 设发送码组 接收码组 若 ,则无错 若 ,则有错,需定义: 差错行矢量 ( )

0 1

2 1 , , , a a a a A n n L ? ? = ( )

0 1

2 1 , , , b b b b B n n L ? ? = A B = A B ≠ ( )

0 1

2 1 , , , e e e e E n n L ? ? = i i i i i a b a b e ≠ = ? ? ? =

1 0 第i位为无错 第i位有无错

43 ? 定义 称为校验子 则 称为校验方程 ? 已知G/H,建立错误图样表 ? 例: (7, 4)汉明码,若接收端收到码 组(1100110),求译码输出 ( ) r s s s S L , ,

2 1 = T H E S ? =

44 ? 已知: ? 错误图样表 ? ? ? ? ? ? ? ? ? ? ? ? =

1 1

0 1

0 0

0 1

0 1

0 1

0 0

0 1

1 0

0 1

0 1

1 1

0 0

0 1 G e6 e5 e4 e3 e2 e1 e0

0 错码位置

111 110

101 011

100 010

001 000 校验子 S1S2S3

45 ? 例:已知线性分组码生成矩阵,求: ? 确定(n, k)码的n和k ? 当信息位是111时,监督位是多少 ? 列出所有可用码组 ? 分析纠/检错能力 ? 若译码器工作在纠错模式下,列出错误图样表 ? 当译码输入110001111111时,输出是什么 ? 编码效率 ? ? ? ? ? ? ? ? ? ? =

1 0

1 1

1 0