跳去內容

Checksum

出自維基百科,自由嘅百科全書
圖解:將 input 嘅信息,用測琛函數將段嘢轉化做測琛冧把。

Checksum借入粵語粵拼cek1 sam1,大致假借中文字cek1),中文核對和總和檢查碼,係一種用嚟檢驗啲數據有冇出錯嘅簡單方法。因為實際上未必真係數學上講嘅,有時又叫核對值核對碼

簡單講,佢涉及嘅係傳訊嗰方用一段演算法,由源數據嗰度產生出一個冧把,包括概念上用商餘計算將個冧把限制喺某個範圍[註 1];收訊嗰方接收到數據之後,就用同一演算法計個冧把應該係乜,如果收到同自己計嘅版本冇分別,就假定傳訊冇事,如果唔夾,就肯定有嘢錯咗。

做法

[編輯]

測琛最基本嘅做法如下[1]

  1. 傳訊方攞住一段想傳出去嘅數據,將段數據斬做 k 橛,每橛都係 n (好多時都係 16 必)咁長;
  2. 傳訊方將呢 k 橛嘅冧把加埋一齊(講緊用二進制),最後得出一個 n 必咁長嘅總和(sum);
  3. 將個總和值做位操作,即係將原先係 0 嘅冧把冚唪唥變晒做 1,而原先係 1 嘅冧把冚唪唥變晒做 0,得出測琛值;
  4. 將測琛值黐落原本段數據嘅最尾嗰度,傳出。
  5. 收訊方收到段數據,計一次測琛,計個測琛值出嚟,如果段數據(例如)畀人篡改過嚟,或者喺傳訊過程當中因為雜音走咗樣,收訊人計到嘅測琛值理應會同傳訊方傳嗰個唔同,噉就顯示段數據有輘輷。

—收訊人可以靠住測琛嘅做法,cek1 吓段數據啱唔啱。

例如如果想傳嘅數據係 10101001 00111001,分做兩橛(k = 2),每橛 8 必咁長(n = 8),噉要計測琛值:

 10101001
 00111001

做二進制加數,同時如果最大嗰個位要進位,就返轉頭進去最細嗰個位度:

 11100010

同呢段冧把做位操作非:

 00011101 # 測琛值

不過事實已經表明咗,測琛呢種做法唔係咁靠得住。而家想像段數據嘅其中一個必走咗樣,同時又有另外一個必走咗樣,如果兩個必嘅位置啱,係有可能出現一種情況,係最後得出嘅測琛值不變嘅—而噉就會令到齋靠測琛值嚟做檢驗嘅收訊者探測唔到個錯誤。

變化

[編輯]

喺電腦,呢段演算法嘅標準定義係喺16位元嘅限制之下就咁將源數據經某種切割方法之後加埋一齊(即係將和限制咗喺 65536 嘅餘數)[2]:88,但係實際上未必係限制喺16位元,亦未必係用加法,例如以前8位元處理器通行嗰陣,核對值可以只係限制喺8位元(即係 256 嘅餘數),或者可能會用邏輯異或[3]:270-271。喺電腦以外好有可能唔係限制個餘數喺2嘅,而係將餘數限制喺10或者其他嘅數;例如日常生活中常見嘅國際標準書號,最後一個冧把就可以話係一個核對值,但係舊版嘅 ISBN-10 係用11嘅餘數,而新版嘅 ISBN-13 就係用10嘅餘數,佢用嘅演算法亦唔係就咁將啲數字加埋就算。

教學

[編輯]

疏士

[編輯]
  1. Error detection (英文)史丹福大學嘅碌士講解點樣探測數據有冇出錯,當中有提到測琛。
  2. Carne, E. Bryan (1995). Telecommunications Primer (美國英文). Prentice Hall; IEEE Press. ISBN 0-13-490426-5.
  3. Zaks, Rodnay (1980). Programming the 6502 (美國英文) (第3版). Sybex. ISBN 0-89588-046-6.

[編輯]
  1. 喺電腦,概念上嘅商餘計算通常唔涉及實際嘅商餘計算,而係概念上用2嘅冪,而呢個2嘅冪通常會係個處理器正常嘅處理單位,即係例如16位元嘅處理器正常會用2嘅16次方;理由係如果用整數計,用機器語言而唔做任何額外嘢處理進位,就自動等於用咗商餘計算。如果㨂嘅2嘅冪細過處理器嘅正常處理單位,亦可以照計,然後用邏輯與鏟走唔要嘅位元,咁計快過真係用除法做商餘計算。

[編輯]