第八章-差错控制编码PPT学习教案

1、会计学1第八章第八章-差错控制编码差错控制编码1、检错检错重发法重发法ARQ (Automatic Repeat Request) ：四、差错控制方法四、差错控制方法2、前向、前向纠错纠错法法FEC (Forword ErrorCorrection)3、反馈校验法、反馈校验法发发收收有错码有错码无错码无错码双向信道双向信道发发收收是否有错是否有错双向信道双向信道效率低效率低发发收收自己纠正自己纠正单向信道单向信道设备复杂设备复杂 信信 源源 编码器编码器 缓冲器缓冲器重发控制重发控制 双双 向向 信信 道道 解码器解码器 指令产指令产生生 输出缓输出缓冲冲 收收 信信 者者正确时输出正确时输出

2、错误时删除错误时删除4、混合纠错法、混合纠错法HEC (Hybrid ErrorCorrection)图图1 自动请求自动请求ARQ方框图方框图第1页/共33页一、差错控制编码的基本概念：一、差错控制编码的基本概念：1、几个名词解释：、几个名词解释：码距：两个码字对应位上数字不同的个数；（汉明距离）码距：两个码字对应位上数字不同的个数；（汉明距离） 例如例如 11000 与与 10011之间的距离之间的距离d=3000、011、101、110（3，2） 011的码重为的码重为2， 000与与011的码距为的码距为2最小码距最小码距 ：码组集中各码距的最小值。：码组集中各码距的最小值。0d码字：

3、由若干个码元组成的序列。例：码字：由若干个码元组成的序列。例：1011001称为一个码字称为一个码字 。结论：线性分组码中，最小码距等于最小码重结论：线性分组码中，最小码距等于最小码重8.2 差错控制编码的基本原理差错控制编码的基本原理码组：由多个码字构成的集合。例：码组：由多个码字构成的集合。例：00,01,10,11。码重码重/汉明重量：码字中汉明重量：码字中“1”的个数；例：码字的个数；例：码字 10110，码重，码重w=3。2、 差错控制编码的基本原理差错控制编码的基本原理（1）举例：发短信、）举例：发短信、天气预报天气预报（3）基本原理基本原理：k位信息码位信息码+r位监督码位监督码

4、n位编码。位编码。（4）编码效率：）编码效率：k/n=1-r/n。 若若2个信息码元中加个信息码元中加1个监督码元，编码效率个监督码元，编码效率2/3。（2）基本思想：在发送信息时，加入某种关联性某种约束关系。）基本思想：在发送信息时，加入某种关联性某种约束关系。第2页/共33页8.2 差错控制编码的基本原理差错控制编码的基本原理举例：举例： 1、 2位码只能表示位码只能表示4种组合。种组合。00（晴）（晴）01（云）（云）10（阴）（阴）11（雨）（雨）2、 假如用假如用3位二进制数字来传送这位二进制数字来传送这4种信息种信息000（晴）（晴）011（云）（云）101（阴）（阴）110（雨）

5、（雨）接收端不能检错，也不能纠错。接收端不能检错，也不能纠错。那么，若任一组码组有一个或多个发生错码，那么，若任一组码组有一个或多个发生错码，变成另一信息码组。变成另一信息码组。接收端此时有可能发现一个或三个错码，接收端此时有可能发现一个或三个错码，但不能发现两个错码。但不能发现两个错码。返回返回第3页/共33页（3）、基本原理：）、基本原理：0 0（晴）（晴）0 1（云）（云）1 0（阴）（阴）1 1（雨）（雨）0 0 0（晴）（晴）0 1 1（云）（云）1 0 1（阴）（阴）1 1 0（雨）（雨）信息位信息位监督位监督位信息码加若干监督码的编码集合，用信息码加若干监督码的编码集合，用 表示

