吳炳昊，董俊超，阮秋琦

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

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

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

1.1 BSC信道與通信場(chǎng)景

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

BSC信道的特點(diǎn)[2-3]：

(1)無(wú)記憶。每個(gè)bit發(fā)生錯(cuò)誤相互獨(dú)立、概率相等。

(2)對(duì)稱。每個(gè)bit從“0”錯(cuò)為“1”的概率，和從“1”錯(cuò)為“0”的概率相等。

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

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

1.2 CRC漏檢情況分析

設(shè)某信息幀有nbit的數(shù)據(jù)位Data(x)，使用的CRC生成多項(xiàng)式為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校驗(yàn)位；MS(x)為這兩部分之和。MS(x)必能被CRC(x)整除，即

0≡MS(x)modCRC(x)

(2)

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

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

(3)

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

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

E(x)modCRC(x)=0

(4)

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

E(x)modCRC(x)=0

(5)

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

1.3 CRC生成多項(xiàng)式檢錯(cuò)特性

一些影響CRC生成多項(xiàng)式檢錯(cuò)能力的特性有[9]：

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

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

(3)所有的CRC(x)均可檢出誤碼長(zhǎng)度不超過(guò)k(含k)的錯(cuò)誤。

需要說(shuō)明的是，上述第(3)項(xiàng)中的誤碼長(zhǎng)度不同于誤碼bit數(shù)，而是指?jìng)鬏斝畔⒅械谝粋€(gè)錯(cuò)誤bit到最后一個(gè)錯(cuò)誤bit之間的距離。如：若10101100錯(cuò)為11111110，則誤碼數(shù)為3，誤碼長(zhǎng)度為6；若10101100錯(cuò)為00101101，則誤碼數(shù)為2，誤碼長(zhǎng)度為8。

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

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

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

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

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

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

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

2.1 CRC生成多項(xiàng)式檢錯(cuò)能力的推導(dǎo)

(6)

對(duì)于情況1，由表1可知：

(7)

CRC-32(0x104c11db7)可檢出所有1～6 bit錯(cuò)誤，其可完全檢錯(cuò)情況的總概率P32a(e)為

(8)

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

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

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

(17)

(18)

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

(19)

(20)

2.2 CRC生成多項(xiàng)式檢錯(cuò)能力推導(dǎo)的驗(yàn)證

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

對(duì)于CRC-24(0x1974f0b)：

對(duì)于CRC-32(0x104c11db7)：

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

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

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

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

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

3.2 漏檢率比較分析

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

(21)

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

(1)CRC-24漏檢比例am。0≤m≤7或m為奇數(shù)時(shí)，am=0；另外有a8=1.234 6×10-7，a10=1.189 8×10-7。

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

對(duì)于CRC-24(0x1974f0b)，將上述數(shù)據(jù)代入式(18)，并結(jié)合式(21)，可得到

(22)

(23)

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

(24)

(25)

圖與的比較

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

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

由式(6)可以得到：

(26)

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

(27)

(28)

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

(29)

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

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

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

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

4 誤碼率的測(cè)量方案

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

pf=1-(1-e)l

(30)

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

5 結(jié)論

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

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

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