1. 真正根源

1.1. 在電報和電話等通信系統中出現的

1.2. 理查德·漢明創造了第一批糾錯碼：一種近乎神奇的能偵測并糾正計算機資料中錯誤的演算法

2. 資訊理論學的一部分

2.1. Information Theory

2.2. 香農通過數學展示了有可能從根本上通過一個嘈雜的、引發錯誤的鏈接實作錯誤率極低的通信

2.3. 即便是極端不可靠的通信頻道也可以以極低的錯誤率傳輸資料

2.4. 沒有糾錯碼，計算機和通信系統就會比現在慢很多，功能弱許多，可靠性也會差很多

3. 計算機三項基本作業

3.1. 執行計算

3.2. 存盤資料

3.3. 傳輸資料

4. 錯誤偵測及糾正的需求

4.1. 計算機要無誤地存盤和傳輸的資訊量絕對是海量

4.2. 精確度達到99.999 9%也還是不夠好

4.3. 必須能在存盤和傳輸數十億“塊”資訊的情況下，不犯任何一個錯誤

5. 雜項

5.1. overhead

5.2. 為確保訊息被正確接收而發送的多余資訊

5.3. 一個糾錯系統的“雜項”就是在發送訊息本身以外要發送的額外資訊量

6. 重復把戲

6.1. 同時偵測和糾正資料中錯誤的方法

6.2. 要確保一些資訊被正確地傳輸，只需重復幾次該資訊

6.3. 通過重復一條不可靠的訊息足夠多次，就可以讓訊息的可靠性高到讓你滿意為止

6.4. 假設錯誤隨機發生，相反，如果一個惡意物體故意干擾傳輸，并選擇制造某些錯誤，重復把戲都會變得不可靠

6.5. 通過使用重復把戲，不可靠通信的問題能夠被解決，錯誤基本上能被消滅

6.6. 你發送的額外東西就是更多份原始訊息

6.6.1. 雜項數量巨大，因為必須發送數份完整訊息

7. 代碼字

7.1. code words

7.2. 示例

7.2.1. “one”（一）、“two”（二）、“three”（三）

8. 冗余把戲

8.1. The Redundany Trick

8.2. 同時偵測和糾正資料中錯誤的方法

8.3. 基本原則

8.3.1. 你不能只發送原始訊息，你要發送一些多余的東西以增加可靠性

8.4. 示例

8.4.1. “5 213.75”

8.4.1.1. five two one three point seven five

8.4.1.2. fiqe kwo one thrxp point sivpn fivq

8.4.1.3. 使用了一條冗余訊息，所以對訊息中的任何單個變化進行可靠偵測及糾正變得可行

8.4.2. 數字“367”代表了一個數

8.4.2.1. 因為這條訊息中沒有冗余，其中一個數字被替換，就沒辦法知道原始數字是多少

8.5. （7，4）漢明代碼（Hamming code）

8.5.1. 理查德·漢明于1947年在貝爾實驗室發明的代碼之一

8.5.2. 所有事情都通過0和1完成

8.5.2.1. 現實生活中使用的所有代碼也限用這兩個數字

8.5.3. 在編碼時，每一組4位數字都加入了冗余，由此產生了一個7位數的代碼字

8.5.4. 在解碼時，你首先要為接收的7位數尋找完全匹配，如果尋找完全匹配失敗，就選擇最接近的匹配

8.5.5. 7位數代碼字中的任何錯誤都能得到確定無疑的糾正

8.5.6. 只能糾正7位數代碼字中的一個錯誤

9. 校驗和把戲

9.1. 不管糾錯，而是將精力集中在偵測錯誤上

9.2. The Checksum Trick

9.3. “check”（校驗）訊息的“sum”（和）就是術語“checksum”（校驗和）的由來

9.4. 假設我們所有的訊息都只由數字組成會更方便些

9.4.1. 這是一個非常真實的假設，因為計算機用數字存盤所有的資訊，只有在向人展示資訊時，才把數字轉譯成文本或影像

9.5. 簡單校驗和

9.5.1. Simple Checksum

9.5.2. 只需將訊息中的所有數字相加，只保留結果的最后一位數，剩下的數字就是你的簡單校驗和

9.5.3. 只需在發送原始訊息前，將原始訊息的校驗和附加到訊息末尾即可

9.5.4. 如果只有一個錯誤，簡單校驗和絕對能保證偵測到它

9.5.5. 兩個或更多錯誤，簡單校驗和或許能偵測到它們，但也有可能偵測不到

9.5.6. 示例

9.5.6.1. 4 6 7 5 6

9.5.6.2. 4+6+7+5+6=28

