關(guān)于海明碼為什么能發(fā)現(xiàn)兩位錯(cuò)，海明碼這個(gè)很多人還不知道，今天菲菲來(lái)為大家解答以上的問(wèn)題，現(xiàn)在讓我們一起來(lái)看看吧！

1、海明碼是一種可以糾正一位差錯(cuò)的編碼。

2、它是利用在信息位為k位，增加r位冗余位，構(gòu)成一個(gè)n=k+r位的碼字，然后用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來(lái)區(qū)分無(wú)錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò)。

3、它必需滿足以下關(guān)系式： r 2^r ≥ k r 1 或 2^r ≥ n 1海明碼的編碼效率為： R=k/(k+r) 式中 k為信息位位數(shù) r為增加冗余位位數(shù)目錄 1.海明碼的原理 2.海明碼的生成與接收 3.海明碼的計(jì)算 4.海明碼校驗(yàn)程序設(shè)計(jì)原理分析參考編輯本段1.海明碼的原理　　在數(shù)據(jù)中間加入幾個(gè)校驗(yàn)碼，碼距均勻拉大，將數(shù)據(jù)的每個(gè)二進(jìn)制位分配在幾個(gè)奇偶校驗(yàn)組里，當(dāng)某一位出錯(cuò)，會(huì)引起幾個(gè)校驗(yàn)位的值發(fā)生變化。

4、　　海明不等式：　　校驗(yàn)碼個(gè)數(shù)為K，2的K次方個(gè)信息，1個(gè)信息用來(lái)指出“沒(méi)有錯(cuò)誤”，其余（2^K)-1個(gè)指出錯(cuò)誤發(fā)生在那一位，但也可能是校驗(yàn)位錯(cuò)誤，故有N<=(2^K)-1-K能被校驗(yàn)。

5、　　海明碼的編碼規(guī)則：　　1.每個(gè)校驗(yàn)位Ri被分配在海明碼的第2的i次方的位置上，　　2.海明碼的每一位（Hi)是由多個(gè)/1個(gè)校驗(yàn)值進(jìn)行校驗(yàn)的，被校驗(yàn)碼的　　位置碼是所有校驗(yàn)位的校驗(yàn)位位置碼之和。

6、　　一個(gè)例題：　　4個(gè)數(shù)據(jù)位d0,d1,d2,d3, 3個(gè)校驗(yàn)位r0,r1,r2，對(duì)應(yīng)的位置為：　　d3 d2 d1 r2 d0 r1 r0 ======b7 b6 b5 b4 b3 b2 b1　　校驗(yàn)位的取值，就是他所能校驗(yàn)的數(shù)據(jù)位的異或　　b1為b3,b5,b7的異或，b2為b3,b6,b7 b4為b5,b6,b7　　海明v傳送到接受方后，將上三式的右邊（b1,b2,b4)的邏輯表達(dá)式分別　　異或上左邊的值就得到了校驗(yàn)方程，如果上題采用偶校驗(yàn)　　G1=b1 b3 b5 b7的異或　　G2=b2 b3 b6 b7的異或　　G3=b4 b5 b6 b7的異或　　若G1G2G3為001是第一位錯(cuò)　　若為011是第三位錯(cuò)編輯本段2.海明碼的生成與接收　　特注：以下的+均代表異或　　方法一：　　1)海明碼的生成。

7、　　例1.已知：信息碼為："0010"。

8、海明碼的監(jiān)督關(guān)系式為：　　S2=a2+a4+a5+a6　　S1=a1+a3+a5+a6　　S0=a0+a3+a4+a6　　求：海明碼碼字。

9、　　解：1)由監(jiān)督關(guān)系式知冗余碼為a2a1a0。

10、　　2)冗余碼與信息碼合成的海明碼是："0010a2a1a0"。

