IEEE802.11無線局域網(wǎng)中糾錯的實現(xiàn)

余 網(wǎng) 譚明新

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

1 引言

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

圖1 MAC幀格式

2 CRC碼的生成方法

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

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

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

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

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

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

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

即C(x)=(1100011100)

3 MAC幀糾錯的實現(xiàn)

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

圖3 ACK幀

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

實現(xiàn)對MAC幀的差錯控制。

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

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

表1 ACK幀的糾錯碼表

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

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

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

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

4 結(jié)論

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

[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ù)實用教程[M].北京:電子工業(yè)出版社,2012.

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