信息论与编码第六章信道编码.ppt

《信息论与编码第六章信道编码.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第六章信道编码.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码第六章信道编码现在学习的是第1页，共47页6.1 概述概述作用作用提高信息传输时的抗干扰能力提高信息传输时的抗干扰能力目的目的增加信息传输的可靠性增加信息传输的可靠性手段手段增加信息冗余度增加信息冗余度名称名称信道码、数据传输码、差错控制码信道码、数据传输码、差错控制码2现在学习的是第2页，共47页6.1 概述概述信道编码器在通信系统中的位置信道编码器在通信系统中的位置信源编码信源编码信道编码信源译码信源译码信道译码解密解密加密加密信宿信宿信源信源3现在学习的是第3页，共47页分类分类6.1 概述分分组组码码树树码码线线性性码码非非线线性性码码检检错错码码纠纠错错码码抗抗随随机机差

2、差错错码码抗抗突突发发差差错错码码代代数数码码几几何何码码组组合合码码线性分组码线性分组码群码群码 线性树码线性树码卷积码卷积码 4现在学习的是第4页，共47页最小差错概率准则最小差错概率准则 理想译码器，依赖于输入概率分布。理想译码器，依赖于输入概率分布。最大似然准则最大似然准则 实用译码准则，与最小差错概率准则等价。实用译码准则，与最小差错概率准则等价。6.2 信道译码准则5现在学习的是第5页，共47页6.3 码例码例信道编译码方法的最初范例。信道编译码方法的最初范例。基本思路基本思路将码字分成两段将码字分成两段 用模二和对二元分组码进行一致性校验。用模二和对二元分组码进行一致性校验。奇偶

3、校验码奇偶校验码只有一个校验位的汉明码只有一个校验位的汉明码。二元分组码信息位二元分组码信息位校验位校验位奇校验、偶校验。奇校验、偶校验。6现在学习的是第6页，共47页6.3 码例码例 奇校验奇校验 DES算法算法例例1 1 0 0 1 0 111 1 0 0 1 0 10偶校验偶校验7现在学习的是第7页，共47页6.3 码例码例多个校验位的汉明码多个校验位的汉明码 每个校验位是部分或全部信息位按模每个校验位是部分或全部信息位按模二和规则确定。二和规则确定。例例N=7，k=4c4c6c5u3u2u1u0c4c6c5c3c2c1c08现在学习的是第8页，共47页6.3 码例码例0101011可以

4、纠正一个错误。可以纠正一个错误。译码译码 -验证校验位验证校验位 -错误位取反错误位取反9现在学习的是第9页，共47页6.4 线性分组码同时具有线性特性和分组特性把符号同时看成是运算的数把符号同时看成是运算的数引入模引入模2 2算术算术二元有限域有限个元素的集合，定义两种运算有限个元素的集合，定义两种运算加和乘加和乘加法有零元，乘法有幺元加法有零元，乘法有幺元有加逆元和乘逆元有加逆元和乘逆元加、乘满足结合律和交换律，加和乘满足分配加、乘满足结合律和交换律，加和乘满足分配律律 10现在学习的是第10页，共47页6.4 线性分组码加法加法 a+b乘法乘法 ab=c不可约不可约多项式多项式11现在学

5、习的是第11页，共47页6.4 线性分组码线性分组码的基本参数码码 长：长：n信息位长：信息位长：k码码 字字 数：数：M监督位长：监督位长：r最小码距：最小码距：dmin例例重复码重复码00011112现在学习的是第12页，共47页6.4 线性分组码（4，3）偶校验码）偶校验码例例例例例例 奇校验码？奇校验码？恒比码？恒比码？010110110113现在学习的是第13页，共47页 6.4 线性分组码衡量码的重要指标衡量码的重要指标 汉明重量（码重）汉明重量（码重）码字中非零码元的数目。码字中非零码元的数目。汉明重量（码重）汉明重量（码重）=例例1011010114现在学习的是第14页，共47

6、页6.4 线性分组码两个码字中相应码元取不同数值的码元数。两个码字中相应码元取不同数值的码元数。汉明距离（码距）汉明距离（码距）汉明距离（码距）汉明距离（码距）=1011010111010011例例15现在学习的是第15页，共47页 6.4 线性分组码 最小最小汉明距离（最小码距）汉明距离（最小码距）同一码所有汉明距离中最小的一个。同一码所有汉明距离中最小的一个。例例（4，3）偶校验码）偶校验码10010000001111001010111101010110最小汉明距离（最小码距）最小汉明距离（最小码距）=16现在学习的是第16页，共47页6.4 线性分组码检错和纠错能力检错和纠错能力1检错检

7、错l=dmin-12纠错纠错t=（dmin-1）/23l+t=dmin-1,tl最小汉明距离最小汉明距离 （最小码距（最小码距d d）：任意两码）：任意两码字之间的汉明距离的最小值字之间的汉明距离的最小值 17现在学习的是第17页，共47页6.4 线性分组码线性分组码检、纠错能力图示检、纠错能力图示18现在学习的是第18页，共47页0011001110101010110001106.4 线性分组码线性分组码检、纠错能力图示检、纠错能力图示19现在学习的是第19页，共47页汉明码简介6.4 线性分组码码码 长：长：n=2r-1信息位长：信息位长：k=n-r=2r-r-1码码 字字 数：数：M=2