11、　　設(shè)S2=S1=S0=0,由監(jiān)督關(guān)系式得：　　異或運(yùn)算：　　a2=a4+a5+a6=1　　a1=a3+a5+a6=0　　a0=a3+a4+a6=1　　因此，海明碼碼字為："0010101"　　對(duì)以上這道題目的第二問(wèn)的疑問(wèn)：　　冗余碼與信息碼合成的海明碼是："0010a2a1a0"。

12、為什么a2a1a0直接加在信息碼后面，而不是按照1,2,4,8位的順序加在信息碼后面【例如：001(a2)0(a1)(a0)=0011001】　　2)海明碼的接收。

13、　　例2.已知：海明碼的監(jiān)督關(guān)系式為：　　S2=a2+a4+a5+a6　　S1=a1+a3+a5+a6　　S0=a0+a3+a4+a6　　接收碼字為："0011101"(n=7)　　求：發(fā)送端的信息碼。

14、　　解：1)由海明碼的監(jiān)督關(guān)系式計(jì)算得S2S1S0=011。

15、　　2)由監(jiān)督關(guān)系式可構(gòu)造出下面錯(cuò)碼位置關(guān)系表：　　S2S1S0　　000　　001　　010　　100　　011　　101　　110　　111　　錯(cuò)碼位置　　無(wú)錯(cuò)　　a0　　a1　　a2　　a3　　a4　　a5　　a6　　3)由S2S1S0=011查表得知錯(cuò)碼位置是a3。

16、　　4)糾錯(cuò)--對(duì)碼字的a3位取反得正確碼字："0 0 1 0 1 0 1"　　5)把冗余碼a2a1a0刪除得發(fā)送端的信息碼："0010"　　方法二：(不用查表，方便編程)　　1)海明碼的生成（順序生成法）。

17、　　例3.已知：信息碼為：" 1 1 0 0 1 1 0 0 " (k=4代表冗余位數(shù)，即校驗(yàn)碼位數(shù))　　求：海明碼碼字。

18、　　解：1)把冗余碼A、B、C、…，順序插入信息碼中，得海明碼　　碼字:" A B 1 C 1 0 0 D 1 1 0 0 "　　碼位: 1 2 3 4 5 6 7 8 9 10 11 12　　其中A,B,C,D分別插于2的k次方位(k=0,1,2,3)。

19、碼位分別為1,2,4,8。

20、　　2)冗余碼A,B,C,D的線性碼位是：(相當(dāng)于監(jiān)督關(guān)系式)　　監(jiān)督關(guān)系式的推導(dǎo)：　　D C B A　　1 0 0 0 1　　2 0 0 1 0　　3 0 0 1 1　　4 0 1 0 0　　5 0 1 0 1　　6 0 1 1 0　　7 0 1 1 1　　8 1 0 0 0　　9 1 0 0 1　　10 1 0 1 0　　11 1 0 1 1　　12 1 1 0 0　　根據(jù)上面表格得到 A B C D　　需要說(shuō)明的是公式中參與計(jì)算的是表格中出現(xiàn)"1"的那個(gè)位 右邊是數(shù)據(jù)位的二進(jìn)制數(shù),公式中的"+"表示異或　　故此有如下表達(dá)式：　　A->1,3,5,7,9,11；(這里的1 3 5 7 9 11均為A那一列出現(xiàn)1的位)　　B->2,3,6,7,10,11；　　C->4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)　　D->8,9,10,11,12。

21、　　3)把線性碼位的值的偶校驗(yàn)作為冗余碼的值(設(shè)冗余碼初值為0)：　　A=∑(0,1,1,0,1,0)=1　　B=∑(0,1,0,0,1,0)=0　　C=∑(0,1,0,0,0) =1　　D=∑(0,1,1,0,0) =0　　4)海明碼為:"1 0 1 1 1 0 0 0 1 1 0 0"　　2)海明碼的接收。

