常用检错算法分析及实现

1、几种常用检错算法分析及实现简介：在进行通信的过程中，信道中的各种干扰有可能使通信的内容发生差错；在进行信息的长 期存储时.由于时变效应，所存储的信.态有可能因为存储介质的性质退化而发生一些改变。 为提高信息在通信或存储过程中的准确性，一般要在通信或存储前进行一次编码.使出现的绝 大多数差错都能及时发现，这种编码就是“校验码”，有了校验码就不会把错误的信息当作正 确的信息加以利用，造成不良后果。在发现错误后可以要求重发，直到接收到正确的信息为止。常见的几种校验方式有：奇偶校验，求和校验，LRC校验，CRC校验。奇偶校验最常见的校验码是奇偶校验码，它在原编码的基础上增加了一位奇偶校验位，使得整个编

2、 码1的个数固定为奇数（奇校验）或偶数（偶校验），如表1所列。在信息的传输过程中，如 果有奇数位代码发生改变，校验码的奇偶性（1的个数）就会发生变化.从而检查出差错。如 果有偶数位代码发生改变.则码的奇偶性（1的个数）不变，这时就检查不出筹错。通过概率分析可以得知，如果发生一个位差错的概率为p，则发生两个位差错的概率大约为p2/2.因为p是一个很小的值（例如p=0.001），发生更 多差错的概率就更小。因此，绝大多数都是 一个位差错的情况，而奇偶校验可以发现一 个位差错，故具有很高的实用性。它是由 n-1位信息元和1位校验元组成，可以表示 成为（n，n-1）。如果是奇校验码，在附加原码校验类型

3、奇偶校验码校验码中1的个数原码位校验位0 xA6奇校验1010011015偶校验10100110040 x5B奇校验0101101105偶校验0101101116表1奇偶校验码示意表上一个校验元以后，码长为n的码字中“ 1”的个数为奇数个；如果是偶校验码，在附加上一 个校验元以后，码长为n的码字中“1”的个数为偶数个。设：如果一个偶校验码的码字用 A=an-1,an-2,，a1,a0表示，则：an-1,an-2,-，a1,a0=0o这个式子通常被称为校验方程。由信息 元即可求出校验元。另外，如果发生单个（或奇数个）错误，就会破坏这个关系式，因此通过 该式能检测码字中是否发生了单个或奇数个错误。

4、因为奇校验不能产生全0的代码一般很少使 用，常用的奇偶校验码是“偶校验码”。和校验当干扰持续时间很短（如常见的尖峰干扰）时，差错一般是单个出现.这时采用奇偶校验 可以有效地达到检错的目的们也有一些突发性干扰的持续时间较长（如雷电、电源波动等）， 会引起连续几个位差错.在进行信息存储时.存储介质的缺陷也会引起连续几个位差错。如果 差错数是2、4、6个，简单的奇偶校验就不能发现差错，这时可以采用“和校验”。如果一串信息有n字节，对这，字节进行“加”运算，然后将结果附曲字节信息后面一 起传送（或存储），这附加的字节就是“校验和。接收方按相同的算法对这n字节信息进行运 算，将运算结果与附加的校验字节进

5、行比较.从而判断有无差错。这种检错方式就是“和校验”。 在这里所谓的“加”运算有两种，一种是模2加（按位加），采用按位“异或”操作指令来完 成；另一种是算术加（按字节加），采用加法指令来完成。两种算法的检错效果相同。纵向冗余校验（LRC）纵向冗余校验（LRC，Longitudinal Redundancy Check）是通信中常用的一种校验形式。纵 向冗余校验（LRC）是一种从纵向通道上的特定比特串产生校验比特的错误检测方法。在行列格式 中（例如，在磁带中），LRC经常是与VRC 一起使用，这样就会为每个字符校验码。LRC域是一个包含一个8位二进制值的字节。LRC值由传输设备来计算并放到消息帧

6、中， 接收设备在接收消息的过程中计算LRC，并将它和接收到消息中LRC域中的值比较，如果两值 不等，说明有错误。LRC校验比较简单，它在ASCII协议中使用，检测了消息域中除开始的冒 号及结束的回车换行号外的内容。计算方法1：取反后加1B：把数据转换为二进制，每位取反后再加1B。例如：0AH=00001010B，按位 取反后得 11110101B，11110101B+1B=11110110B=F6H，0AH 的二次反补就是 F6H。取反后加1H：把数据转换为二进制，每位取反后再加1H。例如：0AH=00001010B，按位 取反后得 11110101B=F5H，F5H+1H=F6H，0AH 的

