信道编码：基本概念、汉明码编码、错误图样.ppt

《信道编码：基本概念、汉明码编码、错误图样.ppt》由会员分享，可在线阅读，更多相关《信道编码：基本概念、汉明码编码、错误图样.ppt（31页珍藏版）》请在三一办公上搜索。

1、信道编码,信道编码的几个基本概念,1）码重：码字中非零位的数目定义为该码组的重量，即所含“1”的个数简称码重，记为Wc。如“10011”码组的码重为32）码距：两个码组中对应码位上具有不同二进制码元的位数被定义为两码组的距离，称为汉明（Hamming）距离，简称码距，记为d(ci,cj)。如两码组“10011”与“11010”间码距为23）编码效率：指一个码组中信息位所占比重，用 表示=k/n其中k为信息码元的数目，n为码长。值越大表明信息位所占的比重越大，码组传输信息的有效性越高,若某信源产生两个符号A与B，假设分别用两个长度为4的码组（已被信道编码）进行表示：A=0110；B=1100，码

2、距d=2，此时只有这两个码组是许用码组，其他4位二进制比特位的组合均为禁用码组（不能代表任何消息）1.假设这种信道编码方式具有检错能力，下面分析码距与检错能力的关系 1）消息A经过传输后发生一位错误后的情况可能为：A(0110)1110，0010，0100，0111 2）消息A经过传输后发生二位错误后的情况可能为：A(0110)1010，0000，0101，1100，1111，0011 A码组的误码集合中存在许用码组B，可知该编码方法不能检查二位以上的错误因此编码的检错能力与码距有关,最小码距与检、纠错能力关系,有上述分析可知：假设一个码能检测e个独立错误，则要求其最小码距 dmine+1反之

3、，若码的最小距离为dmin，则最多能检测dmin-1个错码,若某信源产生两个符号A与B，假设分别用两个长度为4的码组（已被信道编码）进行表示：A=0110；B=1000，码距d=31.假设这种信道编码方式具有纠错能力，下面分析码距与纠错能力的关系1）若信道中只可能发生一位或两位错误，则消息A与消息B经过传输后发生一位错误后的情况分别可能为：A(0110)1110，0010，0100，0111 B(1000)0000，1100，1010，1001 若该种编码方法可以纠正t=1个错误，即d 2t+1，对于上面两个误码集合是没有交集的。因此可以完全的纠错，即可以分别将误码集合中的码字纠正为A或B,2

4、）若信道中最多可以发生两位以内错误，消息A与消息B经过传输后发生一位或两位错误后的情况分别可能为：A(0110)1110，0010，0100，0111，1010，0000，0101，1100，1111，0011 B(1000)0000，1100，1010，1001，0100，1110，1011，1010，1001，1101 每个误码集合中前4个码组为误码一位的码组，后6个位误码两位的码组若该种编码方法可以纠正t=2个错误，即d 2t+1；观察发现两个误码集合存在交集，交集中的码组用相应的颜色标出；两个集合中黑色字体的码组都可以被正确的纠正，但对于其他颜色的码组，比如1110，它在两个集合中都存

5、在，此时接收端不知道该纠正为A还是B。因此当d 2t+1时不能完全正确的进行纠错,由上述分析可知：一个码能纠正t个错码，则要求其最小码距 dmin 2t+1反之，若码的最小距离为dmin，则最多能纠正(dmin-1)/2个错码,一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmine+t+1(et)纠正t个错码，同时能检测e个错码，称为纠检结合，错码数较少时执行纠错方式，错码数较多时执行检错方式,有限域的简单知识,所谓有限域是指包含有限个元素的集合，按照所规定的运算规则运算后的结果仍为集合中的元素编码理论中有限域为0,1二元集合，记为GF(2)GF(2)的加法与乘法：1）加法：相

