余 網(wǎng) 譚明新

（華中師范大學(xué),湖北 武漢 430079）

1 引言

隨著無線技術(shù)和因特網(wǎng)的發(fā)展,對(duì)可攜帶、可移動(dòng)的計(jì)算機(jī)或工作站的需求不斷增長(zhǎng),無線局域網(wǎng)以其高靈活性、緊急狀況下的健壯性被廣泛應(yīng)用,其中應(yīng)用最為廣泛的就是IEEE 802.11系列標(biāo)準(zhǔn)?；贗EEE 802.11的網(wǎng)絡(luò)中,傳輸信息的基本單元通用MAC(Media Access Control:介質(zhì)訪問控制)幀格式如圖1（QoS:quality-of-service服務(wù)質(zhì)量,HT:high-throughput高吞吐率）所示,由MAC頭部、幀體部分、幀校驗(yàn)序列（FCS:Frame Check Sequence）三部分組成。由于幀中包含了幀控制域、持續(xù)時(shí)間/標(biāo)識(shí)、地址域等重要信息,每一個(gè)接收幀的站點(diǎn)要求能夠利用FCS驗(yàn)證每一個(gè)接收到的幀,并從MAC頭部中解釋特定的字段[1]。FCS為32位的CRC(Cyclic Redundancy Check,循環(huán)冗余校驗(yàn))碼,本文主要討論利用CRC糾正單比特的隨機(jī)錯(cuò)誤。

圖1 MAC幀格式

2 CRC碼的生成方法

CRC基本結(jié)構(gòu)如圖2所示。

圖2 CRC的結(jié)構(gòu)

由圖2可知,CRC碼由兩部分組成,即k位信息位和(n-k)位校驗(yàn)位。信息位和校驗(yàn)位分別用碼多項(xiàng)式m(x)和r(x)表示。CRC碼字用多項(xiàng)式c(x)表示,其編碼過程分為兩步:(1)首先將原信息碼 m(x)左移 n-k位,得到 xn-k·m(x)；(2)用xn-k·m(x)除以生成多項(xiàng)式g(x)（模2）,所得的余數(shù)為校驗(yàn)碼r(x)。最后得到完整的碼字多項(xiàng)式 c(x)=xn-k·m(x) +r(x)[2]。

例如,若CRC的生成多項(xiàng)式g(x)=x4+x+1,如果要發(fā)送6位信息110001,則CRC信息的生成按如下步驟實(shí)現(xiàn):首先把信息碼字110001用如下的多項(xiàng)式表示:m(x)=x5+x4+1,信息位k=6。又因?yàn)樯啥囗?xiàng)式g(x)的最高階數(shù)等于4,即n–k=4,因此發(fā)送碼字長(zhǎng)度n=10,包括6bit信息和4bit檢錯(cuò)糾錯(cuò)信息。編碼過程如下:

(1)首先將原信息碼m(x)左移n-k=4位,得到

(2)用x9+x8+x4除以生成多項(xiàng)式g(x)（模2）,得到的余數(shù)即為校驗(yàn)碼,即

(3)發(fā)送碼字多項(xiàng)式

即C(x)=(1100011100)

3 MAC幀糾錯(cuò)的實(shí)現(xiàn)

針對(duì)幀的不同功能,802.11中的MAC幀分為數(shù)據(jù)幀、控制幀、管理幀三類。不同功能的幀其幀長(zhǎng)不同,例如數(shù)據(jù)幀因有幀體部分,其長(zhǎng)度比控制幀、管理幀的長(zhǎng),本文以確認(rèn)(ACK:Acknowlegement)幀為例研究CRC糾錯(cuò)的實(shí)現(xiàn)。ACK幀格式如圖3,總長(zhǎng)14個(gè)字節(jié)(112比特):幀控制域占2字節(jié),幀持續(xù)時(shí)間占2字節(jié),接收站點(diǎn)地址占6字節(jié),最后4字節(jié)為幀校驗(yàn)序列,即CRC碼,用來檢測(cè)或糾正幀中的差錯(cuò)。

圖3 ACK幀

在802.11網(wǎng)絡(luò)中,站點(diǎn)經(jīng)由無線介質(zhì)（WM:Wireless Medium）傳輸信息,將其看作為二元無記憶信道(BSC信道),在此信道中,一般錯(cuò)誤位數(shù)少的隨機(jī)錯(cuò)誤最多,采用糾正1位隨機(jī)錯(cuò)誤的糾錯(cuò)碼就能使誤碼率下降幾個(gè)數(shù)量級(jí)。國(guó)際電信聯(lián)盟電信標(biāo)準(zhǔn)分局(ITU-T:International Telecommunication Union-Telecommunication Standardization Sector)推薦使用CRC-32,即

實(shí)現(xiàn)對(duì)MAC幀的差錯(cuò)控制。

