[工学]通信原理_第十一章_差错控制编码.ppt

1、,11.1 概述 11.2 纠错编码的基本原理 11.4 简单的实用编码 11.5 线性分组码 11.6 循环码 11.7 卷积码,第十一章 差错控制编码,本章内容简介,11.1 概述,一. 差错的产生,二. 差错控制方法,噪声与干扰,检错重发法：双向信道工作。接收信息方具有检错能力，收到信息无误，回发肯定应答；有误则不发应答或发否定应答。,前向纠错法：单向信道工作。接收信息方具有纠错能力，发现收到信息有误时，确定误码的位置并按规则予以纠正。,反馈校验法：双向信道工作。接收信息方简单地将收到信息回传给发送方，由发送方判断前次发送是否无误。,第十一章 差错控制编码,11.1 概述,三. 自动要求

2、重发(ARQ)系统,第十一章 差错控制编码,数据按分组发送。每发送一组数据后发送端等待接收端的确认(ACK)答复，然后再发送下一组数据。 图中的第3组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第3组数据。 系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。,停止等待ARQ系统,11.1 概述,三. 自动要求重发(ARQ)系统,第十一章 差错控制编码,拉后ARQ系统,发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认(ACK)或否认(NAK)答复。 例如，图中第5组接收数据有误，则在发送端收到第5组接收的否认答复后，从第5组开始重发数据组。 在这种系统

3、中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。,11.1 概述,三. 自动要求重发(ARQ)系统,第十一章 差错控制编码,选择重发ARQ系统,它只重发出错的数据组，因此进一步提高了传输效率。,11.1 概述,三. 自动要求重发(ARQ)系统, ARQ系统主要优点: 1. 只需少量多余码元； 2. 适应不同差错特性； 3. 检错方法简单。, ARQ系统主要缺点: 1. 需要双向信道； 2. 出错率高时，重发降低信道效率； 3. 信息传输实时性差。,第十一章 差错控制编码,11.1 概述,四. 差错控制编码,在信息码元序列中加入一定数目的监督码元就称为差错控制编码。,

4、差错控制编码的检纠错能力, 差错控制编码的编码效率（码率）,一般说来，差错控制编码的检纠错能力取决于： 在信息码元序列中加入的监督码元的多少。对于一定长度的信息码元序列,加入的监督码元越多，检纠错能力越强。 不同的编码规则与方法（有不同的检错或纠错能力）。,在一定长度信息码元序列中加入监督码元的数目越多, 差错控制编码的编码效率越低。如信息码长为k，监督码长为r,则编码效率为k/(k+r)=k/n。监督码元数r 和信息码元数 k 之比r/k = (n-k)/k 称为冗余度。,第十一章 差错控制编码,11.2 纠错编码的基本原理,第十一章 差错控制编码,分组码基本原理：举例说明如下。 设有一种由

5、3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气， 例如：“000”（晴），“001”（云）， “010”（阴），“011”（雨）， “100”（雪），“101”（霜）， “110”（雾），“111”（雹）。 其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。,11.2 纠错编码的基本原理,第十一章 差错控制编码,若在上述8种码组中只准许使用4种来传送天气，例如： “000”晴 “011”云 “101”阴 “110”雨 这时，虽然只能传送4种不同的天气，但是接收端却有可能发现码组中的一个错码。 例如，

6、若“000”（晴）中错了一位，则接收码组将变成“100”或“010”或“001”。这3种码组都是不准使用的，称为禁用码组。 接收端在收到禁用码组时，就认为发现了错码。当发生3个错码时，“000”变成了“111”，它也是禁用码组，故这种编码也能检测3个错码。 但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组。,11.2 纠错编码的基本原理,第十一章 差错控制编码,检错和纠错 上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“100”时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。 要能够纠正错误，还要增加多余度

