IEEE802.11無線局域網中糾錯的實現

余 網 譚明新

（華中師范大學,湖北 武漢 430079）

1 引言

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

圖1 MAC幀格式

2 CRC碼的生成方法

CRC基本結構如圖2所示。

圖2 CRC的結構

由圖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）,所得的余數為校驗碼r(x)。最后得到完整的碼字多項式 c(x)=xn-k·m(x) +r(x)[2]。

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

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

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

(3)發送碼字多項式

即C(x)=(1100011100)

3 MAC幀糾錯的實現

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

圖3 ACK幀

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

實現對MAC幀的差錯控制。

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

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

表1 ACK幀的糾錯碼表

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

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

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

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

4 結論

文章用查表法對單比特錯誤進行糾正的方法簡單直觀。接收端通過糾正單比特的錯誤,可以提高信息傳輸的可靠性。由于MAC幀中數據幀的長度較長,本文以ACK幀為例給出了利用CRC糾正MAC幀中錯誤的方法。當傳輸過程中發生多位的差錯時,計算表的復雜度就更高,甚至不能完全糾正錯誤,期望未來對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]譚明新.現代交換技術實用教程[M].北京:電子工業出版社,2012.

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