1错误检测(ERRORDETECTION)传送讯框时发生错误的一些机率定义.doc

 PAGE 2 無線通訊與網路 1 錯誤檢測(ERROR DETECTION) 傳送訊框時發生錯誤的一些機率定義： Pb：單一位元錯誤機率or位元錯誤率(BER) P1：收到的訊框內無任何位元錯誤的機率 P2：使用錯誤檢測演算法時收到的訊框仍有一個或多個未檢知錯誤的機率 P3：使用錯誤檢測演算法時接收訊框檢測出一個或多個錯誤位元但無其他未檢知錯誤的機率 先考慮沒有使用錯誤檢測演算法的情況，其檢測錯誤機率(P3)為0。假設任何位元的錯誤機率相同且相互獨立: Ｆ是一個訊框的位元個數。當單一位元錯誤機率遞增時接收訊框沒有位元錯誤的機率愈低。增加訊框的長度時接收訊框沒有位元錯誤的機率愈低，訊框愈長其錯誤率愈高。 例子: ISDN要求在一個64 kbps通道上觀察1分鐘至少90%的期間其BER低於10-6； 一用戶連續使用64-kbps傳輸，平均每天允許一個未檢知位元錯誤的訊框，設一個訊框長度為1000位元，一天內可以傳送的訊框數為5.529?106，所要求最大訊框錯誤率P2 = 1/(5.529?106) = 0.18?10-6；假定Pb=10-6則P1 = (0.999999)1000 = 0.999和P2 = 10-3，離要求的10-6甚遠。 資料 PAGE 1 無線通訊與網路 編碼器 (a) 發送器 資料 PAGE 1 無線通訊與網路 (b) 接收器 比較 編碼器 圖1錯誤檢測程序 k位元的資訊區塊，其錯誤檢測演算法產生n?k位元的錯誤檢測碼 or稱查核位元(check bits) 的錯誤檢測碼附加於資訊區塊而產生n位元的訊框。 錯誤檢測系統將檢知錯誤其錯誤機率用P3表示，而P2稱為剩餘錯誤率，表示使用錯誤檢測系統去檢測錯誤而未檢測到錯誤的機率。 同位元查核(Parity Check) 傳輸字元有偶數個1 (偶同位)或有奇數個1(奇同位)。 一般偶同位用於同步傳輸而奇同位用於非同步傳輸。 可靠度不高，因為高速資料傳輸系統，雜訊脈衝常造成一個位元以上之錯誤。 循環冗碼查核(Cyclic Redundancy Check, CRC) 最常見且功能強大的錯誤檢測碼。給定k位元的資訊區塊，產生n?k位元訊框檢驗序列(frame check sequence, FSC)，組成一可被預定數除盡的n位元訊框。接收到的訊框除以相同之數，如果沒有餘數則表示沒有錯誤發生。 2-??運算 (Modulo 2 Arithmetic):無進位的二進制加減法，相當於互斥或(exclusive-OR, XOR)運算 定義: T = 傳送之n位元訊框。 D = k位元的資料或訊息；即T之前面k位元。 F = (n-k) FCS位元；即T之後面(n-k)位元。 P = (n-k+1)位元之模式序列；即預定之除數。 希望T / P整除沒有餘數。 D乘上2n-k的作用:向左移動n-k位元且原本之位元補零。設 　　　　　　 (1) 有商和餘數，餘數相當於FCS，so 　　　　　　 (2) ?T/P整除。 產生FCS：除以P得(n - k)餘數位元當FCS。 例： 給定 　　　　　訊息 (10位元) 模式序列(6位元) FCS, R = 待計算 (5位元) 　可知n = 15、k = 10和n-k = 5 將訊息乘上25得 101000110100000 將結果除以P 將餘數與25D相加得T = 101000110101110，傳送此序列。 假如傳輸沒有錯誤，接收機將完整接收到T，將接收訊框除以P： 餘數為0：沒有錯誤發生 模式序列P比FCS多一個位元，其模式的選擇取決於預期錯誤的型式，其最低限制：P的最高和最低位元都必須為1。 描述一個或多個位元錯誤發生： 　　　T = 傳送訊框 E = 錯誤發生位置為1之錯誤模式 Tr = 接收訊框 如有錯 (E ? 0)，只有當Tr整除P(相當於E整除P)時接收器不能檢知錯誤： Unlikely 多項式 (Ploynomials) 將所有位元值表示成X變數的多項式之二進制係數：係數與二進制數中的位元相對應。 例： 同先前的例子，將D = 1010001101和P = 110101分別表成D(X) = X9+ X7+ X3+ X2+ 1和P(X)=X5+ X4+ X2+ 1，而餘數R = 01110對應R(X) = X3+ X2+ X。 圖2多項式除法 只有當E(X)可整除P(X)時，E(X)偵測不到錯誤。[PETE 61, RAMA88] 顯示下列全部情況E(X)無法被適當之P(X)除盡，因此可檢知錯誤： 假如P(X)為一非零項多時，可以檢知所有單一位元的錯誤 只要P(X)包含一個三項因式，可以檢測所有雙位元的錯誤 只要P(X)含有因式(X-1)，可以檢測