《线性分组码解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《线性分组码解析ppt课件.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 信道编码 信道编码n6.1 信道编码简介信道编码简介n6.2 6.2 线性分组码线性分组码 n6.3 循环码循环码线性分组码线性分组码n线性分组码（线性分组码（n,k）：）：n分组特性：码长和消息长度恒定分组特性：码长和消息长度恒定n码长为码长为n，其中消息位为，其中消息位为k位位,且每输出且每输出n位只和当前位只和当前的的k位输入有关；位输入有关；n线性特性：码字线性特性：码字c的各位码元是消息的各位码元是消息m各位的线性组各位的线性组合合n一个（一个（n,k）线性分组码的码字）线性分组码的码字 c可以表示为可以表示为nc=mGn其中其中m：长度为：长度为k的消息或的消息或k维的消息
2、向量维的消息向量nGk*n：k行行n列的列的生成矩阵生成矩阵n矩阵运算采用模二加和模二乘。矩阵运算采用模二加和模二乘。例例6.2.16.2.1：P P176176求求3 3重复码的生成矩阵。重复码的生成矩阵。n解：解：3重复码的编码规则：重复码的编码规则：n消息消息0重复三次编成重复三次编成000n消息消息1重复三次编成重复三次编成111n所以所以3重复码是一个（重复码是一个（3，1）码）码n根据根据C=mG得得 n生成的码字生成的码字 (000)，（，（111）：称为许用码组。）：称为许用码组。n由由0，1组成的长为组成的长为3的其余码字有的其余码字有23-2个：称为禁个：称为禁用码组。用码
3、组。 111 )()()(3100031031210GmmmGmccc)()(0000mmmcmmn例：已知二进制消息长为例：已知二进制消息长为k,则消息为则消息为m=(m0，m1，mk-1)，生成码长为，生成码长为n的码字的码字C=(c0，c1cn-1)，由，由m生成生成C满足下列约束方程：满足下列约束方程：c0 0=m0 0c1 1=m1 -2n-2= mk-1 k-1 则则n=k+1cn-1n-1=m0 0+m1 1+mk-1k-1 求生成矩阵，并判断该码具备什么特点。求生成矩阵，并判断该码具备什么特点。n解：解：由约束方程易知由约束方程易知 c0，c1cn-1= m0，m1mk-1，m
4、0+m1+mk-1又因为又因为C=mG =m0，m1，mk-1Gk*n所以可求出所以可求出n该码的特点：该码的特点：n生成规则：生成规则：前前k位信息位位信息位原封不动的搬到码字的前原封不动的搬到码字的前k位，最后一位位，最后一位校验位校验位为前面所有信息位的和。为前面所有信息位的和。n校验规则校验规则：c0+c1+ cn-2+cn-1 = m0+m1+mk-1+(m0+m1+mk-1) =0n所以译码时可以通过判断码字的各位和是否为所以译码时可以通过判断码字的各位和是否为0来确定传输中是否发生了差错。来确定传输中是否发生了差错。n这种码称为这种码称为奇偶校验码奇偶校验码(n,n-1)：只能检
5、测奇数：只能检测奇数个错误，不能检测偶数个差错（因为二进制求和，个错误，不能检测偶数个差错（因为二进制求和，错偶数位，错错相抵）错偶数位，错错相抵）例例6.2.2：P176已知（已知（4，3）奇偶校）奇偶校验码的生成矩阵，求生成的所有码字。验码的生成矩阵，求生成的所有码字。n解：由奇偶校验码的生成矩阵解：由奇偶校验码的生成矩阵110010101001nkG而而C=mGC=mG, ,所以所以由生成规则得：全部的生成码字为：由生成规则得：全部的生成码字为：00000000000000，00100100110011，01001001010101，01101101100110，100100100110
6、01，10110110101010，11011011001100，11111111111111线性分组码的性质线性分组码的性质（1）零向量一定是一个码字，记作）零向量一定是一个码字，记作（2）任意两码字的和仍是一个码字。）任意两码字的和仍是一个码字。（3）任意码字）任意码字c都可以表示为都可以表示为G的行向量的线性组合。的行向量的线性组合。 G的行向量是码集合中的码字（它们线性无关）的行向量是码集合中的码字（它们线性无关）（4）线性分组码的）线性分组码的最小距离最小距离等于等于最小非最小非0码的码重码的码重：n码重：码字中的非码重：码字中的非0码元的个数。码元的个数。)0 , 0 , 0()(
7、minmincwdc)0101(c例：2)(cwd校验矩阵校验矩阵n根据奇偶校验码的校验规则，可以通过计算接收根据奇偶校验码的校验规则，可以通过计算接收向量向量r的所有校验方程是否为的所有校验方程是否为0来判断传输过程中来判断传输过程中是否出现差错，那么所有的校验方程满足以下是否出现差错，那么所有的校验方程满足以下n又因为又因为Gk*n的每一行都是一个码字，所以的每一行都是一个码字，所以TcH方程。的每一列确定一个校验TH位数表示监督位或校验位的, knr。线性分组码的校验矩阵为称),(knHnrTGHn若某个码集合的生成矩阵中含有单位阵，即若某个码集合的生成矩阵中含有单位阵，即n（1）则该码
8、称为）则该码称为系统码系统码。n容易发现，若系统线性分组码的生成矩阵容易发现，若系统线性分组码的生成矩阵G 的的左左（右）半部分是（右）半部分是Ik*K的单位阵，则线性分组码的的单位阵，则线性分组码的前前（后）（后）k位是信息位，后位是信息位，后n-k位是校验位。位是校验位。n若不是系统码生成矩阵，也可以通过简单行变换若不是系统码生成矩阵，也可以通过简单行变换得到系统码生成矩阵。得到系统码生成矩阵。n（2）系统码的校验矩阵称为一致校验矩阵，记作）系统码的校验矩阵称为一致校验矩阵，记作nkrkkksQIGG，nrrTrksIQH,例例6.2.3：P177已知一个（已知一个（5，3）线）线性分组码
9、的生成矩阵为性分组码的生成矩阵为n解解：要求系统码生成矩阵，先观察已知的生成矩：要求系统码生成矩阵，先观察已知的生成矩阵是否符合系统码生成矩阵的特点。阵是否符合系统码生成矩阵的特点。n观察发现不符，则需对观察发现不符，则需对G进行初等行变换使其变为进行初等行变换使其变为含单位阵含单位阵I3的矩阵：的矩阵： 010111101001101G求它相应的系统码生成矩阵求它相应的系统码生成矩阵GsGs和一致校验矩阵和一致校验矩阵HsHs。 53233QIQIGnkrkkks，n对对G进行初等行变换使其变为含单位阵进行初等行变换使其变为含单位阵I3的矩阵：的矩阵： SRRRRRRRRGG11100110
10、101000110001110101110010001110100110101011110100110131131332n由系统码生成矩阵由系统码生成矩阵GS可以很容易的确定一致校验可以很容易的确定一致校验矩阵矩阵HS10111011101001111110,52252IQHIQHTrknrrTrks线性分组码的最小码距n定理：定理：n线性分组码的最小码距线性分组码的最小码距dmin：一致校验矩阵：一致校验矩阵Hs中中任意任意dmin-1列线性无关，列线性无关，dmin列线性相关。列线性相关。n即即dmin=Hs中线性相关列的最小值中线性相关列的最小值，通过观察，通过观察可以方便求得：可以方便
11、求得：n令令Hs任意两列相加，若存在等于任意两列相加，若存在等于0的这么的这么2列，则列，则dmin=2；n否则继续让否则继续让HS任意任意3列相加，若存在等于列相加，若存在等于0的这么的这么3列，则列，则dmin=3；n1011101110sHn例：上题中的例：上题中的n因为有两列相同，两列相加即出现为因为有两列相同，两列相加即出现为0 0向量的情况，向量的情况，说明存在不全为说明存在不全为0 0的系数（系数为的系数（系数为1 1），使两列线性），使两列线性和为和为0 0向量。所以两列相关向量。所以两列相关, ,即即d dminmin=2=2n该该码的检错能力码的检错能力如何？如何？n该码最
12、多检测出该码最多检测出1 1位错。位错。1min de代入检错公式：线性分组码的译码线性分组码的译码 n译码：根据接收向量译码：根据接收向量r r，能够判断其是否发生差，能够判断其是否发生差错，并将其纠正为正确的码字错，并将其纠正为正确的码字c c。n描述接收向量描述接收向量r r是否有错的特征向量是伴随式向是否有错的特征向量是伴随式向量量s s, ,简称简称伴随式伴随式。)(10rTssrHsTTTTeHseHcHHecsecr)(0TcH又线性分组码的译码线性分组码的译码 n伴随式译码：伴随式译码：n判断判断 是否为是否为0。n若若s为为0，则说明可能存在两种情况：，则说明可能存在两种情况
13、：n（1）r=c，说明接收码字，说明接收码字r无差错。无差错。n（2） 称为不可检错误，对应的称为不可检错误，对应的e称为不可检差错图样。称为不可检差错图样。n若若s不为不为0，说明肯定有误码。，说明肯定有误码。样此时差错图样和码字一即,cerTTeHrHs或说明：说明：伴随式既可以通过接收矢量伴随式既可以通过接收矢量r r求得，也可通求得，也可通过信道错误图样过信道错误图样e e求得，因此可以通过以上两种途求得，因此可以通过以上两种途径来判断信道传输是否有差错，并得出译码方案。径来判断信道传输是否有差错，并得出译码方案。伴随式译码的步骤伴随式译码的步骤P178n1、按照可能出现的差错图案、按
14、照可能出现的差错图案e，计算对应的伴随，计算对应的伴随式式s（s=eHT），并构造所有的），并构造所有的【(s,e)】n2、对实际接收到的码字（向量）、对实际接收到的码字（向量）r，计算伴随式，计算伴随式s*(s*=rHT)n3、查、查【(s,e)】表得到第】表得到第2步求得的步求得的s*对应的对应的e*n4、纠错计算：、纠错计算：*erc伴随式译码举例伴随式译码举例n例：已知某线性分组码的一致校验矩阵为例：已知某线性分组码的一致校验矩阵为解：解：（1 1）可求出）可求出d dminmin=3=3，所以最多能纠，所以最多能纠1 1位错。位错。由由H判断码长判断码长n为为6，因此错一位的错误图样
15、，因此错一位的错误图样e有有6种：种： 100000 010000 001000 00010000001000000163100101010110001011sH求求d dminmin，设收到码字，设收到码字r=000110r=000110，用伴随式进行译码。，用伴随式进行译码。（2 2）用伴随式译码：）用伴随式译码：n1 1）构造纠错能力内的（）构造纠错能力内的（s,es,e）表）表 错误图样错误图样e e伴随式伴随式100000100000101101010000010000110110001000001000011011000100000100100100000010000010010010000001000001001001TeHs n2 2）将）将r=000110r=000110代入代入 s s* *=110=110n3 3）查表）查表1 1）知对应）知对应s s* *=110=110时，时，e e* *010000010000，则，则n4 4）通过纠错计算得正确的码字应为）通过纠错计算得正确的码字应为得TrHs *010110010000000110*erc