我生活在充滿(mǎn)各類(lèi)信息的社會(huì),。人們可以輕松的與地球另一端的同胞交流,。這就是為什么21世紀(jì)又被稱(chēng)作信息時(shí)代。但是無(wú)論信息以什么形式傳播,，通過(guò)電話(huà),，互聯(lián)網(wǎng)或者衛(wèi)星，都有可能在傳播過(guò)程中混入一些錯(cuò)誤,。背景噪聲,，系統(tǒng)錯(cuò)誤，甚至宇宙射線(xiàn)都可能打亂我們傳遞的信息,。幸運(yùn)的是,，人類(lèi)提出了一些編碼數(shù)據(jù)的方式，讓傳輸中的錯(cuò)誤可以被檢測(cè)到甚至糾正,。下面我們簡(jiǎn)單介紹一下這類(lèi)編碼是如何起作用的,。

早在人們用手抄來(lái)實(shí)現(xiàn)書(shū)籍復(fù)制的時(shí)候,，糾錯(cuò)的需求也隨之出現(xiàn)了。當(dāng)然對(duì)于重要的手抄本,，比如律法或者行政命令,，保證手抄本無(wú)錯(cuò)誤是非常重要的。但是,，逐一檢查每個(gè)詞是一個(gè)極其費(fèi)時(shí)費(fèi)力的過(guò)程,。所以人們想出了一些替代方案，比如統(tǒng)計(jì)原文每個(gè)段落的單詞數(shù),，再數(shù)一數(shù)抄寫(xiě)得到的復(fù)制本中對(duì)應(yīng)的單詞數(shù)，如果兩者不一致,，說(shuō)明一定出了問(wèn)題,。

15世紀(jì)的抄寫(xiě)員，裝裱家,，翻譯家和作家Jean Miélot在他的書(shū)桌前

現(xiàn)代數(shù)字信息是由很多0和1組成的序列,。當(dāng)我們采用如同上面一樣思路來(lái)檢查我們的信息時(shí)，通常會(huì)涉及到所謂的哈希函數(shù),。需要傳遞的信息序列通過(guò)一個(gè)哈希函數(shù)計(jì)算后會(huì)得到一小段數(shù)據(jù),。我們將這段數(shù)據(jù)貼在需要傳遞的數(shù)據(jù)后面。接收者就可以拿接受到的信息利用同一個(gè)哈希函數(shù)重新這段數(shù)據(jù),，并與接受到的數(shù)據(jù)尾部結(jié)果對(duì)比,，如果不一致說(shuō)明傳遞過(guò)程引入了錯(cuò)誤。

舉個(gè)最簡(jiǎn)單的例子,，我們就將所有需要傳遞的信息序列按位加在一起,，按照二進(jìn)制的運(yùn)算法則：0+0=0,0+1=1,1+0=1,1+1=0，最后我們會(huì)得到一個(gè)0或者1,，將它放在數(shù)據(jù)序列最后再傳遞數(shù)據(jù),，比如開(kāi)始信息為111，則傳遞時(shí)候變成1111,，如果開(kāi)始為101,，傳遞出的信息為1010。收到信息的人檢查每一位的和就可以判斷信息是否可能出錯(cuò),。

另外一個(gè)更常見(jiàn)的例子是商品上的條形碼,，條形碼通常按照UPC-A或者EAN-13標(biāo)準(zhǔn)編碼。以UPC-A為例,，其由12位數(shù)字組成,，第一位一般表示生產(chǎn)者的國(guó)籍或者其他特定信息，比如ISBN號(hào),。第2到6位放在一起表示產(chǎn)品生產(chǎn)商編號(hào),，第7到11位放在一起表示產(chǎn)品的編號(hào),，最后一位是矯正位，作用和上面一致,，可以糾正掃碼時(shí)候出現(xiàn)的錯(cuò)誤,。

同樣的手法也被用在信用卡卡號(hào)上，其運(yùn)用了Luhn算法（專(zhuān)門(mén)用來(lái)計(jì)算10進(jìn)制數(shù)列的一種算法）來(lái)計(jì)算糾正位,。

當(dāng)我們發(fā)現(xiàn)得到的信息有錯(cuò)誤時(shí),，我們會(huì)怎么做呢？當(dāng)然有很多辦法,。比如最簡(jiǎn)單有效的,，讓整個(gè)系統(tǒng)停下來(lái)，直到問(wèn)題被解決,。比如大家都遇見(jiàn)過(guò)的windows藍(lán)屏,。

Windows8的藍(lán)屏死機(jī)

之所以會(huì)這樣，是因?yàn)橐话悴蛔鋈魏翁幚肀茸鲆恍┟髦朗清e(cuò)的事情更好,。然而我們?cè)谶@種情況下,，一般可以做的事只有重啟系統(tǒng)，這樣我們很可能會(huì)漏掉系統(tǒng)運(yùn)行過(guò)程中得到的其他信息,。

