信息论与编码第八章 纠错编码.ppt

第八章 纠错编码 白慧慧 办公地址：9号教学楼北605 Email: hhbai@bjtu.edu.cn 手机内容提要 一、纠错码的基本概念 二、纠错编码的代数基础 三、线性分组码 四、循环码 五、卷积码 内容提要 一、纠错码的基本概念 二、纠错编码的代数基础 三、线性分组码 四、循环码 五、卷积码 1.信道纠错编码 2. 差错控制系统模型及分类 2. 差错控制系统模型及分类 2. 差错控制系统模型及分类 2. 差错控制系统模型及分类 2. 差错控制系统模型及分类 3. 差错类型 3. 差错类型 4. 纠错码的分类 4. 纠错码的分类 内容提要 一、纠错码的基本概念 二、纠错编码的代数基础 三、线性分组码 四、循环码 五、卷积码 近世代数简介 近世代数又称抽象代数，其研究对象是定义在某些运算下的集合，运算对象可以是数、多项式、矢量、矩阵、线性空间等。 编码理论是建立在码的代数结构基础上的，为便于初学者理解，我们将简单介绍抽象代数中与编码直接相关的基础知识，主要涉及整数及多项式的一些基本概念及群、环、域的基本知识。 1. 群 1. 群 1. 群 1. 群 在实数加法下整数集是一个交换群。在这种情况下，整数0是单位元，整数-i是整数i的逆元。除去0的有理数集合在实数乘法下是交换群。整数1是关于实数乘法的单位元，有理数b/a是a/b的乘法逆元。 1. 群 这样的二元运算称为模2(modulo-2)加法。集合G={0,1}在模2加法下是一个群。由模2加法 的定义，G在 下是封闭的，同时 满足交换律、结合律。元素0是单位元，0的逆元是它本身，1的逆元也是它本身。这样，定义了 的G是一个交换群。 1. 群 1. 群 1. 群 1. 群 令p为一个素数(例如p=2,3,5,7,11,…) 1. 群 1. 群 1. 群 1. 群 1. 群 1. 群 1. 群 1. 群 2. 域 2. 域 需要指出群(G)与域(F)的区别： 一个群只有规定的一种代数运算(加法或乘法)， 而域是有两种代数运算(加法和乘法)的代数系统。 2. 域 2. 域 2. 域 3. 环 3. 环 3. 环 3. 环 3. 环 3. 环 内容提要 一、纠错码的基本概念 二、纠错编码的代数基础 三、线性分组码 四、循环码 五、卷积码 1. 分组码相关定义 假设信源信息是二进制数字序列，将信道编码器的输出序列构成长度为n的段，记为C C=[c1,c2,…,cn] 设有m个不同的信息序列，每个不同的序列由k(kn)位相继的信息数字组成。由于每个信息序列组成k位二进制数字，则有2k个可能不同的信息序列，即m=2k，这2k个码字的集合称为(n,k)分组码。 1.分组码相关定义 对于2k个n长码字全体构成的分组码，其码字中的k位称为信息位，n-k位称为校验位或监督位。 例如，当k=3，n=7时，可能的消息序列数m=2k=8个，可能的长为n=7的预选序列有27=128个。具体如表： 对于所选定的n长序列称为允许使用序列，即码字；而其他序列则是不允许使用的，即禁用序列。 该例中，信息位为3，码长为7，监督位为4，如果用R=k/n表示码字中信息位所占比重，称为编码效率。表明了信道的利用率。 1.分组码相关定义 若(n,k)分组码中k个信息位同原始k个信息位相同，且位于n长码字的前(或后)k位，而校验位位于其后(或前)，则称该分组码为系统码，否则为非系统码。 右表所示为系统码。 2. 线性分组码定义 定义：[n, k]线性分组码是GF(q)上的n维线性空间中的一个k维子空间。 2. 线性分组码定义 也可以这样理解：n长码字C=[c1,c2,…,cn]中每一位同原始的k个信息位d=[d1,d2,…dk]之间满足一定的函数关系ci=f(d1,d2,…dk), (n=1,2,…,n) 若函数关系是线性的，则称该分组码为线性分组码，否则为非线性分组码。 2. 线性分组码定义 2. 线性分组码定义 2. 线性分组码定义 容易验证C是线性的。假设消息序列与码字序列的映射关系为如下两种： 第一种： 映射关系为： 第二种： 映射关系与第一种截然不同。 2. 线性分组码定义 3. 线性分组码编码 3. 线性分组码编码 由校验方程，可将n=7，k=3的线性分组码写成 3. 线性分组码编码 3. 线性分组码编码 3. 线性分组码编码 3. 线性分组码编码 3. 线性分组码编码 生成矩阵和校验矩阵关系 例题 （n，k）线性分组码编码电路 4. 伴随式与译码 4. 伴随式与译码 4. 伴随式与译码 证明：根据线性分组码的封闭性可知，任意