差错控制编码资料
1,第九章 差错控制编码,主要内容： 纠错编码的原理 线性分组码 循环码 卷积码,（数字通信特有）,2,9.1 引 言, 信号在信道中受到干扰,干扰种类：乘性码间干扰；克服方法：均衡器, 加性干扰的类型：,突发型错码：错码成串集中出现； 原因：脉冲干扰，衰落,混合型错码：,加性错码；克服方法：差错控制编码,随机型错码：错码是随机出现的，相互间统计独立 原因：白噪声。,提高信号抗加性干扰的能力,3,CCITT 建议的误码率标准,检错重发、前向纠错、反馈校验、检错删除, 差错控制的方法,4,检错重发：如接收端检测出错码，通知发端重发，直到 (ARQ) 接收正确为止。此方法只能判断是否有错码， 不能判断具体的错码位置。所以，只能检错不 能纠错，且需要双向通道。,前向纠错：收端能检测出错码，并可以确定错码的位 (FEC) 置，并予纠正。此方法只需要单向通道。实 时性好，但设备复杂。,反馈校验：接收端将收到的信号原封不动的发回发端，由发端将其与原发信号相比较，如果有错则重发。这种方法需双向通道，效率低，设备简单,检错删除：如：重复发送的的遥测信号。,5,自动请求重发系统（ARQ）,工作过程：,2）重发控制器收到重发命令时，控制输入缓冲储存器重发一次当前码组，否则发送后一码组。,1）收端解码器检测出错码时由指令发生器产生重发命令传给发端，同时发出删除命令，删除输出缓冲器内容。,6,优点：1）监督码少; 2）对各种信道有一定的适应能力； 3）成本及复杂性低。,缺点：1）需要双向通道； 2）干扰大时系统可能处于重发循环中，效率降低； 3）实时性差。,7,在信息码序列中加监督码元，监督码和信息码之间存在一种逻辑关系。因此，收端可以利用这种逻辑关系发现或纠正存在的错码。,一般来说，监督码元越多，检、纠错能力越强。用降低传输速率换取传输可靠性的提高。 不同的编码方法，有不同的检错或纠错能力。 目标：监督码元要少，检、纠错能力要强。,9.2 纠错编码的基本原理,8,例：表示天气,结论：虽然接收码组有错，但接收端无法识别。,错 1 位,9,增加一位监督码,错 1 位,错 2 位,结论：可以检测出 1 位错码，但不能纠错。,禁用码组：非信息码组,许用码组：有效信息码组,码距,10,结论：能纠正 1 位错码，或检测出 2 位错码。,错 1 位,错 2 位,增加三位监督码,码距关系,11,特征：分组码中的监督码元仅监督本码组中的信息码元。,分组码定义：将信息码分组，为每组信息码后附加若干监督码元形成的码集合。, 分组码,k ： 码组中信息码元的数目。 n ： 码组的总位数，又称为码组长度。 r = n - k ：码组中监督码元的数目。 编码效率：k/n；冗余度：(n-k)/k,符号：( n , k ),12,结构,码长 n = k + r,k 个信息位,r 个监督位,码组重量：码组中 “1 ” 的数目。,码距 d ：两个码组对应位上不同的码元个数，称为汉明距离。,最小码距 d0 ：码集合中任意两两码组间距离的最小值。,天气编码举例,13, 检测 e 个错码，要求最小码距, 纠正 t 个错码，要求最小码距, 纠正 t 个错码、同时检测 e 个错码，要求最小码距, 码距与码集合检、纠错能力的关系,A,B,例： A = ( 00000 ) 、B = ( 11111 )， d0 = 5,结论：e = 4 或 t = 2 或 t = 1 、 e = 3,d = 1,d = 2,d = 3,天气编码举例,14, 奇数监督码:使码组中“1” 的个数为奇数, 偶数监督码:使码组中“1” 的个数为偶数,码距为2，能检测奇数个错码,二维奇偶监督码（矩阵码）,生成规则： 许用码组写成一行（包括信息码和1 位监督码），设共有m 行。第 m+1 行为按列增加的监督码。（构成监督码行）,1、奇偶监督码,一维奇偶监督码： 1 位监督码；,9.3 常用的简单编码,常用,an-1an-2a0=1,an-1an-2a0=0,15,例 :一维偶数监督码,错 1 位,满足：,检验:,只能检错，不能纠错,返回,16,1）设 和 发生错码，按行无法检测出有错，而 按列可检测。,a2 a1 a0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0,例 二维偶数监督码,通式,突发性错码,2）能检测突发性错码；适用于突发信道。,17,3）若仅一行有奇数个错码时，可通过列确定错码位置并纠正。 4）当 同时出错，则按行按列均不能检测 出有错。 5）方阵码除了在行列上的错码都为偶数时，无法检测外，其余均能检测。,上页,18,2恒比码 在恒比码中，每个码组均含有相同数目的“1”(和“0”)。这种码在检测时，只要判断接收码组中“1”的数目是否正确，就能判断有无错误。 P286表9-2中的保护电码，每个码组的长度为5，其中恒有3个“1”，称为5/3恒比码。用于我国的汉字电传编码。 从5中取3的组合数C35=5!/(3! 2!)=10。这10种许用码组恰好可用来表示10个阿拉伯数字。用4位阿拉伯数字表示一个汉字。 在无线电报通信中，广泛采用的是 7/3恒比码，这种码组中总是有3个“1”。共有7!/(3！4!)=35种许用码组，它们可用来代表26个英文字母及其他控制符号。,19,特征：具有纠正 1 位错码、检测 2 位和大部分 2 位以上错码的能力,定义：信息码位数与监督码位数相同,编码 规则：,1）当信息位中有奇数个“1”时，监督位是信息位的重复,2）当信息位中有偶数个“1”时，监督位是信息位的反码,1 0 0 0 1,例：若信息码为 1 1 0 0 1,3、 正反码,则正反码为 1 1 0 0 1 1 1 0 0 1,1 0 0 0 1 0 1 1 1 0,1）将接收码组中信息码和监督码对应按位模2 加，得合成码组,2）根据接收码组中信息码含 “1” 的奇偶情况，由合成码组生成校验码组,3）根据校验码组的组成，依表判断错码情况，并予检错与纠错,译码 规则：,“1”为奇 校验 = 合成 “1”为偶 校验 =,20,例：发 1 1 0 0 1 1 1 0 0 1,1）收无错, 信息码中含奇数个“1”,2）收有错、为 1 0 0 0 1 1 1 0 0 1,合成码组=,1 1 0 0 1 1 1 0 0 1,0 0 0 0 0,译码判决：, 校验码组 = 合成码组 = 00000,判断接收无错码,合成码组=,1 0 0 0 1 1 1 0 0 1,0 1 0 0 0, 信息码中含偶数个“1”,查表知信息码第二位错,特征：编码效率低,21,9.4 线性分组码,汉明码的编码原理,一般线性分组码的编码原理,（可以纠错）,线性码：监督码和信息码之间的关系是线性关系,22,分析偶数监督码，寻找逻辑组合,监督方程,所以解码就是要计算,只能表示出错 不能描述错码位置,一位监督码对应一个监督方程，即对应一个校正子,结论：若增加监督码元，建立多个监督方程，多个校正子就能形成逻辑组合描述错码位置。 r位监督码对应r个校正子，就有2r 种组合，用其中一种组合表示无错，其余2r-1种组合表示错码的位置。,9.4.1 汉明码,s=an-1an-2a0,an-1an-2a0=0,校正子,23,确定监督关系表,建立监督方程,建立编码方程,如果只错一位，分组码(n,k)中的错码有n个可能的位置 ，要用r 位监督码表示这n 个错码的位置， 为提高编码效率， r 取最小值,例：已知( 7 , 4 )码，r = 3, 共有3个监督方程， 构成 3个校正子 S1 S2 S3,只纠正一位错码,24,求码组集合,k = 4，信息码组有 16 个,能纠正一位错码，且2r-1=n的线性分组码，称为汉明码。,其编码效率为 k/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n 当n很大时，则编码效率接近1。可见，汉明码是一种高效码。,25,汉明码的监督方程为,用矩阵表示,9.4.2 一般线性分组码的编码原理,记为：,监督矩阵,码组向量,当 称 H 为典型监督矩阵（含单位阵）,错误图样,26,根据监督方程确定了编码方程,两边同取转置,构造生成矩阵,G 为典型生成矩阵, 编码矩阵方程,特点：信息位不变，监督位附加于其后。,由典型生成矩阵得出的码组 A是系统码,27,生成矩阵,G 中每行均为一个码组，且线性无关 若能找到k个线性无关的已知码组，就能构成矩阵G。,循环码生成矩阵,28,译码运算，当,S 为校正子。说明 S 与E 有确定的线性关系,若 E 的数目有限，能与 S 一一对应， 则 说明 S 能描述错码的位置，具有纠错能力。,令 发码组为 A、收码组为 B, 错码图样 E = B- A,错误图样收发码组的关系,令 B =E + A,29,发码组 A = 1 1 0 0 0 1 0,收码组 B = 1 0 0 0 0 1 0, 译码运算,例： ( 7 , 4 )汉明码, a5 错,含义：错码图样 E =（0 1 0 0 0 0 0） 只有一位错码,30,线性码中任意两个码组之和仍为这种码中的一个码组,证： 设 A1 、 A2 为线性码中两个许用码组,两式相加,是许用码组,推广：,1）两个码组间的距离必是另一码组的重量,2）除 全0 码组之外，编码的最小码重是码集合的最小码距。,线性分组码的性质：封闭性,3)线性分组码中必有全0码； （信息码全0，监督码全0）,31,9.5 循环码,9.5.1 码多项式,9.5.2 循环码的特性,9.5.3 循环码的编码方法,循环码是线性分组码中一种重要的编码。它是在严密的代数理论基础上建立起来的。其编码和解码不太复杂，但检(纠)错的能力较强。循环码除了具有线性码的一般性质外，还具有循环性，见表11-5。,32,码多项式的模运算：,9.5.1 码多项式,码多项式以码组中各码元为系数的多项式,T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0,设 多项式 F(x)、除式为 N(x),注：多项式按模 N(x) 运算过程中，其系数均为模2 运算。,x 仅为码元位置的标记,模 N( x )； R( x )：余式,例：( 110 0101 ) T( x ) = x 6 + x 5 + x 2 + 1,33,例：,解：,记为：,余式,系数为二进制，只能取0或1，二进制的加减都是一样的,34,用码多项式的运算来表示：若T(x)对应一个码长为 n 的许用码组，则x i T(x)按模x n+1运算后余式T´(x)仍为许用码组。,证： 令, T´(x)的系数是T(x)中系数向左循环移位 i 次的结果,9.5.2 循环码的特性,编码中任意一个码组，左移或右移一位得到的新码组必是该码集合中另一码组。,生成多项式, T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0, x iT( x ) = an-1 x n-1+i + . + an-1-i x n-1+ . + a0 xi,x iT(x) an-1-i x n-1 +. + a0 x i + an-1 x i-1 + . +an-i,35,例： ( 7 , 3 )循环码, 码组为( 110 0101 )，验证 x 3 T( x ) 按模 x 7 +1 运算后余式仍是一个许用码组 。,解： T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0, T( x ) = x 6 + x 5 + x 2 + 1, x 3 T( x ) = x 9 + x 8 + x 5 + x 3, 余式T´(x) 对应码组为(0101
