吴炳昊，董俊超，阮秋琦

(1.北京全路通信信号研究设计院集团有限公司，北京 100070； 2.通号城市轨道交通技术有限公司，北京 100070； 3.北京交通大学 信息科学研究所，北京 100081)

CRC校验是常用的信息错误检测方法，其检错能力与选用的CRC生成多项式有关。IEEE 802.3使用的CRC-32(0x104c11db7)是众多CRC生成多项式中著名的一个[1]，也因其著名而被广泛使用。北京S1线也采用CRC校验来检测车地通信的信息错误，但因其信息帧仅有128 bit，需在消耗尽量少校验位的同时，拥有较高的信息检错能力，因此，选择适合的CRC生成多项式，是一个需要攻克的技术难点。本文的研究，为此提供了基础，并说明：应根据数据位bit数、信道误码率，而非CRC生成多项式的著名程度，去选择适合检错能力要求的CRC生成多项式。

1 分析前提与基础

1.1 BSC信道与通信场景

本文采用低误码率的二进制对称信道(Binary Symmetric Channel，BSC)作为通信信道模型，对CRC检错能力(即漏检率)进行分析与实验。

BSC信道的特点[2-3]：

(1)无记忆。每个bit发生错误相互独立、概率相等。

(2)对称。每个bit从“0”错为“1”的概率，和从“1”错为“0”的概率相等。

BSC信道中，任一个bit发生错误的概率与BSC信道的误码率相等。BSC信道的误码率在本文中记为e，有e< 1/2[4-5]。

设传输信息帧的bit数为l，其中包含nbit数据位和kbit校验位，即l=n+k。本文考虑的通信场景是低误码率BSC信道中的l=128 bit信息帧。

1.2 CRC漏检情况分析

设某信息帧有nbit的数据位Data(x)，使用的CRC生成多项式为CRC(x)，则信源传输的信息MS(x)为[6]

MS(x)=Data(x)×xk+(Data(x)×xk)modCRC(x)

(1)

式中：Data(x)×xk为前nbit数据位；(Data(x)×xk)modCRC(x)为后kbit校验位；MS(x)为这两部分之和。MS(x)必能被CRC(x)整除，即

0≡MS(x)modCRC(x)

(2)

基于BSC信道的特点，用多项式E(x)表示BSC信道产生的误码，用多项式MD(x)表示信宿接收到的信息，则MD(x)可表示为

MD(x)=MS(x)+E(x)

(3)

式(3)中多项式E(x)中非0项的个数，即为MS(x)通过BSC信道发生错误的bit数，也就是误码的码重。信宿判断收到信息正确的条件为[6]

MD(x)modCRC(x)=MS(x)modCRC(x)+

E(x)modCRC(x)=0

(4)

根据模运算规则[7]，信宿通过CRC校验的条件也可表示为

E(x)modCRC(x)=0

(5)

在式(5)得到满足时，如果还有E(x)≠0，则意味着信息发生错误，且信宿未检出。因此，BSC信道的CRC漏检决定于：信息帧包含的数据位bit数n，BSC信道的误码率e，以及使用的CRC生成多项式CRC(x)。该推论与Philip Koopman教授[8]的研究结果相符。

1.3 CRC生成多项式检错特性

一些影响CRC生成多项式检错能力的特性有[9]：

(1)若CRC(x)为本原多项式(Primitive Polynomial)，可得到指定k时可防护最多的信息bit数(2k-1，含数据位和校验位)，且可检出所有单bit错误和两bit错误。

(2)若CRC(x)包含(x+1)因子，可检出所有奇数bit错误。

(3)所有的CRC(x)均可检出误码长度不超过k(含k)的错误。

需要说明的是，上述第(3)项中的误码长度不同于误码bit数，而是指传输信息中第一个错误bit到最后一个错误bit之间的距离。如：若10101100错为11111110，则误码数为3，误码长度为6；若10101100错为00101101，则误码数为2，误码长度为8。

本文的分析对象是CRC-24(0x1974f0b)与CRC-32(0x104c11db7)对l=128 bit信息帧的检错能力。根据Philip Koopman[8]的研究成果，CRC-24(0x1974f0b)是其列出的所有CRC-24生成多项式中，可检出128 bit信息帧中最多错误bit数的多项式；而CRC-32(0x104c11db7)为IEEE 802.3使用的CRC-32生成多项式[1]。通过Wolfram Alpha[10]可发现：CRC-24(0x1974f0b)含(x+1)因子，因此可检出所有奇数bit错误；CRC-32(0x104c11db7)为本原多项式(不可分解为各因子相乘的形式)，因此可在低误码率的环境下用来防护较多bit的数据位[1,11]。它们对l=128 bit信息帧的检错能力对比见表1。

表1 CRC-24(0x1974f0b)与CRC-32(0x104c11db7)对128 bit信息帧的检错能力对比[8]

2 检错能力推导

CRC-24(0x1974f0b)和CRC-32(0x104c11db7)的检错能力推导分以下2种情况：

情况1，可完全检错情况：信息错误bit数在可完全检错范围内。

情况2，不能完全检错情况：信息错误bit数在可完全检错范围外，即情况1以外的情况。

