1第三章數(shù)據(jù)鏈路層曹袖（xiucao@）2015.10第三章數(shù)據(jù)鏈路層2數(shù)據(jù)鏈路層的功能（3.1）幀同步機(jī)制差錯(cuò)檢測(cè)與校正（3.2）簡(jiǎn)單差錯(cuò)控制編碼：奇偶校驗(yàn)碼、Internet檢驗(yàn)和、循環(huán)冗余碼(CRC)、線性分組碼卷積碼RS碼數(shù)據(jù)鏈路協(xié)議（3.3）停等協(xié)議滑動(dòng)窗口協(xié)議數(shù)據(jù)鏈路層協(xié)議舉例（3.4）HDLCPPP數(shù)據(jù)鏈路層的功能3

數(shù)據(jù)鏈路層的基本功能是在物理層提供的比特流傳輸服務(wù)基礎(chǔ)上，把服務(wù)用戶（網(wǎng)絡(luò)層）來的數(shù)據(jù)沿一段邏輯鏈路可靠地傳遞給相鄰的節(jié)點(diǎn)網(wǎng)絡(luò)層。涉及4方面的內(nèi)容：幀同步：約定處理的基本單元（幀，或稱DL-PDU），進(jìn)行幀的起始和結(jié)束定位。傳輸過程中可能有差錯(cuò)、流量等需要處理和控制。更有效地利用鏈路。差錯(cuò)控制（可靠傳遞）差錯(cuò)檢測(cè)與校正。反饋重發(fā)：確認(rèn)和重傳。超時(shí)和序號(hào)：一幀可能完全消失，或重復(fù)。幀同步機(jī)制5有2類通信協(xié)議（同步）機(jī)制：

異步協(xié)議（字符為單位同步，字符間異步：字符內(nèi)連續(xù)傳輸）在字符起始處進(jìn)行同步位同步：發(fā)送方和接收方采用近似同一頻率的時(shí)鐘，短時(shí)間內(nèi)時(shí)鐘的偏移是可以忍受的。同步協(xié)議（幀為單位同步，字符間同步：幀內(nèi)連續(xù)傳輸）在幀（比較大的數(shù)據(jù)單元）的起始處同步。維持固定的時(shí)鐘，采用某種方法（比如上章介紹的4B/5B編碼等）將時(shí)鐘信號(hào)編碼進(jìn)數(shù)據(jù)中。面向字符的同步協(xié)議：特殊字符表示幀的開始和結(jié)束。面向比特的同步協(xié)議：特殊比特模式表示幀的開始和結(jié)束。字節(jié)計(jì)數(shù)的同步協(xié)議：特殊字符表示開始，字節(jié)數(shù)表示結(jié)束。違例編碼法：采用不在正常數(shù)據(jù)部分出現(xiàn)的物理信號(hào)模式。固定長(zhǎng)度（SONET/ATM/T1）：搜索特定比特模式來確定開始。起止式異步規(guī)程

起始位和終止位進(jìn)行同步，起始位為低電平，終止位和空閑位為高電平。

接收端通過檢測(cè)起始位的下降前沿來決定字符的開始，并作為后面各位的定時(shí)基準(zhǔn)。大部分接收端采用更短周期時(shí)鐘：比如16倍時(shí)鐘。簡(jiǎn)單、信道有效利用率低、差錯(cuò)和通信控制能力差。如：1個(gè)起始位、5~8個(gè)數(shù)據(jù)位、0~1個(gè)奇/偶校驗(yàn)位、1~2個(gè)終止位6面向字符的同步協(xié)議

利用一些特殊定義的字符來標(biāo)識(shí)幀的起始位置，分隔不同的段，控制信息交換的過程。字符填充：特殊字符可能在數(shù)據(jù)部分出現(xiàn)。一種方案：利用轉(zhuǎn)義字符DLE(Data

Link

Escape)來實(shí)現(xiàn)數(shù)據(jù)透明在控制字符前面有一個(gè)DLE時(shí)才具有特殊意義。每個(gè)獨(dú)立的控制字符作為普通的數(shù)據(jù)字符。

若數(shù)據(jù)段本身出現(xiàn)DLE，則在前面插入一個(gè)DLE。接收方接收到連續(xù)兩個(gè)DLE，則去掉第一個(gè)DLE，并且作為普通字符看待，不再具有轉(zhuǎn)義意義。例：接收到DLE/DLE/DLE/ETX

表示DLE(data)

+

ETX(control)特殊字符隨采用的字符編碼集而不同（ASCII/EBCDIC）。有很大局限性（早期使用較多）。ISO

1745Q:來自網(wǎng)絡(luò)層的分組放在哪？7面向比特的同步規(guī)程