7、二次反补就是 F6H。计算方法2：有个简单算法就是：这个十六进制值有几位数，就把高于这个位数的最小值减去这个值。 如果16进制数有2位，那么高于2位的最小值就是100H，用100H减去这个数就是其二次反 补。实际上，该方法的原理和方法1相同：以2位16进制数为例，FFH减去那个数就是把那 个数取反（FFH的数据为全1，减去那个数的结果就是原来1的位数变为0，原来0的位数变 为1），而FFH+1H=100H。所以取反然后加一就等于100H减去这个数。0AH的二次反补就是： 100H-0AH=F6H循环冗余检验（CRC）应用最广泛、功能最强大的校验码是循环冗余校验码CRC （Cyclical Re

8、dundancy Check）。CRC 的基本原理是将一段信息看成一个很长的二进制数（例如将一段128字节的信息看成一个1024 位的二进制数）.然后用一个特定的数（例如二进制数10001000000100001B，即十六进制数 0 x11021）去除它，最后将余数作为校验码附在信息代码之后一起传送（或存储。在进行接收 （或读出）时进行同样的处理，若有差错即可发现。据文献资料分析，当采用余数为16位的CRC时，它的错误发现率如下：单个位的差错：100%比16位短的突发性差错：100%两个位差错：100%恰好17位的突发性差错：99.9969%奇数个位差错：100%其他所有的突发性差错：9如此强

9、大的检错能力使CRC广泛地使用在数据存储与数据通信中，并且在国际上已经形成 规范，以硬件形式放入磁盘骆动器和通信产品中。任意一个由二进制位串组成的代码都可以与一个系数仅为“0和“1”的多项式一一对应。例 如：代码 1010111B 对应的多项式为 1X6+0X5+1X4+0X3+1X2+1X1+1X0，艮口 X6+X4+X2+X+1 ；而多项式 为 X5+X3+X2+X+1 对应的代码 101111B。设编码前的原始信息多项式为P(x)，P(x)的最高幕次加1等于k；生成多项式为G(x)，G(x) 的最高幕次等于r； CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。发送方编码方

10、法：将P(x)乘以Xr,(即对应的二进制码序列左移r位，右边填补r个零)， 再除以G(x).所得余式即为R(x)。用公式表示为：T(x)=X2P(x)+R(x)。接收方解码方法：将T(x) 除以G(x)，如果余数为O,则说明传输中无错误发生，否则说明传输有误。举例说明，设信息码为1101100111，生成多项式为100010000001000011B，即： P(X)=X7+X6+X4+X3+1，G(X)=X16+X12+X5+1。计算CRC的过程为：首先将原始信息码左移16位，变 为110110010000000000000000B，再除以10001000000100001B。不过在这里所用的

11、除法是模 2除法，并非算术除法。1 0001 0000 0010 000110 0001 0000 0000 0000 0000湖 100 0100 0000 1000 01010 0101 0000 1000 0100 0000E 001。0000 0100 00100 0111 Q。1100 0110 0000 100 0100 0000 1000 01 011 0100 1100 1110 010010 0010 0000 0100 00101 0110 1100 1010 01101 0001 0000 0010 00010 0111 1100 1000 0111 图1 CRC校验示意

12、图模2除法的操作过程是：从被除数高端 (数据串的开始端)开始，取与除数相同的 比特，如果最高位为0，得1比特的商0,被 除数不用减去除数；如果最高位为1，得l 比特的商1，被除数就要减去除数。用“异 或”操作代替减法后，由于除数和被除数的 最高位都为1，“异或”操作必然使结果的 最高位为0,故所得余数必然小于除数的比 特数，实际操作时就可以只进行比除数少1 比特的“异或”操作。整个模2除法的过程 可以概括为从高位到低位按二进制扫描被除数，对每一位进行判断，如果是0,则不用处理； 如果是1，就将其后的若1：比特与除数的低若干比特进行“异或”操作。直至所剩卜的余数 比除数少1比特，该余数就是所需的CRC校验码。附录：CRC校验代码unsigned int CRC_16(unsigned char *buf,unsigned char len)unsigned int crc_gen = 0 xa001;/1,1000,0000,0000,0101B/unsigned in