资源描述
现代通信原理第十一章 差错控制编码7/17/2024第十一章 差错控制编码 l11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能11.1 概述l误码分类噪声引入的随机误码,均匀分布由干扰、快衰落引起的突发误码l如何减少误码?从信源编码看,误码引起的性能恶化尽可能小,容错技术从传输看,可采用抗干扰能力强的调制方式,信道特性不理想可采用均衡。特别需要差错控制技术。数字通信中,要求误码率108以下,必须采用差错控制。11.1.1 差错控制分类1.反馈检验法2.检错重发法(ARQ)3.前向纠错(FEC)1.反馈检验法需要双向信道,和前向信道有相同的通信容。引入较大的停顿(不实时)。可以纠正任何错误。2.检错重发法(ARQ)自动请求重发也需要反向信道,但容量可以降低,也会引入停顿3.前向纠错(FEC forward error correctionforward error correction)不需要双向信道不会引入停顿靠纠错编码11.1.2 差错控制编码的基本原理l如用三位二进制编码来代表八个字母000 A100E001 B101F010C110G011D111H不管哪一位发生错误,都会使传输字母错误l如用三位字母传四个字母000 A011B101 C110D发生一位错误,准用码字将变成禁用码字,接收端就能知道出错,但是不能纠错。差错控制编码l如用三位字母传二个字母000 A111B检三个错误,纠正一个错误。l结论具有检错或纠错的码组,其所用的比特数必须大于信息码组原来的比特数引入多余度。码重、码距l码重(weight)l一个码组中“1”的数目l码距(distance)l两个码组之间对应位置上1、0不同的位数,又叫汉明(Hamming)距。10 1 1 0 码重:301 1 00 2 距离:3检错、纠错能力1)为检查出 个错误,要求最小码距为2)为纠正 个错误,要求最小码距为3)为纠正 个错误,同时检查出 个错误,要求最小码距为 11.1.3.差错控制编码分类l按功能分l检错码 l纠错码l纠删码(发现不可纠正的错误时,可发出指示或删除)l按信息码元和监督码元之间的校验关系分l线性码l非线性码l按信息码元和监督码元之间的约束方式分l分组码l卷积码香农理论l纠错码建立在香农理论基础上l香农定理存在噪声干扰的信道,若信道容量为C,只要发送端以低于C的速率R发送信息(R为输入到编码器的二进制码元速率),则一定存在一种编码方式,使编码的错误概率随着码长n的增加将按指数下降到任一的值,即l结论如码长及发送信息速率一定,可以通过增大信道容量,使P减小。如在信道容量及发送信息速率一定,可以通过增加码长,使错误概率下降。分组码l表示:(n,k)n:帧长k/n:编码效率l特点监督码只用来监督本帧中的信息位l分类线性码 信息码与监督码之间为线性关系非线性码 不存在线性关系 奇偶监督码l偶监督l奇监督l如果以上关系被破坏,则出现错误,因此能检查出奇数个错误,但不能检测偶数个错误。最小码距为 dmin=2l这种码检错能力不高,采用什么方法提高呢?水平奇偶监督码和水平垂直监督码l又叫 二维奇偶监督码l水平奇偶监督码检码字按行排成方阵,每行采用奇偶监督码,发送时按列的顺序传送,接收时仍将码字排列成发送时方阵形式,然后按行进行奇偶校验。在不增加冗余度时,不仅能发现某一行上奇数个错误,而且也能发现不大于方阵行数的突发错误。l水平垂直奇偶监督码不仅对行进行奇偶校验,而且也对列进行奇偶校验。等比码l在码长一定时,“1”码和“0”码的比例恒定。已用于电报传输中。l五中取三0101111001表示十位数字,C53=10种许用码组。第十一章 差错控制编码 l11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能11.2 分组码(1)l汉明码:能纠一位错误(7,4)分组码(2)在接收端,按如下规律运算分组码(3)l分组码的监督方程l矩阵形式分组码(4)l监督矩阵lH矩阵称为典型形式,各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形式,通过监督矩阵可以知道监督码和信息码的监督关系。分组码(5)l生成矩阵 ,通过生成矩阵可以得到生成码组。l如果输入码组为 0011分组码(6)l由这种方式得到的生成矩阵称为典型生成矩阵,由它产生的分组码必定为系统码,也就是信息码字保持不变,监督位附加其后,每行一定是线性无关的,每行都是一个生成码组。汉明码汉明码监督位为 位,因此它可以组成 个可能情况,其中一个为无错。因此可以监督码位共 要纠正一个错误,必须满足最小码距l如果 r 位监督位所组成的校正子码组与误码图样一一对应,这种码组称为完备码(取等号时)扩展汉明码l如果在汉明码基础上,再加上一位对所有码字进行校验的监督位监督码字由 r 位增加到 r+1 位信息位不变l码长 码结构l纠 1 位错,检测 2 位错l如(8,4),(16,11)扩展汉明码矩阵 如(7,4)(8,4)缩短汉明码l(n,k)(n-s,k-s)l如(15,11)(12,8)监督矩阵 Hs 是将原 H 的前 3 列 去掉l缩短汉明码的最小码距至少和原来码的码距相同,因为监督位没有变。缩短汉明码l能纠 t 个错误的(n,k)应满足取等号时为完备码l不同结构的线性码其纠错能力不同,能力和dmin 有关,dmin 越大越好。最小码距界限l上界:汉明界,普洛特金界l下界:吉尔伯特界l问题:给定码长与编码效率,寻找 dminl例:dmin=5,码长=63 的分组码设计从汉明界得,因此信息位最多可以取最小码距界限l通过吉尔伯特界求下界l线性码 k 越接近 52,效率越高。第十一章 差错控制编码 l11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能11.3 循环码(Cyclic code)l1957 年发现l特点线性分组码循环性任一许用码字经过循环移位后,得到的码组仍为一个许用码组l如 是循环码的一许用码组 l则 也是一许用码组 码多项式表示l码组码多项式码组码多项式l左移一位l左移 位循环码性质l 为许用码组,则 也是许用码组l性质若 是长度为n的循环码组,则 在按模 进行运算后,也是一个循环码组,也就是 用 多项式除后所得之余式,即为所求的码组。循环码例子码组左移 3 位去除 得余式如 左移 3 位后,得 是许用码组循环码生成多项式g(D)lg(D)是 D的(n-k)次即r 次多项式l信息多项式为M(D),k 位,(k-1)次多项式g(D)l定理.一个(n,k)的二进制循环码可以看成是唯一由它的生成多项式产生,即J如(7,3)循环码,n=7,k=3,r=4J如果信息位为 010,M(D)=D 生成码为 生成矩阵 G(D)l由于 k 位信息位共有 个码组,都可用此法产生,如果现有信息码 生成 k 个码字,且这 k 个码组都线性无关,用这 k 个码组作为一个矩阵G 的 k行 构成生成矩阵 G(D)称为循环码的生成矩阵多项式(7,3)循环码l(7,3)循环码生成矩阵生成矩阵和监督矩阵l这样构成的循环码并非是系统码l系统码的生成矩阵典型形式 l非系统码 系统码生成矩阵监督矩阵非系统码 系统码l系统码的码多项式为l例如,(7,4)码,1011 非系统码 系统码l(7,3)码寻找生成多项式l 循环码的生成多项式必须能除尽 h(D)是监督多项式,是 K阶多项式l例:要构成(7,3)循环码,求g(D).解:g(D)应为4阶 都能生成(7,3)l生成(7,6)循环码l生成(7,1)循环码 循环码的编码器l原理:按系统码的生成方式:将信息码多项式升(n-k)次幂后,再除生成多项式,然后将余式置于升幂后的信息多项式之后以(7,4)码为例 循环码的译码器l译码比编码复杂得多l译码三步伴随式S的计算由S得到错误图样纠正伴随式的计算l发送码组 l接收码组l误差码组l校正子只与 E 有关,根本是计算校正子 校正子S的计算l生成多项式 g(D)去除接收码字B(D)第十一章 差错控制编码 l11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能11.4 BCH码l特点:它也属于循环码,具有纠多个随机错误的能力,构造容易。因此由码的最小距离,可以很快得到码的生成多项式l即约多项式一个 m 次多项式不能被二元域上任何次数小于m的,但大于0的多项式除尽,如 是即约的。l本原多项式若m次多项式P(x)除尽的 的最小正整数 n 满足 ,就称为本原的。如 能除尽 ,但除不尽 的 。如:是即约的,但不是本原的,因它能除尽 。11.4.1 本原循环码l由本原多项式构成的码称为本原码。l特点码长为它的生成多项式是由若干m阶或以m的因子为最高阶的多项式相乘而构成。l要判定(n,k)的循环码是否存在,只需要判断 n-k 阶的生成多项式是否能由 Dn+1的因式构成。循环码例子l生成多项式的阶次为 r,该生成多项式是否是 的因此。l一个m阶即约多项式一定能除尽l如,m5,共有6个5阶即约多项式。l再加上 因子,是以上7个多项式的乘积。循环码例子l表11-12表示了m12的即约多项式l在表中多项式的系数是用8进制表示的,而且反多项式没有表示 如 m=5,45,75,67 100101 111101 11011111.4.2 BCH 码的生成多项式l如果循环码的生成多项式具有如下形式l 为纠错个数,为最小多项式,为最小公倍数,由这种方式生成的循环码是BCH码最小码距 码长为 的BCH码称为 本原BCH码(狭义BCH码)码长为 则称为非本原BCH码 BCH 码l由于g(D)有t个因式,且每个因式的最高次为m,因此监督码元最多有mt位。l对于纠t 个错误的本原BCH码,其生成多项式l纠单个错误的本原BCH码为汉明码。表1113给出了 n511的本原BCH码。1114给出了部分非本原BCH码。BCH 码例子l纠正 3 个错误,码长为15的BCH码解:n=15,m=4 查表11-12得,23 37 07 m1(D)m3(D)m5(D)这是(15,5)码。重要的BCH码(23,12)l表1114中最重要的非本原BCH码是(23,12)称为格雷码,码距为7,能纠正3个错误。生成多项式 它是一个完备码l在实际通信系统中,所要求的n、k并不是码表中所推荐的值,在这时我们可以采用缩短或扩展的方式加以修正,也就是通过增加信息符号或校验符号来增加码组长度,或减少信息和校验位来减少码组长度。BCH码l如 BCH码的码长为奇数,而有时需要偶数码长,这时可以在原BCH码生成多项式中乘以(D+1)因子,从而得到(n+1,k)扩展BCH码,这时相当于在原BCH码上加一个全校验位,从而将码距增加1,这时的码字不具有循环性。l如果BCH码不是2m-1或它的因式,这时可以采用缩短的方式,去掉s位信息,(n-s,k-s)缩短BCH码RS码 Reed-Solomonl非二进制BCH码,输入以符号来考虑l假定每组有 K 个符号,每个符号用m比特,输入信息将是 Km 比特。RS码一般写成(n,k,d)最小码距RS码lRS码适合于纠正突发错误,纠正的错误图样有l对于一个长度为 符号的RS码,每个符号都可以看成是有限域 中的一个元素,如RS码的最小码距为d符号,则生成多项式第十一章 差错控制编码 l11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能11.5 纠正和检测突发错误的分组码交织码interleavedl在水平垂直监督码中将信息码排列成方阵,然后对行和列分别进行检验,可以达到检测突发错误的目的。l如果方阵中行码是能纠 t 个随机错误,交织后能纠t个长度为i的突发错误。i称为交织深度。l如果每行能纠正 b 个突发错误,用上面的同样方法,构成方阵,可以纠正突发长度为bi个突发错误。l通常把i称为交织深度循环码构成交织码l采用循环码构成交织码时,可以不采用方阵就能实现编码。l假设交织码每行为 循环码,其生成多项式为 ,可以除尽 ,如交织深度为 其交织码为 ,其生成多项式为 可以除尽 ,所以 也是循环码。循环码构成交织码(续)l如,循环码(7,4),其生成多项式为构成交织深度为3 的(21,12)交织码。交织码的生成多项式为它也是循环码,可以用循环码的方式构成。在发送端可以不排成方阵,但是在译码时,必须将码元排列成 阵列,然后分别独立的对每行码字进行译码。交织码 之小结l为了进一步提高纠错能力,可以在交织阵列中不仅对每行进行纠错编码,而且也对每列进行纠错编码,这种形式的交织码称为乘积码。l若乘积码的行码和列码 分别能纠长度不超过 的突发错误,则乘积码能纠正长度为 的突发错误。l交织一般都带固有延时,在语音中交织的延时不要超过40ms。法尔码 Firel也是循环码,能纠单个突发错误。法尔码的纠错能力CRC 码l循环冗余检验码,简称CRC,也是循环码。l能检测出以下错误常用 CRC 码l常用的四种,已经成为国际标准。表11-16 常用的CRC码码生成多项式CRC-12CRC-16CRC-32CRC-CCITTD12+D11+D3+D2+D+1D16+D15+D2+1D16+D12+D5+1D32+D26+D23+D22+D16+D12+D11+D10+D8+D7+D5+D4+D2+D+1第十一章 差错控制编码 l11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能11.6 纠错码的误码特性l任何纠错码的能力都是有限的,超出纠错码能力的错误不可能纠正,甚至会出现乱纠的现象。l采用纠错后,误码性能的改善?l由于纠错码种类很多,纠错能力各不相同,译码方法也不同,因此其性能必须根据具体分析和计算。BSC&AWGN lBSC如果纠正 t 个随机错误,则 Pe为不加纠错 时的误码率lAWGNBPSKBSC&AWGNlRb Rc Eb Ec 这时的功率要降低 Rb采用1/2编码时,Rc=2Rb Eb Eb 降低了3dB 编码增益 G=加纠错和不加纠错时,达到同样误码率时的信噪比之差
展开阅读全文