线性分组码..[共25页].ppt

1 分组码krnk是每组二进制信息码元的数目，n是编码码组的码元总位数又称为码组长度，简称码长n-k=r为每个码组中的监督码元数目n,k)分组码是对每段k位长的信息组以一定的规则增加r个监督位， 组成长为n的码组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)监督位信息位假设校正子与错码位置的对应关系如表规定(也可以另外规定) 。

仅当仅当一位错码一位错码在在a2 、a4、a5或或a6时，校正子时，校正子S1为为1,偶数监督关系偶数监督关系a1、a3、a5和和a6构成偶数监督关系：构成偶数监督关系：a0、a3、a4和和a6构成偶数监督关系：构成偶数监督关系：如何构造监督关系式？监督位监督位a2、a1和和a0应根据信息位的取值按监督关系来确定，即应根据信息位的取值按监督关系来确定，即监督位应使监督位应使S1、S2和和S3的值为的值为0:上式经过移项运算，解出监督位上式经过移项运算，解出监督位给定信息位后，可以直接按上式算出监督位给定信息位后，可以直接按上式算出监督位接收端接收端收到每个码组后，先按照约定计算出收到每个码组后，先按照约定计算出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个错码 线性分组码的一般原理线性分组码的一般原理线性分组码的构造线性分组码的构造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。