7、。例如，若规定许用码组只有两个：“000”（晴），“111”（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。 例如，当收到禁用码组“100”时，若当作仅有一个错码，则可以判断此错码发生在“1”位，从而纠正为“000”（晴）。因为“111”（雨）发生任何一位错码时都不会变成“100”这种形式。 但是，这时若假定错码数不超过两个，则存在两种可能性：“000”错一位和“111”错两位都可能变成“100”，因而只能检测出存在错码而无法纠正错码。,11.2 纠错编码的基本原理,为每组信息码后附加若干个监督位构成的码组集合, 称为分组码。分组码用符号(n,k)表示, k是信息位的数目

8、, n是码组总长度, n-k=r是监督位数目。,第十一章 差错控制编码,11.2 纠错编码的基本原理, 码重与码距概念, 一条码组中 “1” 的个数称为该码组的码重。 两码组中不同位的数目称为该两码组的码距。, 最小码重与最小码距, 某码组集合中含 “1” 个数最少的码组的码重, 称该码组集合的最小码重。 某码组集合中不同位数最少的两码组的码距, 称该码组集合的最小码距。,码组集合 1001001 0011011 1011100 0111011 0100011 1000100,码重 w=3 w=4 w=4 w=5 w=3 w=2,码重与码距概念举例,第十一章 差错控制编码,11.2 纠错编码的

9、基本原理, 码距(汉明Hamming距离)概念,最小码距d0 是衡量差错控制编码系统检错及纠错能力的决定性参数。,第十一章 差错控制编码,11.2 纠错编码的基本原理, 最小码距d0与检错纠错能力关系,（1）只检模式 为检测 e 个误码，要求最小码距 d0 e + 1 (11.2-2),第十一章 差错控制编码,11.2 纠错编码的基本原理, 最小码距d0与检错纠错能力关系,（2）只纠模式 为纠正 t 个误码，要求最小码距 d0 2t + 1 (11.2-3),第十一章 差错控制编码,11.2 纠错编码的基本原理, 最小码距d0与检错纠错能力关系,（3）先纠后检，纠检结合模式 为纠正 t 个误码

10、, 同时能检出 e 个误码, 要求最小码距 d0 e + t + 1 ( e t ) (11.2-4),第十一章 差错控制编码,11.2 纠错编码的基本原理, 最小码距d0与检错纠错能力关系,(1)只检模式 由d0 e + 1 , 可知系统的检错能力：最多可检出6位误码。,(2) 只纠模式 由d0 2t + 1 , 可知系统的纠错能力：最多可检出3位误码。,(3) 纠检结合模式 由d0 t + e + 1 ( e t ) , 可知: 若先纠正1位误码，则还可以检出5位以下的误码。, 若先纠正2位误码，则还可以检出4位以下的误码。,第十一章 差错控制编码,11.2 纠错编码的基本原理, 差错控制

11、(纠错)编码的效用,例如，当码长 n =7 ，Pe = 10-3 时 P7 ( 1 ) 710-3 P7 ( 2 ) 2.110-5 P7 ( 3 ) 3.510-8,采用差错控制编码,即使仅能够检出或纠正12个误码，也能使误码率降低几个数量级。,第十一章 差错控制编码,11.4 常用的简单编码,1. 奇偶监督码, 偶监督码 信息位附加监督位后，码组中“1”的个数为偶数, 即满足 an-1 an-2 a1 a0 = 0 (11.4-1), 奇监督码 信息位附加监督位后，码组中“1”的个数为奇数, 即满足 an-1 an-2 a1 a0 = 1 (11.4-2),奇偶监督码的编码效率=(n-1)

