理学信道编码.pptx

《理学信道编码.pptx》由会员分享，可在线阅读，更多相关《理学信道编码.pptx（179页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基本概念l信源编码的目的是压缩冗余度，提高信息的传输速率。l信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术纠错编码技术。这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。第1页/共179页本章内容有扰离散信道的编码定理 纠错编译码的基本原理与分析方法线性分组码 卷积码编码与调制的结合TCM码运用级联、分集与信息迭代概念的纠错码第2页/共179页6.1信道编码的基本概念 一、差错图样（errorpat

2、tern）定量地描述信号的差错，收、发码之“差”：差错图样E发码C 收码R（模M）第3页/共179页差错类型差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示对于二进制传输系统，符号差错等效于比特差错；对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。第4页/共179页差错图样类型 随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错

3、码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。第5页/共179页二、纠错码分类 从功能角度：检错码、纠错码 码元与原始信息位的关系：线性码、非线性码 对信息序列的处理方法：分组码、卷积码差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码、几何码、算术码、组合码等 第6页/共179页三、差错控制系统分类 前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错 反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码 混合纠错（HEC）：前向纠错和反馈重发

4、的结合，发端发送的码兼有检错和纠错两种能力 第7页/共179页矢量空间与码空间 F表示码元所在的数域，对于二进制码，F代表二元域0,1，设n重有序元素的集合V=Vi,若满足条件：1、V中矢量元素在矢量加运算下构成加群；2、V中矢量元素与数域F元素的标乘封闭在V中；3、分配律、结合律成立，则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。第8页/共179页矢量空间与基底注意：1、n维矢量空间一定包含0矢量2、n维矢量空间中的各矢量可能线性无关，也可能线性相关第9页/共179页矢量空间中矢量的关系 对于域F上的若干矢量线性组合：线性相关：其中任一矢量可表示

5、为其它矢量的线性组合线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。第10页/共179页矢量空间与基底3、一组线性无关的矢量 ，线性组合的集合就构成了一个矢量空间V，这组矢量 就是这个矢量空间的基底。n维矢量空间应包含n个基底 基底不唯一第11页/共179页二元域GF(2)上三重矢量空间 以（100）为基底可张成一维三重子空间V1，含21=2 个元素，即以(010)(001)为基底可张成二维三重子空间V2，含 22=4个元素，即以(100)(010)(001)为基底可张成三维三重空间V,含 23=8个元素，V1和V2都是V的子空间。第12页/共179页矢量空间两个矢

6、量正交：V1V2 0 两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交 两个矢量空间的基底正交，则两个矢量空间正交正交的两个子空间V1、V2互为对偶空间(Dual Space)，其中一个空间是另一个空间的零空间（null space，也称零化空间）。第13页/共179页码空间 消息k长(n,k)码字n长 qk种分组编码器qn种k维k重矢量n维n重矢量通常通常qnqk，分组编码的任务是，分组编码的任务是要在要在n维维n重矢量空间的重矢量空间的qn种可能组合种可能组合中选择其中的中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码的其元素就是许用码的码集码集。第

7、14页/共179页分组编码的任务 选择一个维n重子空间作为码空间。确定由k维k重信息空间到维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。第15页/共179页随机编码运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。第16页/共179页在(N,K)分组编码器中随机选定的码集有qNM种 第m个码集(记作cm)被随机

8、选中的概率是设与这种选择相对应的条件差错概率是Pe(cm)全部码集的平均差错概率是第18页/共179页必定存在某些码集某些码集若 ，就必然存在一批码集 即差错概率趋于零的好码一定存在 第19页/共179页码集点数M=qK占N维矢量空间总点数qN的比例是F=qK/qN =q-(N-K)当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。当F0 即(N-K)时，能否让平均差错概率？Gallager在1965年推导了 的上边界，并证明这个上边界是按指数规律收敛的。第20页/共179页E(R)为可靠性函数，也叫误差指数 码率：R=(lbM

9、)/N M是可能的信息组合数，M=qKN是每码字的码元数，R表示每码元携带的信息量，单位是每符号比特（bit/symbol）第21页/共179页R在0,R0区间时E(R)R曲线是斜率 为-1（-45）的 直 线，E(R)反比于R；而当R=C时E(R)=0即可靠性为零。E(R)C R0R0-45 E(R)和和R的关系曲线的关系曲线第22页/共179页信道编码定理正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R C，就不可能有任何一种编码能使差错概率任意小。第23页/共179页第

