信息论与编码基础_教学课件.ppt

信息论与编码基础 线性分组码 一、线性分组码的基本原理 二、循环码的基本原理 1、基本概念 2、循环码的编码 3、循环码的一般译码方法 4、循环汉明码及其派生码 信息论与编码基础 循环汉明码 线性分组码 既约多项式：如果多项式f(x)除了常数和它本 身以外，不能再被GF(q)的其他多项式除尽，则 称f(x)是GF(q)上的既约多项式。 本原多项式：若m次既约多项式f(x)除尽xn+1的 最小正整数n满足n=2m-1，则称该多项式为本原 多项式。 由m次本原多项式g(x)生成的长度2m-1(m≥3)的 循环码是(2m-1, 2m-1-m)汉明码。 0000000 0001011 0010110 0011101 0101100 0100111 0110001 0111010 1000101 1001110 1010011 1011000 1110100 1101001 1100010 1111111 缩短循环码 线性分组码 信息论与编码基础 缩短循环码字已经不再具有循环特性。 信息论与编码基础 缩短循环码 线性分组码 与门 输出 输入R D0 D1 D2 D3 10级移位寄存器 信息论与编码基础 删信循环码 线性分组码 信息论与编码基础 循环码编码电路 循环码译码电路 线性分组码 本课小结 循环汉明码、缩短码、删信码 习题六: 3, 4, 5 , 12 , 17、18 1、汉明码的结构 码长 信息位数 监督码位 最小码距 纠错能力 信息论与编码基础 线性分组码 信息论与编码基础 2、扩展汉明码 (7,4)汉明码 (8,4)扩展汉明码 线性分组码 信息论与编码基础 3、从已知线性分组码来构造新的线性分组码 2）凿孔码 将线性分组码中所有码字的某些校验位删除。 3）除删码 将线性分组码中一部分码字删除。 4）增广码 与除删码对应。 5）延长码 原码 增广 扩展。 线性分组码 1）缩短码 缩短线性分组码的信息位。 信息论与编码基础 扩展汉明码 (2r,2r-1-r,4) 偶重量码字构成 的子码 (2r-1,2r-2-r,4) 汉明码 (2r-1,2r-1-r,3) 通过增 加全校 验位来 扩展 在全校 验位上 凿孔 延长 缩短 除删 丢弃奇重码字 通过加入全“1” 分量来增广 线性分组码 3、从已知线性分组码来构造新的线性分组码 信息论与编码基础 线性分组码的纠错能力（d0 与 H的关系） 汉明码（完备性，码结构 ） 本课小结 构造新的线性分组码的方法 线性分组码 信息论与编码基础 线性分组码 一、线性分组码的基本原理 二、循环码的基本原理 1、基本概念 2、循环码的编码 3、循环码的一般译码方法 4、循环汉明码及其派生码 多项式 零多项式:各次系数均为0的多项式 首一多项式：最高次系数为1的多项式 信息论与编码基础 线性分组码 汉明码 (7,4)汉明码码字 (0000000) (0001011) (0010110) (0100111) (1000101) (0011101) (0101100) (1001110) (0110001) (1010011) (1100010) (0111010) (1011000) (1110100) (1101001) (1111111) (0000000) (0001011) (0010110) (0100111) (1000101) (0011101) (0101100) (1001110) (0110001) (1010011) (1100010) (0111010) (1011000) (1110100) (1101001) (1111111) 信息论与编码基础 线性分组码 信息论与编码基础 1 0 0 0 1 0 1 1000101 0001011 0010110 0101100 1011000 0110001 1100010 0100111 1001110 0011101 0111010 1110100 1101001 1010011 0 1 0 0 1 1 1 1111111 0000000 循环汉明码 信息论与编码基础 线性分组码 码多项式 信息论与编码基础 线性分组码 生成多项式 定理一个二进制(n,k)循环码中有唯一的非零最低次多项式 ，且常数项为1。 生成多项式 信息论与编码基础 线性分组码 例子 例 GF(2)上多项式 构造一个（7，3）循环码。 码多项式 码 字 （0010111） （0101110） （1011100） （0111001） （1110010） （1100101） （1001011） （0000000） 只要知道了xn+1的因式分解，用它的各个因式 的乘积，便能得到很多个不同的循环码。 生成矩阵和一致