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