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

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

二、海明碼計(jì)算

海明碼計(jì)算要按下面步驟來進(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ì)帶入去算Ｃ琛）。101101100又需要多少位校檢碼呢履腋？（還是4位）珊燎。
2.確定校檢碼位置
??海明碼的校檢碼的位置必須在2ⁿ（n從0開始）。也就是從左邊開始第1遵湖、2悔政、4、8延旧、16......).
根據(jù)第一步我們知道10011101需要4位校檢碼谋国，那么校檢碼就在1、2迁沫、4芦瘾、8的位置上捌蚊。把有效信息按位置填入相應(yīng)位（不是校檢位），校檢位暫時(shí)留空近弟，于是得到下圖：

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

（1）第1位要填什么窗宦？從上表找出1這列全1對(duì)應(yīng)的十進(jìn)制數(shù)：1、3二鳄、5赴涵、7、9订讼、11髓窜、13、15（1沒有就不算）欺殿，看第一個(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沒有）再對(duì)應(yīng)第一個(gè)表中為10110濒募，數(shù)1個(gè)數(shù)為奇數(shù)鞭盟，所以第二位填 1。
（3）第4位看4這列對(duì)應(yīng)全1的 4瑰剃、5齿诉、6、7、12（4沒有）對(duì)應(yīng)第一個(gè)表0011粤剧，1個(gè)個(gè)數(shù)為偶數(shù)歇竟，所以填 0。
（4）第8位看8這列對(duì)應(yīng)全1的 8抵恋、9焕议、10、11馋记、12（8沒有）對(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ù)沒有柔昼，只是為了方便理解其分組</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除法