10、六章：信道编码第六章：信道编码l信道编码的目标目标：提高通信的可靠性。1.信道编码概述l信道编码信道编码，就是按照一定的规则给信源编码后的码符号序列增加一些冗余信息，使其变成具有一定数学规律的码符号序列。l信道译码信道译码，就是按与信道编码器相同的数学规律去掉接收到的码符号序列中的冗余符号。l通常来说，增加的冗余符号越多，检错和纠错能力就越强。但是，增加的冗余符号越多，传输效率就越低。信道编码的相关概念第24页/共179页信道编码器：将信源编码后的符号加上冗余符号，提高传输的可靠性。第六章：有噪信道编码第六章：有噪信道编码1.信道编码概述（续1）信道编码的相关概念第25页/共179页第六章：有

11、噪信道编码第六章：有噪信道编码1.信道编码概述（续2）信道编码的相关概念图1编码信道模型信道编码器信道译码器信道第26页/共179页第六章：有噪信道编码第六章：有噪信道编码2.译码规则对错误概率的影响例1 1：二进制对称信道0101信道编码的相关概念第27页/共179页第六章：有噪信道编码第六章：有噪信道编码2.译码规则对错误概率的影响（续1）译码规则1：信道译码器收到符号“0”译为“0”信道译码器收到符号“1”译为“1”正确译码概率0.1，错误译码概率信道编码的相关概念0101第28页/共179页第六章：有噪信道编码第六章：有噪信道编码2.译码规则对错误概率的影响（续2）译码规则2：信道译码

12、器收到符号“0”译为“1”信道译码器收到符号“1”译为“0”信道编码的相关概念正确译码概率0.9，错误译码概率第29页/共179页第六章：有噪信道编码第六章：有噪信道编码定义6.1设信道的输入符号集为，输出符号集为。若对每一个输出符号都有一个确定的函数，使对应于唯一的一个输入符号，则称这样的一个函数为译码规则译码规则，记为3.译码规则XYx1x2xry1y2ysp(yj|xi)信道编码的相关概念第30页/共179页第六章：有噪信道编码第六章：有噪信道编码3.译码规则（续1）信道共有rs 种译码规则信道编码的相关概念第31页/共179页译码规则例：01013.译码规则（续2）第六章：有噪信道编码

13、第六章：有噪信道编码信道编码的相关概念第32页/共179页第六章：有噪信道编码第六章：有噪信道编码3.译码规则（续3）例2：设一个信道的信道矩阵为，根据此信道矩阵，设计译码规则。解：译码规则A译码规则B信道编码的相关概念第33页/共179页对于有r个输入符号，s个输出符号的信道，总共可以设计出种译码规则，到底哪一种译码规则最好哪一种译码规则最好？依据什么标准什么标准来选择译码规则？问题：3.译码规则（续4）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第34页/共179页4.错误译码概率l设译码规则为当输入符号是xi时，译码正确当输入符号为除xi以外的(r-1)种符号时，译码错误正

14、确译码的概率：错误译码的概率：第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第35页/共179页4.错误译码概率（续1）l平均正确译码概率：l平均错误译码概率：第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第36页/共179页5.两种重要的译码规则为提高规则通信的可靠性，所采用的译码应当使平均错误译码概率最小。-最大后验概率译码规则最常用的译码规则，包括：极大似然译码规则最大后验概率译码规则第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第37页/共179页5.两种重要的译码规则（续1）(1 1)最大后验概率译码规则已知：当求和项中的每一项都达到最小值时，就最

15、小。要最小。要最大。第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第38页/共179页定义6.2令，而应满足条件5.两种重要的译码规则（续2）称满足上述条件的译码函数对应的译码规则为最大后验概率译码规则。第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第39页/共179页5.两种重要的译码规则（续3）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第40页/共179页5.两种重要的译码规则（续4）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第41页/共179页5.两种重要的译码规则（续5）问题：最大后验概率通常是未知的，使用不方便。我们能否推导出更

16、便于使用的译码规则?第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第42页/共179页5.两种重要的译码规则（续6）当输入符号等概分布时(2 2)极大似然译码规则第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第43页/共179页第六章：有噪信道编码第六章：有噪信道编码5.两种重要的译码规则（续7）1)当输入符号等概分布时，采用极大似然译码准则等价于最大后验概率准则。2)当输入符号不等概分布或先验概率未知时，采用极大似然译码准则不一定使 最小。l 关于极大似然译码准则：第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第44页/共179页5.两种重要的译码规则（续