通過一個(gè)特定的比特模式“01111110”來標(biāo)識(shí)幀的起始位置。比特填充：保證數(shù)據(jù)部分不會(huì)出現(xiàn)連續(xù)6個(gè)1幀中的其他字段中如果出現(xiàn)連續(xù)5個(gè)1，則之后插入一個(gè)0。當(dāng)接收時(shí)，如果出現(xiàn)連續(xù)5個(gè)1后跟一個(gè)0，則刪除0。HDLC相比面向字符，兼容性好，硬件實(shí)現(xiàn)方便。8字節(jié)計(jì)數(shù)的同步規(guī)程同步字符來進(jìn)行幀同步，SOH標(biāo)志幀開始。字節(jié)計(jì)數(shù)來確定幀的結(jié)束邊界位置。CRC1對(duì)前面標(biāo)題部分校驗(yàn)，CRC2對(duì)數(shù)據(jù)部分校驗(yàn)。–特殊字符少，但Count的差錯(cuò)可能是災(zāi)難性的。違例編碼法通過不會(huì)在數(shù)據(jù)部分出現(xiàn)的編碼信號(hào)來進(jìn)行定位。比如曼徹斯特編碼中的高-高/低-低信號(hào)。字節(jié)計(jì)數(shù)的同步規(guī)程/違例編碼法9固定長(zhǎng)度

SONET幀固定為810字節(jié)，每行前面三個(gè)字節(jié)頭部，87字節(jié)用戶數(shù)據(jù)，每幀的前面兩個(gè)字節(jié)包含一個(gè)特殊的比特模式來表示幀的開始。數(shù)據(jù)部分沒有進(jìn)行填充來保證數(shù)據(jù)透明。

接收方首先檢查相應(yīng)的幀開始模式，然后檢查每隔810字節(jié)后是否也是相同的比特模式，如果不是，則重新掃描幀開始模式。10固定長(zhǎng)度+HEC

ATM（異步傳輸模式）采用53字節(jié)的信元cell，其中5個(gè)字節(jié)的頭部中最后一個(gè)字節(jié)為HEC（信頭差錯(cuò)校正）。同步狀態(tài)：搜索逐比特檢查HEC預(yù)同步同步逐信元檢查HEC連續(xù)

次HEC正確HEC正確HEC不正確連續(xù)

次HEC不正確11差錯(cuò)檢測(cè)與校正：傳輸差錯(cuò)特性鏈路上有兩種不同的差錯(cuò)隨機(jī)差錯(cuò)：隨機(jī)熱噪聲隨機(jī)熱噪聲是信道固有的、持續(xù)存在的；碼元（比特）的差錯(cuò)是獨(dú)立的，和前后的碼元無關(guān)；隨機(jī)錯(cuò)的概率很低，物理信道的設(shè)計(jì)保證相當(dāng)大的信噪比。誤碼率(BER)：突發(fā)差錯(cuò)：沖擊噪聲外界的因素，持續(xù)時(shí)間短，突發(fā)性；傳輸中產(chǎn)生差錯(cuò)的主要原因；突發(fā)長(zhǎng)度：突發(fā)差錯(cuò)發(fā)生的第一個(gè)碼元到有錯(cuò)的最后一個(gè)碼元間所有碼元的個(gè)數(shù)。比如4800bps信道上的10ms的沖擊噪聲的突發(fā)長(zhǎng)度為48比特。12差錯(cuò)控制通常通過差錯(cuò)編碼來實(shí)現(xiàn)。

基本思想：在被傳送的信息中附加一些監(jiān)督位（碼元），在收和發(fā)之間建立某種校驗(yàn)關(guān)系，當(dāng)這種校驗(yàn)關(guān)系因傳輸錯(cuò)誤而受到破壞時(shí)，可以被發(fā)現(xiàn)甚至糾正錯(cuò)誤，這種檢錯(cuò)與糾錯(cuò)能力是用信息量的冗余度來換取的。

差錯(cuò)編碼：對(duì)要發(fā)送的信息位(k)附加上按照某種數(shù)學(xué)關(guān)系產(chǎn)生的冗余/監(jiān)督位(r)。編碼效率R=k/(k+r)：碼字中信息位所占的比例。漏檢率：接收者無法了解到信息位出錯(cuò)的概率。按照：是否能糾錯(cuò)：檢錯(cuò)碼和糾錯(cuò)碼。信息碼元和冗余碼元之間的關(guān)系是否為線性：線性碼和非線性碼。信息碼元和冗余碼元之間的約束方式：分組碼和卷積碼。糾正錯(cuò)誤類型：糾正隨機(jī)錯(cuò)誤和糾正突發(fā)錯(cuò)誤碼。

差錯(cuò)編碼的任務(wù)就是要根據(jù)不同的差錯(cuò)特性，設(shè)計(jì)出編碼效率高、糾錯(cuò)能力強(qiáng)的編碼。實(shí)現(xiàn)中，根據(jù)需要盡量簡(jiǎn)化編碼實(shí)現(xiàn)的復(fù)雜度，節(jié)省設(shè)計(jì)費(fèi)用。13差錯(cuò)控制編碼一些差錯(cuò)編碼術(shù)語14