6、。表示。),(knkn ：信息码元的数目，：信息码元的数目， ：码组的总位数：码组的总位数knr表示监督码元的数目表示监督码元的数目其结构为：信息码其结构为：信息码+ +监督码监督码返回返回第4页/共33页二、最小码距二、最小码距d0与纠错能力的关系：与纠错能力的关系：8.2 差错控制编码的基本原理差错控制编码的基本原理1、重复码：、重复码：用来发送天气预报用来发送天气预报 举例：举例： 结论：纠错能力与码的位数有关。怎么样的关系呢？结论：纠错能力与码的位数有关。怎么样的关系呢？(1) 检测检测e个随机错误，则要求码的最小距离个随机错误，则要求码的最小距离d0e+1;(2) 纠正纠正t个随机错

7、误，个随机错误， 则要求码的最小距离则要求码的最小距离d02t+1;(3) 纠正纠正t个同时检测个同时检测e个随机错误，则要求码的最小距离个随机错误，则要求码的最小距离d0t+e+1， (et)。2、最小码距、最小码距d0与纠错能力的关系：与纠错能力的关系：三、差错控制编码的分类：三、差错控制编码的分类：从用途、监督关系、码字结构、信息处理等方面分类从用途、监督关系、码字结构、信息处理等方面分类第5页/共33页举例：举例： 1、 2位码只能表示位码只能表示4种组合。种组合。00（晴）（晴）01（云）（云）10（阴）（阴）11（雨）（雨）2、 假如用假如用3位二进制数字来传送这位二进制数字来传送

8、这4种信息种信息000（晴）（晴）011（云）（云）101（阴）（阴）110（雨）（雨）接收端不能检错，也不能纠错。接收端不能检错，也不能纠错。那么，若任一组码组有一个或多个发生错码，那么，若任一组码组有一个或多个发生错码，变成另一信息码组。变成另一信息码组。接收端此时有可能发现一个或三个错码，接收端此时有可能发现一个或三个错码，但不能发现两个错码。但不能发现两个错码。第6页/共33页 它只能检测错误，而不能纠正错误。它只能检测错误，而不能纠正错误。若要想能纠正错误，还要增加冗余度。若要想能纠正错误，还要增加冗余度。000、101、110011接收端接收端发送端发送端 错一个错一个错三个错三个

9、100肯定出错了肯定出错了（禁用码组）（禁用码组）000错两个错两个011、110、101正确正确不能肯定出错不能肯定出错（许用码组）（许用码组）第7页/共33页3、若用、若用3位码表示位码表示2种信息，种信息， 000（晴）（晴） 111（雨）（雨）接收端此时有可能发现一个错码并能纠正它，接收端此时有可能发现一个错码并能纠正它，或发现二个以下错码不能纠正，不能发现三个错误。或发现二个以下错码不能纠正，不能发现三个错误。000接收端接收端发送端发送端错一个错一个100肯定出错了，且能纠错肯定出错了，且能纠错（禁用码组）（禁用码组）A、若错一位，则能确定发端的码。、若错一位，则能确定发端的码。0

10、00错三个错三个111正确正确不能肯定出错不能肯定出错B、若错码不超过二位，、若错码不超过二位， 则则 不能确定发端的码。不能确定发端的码。000111接收端接收端发送端发送端错一个错一个错两个错两个100肯定出错了，不能纠错肯定出错了，不能纠错返回返回第8页/共33页8.3 常用的简单编码常用的简单编码1、奇偶监督码、奇偶监督码奇偶监督码可分为奇数监督码和偶数监督码，两者的原理相同。奇偶监督码可分为奇数监督码和偶数监督码，两者的原理相同。（1）偶数监督码：监督位只有一位，使得码组中）偶数监督码：监督位只有一位，使得码组中“1”的个数为偶数，即满足的个数为偶数，即满足0021aaann0a为监

11、督位为监督位它能检测奇数个错码，无纠错能力。它能检测奇数个错码，无纠错能力。例例 收端：收端：1001 1011，则可能发生了奇数个错码，则可能发生了奇数个错码0001 1011、1101 10110111 1011发端可能为发端可能为错一位错一位错三位错三位（2）奇数监督码：监督位也只有一位，使得码组中）奇数监督码：监督位也只有一位，使得码组中“1”的个数为奇数，即满足的个数为奇数，即满足1021aaann它也能检测奇数个错码，无纠错能力。它也能检测奇数个错码，无纠错能力。编码效率：编码效率：(n-1)/n应用：适用于一般随机错误的检测应用：适用于一般随机错误的检测第9页/共33页2、二维奇

12、偶监督码、二维奇偶监督码行监督行监督列监督列监督码组码组1）原理：）原理：2）举例：）举例：3）检错能力：）检错能力：4）编码效率：）编码效率：5）特点：适合检测突发误码。）特点：适合检测突发误码。3、恒比码、恒比码码组中码组中“1”（或（或“0”）的个数相同。也即它们的比保持恒定。）的个数相同。也即它们的比保持恒定。接收端计算码组中接收端计算码组中“1”的个数即可知道有无误码。的个数即可知道有无误码。优点：适合用来传输电传机或键盘设备产生的信息。优点：适合用来传输电传机或键盘设备产生的信息。举例：举例：5取取3恒比码我国电传机，恒比码我国电传机，7取取3恒比码国际电传电报恒比码国际电传电报第

13、10页/共33页2）举例：）举例：4行行7列信息组的水平垂直偶校验码为：列信息组的水平垂直偶校验码为：发往线路顺序：发往线路顺序： 01110010|00101011|01010110|10101010|10100101 第第1字符字符 第第2字符字符 第第3字符字符 第第4字符字符 偶校验字符偶校验字符 返回返回第11页/共33页4、正反码（能纠正一位错码）、正反码（能纠正一位错码）1）、编码规则：监督位数与信息位数相同。）、编码规则：监督位数与信息位数相同。“1”的个数决定监督码元是否与信息码元相同或相反。的个数决定监督码元是否与信息码元相同或相反。举例：举例：电报通信电报通信 （10 5

14、) 若有奇数个若有奇数个“1”，则监督码元与信息码元相同，则监督码元与信息码元相同若有偶数个若有偶数个“1”，则监督码元与信息码元相反，则监督码元与信息码元相反110011100110001011102）、解码原理：）、解码原理：A、信息位与监督位按位模、信息位与监督位按位模2加加合成码字合成码字校验码字校验码字B、合成码字合成码字校验码字的规则校验码字的规则若收到码字的信息位有奇数个若收到码字的信息位有奇数个“1”，合成码字就是校验码字，合成码字就是校验码字若收到码字的信息位有偶数个若收到码字的信息位有偶数个“1”，合成码字的反码是校验码字，合成码字的反码是校验码字3）、由校验码字来检错纠错

