信道纠错编码

对离散信源进行无失真信源编码的要求、方法及理论极限,并引出香农第一定理。以及对差错控制的基本形式、 纠错码分类及基本概念 、线性分组码 、循环码和卷积码的介绍。
展开查看详情

1.信息论与编码技术 第 4 章 信道纠错编码 苗付友 mfy@ustc.edu.cn 2016 年 9 月

2.本章介绍对离散信源进行无失真信源编码的要求、方法及理论极限,并引出香农第一定理。进一步加深对熵的物理意义的理解

3.7.1 差错控制的基本形式 7.2 纠错码分类及基本概念 7.3 线性分组码 7.4 循环码 7.5 卷积码 主要内容

4.7.3.1 一般概念 7.3.2 一致监督方程和一致 监督矩阵 7.3.3 线性分组码的 生成矩阵 7.3.4 线性分组码的编码 7.3.5 线性分组码的 最小距离 、检错和纠错能力 7.3.6 线性分组码的 译码 7.3.7 线性分组码的性能 7.3.8 汉明码 7.3.9 由已知码构造新码的方法 7.3.10 GSM 的信道编码总体方案 7.3.11 线性分组码的码限 7.3 线性分组码

5.(1) 线性分组码的编码: 编码过程分为两步: 把信息序列按一定长度分成 若干 信息码组 , 每组由 k 位 组成 ; 编码器按照预定的 线性规则 (可由线性方程组规定),把信息码组变换成 n 重( n > k )码字,其中 ( n - k ) 个附加码元是由信息码元的 线性运算 产生的。 (2) 线性分组码的码字数: 信息码组长 k 位 ,有 2 k 个不同的信息码组,有 2 k 个码字与它们一一对应。 7.3.1 一般概念

6.(3) 术语 线性分组码: 通过预定的线性运算将长为 k 位的信息码组变换成 n 重的码字 ( n > k ) 。由 2 k 个信息码组所编成的 2 k 个码字集合,称为 线性分组码 。 码字: 一个 n 重的码字可以用矢量来表示: C =( c n - 1 , c n - 1 ,…, c 1 , c 0 ) ( n , k ) 线性码: 信息位长为 k ,码长为 n 的线性码。 编码效率 / 编码速率 / 码率 / 传信率: R = k / n 。它说明了信道的利用效率, R 是衡量码性能的一个重要参数。 7.3.1 一般概念 返回目录

7.7.3.2 一致监督方程和一致监督矩阵 (1) 一致监督方程 (2) 举 例 (3) 一致监督矩阵 (4) 一致监督矩阵特性

8.(1) 一致监督方程 构成码字的方法: 编码是给已知信息码组按预定规则添加监督码元,构成码字。 在 k 个信息码元之后附加 r ( r = n - k ) 个监督码元,使每个监督元是其中某些信息元的模 2 和。 举例: k =3, r =4 ,构成 (7,3) 线性分组码。设码字为: ( c 6 , c 5 , c 4 , c 3 , c 2 , c 1 , c 0 ) c 6 , c 5 , c 4 为信息元, c 3 , c 2 , c 1 , c 0 为监督元,每个码元取“ 0” 或“ 1” 监督元按下面方程组计算: 7.3.2 一致监督方程和一致监督矩阵

9.(1) 一致监督方程 一致监督方程 / 一致校验方程:确定信息元得到监督元规则的一组方程称为监督方程 / 校验方程。由于 所有码字都按同一规则确定, 又称为一致监督方程 / 一致校验方程。 为什么叫线性分组码? 由于一致监督方程是 线性 的,即监督元和信息元之间是线性运算关系,所以由线性监督方程所确定的分组码是 线性分组码。 7.3.2 一致监督方程和一致监督矩阵

