通信原理AII第5次课教案(2011).doc

10.4 循环码 循环码是线性分组码中最重要的一个子类。 循环码除了具有线性分组码的封闭性外，还具有一个独特的特点：循环性。所谓循环性是指：一个循环码中每个码组经任意循环移位之后，仍然是一个码组。表10.4.1给出了一种（7，3）循环码的全部码组。其中，全零码组自身形成一个封闭的自我循环，其余码组形成一个周期为循环环。可见，循环码是指它的任一码组循环移位后仍然是码组，而不是所有码组都可由一个码组循环而得。表10.4.1 （7，3）循环码的全部码组码组编号信息位编码码组码组编号信息位编码码组 1 2 3 4 000 001 010 01100000000010111010111001110015678 100101110111 1001011 1011100 1100101 1110010 循环码的这一外在特点，给循环码的编译码实现带来了便利。目前，实用差错控制系统中所使用的线性分组码几乎都是循环码或循环码的子类(如BCH等)。10.4.1 循环码的多项式描述 1. 码多项式 定义：码组A = 的码多项式为 （10.4.1）例如，码组A =（1100101）可以表示为。在码多项式中，的幂次指示码元的位置，其系数代表码元的取值。因此，我们并不关心本身的值。 2. 码多项式的按模运算 在码多项式运算中也有类似的按模运算。若一任意多项式被一次多项式除，得到商式和一个次数小于的余式，即 （10.4.2）或 （10.4.3）则在模运算下 （10.4.4）这里，码多项式系数仍按模2运算，即只取值0和1。例10.4.1 被除，求余式。解 用长除法 注意，由于在模2运算中，用加法代替了减法，故余式不是而是。 3. 循环码多项式的模运算 把一个码组表示成码多项式的形式后，循环码的循环特性可按如下方式表示。 将码组A = 的循环移位记为 则它们各自对应的码多项式分别是 于是有 （10.4.5）证明：将乘以得到 例10.4.2 在表10.4.1中（7，3）循环码的第7个码组的码多项式为 请写出左循环移位3次的码组。解 , 用长除法求余式 其对应的码组为0101110，它是表10.4.1中第3个码组。 由上述分析看出，在循环码理论中，多项式非常重要。10.4.2 循环码的生成多项式与生成矩阵 对于表10.4.1所给出的（7，3）循环码，按线性分组码生成矩阵特性(2)，得到其生成矩阵为 或 （10.4.6） 可见，在循环码中，生成矩阵G可以由一个元素（码多项式）及其循环移位构成，这个元素叫做该循环码的生成多项式。因此，求循环码生成矩阵G可进一步简化为求码的生成多项式。 1. 循环码生成多项式定义 循环码生成多项式是所有码多项式中除0多项式以外，次数最低的码多项式。例如，在表10.4.1所给出的（7，3）循环码中，第2个码组0010111对应的码多项式即为生成多项式。 2. 循环码生成多项式特性 循环码生成多项式具有以下特性： (1)的常数项不为零。 (2) 是唯一的，即码多项式集合中除0多项式以外次数最低的多项式只有一个。(3) 循环码的每一码多项式都是的倍式，这意味着，次数小于次的一定是码组。即 （10.4.7）换句话说，一定可以整除所有码多项式。(4) 的次数是。(5) 是的一个因子。 例如，在表10.4.1所给出的（7，3）循环码中：(1) 生成多项式的常数项是1。(2) 码组0010111是除全零码组外，所有码组中高位连0最多的码组，所对应的码多项式的次数最低。(3) 编号为5的码组所对应的码多项式可以表示为 可见，利用关系式求出的码组并不一定是系统码。(4) 生成多项式的次数是。(5) 生成多项式是的一个因子，即有3. 循环码的生成矩阵 将式（10.4.8）推广到一般情况，循环码的生成矩阵G可以写成 （10.4.8） 式中，生成多项式。 一般来说，直接利用式（10.4.8）或式（10.4.7）求出的码组并不是系统码。10.4.3 系统循环码编码例10.4.3 用线性反馈移存器实现表10.4.1中(7,3)系统循环码。解：1. 编码原理按前面的约定，系统码的码组中左边位是信息位，其余位是监督位。系统循环码编码步骤如下：(1) 用乘信息码多项式。例如，信息码为110，它相当于，当时，相当于1100000，使信息位移至码组的最左边3位。(2) 再用生成多项式除，得余式。即例如，得余式，相当于101。(3) 编出码组。例如，是表10.4.1中第7个码组。证明是一循环码多项式。证：用生成多项式除，得 （10.4.9）其中，余式。在式（10.4.11）两边同时加上（模2加）余式，可得 （10.4.10）不难看出，式（10.4.10）是一个小于次的的倍式，由生成多项式特性(3)可知 （10.4.11）是一循环码多项式。2. 编码电路 (1) 编码器结构表10.4.1中(7,3)系统循环码的生成多项式是，由其决定的编码电路如图10.4.1所示。图10.4.1 (7,3)系统循环码的编码电路图10.4.1中，作为编码器主体的是由一些移存器和模2加法器组成的除法电路（计算除以的余数），其结构由生成多项式来确定： 移存器个数为的幂次数； 移存器输出端有无模2加法器取决于中系数的值： ，有； ，没有。 (2) 编码器工作原理 设各级移存器初始化为零（清空移存器）。 门1开、门2关，当信息位输入时，一方面送入除法器进行运算，另一方面直接输出； 当输入完位信息后，门1关、门2开，移存器中存储的是被除后的余项； 将余项依次取出，同时清空移存器。例如，当信息时，输出码组。编码器工作过程如下：输入序列 时钟节拍 反馈 移存器内容 输出0000011 0 0 0000 000001 1 1 1110 1 00000 2 1 1001 1 0000 3 1 1010 0 000 4 0 0101 0 00 5 0 0010 1 0 6 0 0001 0 7 0 0000 110.4.4 循环码译码下面，以梅吉特译码器（Meggit,1961）为例，介绍一种循环码的纠错译码方法。例10.4.4 已知二进制(7,3)循环码生成多项式为，梅吉特译码电路图10.4.2所示，说明其译码过程。图10.4.2 (7,3)循环码梅吉特译码电路 解：图10.4.2是对应例10.4.3 的(7,3)循环码译码器。1. 梅吉特译码电路的组成(1) 校正子计算电路除法电路实现校正子计算和校正子循环移位。 计算校正子 循环码校正子定义式为 （10.4.12）即，定义循环码的校正子是接收码除以生成多项式后的余式。 校正子循环移位 令为接收码组循环移位次后计算得到的校正子，即 则循环码具有如下特性： （10.4.13）上式表明：某码组循环移位次的校正子等于原码组校正子在除法电路中循环移位次所得的结果。例如，表10.4.2中的校正子是循环移位1次得结果，即有 得。(2) 错误图样检测器 梅吉特译码器是基于错误图样检测（识别）的译码器，它根据校正子找到错误图样，并通过模2加法器与存储在缓存器中的循环码相“异或”，来纠正接收码组中的可纠正错误。由表10.4.1不难看出，(7,3)循环码的最小码距，故可纠正一位错码。可纠正的错误图样有7个，它们与校正子的对应关系如表10.4.2所列。表10.4.2 校正子与错误图样的对应关系校正子S（dcba）可纠正错误图样E1011111001111000010000100001 1000000 0100000 0010000 0001000 0000100 0000010 00000012. 梅吉特译码电路工作原理设发送码组为1100101，并假定在传输过程中第2位（码组左边第2位）码元发生错误，于是接收到的码组为1000101。 当接收码组时，由式（10.4.12）得 即校正子，相当于。此时，错误图样检测器输出“0”码，对存储在缓存器中接收码组的第1位 。 校正子在除法电路中循环移位1次，有得校正子或。此时，错误图样检测器输出“1”码，通过模2加法器与存储在缓存器中接收码组第2位“0”码相“异或”，从而纠正接收码组中的第2位错码。由例10.4.4可见，利用式（10.4.14）的循环码特性，可以使错误图样检测电路大为简化。错误图样检测器只要能识别一个可纠正错误图样，就能检测出加循环后的其他同类错误图样。按错误图样检测器的输入输出逻辑关系，本例中识别的错误图样是（1000000），即当错误图样检测电路的输入校正子为时，检测出的错误图样是。 10.4.5 缩短循环码缩短循环码是在循环码的个码组中挑选出前个信息位均为0值的码组（有个这样的码组）作为缩短循环码的码组。 例10.4.6 某（7,4）系统循环码的生成矩阵和监督矩阵分别为 和 将它缩短为（5,2）缩短循环码。解：利用生成多项式可以产生（7,4）系统循环码的整个码组，见表10.4.3。（5,2）码即（7-2,4-2），由（7,4）码缩短2而来。在表10.4.3中挑选出前2个信息位均为0值的码组，可得（5,2）全部（4个）缩短循环码码组，它们是（00000），（01011），（10110），（11101）。表10.4.3 (7,4)系统循环码码组编号编码码组码组编号编码码组1234567800000000001011001011000111010100111010110001100010111010 910111213141516 1000101 1001110 1010011 1011000 1100010 1101000 1110100 1111111与（7，4）码47的生成矩阵相比，（5，2）缩短码的生成矩阵变为25，少了2行2列。去除矩阵的最上边2行和最左边2列，即得缩短循环码的生成矩阵。 由信息组可能的4种组合（00），（10），（01），（11）与相乘也可以得到全部（4个）缩短循环码码组。缩短循环码具有下列特性： 缩短循环码的码集是循环码码集的子集，因此它的码组也一定能被除尽。 对于缩短循环码而言，任意码组的循环移位不再一定是码组，它已失去了循环码的外部特性，不是典型意义上的“循环”码了。 由于缩短循环码是挑选前个信息位均为0值的码组，删去前位而缩短的，在此过程中没有删除过“1”，因此缩短后的码组重量即不变，于是缩短循环码的纠错能力与原循环码相同，只是编码效率降低了。10.4.6 循环冗余校验码循环冗余校验码简称CRC码，是一种缩短循环码。循环冗余校验码的“循环”表现在是循环码生成多项式，“冗余”表现为校验位长度一定（与原循环码的校验位为相同，即）。既然是循环码，应有,即是的因子，一旦固定，则也固定，或只有很少几种取值。但在帧校验的实际应用中，帧长是不定的，而且可能连续变化。所以工程应用的CRC码并不是按设计的原始的循环码，而是该码的缩短码。即先设计循环码，再缩短任意位而得到CRC码。如例10.4.7中，（10,6）缩短循环码是（15,11）循环码缩短4位而得到的CRC码。CRC码一般采用系统码的形式，广泛应用于帧校验（检错码），CRC码的结构如图10.4.3所示。从差错控制编码角度来看，整个位帧（或称分组、信元、单元、包等）就是一个码组，习惯上仅把校验位部分称为CRC码。 图10.4.3 循环冗余校验码（CRC）结构例10.4.7 某CRC码的生成多项式。如果想发送一串信息110001的前6位并加上CRC校验，发送码应如何安排？接收码如何检验？解 本题,信息多项式,即，因此得。对于系统循