17、8）当输入符号等概分布时第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第45页/共179页5.两种重要的译码规则（续9）例3：设信道矩阵为，且输入符号等概分布，即，求译码规则和平均错误译码概率。第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第46页/共179页5.两种重要的译码规则（续10）解：因为输入符号为等概分布，所以由最大似然译码规则可得译码规则第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第47页/共179页5.两种重要的译码规则（续11）译码规则A译码规则B例6.3假设输入等概，求以下两种译码规则的平均错误译码概率。第六章：有噪信道编码第六章：有噪

18、信道编码信道编码的相关概念第48页/共179页5.两种重要的译码规则（续12）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第49页/共179页5.两种重要的译码规则（续13）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第50页/共179页5.两种重要的译码规则（续14）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第51页/共179页6.Fano不等式l定理6.1平均错误概率与信道疑义度H(X|Y)满足不等式：第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第52页/共179页01017.简单重复编码第六章：有噪信道编码第六章：有噪信道编码信道

19、编码的相关概念第53页/共179页7.简单重复编码（续1）二元对称信道的三次扩展信道M=2第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第54页/共179页由最大似然译码规则，可得7.简单重复编码（续2）自动纠正一位错第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第55页/共179页7.简单重复编码（续3）l在输入符号集（M个符号）等概的条件下，每个符号平均携带的最大信息量是。l当用n个码元符号来传输M个信源符号时，每个码符号携带的平均信息量，即信道信息传输率为：l不重复编码时(n=1)，l重复编码时(n=3)，第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念

20、第56页/共179页n=1,R=1,n=3,R=1/3,n=5,R=1/5,n=7,R=1/7,n=9,R=1/9,n=11,R=1/11,增加重复次数n，可使减小很多，但信息传输率R也减少很多。7.简单重复编码（续4）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第57页/共179页7.简单重复编码（续5）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念l如果在扩展信源的 个码符号序列中任意选择M个序列作为信道的输入，以代表M个信源消息。第58页/共179页l 因此若选择“000000”和“001001”代表消息“0 0”和“1 1”，则 7.简单重复编码（续6）第六章

21、：有噪信道编码第六章：有噪信道编码信道编码的相关概念第59页/共179页l有没有一种很简便的方法，帮我们选择平均错误概率最小的M个序列？7.简单重复编码（续7）第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第60页/共179页8.汉明距离1）汉明距离2）码的最小距离3）汉明距离与极大似然译码准则第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第61页/共179页8.汉明距离（续1）定义6.4设和表示两个长度为n的码符号序列，定义称为码字和之间的汉明距离。1）汉明距离第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第62页/共179页8.汉明距离（续2）例4：求下

22、面两个码字之间的汉明距离。解：第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第63页/共179页8.汉明距离（续3）定义6.5在二元码C中，任意两个码字之间的汉明距离的最小值，被称为码C的最小距离：2）码的最小距离第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第64页/共179页8.汉明距离（续4）例5：设有n=3的两组码，分别求它们的最小汉明距离。解：码的最小汉明距离为码的最小汉明距离为第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念第65页/共179页码1码2码3码4码5码600011100000100001110111000000110001000000

23、011011011111010000001010011100101110111第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念8.汉明距离（续5）第66页/共179页码1码2码3码4码5码字00011100001110111000000110001000000011011011111010000001010011100101110111消 息 数M24448信 息 传输率R1/32/32/32/51码的最小距离32131平均错误概率（最大似然译码）第67页/共179页8.汉明距离（续7）结论：码的最小距离越大，平均译码错误概率越小。第六章：有噪信道编码第六章：有噪信道编码信道编码的相

24、关概念第68页/共179页设和表示两个长度为n的码符号序列，为信道的输入，为信道的输出。和的汉明距离为D。8.汉明距离（续8）3)汉明距离与极大似然译码准则对于离散平稳无记忆二元对称信道，有第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念通常情况下，D越小，就越大。第69页/共179页8.汉明距离（续9）根据极大似然译码准则，极大似然译码准则就等价于，当接收到一个长为n的码符号序列时，在输入码字集中寻找一个，使第六章：有噪信道编码第六章：有噪信道编码信道编码的相关概念最小距离译码准则第70页/共179页1.有噪信道编码定理定理6.2（香农第二定理）设有一离散无记忆平稳信道，其信道容量

