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

《信息论与编码基础_教学课件_6.ppt》由会员分享，可在线阅读，更多相关《信息论与编码基础_教学课件_6.ppt（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理二、循环码的基本原理信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理一、线性分组码的基本原理二、循环码的基本原理1、基本概念2、生成矩阵和一致校验矩阵3、线性分组码的译码及纠错能力4、汉明码简介信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理一、线性分组码的基本原理二、循环码的基本原理1、基本概念2、生成矩阵和一致校验矩阵3、线性分组码的译码及纠错能力4、汉明码简介编码器编码器信息序列码元序列信息论与编码基础信息论与编码基础线性分组码线性分组码例例（7 7，3 3

2、）线性分组码）线性分组码信息组信息组码字码字定义 二进制(n,k)线性分组码，是GF(2)域上的n维线性空间Vn中的一个k维子空间Vn,k。定理 一个(n,k)线性分组码中非零码字的最小重量等于C中的最小距离d0。信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理一、线性分组码的基本原理二、循环码的基本原理1、基本概念2、生成矩阵和一致校验矩阵3、线性分组码的译码及纠错能力4、汉明码简介信息论与编码基础信息论与编码基础线性分组码线性分组码信息论与编码基础信息论与编码基础线性分组码线性分组码典型矩阵典型矩阵+信息论与编码基础信息论与编码基础线性分组码线性分组码=生成矩阵

3、生成矩阵信息论与编码基础信息论与编码基础线性分组码线性分组码一致校验矩阵一致校验矩阵信息论与编码基础信息论与编码基础线性分组码线性分组码或或一致校验矩阵一致校验矩阵信息论与编码基础信息论与编码基础线性分组码线性分组码信息论与编码基础信息论与编码基础线性分组码线性分组码练习1）n=?，k=?2）求出该码的全部码字；3）求出该码的一致校验矩阵H0。信息论与编码基础信息论与编码基础线性分组码线性分组码如果把(n,k)码的一致校验矩阵看成是(n,r)码的生成矩阵，将(n,k)码的生成矩阵看成是(n,r)码的一致校验矩阵，则这两种码互为对偶。任何对偶码的码字相乘为0吗？对偶码对偶码思考题：思考题：设C为

4、数域F3=0,1,2中的一个线性分组码：请给出该码的所有码字，并给出一个校验矩阵。信息论与编码基础信息论与编码基础线性分组码线性分组码线性分组码基本概念线性分组码基本概念对偶码对偶码信息论与编码基础信息论与编码基础线性分组码线性分组码本课小结本课小结生成矩阵和一致校验矩阵生成矩阵和一致校验矩阵信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理一、线性分组码的基本原理二、循环码的基本原理1、基本概念2、生成矩阵和一致校验矩阵3、线性分组码的译码及纠错能力4、汉明码简介错误图样信息论与编码基础信息论与编码基础线性分组码线性分组码信息论与编码基础信息论与编码基础线性分组码线

5、性分组码 标准阵列译码标准阵列译码码字码字禁禁用用码码字字(000)陪集陪集首 标准阵列译码标准阵列译码信息论与编码基础信息论与编码基础线性分组码线性分组码例例1 1：（：（4 4，2 2）线性分组码）线性分组码 标准阵列译码标准阵列译码禁用禁用码组码组 1000 1111 0010 01010100 00111110 100100010110 1011 1100 信息论与编码基础信息论与编码基础线性分组码线性分组码 同一行中任意两个码矢量之和为同一行中任意两个码矢量之和为C中码字。中码字。标准阵列的同一行中没有两个标准阵列的同一行中没有两个n重矢量相同，重矢量相同，每个每个n重矢量在且仅在一

6、行出现。重矢量在且仅在一行出现。标准阵列译码标准阵列译码信息论与编码基础信息论与编码基础线性分组码线性分组码伴随式译码伴随式译码伴随式伴随式S S信息论与编码基础信息论与编码基础线性分组码线性分组码伴随式译码伴随式译码信息论与编码基础信息论与编码基础线性分组码线性分组码定理定理每个陪集全部个矢量都有相同的伴随式而不同陪集有不同的伴随式。信息论与编码基础信息论与编码基础线性分组码线性分组码伴随式译码伴随式译码例例2 2：（：（4 4，2 2）码的伴随式译码）码的伴随式译码 000000100010010011000101ESStep1：由R求SS=RHtStep2：由S求E令令E E(e3 e2

7、 e1 e0)，Step3：纠错 C=R+E信息论与编码基础信息论与编码基础线性分组码线性分组码伴随式译码伴随式译码S0R=(r3r2r1r0)r0r1r2r3伴随式译码伴随式译码S1c0c1c2c3e0e2e3串行输出串行输出C=R+E000000100010010011000101ES信息论与编码基础信息论与编码基础线性分组码线性分组码r0r1rn-1s0s1sr-1e0e1en-1c0c1cn-1（n，k）线性分组码一般译码电路）线性分组码一般译码电路S=RHtS=EHtC=R+E接收矢量缓存器接收矢量缓存器伴随式计算电路伴随式计算电路错误图样产生器错误图样产生器n级移位寄存器输出级移位

