一、海明碼檢錯(cuò)/糾錯(cuò)基本思想

海明碼（Hamming Code）是一個(gè)能夠有多個(gè)校驗(yàn)位。具有檢測(cè)并糾正一位錯(cuò)誤代碼的糾錯(cuò)碼，所以也僅用于信道特性比較好的環(huán)境中。如以太局域網(wǎng)。它的檢錯(cuò)、糾錯(cuò)基本思想例如以下：
（1）將有效信息按某種規(guī)律分成若干組，每組安排一個(gè)校驗(yàn)位通過(guò)異或運(yùn)算進(jìn)行校驗(yàn)。得出詳細(xì)的校驗(yàn)碼
（2）在接收端相同通過(guò)異或運(yùn)算看各組校驗(yàn)結(jié)果是否正確，并觀察出錯(cuò)的校校組。或者多個(gè)出錯(cuò)的校驗(yàn)組的共同校驗(yàn)位。得出詳細(xì)的出錯(cuò)比特位。
（3）對(duì)錯(cuò)誤位取反來(lái)將其糾正。

二、海明碼計(jì)算

海明碼計(jì)算要按下面步驟來(lái)進(jìn)行：計(jì)算校驗(yàn)碼位數(shù)→確定校驗(yàn)碼位置→確定校驗(yàn)碼
1.計(jì)算校檢碼位數(shù)
??計(jì)算公式: m + k + 1 ≤ 2^k (其中 m 是有效信息位數(shù)，k表示加入校檢碼的位數(shù))

比如：10011101需要的校檢碼位數(shù)?此時(shí)，m = 8，帶入公式得：8+k+1≤ 2^k,所以 k = 4。（怎么算的？枚舉，枚舉，枚舉......^_,就是估計(jì)帶入去算?。?01101100又需要多少位校檢碼呢？（還是4位）。
2.確定校檢碼位置
??海明碼的校檢碼的位置必須在2ⁿ（n從0開始）。也就是從左邊開始第1、2、4、8、16......).
根據(jù)第一步我們知道10011101需要4位校檢碼，那么校檢碼就在1、2、4、8的位置上。把有效信息按位置填入相應(yīng)位（不是校檢位），校檢位暫時(shí)留空，于是得到下圖：

3.計(jì)算各位校檢碼
??為了說(shuō)明先直接畫圖。
由于是4位校檢位，直接寫出4位2進(jìn)制的表。

（1）第1位要填什么？從上表找出1這列全1對(duì)應(yīng)的十進(jìn)制數(shù)：1、3、5、7、9、11、13、15（1沒(méi)有就不算），看第一個(gè)表中，3、5、7、9、11中分別是1、0、1、1、0為奇數(shù)，所以第一位應(yīng)該填 1（假設(shè)采用偶校檢）。
（2）第2位要填什么？從上表找出2這列全1對(duì)應(yīng)的十進(jìn)制數(shù)2、3、6、7、10、11（2沒(méi)有）再對(duì)應(yīng)第一個(gè)表中為10110，數(shù)1個(gè)數(shù)為奇數(shù)，所以第二位填 1。
（3）第4位看4這列對(duì)應(yīng)全1的 4、5、6、7、12（4沒(méi)有）對(duì)應(yīng)第一個(gè)表0011，1個(gè)個(gè)數(shù)為偶數(shù)，所以填 0。
（4）第8位看8這列對(duì)應(yīng)全1的 8、9、10、11、12（8沒(méi)有）對(duì)應(yīng)第一個(gè)表為1101，所以填 1。
（5）最后校檢碼為 1101。
（6）將校檢碼插入信息碼

總結(jié)：第n位校檢碼校檢的碼位，從自己開始校檢n位，然后空n位，在校檢n位。
例如：
第2位校檢2、3、（空）、（空）、6、7、（空）、（空）、10、11 ......
第4位校檢4、5、6、7、（空）、（空）、（空）、（空）、12、13、14、15 ......

【例】二進(jìn)制碼 101101100，求它的海明編碼？
1.計(jì)算k，m = 9，m + k + 1 ≤ 2^k，所以k = 4。
2.確定校檢碼位置：

3.確定校檢碼
（1）第1位，找到（1）、3、5、7、9、11、13位，為101010,1為奇數(shù)，填1.
（2）第2位，找到（2）、3、6、7、10、11位，為11111,1為奇數(shù)，填1.
（3）第4位，找到（4）、5、6、7、12、13位，為01100,1為偶數(shù)，填0.
（4）第8位，找到（8）、9、10、11、12、13、（14）、（15）位、為01100,1為偶數(shù)，填0，
（5）校檢碼為1100.

4.所以插入了校檢碼的信息碼：1110011001100。

三、糾錯(cuò)
??依然根據(jù)上面的例題，我們將11位上改為0.也就是：

<em>由于信息只有13位，下面（）中的位數(shù)沒(méi)有，只是為了方便理解其分組</em>

（1）第1位，找到1、3、5、7、9、11、13位，為1101000,1為奇數(shù)，錯(cuò)誤.
（2）第2位，找到2、3、6、7、10、11位，為111110,1為奇數(shù)，錯(cuò)誤.
（3）第4位，找到4、5、6、7、12、13、（14）、（15）位，為001100,1為偶數(shù)，正確.
（4）第8位，找到8、9、10、11、12、13、（14）、（15）位、為001000,1為奇數(shù)，錯(cuò)誤。
所以出錯(cuò)位數(shù)應(yīng)該是 1+2+8=11位，將第11位0改為1即可糾正錯(cuò)誤！

<h2>三、CRC校檢碼</h2>

CRC的實(shí)現(xiàn)原理十分易于硬件實(shí)現(xiàn)，因此被廣泛的應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)上的差錯(cuò)控制。CRC校驗(yàn)碼需根據(jù)CRC生成多項(xiàng)式進(jìn)行。

1.根據(jù)多項(xiàng)式確定代碼 P 以及R的位數(shù)（R位數(shù) = P位數(shù) -1）。
2.在信息 M 后面加 0，加 0 的個(gè)數(shù)等于 R位數(shù).
3.用 M 對(duì) P 做模2除法（也就是按位做異或）得到余數(shù)r。
4.余數(shù) r 不夠 R位數(shù)，則在高位補(bǔ)0，得到的數(shù)即校檢碼。

異或：0 ⊕ 0 = 0；0 ⊕ 1 = 1；1 ⊕ 0 = 1；1 ⊕ 1 = 0；運(yùn)算數(shù)相同結(jié)果為0，不同結(jié)果為1

【例】現(xiàn)假設(shè)選擇的CRC生成多項(xiàng)式為G（X） = X⁴ + X³ + 1，要求出二進(jìn)制序列10110011的CRC校驗(yàn)碼。
(1)更具多項(xiàng)式確定代碼P以及R的位數(shù)
多項(xiàng)式為G（X） = X⁴ + X³ + 1，那么

也就是代碼P = 11001，P為5位，R位數(shù)則為5 - 1 = 4位。
（2）在信息 M 后面加 0，加 0 的個(gè)數(shù)等于 R位數(shù).
M = 10110011，那么加 4 位 0 后得到 101100110000.
（3）用 M 對(duì) P 做模2除法（由于不關(guān)心商多少，直接去掉除法上面商部分^_）。

模2除法