25、为C，只要待传送的信息传输率RC，即，则无论码长n 取多大，也不可能使译码错误概率任意小。第六章：有噪信道编码第六章：有噪信道编码有噪信道编码定理第73页/共179页1.有噪信道编码定理（续3）信道容量是在信道中可靠传输信息的最大信息传输率。结论：第六章：有噪信道编码第六章：有噪信道编码有噪信道编码定理第74页/共179页2.错误概率的上界第六章：有噪信道编码第六章：有噪信道编码有噪信道编码定理第75页/共179页纠错编码纠错编码1 1 纠错码的分类纠错码的分类2 2 纠错码的基本概念纠错码的基本概念 3 3 线性分组码线性分组码 4 4 汉明码汉明码 5 5 循环码循环码*6 *6 卷积码卷

26、积码第76页/共179页概述概述l 香农第二定理证明，当 时 的码存在。l 证明过程采用的是随机编码的方法：随机编码所得的码集很大，通过搜索得到好码的方法在实际上很难实现；即使找到了好码，这种码的码字也没有规律，不便于译码。l 真正实用的信道编码方法还需要通过各种数学工具来构造，使码具有好的结构性以便于译码。第77页/共179页l 近世代数是信道编码理论用到的最重要的数学工具，它包括群论、环论、域论、格论、线性代数等许多分支。l 广义信道编码包括：调制、成形滤波、扩频、上下变频等。l 纠错编码是提高传输可靠性的最主要的措施之一。概述概述第78页/共179页l 纠错编码的基本思路：根据一定的规律

27、在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规则相互关联（约束）。在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。概述概述第79页/共179页E概述概述mmsgCcodeRnoisycodenewmsg第80页/共179页干扰一般分为两种形式：一是随机噪声，它主要来源于设备的热噪声和散弹噪声以及传播媒介的热噪声，它是通信系统中的主要噪声；二是脉冲干扰和信道衰落，它的特点是突发出现，主要来源于雷电、通电开关、负荷突变或设备故障等。概述概述第81页/共179页信道

28、可分为三类：1.只产生随机错误的信道称为随机信道。比如卫星信道、同轴电缆、光缆信道以及大多数微波中继信道。2.产生突发错误的信道称为突发信道。实际的短波信道、移动通信信道、由于擦伤造成成串差错的光盘和磁盘，均为这一类信道。3.有些实际信道既有随机错误又有突发错误，称为混合信道。根据不同的信道类型设计的信道编码分为纠随机错误码、纠突发错误码和纠混合错误码。概述概述第82页/共179页在通信系统中，纠检错的工作方式有：(1)反馈重传(ARQ)(2)前向纠错(FEC)(3)混合纠错概述概述第83页/共179页 发送端经编码后发出能够发现错误的码，接收端收到后经检验，如果发现传输中有错误，则通过反馈系

29、统把这一判断结果反馈回发端，然后发送端把前面发出的信息重新传送一次，直到接收端认为正确地收到信息为止。(1)反馈重传(ARQ)检错编码信道检错译码反馈概述概述第84页/共179页(2)前向纠错(FEC)纠错编码信道纠错译码 发送端发出的是具有纠错能力的纠错码，接收端根据译码规则进行译码。当误码个数在码的纠错能力范围内时，译码器可以自动纠正错误。概述概述第85页/共179页特点：1 1）前向纠错方式不需要反馈信道，特别适合于只能 提供单向信道的场合。2 2）由于能自动纠错，不要求检错重发，因而延时小，实时性好。3 3）随着纠错能力的增强，译码设备也变得复杂。概述概述第86页/共179页(3)混合

30、纠错 对发送端进行适当的编码。当错误不严重，在码的纠错能力范围之内时，采用自动纠错；当产生的差错超出码的纠错能力范围时，通过反馈系统要求发端重发。概述概述第87页/共179页(1)按功能分：检错码：仅能检测误码纠错码：可纠正误码 纠删码：兼纠错和检错能力(2)按信息码元与监督码元之间的检验关系分：线性码：满足线性关系 非线性码：不存在线性关系 纠错码1 1 纠错码的分类纠错码的分类第88页/共179页(3)按信息码元与监督码元之间的约束方式不同分：分组码：本码组的监督码元仅和本码组的信息元相关。树码：本码组的监督码元不仅和本码组的信息元相关，而且与前面码组的信息码元有关。如果是线性关系则称为卷