22、　　例4.已知：接收的碼字為："1 0 0 1 1 0 0 0 1 1 0 0"(k=4代表冗余位數(shù)，即校驗(yàn)碼位數(shù))　　求：發(fā)送端的信息碼。

23、　　解：1)設(shè)錯(cuò)誤累加器(err)初值=0　　2)求出冗余碼的偶校驗(yàn)和，并按碼位累加到err中：　　A=∑(1,0,1,0,1,0)=1 err=err+2^0=1　　B=∑(0,0,0,0,1,0)=1 err=err+2^1=3　　C=∑(1,1,0,0,0) =0 err=err+0 =3　　D=∑(0,1,1,0,0) =0 err=err+0 =3　　由err≠0可知接收碼字有錯(cuò)，　　3)碼字的錯(cuò)誤位置就是錯(cuò)誤累加器(err)的值3。

24、　　4)糾錯(cuò)--對(duì)碼字的第3位值取反得正確碼字：　　"1 0 1 1 1 0 0 0 1 1 0 0"　　5)把位于2的k次方位的冗余碼刪除得信息碼："1 1 0 0 1 1 0 0"編輯本段3.海明碼的計(jì)算　　海明碼(Hamming Code )編碼的關(guān)鍵是使用多余的奇偶校驗(yàn)位來(lái)識(shí)別一位錯(cuò)誤。

25、　　碼字(Code Word) 按如下方法構(gòu)建：　　把所有2的冪次方的數(shù)據(jù)位標(biāo)記為奇偶校驗(yàn)位(編號(hào)為1, 2, 4, 8, 16, 32, 64等的位置)　　2、其他數(shù)據(jù)位用于待編碼數(shù)據(jù). (編號(hào)為3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置)　　3、每個(gè)奇偶校驗(yàn)位的值代表了代碼字中部分?jǐn)?shù)據(jù)位的奇偶性，其所在位置決定了要校驗(yàn)和跳過(guò)的比特位順序。

26、　　位置1：校驗(yàn)1位，跳過(guò)1位，校驗(yàn)1位，跳過(guò)1位(1,3,5,7,9,11,13,15,…)　　位置2：校驗(yàn)2位，跳過(guò)2位，校驗(yàn)2位，跳過(guò)2位 (2,3,6,7,10,11,14,15,…)　　位置4：校驗(yàn)4位，跳過(guò)4位，校驗(yàn)4位，跳過(guò)4位 (4,5,6,7,12,13,14,15,20,21,22,23,…)　　位置8：校驗(yàn)8位，跳過(guò)8位，校驗(yàn)8位，跳過(guò)8位(8-15,24-31,40-47,…)　　…　　如果全部校驗(yàn)的位置中有奇數(shù)個(gè)1，把該奇偶校驗(yàn)位置為1；如果全部校驗(yàn)的位置中有偶數(shù)個(gè)1，把該奇偶校驗(yàn)位置為0.　　舉例說(shuō)明：　　一個(gè)字節(jié)的數(shù)據(jù)：10011010　　構(gòu)造數(shù)據(jù)字(Data Word),對(duì)應(yīng)的校驗(yàn)位留空_ _ 1 _ 0 0 1 _ 1 0 1 0　　計(jì)算每個(gè)校驗(yàn)位的奇偶性 ( ?代表要設(shè)置的比特位):　　位置1檢查1,3,5,7,9,11:　　? _ 1 _ 0 0 1 _ 1 0 1 0. 偶數(shù)個(gè)1，因此位置1設(shè)為0，即: 0 _ 1 _ 0 0 1 _ 1 0 1 0　　位置2檢查2,3,6,7,10,11:　　0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇數(shù)個(gè)1，因此位置2設(shè)為1，即: 0 1 1 _ 0 0 1 _ 1 0 1 0　　位置4檢查4,5,6,7,12:　　0 1 1 ? 0 0 1 _ 1 0 1 0. 奇數(shù)個(gè)1，因此位置4設(shè)為1，即: 0 1 1 1 0 0 1 _ 1 0 1 0　　位置8檢查8,9,10,11,12:　　0 1 1 1 0 0 1 ? 1 0 1 0. 偶數(shù)個(gè)1，因此位置8設(shè)為0，即: 0 1 1 1 0 0 1 0 1 0 1 0　　因此碼字為: 011100101010.　　查找并糾錯(cuò)一位錯(cuò)誤　　上例中構(gòu)建了一個(gè)碼字 011100101010，假定實(shí)際接收到的數(shù)據(jù)是011100101110. 則接收方可以計(jì)算出哪一位出錯(cuò)并對(duì)其進(jìn)行更正。