10.(2) 举例 信息码组 ( 101 ) ,即 c 6 =1, c 5 =0, c 4 =1 代入 (7.2.1) 得: c 3 =0, c 2 =0, c 1 =1, c 0 =1 由信息码组 ( 101 ) 编出的码字为 ( 101 0011 ) 。其它 7 个码字如表 8.2.1 。 7.3.2 一致监督方程和一致监督矩阵

11.7.3.2 一致监督方程和一致监督矩阵 (3) 一致监督矩阵 为了运算方便,将式 (7.2.1) 监督方程写成矩阵形式,得: 将式 (8.2.2) 可写成: H · C T = 0 T 或 C · H T = 0 C T 、 H T 、 0 T 分别表示 C 、 H 、 0 的转置矩阵。

12.7.3.2 一致监督方程和一致监督矩阵 (3) 一致监督矩阵 系数矩阵 H 的后四列组成一个 (4×4) 阶单位子阵,用 I 4 表示, H 的其余部分用 P 表示:

13.(3) 一致监督矩阵 推广到一般情况: 对 ( n , k ) 线性分组码,每个码字中的 r ( r = n - k ) 个监督元与信息元之间的关系可由下面的线性方程组确定: 7.3.2 一致监督方程和一致监督矩阵

14.(3) 一致监督 矩阵 令上式的系数矩阵为 H ,码字行阵列为 C : 7.3.2 一致监督方程和一致监督矩阵

15.(4) 一致监督矩阵特性 对 H 各行实行初等变换,将后面 r 列 化为 单位子阵 ,得到下面矩阵,行变换所得方程组与原方程组同解。 监督矩阵 H 的标准形式 : 后面 r 列 是一 单位子阵 的监督矩阵 H 。 7.3.2 一致监督方程和一致监督矩阵

16.(4) 一致监督矩阵特性 H 标准形式的特性 H 阵的每一行都代表一个监督方程,它表示与该行中“ 1” 相对应的码元的模 2 和为 0 。 H 的标准形式表明了相应的监督元是由哪些信息元决定的。例如 (7,3) 码的 H 阵的第一行为 ( 101 1000 ) ,说明第一个监督元等于第一个和第三个信息元的模 2 和,依此类推。 H 阵的 r 行代表了 r 个监督方程, 由 H 所确定的码字有 r 个监督元。 为了得到确定的码, r 个监督方程(或 H 阵的 r 行)必须是 线性独立 的,这要求 H 阵的秩为 r 。 若把 H 阵化成标准形式,只要检查单位子阵的秩,就能方便地确定 H 阵本身的秩。 7.3.2 一致监督方程和一致监督矩阵 参见方程

17.7.3.3 线性分组码的生成矩阵 (1) 线性码的封闭性 (2) 线性分组码的生成矩阵 (3) 生成矩阵与一致监督矩阵的关系 (4) 对偶码

18.(1) 线性码的封闭性 线性码的封闭性: 线性码任意两个码字之和仍是一个码字。 定理 7.3.1 : 设二元线性分组码 C I ( C I 表示码字集合 ) 是由监督矩阵 H 所定义的,若 U 和 V 为其中的任意两个码字,则 U + V 也是 C I 中的一个码字 . [ 证明 ] : 由于 U 和 V 是码 C I 中的两个码字,故有: HU T = 0 T HV T = 0 T ,那么 H ( U + V ) T = H ( U T + V T )= HU T + HV T = 0 T 即 U + V 满足监督方程,所以 U + V 一定是一个码字。 一个长为 n 的二元序列可以看作是 GF (2) ( 二元域 ) 上的 n 维线性空间中的一点。所有 2 n 个矢量集合构成了 GF (2) 上的 n 维线性空间 V n 。把线性码放入线性空间中进行研究,将使许多问题简化而比较容易解决。 ( n , k ) 线性码是 n 维线性空间 V n 中的一个 k 维子空间 V k 。 7.3.3 线性分组码的生成矩阵