可见，情况1和情况2互不重叠，并且完整考虑了CRC校验的所有误码情况，其中也包含本文1.3节中的第(3)项。因此，通过对上述两种情况的分析，再进行综合，即可得出CRC生成多项式的总体检错能力。

2.1 CRC生成多项式检错能力的推导

(6)

对于情况1，由表1可知：

(7)

CRC-32(0x104c11db7)可检出所有1～6 bit错误，其可完全检错情况的总概率P32a(e)为

(8)

比较式(7)和式(8)可知，P32a(e)

对于情况2，由表1可知：

(9)

(10)

λm×em×(1-e)l-m

(11)

(12)

(13)

(14)

βm×em×(1-e)l-m

(15)

(16)

综上，在情况2下，CRC-24 (0x1974f0b)与CRC-32(0x104c11db7)检错能力的强弱取决于λm和βm。

综合情况1与情况2，可被CRC-24(0x1974f0b)检出错误的总概率P24(e)为

(17)

(18)

同样，对于CRC-32(0x104c11db7)，综合情况1与情况2，可被其检出错误的总概率P32(e)为

(19)

(20)

2.2 CRC生成多项式检错能力推导的验证

情况1、情况2以及无错误发生情况的概率总和应为1，可以此验证之前分析的正确性。

对于CRC-24(0x1974f0b)：

对于CRC-32(0x104c11db7)：

3 低误码率区间的检错能力比较分析

3.1 可用数据

针对CRC-24(0x1974f0b)和CRC-32(0x104c11db7)，Philip Koopman教授[8]的研究结果给出了一些可用数据。l=128 bit时，结合表1，CRC-24(0x1974f0b)和CRC-32(0x104c11db7)有以下可用数据：

(1)CRC-24漏检数λm：0≤m≤7或m为奇数时，λm=0；另外有λ8=176 516，λ10=26 989 715。

(2)CRC-32漏检数βm：0≤m≤6时，βm=0；另外有β7=5，β8=360，β9=4 726。

3.2 漏检率比较分析

通过CRC-24(0x1974f0b)和CRC-32(0x104c11db7)的漏检情况数λm和βm，可得到漏检比例，分别记为am和bm。l=128 bit时，am和bm可表示为

(21)

结合式(21)和λm、βm的可用数据，可以得到：

(1)CRC-24漏检比例am。0≤m≤7或m为奇数时，am=0；另外有a8=1.234 6×10-7，a10=1.189 8×10-7。

(2)CRC-32漏检比例bm。0≤m≤6时，bm=0；另外有b7=5.289 6×10-11，b8=2.518 0×10-10，b9=2.479 2×10-10。

对于CRC-24(0x1974f0b)，将上述数据代入式(18)，并结合式(21)，可得到

(22)

(23)

对于CRC-32(0x104c11db7)，将已知的CRC-32漏检比例bm代入式(20)，并结合式(21)，可得到

(24)

(25)

图与的比较

3.3 误码率e趋近于0时的进一步论证

由于前文的计算基于误码率e的离散采样点，为说明分析结果对低误码率区间连续误码率的适用性，采用极限运算进行分析。

由式(6)可以得到：

(26)

结合式(18)和式(20)，分别有

(27)

(28)

对它们的比值取对数可以得到

(29)

因此，在e趋近于0时，本文的分析结果仍然成立；且e越小，CRC-24(0x1974f0b)相比CRC-32(0x104c11db7)的检错能力的优势就越显著。

3.4 误码率临界点e0准确度分析

图2 e0的精准度分析

综上，本文得到的e0具有高准确度，即实际的临界误码率与e0=2.838 41×10-5非常接近。

4 误码率的测量方案

信息帧bit数l，BSC信道误码率e与错误信息帧概率(记为pf)的关系可表示为

pf=1-(1-e)l

(30)

在实践中，可通过统计得到CRC校验未通过的信息帧数量占总信息帧数量的比率。CRC校验的漏检概率可按2-k进行估计[3]，对于CRC-24和CRC-32，它们漏检的错误信息帧数量相比检出的错误信息帧数量可忽略。因此，经过统计可得到CRC校验未通过的信息帧数量占总信息帧数量的比率，该值约等于pf，统计数量越大、误差越小。因此，可通过式(30)和已知的l、统计得到的pf，计算BSC信道的误码率e。后续可通过上述方法对BSC信道误码率进行测量。

5 结论

(1)本文基于BSC信道，针对北京S1线车地通信128 bit信息帧(包含数据位、校验位)的场景，对CRC-24(0x1974f0b)与IEEE 802.3使用的CRC-32(0x104c11db7)的漏检率进行了分析和定量比较，并给出了误码率的测量方法。

(2)本文在Philip Koopman教授研究成果的基础上，测算出CRC-24(0x1974f0b)的检错能力优于CRC-32(0x104c11db7)的临界误码率e0近似为2.838 41×10-5，且误差很小。可认为128 bit信息帧在BSC信道误码率低于e0=2.838 41×10-5时，CRC-24(0x1974f0b)不但比CRC-32(0x104c11db7)少消耗8 bit校验位，还能提供更优的检错能力，并且误码率越低优势越显著。

(3)在实践中，应根据需防护的数据位bit数、信道误码率、以及对检错能力的要求等因素选择合适的CRC生成多项式。