第11章-差错控制编码1212

1,第11章差错控制编码,2,11.1概述,信道编码：目的：提高信号传输的可靠性。方法：增加多余比特，以发现或纠正错误。差错控制：包括信道编码在内的一切纠正错误手段。产生错码的原因：乘性干扰引起的码间串扰加性干扰引起的信噪比降低信道分类：按照加性干扰造成错码的统计特性不同划分随机信道：错码随机出现，例如由白噪声引起的错码突发信道：错码相对集中出现，例如由脉冲干扰引起的错码混合信道,3,差错控制技术的种类：检错重发：能发现错码，但是不能确定错码的位置。通信系统需要有双向信道。前向纠错(FEC)：利用加入的差错控制码元，不但能够发现错码，还能纠正错码。反馈校验：将收到的码元转发回发送端，将它和原发送码元比较。缺点：需要双向信道，传输效率也较低。检错删除：在接收端发现错码后，立即将其删除。适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。,4,差错控制编码一般原理：发端在信息码元中增加差错控制码元，称为监督码元，利用信息码元与监督码元之间的函数关系，在收端发现或纠正错码。差错控制编码用降低信息传输速率来换取传输可靠性的提高。编码序列的参数n编码序列中总码元数量k编码序列中信息码元数量r编码序列中差错控制码元数量（差错控制码元，以后称为监督码元或监督位）k/n码率（编码效率）(n-k)/k=r/k冗余度,5,检错重发自动要求重发(ARQ)系统停止等待ARQ系统：半双工状态，传输效率低拉后ARQ系统：双工,6,选择重发ARQ系统：双工，只选择重发错码ARQ和前向纠错比较：优点监督码元较少，即码率较高检错的计算复杂度较低缺点需要双向信道。只适用于点到点的通信系统。传输效率降低，可能因反复重发而造成事实上的通信中断。,7,分组码举例设：由3个二进制码元构成的编码，它共有23=8种不同的可能码组：000晴001云010阴011雨100雪101霜110雾111雹若一个码组中发生错码，则将收到错误信息。若在此8种码组中仅使用4种来传送天气，例如：令000晴011云101阴110雨为许用码组，其他4种不允许使用，称为禁用码组。接收端有可能发现（检测到）码组中的一个错码。这种编码只能检测错码，不能纠正错码。若规定只许用两个码组：例如000晴111雨就能检测两个以下错码，或纠正一个错码。,11.2差错控制编码的基本原理,8,分组码概念分组码信息位监督位分组码符号：(n,k)其中，n码组总长度，k信息码元数目。r=nk监督码元数目。分组码的一般结构：分组码的参数：码重：码组内“1”的个数码距：两码组中对应位取值不同的位数，又称汉明距离最小码距(d0)：各码组间的最小距离,9,码距的几何意义：以n=3的编码为例码距是n维空间中单位正多面体顶点之间沿立方体各边行走的几何距离。,10,一种编码的纠检错能力：决定于最小码距d0的值。为了能检测e个错码，要求最小码距为了能纠正t个错码，要求最小码距,11,为了能纠正t个错码，同时检测e个错码，要求最小码距,12,一维奇偶监督码奇偶监督码：分为奇数监督码和偶数监督码两类。在奇偶监督码中，监督位只有1位，故码率等于k/(k+1)。偶数监督码中，此监督位使码组中“1”的个数为偶数：式中，a0为监督位，其他位为信息位。奇数监督码中，此监督位使码组中“1”的个数为奇数：,11.3简单的实用编码,13,11.4.2二维奇偶监督码有可能检测偶数个错码，构成矩形的4个错码无法检测能够纠正部分错码（仅在一行中有奇数个错码）,14,代数码：利用代数关系式产生监督位的编码线性分组码：代数码的一种，其监督位和信息位的关系由线性代数方程决定汉明码：一种能够纠正一个错码的线性分组码校正子：在偶数监督码中，计算实际上就是计算并检验S是否等于0。S称为校正子。监督关系式：,11.4线性分组码,15,纠错基本原理中，S只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。若监督位增加一位，则增加一个监督关系式，因此得到两个校正子。两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息。若用其中一种组合表示无错码，则还有其他3种组合可以用于指明一个错码的3种不同位置，从而可以有纠错能力。一般而言，若有r个监督关系式，则r个校正子可以指明一个错码的(2r1)个不同位置。当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求,16,汉明码例：要求设计一个能够纠正1个错码的分组码(n,k)，给定的码组中有4个信息位，即k=4。由这时要求监督位数r3。取r=3，则n=k+r=7。现在用a6a5a4a3a2a1a0表示这7个码元，用S1S2S3表示校正子，则这3个校正子恰好能够指明231=7个错码的位置。规定校正子和错码位置的关系如下表，则仅当在a2a4a5a6位置上有错码时，校正子S1的值才等于1；否则S1的值为零。这就意味着a2a4a5a6四个码元构成偶数监督关系：同理，有,17,在编码时，信息位a6a5a4a3的值取决于输入信号，监督位a2a1a0是按监督关系确定的，应该保证上列3式中的校正子等于0，即有给定信息位后，为了计算监督位，上式可以改写为按照上式计算监督位结果为：,18,在接收端解码时，对于每个接收码组，先按式计算出校正子S1，S2和S3，然后按下表判断错码的位置。例：若接收码组为0000011，则按上三式计算得到：S1=0，S2=1，S3=1。由上表可知，错码位置在a3。,19,上例中的汉明码是(7,4)码，其最小码距d0=3。由式可知，此码能够检测2个错码，或纠正1个错码。,20,分组码的一般原理线性分组码的监督位和信息位的关系可以改写为上式中，将“”简写成“+”。,21,监督矩阵上式可以写成矩阵形式：（模2）将上式简写为：HAT=0T或AHT=0,22,HAT=0T，其中，称为监督矩阵,23,监督矩阵的性质监督矩阵H确定码组中的信息位和监督位的关系。H的行数就是监督关系式的数目，即监督位数r。H的每行中“1”的位置表示相应的码元参与监督关系。H可以分成两部分，例如典型监督矩阵式中，P为rk阶矩阵，Ir为rr阶单位方阵。H矩阵的各行应该是线性无关的，否则将得不到r个线性无关的监督关系式。若一个矩阵能写成典型阵形式PIr，则其各行一定是线性无关的。,24,生成矩阵例：可以写为上式两端分别转置后，可以变成式中，Q为kr阶矩阵，是P的转置，即Q=PT,25,将Q的左边加上一个k阶单位方阵，称为生成矩阵：生成矩阵G称为生成矩阵，因为可以用它由信息码元产生整个码组A（信息码元与监督码元），即有,26,生成矩阵的性质具有IkQ形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码组称为系统码。矩阵G的各行也必须是线性无关的。,27,错误图样设：发送码组A是一个n列的行矩阵：接收码组是一个n列的行矩阵B：令接收码组和发送码组之差为E就是错码的行矩阵称为错误图样式中，(i=0,1,n-1)若ei=0，表示该码元未错；若ei=1，表示该码元为错码。,BA=E(模2),28,例如，若发送码组A=1000111，接收码组B=1000011，则错码矩阵（错误图样）E=0000100。,29,校正子矩阵BA=E可以改写成B=A+E上式表示发送码组A与错码矩阵E之和等于接收码组B。在接收端解码时，将接收码组B代入式AHT=0中A的位置进行计算。若接收码组中无错码，则B=A。代入后，该式仍成立，即有BHT=0只有当接收码组中有错码时，BHT0定义S=BHT校正子矩阵将B=A+E代入上式，得：S=(A+E)HT=AHT+EHT上式右端第一项等于0，所以S=EHT当H确定后，上式中S只与E有关，而与A无关。,30,线性码的封闭性：若A1和A2是一种线性码中的两个码组，则(A1+A2)仍是其中一个码组。证若A1和A2是两个