碼元：數(shù)據(jù)通信中每一個(gè)符號(hào)的通稱。在差錯(cuò)編碼中一般用二進(jìn)制表示，此時(shí)對(duì)應(yīng)于比特（位）。碼字：若干個(gè)碼元序列組成的數(shù)據(jù)單元。碼長(zhǎng)：碼字中碼元的數(shù)目。碼重：碼字中非0數(shù)字的數(shù)目對(duì)于二進(jìn)制碼來講，碼重W就是碼字中1的數(shù)目。例如碼字10100，碼長(zhǎng)n=5，碼重W=2。

碼距（漢明/海明距離）：兩個(gè)等長(zhǎng)碼字之間對(duì)應(yīng)符號(hào)不同的數(shù)目

對(duì)于二進(jìn)制碼字而言，兩個(gè)碼字之間的模二相加，其不同的對(duì)應(yīng)位必為1，相同的對(duì)應(yīng)位必為0。兩個(gè)碼字之間模二相加得到的碼重就是這兩個(gè)碼字之間的距離。如：碼字10100與11000之間的碼距d=2。

最小碼距：在碼字集合中全體碼字之間距離的最小數(shù)值，表示為dmin。差錯(cuò)控制方式自動(dòng)請(qǐng)求重發(fā)ARQ（Automatic

Request

for

Repeat）接收方檢測(cè)錯(cuò)誤，通知發(fā)送方重傳。雙向信道，發(fā)送方緩存發(fā)送的數(shù)據(jù)。前向糾錯(cuò)FEC（Forward

ErrorCorrection）接收方不僅可以檢測(cè)錯(cuò)誤，而且知道錯(cuò)誤的位置、加以糾正。采用糾錯(cuò)碼，無需反向信道，無需重發(fā)。

糾錯(cuò)碼一般說來要比檢錯(cuò)碼使用更多的冗余位，也就是說編碼效率低，而且糾錯(cuò)的設(shè)備也比檢錯(cuò)的設(shè)備復(fù)雜得多混合糾錯(cuò)HEC（Hybrid

Error

Correction）：ARQ和FEC結(jié)合誤碼率較高時(shí)采用ARQ，低時(shí)采用FEC。（簡(jiǎn)單的FEC，不行則ARQ）15奇偶校驗(yàn)水平(橫向)奇偶校驗(yàn)垂直(縱向)奇偶校驗(yàn)

檢測(cè)出每列（段）中所有奇數(shù)（1、3…）個(gè)錯(cuò)；突發(fā)錯(cuò)誤的漏檢率為50%；在發(fā)送和接收的過程中進(jìn)行編解碼。各段同一位上的奇數(shù)個(gè)錯(cuò)；長(zhǎng)度小于等于p的突發(fā)差錯(cuò)；

編碼和檢測(cè)相比垂直校驗(yàn)而言實(shí)現(xiàn)要復(fù)雜一些。16Internet校驗(yàn)和18高層協(xié)議的軟件校驗(yàn)方法。

每2個(gè)字節(jié)為一組(word)，按照二進(jìn)制反碼運(yùn)算相加。–最后如果為單字節(jié)，則附加一個(gè)為0的字節(jié)。生成校驗(yàn)和

校驗(yàn)和字段為0，然后二進(jìn)制反碼相加，最后取其反碼作為校驗(yàn)和的取值。驗(yàn)證校驗(yàn)和

按照二進(jìn)制反碼運(yùn)算相加，如果為全1（-0），則說明校驗(yàn)和正確。u_short