8、寄存器输出伴随式译码伴随式译码信息论与编码基础信息论与编码基础线性分组码线性分组码思考题思考题1 1：设C为数域F3=0,1,2中的一个线性分组码：利用伴随式译码对(1122),(2110),(2222)码字进行译码。000000100022010012000101ES001111100120101002020021001010信息论与编码基础信息论与编码基础线性分组码线性分组码思考题思考题2 2：信息论与编码基础信息论与编码基础线性分组码线性分组码考虑码率为1/2的（n,n/2）的线性分组码C，其生成矩阵为G。证明：如果则码C是自对偶码。你能构造出符合该条件的码吗？标准阵列译码（标准阵列译码

9、（陪集、译码步骤陪集、译码步骤）伴随式译码（伴随式译码（伴随式、译码过程伴随式、译码过程）信息论与编码基础信息论与编码基础线性分组码线性分组码本课小结本课小结信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理一、线性分组码的基本原理二、循环码的基本原理1、基本概念2、生成矩阵和一致校验矩阵3、线性分组码的译码及纠错能力4、汉明码简介例例 （7，3）码码信息论与编码基础信息论与编码基础线性分组码线性分组码定理定理任一(n,k)线性分组码若要纠正小于等于t个错误，其充要条件是H矩阵中任何2t列线性无关。定理定理(n,k)线性分组码最小距离等于的充要条件是H矩阵中任何列线性

10、无关。结论：1、上述定理是构造距离为d的任何类型线性分组码的基础2、H矩阵列排序不同，码集不同，但纠错能力不变3、d0 n k+1信息论与编码基础信息论与编码基础线性分组码线性分组码定理定理若C是k维n重二元码，当已知k时，要使C能纠正t个错，则必须有不少于r个校验位，且使r满足完备码完备码信息论与编码基础信息论与编码基础线性分组码线性分组码信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理一、线性分组码的基本原理二、循环码的基本原理1、基本概念2、生成矩阵和一致校验矩阵3、线性分组码的译码及纠错能力4、汉明码简介信息论与编码基础信息论与编码基础线性分组码线性分组码R

11、ichard Wesley Hamming美国数学家提出汉明码、汉明窗、汉明数、球填充、汉明距离等重要概念和方法。l1980年被评为美国国家工程学院院士；l1986年IEEE设立以其名字命名的Richard W.Hamming奖，奖励对信息科学、系统和技术作出杰出贡献的人。1、汉明码的结构、汉明码的结构码长信息位数监督码位最小码距纠错能力信息论与编码基础信息论与编码基础线性分组码线性分组码信息论与编码基础信息论与编码基础2、扩展汉明码、扩展汉明码(7,4)汉明码(8,4)扩展汉明码线性分组码线性分组码信息论与编码基础信息论与编码基础3、从已知线性分组码来构造新的线性分组码、从已知线性分组码来构

12、造新的线性分组码2）凿孔码将线性分组码中所有码字的某些校验位删除。3）除删码将线性分组码中一部分码字删除。4）增广码与除删码对应。5）延长码 原码 增广 扩展。线性分组码线性分组码1）缩短码缩短线性分组码的信息位。信息论与编码基础信息论与编码基础扩展汉明码(2r,2r-1-r,4)偶重量码字构成的子码(2r-1,2r-2-r,4)汉明码(2r-1,2r-1-r,3)通过增加全校验位来扩展在全校验位上凿孔延长缩短 除删丢弃奇重码字通过加入全“1”分量来增广线性分组码线性分组码3、从已知线性分组码来构造新的线性分组码、从已知线性分组码来构造新的线性分组码信息论与编码基础信息论与编码基础线性分组码的

13、纠错能力线性分组码的纠错能力（d0 与与 H的关系）的关系）汉明码汉明码（完备性，码结构（完备性，码结构）本课小结本课小结构造新的线性分组码的方法构造新的线性分组码的方法线性分组码线性分组码信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理二、循环码的基本原理二、循环码的基本原理1、基本概念2、循环码的编码3、循环码的一般译码方法4、循环汉明码及其派生码p多项式多项式零多项式:各次系数均为0的多项式首一多项式：最高次系数为1的多项式信息论与编码基础信息论与编码基础线性分组码线性分组码p汉明码汉明码(7,4)汉明码码字(0000000)(0001011)(0010110

14、)(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)信息论与编码基础信息论与编码基础线性分组码线性分组码信息论与编码基础信息论与

15、编码基础100010110001010001011001011001011001011000011000111000100100111100111000111010111010111010011010011010011010011111111110000000p循环汉明码循环汉明码信息论与编码基础信息论与编码基础线性分组码线性分组码p码多项式码多项式信息论与编码基础信息论与编码基础线性分组码线性分组码生成多项式定理定理一个二进制(n,k)循环码中有唯一的非零最低次多项式，且常数项为1。p生成多项式生成多项式信息论与编码基础信息论与编码基础线性分组码线性分组码例子例例GF(2)上多项式构造一个（

