第7章错控制原理

1、第7章 差错控制原理石高涛石高涛天津大学计算机科学与技术学院天津大学计算机科学与技术学院2差错产生的原因差错产生的原因 信号在传输过程中会收信号在传输过程中会收到例如脉冲干扰、随机到例如脉冲干扰、随机噪声干扰等使信号波形噪声干扰等使信号波形失真，从而使接收解调失真，从而使接收解调后的信号产生差错。后的信号产生差错。 误比特率是指二进制比误比特率是指二进制比特在数据传输系统中被特在数据传输系统中被传错的概率，它在数值传错的概率，它在数值上近似等于：上近似等于： pe = ne/n 其中，其中，n为传输的二进为传输的二进制比特总数，制比特总数，ne为被传为被传错的比特数错的比特数 信源信源通信信道

2、通信信道信宿信宿数据数据噪声噪声数据数据+噪声噪声3差错产生的原因差错产生的原因 两类噪声：两类噪声：随机噪声：时时处处随机噪声：时时处处存在、幅度小、频带存在、幅度小、频带宽，导致产生的噪声宽，导致产生的噪声随机、离散，前后差随机、离散，前后差错之间无关联。错之间无关联。脉冲噪声：强度大、脉冲噪声：强度大、持续时间与数据传输持续时间与数据传输中每比特的时间相比中每比特的时间相比较长，因而造成错误较长，因而造成错误成串出现。成串出现。信源信源通信信道通信信道信宿信宿数据数据噪声噪声数据数据+噪声噪声4主要内容主要内容 差错控制基本原理差错控制基本原理 汉明距与检错纠错汉明距与检错纠错 差错控制

3、编码差错控制编码 差错控制方法差错控制方法5主要内容主要内容 差错控制基本原理差错控制基本原理 汉明距与检错纠错汉明距与检错纠错 差错控制编码差错控制编码 差错控制方法差错控制方法6信源编码与信道编码信源编码与信道编码 在数字通信系统中，为了提高数字信号传输的有在数字通信系统中，为了提高数字信号传输的有效性而采取的编码称为效性而采取的编码称为信源编码信源编码；为了提高数字；为了提高数字通信的可靠性而采取的编码称为通信的可靠性而采取的编码称为信道编码信道编码。 信源编码信源编码：模拟信号如果想利用数字通信系统进行传输，模拟信号如果想利用数字通信系统进行传输，就需要将模拟信息源的输出转化为数字信号

4、，而这个转化就需要将模拟信息源的输出转化为数字信号，而这个转化构成就称为信源编码。脉冲编码调制构成就称为信源编码。脉冲编码调制(pcm)、差分脉冲编、差分脉冲编码调制码调制(dpcm) 、增量调制、增量调制(dm). 信道编码信道编码：又称差错控制编码，是在信息序列上附加上又称差错控制编码，是在信息序列上附加上一些一些监督码元，利用这些冗余的码元监督码元，利用这些冗余的码元，使原来不规律的或，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；差错规律性不强的原始数字信号变为有规律的数字信号；差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，控制译码则利用这些规律性来鉴别传输过

5、程是否发生错误，或进而纠正错误。或进而纠正错误。 7差错控制基本原理差错控制基本原理 原始数字信号是分组传输的，例如每原始数字信号是分组传输的，例如每k个二个二进制码元为一组（称为信息组），进制码元为一组（称为信息组）， 经信道编码后转换为每经信道编码后转换为每n个码元一组的码字个码元一组的码字(码组码组)，这里，这里nk，分组码分组码通常表示为通常表示为(n，k)，其中，其中n=k+r, r是码组中监督码位的长是码组中监督码位的长度度,n是编码码组的总长度。是编码码组的总长度。 信道编码是用增加数码，利用信道编码是用增加数码，利用“冗余冗余”来来提高抗干扰能力的，也就是以降低信息传提高抗干扰

6、能力的，也就是以降低信息传输速率为代价来减少错误的，或者说是用输速率为代价来减少错误的，或者说是用削弱有效性来增强可靠性的。削弱有效性来增强可靠性的。 8增加冗余码的原因增加冗余码的原因 原始数据码本身随机变化，无任何规律，通过增原始数据码本身随机变化，无任何规律，通过增加冗余信息使其呈现某种规律性，从而可以在接加冗余信息使其呈现某种规律性，从而可以在接收端进行错误检测。收端进行错误检测。 考察考察3位二进制码，其中的八个组合可表示八种不位二进制码，其中的八个组合可表示八种不同信息，如果只传输这三位，则任意一个组合出同信息，如果只传输这三位，则任意一个组合出错都回变成另一组码，接受端无法发现错

