糾錯碼和壓縮算法是同一枚硬幣的兩面。
兩者都來自于對冗余的想法。 糾錯碼被視為向消息或文件中添加冗余的原則性方法。而壓縮算法正好相反，他們會從消息或文件中移除冗余。
壓縮和糾錯并不是彼此抵消的，相反，好的壓縮算法會移除抵消冗余，而糾錯編碼會增加另一種更高效的冗余。
因此首先壓縮一條信息，再往里面添加一些糾錯碼的做法十分常見。 下面分別介紹兩者的具體內(nèi)容：

糾錯碼trick

如果使用正確的技巧，即使是極端不可靠的通信頻道也可以以極低的錯誤率傳輸數(shù)據(jù)。

1、重復(fù)技巧

要確保一些信息被正確傳輸，你只需要重復(fù)幾次該信息。

如果你的賬戶余額是5213.75美元，但不幸的是，網(wǎng)絡(luò)不穩(wěn)定，每個數(shù)字都有20%的概率變成其他數(shù)字

通過運用重復(fù)技巧，可以推測真正的余額：假設(shè)你請求傳輸余額5次，并收到如下反饋：

只要我們增加重新傳輸?shù)拇螖?shù)，直到可靠性高到我們滿意為止。

相反，如果一個惡意實體故意干擾傳輸，并選擇制造某些錯誤，重復(fù)技巧將變得不可靠。

并且在下載一個大型軟件，顯然傳輸多次以確保正確性是不成熟的。

2、冗余技巧

基本原則：不能只發(fā)送原始消息，要發(fā)送一些多余的東西以增加可靠性，這里我們討論的是把原始消息轉(zhuǎn)換成一條更加長的冗余消息，原始消息會被刪除。

還是以銀行余額為例：

如果你的賬戶余額是5213.75美元

我們用英語單詞簡單地拼出余額：

five two one three point seven five

由于信道糟糕，這條消息中約20%的字符會變成隨機(jī)字符，這條消息可能會變成：

fiqe kwo one thrxp point sivpn fivq

如果我們告訴你對消息中的任何單個變化進(jìn)行可靠偵測以及糾正變得顆星，我們絕對可以猜出原始消息中的單詞。

但是如果我告訴你"367"代表了一個數(shù)，但其中一個數(shù)字被替換了，你就沒辦法直道原始數(shù)字是多少了，因為這條消息中沒有冗余。

冗余和讓消息變長有關(guān)，消息的每一部分都應(yīng)該符合某種已知模式。通過這種方法，任何變化都能首先被識別，然后被糾正。

冗余的工作機(jī)理：消息由符號組成

要傳輸一條消息：

1、首先要找出每個符號，并將符號轉(zhuǎn)譯成對應(yīng)的代碼字。

2、然后，將轉(zhuǎn)換的消息通過不可靠信道發(fā)送。

3、當(dāng)消息被接收時，查看消息的每個部分，檢查其是否為有效的代碼字。如果是有效的，只需將其轉(zhuǎn)換為相應(yīng)的符號，如果不是有效的代碼字，你就要找出它和哪個代碼字最匹配

由理查德漢明于貝爾實驗室發(fā)明的代碼和我們相比最明顯的區(qū)別就是將所有事情都通過0和1完成：

在編碼時，每一組4位數(shù)字都加入了冗余，由此產(chǎn)生了一個7位數(shù)的代碼字。

解碼時，首先尋找完全匹配，否則選擇最接近匹配。這里我們不深究7位數(shù)代碼字中的設(shè)計。

3、冗余和重復(fù)比較

通常用雜項(overhead)衡量糾錯系統(tǒng)的成本。雜項就是為確保消息被正確接收而發(fā)送的多余信息。

重復(fù)技巧的雜項數(shù)量巨大，因為你必須發(fā)送數(shù)份完整消息。

冗余技巧的雜項取決于使用的代碼字的具體類型。

4、校驗和技巧

上面的兩個技巧都屬于同時偵測和糾正數(shù)據(jù)中錯誤的方法。