12、/n,第十一章 差错控制编码,11.4 常用的简单编码,2. 二维奇偶监督码, 二维奇偶监督码有可能检测出偶数个错误, 甚至可能纠正一些错误。 二维奇偶监督码特别适合于检测突发性错误。 二维奇偶监督码的编码效率低于一维奇偶监督码。 上例中，= m(n-1)/n(m+1),二维奇偶监督码又称为方阵码。它是将上述的m条偶或奇监督码排成一个方阵，然后沿垂直方向加上垂直监督位构成。,第十一章 差错控制编码,11.4 常用的简单编码,2. 二维奇偶监督码,举例,本例中，信息位 k = 77 = 49位，监督位 r = 7+8 = 15位，编码效率 = 49/(49+15) = 49/64,第十一章 差错

13、控制编码,11.4 常用的简单编码,3. 恒比码 (等重码),在全部码组集合中，每条码组中包含 “1” 的数目相同 。,恒比码中无法清晰地将信息位与监督位分开。因此一般只适用与传输电传机或键盘设备输入信息编码。恒比码不适合信源随机信息的编码。,4. 正反码,正反码中信息位数目和监督位数目相同。当信息位中“1”为奇数时，监督位与信息位相同; 当信息位中“1”为偶数时，监督位与信息位相反。正反码的编码效率= 1/2, 是具有纠错能力的编码。,第十一章 差错控制编码,11.5 线性分组码,前述的偶监督码，n-1个信息位附加1个监督位，构成整个码组中“1”的个数为偶数, 唯一的监督关系满足 an-1

14、an-2 a1 a0 = 0,在接收端，由收到整个码组an-1 an-2 a1 a0 ，计算校正子S S = an-1 an-2 a1 a0 (11.5-1) 单个校正子S的取值只有两种可能，“0”或“1”。若S = 0, 表示“无错”, S = 1, 表示“有错”。无法确定误码的位置进行纠正。,增加监督位的数量，可以建立监督位和信息位关系（监督关系）的多个监督关系式。在接收端，由收到整个码组an-1 an-2 a1 a0 ，计算多个校正子S1、S2 、 Sr 。组合取值有2r 种可能，一种表示“无错”, 其他2r -1种可以用来确定误码的位置以进行纠正。,第十一章 差错控制编码,11.5 线

15、性分组码,若由信息位和监督位构成的整个码组的总长度n满足 n 2r 1 或 2r n + 1 = k + r + 1 (11.5-2) 则除一种状态表示“无错”外，校正子S1、S2 、 Sr 组合的其他2r -1种状态,至少可以确定长度为n的码组中，一个单个误码的位置。,若码组的总长度n满足 n = 2r 1 或 2r = n + 1 这时r个校正子组合的2r 种状态,恰好可以表示出“无错”和n位码组当中的1位误码位置。作为能够纠正1位误码的一种编码，其编码效率是最高的, 称为汉明(Hamming)码。,能够纠正1位误码的 (7,4)、(15,11)、(31,26)、(63,57)、. ，其编

16、码效率在同码长的编码中都是最高的, 都是汉明码。,第十一章 差错控制编码,11.5 线性分组码,现在通过（7, 4）分组码例子说明汉明码的监督关系式构造。 信息位(k=4): a6 a5 a4 a3 监督位(r=3) : a2 a1 a0,可以看出，仅当1位误码位置在a2 、a4 、a5或a6时，校正子S1为1；否则S1为0。这意味着a2 、a4 、a5、a6 4个码元构成偶监督关系 S1 = a6 a5 a4 a2 (11.5-3),第十一章 差错控制编码,同理可得到关于S2、S3的偶监督关系，有 S1 = a6 a5 a4 a2 (11.5-3) S2 = a6 a5 a3 a1 (11.

17、5-4) S3 = a6 a4 a3 a0 (11.5-5),11.5 线性分组码,第十一章 差错控制编码,11.5 线性分组码,第十一章 差错控制编码,例如：接收到码组“0000011”,该码组确实是表11-4中某码组传输中产生了1位误码所致。由式(11.5-3) 、(11.5-4) 和(11.5-5) 分别计算3个校正子，有 S1 = a6 a5 a4 a2 = 0 0 0 0 = 0 S2 = a6 a5 a3 a1 = 0 0 0 1 = 1 S3 = a6 a4 a3 a0 = 0 0 0 1 = 1 根据表11-3 校正子与误码位置对应关系，可以确定1位误码的位置在a3 处，正确的

