糾錯碼簡介
糾錯碼是個什麼東西
引出
網路中的通訊基於TCP和UDP兩個通訊協議, 這大家都知道的, 什麼TCP的三次握手等等, 面試經常被問到. 三次握手是為了保證連接的正確建立. 但是, 在通訊的時候, 你如何保證你的消息正確送達了呢? 有人說了, 有收到請求的響應包. 但我說的不是這個,
比如說, 你發送了一個數字1, 你如何保證接受方收到的數字也是1呢? 畢竟, 在網路中環境如此複雜, 就算是物理上也不能保證數據一定是不變的啊. 比如有一個機房在上海, 你在北京訪問, 那數據是要途徑一千多公里的, 在這個傳輸的過程中會受到各種干擾, 很難保證數據不會失真.
這個時候, 糾錯碼出現了. 簡單介紹一下, 其中所有有關數學的內容的去掉了, 畢竟太高深, 咱也不懂.
思考
因為電腦傳輸中只存在0和1, 所以可以簡單將其類比為數字.
想像一個場景, 你需要將一組數字發送給B, 在發送的過程中, 每個數字都有20%的概率變成其他數字(途中收到干擾導致失真). 你們應該如何保證接收到的數字與發送的數字一致呢?
假定這組數字是: 123456789
方案一
根據概率論, 每個數字20%的概率會錯亂, 也就是有80%是正確的. 那隻要樣本足夠多, 那出現次數最多的就是正確的.
比如, 發送了5次, 收到的內容是:
- 123456781
- 127456789
- 623456789
- 123456789
- 123459789
將每一位單獨拿出來, 找到出現次數最多的數字就是正確的數字.
但是, 這樣不能保證完全正確, 畢竟是概率事件, 需要通過增大樣本數量來增加準確率. 只要傳輸的次數足夠多, 就能夠將錯誤的概率降低到足夠小.
很好, 這樣確實能解決問題. 但是, 如果只是通訊間傳輸幾k的數據還好, 如果下載一個1G的電影, 為了糾錯, 需要你耗費10G的流量下載10遍, 你能接受么?
方案二
方案一被pass了. 既然多次傳輸不行, 又該如何是好呢? 單次傳輸的話, 僅僅依靠消息本身是肯定無法保證可靠的.
換個角度想一下, 既然每個數字的出錯概率是20%, 那麼如果將1個數字映射到4個數字上面, 整體出錯的概率就下降了. 為了方便理解, 使用英文來表示映射關係, 即1(one), 2(two)…
如果你收到了一個數字345, 告訴你其中可能存在錯誤, 你是無法知道它原本的數字是什麼的. 但如果你收到的是 ofe, 你應該能夠很快想到它是 one, 並將其還原.
這個時候, 假設你收到的數據是這樣的: one tno shree four fiae . 你應該能夠很快將其還原為: 12345 . 只需要檢查每個單詞, 若是有效的直接轉換, 若是無效的則轉換為最接近的單詞.
當然, 電腦在傳輸過程中是無法傳輸英文的, 所以將數字映射到另一個較長的數字(編碼)上去. 這個編碼就是 漢明程式碼. 如下:
- 0000 -> 0000000
- 0001 -> 0001011
- 0010 -> 0010111
- …
將每一個4位都轉換為7位. 這種方案存在匹配後的值是一個較接近的錯誤的值么? 據說不會, 涉及到數學領域, 沒太懂.
至此, 其實糾錯的任務已經接近完成了. 通過數據的冗餘, 已經可以將出錯的概率降低到很小了.
方案三
能否使用更少的數據來進行糾錯呢? 下面介紹的就是了, 一種稱為校驗和的手段. 這種方法僅僅用來校驗數據是否出錯, 但不會對數據進行修復.
比如你需要傳輸的數字是: 4567.
在後邊添加一位數字作為校驗數字, 校驗數字的生成規則是四個數字的和取個位數. 即: 4+5+6+7=22, 校驗數字為 2.
當接到45672 這個數字時, 只需要進行簡單的計算, 就可以知道數據是否正確. 其中任何一個數字出錯, 結果都不會是2. 但是, 如果有兩個數字出錯呢? 你收到的數字是: 44772. 你通過計算髮現校驗數字是2. 嘿嘿.
也就是說, 一個校驗數字只能保證一位出錯的情況, 這時通過添加校驗數字, 通過另外一個生成規則再生成一個校驗數字添加到後邊(這裡不能使用同一個生成規則), 就可以處理兩位出錯的情況了. 但是三位出錯呢? 為了保證完全校驗, 就需要添加更多位數的校驗數字.
但是如果是一個100mb的文件, 總不能用於校驗的大小也是100mb吧. 勿慌, 只需要一個100位的數字進行校驗. 這裡又涉及數學領域了, 其出錯的概率微乎其微, 幾乎可以忽略.
還記得在各個官網下載文件的時候附送的MD5校驗碼嗎? 沒錯, 就是它了. 可以校驗文件在傳輸過程中是否被損壞或是否被篡改.
方案四
上面是添加校驗數字的方案只能夠檢測數據是否出錯, 而不能夠對出錯的數據進行修復. 現在將校驗數字的思想改進一下, 使其可以對錯誤數據進行修復.
假設我們發送的數字是: 12341234123412134
將其每4位分開, 並分別計算其行和列的校驗和. 如下圖:
然後, 將其鋪開進行傳輸: 123401234012340123404826
假如, 接收到的數據中有一位出錯了, 數據變成了下面這種:
你通過計算, 發現第二行和第三列出現問題, 很快就可以定位到數字5. 計算第三列校驗和: 3+5+3+3=14, 個位為4. 將5-2, 得到預測的原始數字3. 然後在計算第二行的校驗和是否為0. 完成糾錯. 最後將糾正後的正確的數字從中取出來. 得到原始的數據: 1234123412341234.
這種糾錯方式被稱為: 二維奇偶校驗碼.
電腦硬碟, 網路通訊等都有著糾錯碼的身影, 它保證了數據的傳輸可靠. 在TCP的每個包中都存在校驗和內容, 若校驗出錯, 則包會被直接丟棄.
簡單說一下…