7、误。错都回变成另一组码，接受端无法发现错误。许用码许用码000011101110禁用码禁用码001010100111 其中任一个码其中任一个码一位一位出错，都会出错，都会变成禁用码。从而接收端变成禁用码。从而接收端能够能够且只能够且只能够检测出错误。检测出错误。 相当于用相当于用3位二进制表示位二进制表示4个信个信息，从而存在一位冗余。息，从而存在一位冗余。 9增加冗余码的原因增加冗余码的原因 为了能纠正错误，还需要增加冗余码元。如下表为了能纠正错误，还需要增加冗余码元。如下表所示，若所示，若许用码只有许用码只有000,111，其余均为禁用码组，其余均为禁用码组。 这相当于使用三位二进制码来代

8、表两种不同的信这相当于使用三位二进制码来代表两种不同的信息，有两位码是冗余的。息，有两位码是冗余的。 接收端可检测出接收端可检测出2位以下的错误或者纠正位以下的错误或者纠正1位错误位错误许用码许用码000111禁用码禁用码001010011100101111 当收到禁用码组时当收到禁用码组时100时，可以认为时，可以认为只有一位出错，则原始信息为只有一位出错，则原始信息为000，因为因为111任何一位出错都不会变成任何一位出错都不会变成100，此时即此时即检错检错1位又能纠错位又能纠错1位位。 若认为错码不超过若认为错码不超过2位，则存在两种位，则存在两种可能：可能：000错错1位或者位或者1

9、11错错2位。位。10检错码和纠错码检错码和纠错码 按照信道编码的不同功能，可以将它分为按照信道编码的不同功能，可以将它分为检错码和纠错码检错码和纠错码。 检错码仅能检测误码，例如，在计算机串检错码仅能检测误码，例如，在计算机串口通信中常用到的奇偶校验码等；口通信中常用到的奇偶校验码等； 纠错码可以纠正误码，当然同时具有检错纠错码可以纠正误码，当然同时具有检错的能力，当发现不可纠正的错误时可以发的能力，当发现不可纠正的错误时可以发出出错指示。出出错指示。 11主要内容主要内容 差错控制基本原理差错控制基本原理 汉明距与检错纠错汉明距与检错纠错 差错控制编码差错控制编码 差错控制方法差错控制方法

10、12汉明距离汉明距离 汉明距离又称码距，它是指两个等长二进汉明距离又称码距，它是指两个等长二进制码组之间制码组之间对应位不同的个数对应位不同的个数，用来描述，用来描述码组之间的不同程度。码组之间的不同程度。1()njikiidaa 其中其中aji,aki分别为第分别为第j个码组和第个码组和第k个码组的个码组的第第i为码元为码元;n为码组长度为码组长度 一个码组集合中，任何两个码组间的汉明一个码组集合中，任何两个码组间的汉明距离的最小值称为距离的最小值称为最小码距最小码距。 最小码距越大，差错控制能力越强。最小码距越大，差错控制能力越强。13汉明距离汉明距离 汉明距离又称码距，它是指两个等长二进

11、汉明距离又称码距，它是指两个等长二进制码组之间制码组之间对应位不同的个数对应位不同的个数，用来描述，用来描述码组之间的不同程度。码组之间的不同程度。1()njikiidaa许用码许用码000011101110许用码许用码000111 最小码距为最小码距为2，接收端，接收端能能够够检测出检测出1位错误位错误。 最小码距为最小码距为3，接收端，接收端能够能够检测出检测出2位错误位错误。14汉明距和检错纠错的关系汉明距和检错纠错的关系 当码字用于当码字用于检测错误检测错误时，如果要检测时，如果要检测e个错个错误，则分组码最小汉明距离误，则分组码最小汉明距离d0和和e之间的关之间的关系：系： 在图中用