18、码组应该为“0001011”，它就是表11-4中的第2条码组。,11.5 线性分组码,如果 1 条码组在传输过程中确实产生了 1 位错误，前述的(7,4)汉明码就能无误地指出误码位置以进行纠正。,第十一章 差错控制编码,11.5 线性分组码,从表11-4 (7,4) 汉明码的全部码组可以看到，这种码的最小码距 (数值上和非全零码的最小码重相等) d0=3，用于检错可检测出 e=2 位以下的误码，用于纠错只可纠正 t=1 位误码 。这种码的编码效率= k/n = 4/7。,第十一章 差错控制编码,11.5 线性分组码,并可表示为矩阵形式,第十一章 差错控制编码,11.5 线性分组码,第十一章 差

19、错控制编码,11.5 线性分组码,对已知信息位a6 a5 a4 a3 求监督位a2 a1 a0的关系(11.5-7)扩充，变为已知信息位a6 a5 a4 a3 求整个码组a6 a5 a4 a3 a2 a1 a0的关系式,a2 = a6 a5 a4 a1 = a6 a5 a3 a0 = a6 a4 a3,第十一章 差错控制编码,11.5 线性分组码, 线性分组码具有封闭性。它是指一种线性分组码的任意两条合法码组相异或，得到的结果仍然是该线性分组码的一条合法码组。, 线性分组码的两个重要性质, 线性分组码的最小码重（全零码除外），就是该线性分组码的最小码距。这是因为，任一码组中“1”的个数（码重）

20、，都是某两条码组不相同位的数目（码距）。,第十一章 差错控制编码,11.6 循环码,循环码是一种简单、重要、常用的线性分组码。除了具有线性分组码的一般性质外，还具有循环性，即码组集合中任一码组循环左移或右移若干位，得到的结果仍然为该码组集合中的一条合法码组。,11.6.1 循环码原理,本例中，只要知道一条非全零码组,通过移位就可求出全部码组。,第十一章 差错控制编码,11.6 循环码, 码的多项式表示 对于码组an-1 an-2 a1 a0 ，若将各码元作为多项式系数，则可得到码组的多项式表示 T(x) = an-1 xn-1 + an-2 xn-2 + + a1 x + a0 (11.6-1

21、) 对于前例的 (7, 3)码, 任一码组都可表示为 T(x) = a6 x6 + a5 x5 + a4 x4 + a3 x3 + a2 x2 + a1 x + a0 (11.6-2) 而其中的第7条码组“1 1 0 0 1 0 1”可表示为多项式 T7 (x) = x6 + x5 + x2 + 1 (11.6-3),11.6.1 循环码原理,第十一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,1. 码多项式的按模运算,第十一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,1. 码多项式的按模运算,重要结论: 在循环码中，若 T(x) 是一个长度为 n 的码组，则

22、xi T(x) 在按模 xn+1 运算下，也是该循环码的一个许用码组。,第十一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,1. 码多项式的按模运算,重要结论: 在循环码中，若 T(x) 是一个长度为 n 的码组，则xi T(x) 在按模 xn+1 运算下，也是该循环码的一个许用码组。,证明详见教材。 举例 T(x)= x 4 + x2 + x + 1 是一个长度为 7 的合法码组, 可以证明 T(x) = x 3 T(x) = x7 + x5 + x4 + x3 按模 x7 +1运算,其结果为 T(x) x5 + x4 + x3 + 1 也是一个长度为 7 的合法码组。,第十