9.5.6.3. 只保留最后一位數8

9.5.6.4. 4 6 7 5 6 8

9.5.7. 只能保證對相對較短的訊息奏效（少于10位數）

9.6. 階梯校驗和

9.6.1. Staircase Checksum

9.6.2. 像之前一樣把數字相加，但每個數都要和該數字所在位階數相乘，每個數都比前一個數大一個位階

9.6.2.1. 樓梯臺階編號為1、2、3……依此類推

9.6.3. 示例

9.6.3.1. 4 6 7 5 6

9.6.3.2. （1×4）+（2×6）+（3×7）+（4×5）+（5×6）=4+12+21+20+30=87

9.6.3.3. 只保留最后一位數7

9.6.3.4. 4 6 7 5 6 7

9.6.4. 只能保證對相對較短的訊息奏效（少于10位數）

9.7. 首先是簡單校驗和，其次是階梯校驗和

9.7.1. 4 6 7 5 6

9.7.2. 4 6 7 5 6 8 7

9.7.3. 可以保證這條訊息要么是正確的，要么至少有三處錯誤

9.7.4. 只要錯誤不超過兩處，你就都能夠偵測到錯誤

9.7.5. 只能保證對相對較短的訊息奏效（少于10位數）

9.8. 加密哈希函式（Cryptographic Hash Function）的特定校驗和

9.8.1. 軟體包的校驗和比不上軟體包大小的十萬之一

9.8.2. 使用這種長度的校驗和偵測錯誤，其失敗的概率極其微小，在現實中幾乎不可能失敗

9.8.2.1. 尤其是在惡意敵人而非糟糕信道的隨機變動對資訊做出改變時

10. 定位把戲

10.1. The Pinpoint Trick

10.1.1. 能讓你迅速定位一處錯誤

10.2. 二維奇偶校驗碼

10.2.1. Two-Dimensional Parity

10.2.2. 被形容為二維，是因為訊息被放在有兩個維度的表格（行和列）中

10.3. 如果你有一條長訊息，就將其打碎成16位數長的“塊”，并單獨處理每“塊”資料

10.4. 如果訊息比16個數字短，就用0把它補成16位數

10.5. 示例

10.5.1. 4 8 3 7 5 4 3 6 2 2 5 6 3 9 9 7

10.5.2.

4 8 3 7

5 4 3 6
2 2 5 6
3 9 9 7

10.5.2.1. 重新排列成一個從左往右、自上向下讀的方框

10.5.3.

4 8 3 7 2

5 4 3 6 8
2 2 5 6 5
3 9 9 7 8

10.5.3.1. 算每一行的校驗和，并添加在每行的右側

10.5.4.

4 8 3 7 2

5 4 3 6 8
2 2 5 6 5
3 9 9 7 8
4 3 0 6

10.5.4.1. 算每一欄的簡單校驗和，并將其添加在每列的底部

10.5.5. 4 8 3 7 2 5 4 3 6 8 2 2 5 6 5 3 9 9 7 8 4 3 0 6

10.5.5.1. 重新排列所有數，讓其能以一次一個數的方式被存盤或傳輸

10.5.5.2. 從左往右、自上向下的方式讀數

10.5.6. 4 8 3 7 2 5 4 3 6 8 2 7 5 6 5 3 9 9 7 8 4 3 0 6

10.5.7.

4 8 3 7 2 2

5 4 3 6 8 8
2 7 5 6 5 0
3 9 9 7 8 8
4 3 0 6
4 8 0 6

10.5.7.1. 不同之處的位置正好說明了通信錯誤出現的位置

10.5.7.2. 錯誤同時被定位和糾正了

11. 里德–所羅門（Reed-Solomon）代碼

11.1. 能被用來糾正每個代碼字中的眾多錯誤

11.2. 基于一個名為有限域代數（Finite Field Algebra）的數學分支,結合了階梯校驗和及二維定位把戲的特色

11.3. CD、DVD和計算機硬碟中都用到了

12. 現實中的運用

12.1. 一般用于偵測而非糾正錯誤

12.2. 以太網

12.2.1. CRC-32

12.3. 軟體包

12.3.1. MD5

12.3.1.1. 約40位數

12.3.2. SHA-1

12.3.2.1. 約50位數

12.3.3. SHA-256

12.3.3.1. 約75位數

12.3.4. SHA-512

12.3.4.1. 約150位數

12.4. 低密度奇偶校驗碼（Low-Density Parity-check Codes）

標籤：其他

上一篇：sakuya726's 2023 ICPC China SiChuan Provincial Programming Contest（ICPC2023四川省賽）游記隨筆

下一篇：返回列表