31、积码。(4)按信息码元在编码后是否保持原形式不变：系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持不变；非系统码：信息位打乱，与编码前不同。1 1 纠错码的分类纠错码的分类第89页/共179页(5)(5)按纠正差错的类型可分为：纠随机错误码纠突发错误码纠随机和突发错误码1 1 纠错码的分类纠错码的分类第90页/共179页纠错码按结构分类如下：纠错码按结构分类如下：1 1 纠错码的分类纠错码的分类第91页/共179页l分组码的表示方法：（二元分组码）信息码组由k 个信息码元（信息位）组成，共有2k 个不同的信息码组；附加 个校验码元（校验位或监督位），每个校验码元是该信息码组的

32、某些信息码元模2和；编码器输出长度为n的码字；码字的数目共有2k；这2k个码字的集合称为(n,k)分组码；2 2 纠错码的基本概念纠错码的基本概念第92页/共179页对 二进制(n,k)线性分组码，合法码字数为2k，可用编码空间的序列数为2n个。许用序列，禁用序列任一种2k信息集合到二进制序列集合(2n)的映射都是一种(n,k)码，因此总共可能的编码方案有 种。2 2 纠错码的基本概念纠错码的基本概念l信息传输率（码率）l编码效率第93页/共179页发现或构造好码是信道编码研究的主要问题。线性分组码是最具实用价值的一类码，比如汉明码、循环码、BCH码、RS码等。2 2 纠错码的基本概念纠错码的

33、基本概念第94页/共179页2 2 纠错码的基本概念纠错码的基本概念对信道编码的一般要求是：纠错检错能力强；信息传输率高；编码规律简单，实现设备简单且费用合理；与信道的差错统计特性相匹配。第95页/共179页汉明距离汉明距离满足距离公理汉明距离满足距离公理(1)非负性非负性(2)对称性对称性(3)三角不等式三角不等式2 2 纠错码的基本概念纠错码的基本概念第96页/共179页汉明重量码C的最小距离线性分组码的最小距离等于非零码字的最小重量。2 2 纠错码的基本概念纠错码的基本概念第97页/共179页码1码2码3码4码5码6000111000001000011101110000001100010

34、000000110110111110100000010100111001011101112 2 纠错码的基本概念纠错码的基本概念第98页/共179页3 3 线性分组码线性分组码3.1校验矩阵与生成矩阵(1)校验矩阵第99页/共179页3 3 线性分组码线性分组码第100页/共179页l被称为校验矩阵。l对线性分组码，校验矩阵为维矩阵。l对于系统码，校验矩阵可以表示为其中为维矩阵，为维单位矩阵。3 3 线性分组码线性分组码第101页/共179页由校验方程，得到(2)生成矩阵3 3 线性分组码线性分组码第102页/共179页令3 3 线性分组码线性分组码第103页/共179页其中为维矩阵，为维单位

35、矩阵。l被称为生成矩阵。l对线性分组码，生成矩阵为维矩阵。l对于系统码，生成矩阵可以表示为3 3 线性分组码线性分组码第104页/共179页l把生成矩阵的每一行用一个行向量来表示，则生成矩阵可以表示为l令，则3 3 线性分组码线性分组码第105页/共179页l由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足 ，则有l对于标准形式的校验矩阵和监督矩阵，有(3)校验矩阵和生成矩阵的关系3 3 线性分组码线性分组码第106页/共179页l线性分组码的封闭性：线性分组码中任意两个码字之和仍然是该码的码字。证明：设 和 分别是码 中的两个码字，因此有即 满足监督方程，所以是码 中的一个码字。3

36、3 线性分组码线性分组码第107页/共179页例1：3重复码是一个（3,1）线性分组码。其生成矩阵为3 3 线性分组码线性分组码第108页/共179页例2：（4,3）偶校验码是一个（4,3）线性分组码，其生成矩阵为3 3 线性分组码线性分组码第109页/共179页例3：已知生成矩阵为求生成的线性分组码及由H生成的线性分组码。3 3 线性分组码线性分组码第110页/共179页3 3 线性分组码线性分组码第111页/共179页111111111111001110111000111011101010110011000001011101101110101010110100110011011000100