cksum(u_short

*buf,

int

count{register

u_long

sum

=

0;while

(count--){sum

+=

*buf++;if

(sum

&

0xFFFF0000){/*

carry

occurred,so

wrap

around

*/sum

&=

0xFFFF;sum++;}}return

?(sum

&

0xFFFF);}RFC1071/wiki/Cyclic_redundancy_check計(jì)算機(jī)網(wǎng)絡(luò)/存儲(chǔ)中使用廣泛的檢錯(cuò)碼糾錯(cuò)碼的編碼效率較低，常采用檢錯(cuò)碼＋ARQ。也稱為多項(xiàng)式碼二進(jìn)制比特串和一個(gè)只有0和1兩個(gè)系數(shù)的多項(xiàng)式一一對(duì)應(yīng)；k位信息位對(duì)應(yīng)于一個(gè)(k-1)次多項(xiàng)式K(x):比如1011011；r位冗余位對(duì)應(yīng)于一個(gè)(r-1)次多項(xiàng)式R(x):比如110110；信息位＋冗余位（n=k+r）對(duì)應(yīng)于一個(gè)(n-1)次多項(xiàng)式 T(x)=xrK(x)+R(x)編碼：找一個(gè)生成多項(xiàng)式G(x)（r次多項(xiàng)式，最高位的系數(shù)為1），

xrK(x)除以G(x)得到的余式為冗余位R(x)。解碼：接收方的碼字除以G(x)，如余式為0（能整除）表示無錯(cuò)。19循環(huán)冗余碼CRC循環(huán)冗余碼CRC（續(xù)）CRC的多項(xiàng)式運(yùn)算采用模2運(yùn)算（異或、按位加/減）半加

半減＝–例：信息位1010001，多項(xiàng)式K(x)=x6+x4+1；生成多項(xiàng)式G(x)=x4+x2+x+1（對(duì)應(yīng)代碼10111）；則r=4，那么：20….即：R(x)=x3+x2+1循環(huán)冗余碼CRC（續(xù)）

差錯(cuò)模式（差錯(cuò)多項(xiàng)式）E(x)＝發(fā)送碼字和接收碼字的半加，其中1的位置對(duì)應(yīng)變化信息位（差錯(cuò)）的位置。若E(x)能被G(x)整除，則CRC不能檢測(cè)這樣的錯(cuò)誤。Q:T(x)+E(x)是什么？21生成多項(xiàng)式若r次多項(xiàng)式G(x)含(x+1)的因子，則能檢測(cè)出所有奇數(shù)位錯(cuò)：

若G(x)中不含x的因子，即G(x)中的常數(shù)項(xiàng)為1，則能檢測(cè)出所有突發(fā)長(zhǎng)度 r的突發(fā)錯(cuò)：n-1，除不盡xe+1，則

若G(x)中不含x的因子，且對(duì)任何0<e能檢測(cè)出所有的雙錯(cuò)：22生成多項(xiàng)式（續(xù)）

若G(x)中不含x的因子，則對(duì)突發(fā)長(zhǎng)度為r+1的突發(fā)錯(cuò)誤的漏檢率為2-(r-1)

。

若G(x)中不含x的因子，則對(duì)突發(fā)長(zhǎng)度b(b>r+1)的突發(fā)錯(cuò)誤的漏檢率為2-r

。23生成多項(xiàng)式（續(xù)）若適當(dāng)選取r次多項(xiàng)式G(x)，滿足：含有x+1因子。常數(shù)項(xiàng)不為0：不含x的因子。周期大于等于n·

周期e為使G(x)能除盡xe+1的最小正整數(shù)。則能：檢測(cè)出所有奇數(shù)位錯(cuò)、突發(fā)長(zhǎng)度小于等于r的突發(fā)錯(cuò)、雙錯(cuò)。

突發(fā)長(zhǎng)度為r+1的突發(fā)錯(cuò)誤的漏檢率為2-(r-1)，對(duì)突發(fā)長(zhǎng)度b(b>r+1)的突發(fā)錯(cuò)誤的漏檢率為2-r

。常用的CRC多項(xiàng)式：IBM

BSC/USB802.15.4/CDMA/Bluetooth/HDLC/PPPEthernet/MPEG/PNG24碼字輸出端輸出開關(guān)信息輸入端CRC硬件實(shí)現(xiàn)R0R1Rr-1g1g2gr-1K(x)=1010001T(x)=1010001110125例

除以G(x)的運(yùn)算可以通過移位寄存器和半加器來實(shí)現(xiàn)：

軟件實(shí)現(xiàn)：查表線性分組碼26

線性：信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線性方程來表示。

分組：將信息碼元若干位為一組，該組監(jiān)督碼元僅與本組信息位有關(guān)。線性分組碼的線性特性任意兩個(gè)許用碼字的和也是許用碼字。碼集（碼字集合）的最小碼距等于非零碼的最小碼重。一些線性分組碼奇偶校驗(yàn)循環(huán)冗余碼海明碼Reed-Solomon碼碼集漢明(海明)距離和檢/糾錯(cuò)能力27假設(shè)要傳送的消息為A/B兩個(gè)狀態(tài)編碼（碼字）–

A:

0 B:

1海明距離=1；沒有檢錯(cuò)/糾錯(cuò)。–

A:

00 B:

11海明距離=2；{01,10}不用，可以檢測(cè)1比特錯(cuò)，沒有糾錯(cuò)能力。–

A:

000 B:

111海明距離=3；檢測(cè)出兩位及兩位以下差錯(cuò)；糾正1比特差錯(cuò)。碼集海明距離和檢/糾錯(cuò)能力（續(xù)）28為檢出e個(gè)錯(cuò)碼，要求碼集的海明距離d≥e+1。為糾正t個(gè)錯(cuò)碼，要求碼集的海明距離d≥2t+1。為檢出e個(gè)錯(cuò)碼，同時(shí)能糾正t個(gè)錯(cuò)碼，則應(yīng)滿足

d≥e+t+1

(e>t)。例：if

e=2,

t=1,

then

d≥e+t+1=4–{0000,1111} d=4,能檢2個(gè)錯(cuò)碼，能糾1個(gè)錯(cuò)碼；–{0011,0101,0110},{1001,1010,1100} 能檢1個(gè)錯(cuò)碼；–{1100,1011} 能糾1位錯(cuò)。糾正一比特錯(cuò)的線性分組碼：海明碼回顧奇偶校驗(yàn)：一個(gè)k=n-1的信息位an-1an-2

…a1加上一個(gè)偶校驗(yàn)位a0（an-1an-2

…a1a0）。接收端：利用一個(gè)監(jiān)督關(guān)系式計(jì)算校正因子S（=0和1），分別區(qū)分無錯(cuò)和有錯(cuò)（奇數(shù)位錯(cuò)）的情況：

擴(kuò)展（Hamming碼）：k位信息位后增加r個(gè)冗余位構(gòu)成n(=k+r)位的碼字。每個(gè)冗余位是通過信息位中的某些位半加后的結(jié)果。對(duì)應(yīng)的接收方通過r個(gè)監(jiān)督關(guān)系式產(chǎn)生r個(gè)校正因子來區(qū)分無錯(cuò)和n位的碼字中一位錯(cuò)。要求：29Hamming

codes

with

additional

parity

(SECDED)Hamming

codes

have

a

minimumdistance

of

3,

whichmeans

that

the

code

can

detect

and

correct

a

single

error,

but

a

double

bit

error

isindistinguishable

froma

different

code

with

a

single

bit

error.

Thus,

they

can

detect

double-bit

errors

onlyif

correction

is

not

attempted.By

including

an

extra

parity

bit,

it

is

possible

to

increase

the

minimumdistance

of

the

Hamming

code

to

4.

This

gives

the

code

the

ability

to

detectand

correct

a

single

error

and

at

the

same

time

detect

(but

not

correct)

a

double

error.

(Itcould

also

be

used

to

detect

up

to3

errors

but

notcorrect

any.)This

code

system

is

popular

in

computer

memory

systems,

where

it

is

known

as

SECDED

("single

error

correction,

double

error

detection").Particularly

popular

is

the

(72,64)

code,

atruncated

(127,120)

Hamming

code

plus

an

additional

parity

bit,

which

has

the

same

space

overheadas

a

(9,8)

parity

code.an

overall

parity

bit

(bit

0)is

included,

the

code

can

detect

(but

not

correct)

any

two-bit

error,

making

a

SECDED

code.

The

overall

parityindicates

whether

the

total

numberof

errors

is

even

orodd.

If

the

basic

Hamming

code

detects

an

error,

but

the

overall

parity

says

that

there

arean

even

number

of

errors,

an

uncorrectable

2-bit

error

has

occurred.海明碼（續(xù)）：例子

假設(shè)信息位為k=4，則r 3。取r=3，n=7，即a6a5a4a3

+a2a1a0。（編碼效率R=4/7）冗余位a2、a1和a0是信息位中的某幾位半加得到。三個(gè)監(jiān)督關(guān)系式和校正因子S2S1S0來自冗余位a2a1a0與信息位a6a5a4a3半加S2S1S0區(qū)分無錯(cuò)和7位碼字中某一位有錯(cuò)（糾錯(cuò)）的情況S2

S1

S0000001010100011101110111錯(cuò)碼位置無錯(cuò)a0a1a2a3a4a5a6海明距離為3 糾正單比特差錯(cuò)或檢測(cè)出2個(gè)比特差錯(cuò),對(duì)于(7,4)海明碼兩者同時(shí)滿足。

實(shí)踐中進(jìn)一步增加了一個(gè)奇偶校驗(yàn)位，使得海明距離為4（如果檢測(cè)出差錯(cuò)，但奇偶校驗(yàn)為偶數(shù)個(gè)差錯(cuò)，說明為2個(gè)比特差錯(cuò)，否則為單比特差錯(cuò)）。30海明碼（續(xù)）：糾錯(cuò)性能

信息位越長(zhǎng)，編碼效率越高。如：k=7，冗余位最少為4，編碼效率為7/11。（k→∞，編碼效率k/(k+r)趨于100％）糾正突發(fā)錯(cuò)誤–連續(xù)P個(gè)碼字排成一個(gè)矩陣，每行一個(gè)碼字，從而可以糾正突發(fā)長(zhǎng)度 P的突發(fā)錯(cuò)。31RS（Reed-Solomon）碼*：伽羅瓦域32伽羅瓦域（有限域）：GF(pm)有限域的階（有限域中元素的個(gè)數(shù)）一定是一個(gè)素?cái)?shù)的冪=pm