6、同为0，相异为1；2）乘法：除了11=1，其他均为0二元扩展域，记为GF(2n)：由GF(2)中的元素构成的长为n的序列的集合，若 1）加法 2）乘法,二、线性分组码,线性分组码的数学定义：信道编码可表示为由编码前的信息码元空间Uk到编码后的码字空间Cn的一个映射f，即：f：Uk Cn 其中(n k)若f进一步满足线性关系：则称f为线性编码映射，若f为一一对应映射，则称f为唯一可译线性编码，由f编写的码c=(cn-1cn-2c0)称为线性分组码，u=(un-1un-2 u0)为编码前的信息分组，其中k为信息位数，n为码长，其编码效率为=k/n,数学定义的解释：1）“线性”是指码组中码元之间的约

7、束关系为线性；2）“分组”是在编码时将每k个信息位分为一组进行独立处理；3）将其变换成长度为n（nk）的二进制码组，一般称为（n,k）线性分组码线性分组码的特征：1）加法封闭性：码组集合中任意两个码组相加仍为集合中的一个许用码组；2）全零序列是线性分组码中的一个码字；3）码组集合中码组之间的最小码距等于某非零码字的最小码重,偶监督偶校验码发送端编码：将一位监督码元附加在信息码元后，使得码组中“1”码元个数为偶数（偶监督）接收端译码校验：1）计数接收码组中“1”码元个数是否为偶数，即计算 S=an-1+an-2+a0 2）S=0认为没错，S=1认为有错 3）上式称为监督方程（监督关系式），其中S

8、 称为校正子（校验子、伴随式）4）S只能判断有错无措，而不能纠错,汉明码的构造,假设有1个信息码组由4位二进制位组成，在其后添加3位二进制位作为监督码元，最后所组成的码组表示为：c=(u6u5u4u3c2c1c0)并且令：1）c2监督u6 u5 u4，即 2）c1监督u6 u5 u3，即 3）c0监督u6 u4 u3，即接收端译码校验，得到监督方程：,对于上式，若无错误发生，三个校验子均为0；假设传输过程中有且仅有一位发生错误：1）若c0发生错误，观察监督方程，则三个校验子S2 S1 S0的组合为001；2）若c1发生错误，S2 S1 S0=010；3）若c2发生错误，S2 S1 S0=100

9、；4）若u3发生错误，S2 S1 S0=011；5）若u4发生错误，S2 S1 S0=101；6）若u5发生错误，S2 S1 S0=110；7）若u6发生错误，S2 S1 S0=111；,因此依据监督关系式就可计算出所有4位二进制信息位u6u5u4u3的监督位c2c1c0，这一过程即为(7,4)线性码的构造过程，其码组空间为：,表中所示为(7,4)线性码的码组空间,监督矩阵的推导,将监督关系式进行变换观察发现上式即为一个线性方程组，因此可用矩阵方程来表示：,对于上面的矩阵方程，令：则矩阵方程可化简为：HCT=OT 或 CHT=O那么H称为线性码监督矩阵，rn 阶的矩阵，由r（监督位个数）个线性

10、独立方程组的系数组成，每一行代表了监督位与信息位间的监督关系。观察矩阵H：把具有(PIr)形式的H矩阵称为典型形式的监督矩阵，其中P矩阵为rk 阶矩阵,Ir矩阵为rr 阶单位方阵H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关,生成矩阵的推导,对监督关系式进行移项变换（移动红色部分）：,观察上面的矩阵方程：其中系数矩阵与监督矩阵H中的P矩阵一样，对此矩阵方程两边做转置变换：其中Q=PT，为kr 阶矩阵；U矩阵表示信息位由上面的矩阵方程可知，只要用信息位与矩阵Q相乘就可得到监督位，然后拼接在信息位之后就是一个（n,k）线性分组码集合中的一个码字,虽然通过Q矩阵可以产生线性分组码