還有一種思路：可以先不管糾錯，而是將精力集中在偵測錯誤上。對于許多應(yīng)用場景，只偵測到一個錯誤就足夠了，然后請求再發(fā)送一份數(shù)據(jù)即可，可以一直請求拷貝，直到得到完全無誤的拷貝，我們稱之為校驗和技巧。

簡單校驗和：將消息中的所有數(shù)字相加，只保留結(jié)果的最后一位數(shù)作為簡單校驗和

例：假設(shè)消息為 4 6 7 5 6，所有數(shù)字之和：4+6+7+5+6=28，保留最后一位數(shù)，因此這條消息的簡單校驗和是8.

在發(fā)送原始消息前，將原始消息的校驗和附加到消息末尾即可。別人在接收消息后，就能再次計算校驗和，并和你發(fā)送的校驗和比較，看收到的消息是否正確。

缺點：簡單校驗和最多只能在消息中偵測出一處錯誤，如果有兩個或者更多錯誤，簡單校驗和可能就偵測不到了。

我們定義一種新的校驗和，階梯校驗和：每個數(shù)都和該數(shù)字所在的位階相乘，每個數(shù)都比前一個數(shù)大一個位階，最后只保留最后一位數(shù)。

假如消息為4 6 7 5 6，階梯校驗和計算：

(1x4) +(2x6)+(3x7)+(4x5)+(5x6)=87,保留最后一位數(shù)，為7，所以階梯校驗和為7；

只要錯誤不超過兩處，你就能用這兩種方法，偵測到錯誤。

上面描述的校驗和技巧只生成了兩個校驗和數(shù)字，但真正的校驗和通常會生成很長的數(shù)字。

重點是，校驗和的長度是固定的。對非常長的消息來說，即使一個較大的校驗和，最終和消息本身相比也極小。(校驗和長度越長，偵測錯誤失敗概率越小，在現(xiàn)實中幾乎不可能失敗)

當(dāng)存在惡意攻擊而非糟糕信道時，采用加密哈希函數(shù)的特定校驗和效果較好。

5、定位技巧

此處介紹一種特殊的冗余技巧，它能讓你迅速定位一處錯誤，我們稱之為定位技巧。

假設(shè)消息有16個數(shù)字(如果有一條長消息，將其打碎成16位數(shù)據(jù)的“塊”，并單獨處理每塊數(shù)據(jù)；如果消息比16個數(shù)字短，就用0把它補成16位數(shù))

第一步：重新排列消息中的16個數(shù)，將其排列成一個從左往右、自上向下讀的方框：

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

重新排列為：

計算每一行的簡單校驗和，并添加在每行的右側(cè)：

計算每一列的簡單校驗和，并添加在每列的底側(cè)：

重新排列所有數(shù)，讓其能以一次一個數(shù)的方式被存儲或傳輸，然后通過從左往右、自上而下的方式讀數(shù)，最后會得到如下24位數(shù)的消息：

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

把數(shù)字放入一個5x5的方框中，最后一行和最后一列都對應(yīng)隨原始消息一起被發(fā)送的校驗和數(shù)字：

接下來，計算每一行每一列4個數(shù)的簡單校驗和，在接收的校驗和值旁邊新建一行和一列：

這里會出現(xiàn)兩組校驗和：1個是你發(fā)送的，1個是你接收的

如果它們都一樣，那么可以確定收到的消息很可能是正確的。那么出一個錯誤呢？

我們可以很快定位出出錯位置，那么我們該如何糾正呢？

我們只要用一個能讓兩個校驗和都正確的數(shù)字替代出錯的那個數(shù)字就可：第二列校驗和本應(yīng)該是3，但結(jié)果是8，也就是說校驗和要減去5,7-5=2。

將糾正后的原始16位數(shù)消息從5x5的框中取出，忽略最后一行和最后一列，從左往右從上往下取出：

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

這種定位技巧我們稱之為二維奇偶校驗碼，奇偶校驗碼和簡單校驗和的意思一樣。二維奇偶校驗碼在一些真正的計算機(jī)系統(tǒng)中也有運用，但是并不如其他一些冗余技巧高效。

