通信原理幻灯片第11章-差错控制编码

2019/4/20,1,通 信 原 理 电 子 教 案 第11章 差错控制编码,西 北 工 业 大 学 （2008.6）,2019/4/20,2,研究的问题:,11.1 概述 11.2 纠错编码的基本原理 11.3 纠错编码的性能 11.4 常用的简单编码 11.5 线性分组码 11.6 循环码 11.7 卷积码 11.8 Turbo码 11.9 低密度奇偶校验码 11.10 网格编码调制,2019/4/20,3,11.1 引言 一、编码问题的提出 由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能发生错判。,信道,译码,检/纠错编码,若还不行，则需差错控制编码。 目的：在数字通信系统中，为了提高数字通信的可靠性而采取的编码称为信道编码。差错可控 之前：为了提高数字信号传输的有效性而采取的编码称为信源编码。 模型：,2019/4/20,4,二、错误的类型 随机性错误 （白噪声引起） 特点：单个错，错误之间不相关。主要出现在无记忆信道。 2. 突发性错误 (脉冲干扰引起） 特点：成串错，错误之间有相关性。主要出现在有记忆信道。错误传播。 3. 混合性错误,2019/4/20,5,三、差错控制的方式 1. 检错重发(ARQ),特点: 1）双向通道 2）通信效率低 3）不适于实时通信 4）编、译码设备简单 5）编码效率高,总码元 (n bit)= 信元 (k bit)+ 督元 (r bit )。,只检不纠，有错自动要求重发。,督元长度低！,2019/4/20,6,2. 前向纠错 (FEC),特点： 1）只需单向信道省信道！ 2）通信效率高； 3）适于实时传输； 4) 译码设备复杂； 5) 编码效率低。,检错并纠错,督元变长！,2019/4/20,7,3. 反馈检验法,原理：收端将信码原封不动地转发回发端，并与原发送信码相比较：发现错重发；否则：PASS 特点: 1）需要双向通道； 2）收发设备简单； 3）传输效率低（最低）。,2019/4/20,8,11.2 纠错编码的基本原理 一. 基本思想,信元和督元有一的函数关系，插入督元的过程就是一种编码的过程，接收端可检错纠错。显然，传输效率（引入冗余码） 例：天气预报,三位码元有23=8种组合，实际使用了22=4种许用码组。 其余 001，010，100，111 为禁用码组。 检错能力：可检错奇数个错； 纠错能力：无。,2019/4/20,9,例：天气预报，可预报天晴,冗余量加大，禁用码组比例提高。 检错能力：检2； 纠错能力：纠1。 纠检不兼得！,许用码组2个，禁用码组6个,晴 阴,2019/4/20,10,二. 纠错编码的分类 线性码和非线性码 分组码、卷积码和循环码 系统码和非系统码 三. 分组码 定义:将信息码分组，为每信息码附加若干个监督码编码，称为分组码。 特点: 在分组码中，监督码元仅监督本码组中的信息码元。,符号: ( n , k ) , r = n k 码字:,结构:,k个信元,r个督元,码长n,2019/4/20,11,码组的重量和码距及纠错能力 1. 重量 码组中非0元素的个数 例: A= ( 10110 ) 码重 = 3 2. 码距 两两码组对应位上数值不同的个数，记为d。 最小码距: 某种编码中各个码组间距离 的最小值，记做d0 d0=dmin 码距的几何意义: (n=3) 各顶点 沿立方体各边行走的几何距离。 码元值：每一码组的三个码元值， 就是此立方体各顶点的座标（a2a1a0） 最小码距: 1,2019/4/20,12,前例中：天气预报,四个许用码组之间的距离均为2。 Why? 摈弃d=1的码禁用码组。许用码组最小码距愈大，抗干扰能力愈强！ 确定最小码距的目的：决定编码的检纠错能力。,2019/4/20,13,3. d0与纠检错能力 若要求检测e个错,则 d0e+1 若要求纠正t个错,则 d02t+1 若要检测e纠正t 个错（同时），则 d0e+t+1, 且et 码距与检错和纠错能力的关系：,t 1 t,e,2019/4/20,14,0 1 2 3 A B,d0,0 1 2 3 4 5 A B,t t,d0,A B,t 1 t,e,2019/4/20,15,11.4 常用的简单编码 属于分组码一类。简单、实用。 11.4.1 奇偶监督码 满足:,偶监督码：码组中1的个数为偶数； 奇监督码：码组中1的个数为奇数。 检错能力: 所有奇数个错。一半！应用非常多。 编码效率:,2019/4/20,16,11.4.2 二维奇偶监督码 进行横、纵向监督 例:,横 向 监 督,纵 向 监 督,纠检错能力: 仍可检错奇数个错 还可检错偶数个错 可纠正一些错码 适于检测突发性错误,2019/4/20,17,11.4.3 横比码(等重码)主要用在电传机 编码特点：每个码组中“1”与“0”的比值是恒定的。 例: 码重为3,1 . 0 1 0 1 1 1 1 0 0 1 1 0 1 1 0,许用码组: C35 = 10 禁用码组: 25-10 = 22,检错能力：可检测所有奇数个码元的错和部分偶数个码元的错，但不能检测码组中“1”变为“0” 与“0”变为“1”的错码数目相同的那些偶数错码。 编码效率：,2019/4/20,18,例： n=10 , 则 k=5, 接收端的检测 （合成码） 校验码：信息位中有奇数个1：校验码合成码 信息位中有偶数个1：校验码合成码的反码,11.4.4 正反码 编码规则: 信息位(n/2)中有奇数个“1”，则监督位与信息位相同； 信息位(n/2)中有偶数个“1”，则监督位是信息位的反码。,2019/4/20,19,例： n=10 , 则 k=5, 接收端的检测 （合成码） 校验码：信息位中有奇数个1：校验码合成码 信息位中有偶数个1：校验码合成码的反码,编码规则: 信息位(n/2)中有奇数个“1”，则监督位与信息位相同； 信息位(n/2)中有偶数个“1”，则监督位是信息位的反码。, 错码的位置： 校验码中： 1）4个“1”，一个“0”，信息位错一个，位置“0”处； 2）4个“0”，一个“1”，监督位错一个，位置“1”处； 3）其他：错不止一个。,2019/4/20,20,11.5 线性分组码 定义：若分组码（n,k）,督元与信元的关系可用一线性方程组来描述，则该分组码（n,k）称为线性分组码。 11.5.1 汉明码 能纠一位错的线性分组码。 定义：是一种能纠正一位错码，且编码效率较高的线性分组码。 最小码距：d0=3 1. 构造原理 考察：定义一个监督方程（监督关系式、偶监督）：,由于一位校正子只有两种取值，故只能表示有错或无错，不能指出错码的位置。,2019/4/20,21,推想：如果监督位增加一位（即变成两位），则可增加一个类似于上式的监督关系，即可获得两个校正子，于是可有,2019/4/20,22,再推广：,S1 S2 Sr 0 0 . 0 0 0 . 1 1 1 .1 1,显然：要求 2r-1n（n=k+r），则可指示（仅一位错时）任一错码的位置包括信元、督元。 或： 2rk+r+1,可指示一个错码可能出现的2r-1个位置。,2019/4/20,23,2. 例: 构造k=4 的汉明码 （1）确定 r 由 2r k+r+1 得 r = 3，则 n= k+r=7 ( 7,4 ) 分组码,（2）写出校正子的编码表,2019/4/20,24,（2）写出校正子的编码表 r = 3 共有3个校正子,（3） 由校正子编码表得监督方程组校正子和哪些码元构成偶监督关系,若 S1S2S3 = 000 时, 即无错得校验方程:,偶监督关系,校正子编码表不是唯一的。,2019/4/20,25,得校验方程:,即实际上确定了督元和信元之间的关系:,校验方程,督信关系,有了校正子编码表，督元不是随便选的！（表的编制不是唯一的）,（4） 给定了信元a6a5a4a3,可由“督信关系”确定督元全部( 7,4 ) 码组。,2019/4/20,26,（4） 给定了信元a6a5a4a3,可确定督元全部( 7,4 ) 码组,2019/4/20,27,11.5.2 线性分组码一般性讨论 1. 线性方程组和监督方程从校验方程入手,写成矩阵式:,校验方程 来自编码表,2019/4/20,28,可见：H一旦确定，督元和信元之间的关系也就确定了。 若:,则称H为典型阵，一般，H总可以化为典型阵。,2019/4/20,29,2. 生成矩阵,矩阵形式:,从督信方程入手 由,2019/4/20,30,写成行阵形式:,其中 Q = PT。上式表明：信息位给定后，就产生了监督位！,进一步，令生成矩阵 G = Ik Q 则，码组行阵 A = a6a5a4a3 G,Q能生成督元 G才生成线性分组码 如何装配：信元督元？,2019/4/20,31,例：生成矩阵,讨论： 由具有 Ik Q 形式的生成矩阵称为典型生成阵。 由典型生成矩阵得出的码组A中，信息位不变，监督位附加其后这种码称为系统码。,码组行阵：,督元由相应的信息位决定！,2019/4/20,32,一般形式: A = an-1an-2ar G,3. G 和 H 的关系 由 Q = PT 或 P = QT 则 : H = P · Ir G = Ik · Q 综上：线性分组码的编码，就是根据其监督阵H或生成阵G将长为k的信息码编成长为n的码组。,2019/4/20,33,4. 线性分组码的纠错译码过程 怎样由含有错误的接收码组中的接收码组中恢复正确。 （1）错误图样 设：发码组为A , 接受码组为B 则 B A = E ( 模 2 )错误行阵或错误图样： E= en-1en-2e0 ,例: A = 1 1 1 1 1 1 1 B = 1 0 0 1 1 0 1 则 E = 0 1 1 0 0 1 0 ,2019/4/20,34,（2）校正子（或称译码伴随式）,B = A+E 代入上式，得,结论：校正子S仅于错误图案有关，与发送码组无关。,2019/4/20,35,由收到的码组B，按式：BHT=SS 由 S=EHT E 按B+E=A A 由A 原始信息,（3）纠错译码过程,2019/4/20,36,5. 线性分组码的重要性质 （1）封闭性 设： A1、A2 分别为一线性分组码的任意两个许用码组。 则：A1+A2 仍为该线性分组码的许用码组。 证：由假设知 A1HT=0、A2HT=0 所以 A1HT+A2HT=（A1+A2）HT0 即A1+A2也是一个码组。 结论：线性码组中任意两个码字之和，仍为该线性码组之码字。 （2）线性分组码的最小码距即为该码的最小重量: d0=Wmin（除全0码组） 证：由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！,2019/4/20,37,11.6 循环码 仍属于线性分组码 特点: 编译码设备简单，检纠错能力强。 11.6.1 循环码的原理 具有线性分组码的所有性质之外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。,2019/4/20,38,码多项式 T(x) （1）定义 为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。 设：许用循环码A=