【正文】 碼 (CRC碼 )， 并將添加二進制位串后所形成的二進制碼字看成是一個多項式 F(X)的系數序列 ， 所添加的二進制位串要使得所形成的多項式 F(X)能被另一個稱為生成多項式的 G(X)除盡 。 當數據鏈路將這個二進制碼字發(fā)送到接收方后 ， 接收方同樣將其看成是一個多項式的系數序列 ， 并用相同的生成多項式 G(X)來除該多項式 。 若余數為零 ， 則傳輸無差錯；否則 ， 傳輸有差錯 。 第 2章 數據通信基礎 顯然 ， 循環(huán)冗余校驗的首要問題是確定所添加的二進制位串 ， 即 CRC碼 。 這里介紹 CRC碼的生成方法： (1) 選定一個最高階為 k的生成多項式 G(X)，如X5+X4+X2+1，該生成多項式的最高階為 5。注意生成多項式的最高位和最低位系數必須為 1。 第 2章 數據通信基礎 (2) 在要被檢測的二進制位串尾部添加 k個 0。 k為生成多項式的最高階數 ， 若要檢測的二進制位串為 n位 ，那么 ， 在添加 k個 0后 ， 所形成的碼字為 (n+k)位 。 如要檢測的二進制位串為 1010001101， 若采用 (1)中的生成多項式 X5+X4+X2+1， 則在該二進制位串的尾部添加 5個 0后 ， 所形成的碼字為 101000110100000。 第 2章 數據通信基礎 (3) 將添加 k個 0后所形成的 (n+k)位碼字看成是一個(n+k－ 1)階多項式 F39。?(X)的系數序列 。 如果將 (2)中所形成的碼字看成是 (10+5－ 1)階多項式的系數序列時 ， 那么 ， 對應的多項式形式為 F39。?(X)=1 X14+0 X13+1 X12+0 X11+0 X10+0 X9+1 X8+1 X7+0 X6+1 X5 +0 X4+0 X3+0 X2+0 X1+0 X0 第 2章 數據通信基礎 (4) 用生成多項式 G(X)按模 2除法去除 F39。 (X)，得到商和余數，所得余數即為 CRC碼。若從 F39。 (X)中減去余數后再被 G(X)除，則結果的余數必將為 0。由于是按模2運算，加一個數和減一個數的結果是相同的，即F(X)=F39。 (X)+余數 = F39。 (X)－余數，且 F(X)/G(X)的余數為零。因此，可將所得的余數作為校驗和 (CRC碼 )。 例如，已知要傳送的信息為 1010001101，G(X)=X5+X4+X2+1，計算校驗和的過程和結果如下： 第 2章 數據通信基礎 故 CRC=01110。 第 2章 數據通信基礎 由此 ， 最終要發(fā)送的碼字為 101000110101110。 在接收端用同樣的生成多項式 G(X)去除所接收到的帶校驗和 CRC碼的碼字 。 根據余數是否為 0， 即可確定數據傳輸過程中是否有差錯 。 若傳輸過程有差錯，則所接收到的結果P(X)=F(X)+E(X)，其中 E(X)是由傳輸差錯引起的。若用 G(X)除所接收到的結果為 G ( X )E ( X )G ( X )F ( X )G ( X )E ( X )F ( X )G ( X )P ( X ) ????第 2章 數據通信基礎 由于 F(X)/G(X)的余數為零 ， 所以 ， P(X)/G(X)所得余數為 E(X)/G(X)的余數 。 這樣 ， 除了 E(X)為 G(X)的整數倍外 ， 其他差錯都能檢測出來 。 由此可見 ， 循環(huán)冗余檢驗碼的檢錯能力是非常強的 ， 且與所使用的生成多項式有關 。 總的說來 ， 若 G(x)選擇得當 ， CRC是非常有效的 。特別地 ， 必須選擇 G(x)， 使得 x 是它的因子而 X+1則不是 。 此時 ， 若 G(X)為產生 r個校驗位的多項式 ， 則 CRC可檢測以下錯誤： 第 2章 數據通信基礎 所有長度為 r(r?G(x)的次數 )的突發(fā)錯誤；所有影響奇數個比特位的任意長度的突發(fā)錯誤；以 ( 2r－ 1－ 1 ) / 2r－ 1的概率檢測出所有長度為 r+ 1 的突發(fā)錯誤 。 以 ( 2r－ 1 ) / 2r的概率檢測出所有長度 r+ 1的突發(fā)錯誤 ((CRC－ 32)多項式能以 (232－ 1)?/?232的概率檢測出所有長度33 的突發(fā)錯誤 ， 這等效于 %的準確率 )。 第 2章 數據通信基礎 國際上的一些標準化組織已給出了幾個建議使用的生成多項式。普遍采用的 G(X)有 16位 CRC碼和 32位CRC碼，它們分別為 16位： CRC＝ X16+X12+ X5+1 或 CRC＝ X16+X15+ X5+1 32位： CRC＝ X32+X26+ X23+ X22+X6+ X12+ X11+X10+ X8+ X7+X5+ X4+X2+X+1 CRC碼主要用于數據鏈路層控制協(xié)議中 ， 廣域網的數據鏈路層協(xié)議通常采用 16位 CRC碼 ， 局域網多采用32位 CRC碼 。 第 2章 數據通信基礎 值得注意的是 ， 在計算機網絡體系結構中 ， 數據鏈路層的 CRC只保證物理層上各位的正確性 ， 這是因為CRC總是在發(fā)送端的數據鏈路層計算 ， 所以當幀通過網橋或交換機在另一個端口上重新發(fā)送時要重新計算CRC。 因此 ， 在轉換設備的存儲轉發(fā)內存中 ， 數據可能會遭到破壞 。 要確保數據正確 ， 必須在更高層協(xié)議中進行數據檢查 。 對于數據鏈路層中其他的檢錯和糾錯都有類似問題 。 第 2章 數據通信基礎 循環(huán)冗余校驗的計算方法看起來比較復雜，但在實際中是采用硬件電路實現(xiàn)的。硬件電路由移位寄存器和模 2加法器兩部分組成，所用移位寄存器和模 2加法器的數量取決于生成多項式。圖 210給出了一個編碼器的典型電路。該電路所對應的生成多項式為X5+X4+X2+1。 第 2章 數據通信基礎 A B C D E 進入數據10 10 00 11 01 00 00 0圖 210 編碼器典型電路 第 2章 數據通信基礎 根據模 2除法運算的規(guī)則 ， 可以得出該運算的特點是： (1) 當余數最高位為 “ 1”時 ， 該次除的商為 “ 1”， 被除數 (余數 )要減去除數 G(X)。 當余數最高位為 “ 0”時 ，該次除的商為 “ 0”， 被除數不變 (即不需進行減法操作 )。 (2) 作減法操作時 ， 除數為 “ 1”的位 (即生成多項式為“ 1”的位 )， 被除數要變反 (該位與 “ 1”作異或操作 )，除數為 “ 0”的位 ， 被除數不變 。 第 2章 數據通信基礎 (3) 除數 (生成多項式 )階為 n， 則余數有 n位 。 由上述特點 ， 可用 n位移位寄存器存放每次運算后所得的余數 ， 由余數最高位控制每一位的運算 (相應于上述第一個特點 )， 并在余數 (移位 )寄存器中 ， 凡對應除數為 1的位前面加一異或運算器 (相應于上述第二個特點 )， 從而形成了求余數電路 ， 運算完畢后 ， 移位寄存器中存放的是最后所得的余數 。 第 2章 數據通信基礎 表 22列出了利用圖 210電路計算上述示例的校驗和過程中，每次向電路送入一位數據運算后，各移位寄存器的變化情況。運算之前，移位寄存器全部清零。以后，發(fā)送數據從高位開始逐位進入電路作求余運算。當 A值為零時， A、 B、 C、 D、 E各位分別向左移一位，最高位丟掉，將新的一位數據移入 E中。當 A值為“ 1”時， B、 D分別與“ 1”作“異或”運算后向左移一位，C、 E也向左移一位，新進入數據與“ 1”作“異或”后進入 E。這樣重復進行，直到數據全部進入為止 (包括附加的 r個“ 0”，在表 22中即為最后列的后 5個“ 0”)。 第 2章 數據通信基礎 表 22 生成多項式為 X5+ X4+X2+1的 CRC碼校驗和計算過程 步數 ABCDE 進入數據 0 00000 1 00001 1 2 00010 0 3 00101 1 4 01010 0 5 10100 0 6 11101 0 7 01110 1 第 2章 數據通信基礎 步數 ABCDE 進入數據 8 11101 1 9 01111 0 10 11111 1 11 01011 0 12 10110 0 13 11001 0 14 00111 0 15 01110 0 第 2章 數據通信基礎 思考題與習題 21 什么是數字通信 ？ 什么是數據通信 ？ 在數據通信中采用模擬傳輸和數字傳輸各有什么優(yōu)缺點 ？ 22 模擬傳輸系統(tǒng)與數字傳輸系統(tǒng)的主要特點各是什么 ？ 23 基帶信號與寬帶信號的傳輸各有什么特點 ？ 24 奈奎斯特公式與香農公式在數據通信中的意義是什么 ？ 第 2章 數據通信基礎 25 電視頻道的帶寬為 6 MHz， 假定沒有熱噪聲 ，如果數字信號取 8種離散值 ， 那么可獲得的最大數據速率是多少 ？ 26 設信道帶寬 3 kHz， 信噪比為 20 dB， 若傳送二進制信號 ， 則可達到的最大數據速率是多少 ？ 27 在相隔 1000 km的兩地間用以下兩種方式傳送 3 kb的數據：一種是通過電纜以 kb/s的速率傳送；另一種是通過衛(wèi)星道以 50 kb/s的速率傳送 ， 問哪種方式需要的時間較短 ？ 第 2章 數據通信基礎 28 56 kb/s的調制解調器是否已突破了香農的信道極限傳輸速率 ？ 這種調制解調器的使用條件是怎樣的 ？ 29 畫出比特流 0001110101的曼徹斯特編碼的波形圖和差分曼徹斯特編碼的波形圖 。 210 設碼元速率為 1600 b/s， 采用 8相 PSK調制 ， 其數據速率是多少 ？ 第 2章 數據通信基礎 211 所謂“二相相對相移鍵控 (2DPSK)”，是利用前后碼元之間的相對相位變化來表示二進制數據的。例如傳送“ 1”時載波相位相對于前一碼元的相移為 π；傳送“ 0”時載波相位相對于前一碼元的相移為 0。假設載波頻率為 2400?Hz，碼元速率 1200?b/s。試畫出數據序列“ 1010011100”的 (2DPSK)波形圖。 第 2章 數據通信基礎 212 在異步通信中 ， 每個字符包含 1位起始位 、 7位ASCII碼 、 1位奇偶校驗位和 2位終止位 ， 數據傳輸速率為 100 b/s， 如果采用 4相相位調制 ， 則傳輸線路的碼元速率為多少 ？ 有效數據速率為多少 ？ 213 設采用異步傳輸 ， 1位起始位 ， 2位終止位 ， 1位奇偶位 ， 每一信號碼元 2位 ， 對于下述碼元速率 ， 分別求出相應的有效數據速率 (b/s)： (1) ?300 b/s； (2) ?600 b/s ； (3)? 1200 b/s； (4) ?4800 b/s 第 2章 數據通信基礎 214 在 T1載波中 ， 由非用戶數據引入的開銷占的百分比是多少 ？ 215 試畫出 CRC生成多項式 G(X)=X9+ X6+ X5+ X4+ X3+ 1的硬件實現(xiàn)電路框圖 。 216 利用上題的生成多項式檢驗收到的報文101010001101是否正確 。 217 已知 CRC生成多項式為 G(X)= X4+X+1， 設要傳送的碼字為 10110?(從左向右發(fā)送 )， 試計算檢驗碼 。 218 利用生成多項式 G(X)= X4+ X3+X+1，計算報文 11001010101的校驗序列。