你也能懂的數據編碼入門

作者：Chris Budd

翻譯：太陽騎士07

審校：山寺小沙彌

我生活在充滿各類信息的社會。人們可以輕鬆的與地球另一端的同胞交流。這就是為什麼21世紀又被稱作信息時代。但是無論信息以什麼形式傳播，通過電話，互聯網或者衛星，都有可能在傳播過程中混入一些錯誤。背景雜訊，系統錯誤，甚至宇宙射線都可能打亂我們傳遞的信息。幸運的是，人類提出了一些編碼數據的方式，讓傳輸中的錯誤可以被檢測到甚至糾正。下面我們簡單介紹一下這類編碼是如何起作用的。

錯誤檢測碼

早在人們用手抄來實現書籍複製的時候，糾錯的需求也隨之出現了。當然對於重要的手抄本，比如律法或者行政命令，保證手抄本無錯誤是非常重要的。但是，逐一檢查每個詞是一個極其費時費力的過程。所以人們想出了一些替代方案，比如統計原文每個段落的單詞數，再數一數抄寫得到的複製本中對應的單詞數，如果兩者不一致，說明一定出了問題。

現代數字信息是由很多0和1組成的序列。當我們採用如同上面一樣思路來檢查我們的信息時，通常會涉及到所謂的哈希函數。需要傳遞的信息序列通過一個哈希函數計算後會得到一小段數據。我們將這段數據貼在需要傳遞的數據後面。接收者就可以拿接受到的信息利用同一個哈希函數重新這段數據，並與接受到的數據尾部結果對比，如果不一致說明傳遞過程引入了錯誤。

舉個最簡單的例子，我們就將所有需要傳遞的信息序列按位加在一起，按照二進位的運演算法則：0+0=0,0+1=1,1+0=1,1+1=0，最後我們會得到一個0或者1，將它放在數據序列最後再傳遞數據，比如開始信息為111，則傳遞時候變成1111，如果開始為101，傳遞出的信息為1010。收到信息的人檢查每一位的和就可以判斷信息是否可能出錯。

另外一個更常見的例子是商品上的條形碼，條形碼通常按照UPC-A或者EAN-13標準編碼。以UPC-A為例，其由12位數字組成，第一位一般表示生產者的國籍或者其他特定信息，比如ISBN號。第2到6位放在一起表示產品生產商編號，第7到11位放在一起表示產品的編號，最後一位是矯正位，作用和上面一致，可以糾正掃碼時候出現的錯誤。

同樣的手法也被用在信用卡卡號上，其運用了Luhn演算法（專門用來計算10進位數列的一種演算法）來計算糾正位。

錯誤糾正碼

當我們發現得到的信息有錯誤時，我們會怎麼做呢？當然有很多辦法。比如最簡單有效的，讓整個系統停下來，直到問題被解決。比如大家都遇見過的windows藍屏。

之所以會這樣，是因為一般不做任何處理比做一些明知道是錯的事情更好。然而我們在這種情況下，一般可以做的事只有重啟系統，這樣我們很可能會漏掉系統運行過程中得到的其他信息。

第二種處理方法叫自動重複請求。顧名思義，我們重新索取傳遞中出問題的信息直到我們認為信息正確為止。這廣泛運用在互聯網通訊。當然生活中也會遇到，在超市裡你買的商品條形碼第一次掃描沒成功，一般你都會再掃一遍。

然而有時候這種重複操作也不可行，比如我們需要實時通訊，像在衛星通訊，行動電話或者讀取CD中。這些情況下我們必須試圖修正錯誤。通常的辦法是向傳遞的數字序列里加入一些多餘的位用於修復可能發生的錯誤。其簡單的原理是一些字母編碼不同於其他字母，當發生少量錯誤時候，它們彼此應該依然不同。這種糾錯碼最先由貝爾實驗室的理查德·衛斯里·漢明（Richard Wesley Hamming）於1947年發明。（譯註：他也因此獲得了1968年圖靈獎）

為了理解糾錯碼是如何工作的，我們先定義兩個序列的hamming距離，其就是兩個序列對應不同位數的個數，比如111010和101111的hamming距離就是3，因為顯然它們有三位不一樣。如果雜訊改變了這兩個序列其中一位，我們依然可以分辨它們。同樣的，我們可以給字母編碼使不同字母編碼之間的hamming距離足夠大，使少量錯誤發生時候我們依然能分辨出來。

