糾錯碼是個什么東西

引出

網(wǎng)絡(luò)中的通信基于TCP和UDP兩個通信協(xié)議, 這大家都知道的, 什么TCP的三次握手等等, 面試經(jīng)常被問到. 三次握手是為了保證連接的正確建立. 但是, 在通信的時候, 你如何保證你的消息正確送達了呢? 有人說了, 有收到請求的響應(yīng)包. 但我說的不是這個,

比如說, 你發(fā)送了一個數(shù)字1, 你如何保證接受方收到的數(shù)字也是1呢? 畢竟, 在網(wǎng)絡(luò)中環(huán)境如此復(fù)雜, 就算是物理上也不能保證數(shù)據(jù)一定是不變的啊. 比如有一個機房在上海, 你在北京訪問, 那數(shù)據(jù)是要途徑一千多公里的, 在這個傳輸?shù)倪^程中會受到各種干擾, 很難保證數(shù)據(jù)不會失真.

這個時候, 糾錯碼出現(xiàn)了. 簡單介紹一下, 其中所有有關(guān)數(shù)學的內(nèi)容的去掉了, 畢竟太高深, 咱也不懂.

思考

因為計算機傳輸中只存在0和1, 所以可以簡單將其類比為數(shù)字.

想象一個場景, 你需要將一組數(shù)字發(fā)送給B, 在發(fā)送的過程中, 每個數(shù)字都有20%的概率變成其他數(shù)字(途中收到干擾導(dǎo)致失真). 你們應(yīng)該如何保證接收到的數(shù)字與發(fā)送的數(shù)字一致呢?

假定這組數(shù)字是: 123456789

方案一

根據(jù)概率論, 每個數(shù)字20%的概率會錯亂, 也就是有80%是正確的. 那只要樣本足夠多, 那出現(xiàn)次數(shù)最多的就是正確的.

比如, 發(fā)送了5次, 收到的內(nèi)容是:

123456781

127456789

623456789

123456789

123459789

將每一位單獨拿出來, 找到出現(xiàn)次數(shù)最多的數(shù)字就是正確的數(shù)字.

但是, 這樣不能保證完全正確, 畢竟是概率事件, 需要通過增大樣本數(shù)量來增加準確率. 只要傳輸?shù)拇螖?shù)足夠多, 就能夠?qū)㈠e誤的概率降低到足夠小.

很好, 這樣確實能解決問題. 但是, 如果只是通信間傳輸幾k的數(shù)據(jù)還好, 如果下載一個1G的電影, 為了糾錯, 需要你耗費10G的流量下載10遍, 你能接受么?

方案二

方案一被pass了. 既然多次傳輸不行, 又該如何是好呢? 單次傳輸?shù)脑? 僅僅依靠消息本身是肯定無法保證可靠的.

換個角度想一下, 既然每個數(shù)字的出錯概率是20%, 那么如果將1個數(shù)字映射到4個數(shù)字上面, 整體出錯的概率就下降了. 為了方便理解, 使用英文來表示映射關(guān)系, 即1(one), 2(two)...

如果你收到了一個數(shù)字345, 告訴你其中可能存在錯誤, 你是無法知道它原本的數(shù)字是什么的. 但如果你收到的是 ofe, 你應(yīng)該能夠很快想到它是 one, 并將其還原.

這個時候, 假設(shè)你收到的數(shù)據(jù)是這樣的: one tno shree four fiae . 你應(yīng)該能夠很快將其還原為: 12345 . 只需要檢查每個單詞, 若是有效的直接轉(zhuǎn)換, 若是無效的則轉(zhuǎn)換為最接近的單詞.

當然, 計算機在傳輸過程中是無法傳輸英文的, 所以將數(shù)字映射到另一個較長的數(shù)字(編碼)上去. 這個編碼就是 漢明代碼. 如下:

0000 -> 0000000

0001 -> 0001011

0010 -> 0010111

...

將每一個4位都轉(zhuǎn)換為7位. 這種方案存在匹配后的值是一個較接近的錯誤的值么? 據(jù)說不會, 涉及到數(shù)學領(lǐng)域, 沒太懂.

