6.2线性分组码.ppt

1、第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列的生成矩阵 矩阵运算采用模二加和模二乘。,例：求3重复码的生成矩阵。,解：3重复码的编码规则： 消息0重复三次编成000 消息1重复三次编成111 所以3重复码是一个（3，1）码 根据C=mG得 生成的码字 (000)

2、，（111）：称为许用码组。 由0，1组成的长为3的其余码字有23-2个：称为禁用码组。,例：已知二进制消息长为k,则消息为m=(m0，m1，mk-1)，生成码长为n，则码字为C=(c0，c1cn-1)，由m生成C满足： c0=m0 c1=m1 . cn-2= mk-1 则n=k+1 cn-1=m0+m1+mk-1 求生成矩阵，并判断该码具备什么特点。,解：由C=mG 得c0，c1cn-1 = m0，m1mk-1，m0+m1+mk-1 =m0，m1，mk-1Gk*n 所以,该码的特点： 生成规则：前k位信息位原封不动的搬到码字的前k位，最后一位校验位为前面所有信息位的和。 校验规则：c0+c1

3、+ cn-2+cn-1 = m0+m1+mk-1+(m0+m1+mk-1) =0 所以译码时可以通过判断码字的各位和是否为0来确定传输中是否发生了差错。 这种码称为奇偶校验码(n,n-1)：只能检测奇数个错误，不能检测偶数个差错（因为二进制求和，偶数位错，错错相抵） 根据定义判断：奇偶校验码是一种系统码。,例：已知（4，3）奇偶校验码的生成矩阵，求生成的所有码字。,解：由奇偶校验码的生成矩阵,而C=mG,所以,由生成规则得：全部的生成码字为：0000000，0010011，0100101，0110110， 1001001，1011010，1101100，1111111,线性分组码的性质,（1）

4、零向量一定是一个码字，记作 （2）任意两码字的和仍是一个码字。 （3）任意码字c都可以表示为G的行向量的线性组合。 G的行向量是码集合中的码字（它们线性无关） （4）线性分组码的最小距离等于最小非0码的码重： 码重：码字中的非0符号个数。,校验矩阵,根据奇偶校验码的校验规则，可以通过计算接收向量r的所有校验方程是否为0来判断传输过程中是否出现差错，那么所有的校验方程满足以下 又因为Gk*n的每一行都是一个码字，所以,若某个码集合的生成矩阵中含有单位阵，即 （1）则该码称为系统码。 容易发现，若系统线性分组码的生成矩阵G 的左（右）半部分是Ik*K的单位阵，则线性分组码的前（后）k位是信息位，后

5、n-k位是校验位。 若不是系统码，则可以通过简单行变换得到系统码生成矩阵。 （2）系统码的校验矩阵称为一致校验矩阵，记作,例：已知一个（5，3）线性分组码的生成矩阵为,解：要求系统码生成矩阵，先观察已知的生成矩阵是否符合系统码生成矩阵的特点。 观察发现不符，则需对G进行初等行变换使其变为含单位阵I3的矩阵：,求它相应的系统码生成矩阵Gs和一致校验矩阵Hs。,对G进行初等行变换使其变为含单位阵I3的矩阵：,由系统码生成矩阵GS可以很容易的确定一致校验矩阵HS,线性分组码的最小码距,定理： 线性分组码的最小码距dmin：一致校验矩阵Hs中任意dmin-1列线性无关，dmin列线性相关。 即dmin

6、=Hs中线性相关列的最小值，通过观察可以方便求得： 令Hs任意两列相加，若存在等于0的这么2列，则dmin=2； 否则继续让HS任意3列相加，若存在等于0的这么3列，则dmin=3； ,例：上题中的,因为有两列相同，两列相加即出现为0的情况，所以两列相关,即dmin=2 该码的检错能力如何？ 该码最多检测出1位错。,线性分组码的译码,译码：根据接收向量r，能够判断其是否发生差错，并将其纠正为正确的码字c。 描述接收向量r是否有错的特征向量是伴随式向量s,简称伴随式。,线性分组码的译码,伴随式译码： 判断 是否为0。 若s为0，则可能有两种情况： （1）r=c，说明接收码字r无差错。 （2） 称

7、为不可检错误，对应的e称为不可检差错图样。 若s不为0，说明肯定有误码。,说明：伴随式与接收矢量r无关，只与信道错误图样e有关，因此可以利用简化的s计算式来判断信道传输是否有差错。,伴随式译码的步骤,1、按照可能出现的差错图案e，计算对应的伴随式s（s=eHT），并构造所有的【(s,e)】 2、对实际接收到的码字（向量）r，计算伴随式s*(s*=rHT) 3、查【(s,e)】表得到第2步求得的s*对应的e* 4、纠错计算：,伴随式译码举例,例：已知某线性分组码的一致校验矩阵为 解：（1）dmin=3，所以最多能纠1位错。 由H判断码长n为6，因此错一位的错误图样e有6种： 100000 010000 001000 000100000010000001,求dmin，设收到码字r=000110，用伴随式进行译码。,（2）用伴随式译码： 1）构造纠错能力内的（s,e）表 错误图样e伴随式100000