信道编码和差错控制.ppt

第10章 信道编码和差错控制,10.1 概述10.2 纠错编码的基本原理10.3 纠错编码系统的性能10.4 奇偶监督码10.5 线性分组码10.6 循环码,信源编码与信道编码 信源编码(有效性编码)去除冗余 提高数字信号的有效性 模拟信号数字化 信道编码(可靠性编码)添加冗余降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性差错控制：包括信道编码在内的一切纠正错误手段 差错控制技术的种类 检错重发 能发现错码，但是不能确定错码的位置 通信系统需要有双向信道 前向纠错(FEC)：利用加入的差错控制码元，不但能够发现错码，还能纠正错码 反馈校验 将收到的码元转发回发送端，将它和原发送码元比较 缺点：需要双向信道，传输效率也较低 检错删除 在接收端发现错码后，立即将其删除 适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处,10.1 概述,自动要求重发(ARQ)系统 停止等待ARQ系统 拉后ARQ系统,10.1 概述,自动要求重发(ARQ)系统 选择重发ARQ系统,10.1 概述,ARQ和前向纠错比较 优点 监督码元较少，即码率较高 检错的计算复杂度较低 能适应不同特性的信道 缺点 需要双向信道 不适用于一点到多点的通信系统或广播系统 传输效率降低，可能因反复重发而造成事实上的通信中断,产生错码的原因 乘性干扰引起的码间串扰 加性干扰引起的信噪比降低 信道分类：按照加性干扰造成错码的统计特性不同划分 随机信道：错码随机出现，例如由白噪声引起的错码 突发信道：错码相对集中出现，例如由脉冲干扰引起的 错码 混合信道编码序列的参数 n 编码序列中总码元数量 k 编码序列中信息码元数量 r 编码序列中差错控制码元数量（差错控制码元，以后称为监督码元或监督位）k/n码率(n-k)/k=r/k冗余度,10.1 概述,10.2 纠错编码的基本原理,差错控制编码 理论依据：香农信道编码定理对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值 基本思想通过对信息码元序列作某种变换,使原来彼此相互独立,没有关联的信息码元序列,经过这种变换后,产生某种规律性或相关性,使在接收端可根据这种规律性来检查,以至纠正传输序列中的差错 实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系,10.2 纠错编码的基本原理,差错控制编码简单例子假如要传送A、B两个消息，消息A-“0”；消息B-“1”若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力 消息A-“00”；消息B-“11”若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力消息A-“000”；消息B-“111”传输中产生一位即使两位错码，都将变成禁用码组，收端判决 传输有错。该编码具有检出两位错码的能力。在产生一位错码情况下，收端可进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。可见，纠错编码之所以具有检错和纠错能力，确实是因为在信息码 元外添加了冗余码元（监督码元）。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。,10.2 纠错编码的基本原理,差错控制能力与编码效率 设：有一种由3个二进制码元构成的编码，它共有23=8种不同的可 能码组：000 晴 001 云 010 阴 011 雨 100 雪 101 霜 110 雾 111 雹 这时，若一个码组中发生错码，则将收到错误信息 若在此8种码组中仅允许使用4种来传送天气，例如：令 000 晴 011 云 101 阴 110 雨 为许用码组，其他4种不允许使用，称为禁用码组 这时，接收端有可能发现（检测到）码组中的一个错码。这种编码只能检测错码，不能纠正错码 若规定只许用两个码组：例如 000 晴 111 雨 就能检测两个以下错码，或纠正一个错码,分组码概念 分组码 信息位 监督位 分组码符号：(n,k)其中，n 码组总长度 k 信息码元数目 r=n k 监督码元数目 右表中的码组为(3,2)码 分组码的一般结构：,10.2 纠错编码的基本原理,码重 码字中非零码元的数目码距 两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，称为汉明（Hamming）距离,简称码距最小码距 在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素 间的最小距离，记为d0码距的几何意义：以n=3的编码为例 一般而言，码距是 n 维空间中单位 正多面体顶点之间的汉明距离,10.2 纠错编码的基本原理,最小码距与检、纠错能力关系 一个码能检测e个错码，则要求其最小码距 d0e+1反之，若码的最小距离为d0，则最多能检测d0-1个错码 一个码能纠正t个错码，则要求其最小码距 d02t+1反之，若码的最小距离为d0，则最多能纠正(d0-1)/2个错码,10.2 纠错编码的基本原理,最小码距与检、纠错能力关系 一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 d0e+t+1(et),10.2 纠错编码的基本原理,误码率性能和带宽的关系 采用编码降低误码率所付出的 代价是带宽的增大,10.3 纠错编码系统的性能,功率和带宽的关系 采用编码以节省功率，并保持误码率 不变，付出的代价也是带宽增大。,10.3 纠错编码系统的性能,传输速率和带宽的关系对于给定的传输系统，其传输速率 和Eb/n0的关系：式中，RB 码元速率。提高传输速率，采用编码以保持误码率不变；付出的代价仍是带宽增大,10.3 纠错编码系统的性能,编码增益定义：在保持误码率恒定条件下，采用纠错编码所节省的信噪比Eb/n0 称为编码增益：式中，(Eb/n0)u 未编码时的信噪比(dB)(Eb/n0)c 编码后所需的信噪比(dB),10.3 纠错编码系统的性能,一维奇偶监督码 在信息码元后附加一位监督位，使得码组中“1”的个数为偶数或奇 数,按照奇偶数分为奇数监督码和偶数监督码两类(n,n-1)分组码，码率为(n-1)/n（或k/(k+1)奇数监督码中，此监督位使码组中“1”的个数为奇数：式中，a0为监督位，其他位为信息位 偶数监督码中，此监督位使码组中“1”的个数为偶数：式中，a0为监督位，其他位为信息位 检错能力 能够检测奇数个错码 应用：以随机错误为主的计算机通信系统，难于对付突发错误,计 算机内部的数据传送，就是采用这种码,10.4 奇偶监督码,二维奇偶监督码 有可能检测偶数个错码，但当偶数个错误刚好分布在矩阵的四个顶点 时，则检测不出 适合检测突发错码 能够纠正部分错码,10.4 奇偶监督码,基本概念 代数码 利用代数关系式产生监督位的编码 线性分组码 代数码的一种，其督位和信息位的关系由线性代数方 程决定 汉明码 一种能够纠正一个错码的线性分组码汉明码 发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”码元个数为偶数 接收端译码：计数接收码组中“1”码元个数是否为偶数，即计算：S=an-1+an-2+a0（1）S=0认为没错，S=1认为有错（1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式,10.5 线性分组码,汉明码 监督位增加到2位：有两个监督方程，两个伴随式；两个伴随式组合有 四种（00表示无错，01、10、11表示一位错码的三种可能位置）监督位增加到r位：可指示一位错码的（2r-1）个可能位置 一般说来，对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个 监督关系式来指示一位错码的n种可能位置，则要求：2r-1n 即 2r k+r+1（2）举例：构造一（n，k)分组码，k=4并能纠正一位错码 欲纠正一位错码，由（2）式知r 3，取r=3，则n=k+r=7 设7位码元为：a6a5 a0；三个伴随式：S1、S2、S3；则可规定S1S2S3的 八种组合与一位错码的对应关系如下（也可规定为另一种对应关 系）：,10.5 线性分组码,10.5 线性分组码,汉明码 举例：构造一（n，k)分组码，k=4并能纠正一位错码 从上表可见：当一位错码发生在a2、a4、a5或a6上时，S1为1；否则为0。即a2、a4、a5和a6构成偶监督关系：S1=a2+a4+a5+a6 同理，a1、a3、a5和a6构成偶监督关系：S2=a1+a3+a5+a6 a0、a3、a4和a6构成偶监督关系：S3=a0+a3+a4+a6,10.5 线性分组码,汉明码 发端编码原则 信息码元a6、a5、a4、a3来源于待编码的信息序列；监督码元 a2、a1、a0的取值应根据信息码元按监督关系式来决定，即使上面三式中的S1、S2、S3均为0：a2+a4+a5+a6=0 a1+a3+a5+a6=0（3）a0+a3+a4+a6=0 a2=a4+a5+a6 a1=a3+a5+a6（4）a0=a3+a4+a6 于是，给定信息位后，根据上式算出各监督位，于是该编码的所有 码组如下表：汉明码的编码效率较高，其编码效率：该汉明码的码率较高：k/n=4/757%。与相同码长、能纠正 一位错码的其他分组码相比，该码效率最高，且实现简单。,1 a6+1 a5+1 a4+0 a3+1 a2+0 a1+0 a0=01 a6+1 a5+0 a4+1 a3+0 a2+1 a1+0 a0=01 a6+0 a5+1 a4+1 a3+0 a2+0 a1+1 a0=0,(5),10.5 线性分组码,线性分组码 监督矩阵 由（7，4）汉明码出发，（3）式可改写成：写成矩阵形式：,(6),可化简为：HAT=0T 或AHT=0其中，H=称为线性分组码的监督矩阵,rn阶矩阵监督矩阵H确定了编码时监督码元与信息码元的关系把具有PIr形式的H矩阵称为典型形式的监督矩阵，其中P为rk阶 矩阵,Ir为r r阶单位方阵 H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线 性无关,10.5 线性分组码,线性分组码 监督矩阵 生成矩阵（4）式也可写成矩阵形式，即 对（7）式两侧作矩阵转置，得：其中Q=PT可见，Q为kr阶矩阵,(7),构造矩阵G：在Q矩阵的左边加上一个k k阶矩阵，即G=IkQ=称为线性码的生成矩阵 生成矩阵G的性质：k n阶矩阵 编码方法完全由生成矩阵G确定 把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中，Ik为kk阶单位方阵，Q为k r阶矩阵 由典型生成矩阵产生的分组码一定是系统码 G矩阵的各行应线性无关，每行均为许用码组,10.5 线性分组码,线性分组码 生成矩阵,错误图样设：发送码组A是一个n列的行矩阵：接收码组是一个n列的行矩阵B：令接收码组和发送码组之差为 E就是错码的行矩阵 称为错误图样 式中，(i=0,1,n-1)若ei=0，表示该码元未错；若ei=1，表示该码元为错码,10.5 线性分组码,校正子矩阵 B A=E 可以改写成 B=A+E 上式表示发送码组A与错码矩阵E之和等于接收码组B 例如，若发送码组A=1 0 0 0 1 1 1 错码矩阵E=0 0 0 0 1 0 0 则接收码组B=1 0 0 0 0 1 1 在接收端解码时，将接收码组B代入式AHT=0 中A的位置进行计算。若接收码组中无错码，则B=A。代入后，该式 仍成立，即有BH T=0 只有当错码未超出检测能力时，上式才不成立。假设，这时该式的右端等于S，即有BH T=S 将B=A+E 代入上式，得到:S=(A+E)H T=AH T+EH T,10.5 线性分组码,校正子矩阵 S=(A+E)H T=AH T+EH T 上式右端第一项等于0，所以 S=EH T 校正子矩阵 当H 确定后，上式中S只与E 有关，而与A 无关 这意味着，S 和错码E 之间有确定的线性变换关系。若S 和E 有一一对应关系，则S 将能代表错码位置。线性分组码的性质 封闭性：若A1和A2是一种线性码中的两个码组，则(A1+A2)仍是其中 一个码组 证若A1和A2是两个码组，则有：A1HT=0,A2HT=0 将上两式相加，得出A1HT+A2HT=(A1+A2)HT=0 所以(A1+A2)也是一个码组。码的最小距离等于非零码的最小重量,10.5 线性分组码,循环码的概念：循环性是指任一码组循环一位后仍然是该编码中的一个码组。例：一种(7,3)循环码的全部码组如下 表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组,10.6 循环码,循环码的概念 一般情况若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组：(an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2)(a0 an-1 a2 a1)仍然是该编码中的码组 多项式表示法一个长度为n的码组(an-1 an-2 a0)可以表示成上式中x 的值没有任何意义，仅用它的幂代表码元的位置例：码组1 1 0 0 1 0 1可以表示为,10.6 循环码,循环码的运算 整数的按模运算 一般说来，若一个整数m可以表示为 式中，Q为整数，则在模n运算下，有m p(模n)所以，在模n运算下，一个整数m等于它被n除得的余数 码多项式的按模运算 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次 数小于n的余式R(x)，即 则在按模N(x)运算下，有 这时，码多项式系数仍按模2运算,10.6 循环码,循环码的运算 码多项式的按模运算 例：x3被(x3+1)除，得到余项1，即 例：循环码的数学表示法 定理1：在循环码中，设T(x)是一个长度为n的码组，若 则T(x)也是该编码中的一个码组，并且T(x)是码组T(x)向左循环移 位 i 次的结果 例：一循环码为1100101，即 若给定 i=3，则有 上式对应的码组为0101110，它正是T(x)向左移3位的结果 结论：一个长为n的循环码必定为按模(xn+1)运算的一个余式,10.6 循环码,循环码的生成 有了生成矩阵G，就可以由k个信息位得出整个码组：例：式中，生成矩阵G的每一行都是一个码组 因此，若能找到 k 个已知的码组，就能构成矩阵G。如前所述，这k个 已知码组必须是线性不相关的。在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而 且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩 阵G,10.6 循环码,循环码的生成 在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是 这种(n,k)码中次数为(n k)的唯一一个多项式 我们称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定了 g(x)，则整个(n,k)循环码就被确定了 因此，循环码的生成矩阵G可以写成,10.6 循环码,循环码的生成 例：上表中的编码为(7,3)循环码，n=7,k=3,n k=4，其中唯一的一 个(n k)=4次码多项式代表的码组是第二码组0010111，与它对应 的码多项式，即生成多项式，为g(x)=x4+x2+x+1,10.6 循环码,将此g(x)代入上矩阵，得到 或 此循环码组的多项式表示式T(x)：,结论：所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不 大于(k 1)的多项式乘g(x)都是码多项式,寻求码生成多项式 因为任意一个循环码T(x)都是g(x)的倍式，故它可以写成T(x)=h(x)g(x)而生成多项式g(x)本身也是一个码组，即有 T(x)=g(x)由于码组T(x)是一个(n k)次多项式，故xkT(x)是一个n次多项式 由可知，xk T(x)在模(xn+1)运算下也是一个码组，所以有上式左端分子和分母都是n次多项式，故相除的商式Q(x)=1。因此，上式可以写成,10.6 循环码,寻求码生成多项式 将T(x)=h(x)g(x)和T(x)=g(x)代入 化简后，得到 上式表明，生成多项式g(x)应该是(xn+1)的一个因子 例：(x7+1)可以分解为 为了求出(7,3)循环码的生成多项式 g(x)，需要从上式中找到一个(n k)=4次的因子。这样的因子有两个，即 以上两式都可以作为生成多项式 选用的生成多项式不同，产生出的循环码码组也不同,10.6 循环码,循环码的编码方法 用xn-k乘m(x)；这一运算实际上是在信息码后附加上(n k)个“0”。例如，信息码为110，它写成多项式为m(x)=x2+x 当n k=7 3=4时，xn-k m(x)=x4(x2+x)=x6+x5，它表示码组1100000 用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即有 例如，若选定g(x)=x4+x2+x+1，则有 上式是用码多项式表示的运算。它和下式等效：编出的码组T(x)为：T(x)=xn-k m(x)+r(x)在上例中，T(x)=1100000+101=1100101,10.6 循环码,循环码的解码方法 在检错时：当接收码组没有错码时，接收码组R(x)必定能被g(x)整除，即：式中，余项r(x)应为零；否则，有误码。当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被g(x)整除。这时，错码就不能检出了。在纠错时：用生成多项式g(x)除接收码组R(x)，得出余式r(x)按照余式r(x)，用查表的方法或计算方法得出错误图样E(x)从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x),10.6 循环码,第10章 小结,10.1 概述10.2 纠错编码的基本原理10.3 纠错编码系统的性能10.4 奇偶监督码10.5 线性分组码10.6 循环码,