27、方法就是驗(yàn)證每一個(gè)校驗(yàn)位。

28、記下所有出錯(cuò)的校驗(yàn)位，可以發(fā)現(xiàn)校驗(yàn)位2和8的數(shù)據(jù)不正確. 錯(cuò)誤校驗(yàn)位 2 + 8 = 10, 則位置10的數(shù)據(jù)出錯(cuò)。

29、一般說(shuō)來(lái)，對(duì)所有校驗(yàn)位進(jìn)行檢查, 將所有出錯(cuò)的校驗(yàn)位置相加, 得到的就是錯(cuò)誤信息所在的位置.編輯本段4.海明碼校驗(yàn)程序設(shè)計(jì)原理分析參考　　海明碼校驗(yàn)是為了保證數(shù)據(jù)傳輸正確而提出的，本來(lái)就是一串要傳送的數(shù)據(jù)，如：D7,D6,D5,D4,D3,D2,D1,D0，這里舉的是八位數(shù)據(jù)，可以是n位數(shù)據(jù)。

30、就這樣傳送數(shù)據(jù)，不知道接收到后是不是正確的。

31、所以，要加入校驗(yàn)位數(shù)據(jù)才能檢查是否出錯(cuò)。

32、這里涉及到一個(gè)問(wèn)題，要多少位校驗(yàn)數(shù)據(jù)才能查出錯(cuò)誤呢？　　我們只要能檢測(cè)出一位出錯(cuò)，則對(duì)于8位信息數(shù)據(jù)，校驗(yàn)位為4位。

33、滿足下列條件：2的k次方大于等于n+k+1，其中k為校驗(yàn)位位數(shù)，n為信息數(shù)據(jù)位位數(shù)。

34、驗(yàn)證一下，2的4次方等于16，n+k+1等于8+4+1等于13。

35、 8位信息數(shù)據(jù)與4位校驗(yàn)位總共有12位數(shù)據(jù)，怎么排列呢？我們先把校驗(yàn)位按P4,P3,P2,P1排列，用通式Pi表示校驗(yàn)位序列，i為校驗(yàn)位在校驗(yàn)序列中的位置。

36、 傳送的數(shù)據(jù)流用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1表示，接下來(lái)的問(wèn)題是如何用D7,D6,D5,D4,D3,D2,D1,D0與P4,P3,P2,P1來(lái)表M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1了。

37、校驗(yàn)位在傳送的數(shù)據(jù)流中位置為2的i－1次方，則P1在M1位，P2在M2位，P3在M4位，P4在M8位。

38、其余的用信息數(shù)據(jù)從高到低插入。

39、 傳送的數(shù)據(jù)流為D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1。

40、 接下來(lái)，我們要弄明白如何找出錯(cuò)誤位的問(wèn)題。

41、引進(jìn)4位校驗(yàn)和序列S4,S3,S2,S1。

42、S4,S3,S2,S1等于0,0,0,0表示傳送的數(shù)據(jù)流正確；如S4,S3,S2,S1等于0,0,1,0則表示傳送的數(shù)據(jù)流中第2位出錯(cuò)；如S4,S3,S2,S1等于0,0,1,1則表示傳送的數(shù)據(jù)流中第3位出錯(cuò)；依次類推。