至此, 其實糾錯的任務(wù)已經(jīng)接近完成了. 通過數(shù)據(jù)的冗余, 已經(jīng)可以將出錯的概率降低到很小了.

方案三

能否使用更少的數(shù)據(jù)來進行糾錯呢? 下面介紹的就是了, 一種稱為校驗和的手段. 這種方法僅僅用來校驗數(shù)據(jù)是否出錯, 但不會對數(shù)據(jù)進行修復(fù).

比如你需要傳輸?shù)臄?shù)字是: 4567.

在后邊添加一位數(shù)字作為校驗數(shù)字, 校驗數(shù)字的生成規(guī)則是四個數(shù)字的和取個位數(shù). 即: 4+5+6+7=22, 校驗數(shù)字為 2.

當接到45672 這個數(shù)字時, 只需要進行簡單的計算, 就可以知道數(shù)據(jù)是否正確. 其中任何一個數(shù)字出錯, 結(jié)果都不會是2. 但是, 如果有兩個數(shù)字出錯呢? 你收到的數(shù)字是: 44772. 你通過計算發(fā)現(xiàn)校驗數(shù)字是2. 嘿嘿.

也就是說, 一個校驗數(shù)字只能保證一位出錯的情況, 這時通過添加校驗數(shù)字, 通過另外一個生成規(guī)則再生成一個校驗數(shù)字添加到后邊(這里不能使用同一個生成規(guī)則), 就可以處理兩位出錯的情況了. 但是三位出錯呢? 為了保證完全校驗, 就需要添加更多位數(shù)的校驗數(shù)字.

但是如果是一個100mb的文件, 總不能用于校驗的大小也是100mb吧. 勿慌, 只需要一個100位的數(shù)字進行校驗. 這里又涉及數(shù)學領(lǐng)域了, 其出錯的概率微乎其微, 幾乎可以忽略.

還記得在各個官網(wǎng)下載文件的時候附送的MD5校驗碼嗎? 沒錯, 就是它了. 可以校驗文件在傳輸過程中是否被損壞或是否被篡改.

方案四

上面是添加校驗數(shù)字的方案只能夠檢測數(shù)據(jù)是否出錯, 而不能夠?qū)Τ鲥e的數(shù)據(jù)進行修復(fù). 現(xiàn)在將校驗數(shù)字的思想改進一下, 使其可以對錯誤數(shù)據(jù)進行修復(fù).

假設(shè)我們發(fā)送的數(shù)字是: 12341234123412134

將其每4位分開, 并分別計算其行和列的校驗和. 如下圖:

然后, 將其鋪開進行傳輸: 123401234012340123404826

假如, 接收到的數(shù)據(jù)中有一位出錯了, 數(shù)據(jù)變成了下面這種:

你通過計算, 發(fā)現(xiàn)第二行和第三列出現(xiàn)問題, 很快就可以定位到數(shù)字5. 計算第三列校驗和: 3+5+3+3=14, 個位為4. 將5-2, 得到預(yù)測的原始數(shù)字3. 然后在計算第二行的校驗和是否為0. 完成糾錯. 最后將糾正后的正確的數(shù)字從中取出來. 得到原始的數(shù)據(jù): 1234123412341234.

這種糾錯方式被稱為: 二維奇偶校驗碼.

計算機硬盤, 網(wǎng)絡(luò)通信等都有著糾錯碼的身影, 它保證了數(shù)據(jù)的傳輸可靠. 在TCP的每個包中都存在校驗和內(nèi)容, 若校驗出錯, 則包會被直接丟棄.

簡單說一下...

關(guān)于找一找教程網(wǎng)

本站文章僅代表作者觀點，不代表本站立場，所有文章非營利性免費分享。

本站提供了軟件編程、網(wǎng)站開發(fā)技術(shù)、服務(wù)器運維、人工智能等等IT技術(shù)文章，希望廣大程序員努力學習，讓我們用科技改變世界。

[糾錯碼簡介]http://www.zyiz.net/tech/detail-134151.html

總結(jié)

以上是生活随笔為你收集整理的java 数据纠错,纠错码简介的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。