12、在图中用a和和b分别表示两个码距为分别表示两个码距为d0的码的码字，若字，若a发生发生e个错误，则个错误，则a就变成以就变成以a为球为球心，心，e为半径的球面上的码字，为了能将这为半径的球面上的码字，为了能将这些码字分辩出来，它们必须距离其最近的些码字分辩出来，它们必须距离其最近的码字码字b至少有一位的差别至少有一位的差别01deabed015汉明距和检错纠错的关系汉明距和检错纠错的关系 当码字用于当码字用于纠正错误纠正错误时，如果要纠正时，如果要纠正t个错误，则个错误，则 在图中用在图中用a和和b分别表示两个码距为分别表示两个码距为d0的码字，若的码字，若a发生发生t个错误，则个错误，则a就

13、变成以就变成以a为球心，为球心，t为半径为半径的球面上的码字；的球面上的码字；b发生发生t个错误，则个错误，则b就变成以就变成以b为球心，为球心，t为半径的球面上的码字。为了在出现为半径的球面上的码字。为了在出现t个错误之后，仍能够分辩出个错误之后，仍能够分辩出a和和b来，那么，来，那么，a和和b之间距离应大于之间距离应大于2t，最小距离也应当使两球体表，最小距离也应当使两球体表面相距为面相距为1。021dtabtd0t116主要内容主要内容 差错控制基本原理差错控制基本原理 汉明距与检错纠错汉明距与检错纠错 差错控制编码差错控制编码 差错控制方法差错控制方法17差错控制编码差错控制编码 奇偶

14、校验码奇偶校验码：奇偶校验码是奇校验码和偶校：奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码。它是验码的统称，是一种最基本的检错码。它是由由n-1位信息元和位信息元和1位校验元组成，可以表示位校验元组成，可以表示成为（成为（n，n-1）。）。 如果是奇校验码，在附加上一个监督元以后，如果是奇校验码，在附加上一个监督元以后，码长为码长为n的码字中的码字中“1”的个数为奇数个；的个数为奇数个； 如果是偶校验码，在附加上一个监督元以后，如果是偶校验码，在附加上一个监督元以后，码长为码长为n的码字中的码字中“1”的个数为偶数个。的个数为偶数个。1230.1nnnaaaa1230.0nnna

15、aaa18 奇偶校验码是最常见的检错码方式，它可奇偶校验码是最常见的检错码方式，它可以构成垂直奇偶校验、水平奇偶校验和垂以构成垂直奇偶校验、水平奇偶校验和垂直水平奇偶校验。直水平奇偶校验。 垂直奇偶校验：垂直奇偶校验：也称为字符奇偶校验。对也称为字符奇偶校验。对于单元字符代码，在字符代码最后一位加于单元字符代码，在字符代码最后一位加上一个奇偶校验位上一个奇偶校验位b7，使码组中的，使码组中的1的个数的个数为奇数或者偶数。为奇数或者偶数。 接收端可以通过校验接收字符码组中的接收端可以通过校验接收字符码组中的1的的个数为偶数个数为偶数(或奇数或奇数)来判断传输是否有差错。来判断传输是否有差错。差错

16、控制编码差错控制编码19垂直水平奇偶校验垂直水平奇偶校验 又叫二维奇偶校验或方阵校验。它不仅对水平又叫二维奇偶校验或方阵校验。它不仅对水平（行）方向的码元，而且还对垂直（列）方向的（行）方向的码元，而且还对垂直（列）方向的码元实施奇偶监督。码元实施奇偶监督。 将信息码组排列成矩阵，每一个码组写成一行，将信息码组排列成矩阵，每一个码组写成一行，然后根据奇偶校验原理在垂直和水平两个方向进然后根据奇偶校验原理在垂直和水平两个方向进行校验。行校验。 发送时需要将校验位和校验码发送到接收端。发送时需要将校验位和校验码发送到接收端。1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0

17、10 1 1 1 1 0 0 0 0 11 0 0 1 1 1 0 0 0 01 0 1 0 1 0 1 0 1 0001011 1 0 0 0 1 1 1 1 0020恒比码恒比码 恒比码中的恒比码中的1和和0的个数保持恒定比例。的个数保持恒定比例。数字码字01234567890 1 1 0 10 1 0 1 11 1 0 0 11 0 1 1 01 1 0 1 00 0 1 1 11 0 1 0 11 1 1 0 00 1 1 1 01 0 0 1 1 若码长为若码长为n，码重为，码重为w，则此码的，则此码的码字个数为码字个数为 ，禁用码字数，禁用码字数为为 。 该码的检错能力较强，除对换

