FEC前向糾錯(cuò)——漢明碼（FEC——Hamming Code）
前向糾錯(cuò)（FEC）,是增加數(shù)據(jù)通信的可信度的方法。前向的意義是糾錯(cuò)過(guò)程為單方向的，沒(méi)有錯(cuò)誤的信息反饋。利用數(shù)據(jù)進(jìn)行傳輸冗余信息的方法，當(dāng)傳輸中出現(xiàn)錯(cuò)誤，將允許接收器再建數(shù)據(jù)。即一種差錯(cuò)控制方式，信號(hào)在被送入傳輸信道之前會(huì)按一定的算法進(jìn)行編碼處理，加入帶有信號(hào)本身特征的冗余碼，在接收端按照相應(yīng)算法對(duì)接收到的信號(hào)進(jìn)行解碼，從而找出在傳輸過(guò)程中產(chǎn)生的錯(cuò)誤碼并將其糾正。比較經(jīng)典的編碼解碼方式例如漢明碼、BCH碼、RS碼等。
漢明碼（Hamming Code），是在電信領(lǐng)域的一種線性調(diào)試碼，以發(fā)明者理查德·衛(wèi)斯里·漢明的名字命名。漢明碼在傳輸?shù)南⒘髦胁迦腧?yàn)證碼，當(dāng)計(jì)算機(jī)存儲(chǔ)或移動(dòng)數(shù)據(jù)時(shí)，可能會(huì)產(chǎn)生數(shù)據(jù)位錯(cuò)誤，以偵測(cè)并更正單一比特錯(cuò)誤。
簡(jiǎn)單來(lái)說(shuō)，前向糾錯(cuò)(FEC)就是在數(shù)據(jù)中添加冗余進(jìn)行傳輸，檢驗(yàn)出錯(cuò)誤后通過(guò)冗余可以恢復(fù)原本的數(shù)據(jù)。漢明碼是一種可用于前向糾錯(cuò)（FEC）的編碼和解碼方式。
一、奇偶校驗(yàn)
漢明碼使用到了奇偶校驗(yàn)的方法，所以先復(fù)習(xí)一下——奇偶校驗(yàn)。
示例中高亮位為校驗(yàn)位，如果傳輸過(guò)程中，某一數(shù)據(jù)位發(fā)生錯(cuò)誤，則檢驗(yàn)便會(huì)不符合校驗(yàn)規(guī)則。
奇校驗(yàn)：所有傳送的二進(jìn)制代碼的數(shù)位（含字符的各數(shù)位和校驗(yàn)位）中，“1”的個(gè)數(shù)為奇數(shù)。
例：1001 1011——0 1001 1011因傳輸?shù)脑紨?shù)據(jù)中，1的位數(shù)為5，奇數(shù)，所以校驗(yàn)位寫(xiě)0。
偶校驗(yàn)：所有傳送的二進(jìn)制代碼的數(shù)位（含字符的各數(shù)位和校驗(yàn)位）中，“1”的個(gè)數(shù)為偶數(shù)。
例：1001 1011——1 1001 1011因傳輸?shù)脑紨?shù)據(jù)中，1的位數(shù)為5，奇數(shù)，所以校驗(yàn)位寫(xiě)1。
二、漢明碼
1、什么是冗余
冗余，在漢明碼中是附加在數(shù)據(jù)中的校驗(yàn)位，它是附加在數(shù)據(jù)的比特位之間，是一種二進(jìn)制位，可以通過(guò)冗余位來(lái)檢驗(yàn)數(shù)據(jù)錯(cuò)誤和恢復(fù)正確的數(shù)據(jù)。那么，一個(gè)數(shù)據(jù)中的冗余位，應(yīng)該是多少個(gè)，可以使用(式 2-1)計(jì)算：
2n>=m+n+1(式 2-1)
(n:冗余位位數(shù)。m:數(shù)據(jù)位數(shù)。)
例：傳輸一個(gè)8位的數(shù)據(jù)0x9B，二進(jìn)制表示為1001 1011，則計(jì)算n的結(jié)果為4：24>=8+4+1。
2、怎么分組
如下圖2-1，假設(shè)有一個(gè)7位的數(shù)據(jù)，每個(gè)位編號(hào)1，2……7。分為3組：C1,C2和C3。
C1:1,2,4,5
C2:2,3,5,6
C3:4,5,6,7
（圖2-1）
始終假設(shè)，只有一個(gè)錯(cuò)誤存在其中。
如果，只有C1區(qū)錯(cuò)誤，C2和C3區(qū)沒(méi)有錯(cuò)誤，根據(jù)這個(gè)條件，可以看出，C2中2,3,5,6是沒(méi)有錯(cuò)誤的，C3中4,5,6,7沒(méi)有錯(cuò)誤，說(shuō)明出錯(cuò)的是1。再來(lái)一次如果，C2和C3區(qū)有錯(cuò)誤，C1區(qū)沒(méi)有錯(cuò)誤。這次我們可以排除C1中1,2,4,5沒(méi)有錯(cuò)誤，C2和C3只有一個(gè)錯(cuò)誤，則出錯(cuò)的肯定是6。
3、編碼
接下來(lái)，我們開(kāi)始編碼了，使用奇校驗(yàn)方式，還是上面那個(gè)數(shù)字為例：0x9B,二進(jìn)制表示位1001 1011，這是一個(gè)8位的數(shù)據(jù)，所以冗余位的個(gè)數(shù)位4，總的數(shù)據(jù)位數(shù)為12。到這里，又出現(xiàn)了一個(gè)問(wèn)題，冗余碼放哪些位置呢？前面or后面？都不是，冗余碼（奇偶校驗(yàn)碼）穿插在數(shù)據(jù)中放置，放置的位置和冗余碼數(shù)量有關(guān)，即位置在：20，21，22，23，24……2n-1。示例為4個(gè)冗余位，則放置在第1，2，4，8位的位置上，如下圖2-2，剩下的數(shù)據(jù)位，我們順序填入需要編碼的數(shù)據(jù)，如下圖2-3。
（圖2-2）
（圖2-3）
這時(shí)候，我們發(fā)現(xiàn)了，圖中我們不僅對(duì)數(shù)據(jù)位編號(hào)，并且表示為二進(jìn)制，原因就是，數(shù)據(jù)位編號(hào)的二進(jìn)制表示，是我們進(jìn)行數(shù)據(jù)位分組的依據(jù)。接下來(lái)，我們開(kāi)始分組：
①二進(jìn)制編號(hào)第一位為1的：1，3，5，7，9，11————20
②二進(jìn)制編號(hào)第二位為1的：2，3，6，7，10，11————21
③二進(jìn)制編號(hào)第三位為1的：4，5，6，7，12 ————22
④二進(jìn)制編號(hào)第四位為1的：8，9，10，11，12————23
高亮的編號(hào)位是每組對(duì)應(yīng)填入奇偶檢驗(yàn)位的位置，對(duì)實(shí)際的數(shù)據(jù)位數(shù)采用奇校驗(yàn)：
①組：1的個(gè)數(shù)為4，因此20處填入1
②組：1的個(gè)數(shù)為2，因此21處填入1
③組：1的個(gè)數(shù)為3，因此22處填入0
④組：1的個(gè)數(shù)為2，因此23處填入1
綜上，編碼后的數(shù)據(jù)為1001 1101 0111，如圖2-4所示。
（圖2-4）
4、檢錯(cuò)和糾錯(cuò)
數(shù)據(jù)傳輸過(guò)程中，如果沒(méi)有錯(cuò)誤，校驗(yàn)通過(guò)，則皆大歡喜。如果數(shù)據(jù)出錯(cuò)了呢，我們便要進(jìn)行檢錯(cuò)（找到錯(cuò)誤）和糾錯(cuò)（糾正錯(cuò)誤）。在此之前，我們還是要重復(fù)一下，漢明碼最多只能糾錯(cuò)一個(gè)比特位的數(shù)據(jù)錯(cuò)誤。我們接下來(lái)開(kāi)始。
假設(shè)數(shù)據(jù)位編號(hào)為7的數(shù)據(jù)，在傳輸過(guò)程中，不小心，從”1“變成了”0”。如圖2-5。
（圖2-5）
檢錯(cuò)：
①奇校驗(yàn)第一組：目前數(shù)據(jù)位11，9，7，5，3，1數(shù)據(jù)表示為010111，此時(shí)數(shù)據(jù)位中1的個(gè)數(shù)為4，不滿足奇校驗(yàn)，說(shuō)明這一組數(shù)據(jù)中某一個(gè)位出錯(cuò)。因?yàn)橐獫M足奇校驗(yàn)，所以需要補(bǔ)1滿足。
②奇校驗(yàn)第二組：目前數(shù)據(jù)位11，10，7，6，3，2數(shù)據(jù)表示為000011，但是此時(shí)數(shù)據(jù)位中1的個(gè)數(shù)為2，不滿足奇校驗(yàn)，說(shuō)明這一組數(shù)據(jù)中某一個(gè)位出錯(cuò)。因?yàn)橐獫M足奇校驗(yàn)，所以需要補(bǔ)1滿足。
③奇校驗(yàn)第三組：目前數(shù)據(jù)位12，7，6，5，4數(shù)據(jù)表示為10010，但是此時(shí)數(shù)據(jù)位中1的個(gè)數(shù)為2，不滿足奇校驗(yàn)，說(shuō)明這一組數(shù)據(jù)中某一個(gè)位出錯(cuò)。因?yàn)橐獫M足奇校驗(yàn)，所以需要補(bǔ)1滿足。
④奇校驗(yàn)第四組：目前數(shù)據(jù)位12，11，10，9，8數(shù)據(jù)表示為10011，此時(shí)數(shù)據(jù)位中1的個(gè)數(shù)為1，滿足奇校驗(yàn)，說(shuō)明這一組數(shù)據(jù)正確。只需要補(bǔ)0。
糾錯(cuò)
重新校驗(yàn)之后，把補(bǔ)上的數(shù)位按照從高位到低位排列得出：0111，也就是7。所以，錯(cuò)誤的數(shù)位編號(hào)為7，只需要將收到的數(shù)據(jù)的第七位取反，即得到正確的發(fā)送方發(fā)送的數(shù)據(jù)：1001 1101 0111。
