《线性分组码-1》由会员分享，可在线阅读，更多相关《线性分组码-1（63页珍藏版）》请在金锄头文库上搜索。
1、1,通信系统,信源编码（减少）冗余，提高编码效率 ； 信道编码提高信息传递的可靠性 .,2,展望,提高信息传输的可靠性和有效性，始终是通信工作所追求的目标； 在一定条件下总存在简单、有效编、译的“好码”.,3,线性分组码,基础知识 抽象代数基础 线性代数基础,4,引例 线性分组码的基本概念 线性分组码的译码 汉明码的编码与译码,线性分组码,5,引例 线性分组码的基本概念 线性分组码的译码 汉明码的编码与译码,线性分组码,6,设传输一比特字符x=0或1若传输过程中出现差错,不能被发现,引例,7,引例,0后附加字符0，1后附加1；即只有00和11被接受，且00视为0，11视为1； 故：如果有一位错
2、误发生，可以被检出！,8,如果通信过程中发现差错，可以通过要求对方重新发送来获得正确的信息，即所谓的“数量换质量”. 但是这在实时信息采集系统中可能是有困难的，因为信息源已经发生变化；即使是在发方保留原信息样本的情况下，也只有在差错率很低的条件下是比较可行的. 因为如果通信条件比较恶劣，差错出现频繁，以至多次重发仍然得不到一份正确的信息. 这时，仅有“检错”手段，已无能为力！,引例,9,引例,0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时： 发生不超过两位的错误均可被检出； 发生一位错误可以被纠正.,10,引例,0后附加字符00，1后附加11；即
3、传输000相当于传送单字符0，111相当于传送单字符1；这时： 发生不超过两位的错误均可被检出； 发生一位错误可以被纠正.,纠错码,信息位,校验位,11,引例 线性分组码的基本概念 线性分组码的编码 汉明码的编码与译码,线性分组码,12,线性分组码的基本概念,分组码 分组码是把信源输出的信息序列，以k个信息位 分为一段，通过编码器把这段信息位按一定规则 f 产生r个校验位，输出长为n=k+r的一个码字， 所得码字的全体.称之为（n， k ）分组码 ！ n表示码长， k信息位个数.,13,引例,0后附加字符00，1后附加11；即传输000相当于传送单字符0，111相当于传送单字符1；这时： 发生
4、不超过两位的错误均可被检出； 发生一位错误可以被纠正.,(3,1)分组码,信息位,校验位,14,线性分组码的基本概念,（n， k ）分组码,若校验位与信息位之间的关系是线性的，即上述编码规则是线性的，称之为（n， k ）线性分组码！,15,线性编码从 到 的一个线性映射 称为一个线性编码；,线性分组码的基本概念,即,均有 ；,若 是一一映射，则称其为唯一可译线性编码；,16,线性分组码的基本概念,线性分组码 线性分组码是把信源输出的信息序列，以k个信 息位分为一段，通过编码器把这段信息位按线性 编码规则f 产生r个校验位，输出长为n=k+r的一 个码字，所得码字的全体.称之为（n， k ）线性
5、分组码 ！ n表示码长， k信息位个数. 码字个数M=2k .,17,若设码字 ，则,即校验位是由信息位线性组合得到.,线性分组码的基本概念,18,可见，码字的三个校验元都由其前两位线性组合得到，即可由的线性方程组求得；,线性分组码的基本概念,信息位k=2 码字数M=4,19,线性编码,线性分组码的基本概念,20,例题1： 下面是某个（n，k）线性二元码的全部码字 x16=000000 x26=100011 x36=010101 x46=001111 x56=110110 x66=101100 x76=011010 x86=111001求n、k的值；,n=6;,线性分组码的基本概念,M=2k
6、k=3.,解：,21,例2、（5，2）线性二元码的全部码字设码字 ，可得,线性分组码的基本概念,22,线性分组码的基本概念,改写为用矩阵可表示成：,校验矩阵,与任一码字的乘积为0,23,线性分组码的特性 2k个码字完全可由其中一组k 个独立的码字组合而成；,线性分组码的基本概念,生成矩阵 从线性分组码（n，k）中任取 k 个线性无关的码字，以行的形式写成矩阵G，则称为该线性分组码的生成矩阵.,24,例题3： 下面是一个（6，3）线性二元码的全部码字,构造它的一个生成矩阵.,线性分组码的基本概念,解：由k=3 个线性独立的码字 组成：,25,例题3： 下面是一个（6，3）线性二元码的全部码字,验
7、证：,线性分组码的基本概念,26,系统码若（n , k）线性分组码的生成矩阵形如G=(Ik A) 其中Ik是k阶单位阵， A为 阶子阵， 则称这类码为系统码.,线性分组码的基本概念,特点：校验矩阵为H=(-AT I(n-k) ) .,27,例题3： 下面是一个（6，3）线性二元码的全部码字,它的一个生成矩阵,线性分组码的基本概念,请写出它的校验矩阵H.,信息组原封不动地搬到码字前位的码,28,线性分组码的基本概念,29,线性分组码的基本概念,汉明距离：指（n,k）分组码中两个码字xn 、 yn对应位取值不同的个数；记为d（xn ，yn）.例：,30,线性分组码的基本概念,理查德卫斯里汉明（Ri
8、chard Wesley Hamming，1915.2.111998.1.7.），美国数学家，主要贡献在计算机科学和电讯。 1937年芝加哥大学学士学位毕业，1939年内布拉斯加大学硕士学位毕业，1942年伊利诺伊大学香槟分校博士学位毕业，博士论文为一些线性微分方程边界值理论上的问题（Some Problems in the Boundary Value Theory of Linear Differential Equations）。 二战期间在路易斯维尔大学当教授，1945年参加曼哈顿计划，负责编写电脑程式，计算物理学家所提供方程的解。该程式是判断引爆核弹会否燃烧大气层，结果是不会，于是核
9、弹便开始试验。 1946至76年在贝尔实验室工作。他曾和约翰怀尔德杜奇、克劳德艾尔伍德香农合作。1956年他参与了IBM 650的程式语言发展工作。,31,线性分组码的基本概念,汉明距离：指（n,k）分组码中两个码字xn 、 yn对应位取值不同的个数；记为d（xn ， yn）.例：,32,线性分组码的基本概念,线性分组码的最小距离：称（n,k）分组码中任两个码字汉明距离的最小值，为该分组码的最小距离d. （5,2）线性分组码全部码字：最小距离d=3.,汉明重量,33,引例 线性分组码的基本概念 线性分组码的译码 汉明码的编码与译码,线性分组码,生成矩阵 校验矩阵 码的最小距离,34,引例 线性
10、分组码的基本概念 线性分组码的译码 汉明码的编码与译码,线性分组码,35,线性分组码的译码,基本概念错误图样 设发送的码字xn =(x1， x2，xn)，通过有扰信道传输， 到达接收端译码器的序列为rn =(r1， r2，rn) 信道中的干扰表示为二进序列：错误图样en =(e1， e2，en). 相应有错的ei取值为1. rn = xn + en ， 其中ri=xi+ei， xi， ri， eiGF(2)称en为信道中的错误图样.,译码器任务从rn中得到xn或en .,36,线性分组码的译码,例4 设发送序列xn = (1111100000)， 收到的序列rn = (1001010000).
11、第二、三、五、六位产生了错误， 因此信道的错误图样en的二、 三、 五、 六位取值为1，其它各位取值为0， 即en =(0110110000). 用式子可表示成：,rn = xn + en,37,线性分组码的译码,基本概念伴随式 由于分组码中的任一码字满足： xnHT=0，所以，可对收到的序列rn进行检验：rnHT=(xn+en )HT=xnHT+enHT=enHT 若en=0，则rnHT=0； 若en0，则rnHT 0. 记S= enHT ，称之为接收序列rn的伴随式.,rnHT仅与错误图样有关，与发送什么码字无关！,38,（n，k）线性分组码的校验矩阵，用列向量表出：,线性分组码的译码,其
12、中，hn-i为H矩阵的第i列.,39,设en=(e1， e2，en)=(0，ei1，0，ei2，0，ei3，0，eit，0，0)其中eij=1,即第i1，i2，it位有错， 则,线性分组码的译码,S是H中相应于eij那几列的线性组合！,40,线性分组码的译码,例5 已知（7，3）码的校验矩阵为若发送码字xn =（1110100），收到rn =（0010100）. 则错误图样为en =（1100000）.,41,线性分组码的译码,由定义可以求得， rn的伴随式：,是H矩阵第一列与第二列之和！,42,线性分组码的译码,若错误图样en =（0010000），则,是H矩阵第三列！,若错误图样中只有一个
13、分量非零，则ST是H矩阵相应的列，因而能够纠正单个错误！,43,线性分组码的译码,若错误图样en =（0010100），则,是H矩阵第三列与第五列之和！,44,线性分组码的译码,由定义可以求得， rn的伴随式：,是H矩阵第一列与第二列之和！,若发生两个错误，译码器只能判决传输有错（ en 0 ）,不能判定由哪几位错误引起！,45,线性分组码的译码,线性分组码能自动纠正t个错误的充要条件是d=2t+1 .,最大似然译码准则是纠错的策略依据.若收到的字符串是码字本身，则直接按码字译码；否则，按与接收到的字的Hamming距离最接近的码字译码.,46,线性分组码的译码,例5 已知（7，3）码的校验矩
14、阵为,最小距离 d=3, d=2t+1,47,线性分组码的译码,（n,k）码的译码步骤（1）由接收到的rn，计算伴随式S= rnHT ；（2）若S=0，则认为接收无误；若S0，则由S找出错误图样en ；（3）由en和rn找出xn= rn-en.,48,引例 线性分组码的基本概念 线性分组码的译码 汉明码的编码与译码,线性分组码,49,线性分组码,汉明码(Hamming Code) 汉明码是1950年由汉明首先构造， 用以纠正单个错误的线性分组码. 由于它的编译码非常简单， 很容易实现， 因此用得很普遍， 特别是在计算机的存贮和运算系统中更常用到，是一类特别引人注意的码.,50,线性分组码,汉明
15、码(Hamming Code) 汉明码不是指一个码，而是代表一类码； 汉明码码长n和信息位k服从以下规律： (n,k)=(2m-1, 2m-1-m)，其中m= n-k； 汉明码的最小距离d=3；所以，纠错能力t = 1；,51,汉明码(Hamming Code) 的译码 例6 已知GF(2)上的（6，3）汉明码的一致校验矩阵H为：,线性分组码,52,线性分组码,若发送码字xn=(101011),接收序列为rn=(101011). 若发送码字xn=(101011),接收序列为rn=(100011).,判定传输中没有发生错误！,判定接收序列rn的第3位是有错的！,53,线性分组码： 生成矩阵，校验
16、矩阵； 伴随式： 线性分组码的译码； 汉明码的编码与译码.,结语,54,设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？ 此分组码的生成矩阵； 向量101010是否是码字？ 设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？,55,设一分组码具有一致校验矩阵：求这个分组码n=？k=？，共有多少个码字？ 此分组码的生成矩阵； 向量101010是否是码字？ 设发送码字C=(001111)，但接收序列为R=(000010),其伴随式S是什么？这个伴随式指出已发生的错误在什么地方，为什么与实际错误不符？,