。有限域的階對(duì)應(yīng)的素?cái)?shù)為有限域的特征Char(GF(pm))，即最小的正數(shù)n：使得滿足n個(gè)元素相加為0。如何構(gòu)造GF(2m)?本原多項(xiàng)式P(x)：一個(gè)m次不可約多項(xiàng)式，可以整除x2m-1+1，但是不能整除其他的xk+1(k<2m-1)?？偣灿?m個(gè)元素，這些元素為0、1、α、α2、α3…α2m-2

，其中α為本原多項(xiàng)式P(x)=0的根。

GF(23)的本原多項(xiàng)式P(x)=x3+x+1，α為本原多項(xiàng)式

P(x)=0的根。33RS碼：伽羅瓦域例GF(23)GF(23

)元素元素mod(α3+α+1)二進(jìn)制對(duì)應(yīng)代碼00(000)1=α01(001)α1α1(010)α2α2(100)α3α+1(011)α4α2+α(110)α5α2+α+1(111)α6α2+1(101)所有運(yùn)算都在域中進(jìn)行，如GF(23)域中運(yùn)算：加法：α+α4=α(1+α3)=αα=α2減法：α-α4=α+α4=α(1+α3)=α2乘法：α4α3=α4+3=α7=αα6=α(α2+1)=α3+α=1除法：α4/α=α3RS碼：RS(n,k)34

