[理學(xué)]計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)第3章-文庫吧
2024-12-20 18:09 本頁面
【正文】 輸，必須在差錯檢測技術(shù)的基礎(chǔ)上，增加定時(shí)器、幀編號、確認(rèn)和重傳機(jī)制。 ? 目前因特網(wǎng)上廣泛使用的數(shù)據(jù)鏈路層協(xié)議已不再使用確認(rèn)和重傳機(jī)制了，即不提供向上的可靠傳輸服務(wù)了。 尋址 ? 必須保證每一幀都能送到正確的目的站，接收方也應(yīng)知道發(fā)送方是哪個站。 差錯控制編碼技術(shù) ? 奇偶校驗(yàn)碼 ? 循環(huán)冗余校驗(yàn)碼 ? 海明碼 糾錯碼（ ErrorCorrecting Code）和檢錯碼（ ErrorDetecting Code）是實(shí)現(xiàn)差錯檢測和糾正的兩種不同的差錯控制編碼技術(shù)。 糾錯碼（ ErrorCorrecting Code）和檢錯碼各有優(yōu)缺點(diǎn)。 比較常見的檢錯碼主要有奇偶校驗(yàn)碼和循環(huán)冗余校驗(yàn)碼，常見的糾錯碼主要有海明碼、正反碼等。 奇偶校驗(yàn)碼 ? 奇偶校驗(yàn)碼 ? 是通過增加冗余位來使得碼字中“ 1”的個數(shù)為奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）的編碼方法。 ? 奇偶校驗(yàn)碼可分為垂直、水平、水平垂直奇偶校驗(yàn)等幾種方式 垂直偶校驗(yàn) 水平偶校驗(yàn) 水平垂直偶校驗(yàn) 循環(huán)冗余校驗(yàn)碼 （ Cyclic Redundancy Check, CRC） ? CRC又叫多項(xiàng)式編碼（ polynomial code） ? 基本思想是：將比特串看成是系數(shù)為 0或 1的多項(xiàng)式。一個 k比特構(gòu)成的幀看作是一個 k1次多項(xiàng)式系數(shù)列表，該多項(xiàng)式共有 k項(xiàng)，從 xk1到 x0，這個多項(xiàng)式的最高階為 k1。 ? 如比特串 110011共有 6位，對應(yīng)一個共有 6項(xiàng)的多項(xiàng)式，其系數(shù)分別為 0、 0、 1和 1，即 x5+x4+x+1（ 1*x5+ 1*x4+ 0*x3+ 0*x2+ 1*x1+ 1*x0）。 ? 多項(xiàng)式的算術(shù)運(yùn)算采用模 2運(yùn)算法則。按照它的運(yùn)算法則，加法不進(jìn)位，減法不借位，加法和減法兩者都與異或運(yùn)算相同，因而計(jì)算結(jié)果相同。 ? CRC具有較強(qiáng)的檢錯能力，可以檢測出所有的奇數(shù)位錯、雙比特錯、小于等于校驗(yàn)和長度的突發(fā)錯。 CRC進(jìn)行編碼和校驗(yàn)的原理 ? (1) 發(fā)送方和接收方事先約定一個生成多項(xiàng)式 G(x)，生成多項(xiàng)式的最高位和最低位必須是 1。 ? (2) 發(fā)送端根據(jù)生成多項(xiàng)式 G(x)去計(jì)算要附加在信息幀尾部的冗余位（校驗(yàn)和， Checksum）。計(jì)算校驗(yàn)和的算法如下。 ? ① 假設(shè)信息幀的比特?cái)?shù)為 k位，對應(yīng)的多項(xiàng)式為 K(x)， G(x)為 r階。在信息幀的低位端加上 r個 0，此時(shí)信息幀的比特?cái)?shù)變?yōu)?k+r位，對應(yīng)的多項(xiàng)式為 xrK(x)。 ? ② 按模 2除法，用對應(yīng)于 G(x)的比特串去除對應(yīng)于 xrK(x)的比特串，從而得到一個小于等于 r位的余數(shù)。這個余數(shù)便可作為校驗(yàn)和。 ? (3) 將校驗(yàn)和附加在 k位信息幀尾部，組成一個新的幀，由發(fā)送端發(fā)送給接收端。假設(shè)這個新的幀對應(yīng)的多項(xiàng)式為 T(x)，其顯然能被 G(x)除盡。因?yàn)檫@個新的幀的多項(xiàng)式 T(x)所對應(yīng)的比特串可以看作是由多項(xiàng)式 xrK(x)對應(yīng)的比特串減去余數(shù)而得到的。 ? (4) 當(dāng)接收方收到帶有校驗(yàn)和的幀時(shí)，用 G(x)去除它，如果余數(shù)不為 0，則說明傳輸過程中出現(xiàn)了錯誤；如果余數(shù)為 0，則認(rèn)為傳輸無差錯。 發(fā)送端生成帶校驗(yàn)和的 CRC幀的過程舉例 ? 信息幀 ? 1101011011 ? 生成多項(xiàng)式 ? x4+ x+1 海明碼 ? 海明碼是由 1950年首次提出的，是一種可以糾正一比特錯的編碼。 ? 簡單的奇偶校驗(yàn)中的一個重要的結(jié)論 ? 信息位為 k=n1位 an1an2…a 1，加上一個偶校驗(yàn)位a0，構(gòu)成一個 n位的碼字 an1an2…a 1a0。在接收端校驗(yàn)時(shí)，可按關(guān)系式： S0=an1+an2+…+a 1+a0（模2運(yùn)算）來計(jì)算，若 S0=0，則認(rèn)為無錯；若 S0=1，則肯定有錯。上面關(guān)系式稱為監(jiān)督關(guān)系式， S0稱為校正因子。 海明碼原理推導(dǎo) ? 對上面結(jié)論的分析 ? 在上面偶校驗(yàn)情況下，只有一個監(jiān)督關(guān)系式，一個校正因子，其取值只有 0或 1兩種可能，分別代表了無錯和有錯兩種情況，但卻不能指出差錯所在的位置。不難設(shè)想，如果增加冗余位，讓每個冗余位分別與信息中的某些位構(gòu)成一個偶校驗(yàn)關(guān)系，則就會相應(yīng)地增加監(jiān)督關(guān)系式和校正因子，就能區(qū)分更多的情況。 ? 不難推出，信息位為 k位，增加 r位冗余位，構(gòu)成 n=k+r位碼字。若希望用 r個監(jiān)督關(guān)系式產(chǎn)生的 r個校正因子來區(qū)分無錯和在碼字中的 n個不同位置的 1位錯，則要求： 2r≥n+1或2r≥k+r+1 k=4時(shí)，海明碼產(chǎn)生基本原理示例 ? 構(gòu)造 S2S1S0取值與錯碼位置的對應(yīng)關(guān)系 也可以規(guī)定成另外的對應(yīng)關(guān)系，這并不影響討論的一般性 ? 根據(jù)上表推出監(jiān)督關(guān)系式 ? 令校正因子都等于零，代入已知信息位，計(jì)算出冗余位 K=4時(shí)由信息位算得的冗余位 ? 基于上面構(gòu)造的海明碼，可得到各種信息位與
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1