吳炳昊，董俊超，阮秋琦

(1.北京全路通信信號研究設(shè)計院集團(tuán)有限公司，北京 100070； 2.通號城市軌道交通技術(shù)有限公司，北京 100070； 3.北京交通大學(xué) 信息科學(xué)研究所，北京 100081)

CRC校驗是常用的信息錯誤檢測方法，其檢錯能力與選用的CRC生成多項式有關(guān)。IEEE 802.3使用的CRC-32(0x104c11db7)是眾多CRC生成多項式中著名的一個[1]，也因其著名而被廣泛使用。北京S1線也采用CRC校驗來檢測車地通信的信息錯誤，但因其信息幀僅有128 bit，需在消耗盡量少校驗位的同時，擁有較高的信息檢錯能力，因此，選擇適合的CRC生成多項式，是一個需要攻克的技術(shù)難點。本文的研究，為此提供了基礎(chǔ)，并說明：應(yīng)根據(jù)數(shù)據(jù)位bit數(shù)、信道誤碼率，而非CRC生成多項式的著名程度，去選擇適合檢錯能力要求的CRC生成多項式。

1 分析前提與基礎(chǔ)

1.1 BSC信道與通信場景

本文采用低誤碼率的二進(jìn)制對稱信道(Binary Symmetric Channel，BSC)作為通信信道模型，對CRC檢錯能力(即漏檢率)進(jìn)行分析與實驗。

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

(1)無記憶。每個bit發(fā)生錯誤相互獨立、概率相等。

(2)對稱。每個bit從“0”錯為“1”的概率，和從“1”錯為“0”的概率相等。

BSC信道中，任一個bit發(fā)生錯誤的概率與BSC信道的誤碼率相等。BSC信道的誤碼率在本文中記為e，有e< 1/2[4-5]。

設(shè)傳輸信息幀的bit數(shù)為l，其中包含nbit數(shù)據(jù)位和kbit校驗位，即l=n+k。本文考慮的通信場景是低誤碼率BSC信道中的l=128 bit信息幀。

1.2 CRC漏檢情況分析

設(shè)某信息幀有nbit的數(shù)據(jù)位Data(x)，使用的CRC生成多項式為CRC(x)，則信源傳輸?shù)男畔S(x)為[6]

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

(1)

式中：Data(x)×xk為前nbit數(shù)據(jù)位；(Data(x)×xk)modCRC(x)為后kbit校驗位；MS(x)為這兩部分之和。MS(x)必能被CRC(x)整除，即

0≡MS(x)modCRC(x)

(2)

基于BSC信道的特點，用多項式E(x)表示BSC信道產(chǎn)生的誤碼，用多項式MD(x)表示信宿接收到的信息，則MD(x)可表示為

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

(3)

式(3)中多項式E(x)中非0項的個數(shù)，即為MS(x)通過BSC信道發(fā)生錯誤的bit數(shù)，也就是誤碼的碼重。信宿判斷收到信息正確的條件為[6]

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

E(x)modCRC(x)=0

(4)

根據(jù)模運算規(guī)則[7]，信宿通過CRC校驗的條件也可表示為

E(x)modCRC(x)=0

(5)

在式(5)得到滿足時，如果還有E(x)≠0，則意味著信息發(fā)生錯誤，且信宿未檢出。因此，BSC信道的CRC漏檢決定于：信息幀包含的數(shù)據(jù)位bit數(shù)n，BSC信道的誤碼率e，以及使用的CRC生成多項式CRC(x)。該推論與Philip Koopman教授[8]的研究結(jié)果相符。

1.3 CRC生成多項式檢錯特性

一些影響CRC生成多項式檢錯能力的特性有[9]：

(1)若CRC(x)為本原多項式(Primitive Polynomial)，可得到指定k時可防護(hù)最多的信息bit數(shù)(2k-1，含數(shù)據(jù)位和校驗位)，且可檢出所有單bit錯誤和兩bit錯誤。

(2)若CRC(x)包含(x+1)因子，可檢出所有奇數(shù)bit錯誤。

(3)所有的CRC(x)均可檢出誤碼長度不超過k(含k)的錯誤。

需要說明的是，上述第(3)項中的誤碼長度不同于誤碼bit數(shù)，而是指傳輸信息中第一個錯誤bit到最后一個錯誤bit之間的距離。如：若10101100錯為11111110，則誤碼數(shù)為3，誤碼長度為6；若10101100錯為00101101，則誤碼數(shù)為2，誤碼長度為8。

本文的分析對象是CRC-24(0x1974f0b)與CRC-32(0x104c11db7)對l=128 bit信息幀的檢錯能力。根據(jù)Philip Koopman[8]的研究成果，CRC-24(0x1974f0b)是其列出的所有CRC-24生成多項式中，可檢出128 bit信息幀中最多錯誤bit數(shù)的多項式；而CRC-32(0x104c11db7)為IEEE 802.3使用的CRC-32生成多項式[1]。通過Wolfram Alpha[10]可發(fā)現(xiàn)：CRC-24(0x1974f0b)含(x+1)因子，因此可檢出所有奇數(shù)bit錯誤；CRC-32(0x104c11db7)為本原多項式(不可分解為各因子相乘的形式)，因此可在低誤碼率的環(huán)境下用來防護(hù)較多bit的數(shù)據(jù)位[1,11]。它們對l=128 bit信息幀的檢錯能力對比見表1。

表1 CRC-24(0x1974f0b)與CRC-32(0x104c11db7)對128 bit信息幀的檢錯能力對比[8]

2 檢錯能力推導(dǎo)

CRC-24(0x1974f0b)和CRC-32(0x104c11db7)的檢錯能力推導(dǎo)分以下2種情況：