不過它很容易地具化并展現(xiàn)出不要求復(fù)雜數(shù)學(xué)的情況下，在計算機(jī)系統(tǒng)中的流行代碼背后發(fā)現(xiàn)并糾正錯誤。

數(shù)據(jù)壓縮trick

數(shù)據(jù)壓縮分為無損壓縮和有損壓縮

無損壓縮

無損壓縮需要了解的技巧：

1、行程長度編碼：將重復(fù)的“行程”和行程的“長度”編碼在一起；

例如：AAAAABCBCBCBCAAAADEFDEF可以被編碼為：5A、4BC、4A、2DEF

將23個字母壓縮為只有11個字母的字符串。

主要問題：數(shù)據(jù)中心重復(fù)的片段必須是相鄰的，不能有其他數(shù)據(jù)。

例如：ABABAB編碼很容易(3AB),但是ABXABYAB就行不通了。

2、同前技巧：

基于行程長度編碼的改進(jìn)：

例如下面這個數(shù)據(jù)：

VJGDNQMYLH-KW-VJGDNQMYLH-ADXSGF-OVJG

DNQMYLH-ADXSGF-VJGDNQMYLH-EW-ADXSGF

忽略連字符，首先識別數(shù)據(jù)中重復(fù)的數(shù)據(jù)塊。

已知最開始12個字母沒有重復(fù)部分，但是接下來的10個字母VJGDNQMYLH與之前的有部分重合，可以說back12,copy10(數(shù)回12個字母，直至抄到第10個字母),接下來7個字母新出現(xiàn)，不能壓縮。后面的字母又是大的重復(fù)，可以縮寫。

我們縮寫b代替back，c代替copy，指令可以被總結(jié)如下：

VJGDNQMYLH-KW-b12c10-ADXSGF-O-b17c16-b16c10-EW-b18c6

下面一個例子：

使用相同的技巧壓縮FG-FG-FG-FG-FG-FG-FG-FG，消息中有8次重復(fù)。可以使用FG-FG-FG-FGb8c8，

更簡略的寫法：FG-b2c14，在口述最開始的兩個字母之后，我們有了FG，然后收到b2c14指令，抄完兩個之后結(jié)果為FG-FG,持續(xù)抄寫，直到抄寫到14個為止。

3、更短符號技巧：

使用頻率越高，編碼越短。

具體步驟：

1、計算機(jī)使用同前技巧傳輸未經(jīng)壓縮的源文件，讓文件中絕大多數(shù)重讀的數(shù)據(jù)由短得多的指令取代，這些指令會返回并拷貝其他地方的數(shù)據(jù)

2、計算機(jī)檢查傳輸后的文件，選出經(jīng)常出現(xiàn)的符號。隨后計算機(jī)會創(chuàng)建出一張表格，用短數(shù)字碼代表經(jīng)常用到的符號，用更長的數(shù)字碼代表極少用到的符號。

3、計算機(jī)會通過直接將文件翻譯為2中的數(shù)字碼再次傳輸文件。2中計算出的數(shù)字碼表也會存儲到文件中，否則在后面不可能解碼。

有損壓縮：

有損壓縮需要了解的技巧：

1、拋棄技巧：以圖像為例，原圖像為320 x 240,每兩行或每兩列像素就拋棄一行或一列，結(jié)果得到解析度為160 x 120的新圖像。

可以發(fā)現(xiàn)，壓縮后的圖片重構(gòu)之后的有較嚴(yán)重的壓縮缺陷。

接下來講解一下jpeg技術(shù)的基本原理：

jpeg首先將整張圖片劃分為8 x 8 的小方塊，每個方塊都被單獨壓縮，在沒有被壓縮的情況下，每個方塊代表64個數(shù)字(假設(shè)為灰度圖)，如果這個方塊符合某些已知模式，如常數(shù)色(Constant Color)或漸變色(Smoothly Varying Color)的組合，那么其大部分信息都可以被拋棄，只需要存儲每個模式的級別或量即可

參考：【改變未來的九大算法】

總結(jié)

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

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