CRC是循環(huán)碼的一種,可以用多項(xiàng)式來表述錯(cuò)誤圖樣和伴隨式。CRC的伴隨式s(x)定義為接收碼字r(x)或者錯(cuò)誤圖樣e(x)除以生成多項(xiàng)式g(x)所得的余式。對(duì)于ACK幀,g(x)是n–k=32次多項(xiàng)式,所以余式的次數(shù)必小于32,最高為n–k–1=31次,二元循環(huán)碼的伴隨式s(x)共有231種不同的表達(dá)式。伴隨式包含了錯(cuò)誤圖樣的信息,故可以用伴隨式來糾錯(cuò)。在接收端把r(x)除以g(x),若余式為零即無錯(cuò)誤,否則認(rèn)為有差錯(cuò)。當(dāng)余式為某種錯(cuò)誤圖樣的伴隨式,就認(rèn)為是這個(gè)錯(cuò)誤圖樣所引起的錯(cuò)誤。由于s(x)共有2n-k種不同的表達(dá)式,而e(x)有2n種不同的表達(dá)式,所以s(x)與e(x)是一對(duì)多的映射。從最大似然譯碼準(zhǔn)則出發(fā),首先選擇重量最輕的e(x)與s(x)對(duì)應(yīng)。當(dāng)接收端求得接收多項(xiàng)式的余式（伴隨式）為s(x)時(shí),就認(rèn)為錯(cuò)誤圖樣是s(x)所對(duì)應(yīng)的重量最輕的e(x),然后將 r(x)+e(x)=c'(x),譯得所求發(fā)送碼字[3]。自然不能完全排除譯錯(cuò)的可能,但可以減少重傳的可能。

對(duì)于出現(xiàn)一位隨機(jī)差錯(cuò)的情形,錯(cuò)誤圖樣e(x)和伴隨式s(x)一一對(duì)應(yīng),本文計(jì)算了ACK幀中每一位發(fā)生差錯(cuò)與其對(duì)應(yīng)的伴隨式,如表1中所示（由于伴隨式為32位,為簡(jiǎn)便本文轉(zhuǎn)換成十六進(jìn)制表示）。

表1 ACK幀的糾錯(cuò)碼表

表1中的ri(i=0,1,2,···,110,111)對(duì) 應(yīng)中錯(cuò)誤發(fā)生的位置,即表1中與ri相應(yīng)伴隨式的值表示碼字多項(xiàng)式的系數(shù)ri對(duì)應(yīng)的比特位發(fā)生錯(cuò)誤。ACK幀為112bit,所以共有112項(xiàng)。例如當(dāng)r111出錯(cuò),即錯(cuò)誤圖樣E(x)=(100…0)(111個(gè)連續(xù)0)時(shí),相應(yīng)的伴隨式用8進(jìn)制表示為s(x)=(7CD643F7)。

糾正1bit差錯(cuò)的完整過程分為以下三步:(1)首先根據(jù)接收幀的碼字多項(xiàng)式c(x)求出其伴隨式s(x) ,如果s(x)=0,表示幀在傳輸過程中沒有出錯(cuò),不需要進(jìn)行糾錯(cuò)；如果s(x)≠0,則表示幀在傳輸中出現(xiàn)錯(cuò)誤；(2)當(dāng)s(x)≠0時(shí),根據(jù)所求伴隨式s(x)的具體值查表1,找到對(duì)應(yīng)的錯(cuò)誤圖樣ri,確定錯(cuò)誤比特的位置；(3)糾正錯(cuò)誤,即在差錯(cuò)位加1。糾錯(cuò)完成后得到正確的幀。

在802.11網(wǎng)絡(luò)的信息傳送過程中,如果發(fā)送的ACK幀前10字節(jié)是(1D0200808F24D0724)后4字節(jié)是差錯(cuò)控制碼。用上面的方法計(jì)算得出CRC碼的結(jié)果是(7531337C),那么發(fā)送的ACK幀就是(1D0200808F24D07247531337C)。

如果在傳輸過程中由于信道干擾,接收端收到的幀是(9D0200808F24D07247531337C),顯然第1字節(jié)的第1bit發(fā)生了差錯(cuò)。糾錯(cuò)過程如下:(1)首先計(jì)算其伴隨式s(x)=r(x) mod g(x),即 s(x)=(7CD643F7)≠0,所以判斷信息幀在傳輸中出現(xiàn)錯(cuò)誤；(2)進(jìn)一步找出錯(cuò)誤比特的位置。根據(jù)s(x)=(7CD643F7)查表1,在表1中查到與伴隨式s(x)=(7CD643F7)對(duì)應(yīng)的錯(cuò)誤圖樣是r111,即第一位發(fā)生錯(cuò)誤；(3)糾正錯(cuò)誤的方法是在錯(cuò)誤比特位加1,即r111由1變?yōu)?,得到正確的幀信息。

4 結(jié)論

文章用查表法對(duì)單比特錯(cuò)誤進(jìn)行糾正的方法簡(jiǎn)單直觀。接收端通過糾正單比特的錯(cuò)誤,可以提高信息傳輸?shù)目煽啃?。由于MAC幀中數(shù)據(jù)幀的長(zhǎng)度較長(zhǎng),本文以ACK幀為例給出了利用CRC糾正MAC幀中錯(cuò)誤的方法。當(dāng)傳輸過程中發(fā)生多位的差錯(cuò)時(shí),計(jì)算表的復(fù)雜度就更高,甚至不能完全糾正錯(cuò)誤,期望未來對(duì)CRC糾錯(cuò)的研究會(huì)更深入。

[1]IEEE Standard802.11TM - 2016“Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements Part 11: Wireless LAN Medium Access Control(MAC) and Physical Layer (PHY) Specifications”, IEEE D3 , 2012 :C1-1184.

[2]譚明新.現(xiàn)代交換技術(shù)實(shí)用教程[M].北京:電子工業(yè)出版社,2012.

[3]傅祖蕓.信息論-基礎(chǔ)理論與應(yīng)用(第二版)[M].北京:電子工業(yè)出版社,2007.