ErrorDetection线上资源.PDF

第五章 錯誤偵測 (Error Detection) 5.0 導論 本章主要內容是討論網路傳輸中錯誤的偵測與修正的機制 5.1 錯誤的形式 錯誤的類型： • 單一位元 (single-bit error) 錯誤：這種錯誤會把0 換成 1 或者 1換成0 。 • 集體錯誤 (burst error) 的情況，許多位元會被改 變。 圖5.1 錯誤類型 圖5.2 單一位元錯誤 圖5.3 長度為五的集體錯誤 5.2 偵測 • 為了偵測一個錯誤，可以把一組較短的bits 附加 在每一筆料單位的末端。這種技術叫作冗餘 (redundancy) • 三種類型的冗餘檢查被用於區域網路：垂直冗餘 檢查 (vertical redundancy checkVRC) ，縱向冗 餘檢查 (longitudinal redundancy check, LRC) ， 和循環冗餘檢查 (cyclical redundancy check, CRC) 圖5.4 冗餘 圖5.5 偵測方法 5.3 垂直冗餘檢查 • 垂直冗餘檢查 (Vertical Redundancy Check, VRC) ，通常稱為同位檢查(parity check) 。在這 種技術中，多餘的一個位元，稱為同位元 (parity bit) ，被附加到每個資料單位，因此在該單位中1 的總數（包括這個同位元）會變成偶數個。 圖5.6 偶數同位元垂直冗餘檢查觀念 範例 1 • 假設發送端想要送“world”這個字。在ASCII （參 見附錄一）中，這五個字元被編碼成 == 1110111 1101111 1110010 1101100 w o r l d • 開始的四個字元，每一個都有偶數的1 ，所以同 位位元是0 。但是，最後的字元(.d.)有三個 1 （奇 數），所以同位位元是 1 ，讓1 的總數變成偶數 範例 2 • 在之前的範例中，現在假設“world”這個字，在沒 有遭受破壞的情況下被接收端收到了。 =0110111101101100 • 接收端計算每一個字元中的1 ，並且得出偶數值 ( 6 , 6 , 4 , 4 , 4 ) 。這個資料應該被接受 範例 3 • 在之前的範例中，現在假設“world”這個字，由接 收端收到了，但是在傳輸期間遭受破壞。 ==0110111101101100 接收端計算每一個字元中的1 ，並且得出偶數和 奇數值 ( 7 , 6 , 5 , 4 , 4 ) 。接收端知道這個資料 已經遭受破壞，它會丟棄資料，並且要求重送。 5.4 縱向冗餘檢查 • 在縱向冗餘檢查 (Longitudinal Redundancy Check, LRC) 中，一個區塊的位元被組織在一個 列表（行和列）。 圖 5.7 縱向冗餘檢查 範例 4 • 假設下面的區塊被送出 ===0011100111100111 (LRC) 不過，它碰上長度為8的突發性雜訊，而且某些位元被損毀 === 101000 111101110110101010