11、，但需要分为两步，如果对Q矩阵做变换：在Q矩阵的左边加上一个kk阶单位阵，即：则一个（n,k）线性分组码可以通过下面的矩阵方程产生,矩阵G则被称为线性分组码的生成矩阵,对于生成矩阵G：1）kn阶矩阵；2）编码方法完全由生成矩阵G确定；3）把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中Ik为kk阶单位方阵，Q为k r阶矩阵；4）由典型生成矩阵产生的分组码一定是系统码；5）若某生成矩阵G不具有典型形式，则产生的线性分组码为非系统码；若将G进行线性初等矩阵变换，使其具有典型形式，则产生的码组与不变换产生的码组有同样的纠检能力，即系统码与非系统码的纠检能力相同；6）H=PIr=QTIr G=Ik

12、Q=IkPT7）生成矩阵G的各行线性无关,若k位的信息码元出现在线性分组码的前k位，则称此线性分组码为系统码，否则为非系统码,对于监督矩阵H：1）H矩阵rn 阶的矩阵2）H矩阵中每行和其码组集合中的任一码字的内积为0；3）任意一个(n,k)线性分组码的H矩阵行线性无关；4）一个(n,k,d)线性分组码，若要至多纠正t个错误，则其充要条件是H矩阵中任何一个2t列线性无关，由于最小距离d=2t+1，所以也相当于要求H矩阵中任意(d 1)列线性无关,生成矩阵G与监督矩阵H的关系：因为信息位不会全零，因此：再由：H=PIr，G=IkQ，代入上式，得：上式中矩阵的下标为其阶数,例：设（7,4）线性码的生

13、成矩阵G为：当信息位为0001时，试求其后的监督位。,例：试求上例的监督矩阵H解：根据生成矩阵和监督矩阵的关系：G=IkQ，H=PIr可得监督矩阵H为：,对偶码,定义：对于线性分组码：1）将(n,k)码的监督矩阵H作为(n,n k)码的生成矩阵G；2）将(n,k)码的生成矩阵G作为(n,n k)码的监督矩阵H这样的(n,k)码与(n,n k)码互为对偶码,编码过程,观察(7,4)码的监督关系式：可设计出相应的编码电路：,译码纠、检过程,错误矩阵/错误图样E：设发送码组为c，接收码组为y，则 对于二元有限域，上式中的减法等价于加法，即：对于二元有限域的加法的具有确定两个码组中不同比特位的特性，例

14、如：假设长度为n的码组A和B分别为：假设这两个码组的第k位不同，其他位相同，根据加法规则：因此接收端可以利用这种特性进行纠错，即若能确定错误图样就可以进行纠错：,除了第k位为1，其他均为0。若有1位以上的不同，同样可以根据相加之后的1的位置确定不同的比特位，此特性还说明A与B之和的码组的码重等于A与B的码距,接收端纠错后的码组,接收端利用监督矩阵计算校正子S，即可见校正子S只与E有关，即错误图样与校正子之间有确定的关系而校正子S可以用接收码组y与监督矩阵HT相乘获得，则错误图样也就得到确认，即：上式即为一个线性方程组，但它的解不唯一，即求得的错误图样不唯一。假设其中一个解为e0，即e0 HT=

15、S，则对于码组集合中的任一许用码组c，下式一定成立：因此这个线性方程组一共有2k个解，即2k个错误图样,因此利用等式 及2k个错误图样可以纠正出2k个码组，即：稍作变换，每个等式进行移项：再由两个码组之和的码重等于两个码组的码距，可得：最佳译码应选择那些离y最近的，再由上式可知：1）所有错误图样中选择码重最小图样；2）该图样所对应的 作为纠正后的码组,例如，某(7,3)线性分组码的监督矩阵为：1）若收到的码组y=(1001001)，则利用式S=yHT计算出校正子，其结果为S=(0111)；2）再利用式eHT=S计算出所有可能的错误图样，因为k=3，则共有8个图样分别为：(1001001)(1010100)(1101110)(1110011)(0000111)(0011010)(0100000)(0111101)3）其中图样(0100000)的码重最小，则纠正后的码组为：e+y=(0100000)+(1001001)=(1101001),