23、一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,2.循环码生成矩阵和生成多项式,生成矩阵G用于由给定信息位生成完整码组，它由 k 行n列构成，其每一行都是彼此线性无关的合法码组。 在循环码中, 一个(n,k)码有2k种不同码组。现用g(x)表示前(k-1)位皆为“0”的码组,则g(x)、xg(x) 、 x2g(x)、 xk-1g(x) 是k个彼此线性无关的合法码组, 可用来构成循环码的生成矩阵,可以证明, 除全零码外, g(x) 前(k-1)位皆为 “0” 是唯一前面连续“0”最多的码组, 且常数项一定为“1”, 否则经若干次循环移位后会得到一个信息位全零的“非全零”码组，而这

24、是不可能的。,第十一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,2.循环码生成矩阵和生成多项式,g(x) 对应前(k-1)位皆为 “0” 是唯一前面连续“0”最多的码组, 因此，除全零码外， g(x)是一个次数最低的码多项式。是一个常数项不为零的(n-k)次多项式。,典 型 化,第十一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,3.如何寻找(n,k)码的生成多项式,生成多项式 g(x) 是循环码的最关键因素。由它可容易地获得生成矩阵G , 并根据信息位产生全部码组。下面研究的 g(x)获得方法。, 由(n,k) 循环码的全部条码组寻找 g(x),g(x)=

25、x3 + x + 1,第十一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,3.如何寻找(n,k)码的生成多项式, 由(n,k) 循环码的部分码组寻找 g(x),第十一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,3.如何寻找(n,k)码的生成多项式, 由(n,k) 循环码的部分码组寻找 g(x),如何寻找 g(x) ？,第十一章 差错控制编码,11.6 循环码,11.6.1 循环码原理,3.如何寻找(n,k)码的生成多项式, 无已知条件下，求(n,k) 循环码的 g(x),如何寻找 g(x) ？,可以证明(见教材)，生成多项式 g(x) 是(xn + 1)的一个

26、因式。 上述结论告诉我们，可以通过对(xn + 1)分解因式获得g(x) 。 (xn + 1)的因式可能有多个，只有那些常数项不为零的n-k次因式才可作为(n , k)循环码的生成多项式 g(x) 。,第十一章 差错控制编码,11.6 循环码,11.6.2 循环码的编解码方法, 编码步骤,(1) 用信息码多项式m(x)乘以xn-k ，该运算相当于给信息码后加(n- k)个“0”。 例如，信息码为“110”, 相当于m(x)= x2 + x 。当n- k=7-3=4 时， xn-k m(x) = x4 (x2 + x ) = x6 + x5，相当于“1100000” 。,第十一章 差错控制编码,

27、11.6 循环码,11.6.2 循环码的编解码方法, 编码步骤,(3) 编出码组T(x)为 T(x) = xn-k m(x) + r(x) (11.6-30) 在上例中 T(x) = 1100000 + 101 = 1100101 正是表11-6中第7条码组。,第十一章 差错控制编码,11.6 循环码,11.6.2 循环码的编解码方法, 解码步骤,(1) 用接收码组 R(x) = T(x) + E(x)除以生成多项式g(x) , 得到余式 r(x) 。,(2) 根据余式 r(x)用查表方法或运算得到错误图样E(x) , 就可确定误码位置。,(3) 从R(x)中减去E(x) , 就可得到已经纠正

28、错误的原始发送码组T(x) 。,第十一章 差错控制编码,11.6 循环码,11.6.3 缩短循环码,研究表明，并不是任意码组长度n 和信息位 k 都可以找到满足某纠错能力的循环码。但若将某已知循环码缩短，就可能满足码长n 、信息位长度 k 和纠错能力要求。 给定已知(n, k)循环码集合，使前i (0 i k)个高阶信息位数字全为“0”, 于是得到有2k-i个码组的集合, 然后从这些码组中删去这 i 个零信息位数字，最终得到一组新的(n-i, k-i)线性分组码，就是缩短循环码。,例如，若欲构造具有 1 位误码纠正能力的(13, 9)码，则可以由(15, 11)汉明码的全部211条码组中，挑选

