《通信原理 信道编码基本概念汉明码编码错误图样纠检过程.pptx》由会员分享，可在线阅读，更多相关《通信原理 信道编码基本概念汉明码编码错误图样纠检过程.pptx（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、若某信源产生两个符号若某信源产生两个符号A A与与B B，假设分别用两个长度为，假设分别用两个长度为4 4的码组（已被信道编码）的码组（已被信道编码）进行表示：进行表示：A=0110A=0110；B=1100B=1100，码距，码距d d=2=2，此时只有这两个码组是，此时只有这两个码组是许用码组许用码组，其他其他4 4位二进制比特位的组合均为位二进制比特位的组合均为禁用码组禁用码组（不能代表任何消息）（不能代表任何消息）假设这种信道编码方式具有检错能力，下面分析码距与检错能力的关系假设这种信道编码方式具有检错能力，下面分析码距与检错能力的关系 1 1）消息）消息A A经过传输后发生一位错误后
2、的情况可能为：经过传输后发生一位错误后的情况可能为：A(0110)1110A(0110)1110，00100010，01000100，0111 0111 2 2）消息）消息A A经过传输后发生二位错误后的情况可能为：经过传输后发生二位错误后的情况可能为：A(0110)1010A(0110)1010，00000000，01010101，11001100，11111111，0011 0011 同理：同理：B(1100)0000B(1100)0000，00110011，01010101，10101010，10011001，01100110 A A码组的误码集合中存在许用码组码组的误码集合中存在许用码
3、组B B，可知该编码方法不能检查二位以上的错误，可知该编码方法不能检查二位以上的错误因此编码的检错能力与码距有关因此编码的检错能力与码距有关最小码距与检、纠错能力关系在一个码组集合中，任意两个码组间在一个码组集合中，任意两个码组间距离的最小值，即码组集合中任意两距离的最小值，即码组集合中任意两元素间的最小距离，记为元素间的最小距离，记为d dminmin第1页/共35页有上述分析可知：假设一个码能检测e个独立错误，则要求其最小码距 dmine+1反之，若码的最小距离为dmin，则最多能检测dmin-1个错码第2页/共35页若某信源产生两个符号若某信源产生两个符号A A与与B B，假设分别用两个
4、长度为，假设分别用两个长度为4 4的码组（已被信道编码）的码组（已被信道编码）进行表示：进行表示：A=0110A=0110；B=1000B=1000，码距，码距d d=3=31.1.假设这种信道编码方式具有纠错能力，下面分析码距与纠错能力的关系假设这种信道编码方式具有纠错能力，下面分析码距与纠错能力的关系1 1）若信道中只可能发生一位或两位错误，则消息）若信道中只可能发生一位或两位错误，则消息A A与消息与消息B B经过传输后发生一位经过传输后发生一位错误后的情况分别可能为：错误后的情况分别可能为：A(0110)1110A(0110)1110，00100010，01000100，0111 01
5、11 B(1000)0000B(1000)0000，11001100，10101010，1001 1001 若该种编码方法可以纠正若该种编码方法可以纠正t t=1=1个错误，即个错误，即d d 2 2t t+1+1，对于上面两个误码集合是没，对于上面两个误码集合是没有交集的。有交集的。因此可以完全的纠错，即可以分别将误码集合中的码字纠正为因此可以完全的纠错，即可以分别将误码集合中的码字纠正为A A或或B B第3页/共35页2 2）若信道中最多可以发生两位以内错误，消息）若信道中最多可以发生两位以内错误，消息A A与消息与消息B B经过传输后发生一位或经过传输后发生一位或两位错误后的情况分别可能
6、为：两位错误后的情况分别可能为：A(0110)A(0110)11101110，00100010，01000100，01110111，10101010，00000000，01010101，11001100，11111111，0011 0011 B(1000)B(1000)00000000，11001100，10101010，1001 1001，01000100，11101110，10111011，10101010，10011001，1101 1101 每个误码集合中前每个误码集合中前4 4个码组为误码一位的码组，后个码组为误码一位的码组，后6 6个位误码两位的码组个位误码两位的码组若该种编码方法
7、可以纠正若该种编码方法可以纠正t t=2=2个错误，即个错误，即d d 2 2t t+1+1；观察发现两个误码集合存在交集，交集中的码组用相应的颜色标出；观察发现两个误码集合存在交集，交集中的码组用相应的颜色标出；两个集合中黑色字体的码组都可以被正确的纠正，但对于其他颜色的码组，比如两个集合中黑色字体的码组都可以被正确的纠正，但对于其他颜色的码组，比如11101110，它在两个集合中都存在，此时接收端不知道该纠正为，它在两个集合中都存在，此时接收端不知道该纠正为A A还是还是B B。因此当因此当d d 2 t)纠正t个错码，同时能检测e个错码，称为纠检结合，错码数较少时执行纠错方式，错码数较多
8、时执行检错方式第6页/共35页有限域的简单知识所谓有限域是指包含有限个元素的集合，按照所规定的运算规则运算后的结果仍为集合中的元素编码理论中有限域为0,1二元集合，记为GF(2)GF(2)的加法与乘法：1）加法：相同为0，相异为1；2）乘法：除了11=1，其他均为0二元扩展域，记为GF(2n)：由GF(2)中的元素构成的长为n的序列的集合，若 1）加法 2）乘法第7页/共35页二、线性分组码线性分组码的数学定义：信道编码可表示为由编码前的信息码元空间Uk到编码后的码字空间Cn的一个映射f，即：f：Uk Cn 其中(n k)若f进一步满足线性关系：则称f为线性编码映射，若f为一一对应映射，则称f
9、为唯一可译线性编码，由f编写的码c=(cn-1cn-2c0)称为线性分组码，u=(un-1un-2 u0)为编码前的信息分组，其中k为信息位数，n为码长，其编码效率为=k/n第8页/共35页数学定义的解释：1）“线性”是指码组中码元之间的约束关系为线性；2）“分组”是在编码时将每k个信息位分为一组进行独立处理；3）将其变换成长度为n（nk）的二进制码组，一般称为（n,k）线性分组码线性分组码的特征：1）加法封闭性：码组集合中任意两个码组相加仍为集合中的一个许用码组；2）全零序列是线性分组码中的一个码字；3）码组集合中码组之间的最小码距等于某非零码字的最小码重第9页/共35页偶监督偶校验码发送端
10、编码：将一位监督码元附加在信息码元后，使得码组中“1”码元个数为偶数（偶监督）接收端译码校验：1）计数接收码组中“1”码元个数是否为偶数，即计算 S=an-1+an-2+a0 2）S=0认为没错，S=1认为有错 3）上式称为监督方程（监督关系式），其中S 称为校正子（校验子、伴随式）4）S只能判断有错无措，而不能纠错汉明码的构造第10页/共35页 假设有1个信息码组由4位二进制位组成，在其后添加3位二进制位作为监督码元，最后所组成的码组表示为：c=(u6u5u4u3c2c1c0)并且令：1）c2监督u6 u5 u4，即 2）c1监督u6 u5 u3，即 3）c0监督u6 u4 u3，即接收端译
11、码校验，得到监督方程：第11页/共35页对于上式，若无错误发生，三个校验子均为0；假设传输过程中有且仅有一位发生错误：1）若c0发生错误，观察监督方程，则三个校验子S2 S1 S0的组合为001；2）若c1发生错误，S2 S1 S0=010；3）若c2发生错误，S2 S1 S0=100；4）若u3发生错误，S2 S1 S0=011；5）若u4发生错误，S2 S1 S0=101；6）若u5发生错误，S2 S1 S0=110；7）若u6发生错误，S2 S1 S0=111；第12页/共35页因此依据监督关系式就可计算出所有4位二进制信息位u6u5u4u3的监督位c2c1c0，这一过程即为(7,4)线
12、性码的构造过程，其码组空间为：表中所示为表中所示为(7,4)(7,4)线性码线性码的码组空间的码组空间第13页/共35页监督矩阵的推导将监督关系式进行变换观察发现上式即为一个线性方程组，因此可用矩阵方程来表示：第14页/共35页对于上面的矩阵方程，令：则矩阵方程可化简为：HCT=OT 或 CHT=O那么H称为线性码监督矩阵，rn 阶的矩阵，由r（监督位个数）个线性独立方程组的系数组成，每一行代表了监督位与信息位间的监督关系。观察矩阵H：把具有(PIr)形式的H矩阵称为典型形式的监督矩阵，其中P矩阵为rk 阶矩阵,Ir矩阵为rr 阶单位方阵H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一
13、定线性无关第15页/共35页生成矩阵的推导对监督关系式进行移项变换（移动红色部分）：第16页/共35页观察上面的矩阵方程：其中系数矩阵与监督矩阵H中的P矩阵一样，对此矩阵方程两边做转置变换：其中Q=PT，为kr 阶矩阵；U矩阵表示信息位由上面的矩阵方程可知，只要用信息位与矩阵Q相乘就可得到监督位，然后拼接在信息位之后就是一个（n,k）线性分组码集合中的一个码字第17页/共35页虽然通过Q矩阵可以产生线性分组码，但需要分为两步，如果对Q矩阵做变换：在Q矩阵的左边加上一个kk阶单位阵，即：则一个（n,k）线性分组码可以通过下面的矩阵方程产生矩阵矩阵GG则被称为线性分组码则被称为线性分组码的的生成矩
14、阵生成矩阵第18页/共35页对于生成矩阵G：1）kn阶矩阵；2）编码方法完全由生成矩阵G确定；3）把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中Ik为kk阶单位方阵，Q为k r阶矩阵；4）由典型生成矩阵产生的分组码一定是系统码；5）若某生成矩阵G不具有典型形式，则产生的线性分组码为非系统码；若将G进行线性初等矩阵变换，使其具有典型形式，则产生的码组与不变换产生的码组有同样的纠检能力，即系统码与非系统码的纠检能力相同；6）H=PIr=QTIr G=IkQ=IkPT7）生成矩阵G的各行线性无关若若k k位的信息码元出现在线性分组码位的信息码元出现在线性分组码的前的前k k位，则称此线性分组码
15、为系统位，则称此线性分组码为系统码，否则为非系统码码，否则为非系统码第19页/共35页对于监督矩阵H：1）H矩阵rn 阶的矩阵2）H矩阵中每行和其码组集合中的任一码字的内积为0；3）任意一个(n,k)线性分组码的H矩阵行线性无关；4）一个(n,k,d)线性分组码，若要至多纠正t个错误，则其充要条件是H矩阵中任何2t列线性无关，由于最小距离d=2t+1，所以也相当于要求H矩阵中任意(d 1)列线性无关第20页/共35页生成矩阵G与监督矩阵H的关系：因为信息位不会全零，因此：再由：H=PIr，G=IkQ，代入上式，得：上式中矩阵的下标为其阶数第21页/共35页例：设（7,4）线性码的生成矩阵G为：
16、当信息位为0001时，试求其后的监督位。第22页/共35页例：试求上例的监督矩阵H解：根据生成矩阵和监督矩阵的关系：G=IkQ，H=PIr可得监督矩阵H为：第23页/共35页对偶码定义：对于线性分组码：1）将(n,k)码的监督矩阵H作为(n,n k)码的生成矩阵G；2）将(n,k)码的生成矩阵G作为(n,n k)码的监督矩阵H这样的(n,k)码与(n,n k)码互为对偶码第24页/共35页编码过程观察(7,4)码的监督关系式：可设计出相应的编码电路：第25页/共35页译码纠、检过程错误矩阵/错误图样E：设发送码组为c，接收码组为y，则 对于二元有限域，上式中的减法等价于加法，即：对于二元有限域
17、的加法的具有确定两个码组中不同比特位的特性，例如：假设长度为n的码组A和B分别为：假设这两个码组的第k位不同，其他位相同，根据加法规则：因此接收端可以利用这种特性进行纠错，即若能确定错误图样就可以进行纠错：除了第除了第k k位为位为1 1，其他均为，其他均为0 0。若有。若有1 1位以上位以上的不同，同样可以根据相加之后的的不同，同样可以根据相加之后的1 1的位的位置确定不同的比特位，此特性还说明置确定不同的比特位，此特性还说明A A与与B B之和的码组的码重等于之和的码组的码重等于A A与与B B的码距的码距接收端纠错后的码组接收端纠错后的码组第26页/共35页接收端利用监督矩阵计算校正子S
18、，即可见校正子S只与E有关，即错误图样与校正子之间有确定的关系而校正子S可以用接收码组y与监督矩阵HT相乘获得，则错误图样也就得到确认，即：上式即为一个线性方程组，但它的解不唯一，即求得的错误图样不唯一。假设其中一个解为e0，即e0 HT=S，则对于码组集合中的任一许用码组c，下式一定成立：因此这个线性方程组一共有2k个解，即2k个错误图样第27页/共35页因此利用等式 及2k个错误图样可以纠正出2k个码组，即：稍作变换，每个等式进行移项：再由两个码组之和的码重等于两个码组的码距，可得：最佳译码应选择那些离y最近的 ，再由上式可知：1）所有错误图样中选择码重最小图样；2）该图样所对应的 作为纠
19、正后的码组第28页/共35页例如，某(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)第29页/共35页在实际中译码：1）一般事先确定好每种校正子S所对应的所有错误图
20、样；2）选择码重最小的错误图样作为可纠正的错误图样；3）然后将校正子与最小码重的错误图样制成表格；4）译码时，利用校正子查表，然后用等式c=e+y进行纠正译码电路包括三个部分：1）计算校正子；2）查找确定纠正图样；3）纠正接收码组中的错误译码纠、检过程第30页/共35页某（7，4）码的监督矩阵以及校正子错误图样表：查表方法如下：第31页/共35页观察错误图样表发现校正子与错误图样一一对应利用二元有限域的乘法规则，对于等式：S2 S1 S0=1当且仅当S2、S1、S0全为1时成立，因此：1）对每一校正子设计一个这样的乘式，保证其乘积为1；2）对于右表共设计7个乘式，对应于7种可能出现的错误图样；
21、3）当三位校正子确定后，代入到7个乘式中计算，哪个乘式为1，就表明是哪一个图样第32页/共35页由其监督矩阵可知，其监督位与信息位之间的偶监督关系：由其监督矩阵可知，其监督位与信息位之间的偶监督关系：进行纠错，即实现等式：进行纠错，即实现等式：7 7个逻辑与门所进行的运算分别为：个逻辑与门所进行的运算分别为：第33页/共35页线性分组码的封闭性特征的证明：码组集合中任意两许用码组之和仍为一许用码组证明：设A1和 A2为码中任意两许用码组，则有A1HT=0 A2HT=0A1HT+A2HT=(A1+A2)HT=0即（A1+A2）必是该码中一许用码组由封闭性以及二元有限域的加法特性可知，两个码组之间的距离必是另一码组的重量，码的最小距离等于非零码的最小重量。此即证明了为线性分组码的另一特征第34页/共35页感谢您的观看！第35页/共35页