6.2线性分组码解析

第6章信道编码信道编码6.1信道编码简介6.2线性分组码6.3循环码线性分组码线性分组码（n,k）：分组特性：码长和消息长度恒定码长为n，其中消息位为k位,且每输出n位只和当前的k位输入有关；线性特性：码字c的各位码元是消息m各位的线性组合一个（n,k）线性分组码的码字c可以表示为c=mG其中m：长度为k的消息或k维的消息向量Gk*n：k行n列的生成矩阵矩阵运算采用模二加和模二乘。例6.2.1：P176求3重复码的生成矩阵。解：3重复码的编码规则：消息0重复三次编成000消息1重复三次编成111所以3重复码是一个（3，1）码根据C=mG得生成的码字(000)，（111）：称为许用码组。由0，1组成的长为3的其余码字有23-2个：称为禁用码组。]111[)()()(3100031031210GmmmGmccc)()(0000mmmcmm例：已知二进制消息长为k,则消息为m=(m0，m1，…mk-1)，生成码长为n的码字C=(c0，c1…cn-1)，由m生成C满足下列约束方程：c0=m0c1=m1...cn-2=mk-1则n=k+1cn-1=m0+m1+…+mk-1求生成矩阵，并判断该码具备什么特点。解：由约束方程易知[c0，c1…cn-1]=[m0，m1…mk-1，m0+m1+…+mk-1]又因为C=mG=[m0，m1，…，mk-1]Gk*n所以可求出该码的特点：生成规则：前k位信息位原封不动的搬到码字的前k位，最后一位校验位为前面所有信息位的和。校验规则：c0+c1+…+cn-2+cn-1=m0+m1+…+mk-1+(m0+m1+…+mk-1)=0所以译码时可以通过判断码字的各位和是否为0来确定传输中是否发生了差错。这种码称为奇偶校验码(n,n-1)：只能检测奇数个错误，不能检测偶数个差错（因为二进制求和，错偶数位，错错相抵）例6.2.2：P176已知（4，3）奇偶校验码的生成矩阵，求生成的所有码字。解：由奇偶校验码的生成矩阵110010101001nkG而C=mG,所以由生成规则得：全部的生成码字为：000—0000，001—0011，010—0101，011—0110，100—1001，101—1010，110—1100，111—1111线性分组码的性质（1）零向量一定是一个码字，记作（2）任意两码字的和仍是一个码字。（3）任意码字c都可以表示为G的行向量的线性组合。G的行向量是码集合中的码字（它们线性无关）（4）线性分组码的最小距离等于最小非0码的码重：码重：码字中的非0码元的个数。)0,,0,0()(minmincwdc)0101(c例：2)(cwd校验矩阵根据奇偶校验码的校验规则，可以通过计算接收向量r的所有校验方程是否为0来判断传输过程中是否出现差错，那么所有的校验方程满足以下又因为Gk*n的每一行都是一个码字，所以TcH方程。的每一列确定一个校验TH位数表示监督位或校验位的,knr。线性分组码的校验矩阵为称),(knHnrTGH若某个码集合的生成矩阵中含有单位阵，即（1）则该码称为系统码。容易发现，若系统线性分组码的生成矩阵G的左（右）半部分是Ik*K的单位阵，则线性分组码的前（后）k位是信息位，后n-k位是校验位。若不是系统码生成矩阵，也可以通过简单行变换得到系统码生成矩阵。（2）系统码的校验矩阵称为一致校验矩阵，记作nkrkkksQIG][G，nrrTrksIQH],[例6.2.3：P177已知一个（5，3）线性分组码的生成矩阵为解：要求系统码生成矩阵，先观察已知的生成矩阵是否符合系统码生成矩阵的特点。观察发现不符，则需对G进行初等行变换使其变为含单位阵I3的矩阵：010111101001101G求它相应的系统码生成矩阵Gs和一致校验矩阵Hs。53233][][QIQIGnkrkkks，，对G进行初等行变换使其变为含单位阵I3的矩阵：SRRRRRRRRGG11100110101000110001110101110010001110100110101011110100110131131332由系统码生成矩阵GS可以很容易的确定一致校验矩阵HS10111011101001111110],[],[52252IQHIQHTrknrrTrks线性分组码的最小码距定理：线性分组码的最小码距dmin：一致校验矩阵Hs中任意dmin-1列线性无关，dmin列线性相关。即dmin=Hs中线性相关列的最小值，通过观察可以方便求得：令Hs任意两列相加，若存在等于0的这么2列，则dmin=2；否则继续让HS任意3列相加，若存在等于0的这么3列，则dmin=3；……1011101110sH例：上题中的因为有两列相同，两列相加即出现为0向量的情况，说明存在不全为0的系数（系数为1），使两列线性和为0向量。所以两列相关,即dmin=2该码的检错能力如何？该码最多检测出1位错。1minde代入检错公式：线性分组码的译码译码：根据接收向量r，能够判断其是否发生差错，并将其纠正为正确的码字c。描述接收向量r是否有错的特征向量是伴随式向量s,简称伴随式。)(10rTssrHsTTTTeHseHcHHecsecr)(0TcH又线性分组码的译码伴随式译码：判断是否为0。若s为0，则说明可能存在两种情况：（1）r=c，说明接收码字r无差错。（2）称为不可检错误，对应的e称为不可检差错图样。若s不为0，说明肯定有误码。样此时差错图样和码字一即,,cerTTeHrHs或说明：伴随式既可以通过接收矢量r求得，也可通过信道错误图样e求得，因此可以通过以上两种途径来判断信道传输是否有差错，并得出译码方案。伴随式译码的步骤P1781、按照可能出现的差错图案e，计算对应的伴随式s（s=eHT），并构造所有的【(s,e)】2、对实际接收到的码字（向量）r，计算伴随式s*(s*=rHT)3、查【(s,e)】表得到第2步求得的s*对应的e*4、纠错计算：*ˆerc伴随式译码举例例：已知某线性分组码的一致校验矩阵为解：（1）可求出dmin=3，所以最多能纠1位错。由H判断码长n为6，因此错一位的错误图样e有6种：10000001000000100000010000001000000163100101010110001011sH求dmin，设收到码字r=000110，用伴随式进行译码。（2）用伴随式译码：1）构造纠错能力内的（s,e）表错误图样e伴随式100000101010000110001000011000100100000010010000001001TeHs2）将r=000110代入s*=1103）查表1）知对应s*=110时，e*＝010000，则4）通过纠错计算得正确的码字应为得TrHs*010110010000000110*ˆerc