第二種處理方法叫自動(dòng)重復(fù)請(qǐng)求,。顧名思義，我們重新索取傳遞中出問(wèn)題的信息直到我們認(rèn)為信息正確為止,。這廣泛運(yùn)用在互聯(lián)網(wǎng)通訊,。當(dāng)然生活中也會(huì)遇到，在超市里你買(mǎi)的商品條形碼第一次掃描沒(méi)成功,，一般你都會(huì)再掃一遍,。

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

為了理解糾錯(cuò)碼是如何工作的,，我們先定義兩個(gè)序列的hamming距離,，其就是兩個(gè)序列對(duì)應(yīng)不同位數(shù)的個(gè)數(shù)，比如111010和101111的hamming距離就是3,，因?yàn)轱@然它們有三位不一樣,。如果噪聲改變了這兩個(gè)序列其中一位,，我們依然可以分辨它們。同樣的,，我們可以給字母編碼使不同字母編碼之間的hamming距離足夠大,，使少量錯(cuò)誤發(fā)生時(shí)候我們依然能分辨出來(lái)。

舉個(gè)簡(jiǎn)單例子,，0到7這8個(gè)數(shù)字寫(xiě)成二進(jìn)制,，為

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

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

顯然每個(gè)數(shù)字編碼之間最小的hamming距離為1，比如011(3)發(fā)生一位錯(cuò)誤就可能變成010(2)顯然這種編碼沒(méi)有糾錯(cuò)能力,。

我們?cè)谏厦娴木幋a后面每個(gè)再加三位,，變成：

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

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

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

所有錯(cuò)誤糾正碼都是同樣的設(shè)計(jì),，受到一個(gè)序列后，如果不在編碼表里,，我們就尋找一個(gè)離它最近的編碼,。當(dāng)然設(shè)計(jì)一套編碼方案是非常復(fù)雜的，需要很多高深的數(shù)學(xué)知識(shí),。但最基本的都需要每個(gè)編碼之間盡可能的不同,。此外，一個(gè)優(yōu)秀的編碼方案要求糾正錯(cuò)誤時(shí)候盡可能的高效可靠,。

1960年,，里德和所羅門(mén)提出用他們名字命名的RS碼（Reed-solomon codes）。它的第一個(gè)大規(guī)模商業(yè)運(yùn)用是1982年的CD上面,，用于恢復(fù)被刮傷的CD上面的音樂(lè),。盡管在很多地方，RS碼漸漸被更容易并行的LDPC碼取代,，但是它現(xiàn)在仍廣泛用于數(shù)字存儲(chǔ)和數(shù)字通訊里,。RS碼最常用于大規(guī)模存儲(chǔ)器，糾正由儲(chǔ)存介質(zhì)缺陷造成的偶發(fā)錯(cuò)誤,，平均32比特?cái)?shù)據(jù)可以糾正2比特錯(cuò)誤,。值得一提的是,，1977年發(fā)射升空的旅行者一號(hào)，它與地球的通訊就采用RS碼編碼,，它向地球傳回了土星,、木星和其他一些遙遠(yuǎn)星星的圖片。

今天最大的RS碼使用者是Facebook,。Facebook或許是現(xiàn)在世界上最大信息庫(kù),，每天約有3億張照片被存儲(chǔ)在Facebook上。這些信息被分散存在世界各個(gè)數(shù)據(jù)服務(wù)器上,，雖然每個(gè)數(shù)據(jù)存儲(chǔ)器發(fā)生錯(cuò)誤的可能非常小,，但是由于Facebook獲得的數(shù)據(jù)量太大，造成必須利用RS碼糾正或許每時(shí)每刻都會(huì)發(fā)生在某個(gè)存儲(chǔ)器磁盤(pán)的錯(cuò)誤,，保證Facebook的正常運(yùn)轉(zhuǎn),。

最后一部分我們將給有興趣的同學(xué)一些數(shù)學(xué)細(xì)節(jié)。研究如何高效編碼的學(xué)科被稱(chēng)為編碼理論,，是很重要的應(yīng)用數(shù)學(xué)分支之一,。

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

即必須有

p1+d1+d2+d4=0

p2+d3+d1+d4=0

p3+d3+d2+d4=0

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

如果我們收到一個(gè)錯(cuò)誤信息比如y=(1,0,1,0,1,1,1),，我們重新計(jì)算每個(gè)圈的位數(shù)的和，如果為1說(shuō)明該圈內(nèi)某個(gè)量出現(xiàn)了錯(cuò)誤,。對(duì)于我們的例子y=(1,0,1,0,1,1,1),，簡(jiǎn)單計(jì)算得到只有紅色和藍(lán)色的圈內(nèi)的求和為1，那么我們知道是d3位出現(xiàn)了錯(cuò)誤,。

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

編輯：山寺小沙彌