信息论与编码基础-教学课件

信息论与编码基础线性分组码一、线性分组码的基本原理二、循环码的基本原理1、基本概念2、生成矩阵和一致校验矩阵3、线性分组码的译码及纠错能力4、汉明码简介编码器信息序列码元序列信息论与编码基础线性分组码例（7，3）线性分组码信息组码字定义二进制(n,k)线性分组码，是GF(2)域上的n维线性空间Vn中的一个k维子空间Vn,k。定理一个(n,k)线性分组码中非零码字的最小重量等于[C]中的最小距离d0。信息论与编码基础线性分组码信息论与编码基础线性分组码典型矩阵+++++信息论与编码基础线性分组码=生成矩阵信息论与编码基础线性分组码一致校验矩阵信息论与编码基础线性分组码或一致校验矩阵信息论与编码基础线性分组码信息论与编码基础线性分组码练习1）n=?，k=?2）求出该码的全部码字；3）求出该码的一致校验矩阵H0。信息论与编码基础线性分组码如果把(n,k)码的一致校验矩阵看成是(n,r)码的生成矩阵，将(n,k)码的生成矩阵看成是(n,r)码的一致校验矩阵，则这两种码互为对偶。任何对偶码的码字相乘为0吗？对偶码思考题：设C为数域F3={0,1,2}中的一个线性分组码：请给出该码的所有码字，并给出一个校验矩阵。信息论与编码基础线性分组码线性分组码基本概念对偶码信息论与编码基础线性分组码本课小结生成矩阵和一致校验矩阵基本思想错误图样信息论与编码基础线性分组码信息论与编码基础线性分组码标准阵列译码码字禁用码字(00…0)陪集陪集首标准阵列译码信息论与编码基础线性分组码例1：（4，2）线性分组码标准阵列译码译码表：禁用码组100011110010010101000011111010010001011010111100信息论与编码基础线性分组码标准阵列的特点：同一行中任意两个码矢量之和为[C]中码字。标准阵列的同一行中没有两个n重矢量相同，每个n重矢量在且仅在一行出现。标准阵列译码信息论与编码基础线性分组码伴随式译码伴随式S信息论与编码基础线性分组码伴随式译码信息论与编码基础线性分组码定理每个陪集全部个矢量都有相同的伴随式而不同陪集有不同的伴随式。信息论与编码基础线性分组码伴随式译码例2：（4，2）码的伴随式译码

000000100010010011000101ESStep1：由R求SS=RHtStep2：由S求E令E＝(e3e2e1e0)，Step3：纠错

C=R+E信息论与编码基础线性分组码伴随式译码S0R=(r3r2r1r0)r0r1r2r3伴随式计算伴随式译码S1c0c1c2c3e0e2e3串行输出错型产生C=R+E^000000100010010011000101ES信息论与编码基础线性分组码r0r1rn-1s0s1sr-1e0e1en-1c0c1cn-1（n，k）线性分组码一般译码电路S=RHtS=EHt^C=R+E接收矢量缓存器伴随式计算电路错误图样产生器n级移位寄存器输出伴随式译码信息论与编码基础线性分组码思考题1：设C为数域F3={0,1,2}中的一个线性分组码：利用伴随式译码对(1122),(2110),(2222)码字进行译码。000000100022010012000101ES001111100120101002020021001010信息论与编码基础线性分组码思考题2：信息论与编码基础线性分组码考虑码率为1/2的（n,n/2）的线性分组码C，其生成矩阵为G。证明：如果则码C是自对偶码。你能构造出符合该条件的码吗？标准阵列译码（陪集、译码步骤）伴随式译码（伴随式、译码过程）信息论与编码基础线性分组码本课小结例（7，3）码信息论与编码基础线性分组码定理任一(n,k)线性分组码若要纠正小于等于t个错误，其充要条件是H矩阵中任何2t列线性无关。定理(n,k)线性分组码最小距离等于的充要条件是H矩阵中任何列线性无关。结论：1、上述定理是构造距离为d的任何类型线性分组码的基础2、H矩阵列排序不同，码集不同，但纠错能力不变3、d0≤n–k+1信息论与编码基础线性分组码定理若[C]是k维n重二元码，当已知k时，要使[C]能纠正t个错，则必须有不少于r个校验位，且使r满足完备码信息论与编码基础线性分组码信息论与编码基础线性分组码一、线性分组码的基本原理二、循环码的基本原理1、基本概念2、生成矩阵和一致校验矩阵3、线性分组码的译码及纠错能力4、汉明码简介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)信息论与编码基础线性分组码信息论与编码基础100010110001010001011001011001011001011000011000111000100100111100111000111010111010111010011010011010011010011111111110000000循环汉明码信息论与编码基础线性分组码码多项式信息论与编码基础线性分组码生成多项式定理一个二进制(n,k)循环码中有唯一的非零最低次多项式，且常数项为1。定理生成多项式信息论与编码基础线性分组码例子例GF(2)上多项式构造一个（7，3）循环码。码多项式码字（0010111）（0101110）（1011100）（0111001）（1110010）（1100101）（1001011）（0000000）只要知道了xn+1的因式分解，用它的各个因式的乘积，便能得到很多个不同的循环码。生成矩阵和一致校验矩阵…………………信息论与编码基础线性分组码校验矩阵校验矩阵……………例子例系统码情况信息论与编码基础线性分组码例

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

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

是

的伴随式，则

循环移位

（在模运算下）的伴随式，是在伴随式计算电路中无输入时（自发运算）右移一位的结果，即线性分组码定理的伴随式而任意多项式乘所对应的伴随式伴随式计算电路性质及一般译码器伴随式特点信息论与编码基础线性分组码例子例二进制（7，4）循环汉明码，输入缓存译码000110000100001011000111011101110000111111011010011000信息论与编码基础(7,4)码完整译码器线性分组码信息论与编码基础循环码的通用译码器门k级缓存器伴随式计算电路1伴随式计算电路2组合逻辑电路—输入R(x)输出纠错信号线性分组码信息论与编码基础线性分组码一、线性分组码的基本原理二、循环码的基本原理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)汉明码。0000000000101100101100011101010110001