《信息论 基础理论与应用第三版(傅祖芸)-第9章-讲义》由会员分享，可在线阅读，更多相关《信息论 基础理论与应用第三版(傅祖芸)-第9章-讲义（75页珍藏版）》请在金锄头文库上搜索。
1、第9章 信道的纠错编码,差错控制的基本形式,纠错码分类及其基本概念,线性分组码,*循环码,*卷积码,香农第二定理指出，只要信息传输率小于信道容量，通过适当的编译码方法，就能以任意小的错误概率传输信息。但从实际工程看，并没有指出具体的编译码方法。 这正是信道纠错编码要解决的问题。,香农第二定理指出，在信道中以信息传输率R小于信道容量条件下，使差错概率尽可能小的信道编译码原则是： 编码原则： 在n次扩展信道输入符号序列中选取M个作为码字构成一组码C，并尽量使选取的M个码字中两两不相同码字的汉明距离尽可能地大； 译码原则： 当收到符号序列后，翻译成与之汉明距离最近的码字（最大似然准则）。 几十年来，
2、基于香农编码定理和以上编译码原则，科技工作者们开发了很多具有纠错能力的信道编码，如线性分组码、循环码、BCH码、卷积码、TCM码、Tuobo码等，在通信系统中得到了广泛应用。,9.1 差错控制的基本形式,现代数字通信系统中，利用检错和纠错的编码技术，使得信道编译码具备一定的差错控制能力。主要方式有： 1、前向纠错(FEC)方式： 发送端信道编码器将信息码组编成具有一定纠错能力的码。 接收端信道译码器对接收码字译码，若传输中产生的差错数目在码的纠错能力之内，译码器对差错进行定位并加以纠正。,检错、纠错,FEC 特点 单向控制，不需要反馈信道；时延小，实时性好。 为适应较差信道，冗余码元多，编码效
3、率低，译码设备复杂。 有一定的纠错范围限制。 适用于容错能力强的语音、图像传输；不适合容错能力弱的数据通信网。,2、反馈重发(ARQ)方式（检错重发方式）： 发送端发送的是能够发现（检测）错误的码； 接收端收到信道传输来的码后，译码器依据该码编码规则，判决出当前码字传输是否出错，并把判决结果（应答信号）反馈至发送端。发送端把接收端认为有错的信息重新发出，直到接收端认为正确为止。,检错、不纠错,ARQ特点 需要双向控制和反馈信道。 系统的控制设备和存储设备复杂，但编译码设备较简单。 接收端检错能力、系统纠错能力强，可大大降低系统误码率。 具有自适应性。但若重发频繁，将使效率降低，甚至系统阻塞，使
4、得连续性和实时性变差。 在短波、有线干扰情况复杂的信道，在计算机网络、分组交换网、卫星通信、移动通信中广泛应用。,3、混合纠错(HEC)方式： 前向纠错FEC+反馈重发ARQ 发送端发送的是兼有检错和纠错能力的码；接收端收到码字后，首先检测错误情况。当差错在码的纠错能力范围内，就自动纠错；当差错很多已经超出了纠错能力，但能够检测到错误，接收端就通过反馈信道，请求重发。,检错、纠错,HEC的特点 总体性能介于FEC和ARQ之间，误码率低，但需要反馈信道。 实时性和连续性好。 设备不太复杂，应用广泛。,4、信息反馈(IRQ)方式(回程校验方式): 接收端收到信道传输来的码后，全部由反馈信道发回发送
5、端；发送端将发送的码与反馈回的码进行比较，发现错误后，把出错的码再次重发，直到接收端认为正确为止。,不检错、纠错,IRQ特点： 需要双向控制，需要反馈信道。 系统的控制设备和存储设备相对复杂。 无需编译码设备，接收端不具备检、纠错能力强，整体系统纠错能力强，可大大降低整个系统误码率。 具有自适应性，但若重发频繁，将使传输效率降低，甚至系统阻塞，使得连续性和实时性变差。,5、检错删除： 接收端发现错码后，立即将其删除。 适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。 6、差错隐藏： 在某些应用领域，如音乐、语音、图像、视频等领域，有差错或损失的部分数据对人的主观感受影响不大，此时
6、，可根据已接收的数据采用内插或外推的技术，得到满足应用的输出数据。,9.2 纠错码分类,1、纠错码的分类： 按纠正错误的类型分类： 纠随机差错码：无记忆信道中，噪声随机独立地影响每个码元，造成了随机差错； 纠突发差错码：有记忆信道中，突发噪声可造成突发性的成群差错（如太阳黑子、雷电等引起）。 纠混合差错码 按应用目的分类： 检错码只能检测错误是否存在。 纠错码能够检测错误，并能够自动纠正错误。 纠删码能够纠正删除（丢失）了的信息。,按码元取值分类： 二元纠错码目前最常用模式 多元纠错码 按码的结构中对信息序列的处理方式分类： 分组码（n,k）将信息序列每k位分组，再增加入r=n-k 个冗余码元
7、（校验元），校验元只由本组k个信息元按照一定规律产生，与其他信息组无关。 卷积码（n,k0,L）将信息序列每 k0 位分组，编码器输出该段的r=n-k0个与本组和前L组信息元相关的校验元，得到n长的码字。,按码的数学结构中校验元与信息元关系分类： 线性码线性关系，如线性方程组 非线性码非线性关系 按码的是否具有循环性分类： 循环码分组码中任一码字的码元经过循环移位后，仍是本码中的码字。 非循环码至少有一个码字经循环移位后，不再是本码中的码字。 按构造码的数学理论分类： 代数码近世代数，比较完善，如线性分组码。 几何码投影几何学 算术码数论，高等算术 组合码排列组合，数论,实际的码可能同时分别具
8、备以上某些特征，比如：某一纠错码可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代数码等。,9.3 纠错码的概念及其纠错能力,信息序列,码字序列,接收序列,译码后信息序列,噪声源,E 错误图样,对编码器的输入信息序列，每k个信息符号分成信息组： m=（mk-1,mk-2,m0），mi为信息元（i=0,1,k-1）。 （在q元数字通信系统中，共有 种信息组。） 码字： 为了纠错，编码器按一定规则增加产生r个多余符 号，形成长度为 n=k+r 的序列： C=(cn-1,cn-2,c0), ci为码元（i=0,1,n-1） 校验元：增加的 r=n-k 位码元。 n：码长；k：信息组长度； r
9、：校验元的位长。,1、信息元、校验元、码字：,码C中的码字个数（k为信息位数）： （n,k）分组码：编码器输出为 个码字组成的序列； 许用码字： 种码符号序列中，取出 个作为分组码的码字。 禁用码字：其余 种码符号序列。 卷积码（n,k0,L）:编码器输出的校验元不仅由本组信息元有关，也与其前面若干段的信息组所确定。,2、码字的汉明重量： 汉明距离D(C1,C2)：对应位置上不同码元的个数。 码的最小距离：dmin, d(C) 汉明重量（汉明势）：码字中非零码元的个数 W(C)。 对2元码，汉明重量为码字中的“1”的个数。因此，二 元码字的汉明重量和汉明距离为：,模2加，若对应位不同则为1；相
10、同则为0。 其重量即为不相同的总位数，也就是两个码字的汉明距离。,3、错误图样： 码字序列通过信道传输送入译码器之前，由于信道的 噪声干扰，使得接收序列中某些码元发生差错，可用错误 图样（差错图样）定量描述： E=(en-1en-2e1e0)=CR 二元数字通信系统中，码元传输错误图样： E=(en-1en-2e1e0), ei =0,1 ,i=0,1,n-1 若 ei =0 ， 第i位码元无差错； 若 ei =1 ， 第i位码元发生差错；,差错关系： 接收序列 = 许用码字 + 错误图样 R=(rn-1rn-2r1r0), ri =0,1 ,i=0,1,n-1 接收序列长度 = 码字长度 =
11、 错误图样长度 = n 差错类型： 随机差错是相互独立的、不相关，存在这种差错的信道是无记忆信道或随机信道； 突发差错指成串出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串码元。,例 发送码字 C= 010110111, 接收序列 R= 001110011, 错误图样 E=C+R= 011000100 若为随机差错，错误码元为： 2，3，7，错误数量=W(E)=3； 若为突发差错，错误码元串长度为：6； 出错范围：从错误图样E中的第一个1到最后一个1， 其错误串中的0表示该位码元未发生错误。,BSC（二元无记忆对称信道）的错误图样的出现概率 设p为错误概率(1),则n次无记忆扩展
12、信道中，随机差错的某错误图样E的出现概率为：,0位差错（全对）： W(E0)=0， 1位随机差错： W(E1)=1, 2位随机差错： W(E2)=2, e位随机差错： W(Ee)=e, n位差错（全错） W(En)=n,差错图样数,概率,错误图样的总数：,发生多位错误的概率小于较少位数随机错误的概率。 因此，无记忆信道中，一般优先纠正较少位数的随机错 误，如1-2位，此时的误码率就可下降几个数量级。,错误图样出现的概率关系（p1）：,4、分组码的纠错能力与码最小距离的关系 一般地，分组码的码间最小距离 dmin 越大，意味着任 意码字间的差别越大，则码的检、纠错能力越强。 检错能力： 如果一个
13、分组码能检出总位数e 个码元的任何错误图样，称码的检错能力为 e。 纠错能力： 如果分组码能纠正总位数t 个码元的任意错误图样，称码的纠错能力为 t。,例 重复码（3，1）为：（000，111），最小码间距为3。 两个码字在传输后发生1位错误的接收序列形成两个互不相交的子集，按照最小距离译码准则，就能纠正1位随机错误。若发生2-3位错误，则接收序列进入另一个子集内，无法纠正。,定理：对于一个（n,k）分组码C，最小距离为dmin，则： 若能检测（发现）e个随机错误，则要求 dmin e+1 ; 或：可检测出任意小于等于 e = dmin1个随机差错； 若能纠正 t 个随机错误，则要求 dmin
14、 2t+1 ; 或：可纠正任意小于等于 t= INT (dmin-1) / 2个随机差错； 若能纠正 t 个随机错误，同时能检测e t 个随机错误，则要求： dmin t+e+1 。,设V,U为距离最小的两个许用码字。若某码字传输发生错误，按最小距离准则译码，为了检测 R=U+E： 须dmin e+1，否则，会发生码字译码混淆，如 R+E =V 。,设V,U为距离最小的两个许用码字。若某码字传输发生错误，按最小距离准则译码. 若 R=V+E，W（E）= t，则若 dmin 2t+1 , 则可能译码为 U。错误！ 当 dmin 2t+1，D（R，V） D（R，U）译码为 V 。 正确！,设V,U
15、为距离最小的两个许用码字。 自接收序列中码字分别发生t位错误和e位错误，要检错、纠错，需要使得大球和小球不相交。故： 须dmin e+t+1，否则，译码时引起码字译码混淆。,5、分组码的码率 二元无记忆信道中，（n，k）分组码个数为： 也就是说，信道输入的消息数目为M。 信道输入的信息流可以认为是去除了信源剩余度的的无 记忆等概分布的信息流，则信道信息传输率（码率）： 表示了信息位在分组码码字中所占比重，反映了每个码 元符号携带的信息量。是衡量其有效性的重要参数。,9.4 线性分组码,概念： 分组码中的信息元和校验元是用线性方程联系起来的一类差错控制码。 线性分组码的编码过程： 把信息序列按一
16、定长度分成若干长度为k位的信息码组； 编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成 n 长 (nk) 码字，其中 (nk) 个附加码元是由信息码元的线性运算产生的。 对于二元码，信息码组长 k 位，有 2k 个不同的信息码组，则有 2k 个码字与它们一一对应。,2、 一致监督（校验）方程 编码方法：已知信息码组k位信息位，按预定规则生成 r 个监督（校验）码元，与信息位一起构成码字。 要求：每个监督元是其中某些信息元的运算结果。 （以下仅讨论二元码） 例：k=3, r=4，构成 (7,3) 线性分组码。设码字为 (C6,C5,C4,C3,C2,C1,C0) 其中，C6,C5,C4为信息元，C3,C2,C1,C0为监督元，码元取0或1。 监督元可按下面方程组计算,一致监督（校验