15、：）、由校验码字来检错纠错：全全“0”无错码无错码4个个“1”，1个个“0”一位错码，其位置为校验码中一位错码，其位置为校验码中“0”的位置的位置一位错码，其位置为监督码中一位错码，其位置为监督码中“1”的位置的位置4个个“0”，1个个“1”其他其他错码多于一位错码多于一位第12页/共33页8.4 线性分组码线性分组码一、什么是线性分组码？一、什么是线性分组码？（1）封闭性：任何两个许用码字之和，仍为一许用码字。）封闭性：任何两个许用码字之和，仍为一许用码字。2、两个重要性质、两个重要性质分组码分组码:先给信息码分组，然后给每组信息码附加若干监督码的编码。先给信息码分组，然后给每组信息码附加若

16、干监督码的编码。1、基本概念、基本概念代数码代数码:建立在代数学基础上的编码。建立在代数学基础上的编码。线性码线性码:信息位与监督位由线性代数方程组联系在一起。是代数码信息位与监督位由线性代数方程组联系在一起。是代数码线性分组码线性分组码:信息码分组后，定长信息码与监督码由线性代数方程组联系在一起而形成的编码。如汉明码、循环码等。信息码分组后，定长信息码与监督码由线性代数方程组联系在一起而形成的编码。如汉明码、循环码等。（2）最小码距最小码重（全）最小码距最小码重（全“0”码除外）码除外）3、编码效率、编码效率第13页/共33页二、线性分组码的编码原理二、线性分组码的编码原理2）若监督位增加一

17、位，有）若监督位增加一位，有2个监督关系式，校正因子有个监督关系式，校正因子有4种组合种组合若若1种代表无错，其余种代表无错，其余3种可以用来指示错码的种可以用来指示错码的3个不同位置。个不同位置。S的值只有两种，代表有错和无错两种信息（检错）的值只有两种，代表有错和无错两种信息（检错）但不能指出错码的位置但不能指出错码的位置。Saaann021（监督关系式、校正因子）（监督关系式、校正因子）1）奇偶监督码中，接收端计算：）奇偶监督码中，接收端计算：3）若有）若有r位监督位，可以指示错码位监督位，可以指示错码 个不同位置个不同位置12 r1、一般原理、一般原理结论：码长结论：码长 n,信息位信

18、息位 k,监督位为监督位为 r=n-k，若它能指示，若它能指示n个错码位置个错码位置则：则：nr1212rkr（或（或 ）第14页/共33页举例：（举例：（7 4）汉明码）汉明码 r=3 可以指示可以指示7个错码位置个错码位置1） （7 4）应该有）应该有3个校正因子，个校正因子，8种组合，种组合，7个错码位置个错码位置0123456aaaaaaa信息位信息位监督位监督位2）若）若321SSS错码位置错码位置0 1 01a1 0 02a0 1 13a0 0 10a1 1 05a1 0 14a1 1 16a24561aaaaS13562aaaaS36430Saaaa那么：那么：3）正确的监督关系

