数字通信原理第9次课课件(2015)

11.复习(1)线性分组码线性分组码定义和性质，生成矩阵特性，监督矩阵特性，线性分组码的译码，汉明码。①线性分组码定义kn,线性分组码是把信息码元序列的每k个码元分成一组，通过线性变换，映射成由n个码元组成的码组（码字）。②线性分组码的性质·一个kn,线性分组码共有k2个（许用）码组；·对加法满足封闭性；·全零码是线性分组码中的一个码组；·线性分组码的最小码距等于除全零码外的码组的最小重量。③生成矩阵特性：·生成矩阵可以产生整个码组，即A=mG；·生成矩阵的各行本身就是一个码组，并且它们是线性无关的；·典型生成矩阵具有如下的形式：G=QIk，并且由典型生成矩阵得出的码组称为系统码。④监督矩阵特性：·0TAH；·典型监督矩阵具有如下的形式：HrIP；·生成矩阵G与监督矩阵H可以互相转换，即TPQ或TQP。⑤译码过程a)利用式TSBH，计算校正子；b)解方程TEHS，求出Eˆ；2·当校正子的组合数目不少于可纠正错误图样的数目时，S与E之间一一对应（参见例10.3.2）；·若方程TEHS有多解（解E是不唯一），则可以运用概率译码的处理方法选择错误图样的估值。c)由EBA求出发送码组估值ˆA。(2)汉明码①汉明码是一类能纠正单个随机错误的线性分组码。②二进制汉明码应满足条件：nkn12，因此，汉明码的校正子TBHS和可纠正错误图样E是一一对应的，即式TEHS中的S与E之间一一对应。③线性分组码中（7，4），（15，11），（31，26），（63，57），（127，120），（255，247），…是汉明码④n个单个错误的校正子就是监督矩阵H矩阵的每一列。2.本次课学习的主要内容10.4循环码310.4循环码·循环码是线性分组码中最重要的一个子类。目前，实用差错控制系统中所使用的线性分组码几乎都是循环码或循环码的子类(如BCH等)。·循环码除了具有线性分组码的封闭性外，还具有一个独特的特点：循环性。循环码的这一外在特点，给循环码的编译码实现带来了便利。·所谓循环性是指：一个kn,循环码中每个码组经任意循环移位之后，仍然是一个码组。表10.4.1给出了一种（7，3）循环码的全部码组。其中，全零码组自身形成一个封闭的自我循环，其余码组形成一个周期为7n循环环。可见，循环码是指它的任一码组循环移位后仍然是码组，而不是所有码组都可由一个码组循环而得。表10.4.1（7，3）循环码的全部码组码组编号信息位编码码组码组编号信息位编码码组123400000101001100000000010111010111001110015678100101110111100101110111001100101111001010.4.1循环码的多项式描述1.码多项式定义：码组A=011,,,aaan的码多项式为0111axaxaxTnn（10.4.1）例如，码组A=（1100101）可以表示为1256xxxxT。在码多项式中，x的幂次指示码元的位置，其系数代表码元的取值。因此，我们并不关心x本身的值。2.码多项式的按模运算若一任意多项式xF被一n次多项式xN除，得到商式xQ和一个次数小于n的余式xR，即xNxRxQxNxF（10.4.2）或xRxQxNxF（10.4.3）则在模xN运算下4xNxRxFmod（10.4.4）这里，码多项式系数仍按模2运算，即只取值0和1。例10.4.1124xx被13x除，求余式。解用长除法注意，由于在模2运算中，用加法代替了减法，故余式不是12xx而是12xx。111132324xxxxxxx1mod113224xxxxx3.循环码多项式的模运算把一个码组表示成码多项式的形式后，循环码的循环特性可按如下方式表示。将码组A=011,,,aaan的循环移位i记为innininniniaaaaaaaaA,,,,,,,10111101则它们各自对应的码多项式分别是0111axaxaxTnninininiaxaxaxT011于是有1modniixxTxTx（10.4.5）证明：将xT乘以ix得到121121inininnnnninixTxaxaxaxaxiixaxa011ninininxaxaxa111iininxaxaxa01111inininaxaxa111inininaxaxa1111111ninininixaxaxaxT1modnixxT5例10.4.2在表10.4.1中（7，3）循环码的第7个码组7A的码多项式为1256xxxxT请写出7A左循环移位3次的码组。解7n,3i358925631xxxxxxxxxTxi用长除法求余式1mod72353xxxxxxTx其对应的码组为0101110，它是表10.4.1中第3个码组。由上述分析看出，在循环码理论中，1nx多项式非常重要。10.4.2循环码的生成多项式与生成矩阵对于表10.4.1所给出的（7，3）循环码，按线性分组码生成矩阵特性(2)，得到其生成矩阵为001011101011101011100G或11112424242242352346xxxxxxxxxxxxxxxxxxxxxxGxgxxgxgx2（10.4.6）可见，在循环码中，生成矩阵G可以由一个元素xg（码多项式）及其循环6移位构成，这个元素叫做该kn,循环码的生成多项式。因此，求循环码生成矩阵G可进一步简化为求码的生成多项式xg。1.循环码生成多项式定义循环码生成多项式xg是所有码多项式xT中除0多项式以外，次数最低的码多项式。例如，在表10.4.1所给出的（7，3）循环码中，第2个码组0010111对应的码多项式124xxx即为生成多项式。2.循环码生成多项式特性循环码生成多项式xg具有以下特性：(1)xg的常数项不为零。(2)xg是唯一的，即码多项式集合中除0多项式以外次数最低的多项式只有一个。(3)循环码的每一码多项式都是xg的倍式，这意味着，次数小于n次的xgxm一定是码组。即xgxmxT（10.4.7）换句话说，xg一定可以整除所有码多项式xT。例如，设12xxm，生成多项式仍为124xxxxg，则有11136242xxxxxxxxgxmxT查表10.4.1可知，它是编号为5的码组所对应的码多项式，而不是编号为6的码组所对应的码多项式。可见，利用关系式Txmxgx求出的码组并不一定是系统码。(4)xg的次数是kn。(5)xg是1nx的一个因子。例如，在表10.4.1所给出的（7，3）循环码中，生成多项式421gxxxx7是17x的一个因子，即有7342111xxxxxx3.循环码的生成矩阵将式（10.4.6）推广到一般情况，kn,循环码的生成矩阵G可以写成xgxxgxgxxgxxGkk21（10.4.8）式中，生成多项式1111xgxgxxgknknkn。一般来说，直接利用式（10.4.8）或式（10.4.7）求出的码组并不是系统码。10.4.3系统循环码编码例10.4.3用线性反馈移存器实现表10.4.1中(7,3)系统循环码。解：1.编码原理编出所谓的系统循环码，要求码组的前k位原封不动地照搬信息位，而后面kn位为监督位，也就是説，希望码多项式具有如下形式：xrxmxxTkn（10.4.9）其中，0111mxmxmxmkk为信息码多项式，xr是与码组中kn个监督位相对应的1kn次多项式，并且是生成多项式xg除xmxkn的余式。这里需要证明xrxmxxTkn是一循环码多项式。证明xrxmxxTkn是一循环码多项式。证：用生成多项式xg除xmxkn，得8xrxgxqxmxkn（10.4.10）其中，余式0111rxrxrxrknkn。在式（10.4.9）两边同时加上（模2加）余式xr，可得xgxqxrxmxkn（10.4.11）不难看出，式（10.4.10）是一个小于n次的xg的倍式，由生成多项式特性(3)可知xrxmxxTkn是一循环码多项式。2.编码步骤根据上述原理，获得一个产生系统循环码的方法，具体步骤为：(1)用knx乘xm，以使信息位移至码组的最左边k位。例如，信息码为110，它相当于2mxxx，当734nk时，4265nkxmxxxxxx相当于1100000，使信息位移至码组的最左边3位。(2)为了得到监督位，用生成多项式xg除xmxkn得余式xr。例如，652242421111xxxxxxxxxxx得余式21rxx，相当于0101。(3)编出码组xrxmxxTkn。例如，11000001011100101Tx，是表10.4.1中第7个码组。3.编码电路(1)编码器结构表10.4.1中(7,3)系统循环码的生成多项式是124xxxxg，由其决定的编码电路如图10.4.1所示。图10.4.1(7,3)系统循环码的编码电路4g2g1g0g输入输出abcd门2门1或门9图10.4.1中，作为编码器主体的是由一些移存器和模2加法器组成的除法电路（计算xmxkn除以xg的余数），其结构由生成多项式124xxxxg来确定：①移存器个数为xg的幂次数4nk；②移存器输出端有无模2加法器取决于xg中系数1,,1igink的值：121gg，有；30g，没有。(2)编码器工作原理设各级移存器初始化为零（清空移存器）。①门1开、门2关，当信息位输入时，一方面送入xg除法器进行运算，另一方面直接输出；②当输入完k位信息后，门1关、门2开，移存器中存储的是xmxkn被xg除后的余项；③将余项依次取出，同时清空移存器。例如，当信息110m时，输出码组1100101A。编码器工作过程如下：输入序列m时钟节拍反馈移存器内容abcd输出f0000011000000—0000011111101000002110011mf0000311010000040010100050001011ef06000010—70000011010.4.4循环码译码循环码校正子定义式为xgxBxSmod（10.4.12）即，定义循环码的校正子xS是接收码xB除以生成多项式xg后的余式。显然，若接收码xB等于发送码xA，则校正子0xS。10.4.6循环冗余校验码循环冗余校验码简称CRC码，是一种缩短循环码。由于缩短，CRC码失去了循环码外部的循环特性，但循环码的内在特性依然存在，其纠错能力可以通过循环码来分析，编译码电路也可利用循环码来实现。CRC码一般采用系统码的形式，广泛应用于帧