19.(2) 线性分组码的生成矩阵 生成矩阵的来由 : 在由 ( n , k ) 线性码构成的线性空间 V n 的 k 维子空间中,一定存在 k 个线性独立的码字: g 1 , g 2 ,…, g k 。码 C I 中其它任何码字 C 都可以表为这 k 个码字的一种线性组合,即: 7.3.3 线性分组码的生成矩阵

20.(2) 线性分组码的生成矩阵 生成矩阵定义 : 由于矩阵 G 生成了 ( n , k ) 线性码,称矩阵 G 为 ( n , k ) 线性码的生成矩阵。 7.3.3 线性分组码的生成矩阵

21.(2) 线性分组码的生成矩阵 生成矩阵 G 的特性 G 中每一行 g i =( g i 1 , g i 2 ,…, g in ) 都是一个码字; 对每一个信息组 m ,由矩阵 G 都可以求得 ( n , k ) 线性码对应的码字。 ( n , k ) 线性码的每一个码字都是生成矩阵 G 的行矢量的线性组合,所以它的 2 k 个码字构成了由 G 的行张成的 n 维空间的一个 k 维子空间 V k 。 7.3.3 线性分组码的生成矩阵

22.(2) 线性分组码的生成矩阵 线性 系统 分组码 线性系统分组码的构成 : 通过行初等变换,将 G 化为前 k 列是单位子阵的标准形式。 7.3.3 线性分组码的生成矩阵

23.(2) 线性分组码的生成矩阵 线性 系统 分组码 线性系统分组码定义 : 用标准生成矩阵 G k × n 编成的码字,前面 k 位为信息位,后面 r = n - k 位为校验位,这种信息位在前校验位在后的线性分组码称为线性系统分组码。 当生成矩阵 G 确定之后, ( n , k ) 线性码也就完全被确定了,只要找到码的生成矩阵,编码问题也同样被解决了。 7.3.3 线性分组码的生成矩阵

24.(2) 线性分组码的生成矩阵 举例 : (7,4) 线性码的生成矩阵为: 7.3.3 线性分组码的生成矩阵

25.(3) 生成矩阵与一致监督矩阵的关系 由于生成矩阵 G 的每一行都是一个码字,所以 G 的每行都满足: H r × n ( C 1× n ) T =( 0 1× r ) T ,则有: H r × n ( G k × n ) T =( 0 k × r ) T 或 G k × n ( H r × n ) T = 0 k×r 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换 。 7.3.3 线性分组码的生成矩阵

26.(3) 生成矩阵与一致监督矩阵的关系 举例 : 已知 (7,4) 线性系统码的监督矩阵为: 7.3.3 线性分组码的生成矩阵 Q Q T

27.7.3.3 线性分组码的生成矩阵 (4) 对偶码 对偶码 : 对一个 ( n , k ) 线性码 C I ,由于 H r × n ( G k × n ) T =( 0 k × r ) T ,如果以 G 作监督矩阵,而以 H 作生成矩阵,可构造另一个码 C Id , C Id 是一个 ( n , n - k ) 线性码,称码 C Id 为原码的对偶码 . 例如 : (7,4) 线性码的对偶码是 (7,3) 码: (7,3) 码的生成矩阵 G (7,3) 是 (7,4) 码监督矩阵 H (7,4)

28.7.3.3 线性分组码的生成矩阵 ( n , k ) 线性码的编码 : 根据线性码的监督矩阵或生成矩阵 将长为 k 的信息组变换成长为 n ( n > k ) 的码字。 利用监督矩阵构造 (7,3) 线性分组码的编码电路 设码字为: C =( c 6 c 5 c 4 c 3 c 2 c 1 c 0 ) 码的监督矩阵为:

29.7.3.4 线性分组码的生成矩阵 利用监督矩阵构造 (7,3) 线性分组码的编码电路: 根据上面方程组可直接画出 (7,3) 码的并行编码电路和串行编码电路 :