情況1，可完全檢錯情況：信息錯誤bit數(shù)在可完全檢錯范圍內(nèi)。

情況2，不能完全檢錯情況：信息錯誤bit數(shù)在可完全檢錯范圍外，即情況1以外的情況。

可見，情況1和情況2互不重疊，并且完整考慮了CRC校驗的所有誤碼情況，其中也包含本文1.3節(jié)中的第(3)項。因此，通過對上述兩種情況的分析，再進(jìn)行綜合，即可得出CRC生成多項式的總體檢錯能力。

2.1 CRC生成多項式檢錯能力的推導(dǎo)

(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)檢錯能力的強(qiáng)弱取決于λm和βm。

綜合情況1與情況2，可被CRC-24(0x1974f0b)檢出錯誤的總概率P24(e)為

(17)

(18)

同樣，對于CRC-32(0x104c11db7)，綜合情況1與情況2，可被其檢出錯誤的總概率P32(e)為

(19)

(20)

2.2 CRC生成多項式檢錯能力推導(dǎo)的驗證

情況1、情況2以及無錯誤發(fā)生情況的概率總和應(yīng)為1，可以此驗證之前分析的正確性。

對于CRC-24(0x1974f0b)：

對于CRC-32(0x104c11db7)：

3 低誤碼率區(qū)間的檢錯能力比較分析

3.1 可用數(shù)據(jù)

針對CRC-24(0x1974f0b)和CRC-32(0x104c11db7)，Philip Koopman教授[8]的研究結(jié)果給出了一些可用數(shù)據(jù)。l=128 bit時，結(jié)合表1，CRC-24(0x1974f0b)和CRC-32(0x104c11db7)有以下可用數(shù)據(jù)：

(1)CRC-24漏檢數(shù)λm：0≤m≤7或m為奇數(shù)時，λm=0；另外有λ8=176 516，λ10=26 989 715。

(2)CRC-32漏檢數(shù)βm：0≤m≤6時，βm=0；另外有β7=5，β8=360，β9=4 726。

3.2 漏檢率比較分析

通過CRC-24(0x1974f0b)和CRC-32(0x104c11db7)的漏檢情況數(shù)λm和βm，可得到漏檢比例，分別記為am和bm。l=128 bit時，am和bm可表示為

(21)

結(jié)合式(21)和λm、βm的可用數(shù)據(jù)，可以得到：

(1)CRC-24漏檢比例am。0≤m≤7或m為奇數(shù)時，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)，將上述數(shù)據(jù)代入式(18)，并結(jié)合式(21)，可得到

(22)

(23)

對于CRC-32(0x104c11db7)，將已知的CRC-32漏檢比例bm代入式(20)，并結(jié)合式(21)，可得到

(24)

(25)

圖與的比較

3.3 誤碼率e趨近于0時的進(jìn)一步論證

由于前文的計算基于誤碼率e的離散采樣點，為說明分析結(jié)果對低誤碼率區(qū)間連續(xù)誤碼率的適用性，采用極限運算進(jìn)行分析。

由式(6)可以得到：

(26)

結(jié)合式(18)和式(20)，分別有

(27)

(28)

對它們的比值取對數(shù)可以得到

(29)

因此，在e趨近于0時，本文的分析結(jié)果仍然成立；且e越小，CRC-24(0x1974f0b)相比CRC-32(0x104c11db7)的檢錯能力的優(yōu)勢就越顯著。

3.4 誤碼率臨界點e0準(zhǔn)確度分析

圖2 e0的精準(zhǔn)度分析

綜上，本文得到的e0具有高準(zhǔn)確度，即實際的臨界誤碼率與e0=2.838 41×10-5非常接近。

4 誤碼率的測量方案

信息幀bit數(shù)l，BSC信道誤碼率e與錯誤信息幀概率(記為pf)的關(guān)系可表示為

pf=1-(1-e)l

(30)

在實踐中，可通過統(tǒng)計得到CRC校驗未通過的信息幀數(shù)量占總信息幀數(shù)量的比率。CRC校驗的漏檢概率可按2-k進(jìn)行估計[3]，對于CRC-24和CRC-32，它們漏檢的錯誤信息幀數(shù)量相比檢出的錯誤信息幀數(shù)量可忽略。因此，經(jīng)過統(tǒng)計可得到CRC校驗未通過的信息幀數(shù)量占總信息幀數(shù)量的比率，該值約等于pf，統(tǒng)計數(shù)量越大、誤差越小。因此，可通過式(30)和已知的l、統(tǒng)計得到的pf，計算BSC信道的誤碼率e。后續(xù)可通過上述方法對BSC信道誤碼率進(jìn)行測量。

5 結(jié)論

(1)本文基于BSC信道，針對北京S1線車地通信128 bit信息幀(包含數(shù)據(jù)位、校驗位)的場景，對CRC-24(0x1974f0b)與IEEE 802.3使用的CRC-32(0x104c11db7)的漏檢率進(jìn)行了分析和定量比較，并給出了誤碼率的測量方法。

(2)本文在Philip Koopman教授研究成果的基礎(chǔ)上，測算出CRC-24(0x1974f0b)的檢錯能力優(yōu)于CRC-32(0x104c11db7)的臨界誤碼率e0近似為2.838 41×10-5，且誤差很小。可認(rèn)為128 bit信息幀在BSC信道誤碼率低于e0=2.838 41×10-5時，CRC-24(0x1974f0b)不但比CRC-32(0x104c11db7)少消耗8 bit校驗位，還能提供更優(yōu)的檢錯能力，并且誤碼率越低優(yōu)勢越顯著。

(3)在實踐中，應(yīng)根據(jù)需防護(hù)的數(shù)據(jù)位bit數(shù)、信道誤碼率、以及對檢錯能力的要求等因素選擇合適的CRC生成多項式。