线性分组码..

线性分组码线性分组码.2 线性分组码 线性:监督码元与信息码元满足线性关系(n,k)分组码（an-1an-2an-3a0）以下将以 汉明码 为例引入线性分组码一般原理。汉明码是一种用来纠正单个错误的线性分组码。构造原理在偶数监督码中，一位监督位a0，和信息位构成关系式：在接收端解码时，实际上就是在计算监督关系式校正子S=0，认为无错码；S=1，就认为有错码。若监督位增加一位，两个校正子的可能值有4种组合：00，01，10，11，故能表示4种不同信息。1种表示无错其余3种能指示1位错码 若有r个校正子，则可指示1位错误的(2r 1)个可能位置。码长为 n，信息位数为 k，则监督位 rnk。指示1位错码的 n 种可能位置，要求 设分组码设分组码(n,k)中中k=4，为了，为了纠正纠正1位错码，监位错码，监督位需要多少位？督位需要多少位？监督位数监督位数 r 3若取若取 r=3，则，则n=k+r=7码组：（a6 a5 a4 a3 a2 a1 a0)监督位信息位假设校正子与错码位置的对应关系如表规定(也可以另外规定)。S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错码无错码 仅当仅当一位错码一位错码在在a2、a4、a5或或a6时，校正子时，校正子S1为为1,偶数监督关系偶数监督关系a1、a3、a5和和a6构成偶数监督关系：构成偶数监督关系：a0、a3、a4和和a6构成偶数监督关系：构成偶数监督关系：如何构造监督关系式？监督位监督位a2、a1和和a0应根据信息位的取值按监督关系来确定，即应根据信息位的取值按监督关系来确定，即监督位应使监督位应使S1、S2和和S3的值为的值为0:上式经过移项运算，解出监督位上式经过移项运算，解出监督位信息位a6 a5 a4 a3监督位a2 a1 a0信息位a6 a5 a4 a3监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111给定信息位后，可以直接按上式算出监督位给定信息位后，可以直接按上式算出监督位接收端接收端收到每个码组后，先按照约定计算出收到每个码组后，先按照约定计算出S1、S2和和S3，再，再查表判断错码情况。查表判断错码情况。例如：若接收码组为例如：若接收码组为1101100按监督式计算可得：按监督式计算可得：S1=1，S2=1，S3=0。查表可知在查表可知在a5位有位有1错码。错码。码效率：码效率：k/n=(n-r)/n=1 r/n，当当n很大和很大和r很小时，码率接近很小时，码率接近1。汉明码是一种高效码。汉明码是一种高效码。按照上述方法构造的码称为按照上述方法构造的码称为汉明码汉明码。表中所列的表中所列的(7,4)汉明码的最小码距汉明码的最小码距d0=3。这种码能够纠正这种码能够纠正1个错码或检测个错码或检测2个错码。个错码。S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错码无错码信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111 线性分组码的一般原理线性分组码的一般原理线性分组码的构造线性分组码的构造H矩阵矩阵上面上面(7,4)汉明码的例子有汉明码的例子有改写为改写为上式中已经将上式中已经将“”简写成简写成“+”。矩阵形式矩阵形式H称为称为监督矩阵监督矩阵。只要监督矩阵只要监督矩阵 H 给定，编码时监督位给定，编码时监督位和信息位的关系就完和信息位的关系就完全确定了。全确定了。简记为简记为H AT=0T 或或 A HT=0H矩阵矩阵ATH矩阵（矩阵（r行行n列）的性质：列）的性质：1)H 的行数就是监督关系式数，等于监督位数的行数就是监督关系式数，等于监督位数 r。每行中每行中“1”的位置表示监督关系。的位置表示监督关系。H 矩阵可以分成两部分矩阵可以分成两部分P 为为 r k 阶矩阵，阶矩阵，Ir为为r r阶单位方阵。阶单位方阵。我们将具有我们将具有P Ir形式的形式的H矩阵称为矩阵称为典型阵典型阵。G矩阵：汉明码例子中的监督位公式为可以改写成转置得到信息位的行矩阵乘矩阵Q 就产生出监督位K行行r列列Q=PTP在Q矩阵的左边再加上一个kk的单位矩阵，就形成了一个新矩阵G：典型形式生成矩阵K行n列G称为生成矩阵具有Ik Q形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码称 系统码。由生成矩阵由生成矩阵G及信息位可以产生整个码组及信息位可以产生整个码组线性分组码例【1】已知线性分组码的生成矩阵为 求（1）求其监督矩阵H,确定(n,k)中的n和k;（2）写出监督位的关系式，以及该线性分组码的所有许用码组。n（1）因为给出的生成矩阵）因为给出的生成矩阵G是典型阵，所以可以得到是典型阵，所以可以得到由由Q推出：推出：可得：可得：n=6 k=3n=6 k=3n（2）线性分组码的监督关系由其监督矩阵）线性分组码的监督关系由其监督矩阵H来确定：来确定：求许用码组线性分组码例2已知（7，4）码的生成矩阵为：列出所有许用码组并求监督矩阵 错码矩阵和错误图样设发送码组A为n 列的行向量设接收码组B为 n列的行向量发送码组和接收码组之差为B A=E (模2)E 传输中产生的 错码 行矩阵错码矩阵有时也称为错误图样接收端译码接收端译码n 接收端译码时计算错误图样与校正子之间有确定的关系无错时，S等于零有错，S不等于零。校正子(伴随式)例 设 验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？且有3个接收码组解：1）若无错，则错误图样为0，S为0B1无错B2错B3错2）S2=H 第1列 E=1 0 0 0 0 0 第1位错同理 S3=H 第3列 E=0 0 1 0 0 0 第3位错错误图样错误图样e 校正子校正子E1:100000101E2:010000110E3:001000011E4:000100100E5:000010010E6:000001001