|
|
|
3-5 錯誤偵出
3-5-1 錯誤控制簡介 鏈路層將訊框傳送給實體層，實體層再將訊框轉換成連續的訊號後發送到傳輸媒介。訊號在傳輸媒介上容易受環境因素所影響，如電磁波干擾或接續端子接續不良等，而發生訊號串列中某些訊號錯誤或遺失；接收端在接收完訊號後必須有能力去偵測它，到底所收到的資料是否和傳送端所傳送的資料相同。如果要讓接收端有偵測錯誤的能力，則傳送端必須在資料傳送之前，針對傳送資料做一些必要的處理和控制；而接收端在接收完資料之後，則依照雙方的協議來偵測傳輸資料是否有發生錯誤。萬一資料在傳送之中發生錯誤，接收端如何要求傳送端重新傳送？傳送端接到錯誤訊息如何重新傳送？以上所有針對如何保證資料的完整性之措施，稱為『錯誤控制』（Error Control）。錯誤控制包含兩大基本技術：
雖然在通訊協定裡，各層次中的通訊軟體大部分都有提供錯誤控制的管理，但以鏈路層對錯誤控制的管理最為重要，因為它和實體傳輸環境有最直接的關係，錯誤發生的機率最大。所以在鏈路層中所用到的錯誤偵測方法最為嚴謹。但要注意，並非所有錯誤偵測方法都能百分之一百偵測出錯誤，我們只能說較嚴謹的錯誤偵測方法，所能偵測出錯誤的『或然率』（Probability）較高。當然愈嚴謹的錯誤偵測方法愈理想，但有時我們為了考慮傳輸效率而不得不放棄它，改採折衷的錯誤偵測方法。資料訊框的長短對於資料錯誤偵出的或然率有絕對的影響，訊框愈長偵測能力愈低，相對的訊框愈短偵測能力愈高。但訊框長度直接影響傳輸效率，愈長傳輸效率愈高；愈短傳輸效率就愈低，因此如何找到雙方的平衡點，也是制定通訊協定的頭痛問題。既然沒有一種錯誤偵測方法可以百分之一百的偵出錯誤，因此接收端在偵測資料後沒有發現錯誤並不能保證沒有錯誤，只能說『沒有發現錯誤』（No error detected），而不能說『沒有錯誤發生』（Error Free）。 一般在資料傳輸方面，對於資料錯誤控制的方法，除了錯誤偵出外，還有『錯誤修正』（Error Correction）方法。不論錯誤偵出或錯誤修正，都必須產生一個『多餘碼』（Redundancy Code）來保護原始資料，它在錯誤偵測方法中稱為『錯誤偵測碼』（Error-Detecting Code, EDC），而在錯誤修正方法中稱為『錯誤修正碼』（Error-Correcting Code, ECC）。 在有錯誤控制的情況下，假使原來資料為 n 個位元，所產生的多餘碼為 k個位元，則要傳輸整筆資料時就必須傳送 t = (n + k) 個位元。但錯誤修正或偵測碼只用來防止資料錯誤，並非真正的資料，因此稱為『多餘碼』。一般而言，多餘碼愈長，則錯誤控制能力（偵出或修正）愈強，但相對的也會減低傳輸效益，因為多餘碼浪費許多傳送的時間。 如採用錯誤修正方法，為了要使資料具有錯誤修正的能力，在資料傳輸中必須加入許多錯誤修正碼。一般來說，傳輸8位元資料中必須要有5位元的錯誤修正碼，才能偵測2位元的錯誤、和修正1位元的錯誤（One-bit correction two-bit detection）。但整體傳輸效率只有8/13（8/(5+8)），顯然非常的低。它主要應用於記憶體和磁碟機之間近距離傳輸的錯誤控制。在範圍較廣的網路上，傳輸效率會影響到整個網路的效益，因此，一般網路只採用錯誤偵出，而不輕易採用錯誤修正（Bluetooth 便採用此法）。以下介紹三種常用錯誤偵測的方法：
通訊協定各個層次都有流量控制及錯誤偵出的機制，所使用的偵錯方法也都大同小異。除了鏈路層因為牽涉到實體傳輸媒介（較容易出錯），而採用循環多餘碼檢查法外，其它層次大多採用檢查集檢查法。我們在這裡介紹各種方法，以後介紹其他層次裡就不再介紹錯誤檢查的基本原理。 3-5-2 同位元檢查 若要進行『同位元檢查』（Parity Check），傳送端和接收端在傳送資料之前，雙方必須協議出傳送資料（含檢查用的外加碼）轉化為二進位之後，位元值 "1" 的個數是偶數或是奇數。如協議為偶數個 1，則稱為『偶同位元檢查』（Even Parity Check）；奇數個1就稱為『奇同位元檢查』（Odd Parity Check）。為了要使整個資料固定為偶數個或奇數個 1，就必須加入1 個位元的多餘碼，稱為『同位位元』（Parity Bit）。如果資料位元是 n 個位元，則整個傳輸資料長度 m =（n+1）。如雙方傳送協議採用偶同位元檢查，傳送端必須計算每一筆資料中 1 的數目，再決定同位元是 0 或 1，使 m 位元中有偶數個 1。接收端接收到資料後計算是否有偶數個 1，如果是偶數個 1，則表示沒有發現錯誤，再將同位位元（Parity bit）拋棄；如果計算出是奇數個 1，那表示資料在傳送中已發生錯誤。同位位元的計算方式如下：
同樣的，如雙方協議使用奇同位元檢查，接收端收到資料後，便計算資料中 1 的數量。如果 1 的數量是奇數，則表示傳送資料沒有發現錯誤，否則（數量是偶數）表示傳送當中已發生錯誤。如果資料長度太長，同位元檢查的偵測錯誤能力就較低，因為位元串列中只要有偶數個位元發生變化（0→1、1→0），同位元檢查就找不出錯誤（位元是 1 的總數是偶數或奇數沒有改變）。因此，每一筆資料不可以太長，每 5 ~ 9 個位元產生一個同位位元，其偵測能力較高。同位位元的產生與偵測可以用硬體線路直接運算，不必用軟體額外來計算，也不會浪費電腦處理時間，一般應用在電腦內記憶體偵測或交談式的傳輸線上（RS-232C）。 3-5-3 檢查集檢查 『檢查集檢查』（Check-Sum check, CS）是一種以加法為基礎的檢查機制。傳送端欲將資料傳送前，將資料以每個字元（16 位元或32 位元）為單位，連續累加起來得到一個字元（16 位元、32位元、或其他長度），稱之為『檢查集』（Check-Sum, CS），也就是多餘檢查碼。如圖 3-15 所示，檢查集（CS）會連同資料（M）一齊（T = M + CS）傳送給接收端。接收端接收到資料後將資料（M'）以同樣的方法（字元長度）連續累加， CS'，如果 CS = CS' 則沒有發現錯誤；否則表示資料已發生錯誤。
圖 3-15 檢查集檢查運作原理 檢查集不能夠利用硬體線路來建構。通訊軟體必須每次針對要傳送的資料方塊（Block）做運算來計算出檢查集，比較浪費時間。一般應用在較高層通訊協定（如TCP/IP）或備份（backup）檔案的錯誤偵出使用。 3-5-4 循環多餘碼檢查 『循環多餘碼檢查』（Cyclic Redundancy Check，CRC）是利用除法（Modulo 2 運算）來做錯誤的檢出。其原理如圖 3-16 所示，其中通訊兩端必須事先協調好某一個除數（Q，最好為質數），傳送端傳送資料之前先將訊框（M）除以除數（Modulo 2 運算），得到一個餘數（FCS），再將餘數附加在訊框（M）的後端一起（T = M + FCS）傳送給接收端。接收端接收資料（M'）後，也用同樣的除數（Q）除，得到另一個餘數（FCS'）。如果 FCS' 和 T 後面的 FCS 相同（FCS = FCS'）即代表沒有發現錯誤；否則（FCS <> FCS'）已發生錯誤。
圖 3-16 循環多餘碼檢查運作原理 其實在 CRC 檢查運算裡，並不是利用餘數的比較來判斷是否有錯誤發生。其運算原理如下：一個 n 個位元的傳送資料經過 Modulo 2 的除法運算（除以除數 Q）後，產生的 k個位元的餘數，稱之為『訊框檢查序列』（Frame Check Sequence，FCS），而將訊框檢查序列附在傳輸資料後面即成為傳送訊框，傳送訊框為 n + k 個位元長的訊息（T），而且正好可以被預先決定好的除數（Q）所整除。然後接收端便利用該除數（Q）來除收到的訊框（T'），若沒有餘數產生，即表示沒有發現錯誤。對於傳送端的 CRC 檢查碼的產生除法器（產生 FCS），以及接收端判斷是否有錯誤發生的除法器（M' 是否可以整除？），兩者都是相同的除法原理。 以下我們用 Modulo 2（模式 2）運算來推演 CRC 除法原理，假設參數如下：【備註：Modulo 2 運算為 XOR 計算，加法與減法都沒有進位和借位的情況】
如果推演出：接收端所收到的訊框（T'）和傳送訊框（T）相同，則 T' 可以被 P 整除，也表示沒有錯誤發生。推演如下： (1) 在二進位算術中，向左移一位相當於乘以2，向左移 5個位元相當於乘以25，因此對整個傳送訊框（T）內容的表示： T = 2n M + F (2) 傳送訊框T是藉由訊息M向左移n 個位元，並且在後面補上n個0。再加上訊框檢查序列F，便可串接M和F以產生T。為了產生FCS，我們先用2n M除以除數 Q： （2n M）/ Q = K + R / Q (3) 除數Q的選擇儘可能是二進位數中的質數，產生餘數的機率最大。由上式運算中，我們得到結果是商 K 和餘數 R。餘數 R 會比除數 Q 少一個位元，我們就將這個餘數作為FCS。則整個傳送訊框為： T = 2n M + R (4) 如果接收端接收到的訊框沒有錯誤發生，則 T / Q應該沒有餘數。這條件如何產生？我們來做驗證： T / Q = （2n M + R）/ Q 則 T / Q = 2n M / Q + R / Q T / Q = K + R / Q + R / Q = K (5) 由於 Modulo 2運算中，任何相同的數相加是等於零（XOR 運算）。所以上式中 T 可以被Q 整除，而不會產生非零的餘數。因此對於 FCS的產生非常容易，只要將2n M除以 Q，所產生的餘數作為FCS 便可以，再將 2n M 與 FCS 組合成 T。在接收端方面只要用 T 除以 Q，如果沒有餘數，即表示沒有錯誤發生。 (6) 讓我們用一個簡單的例子來說明FCS的產生和錯誤檢查：
訊息 M = 1011100101 （10個位元） 除數 Q = 101011 （6個位元） 欲計算出5個位元的FCS。
CRC除法原理是利用 Modulo 2 的運算原理推論出來。而 Modulo 2 的運算類似於二進位的「互斥或」閘（XOR Gate）運算（沒有進位的加法、沒有借位的減法）。因此，我們可以利用一個含有 XOR 閘和位移暫存器（Shift Register）來設計CRC除法器。 假設：傳送訊框M(X)是一個可變的二進位函數（多項式表示），而除數 Q(X)為固定函數。因此，我們只要設計出 Q(X) 的CRC除法器即可。CRC除法器的邏輯線路設計方式如下： (1) 除法器的線路中含有n個暫存器，相當於餘數 R(X) 的長度。 (2) 最多含有 n 個互斥或閘。 (3) 在除數Q(X) 位置是1的位置，便接有互斥或閘。 假設： 訊息 M = 1010001110 M(X) = X9 + X7 + X3 + X2 + X 除數 Q = 110101（長度為 6） Q(X) = X5 + X4 + X2 + 1 餘數 R(X) 長度為 5
圖 3-17 CRC 除法器範例 圖3-17 為Q(X) = X5 + X4 + X2 +1的CRC除法器之邏輯線路設計圖。此運作方式由清除移位暫存器開始，然後訊息由最高位之位元以一次一個位元的方式進入暫存器，以共同脈衝（Clock）來同步移位。由於要等到第一個被除數之位元到達暫存器的最高位元的端點才會有回饋訊號產生，因此前面的五個位元只有移位而已。當一個1的位元到達暫存器最左端（R(4)）時，從此以後 R(3) 、R(1) 的輸出及輸入位元都會在下一次移位時間和 R(4) 輸出作 XOR 的運算。最前端 R(4)（X5）的輸出會迴旋到輸入端作處理，如果訊息不斷的進入，整個線路的循環就不停止，因此稱之為『循環多餘碼除法器』（CRC 除法器）。使用該技術的錯誤偵出法也稱為『循環多餘碼檢查』。 在圖中，當訊息（1010001110）全部進入除法器後，暫存器上所儲存的值（11010）便是餘數 R(X)，亦是 FCS 的值。又當 0 進入除法器時，相當於所有暫存器的內容往左移一位。因此，我們在訊息後面補上 5 個 0，當 5 個時脈後，FCS 的值就從 R(4) 暫存器上輸出，也將其放入訊框中的FCS欄位內。 圖3-18 是傳送端的CRC除法器。當在傳送資料時，多工器在 0 的位置，表示資料一方面傳送到網路上，一方面進入除法器以產生FCS。當資料傳送完後，繼續送入補 0 的位元時，將多工器位置切換到 1 的位置，繼續傳送 FCS 的位元。因此，FCS 欄位就緊接著訊息 M 之後。不論接收端或傳送端的除法器都可架設硬體線路來運算，而且可以依照資料的輸入或輸出，一個位元接一個位元的進入除法器。也可看出 CRC 除法器完全不會佔用傳送時間。而且傳送端的 FCS 產生和接收端錯誤檢出之 CRC 除法器都是相同，因此，我們只要製作一個 CRC 除法器即可，一般都將其製造在網路卡上。
圖 3-18 CRC 檢查碼的硬體架構 由以上的推演我們可以瞭解，所使用的除數 Q(X) 對錯誤的檢出能力有很大關係。尤其，所欲傳送的訊框是可變長度（限制在某長度範圍以內），訊框愈長錯誤檢出能力就愈低。唯一的方法就是增加除數的長度，但相對所產生的多餘碼（FCS）也就愈長，傳輸效率也會降低。另外，在某固定長度的除數應該是什麼？當然所選的除數必須儘可能會產生餘數。因此，除數最好是選擇質數（二進位的質數），最有可能產生餘數。經過許多數學家的推演，有下列幾種通訊協定上較常使用的 CRC 碼。一般區域網路所使用的是能產生 32 位元長餘數的 CRC-32。
|
翻轉工作室：粘添壽
電腦網路與連結技術：
翻轉電子書系列： |