29、出前两位皆为“0”的码组29 ，构成一个新的码组集合。而在传输时，两个零信息位不发送，即发送的是(13, 9)缩短循环码。,缩短循环码和原始循环码相比，缩短的是信息位，监督位并没减少，因此检错纠错能力不会减少。,第十一章 差错控制编码,11.6 循环码,11.6.4 BCH ( Bose-Chaudhuri-Hocguenghem)码,在系统设计中，通常是在给定纠正随机误码的个数条件下寻找码生成多项式g(x)，从而得到满足一定抗干扰性能要求的编码。BCH码就是为解决这一问题研究发展起来的一类纠正多个随机错误的循环码。, 本原BCH码 本原BCH码的码长为n=2m-1 (m是大于或等于3的整数)

30、 , 其生成多项式g(x)中含有最高次数为m次的本原多项式。, 非本原BCH码 本原BCH码的码长n为( 2m-1 ) 的一个因子，其生成多项式g(x)中不含有最高次数为m次的本原多项式。,可以证明： 对于正整数m (m3) 和t (t m/2) , 必存在 “ 码长n=2m-1，监督位数目r mt , 能够纠正不大于t 个的随机误码”的BCH码。,第十一章 差错控制编码,11.6 循环码,11.6.4 BCH ( Bose-Chaudhuri-Hocguenghem)码,第十一章 差错控制编码,11.6 循环码,11.6.4 BCH ( Bose-Chaudhuri-Hocguenghem)

31、码,第十一章 差错控制编码,11.7 卷积码 (连环码),前述的分组码在编码时，各长度为n的码组进行分别编码。即对于给定的k个信息位，附加上仅仅与这k个信息位有关的r个监督位，形成长度为n的码组。各个码组之间没有任何约束关系，因此在译码时各个码组也是分别独立地进行。,卷积码在编码时，长度为n的码组由k个信息位附加上r个监督位，形成长度为n的码组。但是这r个监督位不仅仅与当前的k个信息位有关，还和前面的(N-1)个码组中的信息位有关。这样若干个(N)码组形成一种约束关系。,卷积码的约束长度:以码组为单位时为N, 以码元为单位时为nN 。,码组长度为n , 信息位组长度为k , 约束长度为N个码组

32、的卷积码记为 (n , k , N)卷积码 , 卷积码的编码效率为Rc=k/n。,第十一章 差错控制编码,11.7 卷积码,11.7.1 卷积码的图形表示,第十一章 差错控制编码,11.7 卷积码,11.7.1 卷积码的图形表示,1. 树状图,第十一章 差错控制编码,11.7 卷积码,11.7.1 卷积码的图形表示,1. 树状图,第十一章 差错控制编码,11.7 卷积码,11.7.1 卷积码的图形表示,2. 网格图,图11-11 (3,1,3)卷积码的网格图,第十一章 差错控制编码,11.7 卷积码,11.7.1 卷积码的图形表示,3. 状态图,状态合并,第十一章 差错控制编码,11.7 卷积

33、码,11.7.1 卷积码的图形表示,例11-1 卷积码编码器(图11-8)的初始状态为a, 对于输入序列“11010111”, 求出输出序列和状态转移路径。,输出序列:,1 1 1,1 1 0,0 1 0,1 0 0,0 0 1,1 0 0,1 1 0,1 0 1,第十一章 差错控制编码,11.7 卷积码,11.7.2 卷积码的解析表示,1. 生成矩阵,卷积码是线性码, 可以由生成矩阵G和监督矩阵H来确定。,例图11-8 (3,1,3)卷积码编码器,第十一章 差错控制编码,11.7 卷积码,11.7.2 卷积码的解析表示,1. 生成矩阵,第十一章 差错控制编码,11.7 卷积码,11.7.2 卷积码的解析表示,1. 生成矩阵,分别写成矩阵形式为 y11y21 y31 = m1 0 0 T1 和 y12y22 y32 = m1