舉個簡單例子，0到7這8個數字寫成二進位，為

000 (0) 001 (1) 010 (2) 011 (3)

100 (4) 101 (5) 110 (6) 111 (7)

顯然每個數字編碼之間最小的hamming距離為1，比如011(3)發生一位錯誤就可能變成010(2)顯然這種編碼沒有糾錯能力。

我們在上面的編碼後面每個再加三位，變成：

000 000 (0) 001 110 (1) 010 011 (2) 011 101 (3)

100 101 (4) 101 011 (5) 110 110 (6) 111 000 (7)

這樣每個數字編碼之間的hamming距離變為3.假設錯誤發生概率很低，每個編碼傳遞時候最多只能發生一個錯誤，我們就可以糾正這種錯誤，比如我們傳遞101 011 (5)時候，接受者得到的序列變成了100 011，那接受者就可以尋找離得到序列的hamming距離最小的編碼，即101 011，其與結果序列的hamming距離為1，錯誤就得到了糾正。

星際航行，Facebook和CD

所有錯誤糾正碼都是同樣的設計，受到一個序列後，如果不在編碼表里，我們就尋找一個離它最近的編碼。當然設計一套編碼方案是非常複雜的，需要很多高深的數學知識。但最基本的都需要每個編碼之間儘可能的不同。此外，一個優秀的編碼方案要求糾正錯誤時候儘可能的高效可靠。

1960年，里德和所羅門提出用他們名字命名的RS碼（Reed-solomon codes）。它的第一個大規模商業運用是1982年的CD上面，用於恢復被刮傷的CD上面的音樂。儘管在很多地方，RS碼漸漸被更容易並行的LDPC碼取代，但是它現在仍廣泛用於數字存儲和數字通訊里。RS碼最常用於大規模存儲器，糾正由儲存介質缺陷造成的偶發錯誤，平均32比特數據可以糾正2比特錯誤。值得一提的是，1977年發射升空的旅行者一號，它與地球的通訊就採用RS碼編碼，它向地球傳回了土星、木星和其他一些遙遠星星的圖片。

今天最大的RS碼使用者是Facebook。Facebook或許是現在世界上最大信息庫，每天約有3億張照片被存儲在Facebook上。這些信息被分散存在世界各個數據伺服器上，雖然每個數據存儲器發生錯誤的可能非常小，但是由於Facebook獲得的數據量太大，造成必須利用RS碼糾正或許每時每刻都會發生在某個存儲器磁碟的錯誤，保證Facebook的正常運轉。

數學細節

最後一部分我們將給有興趣的同學一些數學細節。研究如何高效編碼的學科被稱為編碼理論，是很重要的應用數學分支之一。

我們先介紹Hamming（7，4）碼。它是一種3個冗餘位4個信息位組成的編碼，如果x是序列x=(d1,d2,d3,d4)，傳輸的信息是y=(p1,p2,d1,p3,d2,d3,d4)， p1,p2,p3都是冗餘位，如何確定它們可以參考下圖，我們要求選定 p1,p2,p3使得每個圈裡相加都必須為0。

即必須有

p1+d1+d2+d4=0

p2+d3+d1+d4=0

p3+d3+d2+d4=0

比如 x=(1,1,0,1),可以計算出y=(1,0,1,0,1,0,1)

如果我們收到一個錯誤信息比如y=(1,0,1,0,1,1,1)，我們重新計算每個圈的位數的和，如果為1說明該圈內某個量出現了錯誤。對於我們的例子y=(1,0,1,0,1,1,1)，簡單計算得到只有紅色和藍色的圈內的求和為1，那麼我們知道是d3位出現了錯誤。

實際上，RS碼的構造是先將需要傳遞的n位信息映射到多項式的係數上的，傳遞的數據實際上是n+t維多項式的係數（t為冗餘位數目）。不過神奇的是，正如Hamming（7，4）碼一樣，我們可以寫出編碼結果和原始信息之間的矩陣，熟悉近世代數的同學或許直接就看出這是有限域GF(2)上面的線性空間之間的線性變換。換言之我們似乎利用了線性代數和多項式理論的某種聯繫，這就是Galois理論，由偉大的法國數學家Galois在其年僅19歲時候提出。

原文鏈接：

https://plus.maths.org/content/error-correcting-codes

推薦閱讀：