43、　　用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1如何表示S4,S3,S2,S1呢，簡(jiǎn)單的方法就是S1=1時(shí)，S4,S3,S2從0,0,0到1,1,1的所有的Mx異或。

44、即S1等于M1異或M3異或M5異或M7異或M9異或M11。

45、也就是S1等于P1異或D0異或D1異或D3異或D4異或D6。

46、S2=1時(shí)，S4,S3,S1從0,0,0到1,1,1的所有的Mx異或。

47、即S2等于M2異或M3異或M6異或M7異或M10異或M11。

48、S3=1時(shí)，S4,S2,S1從0,0,0到1,1,1的所有的Mx異或。

49、即S3等于M4異或M5異或M6異或M7異或M12。

50、S4=1時(shí)，S3,S2,S1從0,0,0到1,1,1的所有的Mx異或。

51、即S4等于M8異或M9異或M10異或M11異或M12。

52、這樣，對(duì)于一串碼流，知道幾位校驗(yàn)位，可以很快確定哪一位出錯(cuò)。

53、而在發(fā)送端，可以根據(jù)S4,S3,S2,S1的表達(dá)式求出P4,P3,P2,P1的表達(dá)式，只要把式子右邊的P4或P3或P2或P1移到左邊替換掉S4或S3或S2或S1就可以了。

54、面舉例說(shuō)明：用^表示異或　　D7,D6,D5,D4,D3,D2,D1,D0=11010001　　S4=M8^M9^M10^M11^M12=D7^D6^D5^D4^P4; P4=D7^D6^D5^D4;　　S3=M4^M5^M6^M7^M12 =D7^D3^D2^D1^P3; P3=D7^D3^D2^D1;　　S2=M2^M3^M6^M7^M10^M11 =D6^D5^D3^D2^D0^P2; P2=D6^D5^D3^D2^D0;　　S1=M1^M3^M5^M7^M9^M11=D6^D4^D3^D1^D0^P1; P1=D6^D4^D3^D1^D0;　　所以，　　P4=D7^D6^D5^D4=1^1^0^1=1　　P3=D7^D3^D2^D1=1^0^0^0=1　　P2= D6^D5^D3^D2^D0=1^0^0^0^1=0 P1=D6^D4^D3^D1^D0=1^1^0^0^1=1　　故，傳送碼流為D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1等于　　110110001101　　若接收端收到110110001101，則　　S4=M8^M9^M10^M11^M12=1^1^0^1^1=0　　S3=M4^M5^M6^M7^M12=1^0^0^0^1=0　　S2=M2^M3^M6^M7^M10^M11=0^1^0^0^0^1=0　　S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0　　故，接收碼流正確。

55、　　若M6出錯(cuò)，由0變?yōu)?。

56、則　　S4=M8^M9^M10^M11^M12=1^1^0^1^1=0　　S3=M4^M5^M6^M7^M12=1^0^1^0^1=1　　S2=M2^M3^M6^M7^M10^M11=0^1^1^0^0^1=1 S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0　　即S4S3S2S1=0110，此為十進(jìn)制的6，說(shuō)明第六位出錯(cuò)，也就是M6出錯(cuò)。

57、完全符合。

58、　　5.海明碼的表格計(jì)算　　如果對(duì)于m位的數(shù)據(jù)，增加k位冗余位，則組成位n=m+k位的糾錯(cuò)碼。

59、對(duì)于2^m個(gè)有效碼字中的每一個(gè)，都有n個(gè)無(wú)效但可以糾錯(cuò)的碼字。

60、這些可糾錯(cuò)的碼字與有效碼字的距離是1，含單個(gè)錯(cuò)誤位。

61、這樣，對(duì)于一個(gè)有效的消息總共有n+1個(gè)可識(shí)別的碼字。