RS碼是一種擴(kuò)展的非二進(jìn)制（多進(jìn)制）BCH碼，在GF(2m)中運(yùn)算，常用RS(n,k)來表示，如RS(255,233)。

BCH是循環(huán)碼的一個(gè)子集，基于有限域而構(gòu)建，可以糾正多個(gè)比特差錯(cuò)，用于衛(wèi)星通信、DVD、磁盤、二維條形碼等。n為碼長(zhǎng)，每個(gè)符號(hào)為有限域中的某個(gè)元素，由m(=8)位二進(jìn)制串表示·

線性分組碼：n*m個(gè)比特為一組，每個(gè)符號(hào)由m個(gè)比特組成，總共n個(gè)符號(hào)。k為碼字中信息部分的符號(hào)個(gè)數(shù)。K=n-k為校驗(yàn)（監(jiān)督）部分符號(hào)的個(gè)數(shù)。最小碼距為n-k+1。t=K/2為能糾正的錯(cuò)誤符號(hào)的個(gè)數(shù)。

RS碼可用于CD、DVD、藍(lán)光CD等消費(fèi)電子、DSL、WiMAX等。RS碼：編碼原理

編碼過程：信息多項(xiàng)式M(x)xn-k除以生成多項(xiàng)式G(x)的余式為校驗(yàn)部分。–生成多項(xiàng)式

例：考慮一個(gè)GF(23)上的RS(6,4)碼，信息部分的符號(hào)為m3、m2、m1、m0，而校驗(yàn)部分符號(hào)為q1、q0。信息碼多項(xiàng)式為M(x)=m3x3

+m2x2

+m1x1

+m0余數(shù)多項(xiàng)式為R(x)=q1x+q0生成多項(xiàng)式G(x)=(x-α)(x-α2)，偏移量K0=1因此有：m3x5

+m2x4

+m1x3

+m0

x2

+q1x+q0

=(x-α)(x-α2)Q(x)35RS碼：編碼原理（續(xù)）–x分別取α和α2，則得到校驗(yàn)方程：即：m3α5

+

m2α4

+

m1α3

+

m0α2+

q1α

+

q0

=

0m3α10

+

m2α8

+

m1α6

+

m0α4+

q1α2

+

q0

=

0求解得：q1

=m3α5

+m2α5

+m1α0

+m0α4q0

=m3α

+m2α3

+m1α0

+m0α3假定信息符號(hào)取值分別是m3=α1，m2=α2，m1=α3，m0=α4，則校驗(yàn)符號(hào)為q1=α6，q0=1。–接收時(shí)的校正子可按下式計(jì)算s0

=

m3α5

+

m2α4

+

m1α3

+

m0α2+

q1α

+

q0s1

=

m3α10

+

m2α8

+

m1α6

+

m0α4+

q1α2

+

q0需進(jìn)一步根據(jù)校正子來推算錯(cuò)誤位置和錯(cuò)誤值。36以卷積碼（2,1,3）為例編碼器的生成序列：gi=(gi0，gi1，gi2，…，gim),i=0,1·

g0=(1

0

1

1),

g1=(1

1

1

1)·

編碼方程：v0=u g0

,

v1=u

g1

其中 為離散卷積輸入的信息序列u=(u0，u1，u2，…)，則輸出序列 v=(v00,v01,v10,v11,v20,v21,…)在時(shí)刻k≥0有：v0k=uk+

uk-2

+

uk-3v1k=uk

+

uk-1

+

uk-2

+

uk-3卷積碼：編碼器gg1238半無限矩陣，無限行和列，完全由第一行決定卷積碼：生成矩陣矩陣形式：v=uG

如果輸入u的長(zhǎng)度為b，生成矩陣G有b行m+b列，輸出序列v長(zhǎng)度為m+b。G的相鄰行中，下一行在上一行的基礎(chǔ)上向右移動(dòng)n(=2)個(gè)位置。39約束度：(m+1)*k卷積碼40