37、00100111011100101100110100010101011110100010010100110011110001000100110001000100000000000Cm3 3 线性分组码线性分组码第112页/共179页3.2线性分组码的纠、检错能力对于一个二进制对称信道，当输入为2k个等可能的n长码字，则最大后验概率准则等效于最小汉明距离译码准则。3 3 线性分组码线性分组码第113页/共179页关于码的最小距离与纠、检错能力的关系有以下结论：对于（n，k）线性分组码，设为码的最小距离则（）这组码有纠正u 个错误的充要条件是uu2u+13 3 线性分组码线性分组码第114页/共1

38、79页lll+1（）具有检测l个错误的充要条件是3 3 线性分组码线性分组码第115页/共179页ulu+l+1（）具有纠正u 个错误，同时可以发现l个错误的充分必要条件为3 3 线性分组码线性分组码第116页/共179页码的纠错能力u与码字的长度n和消息数M满足以下关系：3 3 线性分组码线性分组码第117页/共179页3.3校验矩阵与码的最小距离的关系对于（n，k）线性分组码：校验矩阵H中的任意t列线性无关而t+1列线性相关，则码的最小距离(码字的最小重量)为t+1。反过来说，若码的最小距离(码字的最小重量)为t+1则H的任意t列线性无关而t+1列线性相关。3 3 线性分组码线性分组码第1

39、18页/共179页3.4线性分组码的伴随式R=C+EE=e1e2en1)，说明R 是一个码字;2)2)，说明R 不是码字，传输过程产生了误码。3 3 线性分组码线性分组码第119页/共179页例：某（5,2）系统线性码的生成矩阵是设收码是，问它是否是码字。3 3 线性分组码线性分组码第120页/共179页令则（其中表示的列向量）3 3 线性分组码线性分组码结论：1)当传输过程没有错误时，即，2)2)当发生一位错误时，是校验矩阵的某一列。3)3)当发生多个错误时，为校验矩阵对应列的模2 2和。第121页/共179页例：设(7,3)线性分组码的校验矩阵为3 3 线性分组码线性分组码第122页/共1

40、79页（1）接收码字R=(1010011)，传输过程中没有误码，3 3 线性分组码线性分组码第123页/共179页（2）接收码字R=(1110011)，第2位出错，3 3 线性分组码线性分组码第124页/共179页（3）接收码字R=(0011011)，与中的任一列都不相同，不能确定到底是哪两位出错，不能正确译码。3 3 线性分组码线性分组码第125页/共179页线性分组码的伴随式译码3 3 线性分组码线性分组码第126页/共179页3 3 线性分组码线性分组码第127页/共179页若（n，k）线性分组码能够纠正u 个错误，则其校验位的数目必须满足4汉明码上式等号成立则称为完备码如果是能纠正一位

41、错误的完备码则第128页/共179页完备码具有下述特性：（1）以每个发送码字为球心，以u为半径画一个球，那么每一个接收码字都落在其中一个球中，因此接收码字与发送码字的距离至多为u；（2）所有差错数小于等于u的接收码字都能得到纠正；（3）差错数大于等于u+1的接收码字，因为落在另一个球内被纠正为其他的发送码字。完备码并不多见，我们知道的有u=1的汉明码、u=3的高莱码，以及(n,1)中n为奇数的重复码等。4汉明码第129页/共179页完备码非完备码000111000001010100111110101011000000110100000000010001000100010001000000011

42、1001101101011000111101001001011110101110111001011110111.1101011010.4汉明码第130页/共179页l汉明码是一种能够纠正单个错误的完备码。汉明码最小码距设监督码共有r 位，对于汉明码必然有。通常汉明码可以表示成。4汉明码在同样的纠错能力下，汉明码的码率是最高的第131页/共179页l汉明码监督矩阵构成的两种方式：按r 位的二进制数的自然顺序从左到右排列（不包括全0列）。当发生可纠的单个错误时，伴随式为H 阵中对应的列，译码比较方便。构成H H 阵的标准形式，。非标准形式的监督矩阵可以通过列置换变成标准形式的监督矩阵，纠错能力保持

43、不变。4汉明码第132页/共179页例：构造一个r=3的二元（7,4）汉明码解：r=3的汉明码，列置换4汉明码第133页/共179页4汉明码第134页/共179页信息比特码字（循环1）信息比特码字（循环2）信息比特码字000100100101011010001011110000010110010110010110001100011000101101100011000100011010001111001101011011110001110101001110111010100111010100111101001111010000001111000000011111114汉明码第135页/共179页