62、這n+1個(gè)碼字相對(duì)于其他2^m-1個(gè)有效消息的距離都大于1。

63、這意味著總共有2^m（n+1）個(gè)有效的或是可糾錯(cuò)的碼字。

64、顯然這個(gè)數(shù)應(yīng)小于等于碼字的所有的可能的個(gè)數(shù)2^n。

65、于是我們有　　2^m（n+1）<2^n　　因?yàn)閚=m+k，我們得出　　m+k+1<2^k　　對(duì)于給定的數(shù)據(jù)位m，上式給出了k的下界，即要糾正單個(gè)錯(cuò)誤，k必須取最小的值。

66、海明建議了一種方案，可以達(dá)到這個(gè)下界，并能直接指出錯(cuò)在哪一位。

67、首先把碼字的位從1到n編號(hào)，，并把這個(gè)編號(hào)表示成二進(jìn)制數(shù)，即2的冪之和。

68、然后對(duì)2的每一個(gè)冪設(shè)置一個(gè)奇偶位。

69、例如對(duì)于6號(hào)位，由于6=110（二進(jìn)制），所以6號(hào)位參加第2位和第4位的奇偶校驗(yàn)，而不參加第1位奇偶校驗(yàn)。

70、類似的9號(hào)位參加第1位和第8位的奇偶校驗(yàn)而不參加第2位和第4位的奇偶校驗(yàn)。

71、海明把奇偶校驗(yàn)分配在1,2,4,8等位置上，其他位置放數(shù)據(jù)。

72、下面根據(jù)海明編碼的例圖，舉例說(shuō)明編碼的方法 海明編碼的例海明編碼的例　　例如傳送的消息為：1001011　　我們把數(shù)據(jù)放在3,5,6,7,9,10,11等位置上，1,2,4,8則為校驗(yàn)位。

73、　　1001011　1 2 3 4 5 6 7 8 9 10 11　　根據(jù)海明編碼的例，3、5、7、9、11的二進(jìn)制編碼的第一位為1，所以3、5、7、9、11號(hào)位參加第一位校驗(yàn)位，若按偶校驗(yàn)計(jì)算，1號(hào)位應(yīng)為1　　11001011　1 2 3 4 5 6 7 8 9 10 11　　類似的，3、6、7、10、11號(hào)位參加2號(hào)位校驗(yàn)，5、6、7號(hào)位參加4號(hào)位校驗(yàn)，9、10、11號(hào)位參加8號(hào)位校驗(yàn)，全部按偶校驗(yàn)計(jì)算，最終得到如下結(jié)果　　10110010011　1 2 3 4 5 6 7 8 9 10 11　　如果這個(gè)碼字傳輸中有錯(cuò)誤，比如說(shuō)6號(hào)位出錯(cuò)。

74、就會(huì)變成　　√ ╳ ╳ √　　10110110011　1 2 3 4 5 6 7 8 9 10 11　　當(dāng)接收端按照同樣的規(guī)則計(jì)算奇偶位時(shí)，就會(huì)發(fā)現(xiàn)1號(hào)位和8號(hào)位的奇偶性正確而2號(hào)位和4號(hào)位的奇偶性不對(duì)，于是2+4=6,，立即可以判斷錯(cuò)在6號(hào)位。

75、　　上例中k=4，因而m<2^4-4-1=11,即數(shù)據(jù)位可以用到11位，共組成15位的碼字，可檢測(cè)出單個(gè)位置的錯(cuò)誤。

本文到此分享完畢，希望對(duì)大家有所幫助。

　　免責(zé)聲明：本文由用戶上傳，與本網(wǎng)站立場(chǎng)無(wú)關(guān)。財(cái)經(jīng)信息僅供讀者參考，并不構(gòu)成投資建議。投資者據(jù)此操作，風(fēng)險(xiǎn)自擔(dān)。 如有侵權(quán)請(qǐng)聯(lián)系刪除！