前向糾錯(cuò)—FEC

前向糾錯(cuò)（FEC）是增加數(shù)據(jù)通信的可信度的方法。

前向的意義是糾錯(cuò)過程為單方向的，沒有錯(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)行解碼，從而找出在傳輸過程中產(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)說，前向糾錯(cuò)(FEC)就是在數(shù)據(jù)中添加冗余進(jìn)行傳輸，檢驗(yàn)出錯(cuò)誤后通過冗余可以恢復(fù)原本的數(shù)據(jù)。漢明碼是一種可用于前向糾錯(cuò)（FEC）的編碼和解碼方式。

一

奇偶校驗(yàn)

漢明碼使用到了奇偶校驗(yàn)的方法，所以先復(fù)習(xí)一下——奇偶校驗(yàn)。

示例中高亮位為校驗(yàn)位，如果傳輸過程中，某一數(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)位寫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)位寫1。

二

漢明碼

1

什么是冗余

冗余，在漢明碼中是附加在數(shù)據(jù)中的校驗(yàn)位，它是附加在數(shù)據(jù)的比特位之間，是一種二進(jìn)制位，可以通過冗余位來(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

始終假設(shè)，只有一個(gè)錯(cuò)誤存在其中。

如果，只有C1區(qū)錯(cuò)誤，C2和C3區(qū)沒有錯(cuò)誤，根據(jù)這個(gè)條件，可以看出，C2中2，3，5，6是沒有錯(cuò)誤的，C3中4，5，6，7沒有錯(cuò)誤，說明出錯(cuò)的是1。再來(lái)一次，如果C2和C3區(qū)有錯(cuò)誤，C1區(qū)沒有錯(cuò)誤，這次我們可以排除C1中1，2，4，5沒有錯(cuò)誤，C2和C3只有一個(gè)錯(cuò)誤，則出錯(cuò)的肯定是6。

（圖 2-1）

3

編碼

接下來(lái)，我們開始編碼了，使用奇校驗(yàn)方式，還是上面那個(gè)數(shù)字為例：0x9B，二進(jìn)制表示位1001 1011，這是一個(gè)8位的數(shù)據(jù)，所以冗余位的個(gè)數(shù)位4，總的數(shù)據(jù)位數(shù)為12。

到這里，又出現(xiàn)了一個(gè)問題，冗余碼放哪些位置呢？前面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)，我們開始分組：

①二進(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ù)傳輸過程中，如果沒有錯(cuò)誤，校驗(yàn)通過，則皆大歡喜。如果數(shù)據(jù)出錯(cuò)了呢，我們便要進(jìn)行檢錯(cuò)（找到錯(cuò)誤）和糾錯(cuò)（糾正錯(cuò)誤）。在此之前，我們還是要重復(fù)一下，漢明碼最多只能糾錯(cuò)一個(gè)比特位的數(shù)據(jù)錯(cuò)誤。我們接下來(lái)開始。

假設(shè)數(shù)據(jù)位編號(hào)為7的數(shù)據(jù)，在傳輸過程中，不小心，從”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)，說明這一組數(shù)據(jù)中某一個(gè)位出錯(cuò)。因?yàn)橐獫M足奇校驗(yàn)，所以需要補(bǔ)1滿足。

（圖 2-6）

②奇校驗(yàn)第二組：目前數(shù)據(jù)位11，10，7，6，3，2數(shù)據(jù)表示為000011，但是此時(shí)數(shù)據(jù)位中1的個(gè)數(shù)為2，不滿足奇校驗(yàn)，說明這一組數(shù)據(jù)中某一個(gè)位出錯(cuò)。因?yàn)橐獫M足奇校驗(yàn)，所以需要補(bǔ)1滿足。

（圖 2-7）

③奇校驗(yàn)第三組：目前數(shù)據(jù)位12，7，6，5，4數(shù)據(jù)表示為10010，但是此時(shí)數(shù)據(jù)位中1的個(gè)數(shù)為2，不滿足奇校驗(yàn)，說明這一組數(shù)據(jù)中某一個(gè)位出錯(cuò)。因?yàn)橐獫M足奇校驗(yàn)，所以需要補(bǔ)1滿足。

（圖 2-8）

④奇校驗(yàn)第四組：目前數(shù)據(jù)位12，11，10，9，8數(shù)據(jù)表示為10011，此時(shí)數(shù)據(jù)位中1的個(gè)數(shù)為1，滿足奇校驗(yàn)，說明這 一組數(shù)據(jù)正確。只需要補(bǔ)0。

（圖 2-9）

糾錯(cuò)：

重新校驗(yàn)之后，把補(bǔ)上的數(shù)位按照從高位到低位排列得出：0111，也就是7。所以，錯(cuò)誤的數(shù)位編號(hào)為7，只需要將收到的數(shù)據(jù)的第七位取反，即得到正確的發(fā)送方發(fā)送的數(shù)據(jù)：1001 1101 0111。