18、差该码的检错能力较强，除对换差错（错（1和和0成对的产生错误）不能成对的产生错误）不能发现外，其它各种错误均能发现。发现外，其它各种错误均能发现。 国际上通用的电报通信系统中，国际上通用的电报通信系统中，采用采用7中取中取3码，实践证明，应用码，实践证明，应用这种码，使国际电报通信的误码这种码，使国际电报通信的误码率保持在以率保持在以 10-6 下。下。 35cwnc2nwnc21正反码正反码 校验码取决于信息码中校验码取决于信息码中1的数目，或者与信息码元的数目，或者与信息码元相同相同(正码正码)，或者与信息码元相反，或者与信息码元相反(反码反码)。 博多码：当信息码组中有奇数个博多码：当信

19、息码组中有奇数个1时，校验码与信时，校验码与信息码相同，当信息码中有欧数个息码相同，当信息码中有欧数个1时，校验码是信时，校验码是信息码的反码。如：息码的反码。如：11001校验码为校验码为11001，而，而11101校验码为校验码为00010。 接收端将接收的码组中的信息码与校验码模接收端将接收的码组中的信息码与校验码模2加，加，得到一个得到一个5单位合成码组作为校验码。如果信息码单位合成码组作为校验码。如果信息码奇数个奇数个1，合成码就是校验码；如果信息码是欧数，合成码就是校验码；如果信息码是欧数个，则合成码的反码为校验码。个，则合成码的反码为校验码。 对根据校验码中对根据校验码中1的个数

20、依据下表进行判决：的个数依据下表进行判决：22正反码译码判决表正反码译码判决表类型类型校验码组形式校验码组形式译码判决译码判决1全全0传输正确传输正确24个个1，1个个0校验码中校验码中0对应位置的对应位置的1位信息码出错位信息码出错34个个0，1个个1校验码中校验码中1对应的对应的1位监督码出错位监督码出错4其他其他大于大于1位的传输错误位的传输错误 信息码信息码 校验码校验码 信息码有奇数个信息码有奇数个1判决校验码判决校验码判决校验码判决校验码信息码有欧数个信息码有欧数个1取反取反01101 0110101010 101110000011101000000001023循环冗余校验编码循环

21、冗余校验编码 又称又称crc码，纠错能力强，采用多项式编码，纠错能力强，采用多项式编码的方法。目前广泛应用的一种纠错编码。码的方法。目前广泛应用的一种纠错编码。 二进制可使用多项式来表示：如二进制可使用多项式来表示：如10111可表可表示为：示为：x4+x2+x+1,多项式的系数就代表二进多项式的系数就代表二进制制10111. 对长度为对长度为n的二进制序列，存在一个以的二进制序列，存在一个以x为为基的基的n-1次多项式。次多项式。00000101001x100101111x2x2+1x2+x+124 在发送端，将要发送的数据比特序在发送端，将要发送的数据比特序列作为一个多项式列作为一个多项式

22、t(x)的系数，并的系数，并选定一个选定一个k次幂的生成多项式次幂的生成多项式g(x)。对于二进制乘法对于二进制乘法,该步意味着数据该步意味着数据比特序列左移比特序列左移k位位.crc基本原理基本原理 crc生成多项式生成多项式g(x)标准：使用时从中选择：标准：使用时从中选择：crc-12 g(x)=x12+x11+x3+x2+1crc-16 g(x)=x16+x15+x2+1t(x)t(x) xk k位位t(x) xk r(x)g(x) 将将t(x)xk除以生成多项式除以生成多项式g(x) 其中其中q(x)为商，为商，r(x)为余数。为余数。 将将t(x)xk+r(x)所对应的比特序列作为

