《差错控制原ppt课件》由会员分享，可在线阅读，更多相关《差错控制原ppt课件（36页珍藏版）》请在金锄头文库上搜索。
1、第7章过失控制原理石高涛石高涛shgttju.edu天津大学计算机科学与技术学院天津大学计算机科学与技术学院过失产生的缘由过失产生的缘由信号在信号在传输过程中会收程中会收到例如脉冲干到例如脉冲干扰、随机、随机噪声干噪声干扰等使信号波形等使信号波形失真，从而使接失真，从而使接纳解解调后的信号后的信号产生生过失。失。误比特率是指二比特率是指二进制比制比特在数据特在数据传输系系统中被中被传错的概率，它在数的概率，它在数值上近似等于：上近似等于：Pe=Ne/N其中，其中，N为传输的二的二进制比特制比特总数，数，Ne为被被传错的比特数的比特数信源信源通讯信道通讯信道信宿信宿数据数据噪声噪声数据数据+噪声
2、噪声过失产生的缘由过失产生的缘由两类噪声：两类噪声：随机噪声：时时处随机噪声：时时处处存在、幅度小、处存在、幅度小、频带宽，导致产生频带宽，导致产生的噪声随机、离散，的噪声随机、离散，前后过失之间无关前后过失之间无关联。联。脉冲噪声：强度大、脉冲噪声：强度大、继续时间与数据传继续时间与数据传输中每比特的时间输中每比特的时间相比较长，因此呵相比较长，因此呵斥错误成串出现。斥错误成串出现。信源信源通讯信道通讯信道信宿信宿数据数据噪声噪声数据数据+噪声噪声主要内容主要内容过失控制根本原理过失控制根本原理汉明距与检错纠错汉明距与检错纠错过失控制编码过失控制编码过失控制方法过失控制方法主要内容主要内容过
3、失控制根本原理过失控制根本原理汉明距与检错纠错汉明距与检错纠错过失控制编码过失控制编码过失控制方法过失控制方法信源编码与信道编码信源编码与信道编码在数字通讯系统中，为了提高数字信号传输的有在数字通讯系统中，为了提高数字信号传输的有效性而采取的编码称为信源编码；为了提高数字效性而采取的编码称为信源编码；为了提高数字通讯的可靠性而采取的编码称为信道编码。通讯的可靠性而采取的编码称为信道编码。信源编码：模拟信号假设想利用数字通讯系统进信源编码：模拟信号假设想利用数字通讯系统进展传输，就需求将模拟信息源的输出转化为数字展传输，就需求将模拟信息源的输出转化为数字信号，而这个转化构成就称为信源编码。脉冲编
4、信号，而这个转化构成就称为信源编码。脉冲编码调制码调制(PCM)、差分脉冲编码调制、差分脉冲编码调制(DPCM)、增量调、增量调制制(DM).信道编码：又称过失控制编码，是在信息序列上信道编码：又称过失控制编码，是在信息序列上附加上一些监视码元，利用这些冗余的码元，使附加上一些监视码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；过失控制译码那么利用这些有规律的数字信号；过失控制译码那么利用这些规律性来鉴别传输过程能否发生错误，或进而纠规律性来鉴别传输过程能否发生错误，或进而纠正错误。正错误。过失控制根本原理过失控
5、制根本原理原始数字信号是分原始数字信号是分组传输的，例如每的，例如每k个二个二进制制码元元为一一组称称为信息信息组，经信道信道编码后后转换为每每n个个码元一元一组的的码字字(码组)，这里里nk，分，分组码通常表示通常表示为(n，k)，其中，其中n=k+r,r是是码组中中监视码位的位的长度度,n是是编码码组的的总长度。度。信道信道编码是用添加数是用添加数码，利用，利用“冗余来提冗余来提高抗干高抗干扰才干的，也就是以降低信息才干的，也就是以降低信息传输速率速率为代价来减少代价来减少错误的，或者的，或者说是用减是用减弱有效性来加弱有效性来加强可靠性的。可靠性的。添加冗余码的缘由添加冗余码的缘由原始数
6、据码本身随机变化，无任何规律，经过添原始数据码本身随机变化，无任何规律，经过添加冗余信息使其呈现某种规律性，从而可以在接加冗余信息使其呈现某种规律性，从而可以在接纳端进展错误检测。纳端进展错误检测。调查调查3位二进制码，其中的八个组合可表示八种不位二进制码，其中的八个组合可表示八种不同信息，假设只传输这三位，那么恣意一个组合同信息，假设只传输这三位，那么恣意一个组合出错都回变成另一组码，接受端无法发现错误。出错都回变成另一组码，接受端无法发现错误。许用码许用码000011101110禁用码禁用码001010100111其中任一个码一位出错，都会其中任一个码一位出错，都会变成禁用码。从而接纳端可
7、以变成禁用码。从而接纳端可以且只可以检测出错误。且只可以检测出错误。相当于用相当于用3位二进制表示位二进制表示4个信个信息，从而存在一位冗余。息，从而存在一位冗余。添加冗余码的缘由添加冗余码的缘由为了能纠正错误，还需求添加冗余码元。如下表为了能纠正错误，还需求添加冗余码元。如下表所示，假设许用码只需所示，假设许用码只需000,111，其他均为禁用码，其他均为禁用码组。组。这相当于运用三位二进制码来代表两种不同的信这相当于运用三位二进制码来代表两种不同的信息，有两位码是冗余的。息，有两位码是冗余的。接纳端可检测出接纳端可检测出2位以下的错误或者纠正位以下的错误或者纠正1位错误位错误许用码许用码0
8、00111禁用码禁用码001010011100101111当收到禁用码组时当收到禁用码组时100时，可以以为时，可以以为只需一位出错，那么原始信息为只需一位出错，那么原始信息为000，由于，由于111任何一位出错都不会变成任何一位出错都不会变成100，此时即检错，此时即检错1位又能纠错位又能纠错1位。位。假设以为错码不超越假设以为错码不超越2位，那么存在位，那么存在两种能够：两种能够：000错错1位或者位或者111错错2位。位。检错码和纠错码检错码和纠错码按照信道编码的不同功能，可以将它分为按照信道编码的不同功能，可以将它分为检错码和纠错码。检错码和纠错码。检错码仅能检测误码，例如，在计算机串
9、检错码仅能检测误码，例如，在计算机串口通讯中常用到的奇偶校验码等；口通讯中常用到的奇偶校验码等；纠错码可以纠正误码，当然同时具有检错纠错码可以纠正误码，当然同时具有检错的才干，当发现不可纠正的错误时可以发的才干，当发现不可纠正的错误时可以发出出错指示。出出错指示。主要内容主要内容过失控制根本原理过失控制根本原理汉明距与检错纠错汉明距与检错纠错过失控制编码过失控制编码过失控制方法过失控制方法汉明间隔汉明间隔汉明间隔又称码距，它是指两个等长二进汉明间隔又称码距，它是指两个等长二进制码组之间对应位不同的个数，用来描画制码组之间对应位不同的个数，用来描画码组之间的不同程度。码组之间的不同程度。其中其中
10、aji,aki分别为第分别为第j个码组和第个码组和第k个码组的个码组的第第i为码元为码元;n为码组长度为码组长度一个码组集合中，任何两个码组间的汉明一个码组集合中，任何两个码组间的汉明间隔的最小值称为最小码距。间隔的最小值称为最小码距。最小码距越大，过失控制才干越强。最小码距越大，过失控制才干越强。汉明间隔汉明间隔汉明间隔又称码距，它是指两个等长二进汉明间隔又称码距，它是指两个等长二进制码组之间对应位不同的个数，用来描画制码组之间对应位不同的个数，用来描画码组之间的不同程度。码组之间的不同程度。许用码许用码000011101110许用码许用码000111最小码距为最小码距为2，接纳端可以，接纳
11、端可以检测出检测出1位错误。位错误。最小码距为最小码距为3，接纳端，接纳端可以检测出可以检测出2位错误。位错误。汉明距和检错纠错的关系汉明距和检错纠错的关系当码字用于检测错误时，假设要检测当码字用于检测错误时，假设要检测e个错个错误，那么分组码最小汉明间隔误，那么分组码最小汉明间隔d0和和e之间的之间的关系：关系：在图中用在图中用A和和B分别表示两个码距为分别表示两个码距为d0的码的码字，假设字，假设A发生发生e个错误，那么个错误，那么A就变成以就变成以A为球心，为球心，e为半径的球面上的码字，为了能为半径的球面上的码字，为了能将这些码字分辩出来，它们必需间隔其最将这些码字分辩出来，它们必需间
12、隔其最近的码字近的码字B至少有一位的差别至少有一位的差别ABed0汉明距和检错纠错的关系汉明距和检错纠错的关系当当码字用于字用于纠正正错误时，假，假设要要纠正正t个个错误，那，那么么在在图中用中用A和和B分分别表示两个表示两个码距距为d0的的码字，假字，假设A发生生t个个错误，那么，那么A就就变成以成以A为球心，球心，t为半径的球面上的半径的球面上的码字；字；B发生生t个个错误，那么，那么B就就变成以成以B为球心，球心，t为半径的球面上的半径的球面上的码字。字。为了在了在出出现t个个错误之后，仍可以分之后，仍可以分辩出出A和和B来，那么，来，那么，A和和B之之间间隔隔应大于大于2t，最小，最小
13、间隔也隔也该当使两球当使两球体外表相距体外表相距为1。ABtd0t1主要内容主要内容过失控制根本原理过失控制根本原理汉明距与检错纠错汉明距与检错纠错过失控制编码过失控制编码过失控制方法过失控制方法过失控制编码过失控制编码奇偶校奇偶校验码：奇偶校：奇偶校验码是奇校是奇校验码和偶校和偶校验码的的统称，是一种最根本的称，是一种最根本的检错码。它是。它是由由n-1位信息元和位信息元和1位校位校验元元组成，可以表示成，可以表示成成为n，n-1。假假设是奇校是奇校验码，在附加上一个，在附加上一个监视元以后，元以后，码长为n的的码字中字中“1的个数的个数为奇数个；奇数个；假假设是偶校是偶校验码，在附加上一个
14、，在附加上一个监视元以后，元以后，码长为n的的码字中字中“1的个数的个数为偶数个。偶数个。奇偶校验码是最常见的检错码方式，它可奇偶校验码是最常见的检错码方式，它可以构成垂直奇偶校验、程度奇偶校验和垂以构成垂直奇偶校验、程度奇偶校验和垂直程度奇偶校验。直程度奇偶校验。垂直奇偶校验：也称为字符奇偶校验。对垂直奇偶校验：也称为字符奇偶校验。对于单元字符代码，在字符代码最后一位加于单元字符代码，在字符代码最后一位加上一个奇偶校验位上一个奇偶校验位b7，使码组中的，使码组中的1的个数的个数为奇数或者偶数。为奇数或者偶数。接纳端可以经过校验接纳字符码组中的接纳端可以经过校验接纳字符码组中的1的的个数为偶数
15、个数为偶数(或奇数或奇数)来判别传输能否有过来判别传输能否有过失。失。过失控制编码过失控制编码垂直程度奇偶校验垂直程度奇偶校验又叫二维奇偶校验或方阵校验。它不仅对程度又叫二维奇偶校验或方阵校验。它不仅对程度行方向的码元，而且还对垂直列方向的码行方向的码元，而且还对垂直列方向的码元实施奇偶监视。元实施奇偶监视。将信息码组陈列成矩阵，每一个码组写成一行，将信息码组陈列成矩阵，每一个码组写成一行，然后根据奇偶校验原理在垂直和程度两个方向进然后根据奇偶校验原理在垂直和程度两个方向进展校验。展校验。发送时需求将校验位和校验码发送到接纳端。发送时需求将校验位和校验码发送到接纳端。1100101000010
16、00011010111100001100111000010101010100010111000111100恒比码恒比码恒比码中的恒比码中的1和和0的个数坚持恒定比例。的个数坚持恒定比例。数字码字012345678901101010111100110110110100011110101111000111010011假设码长为假设码长为n，码重为，码重为w，那么此，那么此码的码字个数为码的码字个数为，禁用码字，禁用码字数为数为。该码的检错才干较强，除对换过该码的检错才干较强，除对换过失失1和和0成对的产生错误不能成对的产生错误不能发现外，其它各种错误均能发现。发现外，其它各种错误均能发现。国际上通
17、用的电报通讯系统中，国际上通用的电报通讯系统中，采用采用7中取中取3码，实际证明，运用码，实际证明，运用这种码，使国际电报通讯的误码这种码，使国际电报通讯的误码率坚持在以率坚持在以10-6下。下。循环冗余校验编码循环冗余校验编码又称又称CRC码，纠错才干强，采用多项式编码，纠错才干强，采用多项式编码的方法。目前广泛运用的一种纠错编码。码的方法。目前广泛运用的一种纠错编码。二进制可运用多项式来表示：如二进制可运用多项式来表示：如10111可表可表示为：示为：x4+x2+x+1,多项式的系数就代表二进多项式的系数就代表二进制制10111.对长度为对长度为n的二进制序列，存在一个以的二进制序列，存在
18、一个以x为为基的基的n-1次多项式。次多项式。00000101001x100101111x2x2+1x2+x+1在发送端，将要发送的数据比特序在发送端，将要发送的数据比特序列作为一个多项式列作为一个多项式T(x)的系数，并的系数，并选定一个选定一个k次幂的生成多项式次幂的生成多项式G(x)。对于二进制乘法对于二进制乘法,该步意味着数据该步意味着数据比特序列左移比特序列左移k位位.CRC根本原理根本原理CRC生成多项式生成多项式G(x)规范：运用时从中选择：规范：运用时从中选择：CRC-12G(x)=x12+x11+x3+x2+1CRC-16G(x)=x16+x15+x2+1T(x)T(x) x
19、k k位位T(x) xk R(x)G(x)将将T(x)xk除以生成多项式除以生成多项式G(x)其中其中Q(x)为商，为商，R(x)为余数。为余数。将将T(x)xk+R(x)所对应的比特序列作为一个整体发送。所对应的比特序列作为一个整体发送。校验过程校验过程 (接纳端接纳端)在接在接纳端，端，对接接纳序列所序列所对应的多的多项式式T(x)xk进展与展与发送端同送端同样的运算，即：的运算，即：比比较R(x)和和R(x)，假，假设R(x)=R(x)，以，以为传输正正确，否那么以确，否那么以为传输错误。T(x) xk R(x)CRC例子例子假设发送数据为假设发送数据为110011;生成多项式为生成多项
20、式为x4+x3+1，k=4，所对应的序列为，所对应的序列为11001；将发送数据序列左移将发送数据序列左移4位，新的序列为：位，新的序列为：1100110000;按模按模2算法，将生成的新序列用多项式序列去除，算法，将生成的新序列用多项式序列去除，Q(x)T(x)xkR(x)发送新序列为：发送新序列为：1100111001假设没有发送失败那么接纳端收到的假设没有发送失败那么接纳端收到的比特序列一定能被同一个多项式整除。比特序列一定能被同一个多项式整除。CRC的性能的性能CRC生成的多项式构造与检错效果曾经过生成的多项式构造与检错效果曾经过严厉的数学分析。严厉的数学分析。能检错出全部单个错误、能
21、检测出全部随能检错出全部单个错误、能检测出全部随机的机的2位错误位错误能检测出全部奇数个错误。能检测出全部奇数个错误。能检测出全部长度小于等于能检测出全部长度小于等于k位的突发错误位的突发错误能以能以1-(1/2)k-1的概率检测出长度为的概率检测出长度为k+1位突位突发错误。发错误。发送方将数据单元分成发送方将数据单元分成k段，每段段，每段n比特；比特；将各段相加求和；对和取反得到校验和；将各段相加求和；对和取反得到校验和；将校验和字段附加到数据序列末尾与数据将校验和字段附加到数据序列末尾与数据一同发送。一同发送。校验和编码校验和编码接纳端将接纳到的数据单元分生长度为接纳端将接纳到的数据单元
22、分生长度为n比比特的段；将一切分段相加求和；对和求反；特的段；将一切分段相加求和；对和求反；假设结果为假设结果为0，表示传输正确。，表示传输正确。nnnnnnnn校验和例子校验和例子例：假定要发送例：假定要发送16位数据位数据1010100100111001,采用采用8位位校验和，那么发送比特为：校验和，那么发送比特为：1010100100111001000111011010100100111001+1110001000011101取反取反发送端发送端1010100100111001+0001110100000000取反取反接纳端接纳端11111111能检测一切奇数个错误及大多数偶数个错误，但
23、能检测一切奇数个错误及大多数偶数个错误，但假设某一段中的一个或多个比特损坏，下一个分假设某一段中的一个或多个比特损坏，下一个分段中具有相反值的对应位也被破坏，这些列的和段中具有相反值的对应位也被破坏，这些列的和坚持不变，从而无法检测出错。坚持不变，从而无法检测出错。0010100110111001+0001110100000000取反取反11111111出错情况出错情况0010100100111001+0001110110000000取反取反01111111主要内容主要内容过失控制根本原理过失控制根本原理汉明距与检错纠错汉明距与检错纠错过失控制编码过失控制编码过失控制方法过失控制方法过失控制方
24、法过失控制方法发送端对信源数据进展纠错编码，然后送信道传输。发送端对信源数据进展纠错编码，然后送信道传输。接纳端对信号译码，假设检测传输中的错误那么自接纳端对信号译码，假设检测传输中的错误那么自动纠正。动纠正。优点：不需求反向信道，能用于单工通讯，也可用优点：不需求反向信道，能用于单工通讯，也可用于一点对多点通讯。于一点对多点通讯。缺陷：译码设备复杂，为纠正错误需求附加较多的缺陷：译码设备复杂，为纠正错误需求附加较多的冗余码元，传输效率低。冗余码元，传输效率低。向前纠错向前纠错FEC：又称自动纠错，其数学模型如以下：又称自动纠错，其数学模型如以下图：图：信源信源FEC编码信道信道FEC译码信宿
25、信宿过失控制方法过失控制方法自动恳求重发自动恳求重发(ARQ):用于检错编码，接纳用于检错编码，接纳端经过译码可以发现传输错误，但是无法端经过译码可以发现传输错误，但是无法纠正，因此采用自动恳求重发的任务方式。纠正，因此采用自动恳求重发的任务方式。发送端在将数据发向信道的同时还进展缓存，以备发送端在将数据发向信道的同时还进展缓存，以备重发运用。假设接到重发恳求，那么将该数据放入重发运用。假设接到重发恳求，那么将该数据放入缓存器重新编码发送。缓存器重新编码发送。接纳端经过判决器检测，假设正确接纳那么发送接纳端经过判决器检测，假设正确接纳那么发送ACK；在检测到错误时发送；在检测到错误时发送NAC
26、K，要求重发。，要求重发。信源信源编码器器正向信道正向信道译码器器信宿信宿缓存器存器重重发控制器控制器反向信道反向信道重重发判决器判决器自动恳求重发的实现方式自动恳求重发的实现方式停顿停顿-等待方式：每发送一个数据分组后就停顿等等待方式：每发送一个数据分组后就停顿等待接纳端的应对信号。假设发送端收到确认信号待接纳端的应对信号。假设发送端收到确认信号就发送下一组数据，假设收到否认信号就重发。就发送下一组数据，假设收到否认信号就重发。延续重发方式延续重发方式发送端可以延续向接纳端发送数据，接纳端对接发送端可以延续向接纳端发送数据，接纳端对接纳到的数据进展校验，根据结果向发送端发送应纳到的数据进展校
27、验，根据结果向发送端发送应对信号。对信号。当发送端接纳到否认信号就退回到有错的数据分当发送端接纳到否认信号就退回到有错的数据分组，并重发此分组及以后的分组。组，并重发此分组及以后的分组。接纳端丢弃有错误的分组及该分组之后的分组，接纳端丢弃有错误的分组及该分组之后的分组，直到有错误的分组被正确接纳到为止。直到有错误的分组被正确接纳到为止。0123452345601234523456丢弃丢弃选择重发方式选择重发方式选择重发方式与延续重发方式的不同在于：选择重发方式与延续重发方式的不同在于：发送端仅重传接纳出错的数据分组。发送端仅重传接纳出错的数据分组。0123452678901234526789丢
28、弃丢弃选择性选择性ARQ与延续与延续ARQ方式相比，选择性方式相比，选择性ARQ要比延续性要比延续性ARQ方式更有效，但是由于接纳方进方式更有效，但是由于接纳方进展重新排序和存储桢带来的复杂性，以及发送方展重新排序和存储桢带来的复杂性，以及发送方所需求的额外开销，选择性所需求的额外开销，选择性ARQ并不常用。并不常用。作业作业设于发送的数据序列为设于发送的数据序列为1101011011，声称多，声称多项式为项式为G(x)=x4+x+1,试求采用试求采用CRC校验的校验的发送数据序列。发送数据序列。知知CRC码的生成多项式码的生成多项式G(x)=x5+x4+x+1假假设接纳端接纳的数据序列为设接纳端接纳的数据序列为1010110001101，传输中能否出现了错误？，传输中能否出现了错误？
