[理学]第六章_信道编码.ppt

第六章：有噪信道编码,一、信道编码的相关概念,二、有噪信道编码定理,三、纠错编码,基本概念,l信源编码的目的是压缩冗余度，提高信息的传输速率。,l信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。,香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术纠错编码技术。 这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。,本章内容,有扰离散信道的编码定理 纠错编译码的基本原理与分析方法 线性分组码 卷积码 编码与调制的结合TCM码 运用级联、分集与信息迭代概念的纠错码,6.1 信道编码的基本概念,一、差错图样（error pattern） 定量地描述信号的差错，收、发码之“差” ： 差错图样E发码C 收码R （模M）,差错类型,差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示 差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示 对于二进制传输系统，符号差错等效于比特差错； 对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。,差错图样类型,随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特； 突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。,二、纠错码分类,从功能角度：检错码 、纠错码 码元与原始信息位的关系：线性码、非线性码 对信息序列的处理方法：分组码、卷积码 差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。 构码理论：代数码、几何码、算术码、组合码等,三、差错控制系统分类,前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错 反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码 混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力,6.1.2矢量空间与码空间,F表示码元所在的数域，对于二进制码，F代表二元域0,1，设n重有序元素的集合V= Vi , 若满足条件： 1、V中矢量元素在矢量加运算下构成加群； 2、V中矢量元素与数域F元素的标乘封闭在V中； 3、分配律、结合律成立， 则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。,矢量空间与基底,注意： 1、n维矢量空间一定包含0矢量 2、n维矢量空间中的各矢量可能线性无关，也可能线性相关,矢量空间中矢量的关系,对于域F上的若干矢量 线性组合： 线性相关： 其中任一矢量可表示为其它矢量的线性组合 线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。,矢量空间与基底,3、一组线性无关的矢量 ，线性组合的集合就构成了一个矢量空间V，这组矢量 就是这个矢量空间的基底。 n维矢量空间应包含n个基底 基底不唯一,二元域GF(2)上三重矢量空间,以（100）为基底可张成一维三重子空间V1，含21 =2 个元素，即 以(010)(001)为基底可张成二维三重子空间V2，含 22 =4个元素，即 以(100)(010)(001)为基底可张成三维三重空间V,含 23 =8个元素，V1和V2都是V的子空间。,矢量空间,两个矢量正交：V1V2 0 两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交 两个矢量空间的基底正交，则两个矢量空间正交 正交的两个子空间V1、V2互为对偶空间 (Dual Space)，其中一个空间是另一个空间的零空间（null space，也称零化空间）。,码空间,消息k长 (n , k) 码字n长,qk 种 分组编码器 qn种 k维k重矢量 n维n重矢量,通常qn qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。,分组编码的任务,选择一个维n重子空间作为码空间。 确定由k维k重信息空间到维n重码空间的映射方法。 码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。,6.1.3随机编码,运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作随机码界。 用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。,Shannon method for proving one baby weighs less than 10 kg,在(N,K)分组编码器中随机选定的码集有qNM种 第m个码集(记作cm )被随机选中的概率是 设与这种选择相对应的条件差错概率是Pe(cm) 全部码集的平均差错概率是,必定存在某些码集 某些码集 若 ，就必然存在一批码集 即差错概率趋于零的好码一定存在,码集点数M=qK占N维矢量空间总点数qN的比例是 F =qK / qN = q-(N-K) 当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。 当F0 即(N-K)时，能否让平均差错概率 ？ Gallager在1965年推导了 的上边界，并证明这个上边界是按指数规律收敛的。,E(R)为可靠性函数，也叫误差指数 码率：R =(lbM ) / N M是可能的信息组合数，M=qK N是每码字的码元数， R表示每码元携带的信息量，单位是每符号比特（bit / symbol）,R在0,R0区间时E(R)R曲线是斜率为-1（-45）的直线，E(R)反比于R；而当R=C时E(R)=0即可靠性为零。,6.1.4信道编码定理,正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。 逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R C，就不可能有任何一种编码能使差错概率任意小。,第六章：信道编码,信道编码的目标：提高通信的可靠性。,1. 信道编码概述,信道编码，就是按照一定的规则给信源编码后的码符号序列增加一些冗余信息，使其变成具有一定数学规律的码符号序列。,信道译码，就是按与信道编码器相同的数学规律去掉接收到的码符号序列中的冗余符号。,通常来说，增加的冗余符号越多，检错和纠错能力就越强。但是，增加的冗余符号越多，传输效率就越低。,信道编码的相关概念,信道编码器： 将信源编码后的符号加上冗余符号，提高传输的可靠性。,第六章：有噪信道编码,1. 信道编码概述（续1）,信道编码的相关概念,第六章：有噪信道编码,1. 信道编码概述（续2）,信道编码的相关概念,图1 编码信道模型,信道 编码器,信道 译码器,信道,第六章：有噪信道编码,2. 译码规则对错误概率的影响,例1：,二进制对称信道,信道编码的相关概念,第六章：有噪信道编码,2. 译码规则对错误概率的影响（续1）,译码规则1：,信道译码器收到符号“0”译为“0” 信道译码器收到符号“1”译为“1” 正确译码概率0.1，错误译码概率,信道编码的相关概念,第六章：有噪信道编码,2. 译码规则对错误概率的影响（续2）,译码规则2：,信道译码器收到符号“0”译为“1” 信道译码器收到符号“1”译为“0”,信道编码的相关概念,正确译码概率0.9，错误译码概率,第六章：有噪信道编码,定义6.1 设信道的输入符号集为 ，输出符号集为 。若对每一个输出符号都有一个确定的函数 ，使对应于唯一的一个输入符号 ，则称这样的一个函数为译码规则，记为,3. 译码规则,信道编码的相关概念,第六章：有噪信道编码,3. 译码规则（续1）,信道,共有rs 种译码规则,信道编码的相关概念,译码规则,例：,3. 译码规则（续2）,第六章：有噪信道编码,信道编码的相关概念,第六章：有噪信道编码,3. 译码规则（续3）,例2：设一个信道的信道矩阵为 ，根据此信道矩阵，设计译码规则。,解：,译码规则A,译码规则B,信道编码的相关概念,对于有r个输入符号，s个输出符号的信道，总共可以设计出 种译码规则，到底哪一种译码规则最好？依据什么标准来选择译码规则？,问题：,3. 译码规则（续4）,第六章：有噪信道编码,信道编码的相关概念,4. 错误译码概率,设译码规则为,当输入符号是xi时，,译码正确,当输入符号为除xi以外的(r-1)种符号时，,译码错误,正确译码的概率：,错误译码的概率：,第六章：有噪信道编码,信道编码的相关概念,4. 错误译码概率（续1）,平均正确译码概率：,平均错误译码概率：,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则,为提高规则通信的可靠性，所采用的译码应当使平均错误译码概率最小。- 最大后验概率译码规则 最常用的译码规则，包括：,极大似然译码规则,最大后验概率译码规则,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续1）,(1) 最大后验概率译码规则,已知：,当求和项中的每一项都达到最小值时， 就最小。,要最小。,要最大。,第六章：有噪信道编码,信道编码的相关概念,定义6. 2 令 ， ，而 应满足条件,5. 两种重要的译码规则（续2）,称满足上述条件的译码函数对应的译码规则为最大后验概率译码规则。,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续3）,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续4）,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续5）,问题：,最大后验概率 通常是未知的，使用不方便。我们能否推导出更便于使用的译码规则?,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续6）,当输入符号等概分布时,(2) 极大似然译码规则,第六章：有噪信道编码,信道编码的相关概念,第六章：有噪信道编码,5. 两种重要的译码规则（续7）,1)当输入符号等概分布时，采用极大似然译码准则等价于最大后验概率准则。,2)当输入符号不等概分布或先验概率未知时，采用极大似然译码准则不一定使 最小。,关于极大似然译码准则：,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续8）,当输入符号等概分布时,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续9）,例3： 设信道矩阵为 ，且输入符号等概分布，即 ，求译码规则和平均错误译码概率。,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续10）,解： 因为输入符号为等概分布，所以由最大似然译码规则可得,译码规则,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续11）,译码规则 A,译码规则 B,例 6.3 假设输入等概，求以下两种 译码规则的平均错误译码概率。,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续12）,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续13）,第六章：有噪信道编码,信道编码的相关概念,5. 两种重要的译码规则（续14）,第六章：有噪信道编码,信道编码的相关概念,6. Fano不等式,定理6.1 平均错误概率与信道疑义度H(X|Y)满足不等式：,第六章：有噪信道编码,信道编码的相关概念,7. 简单重复编码,第六章：有噪信道编码,信道编码的相关概念,7. 简单重复编码（续1）,二元对称信道 的三次扩展信道,M =2,第六章：有噪信道编码,信道编码的相关概念,由最大似然译码规则，可得,7. 简单重复编码（续2）,自动纠正一位错,第六章：有噪信道编码,信道编码的相关概念,7. 简单重复编码（续3）,在输入符号集（M个符号）等概的条件下，每个符号平均携带的最大信息量是 。 当用n个码元符号来传输M个信源符号时，每个码符号携带的平均信息量，即信道信息传输率为：,不重复编码时(n=1)， 重复编码时(n=3)，,第六章：有噪信道编码,信道编码的相关概念,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）,第六章：有噪信道编码,信道编码的相关概念,7. 简单重复编码（续5）,第六章：有噪信道编码,信道编码的相关概念,如果在扩展信源的 个码符号序列中任意选择M个序列作为信道的输入，以代表M个信源消息。,因此若选择“000”和“001”代表消息“0”和“1”，则,7. 简单重复编码（续6）,第六章：有噪信道编码,信道编码的相关概念,有没有一种很简便的方法，帮我们选择平均错误概率最小的M个序列？,7. 简单重复编码（续7）,第六章：有噪信道编码,信道编码的相关概念,8. 汉明距离,1）汉明距离,2）码的最小距离,3）汉明距离与极大似然译码准则,第六章：有噪信道编码,信道编码的相关概念,8. 汉明距离（续1）,定义6.4 设 和 表示两个长度为n的码符号序列，定义,称 为码字 和 之间的汉明距离。,1）汉明距离,第六章：有噪信道编码,信道编码的相关概念,8. 汉明距离（续2）,例4：求下面两个码字之间的汉明距离。,解：,第六章：有噪信道编码,信道编码的相关概念,8. 汉明距离（续3）,定义6.5 在二元码C中，任意两个码字之间的汉明距离的最小值，被称为码C的最小距离：,2）码的最小距离,第六章：有噪信道编码,信道编码的相关概念,8. 汉明距离（续4）,例5：设有n=3的两组码，分别求它们的最小汉明距离。,解：,码 的最小汉明距离为,码 的最小汉明距离为,第六章：有噪信道编码,信道编码的相关概念,第六章：有噪信道编码,信道编码的相关概念,8. 汉明距离（续5）,8. 汉明距离（续7）,结论：,码的最小距离越大，平均译码错误概率越小。,第六章：有噪信道编码,信道编码的相关概念,设 和 表示两个长度为n的码符号序列， 为信道的输入， 为信道的输出。 和 的汉明距离为D。,8. 汉明距离（续8）,3) 汉明距离与极大似然译码准则,对于离散平稳无记忆二元对称信道，有,第六章：有噪信道编码,信道编码的相关概念,通常情况下， ， ，D越小， 就越大。,8. 汉明距离（续9）,根据极大似然译码准则，,极大似然译码准则就等价于，当接收到一个长为n的码符号序列 时，在输入码字集中寻找一个 ，使,第六章：有噪信道编码,信道编码的相关概念,最小距离译码准则,1. 有噪信道编码定理,定理6.2 （香农第二定理） 设有一离散无记忆平稳信道，其信道容量为C，只要待传送的信息传输率RC，当码长 n 足够大时，则至少存在一种编码，使译码错误概率任意小。,第六章：有噪信道编码,有噪信道编码定理,1. 有噪信道编码定理（续1）,说明：,1) 信息传输速率 2) 香农第二定理仅指出了满足这种要求的信道编码的存在性，没有给出具体的编码方法。,第六章：有噪信道编码,有噪信道编码定理,1. 有噪信道编码定理（续2）,定理6.3 （有噪信道编码逆定理）,设有一离散无记忆平稳信道，其信道容量为C，如果信息传输率RC，即 ，则无论码长 n 取多大，也不可能使译码错误概率任意小。,第六章：有噪信道编码,有噪信道编码定理,1. 有噪信道编码定理（续3）,信道容量是在信道中可靠传输信息的最大信息传输率。,结论：,第六章：有噪信道编码,有噪信道编码定理,2. 错误概率的上界,第六章：有噪信道编码,有噪信道编码定理,纠错编码,1 纠错码的分类,2 纠错码的基本概念,3 线性分组码,4 汉明码,5 循环码,*6 卷积码,概述,香农第二定理证明，当 时 的码存在。 证明过程采用的是随机编码的方法： 随机编码所得的码集很大，通过搜索得到好码的方法在实际上很难实现； 即使找到了好码，这种码的码字也没有规律，不便于译码。 真正实用的信道编码方法还需要通过各种数学工具来构造，使码具有好的结构性以便于译码。,近世代数是信道编码理论用到的最重要的数学工具，它包括群论、环论、域论、格论、线性代数等许多分支。 广义信道编码包括：调制、成形滤波、扩频、上下变频等。 纠错编码是提高传输可靠性的最主要的措施之一。,概述,纠错编码的基本思路： 根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规则相互关联（约束）。 在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。,概述,E,概述,m msg,C code,R noisycode,newmsg,干扰一般分为两种形式： 一是随机噪声，它主要来源于设备的热噪声和散弹噪声以及传播媒介的热噪声，它是通信系统中的主要噪声； 二是脉冲干扰和信道衰落，它的特点是突发出现，主要来源于雷电、通电开关、负荷突变或设备故障等。,概述,信道可分为三类： 1. 只产生随机错误的信道称为随机信道。比如卫星信道、同轴电缆、光缆信道以及大多数微波中继信道。 2. 产生突发错误的信道称为突发信道。实际的短波信道、移动通信信道、由于擦伤造成成串差错的光盘和磁盘，均为这一类信道。 3. 有些实际信道既有随机错误又有突发错误，称为混合信道。,根据不同的信道类型设计的信道编码分为纠随机错误码、纠突发错误码和纠混合错误码。,概述,在通信系统中，纠检错的工作方式有： (1) 反馈重传(ARQ) (2) 前向纠错(FEC) (3) 混合纠错,概述,发送端经编码后发出能够发现错误的码，接收端收到后经检验，如果发现传输中有错误，则通过反馈系统把这一判断结果反馈回发端，然后发送端把前面发出的信息重新传送一次，直到接收端认为正确地收到信息为止。,(1) 反馈重传(ARQ),检错 编码,信道,检错 译码,反馈,概述,(2) 前向纠错(FEC),纠错 编码,信道,纠错 译码,发送端发出的是具有纠错能力的纠错码，接收端根据译码规则进行译码。当误码个数在码的纠错能力范围内时，译码器可以自动纠正错误。,概述,特点：,1）前向纠错方式不需要反馈信道，特别适合于只能 提供单向信道的场合。 2）由于能自动纠错，不要求检错重发，因而延时小， 实时性好。 3）随着纠错能力的增强，译码设备也变得复杂。,概述,(3) 混合纠错,对发送端进行适当的编码。当错误不严重，在码的纠错能力范围之内时，采用自动纠错；当产生的差错超出码的纠错能力范围时，通过反馈系统要求发端重发。,概述,(1) 按功能分： 检错码：仅能检测误码 纠错码：可纠正误码 纠删码：兼纠错和检错能力 (2) 按信息码元与监督码元之间的检验关系分： 线性码：满足线性关系 非线性码：不存在线性关系,纠错码,1 纠错码的分类,(3) 按信息码元与监督码元之间的约束方式不同分：,分组码：本码组的监督码元仅和本码组的信息元相关。,树码：本码组的监督码元不仅和本码组的信息元相关，而且与前面码组的信息码元有关。如果是线性关系则称为卷积码。,(4) 按信息码元在编码后是否保持原形式不变：,系统码：信息码元与监督码元在分组内有确定位置， 编码后的信息码元保持不变；,非系统码：信息位打乱，与编码前不同。,1 纠错码的分类,(5)按纠正差错的类型可分为： 纠随机错误码 纠突发错误码 纠随机和突发错误码,1 纠错码的分类,纠错码按结构分类如下：,1 纠错码的分类,分组码的表示方法： （二元分组码） 信息码组由 k 个信息码元（信息位）组成，共有 2k 个不同的信息码组； 附加 个校验码元（校验位或监督位），每个校验码元是该信息码组的某些信息码元模2和； 编码器输出长度为n的码字； 码字的数目共有 2k ； 这2k 个码字的集合称为 (n,k) 分组码；,2 纠错码的基本概念,对 二进制(n, k)线性分组码，合法码字数为2k，可用编码空间的序列数为2n个。许用序列 ，禁用序列 任一种2k信息集合到二进制序列集合(2n)的映射都是一种(n, k)码 ，因此总共可能的编码方案有 种。,2 纠错码的基本概念,信息传输率（码率） 编码效率,发现或构造好码是信道编码研究的主要问题。,线性分组码是最具实用价值的一类码，比如汉明码、循环码、BCH码、RS码等。,2 纠错码的基本概念,2 纠错码的基本概念,对信道编码的一般要求是： 纠错检错能力强； 信息传输率高； 编码规律简单，实现设备简单且费用合理； 与信道的差错统计特性相匹配。,汉明距离,汉明距离满足距离公理 (1) 非负性 对称性 (3) 三角不等式,2 纠错码的基本概念,汉明重量,码C 的最小距离,线性分组码的最小距离等于非零码字的最小重量。,2 纠错码的基本概念,2 纠错码的基本概念,3 线性分组码,3.1 校验矩阵与生成矩阵,(1) 校验矩阵,3 线性分组码,被称为校验矩阵。 对 线性分组码，校验矩阵为 维矩阵。 对于系统码，校验矩阵可以表示为,其中 为 维矩阵， 为 维单位矩阵。,3 线性分组码,由校验方程，得到,(2) 生成矩阵,3 线性分组码,令,3 线性分组码,其中 为 维矩阵， 为 维单位矩阵。,被称为生成矩阵。 对 线性分组码，生成矩阵为 维矩阵。 对于系统码，生成矩阵可以表示为,3 线性分组码,把生成矩阵的每一行用一个行向量 来表示，则生成矩阵可以表示为,令 ，则,3 线性分组码,由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足 ，则有 对于标准形式的校验矩阵和监督矩阵，有,(3) 校验矩阵和生成矩阵的关系,3 线性分组码,线性分组码的封闭性：线性分组码中任意两个码字之和仍然是该码的码字。,证明：设 和 分别是码 中的两个码字，因此有,即 满足监督方程，所以是码 中的一个码字。,3 线性分组码,例1：3重复码是一个（3,1）线性分组码。其生成矩阵为,3 线性分组码,例2：（4,3）偶校验码是一个（4,3）线性分组码，其生成矩阵为,3 线性分组码,例3： 已知生成矩阵为 求生成的线性分组码及由H 生成的线性 分组码。,3 线性分组码,3 线性分组码,1111111,1111,1001110,1110,0011101,1101,0101100,1100,0001011,1011,0111010,1010,1101001,1001,1011000,1000,0100111,0111,0010110,0110,1000101,0101,1110100,0100,1010011,0011,1100010,0010,0110001,0001,0000000,0000,C,m,3 线性分组码,3.2 线性分组码的纠、检错能力,对于一个二进制对称信道，当输入为2k个等可能的n长码字，则最大后验概率准则等效于最小汉明距离译码准则。,3 线性分组码,关于码的最小距离与纠、检错能力的关系有以下结论：对于（n，k）线性分组码，设 为码的最小距离则 （）这组码有纠正 u 个错误的充要条件是,u,u,2u+1,3 线性分组码,l,l,l+1,（）具有检测l个错误的充要条件是,3 线性分组码,u,l,u+l+1,（）具有纠正 u 个错误，同时可以发现l个错误的充分必要条件为,3 线性分组码,码的纠错能力u与码字的长度n和消息数M满足以下关系：,3 线性分组码,3.3 校验矩阵与码的最小距离的关系,对于（n，k）线性分组码： 校验矩阵H中的任意t列线性无关而t+1列线 性相关，则码的最小距离(码字的最小重量) 为t+1。 反过来说，若码的最小距离(码字的最小重量) 为t+1则H 的任意t列线性无关而t+1列线性相关。,3 线性分组码,3.4 线性分组码的伴随式,R=C+E E=e1 e2 en,1) ，说明R 是一个码字; 2) ，说明R 不是码字，传输过程产生了误码。,3 线性分组码,例：某（5,2）系统线性码的生成矩阵是 设收码是 ，问它是否是码字。,3 线性分组码,令,则,（其中 表示 的列向量）,3 线性分组码,结论：,1) 当传输过程没有错误时 ，即 ， 2)当发生一位错误时， 是校验矩阵的某一列。 3)当发生多个错误时， 为校验矩阵对应列的模2和。,例： 设(7,3)线性分组码的校验矩阵为,3 线性分组码,（1）接收码字R=(1010011)，,传输过程中没有误码，,3 线性分组码,（2）接收码字R=(1110011)，,，第2位出错，,3 线性分组码,（3）接收码字R=(0011011)，,与 中的任一列都不相同，,不能确定到底是哪两位出错，不能正确译码。,3 线性分组码,线性分组码的伴随式译码,3 线性分组码,3 线性分组码,若（n，k）线性分组码能够纠正 u 个错误，则其校验位的数目必须满足,4 汉明码,上式等号成立则称为完备码,如果是能纠正一位错误的完备码则,完备码具有下述特性： （1）以每个发送码字为球心，以u为半径画一个球，那么每一个接收码字都落在其中一个球中，因此接收码字与发送码字的距离至多为u； （2）所有差错数小于等于u的接收码字都能得到纠正； （3）差错数大于等于u+1的接收码字，因为落在另一个球内被纠正为其他的发送码字。 完备码并不多见，我们知道的有u=1的汉明码、u=3的高莱码，以及(n,1)中n为奇数的重复码等。,4 汉明码,完备码,非完备码,000,111,000,001,010,100,111,110,101,011,00000,01101,00000,00001,00010,00100,01000,10000,00011,10011,01101,01100,01111,01001,00101,11101,01110,11100,10111,10111,. . .,11010,11010,. . .,4 汉明码,汉明码是一种能够纠正单个错误的完备码。 汉明码最小码距 设监督码共有r 位，对于汉明码必然有 。 通常汉明码可以表示成 。,4 汉明码,在同样的纠错能力下，汉明码的码率是最高的,汉明码监督矩阵构成的两种方式： 按 r 位的二进制数的自然顺序从左到右排列（不包括全0列）。当发生可纠的单个错误时，伴随式为 H 阵中对应的列，译码比较方便。 构成 H 阵的标准形式， 。非标准形式的监督矩阵可以通过列置换变成标准形式的监督矩阵，纠错能力保持不变。,4 汉明码,例：构造一个r=3的二元（7,4）汉明码,解：r=3的汉明码，,列置换,4 汉明码,4 汉明码,4 汉明码,如果给汉明码添加一位奇偶校验位，可得到扩展汉明码： 信息位保持不变，监督位增加一位。 最小码距 ， 可纠正一位错误，同时发现两位错误。,扩展汉明码的监督方程：,4 汉明码,复习,一个码字的汉明重量就是一个码字中非零码元的个数,记为W(c)。 W(1010101)=4。 定理：设(n,k)为线性分组码,则它的所有非零码字的重量的最小值wmin,称为最小重量,等于最小距离, 即wmin=dmin。 什么是线性分组码? 同时具有分组特性和线性特性的纠错码。,线性分组码的G,H,E,设线性分组码(n,k)的系统码的生成矩阵为 ,n=k+r。校验矩阵H为rn矩阵,满足:cHT=0 或 HcT=0. 其中c=(c1,c2,c3,c4,c5,c6)为码字, ,Q为rk矩阵。,因为G的每行都是码字,故 GHT=0 或HGT=0,从而,有QT+P=0 故 P=QT 或 Q=PT,校验矩阵H的性质:,(1) H与生成矩阵G可以相互转化。 (2) 利用H和式cHT=0判别是否码字。 (3) H中列的线性相关性与纠错能力有关系。,m4,m3,m2,m1,0001101,输入,编码器用4级移位寄存器和7-4=3个模2加法器组成,加法器生成校验位后按顺序暂存在另一个长度为7-4的移位寄存器中,先是4位信息位,然后是7-4位校验比特从两个寄存器中移出.,6.2线性分组码,5 循环码,循环码是线性分组码的一个重要子集。,循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一码字经过循环移位后，所得到的码字仍然是该码的码字。,循环码有严密的代数学理论基础，检错和纠错能力较强，而且编码和解码设备都不太复杂。,5 循环码,1)对于二进制码，码多项式的每个系数不是0就是1。 2) 仅是码元位置的标记。我们并不关心 的取值。,设循环码的码字为 ，用码多项式表示为,码字（1100101）可以表示为：,5 循环码,5 循环码,循环码的循环特性可以用码多项式来证明：,在整数运算中，有模n运算。若一个整数m可以表示为:,则,在模n运算下，一整数m等于其被n除所得的余数。,5 循环码,在码多项式运算中也有类似的按模运算法则。 若一任意多项式 M(x)被一个n次多项式 N(x) 除，得到商式 Q(x)和一个次数小于 n 的余式 P(x) ，也就是： 则可以写为：,在循环码中，若 是一个长为n的许用码字，则 在模 运算下，也是一个许用码字。,5 循环码,例: 某循环码的一个码字为1100101，则 若将此码左移一位，得： 对应的码字为1001011(即将码字1100101循环左移一位）。,5 循环码,5 循环码,从码中取出一个前面k-1位都是0的码字，定义这个码字的码多项式为生成多项式 。,在 循环码中，除了全0码字以外，其他码字的连0个数最多只有k-1个。,生成多项式的次数为 ，且常数项不为0。,5 循环码,为了保证构成的生成矩阵G的各行线性不相关，通常用 这样来构造生成矩阵。,5 循环码,k-1 个 0,5 循环码,设信息码元为 时，由生成矩阵得到相应码字的码多项式：,所有码多项式必定为 的倍式。,5 循环码,5 循环码,一致校验多项式,5 循环码,循环码的伴随多项式 就是用接收码多项式除以生成多项式 所得的余式。,译码可分为三步：,1)由接收到的码多项式 计算伴随多项式 ； 2)由伴随多项式 确定错误图样 ； 3)将错误图样 与 相加，纠正错误。,5 循环码,一 基本概念,6. 卷 积 码,卷积码中编码后的n个码元不仅与当前段的k个信息有关，而且也与前面（N-1）段的信息有关，编码过程中相互关联的码元为nN个。因此，这N段时间内的码元数目nN通常被称为这种码的约束长度。 由于与前面m段规定时间内的信息位有关，这里的mN-1通常用（n，k，m）表示卷积码 。,图 6-5 卷积码(2,1,2)编码器,例如：卷积码的n = 2，k = 1，m = 2，因此，它的约束长度nN = n(m+1) = 23 = 6。,假如输入的信息为D = 11010，为了使信息D全部通过移位寄存器，还必须在信息位后面加3个零。表列出了对信息D进行卷积编码时的状态。 描述卷积码的方法：图解表示和解析表示。 卷积码的译码方法可分为代数译码和概率译码两大类。,起始状态，各级移位寄存器清零，即S1S2S3为000。S1等于当前输入数据，而移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定,表 6-6 (2,1,2)编码器的工作过程,1. 树图,图 6-7 (2,1,2)码的树图,二 卷积码的图解表示,2. 状态图,图 10 -10 (2,1,2)码的状态图,3. 网格图,图 6-8 (2,1,2)码的格图,1. 维特比译码,图 6-9 维特比译码网格图,三 卷积码的译码,2. 序列译码 当m很大时，可以采用序列译码法。 其过程如下： 译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较， 沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，以此类推，最后得到一条路径。若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码器有一个门限值，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码输出。,本章小结：,译码规则：设信道输入符号集X= ,输出符号集Y= 。译码规则就是一个译码函数:F(bj)=(i=1,r;j=1,s)。 设信道的传递矩阵为（其中r=3，s=3） P,联合概率为 ，i=1,2,r,j=1,2,s。 联合概率矩阵为 P,最大后验概率准则(最小错误概率准则): 选择 ,使 即在收到bj的条件下,发出的是a*的概率最大,就将 bj