23、一个整体发送所对应的比特序列作为一个整体发送。( )( )( )( )( )kt x xr xq xg xg x25校验过程校验过程 (接收端接收端) 在接收端，对接收序列所对应的多项式在接收端，对接收序列所对应的多项式t(x)xk进进行与发送端同样的运算，即：行与发送端同样的运算，即： 比较比较r(x)和和r(x)，如果，如果r(x)=r(x)，认为传输正，认为传输正确，否则认为传输错误。确，否则认为传输错误。( )( )( )( )( )kt x xr xq xg xg xt(x) xk r(x)( )()(ktr xq xg xxxgx?26crc例子例子 假设发送数据为假设发送数据为1

24、10011;生成多项式为生成多项式为 x4+x3+1，k=4，所对应的序列为，所对应的序列为11001； 将发送数据序列左移将发送数据序列左移4位，新的序列为：位，新的序列为：1100110000; 按模按模2算法算法，将生成的新序列用多项式序列去除，将生成的新序列用多项式序列去除，10000111001 11001100001100110000110011001q(x)t(x)xkr(x)发送新序列为：发送新序列为：110011 1001如果没有发送失败那么接收端收到的如果没有发送失败那么接收端收到的比特序列一定能被同一个多项式整除。比特序列一定能被同一个多项式整除。100001110011

25、110000111100111100127crc的性能的性能 crc生成的多项式结构与检错效果已经过生成的多项式结构与检错效果已经过严格的数学分析。严格的数学分析。 能检错出全部单个错误、能检测出全部随能检错出全部单个错误、能检测出全部随机的机的2位错误位错误 能检测出全部奇数个错误。能检测出全部奇数个错误。 能检测出全部长度小于等于能检测出全部长度小于等于k位的突发错误位的突发错误 能以能以1-(1/2)k-1的概率检测出长度为的概率检测出长度为k+1位突位突发错误。发错误。28 发送方将数据单元分成发送方将数据单元分成k段，每段段，每段n比特；比特；将各段相加求和；将各段相加求和；对和取反

26、得到校验和对和取反得到校验和；将校验和字段附加到数据序列末尾与数据将校验和字段附加到数据序列末尾与数据一起发送。一起发送。校验和编码校验和编码 接收端将接收到的数据单元分成长度为接收端将接收到的数据单元分成长度为n比比特的段；将所有分段相加求和；对和求反；特的段；将所有分段相加求和；对和求反；如果结果为如果结果为0，表示传输正确。，表示传输正确。n n n n n n n n 取反取反0 ？29校验和例子校验和例子 例：假定要发送例：假定要发送16位数据位数据1010100100111001,采用采用8位校验和，则发送比特为：位校验和，则发送比特为： 10101001 00111001 000

27、111011010100100111001+1110001000011101取反取反发送端发送端1010100100111001+0001110100000000取反取反接收端接收端11111111 能检测所有奇数个错误及大多数偶数个错误，但能检测所有奇数个错误及大多数偶数个错误，但如果某一段中的一个或多个比特损坏，下一个分如果某一段中的一个或多个比特损坏，下一个分段中具有相反值的对应位也被破坏，这些列的和段中具有相反值的对应位也被破坏，这些列的和保持不变，从而无法检测出错。保持不变，从而无法检测出错。0010100110111001+0001110100000000取反取反11111111出

28、错情况出错情况0010100100111001+0001110110000000取反取反0111111130主要内容主要内容 差错控制基本原理差错控制基本原理 汉明距与检错纠错汉明距与检错纠错 差错控制编码差错控制编码 差错控制方法差错控制方法31差错控制方法差错控制方法 发送端对信源数据进行发送端对信源数据进行纠错编码纠错编码，然后送信道传，然后送信道传输。输。 接收端对信号译码，如果检测传输中的错误则自接收端对信号译码，如果检测传输中的错误则自动纠正。动纠正。 优点：不需要反向信道，能用于单工通信，也可优点：不需要反向信道，能用于单工通信，也可用于一点对多点通信。用于一点对多点通信。 缺点

29、：译码设备复杂，为纠正错误需要附加较多缺点：译码设备复杂，为纠正错误需要附加较多的冗余码元，传输效率低。的冗余码元，传输效率低。 向前纠错向前纠错fec：又称自动纠错，其数学模型如下图：又称自动纠错，其数学模型如下图：信源信源fec编码编码信道信道fec译码译码信宿信宿32差错控制方法差错控制方法 自动请求重发自动请求重发(arq):用于检错编码，接收用于检错编码，接收端通过译码能够发现传输错误，但是无法端通过译码能够发现传输错误，但是无法纠正，因此采用自动请求重发的工作方式。纠正，因此采用自动请求重发的工作方式。 发送端在将数据发向信道的同时还进行缓存，以备发送端在将数据发向信道的同时还进行缓存，以备重发使用。如果接到重发请求，则将该数据放入缓重发使用。如果接到重发请求，则将该数据放入缓存器重新编码发送。存器重新编码发送。 接收端通过判决器检测，如果正确接收则发送接收端通过判决器检测，如果正确接收则发送ack；在检测到错误时发送；在检测到错误时发送nack，要求重发。，要求重发。信源信源编码器编码器正向信道正向