44、l如果给汉明码添加一位奇偶校验位，可得到扩展汉明码：信息位保持不变，监督位增加一位。最小码距，可纠正一位错误，同时发现两位错误。l扩展汉明码的监督方程：4汉明码第136页/共179页复习一个码字的汉明重量就是一个码字中非零码元的个数,记为W(c)。W(1010101)=4。定理：设(n,k)(n,k)为线性分组码,则它的所有非零码字的重量的最小值w wminmin,称为最小重量,等于最小距离,即w wminmin=d=dminmin。什么是线性分组码?同时具有分组特性和线性特性的纠错码。第137页/共179页线性分组码的线性分组码的G,H,EG,H,EG,H,EG,H,E设线性分组码(n,k)

45、(n,k)的系统码的生成矩阵为 ,n=k+r ,n=k+r。校验矩阵H H为r rnn矩阵,满足:cH:cHT T=0=0 或 HcHcT T=0.=0.其中c c=(c=(c1 1,c,c2 2,c,c3 3,c,c4 4,c,c5 5,c,c6 6)为码字,Q ,Q为rkrk矩阵。因为G G的每行都是码字,故 GHGHT T=0=0 或HGHGT T=0,=0,从而有Q QT T+P=0 +P=0 故 P=QP=QT T 或 Q=PQ=PT T第138页/共179页校验矩阵H的性质:(1)H与生成矩阵G可以相互转化。(2)利用H和式cHT=0判别是否码字。(3)H中列的线性相关性与纠错能力

46、有关系。第139页/共179页m4m3m2m1ci7ci6ci50001101输入编码器用编码器用4 4级移位寄存器和级移位寄存器和7 7-4=34=3个模个模2 2加法器组成加法器组成,加法器生成加法器生成校验位后按顺序暂存在另一个长度为校验位后按顺序暂存在另一个长度为7-47-4的移位寄存器中的移位寄存器中,先是先是4 4位信息位位信息位,然后是然后是7-47-4位校验比特从两个寄存器中移出位校验比特从两个寄存器中移出.（）6 6.2 2线线性性分分组组码码第140页/共179页5 循环码信息信息信息信息比特比特比特比特码字码字码字码字（循环（循环（循环（循环1 1）信息信息信息信息比特比

47、特比特比特码字码字码字码字（循环（循环（循环（循环2 2）信息信息信息信息比特比特比特比特码码码码 字字字字00010001001000100101010101100110100010001011101111001100000000101110110000101110110 00 01011101100000 011110000001 11 100000010110110111011000000111100000010100011001101000100011101111001100110101010110111011110111000001111110101010001001111110 0

48、1111110100101001001111110 01 10100010011111111010001001 11111110100010000000000111111110000000000000011111111111111第141页/共179页l循环码是线性分组码的一个重要子集。l循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一码字经过循环移位后，所得到的码字仍然是该码的码字。l循环码有严密的代数学理论基础，检错和纠错能力较强，而且编码和解码设备都不太复杂。5 循环码第142页/共179页1)对于二进制码，码多项式的每个系数不是0就是1。2)仅是码元位置的标记。我们并不

49、关心的取值。l设循环码的码字为，用码多项式表示为l码字（1100101）可以表示为：5 循环码第143页/共179页5 循环码第144页/共179页循环码的循环特性可以用码多项式来证明：l在整数运算中，有模n运算。若一个整数m可以表示为:则在模n运算下，一整数m等于其被n除所得的余数。5 循环码第145页/共179页l在码多项式运算中也有类似的按模运算法则。若一任意多项式M(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n 的余式P(x)，也就是：则可以写为：l在循环码中，若 是一个长为n的许用码字，则在模运算下，也是一个许用码字。5 循环码第146页/共179页例:某循环码的

50、一个码字为1100101，则若将此码左移一位，得：对应的码字为1001011(即将码字1100101循环左移一位）。5 循环码第147页/共179页信息比特码字（循环1）信息比特码字（循环2）信息比特码字000100100101011010001011110000010110010110010110001100011000101101100011000100011 010001111001101011011110001110101001110111010100111010100111101001111010000001111000000011111115 循环码第148页/共179页l从码中取