16、7，3）循环码。码多项式码多项式码码 字字（0010111）（0101110）（1011100）（0111001）（1110010）（1100101）（1001011）（0000000）只要知道了xn+1的因式分解，用它的各个因式的乘积，便能得到很多个不同的循环码。p生成矩阵和一致校验矩阵生成矩阵和一致校验矩阵信息论与编码基础信息论与编码基础线性分组码线性分组码校验矩阵校验矩阵校验矩阵例子例例系统码情况系统码情况信息论与编码基础信息论与编码基础线性分组码线性分组码q例例 已知（7，4）系统码的生成多项式为求生成矩阵。信息论与编码基础信息论与编码基础线性分组码线性分组码码多项式、生成多项式码多项

17、式、生成多项式生成矩阵和一致校验矩阵生成矩阵和一致校验矩阵信息论与编码基础信息论与编码基础线性分组码线性分组码本课小结本课小结循环码的特点循环码的特点信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理二、循环码的基本原理二、循环码的基本原理1、基本概念2、循环码的编码3、循环码的一般译码方法4、循环汉明码及其派生码信息论与编码基础信息论与编码基础p多项式除法电路线性分组码线性分组码信息论与编码基础信息论与编码基础例例线性分组码线性分组码D0D1D2+x3x1p循环码编码电路循环码编码电路信息论与编码基础信息论与编码基础1、n-k级编码器级编码器2、k级编码器级编码器k

18、个个信元信元校验位校验位线性分组码线性分组码例例生成多项式的二进制（7，4）汉明码节拍节拍 信息位信息位输出码字输出码字0000111110200011300111411011500116000170000Cn-kCn-k+1Cn-2Cn-1h0h1hk-2hk-1信息论与编码基础信息论与编码基础循环码的循环码的k级编码器级编码器线性分组码线性分组码信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理二、循环码的基本原理二、循环码的基本原理1、基本概念2、循环码的编码3、循环码的一般译码方法4、循环汉明码及其派生码信息论与编码基础信息论与编码基础p伴随式计算和错误的检测

19、线性分组码线性分组码伴随式计算信息论与编码基础信息论与编码基础p伴随式计算电路性质及一般译码器伴随式特点定理定理若 是 的伴随式，则 循环移位 （在模 运算下）的伴随式，是在伴随式计算电路中无输入时（自发运算）右移一位的结果，即线性分组码线性分组码定理定理的伴随式而任意多项式乘所对应的伴随式p伴随式计算电路性质及一般译码器伴随式特点信息论与编码基础信息论与编码基础线性分组码线性分组码例子例例二进制（7，4）循环汉明码，输入输入缓存缓存 译码译码0 0 011 0 000 1 000 0 101 1 000 1 110 1 110 1 110000111 1 11 0 110100110 0 0

20、信息论与编码基础信息论与编码基础(7,4)码完整译码器线性分组码线性分组码信息论与编码基础信息论与编码基础循环码的通用译码器循环码的通用译码器门门k 级级缓存器缓存器伴随式计算电路伴随式计算电路1 1伴随式计算电路伴随式计算电路2 2组合逻辑电路组合逻辑电路输入输入R(x)输出输出纠纠错错信信号号线性分组码线性分组码信息论与编码基础信息论与编码基础线性分组码线性分组码一、线性分组码的基本原理二、循环码的基本原理二、循环码的基本原理1、基本概念2、循环码的编码3、循环码的一般译码方法4、循环汉明码及其派生码信息论与编码基础信息论与编码基础p循环汉明码线性分组码线性分组码既约多项式：如果多项式f(

21、x)除了常数和它本身以外，不能再被GF(q)的其他多项式除尽，则称f(x)是GF(q)上的既约多项式。本原多项式：若m次既约多项式f(x)除尽xn+1的最小正整数n满足n=2m-1，则称该多项式为本原多项式。由m次本原多项式g(x)生成的长度2m-1(m3)的循环码是(2m-1,2m-1-m)汉明码。0000000000101100101100011101010110001001110110001011101010001011001110101001110110001110100110100111000101111111p缩短循环码线性分组码线性分组码信息论与编码基础信息论与编码基础缩短循环码字已经不再具有循环特性。信息论与编码基础信息论与编码基础p缩短循环码线性分组码线性分组码与门输出输入RD0D1D2D310级移位寄存器信息论与编码基础信息论与编码基础p删信循环码线性分组码线性分组码信息论与编码基础信息论与编码基础循环码编码电路循环码编码电路 循环码译码电路循环码译码电路线性分组码线性分组码本课小结本课小结循环汉明码、缩短码、删信码循环汉明码、缩短码、删信码信息论与编码基础信息论与编码基础作业：习题六:3,4,5,12,17、18线性分组码线性分组码