除了采用前面的生成器序列、生成矩陣等解析法來描述卷積碼外，還可以采用圖解法，包括樹狀圖、網(wǎng)格圖和狀態(tài)圖等。卷積碼的譯碼方法：代數(shù)譯碼方法：以一個(gè)約束度的接收序列為單位，基于生成矩陣和監(jiān)督矩陣來譯碼。概率譯碼：從信道的統(tǒng)計(jì)特性出發(fā)，以遠(yuǎn)大于約束度的接收序列為單位，對(duì)信息碼組進(jìn)行最大似然的判決。序列譯碼維特比譯碼法雖然代數(shù)譯碼所要求的設(shè)備簡(jiǎn)單，運(yùn)算量小，但其譯碼性能（誤碼）要比概率譯碼方法差許多。因此，目前在數(shù)字通信的前向糾錯(cuò)中廣泛使用的是概率譯碼方法。數(shù)據(jù)鏈路協(xié)議41

有關(guān)數(shù)據(jù)鏈路層協(xié)議的這部分內(nèi)容，主要是面向連接服務(wù)中的可靠性和流量控制，包括：停等協(xié)議滑動(dòng)窗口協(xié)議停等協(xié)議停等協(xié)議（Stop-and-Wait）–發(fā)送者在發(fā)送一個(gè)幀之后停下來，等待對(duì)方確認(rèn)后繼續(xù)發(fā)送下一幀。while

(1)

{wait(

frame

ready);while

(1)

{transmit

(frame

i);try

{receive

(ack);}

catch

(timeout)

{

continue;

}i++;break}}while

(1)

{receive

(frame

i);transmit

(ack);}42接收方發(fā)送方停等協(xié)議（續(xù)）–如果確認(rèn)在一段時(shí)間后無返回，發(fā)送者超時(shí)，重傳幀。–簡(jiǎn)單的停等協(xié)議不包含序號(hào)，這會(huì)導(dǎo)致一些問題。Q:問題在哪？43停等協(xié)議（續(xù)）解決這個(gè)問題的辦法是使用順序號(hào)標(biāo)識(shí)幀和確認(rèn)（簡(jiǎn)單的只需要1比特）：只有幀發(fā)送成功才能發(fā)新幀。其中發(fā)送方維護(hù)next_frame_to_send，接收方維護(hù)frame_expected。next_frame_to_send=

0;while

(1)

{wait

(frame

ready);while

(1)

{transmit

(frame

next_frame_to_send);try

{receive

(ack

n);if

(n

!=

next_frame_to_send)

continue;}

catch

(timeout)

{

continue;

}break;}next_frame_to_send

++;}frame_expected

=

0;while

(1)

{receive

(framen);ack

(frame

n);if

(n

!=

frame_expected)continue;frame_expected

++;}44接收方發(fā)送方性能分析考慮停等因素的信道利用率–設(shè)信道容量B

bps，幀長(zhǎng)L

bit，往返傳播延遲2R秒，忽略ACK的開銷。–以衛(wèi)星信道(長(zhǎng)肥鏈路)為例：B=50kbps,2R=0.5s,L=1kbU=1000/(1000+25000)=1/26≈4％45性能分析（續(xù)）如果考慮ACK、重傳、幀頭開銷設(shè)D為幀中有效數(shù)據(jù)長(zhǎng)度，H為幀頭長(zhǎng)；則數(shù)據(jù)幀長(zhǎng)L=H+D，ACK幀長(zhǎng)為H；T表示等待ACK的超時(shí)間隔；P1和P2分別表示數(shù)據(jù)幀和ACK丟失的概率。每個(gè)數(shù)據(jù)幀需要進(jìn)行重傳的概率數(shù)據(jù)幀的平均傳輸次數(shù)、重傳次數(shù)46

為了使得不會(huì)出現(xiàn)誤重傳，超時(shí)間隔T必須取得足夠大，即T≥H/B

+2R，U要達(dá)到最大值，T越小越好，取T=H/B

+2R。–第一個(gè)因子表示停等的因素；第二個(gè)表示出錯(cuò)重傳的因素；第三個(gè)為幀頭的開銷。性能分析（續(xù)）47

進(jìn)一步假設(shè)信道上每比特的誤碼率為E，且各比特相互獨(dú)立，即：1-P1=(1-E)H+D，1-P2=(1-E)H，此時(shí)的利用率：–假設(shè)H、B、T、E不變，可求得使U最大的D值，即最佳幀數(shù)據(jù)長(zhǎng)度Dopt

：令48（設(shè)計(jì)最佳D的考慮因素）性能分析（續(xù)）

考慮幀頭開銷的ACK會(huì)影響信道利用率，而大部分的通信是雙向數(shù)據(jù)通信，因此可以使用捎帶確認(rèn)

(piggyback)：ACK幀通常可由反向發(fā)送的數(shù)據(jù)幀頭中一起捎帶回來。但有時(shí)完全的捎帶確認(rèn)并不能工作很好，如教材P102圖3.10例中假設(shè)不支持單獨(dú)ACK導(dǎo)致大量重復(fù)發(fā)送，仍然需要單獨(dú)的ACK幀。49性能分析（續(xù)）滑動(dòng)窗口