19、为：）正确的监督关系为：02456aaaa01356aaaa00346aaaa4562aaaa3561aaaa3460aaaa4）可得）可得16个许用码字个许用码字 P222 表表8-75）汉明码还可纠错）汉明码还可纠错 例例8-4-1第15页/共33页二、线性分组码的编码原理二、线性分组码的编码原理2、监督方程与监督矩阵、监督方程与监督矩阵HTTaaaaaaa00000010110011101010111010001234563、生成方程与生成矩阵、生成方程与生成矩阵G000101100101010100110100011134560123456aaaaaaaaaaaPI1011001110

20、10101110100rH监督矩阵监督矩阵H单位单位方阵方阵QI 0001011001010101001101000111kG生成矩阵生成矩阵GTPQ nk000101110123456aaaaaaa001010110123456aaaaaaa010011010123456aaaaaaa结论：典型阵结论：典型阵H的各行一定是线性无关的，非典型阵可以经线性变换后化成典型阵。根据的各行一定是线性无关的，非典型阵可以经线性变换后化成典型阵。根据AHT=0，用于接收端检、纠错，用于接收端检、纠错典型阵典型阵典型阵典型阵第16页/共33页二、线性分组码的编码原理二、线性分组码的编码原理4、监督矩阵、监督

21、矩阵H与生成矩阵与生成矩阵G的关系的关系TTrrkkHPIQ IGI QI P，结论：生成矩阵的每一行都是码字，利用结论：生成矩阵的每一行都是码字，利用生成矩阵生成矩阵G可以产生整个码组，即可以产生整个码组，即6543Aaaaa G第17页/共33页三、线性分组码的译码原理三、线性分组码的译码原理2、校正子、校正子S1、错误图样、错误图样E120120nnnnAaaaBbbb若发：，收：120000nnEBABAEEeeeE则：或错误图样无错，否则有错()000TTTTTSBHAE HAHEHEHS校正子若无错，否则有错3、结论、结论 接收码元中只错一位时，计算出的校正子接收码元中只错一位时，

22、计算出的校正子S总是和典型阵总是和典型阵H的某一列相同，可判断错误发生在哪个码元。（纠单个错）的某一列相同，可判断错误发生在哪个码元。（纠单个错）例例8-4-2 P225第18页/共33页8.5 循环码循环码1、定义：、定义：是常用的线性分组码，其检、纠错能力强，编译码设备不复杂的码。有严密的代数理论基础，以生成多项式作为收发双方的约束关系。由于码组内任一码字经循环移位后仍为该码组中的一个码字，所以称为循环码。是常用的线性分组码，其检、纠错能力强，编译码设备不复杂的码。有严密的代数理论基础，以生成多项式作为收发双方的约束关系。由于码组内任一码字经循环移位后仍为该码组中的一个码字，所以称为循环码