8、k监督位长：监督位长：r=n-k最小码距：最小码距：dmin=3纠错能力：纠错能力：t=120现在学习的是第20页，共47页6.4 线性分组码线性分组码编码线性分组码编码信息矢量生成矩阵21现在学习的是第21页，共47页6.4 线性分组码一致校验方程组一致校验方程组校验矩阵22现在学习的是第22页，共47页6.4 线性分组码例例编码：编码：23现在学习的是第23页，共47页6.4 线性分组码译码（无差错）：译码（无差错）：24现在学习的是第24页，共47页6.4 线性分组码译码（有差错）：译码（有差错）：接收矢量接收矢量伴随式伴随式S可以指示差错的存在可以指示差错的存在25现在学习的是第25页

9、，共47页6.4 线性分组码例例26现在学习的是第26页，共47页 6.4 线性分组码伴随式s0s1s2错误位置错误图样101z01000000111z10100000110z20010000011z30001000100z40000100010z50000010001 z6000000127现在学习的是第27页，共47页 6.4 线性分组码译码步骤：译码步骤：1计算伴随式，构造伴随式计算伴随式，构造伴随式-差错图案表差错图案表（s，e）；）；2对接收向量计算伴随式；对接收向量计算伴随式；3查（查（s，e）表得）表得e；4纠错。纠错。28现在学习的是第28页，共47页 6.4 线性分组码系统码

10、系统码线性线性(N，k)码生成矩阵码生成矩阵G具有形式具有形式 由此产生的码称为系统码。系统码的一致监督由此产生的码称为系统码。系统码的一致监督矩阵具有形式矩阵具有形式二元有限域上的二元有限域上的-AT=AT码长为码长为N，信息位长度为，信息位长度为k的分组码称为的分组码称为(N，k)码。码。29现在学习的是第29页，共47页6.4 线性分组码线性分组码的性质线性分组码的性质 零向量零向量 是一个码字，称为零码字是一个码字，称为零码字 两码字之和或差仍是一个码字两码字之和或差仍是一个码字线性性线性性在码的所有码字上减去任一特定的在码的所有码字上减去任一特定的码字，结果仍是这同一码的全部码码字，

11、结果仍是这同一码的全部码字。字。对称性对称性二元有限域上最小码距二元有限域上最小码距 最小码重。最小码重。30现在学习的是第30页，共47页6.5 线性循环码汉明码的对偶码汉明码的对偶码线性循环码线性循环码例例31现在学习的是第31页，共47页（1）（3）（4）（2）（4）6.5 线性循环码32现在学习的是第32页，共47页6.5 线性循环码循环码的多项式描述循环码的多项式描述 g(x)一致校验多项式一致校验多项式编码编码译码译码33现在学习的是第33页，共47页 更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。6.5

12、.1 6.5.1 循环码的多项式描述循环码的多项式描述34现在学习的是第34页，共47页35现在学习的是第35页，共47页36现在学习的是第36页，共47页定义定义 如果一个线性分组码的任意一个码字如果一个线性分组码的任意一个码字c(n元组元组)都是另外一个码字都是另外一个码字c的循环移位的循环移位,称此线性分组码为一个循环码称此线性分组码为一个循环码.将循环码的码字用多项式将循环码的码字用多项式c(x)c(x)，称为码多项，称为码多项式（简称码式）表示后，循环码集合表示式（简称码式）表示后，循环码集合表示C(x),C(x),37现在学习的是第37页，共47页例 6.3.2 如下确定的如下确定

13、的C CA A是线性循环码，是线性循环码，C CB B是是非循环的线性分组码，非循环的线性分组码，C CC C是非线性的循环码。是非线性的循环码。，38现在学习的是第38页，共47页定理：定理：（n,k）循环码循环码C(x)中存在唯一的一个中存在唯一的一个非零的，首一的和最低次为非零的，首一的和最低次为r（rn）的码）的码 多项式多项式g(x)满足：满足：g(x)=xr+gr-1xr-1+.+g1X+g0 g00 r=n-k并且并且c(x)是码式当且仅当是码式当且仅当c(x)是是g(x)的倍式的倍式39现在学习的是第39页，共47页定义定义 由上述定理确定的码式由上述定理确定的码式g(x)g(

14、x)称称为循环码为循环码(n,k)(n,k)的的生成多项式生成多项式.因因此此(n,k)(n,k)循循环环码码的的构构造造是是如如何何构构造造生生成成多多项式项式g(x)g(x)。循环码由生成多项式的倍式组成循环码由生成多项式的倍式组成40现在学习的是第40页，共47页定理：定理：g(x)是（是（n,k）循环码的生成多项式）循环码的生成多项式，当且仅当当且仅当g(x)是是xn-1的的r=n-k次因式。次因式。41现在学习的是第41页，共47页42现在学习的是第42页，共47页43现在学习的是第43页，共47页44现在学习的是第44页，共47页6.3.1循环码的多项式描述循环码的多项式描述6.3.2 循环码的生成矩阵循环码的生成矩阵6.3.3系统循环码系统循环码6.3.4多项式运算电路多项式运算电路6.3.5循环码的编码电路循环码的编码电路6.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测6.3.7BCH码与码与RS码码45现在学习的是第45页，共47页6.3.2循环码的生成矩阵和校验矩阵(n,k)循环码的生成矩阵为循环码的生成矩阵为46现在学习的是第46页，共47页(n,k)循环码的校验矩阵为循环码的校验矩阵为47现在学习的是第47页，共47页