吳炳昊,董俊超,阮秋琦
(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)式。
本文采用低誤碼率的二進(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信息幀。
設(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é)果相符。
一些影響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]
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ò)能力。
(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) 情況1、情況2以及無(wú)錯(cuò)誤發(fā)生情況的概率總和應(yīng)為1,可以此驗(yàn)證之前分析的正確性。 對(duì)于CRC-24(0x1974f0b): 對(duì)于CRC-32(0x104c11db7): 針對(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。 通過(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) 圖與的比較 由于前文的計(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ì)就越顯著。 圖2 e0的精準(zhǔn)度分析 綜上,本文得到的e0具有高準(zhǔn)確度,即實(shí)際的臨界誤碼率與e0=2.838 41×10-5非常接近。 信息幀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è)量。 (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)式。2.2 CRC生成多項(xiàng)式檢錯(cuò)能力推導(dǎo)的驗(yàn)證
3 低誤碼率區(qū)間的檢錯(cuò)能力比較分析
3.1 可用數(shù)據(jù)
3.2 漏檢率比較分析
3.3 誤碼率e趨近于0時(shí)的進(jìn)一步論證
3.4 誤碼率臨界點(diǎn)e0準(zhǔn)確度分析
4 誤碼率的測(cè)量方案
5 結(jié)論