23、。1）封闭性）封闭性0123456aaaaaaa6012345aaaaaaa5601234aaaaaaa3、码字多项式、码字多项式0112233445566)(axaxaxaxaxaxaxT0123456aaaaaaa来表示来表示码字与码字多项式有一一对应关系码字与码字多项式有一一对应关系表示方法：表示方法：一、一、 循环码的基本概念循环码的基本概念2、特点：、特点：3）循环性：任一许用码组经循环移位后仍为一许用码组。）循环性：任一许用码组经循环移位后仍为一许用码组。2）最小码距等于最小码重（全）最小码距等于最小码重（全“0”码除外）码除外）举例：举例：循环性：若循环性：若T(x)是长为是长为

24、n的许用码字多项式，则的许用码字多项式，则)(xTxi按模按模1nx运算后，也是许用码字多项式运算后，也是许用码字多项式第19页/共33页4、生成多项式、生成多项式)(xg 是一个能整除是一个能整除xn+1且常数项为且常数项为1的的r（r=n-k)次多项式，是次多项式，是(n,k)循环码集合中（除全循环码集合中（除全“0”码外）幂次最低的多项式，它有唯一性，由生成多项式可以产生循环码的全部码字。码外）幂次最低的多项式，它有唯一性，由生成多项式可以产生循环码的全部码字。5、生成矩阵多项式、生成矩阵多项式G(x)、生成矩阵、生成矩阵G)()()()()(21xgxxgxgxxgxxGkk由生成矩阵

25、可以得到所有的循环码字由生成矩阵可以得到所有的循环码字(n,k)循环码中前（循环码中前（k-1)位都是位都是0，那么，那么 )(xxg)(xg)(2xgx)(1xgxk都是码字多项式，且线性无关。把这些多项式写成矩阵的形式，即都是码字多项式，且线性无关。把这些多项式写成矩阵的形式，即把系数写成矩阵形式把系数写成矩阵形式生成矩阵生成矩阵G(若非典型阵若非典型阵)典型阵典型阵G线性变换线性变换第20页/共33页二、循环码的编码二、循环码的编码1）用）用 乘乘 。相当于在信息码元后面加。相当于在信息码元后面加 个个0；knx)(xmkn2）用）用 除除 ，得到商，得到商Q（x)和余式和余式r(x)(

26、xmxkn )(xg3）编出的码组为）编出的码组为)()()(xrxmxxTkn110110000010111101111101111100000)(xr)(xg1100000+101=11001011、编码步骤、编码步骤并发送并发送4）举例：已知（）举例：已知（7，3）循环码，）循环码，m(x)=x2+x，g(x)=x4+x2+x+1，求经，求经CRC编码后的发送码字编码后的发送码字2、编码电路的实现、编码电路的实现软件有延时，但成本低软件有延时，但成本低硬件实时性强，但有设备成本硬件实时性强，但有设备成本第21页/共33页编码电路编码电路1)(24xxxxg第22页/共33页三、循环码的译

27、码三、循环码的译码收到码多项式收到码多项式R(x)，用，用g(x)做除法，做除法，( )( )( )( )( )R xr xQ xg xg x若若r(x) 0，则无错，否则有错。，则无错，否则有错。( )( )( )R xE xTxTTSRHEHETRE1、译码原理、译码原理举例：举例：P228 例例8-5-22、译码电路的实现、译码电路的实现软件有延时，但成本低软件有延时，但成本低硬件实时性强，但有设备成本硬件实时性强，但有设备成本由由r(x) 找错误图样，最后纠错。即：找错误图样，最后纠错。即：第23页/共33页四、循环码的检查能力四、循环码的检查能力（1）可检测出所有奇数位错；）可检测出

28、所有奇数位错；（2）可检测出所有双比特错；）可检测出所有双比特错；（3）可检测出所有小于、等于校验位长度的突发错。）可检测出所有小于、等于校验位长度的突发错。结论：是一种检纠错能力和编码效率达到最佳折中的编码。在数据通信和计算机网络中得到了广泛应用。结论：是一种检纠错能力和编码效率达到最佳折中的编码。在数据通信和计算机网络中得到了广泛应用。五、几种常用的五、几种常用的CRC校验码生成多项式：校验码生成多项式：44( )1CRCg xxx：1615216( )1CRCg xxxx：1615516( )1CCITTg xxxx：32262322161211108754232( )1CRCg xxx

29、xxxxxxxxxxxx：第24页/共33页8.6 其它差错控制编码简介其它差错控制编码简介8.6.1 BCH码码1、何为、何为BCH码？码？ BCH码是由博斯（码是由博斯（Bose）、查德胡里（）、查德胡里（Chaudhuri）和霍昆格姆（）和霍昆格姆（Hocquenghem）名字的开头字母命名的，有严密的代数理论，纠多个随机错的）名字的开头字母命名的，有严密的代数理论，纠多个随机错的CRCCRC码。根据所要求的纠错能力码。根据所要求的纠错能力t，可求生成多项式，可求生成多项式g(x)，很容易构造出很容易构造出BCH码，译码也易实现。码，译码也易实现。2、BCH码分类码分类本原本原BCH码码

30、：码长为码长为 ，m为正整数；它的生成多项式由若干为正整数；它的生成多项式由若干m阶或以阶或以m阶的因子为最高阶的多项式相乘而构成。阶的因子为最高阶的多项式相乘而构成。 非本原非本原BCH码：码长是码：码长是 的一个因子；它的生成多项式中不含有最高次数为的一个因子；它的生成多项式中不含有最高次数为m的本原多项式。的本原多项式。 21mn 21m第25页/共33页8.6.2 卷积码卷积码1、问题的提出：、问题的提出： 分组码是把分组码是把k个信息比特的序列编成个信息比特的序列编成n个比特的码字，每个码字的个比特的码字，每个码字的n-kn-k个校验位仅与本码组的个校验位仅与本码组的k个信息位有关，而与其他码字无关。为了达到一定的纠错能力和编码效率，分组码的码字长度一般都比较大。个信息位有关，而与其他码字无关。为了达到一定的纠错能力和编码效率，分组码的码字长度一般都比较大。 是否有既要求是否有既要求n、k较小，又要求纠错能力较强的编码呢？较小，又要求纠错能力较强的编码呢？ 答案是肯定的，那就是我们要介绍的卷积码。答案是肯定的，那就是我们要介绍的卷积码。 2、特点