停等協(xié)議在開始傳輸一個(gè)數(shù)據(jù)幀到確認(rèn)回來這一段時(shí)間里必須等待，傳播時(shí)間遠(yuǎn)大于傳輸時(shí)間的時(shí)候會(huì)帶來很大的浪費(fèi)。管道（Pipelining）發(fā)送方在等待確認(rèn)幀回來之前可以連續(xù)發(fā)送多個(gè)數(shù)據(jù)幀序號(hào)位數(shù)要求大于等于發(fā)送者要求能夠緩存那些已經(jīng)發(fā)送的但是沒有確認(rèn)的幀。50滑動(dòng)窗口（續(xù)）如何進(jìn)行pipelined的差錯(cuò)恢復(fù)？–回退N

(Go

Back

N,GBN)·

接收方只允許順序接收，也就是說如果一幀出錯(cuò)，則它后面的N幀盡管可能正確到達(dá)接收方，但被直接丟棄，不發(fā)送確認(rèn)。發(fā)送方將超時(shí)，按序重傳所有未被確認(rèn)的幀。接收方可以不發(fā)前面的Ack而直接發(fā)后面的Ack。51滑動(dòng)窗口（續(xù)）–選擇重傳(Selective

Repeat,SR)·

若某一幀出錯(cuò)，后面送來的正確幀不是簡(jiǎn)單地丟棄，而是緩存在接收緩沖區(qū)，當(dāng)發(fā)送方意識(shí)到壞幀后，只重傳壞幀。一旦重傳的幀收到后，接受方與原先已收到但暫存在緩沖區(qū)中的其余幀一起按正確的順序遞交。52滑動(dòng)窗口（續(xù)）滑動(dòng)窗口的形成序號(hào)計(jì)數(shù)（n比特）是有限的，將會(huì)回繞。發(fā)送緩沖區(qū)和接收緩沖區(qū)是有限的。從而形成發(fā)送窗口、接收窗口滑動(dòng)窗口例停等協(xié)議可以看成是一個(gè)發(fā)送窗口=接收窗口=1的滑動(dòng)窗口協(xié)議。GBN為發(fā)送窗口≤2n-1、接收窗口=1的滑動(dòng)窗口協(xié)議。SR協(xié)議：1≤接收窗口≤發(fā)送窗口≤2n-1。

TCP使用順序號(hào)、累加確認(rèn)、檢驗(yàn)和和超時(shí)重傳機(jī)制，和GBN非常類似，但是許多TCP的實(shí)現(xiàn)都緩沖那些收到的但失序的TCP段。0

1

2

3

4

5

6

7

0

1

…1

2…發(fā)送窗口53接收窗口窗口是動(dòng)態(tài)滑動(dòng)的、大小是不固定的，但有限的。實(shí)際上，發(fā)送窗口即已發(fā)送、尚未確認(rèn)的幀；接收窗口是可用的接收緩沖區(qū)大小。數(shù)據(jù)鏈路層協(xié)議：HDLCHDLC（High-Level

Data

Link

Control）可提供面向連接和無連接的服務(wù)。面向比特的同步規(guī)程：01111110地址：標(biāo)識(shí)目的節(jié)點(diǎn)或源節(jié)點(diǎn)（主站/從站），最低(E)為擴(kuò)展位。控制：指出屬于那種幀·

P(oll)/F(inal)：主站發(fā)出時(shí)表示P，如果為1要求對(duì)方響應(yīng)；從站發(fā)出時(shí)示F，為1表示響應(yīng)結(jié)束。

信息I幀：攜帶用戶數(shù)據(jù)，幀的序號(hào)在N(S)中。并且支持捎帶確認(rèn)：N(R)表示之前的所有幀都正確。監(jiān)控S幀：控制傳輸，亦可實(shí)現(xiàn)單獨(dú)確認(rèn)。（沒有數(shù)據(jù)部分）無編號(hào)U幀：其它鏈路控制功能M=00000：UI（無編號(hào)信息）幀N(S)P/F

N(R)I幀

0S幀

1

0 類型

P/F

N(R)3U幀

1

1

MP/F

M35532HDLC（續(xù)）56三種站點(diǎn)：主站：控制鏈路的操作，發(fā)送COMMAND。從站：響應(yīng)主站的控制，發(fā)送RESPONSE。主從站：主站和從站的結(jié)合。兩種鏈路配置非平衡配置：一個(gè)主站，多個(gè)從站。平衡配置：兩個(gè)主從站。3種數(shù)據(jù)傳輸模式

正常響應(yīng)模式NRM：用于非平衡配置中。主站發(fā)起數(shù)據(jù)傳輸，從站響應(yīng)。

異步響應(yīng)模式ARM：用于非平衡配置中，從站也可發(fā)起數(shù)據(jù)傳輸，但主站維護(hù)鏈路。很少使用。異步平衡模式ABM：用于平衡配置，任何一個(gè)站點(diǎn)可以發(fā)起數(shù)據(jù)傳輸。57連接建立和釋放（U幀）數(shù)據(jù)傳輸數(shù)據(jù)傳輸:RNRS幀：RR(00,Receive