海明碼原理是怎么推理出來的（海明碼）

大家好,小霞來為大家解答以上的問題。海明碼原理是怎么推理出來的，海明碼這個很多人還不知道,現在讓我們一起來看看吧！

1、海明碼其實也不難，相對于寄偶檢驗碼 它不僅可以檢驗出錯誤，還能修正錯誤！但只能是檢驗、修正一位錯誤！說一大堆理論是沒什么意思，下面將通過一個例子，盡可能的用最通俗易懂的方式進行講解！最后大家會發現海明碼很神奇！！假設要傳送的數據為：1011 0011校驗流程如下：一：確定校驗位并插入到有效數據位中。

2、相比奇偶校驗只插入一個檢驗碼，海明碼需要插入多個檢驗碼，插入的位數與有效數據位數相關，公式如下公式：2^r-r>k+1,其中r就是要插入檢驗碼的個數,取滿足條件的最小整數，k是有效數據位數。

3、因為我們要傳送的數據是：1011 0011，顯然k=8,推出r=4。

4、也就說我們要將4個校驗位插入到有效數據中，怎么插入呢？按照如下規則：插入位置固定為2^N（N：0，1,2,3,4，5……）處，因為r=4，即只需要取4個有{2^0,2^1,2^2,2^3},對應位置即是1,2,4,8，當然了，如果r=5,那么插入位置為：1,2,4,8，16.同類可以推出其他情況，不再啰嗦。

5、（之所以選擇這樣的位置插入，是為了有效的分組，保證后面的校驗分組能有效的錯開，不會互相干擾，這句話不需要理解，到后面就能體會！）通過分析得到待傳送的數據為：xx1x 011x 0011,4位校驗位+8為有效數據位。

6、二、確定校驗位的數值。

7、顯然X只能取0,1，下面確定x的值：由一可知待傳送數據為：xx1x 011x 0011。

8、規則：以X的位置為長度，依次從待傳送數據中取X個數，然后跳過X個數，再取X個數，直到待傳送數據串尾,得到一個子串，然后統計子串中1的個數，如果為奇數，則x=0,為偶數，x=1(當然，反過來也行，其實這就是奇偶校驗的規則，想了解奇偶校驗可以參見我以前的回答的，這里不了解也行)第1個X：位置為1，從第1個位置開始依次取1個數據，并跳過1個數據再取，直到串尾得到一個子串：{x 1 0 1 0 1}，這個串可記為第1個校驗組, 因為1的個數是3個為奇數，故x=0.第2個X：位置為2，故從第2個位置開始依次取2個數據，并跳過2個數據再取，直到串尾得到一個子串：{x1 ?11 ?01} ，記為第2個校驗組,因為1的個數為4是偶數，故x=1.第3個X：位置是4，故從第4個位置開始依次取4個數據，并跳過4個數據再取，直到串尾得到一個子串：{x011 ? ? 1}，記為第3個校驗組，因為1的個數為3是奇數，故x=0.第4個X：位置是8，故從第8個位置開始依次取8個數據，并跳過8個數據再取，直到串尾得到一個子串：{x0011 }，記為第4個校驗組，……，X=1。

9、故得到最終的待傳送的數據串為：0110?0111?0011。

10、這里其實就可以看到了，為什么X的位置要取2^N,這樣才能保證各個校驗位不會相互干擾。

11、經過以上一、二步驟就完整了海明碼的構造過程，下面講解校驗過程：三、根據步驟二中的構造規則，取出各校驗組發送的數據串為：0110?0111?0011。

12、假設接受到的數據串為：0110?0111?1011（注意和傳送數據串相比，第9為出現了錯誤！）規則：以X的位置為長度，依次從待傳送數據中取X個數，然后跳過X個數，再取X個數，直到待傳送數據串尾,得到一個子串，然后統計子串中1的個數，如果為奇數，則x=0,為偶數，x=1(規則必須和步驟二中一樣)根據二中制定的規則再次取出各個校驗組。

13、第1個校驗組：從第1個位置開始依次取1個數據，并跳過1個數據再取，直到串尾得到一個子串：{0 1 0 1 1 1}。

14、第2個校驗組：從第2個位置開始依次取2個數據，并跳過2個數據再取，直到串尾得到一個子串：{11 ?11 ?01}第3個校驗組：從第4個位置開始依次取4個數據，并跳過4個數據再取，直到串尾得到一個子串：{0011 ? ?1}第4個校驗組：從第8個位置開始依次取8個數據，并跳過8個數據再取，直到串尾得到一個子串：{11011}.四、根據步驟二的構造規則，確定存在錯誤的校驗組，并通過錯誤校驗組的交集，最終確定出錯的位置。

15、由步驟三得到4個校驗組：1：{0 1 0 1 1 1}。

16、 ?對應位置為{1 3 5 7 9 11}2：{11 ?11 ?01}。

17、?對應位置為{2 3 6 7 10 11}3：{0011 ? ?1} ?。

18、對應位置為{4567 ? ?12}4：{11011}。

19、 ??對應位置為{8 9 10 11 12}因為我們的構造規則是：統計子串中1的個數，如果為奇數，則x=0,為偶數，x=1。

20、所以正確的校驗組中1的個數絕對是奇數！（好好琢磨，很容易就想通了，如果我們的規則是為奇數，則x=1,為偶數，x=0。

21、那么正確的校驗組中1的個數絕對是偶數），所以如果校驗組1的個數不是奇數，那么這個校驗組就存在問題。

22、因而可以判斷第1個和第4個校驗組出現問題了。

23、確定了第1個和第4個校驗組出現問題后，找到這兩個校驗組的交集即第9個位置和第11個位置是它們交集，即共同校驗的位置。

24、于是判斷出現問題的位置要么就是第9個位置，要么就是第11個位置！因為在第2個校驗組中有第11個位置，故第11個位置絕對沒有出錯，因為就可以判斷是第9個位置出現錯誤！到這里，應該懂了吧？但是不是覺得找出錯位置有點麻煩啊？下面就給出一個具體的實現方法，理解了上面的描述，再了解下面實現的方法，立馬就能確定出錯誤的位置：首先：我們對各個校驗組求異或。

25、第一個校驗組：{0 1 0 1 1 1} 異或的結果為：0第二個校驗組：{11 ?11 ?01}異或的結果為：1第三個校驗組：{0011 ? ?1}?異或的結果為：1第四個校驗組：{11011}異或的結果為：0接著：倒置拼接異或結果，得到：0110，最后：按位取反的到：1001,。

26、大家有沒有驚奇的發現1001的十進制數就是9，這不就是出錯的位置嗎？這是巧合嗎？不急再看一個例子：傳送的數據串為： ?0110?0111?0011（還是我們開始的那個串）接受到的數據串為：0110?1111?0011（和正確數據串相比，第5個位置出錯了）第一個校驗組：{0 1 1 1 0 1} 異或的結果為：0第二個校驗組：{11 ?11 ?01}異或的結果為：1第三個校驗組：{0111 ? ?1}?異或的結果為：0第四個校驗組：{10011}異或的結果為：1倒置拼接：1010 ?反轉為：0101 ?對應十進制數為5！也就是說方法是真確的！！不用懷疑！！這也就是海明碼的奇妙之處！再來看看一個例子：傳送的數據串為： ?0110?0111?0011（還是我們開始的那個串）接受到的數據串為：0110?0110?0011（和正確數據串相比，第8個位置校驗位出錯了）顯然這是校驗位出錯了，那么能不能校驗出來呢？第一個校驗組：{0 1 0 1 0 1} 異或的結果為：1第二個校驗組：{11 ?11 ?01}異或的結果為：1第三個校驗組：{0011 ? ?1}?異或的結果為：1第四個校驗組：{00011}異或的結果為：0倒置反轉結果為1000 正好是8，所以也沒問題。

27、下面我們來說下規則：（其實就是說異或與奇偶的關系，想拓展的就可以看看）上面的例子中，我們規定： 統計子串中1的個數，如果為奇數，則x=0,為偶數，x=1。

28、如果是按這樣的規定，那么校驗組中1的個數必定是奇數，正是因為如此，所以校驗組中如果1的個數不是奇數那么肯定出現了錯誤！而如果一個串中1的個數是奇數，那么串異或的結果一定為1，其實這個規則對應的就是奇校驗！反之，如果為奇數，則x=1,為偶數，x=0，那么對應的就是偶校驗！故得到以下結論：如果采用奇檢驗構造海明碼，那么出錯校驗組中的1的個數必為偶數，即異或的結果必定為0！如果采用奇檢驗構造海明碼，那么出錯的位置是校驗組異或結果倒置拼接并反轉的十進制數如果采用偶檢驗構造海明碼，那么出錯校驗組中的1的個數必為奇數，即異或的結果必定為1！如果采用偶檢驗構造海明碼，那么出錯位置是校驗組異或結果直接倒置拼接的十進制數！關于偶檢驗構造海明碼這里就不再詳細展開，如果你能用偶檢驗的方法在把上面的例子都做一遍，那么海明碼你就已經完全弄懂了！試試吧！關于奇偶檢驗碼 建議還是看看，因為海明碼是基于奇偶校驗的改進！而且奇偶校驗更簡單！1.海明碼的概念海明碼是一種可以糾正一位差錯的編碼。

29、它是利用在信息位為k位，增加r位冗余位，構成一個n=k+r位的碼字，然后用r個監督關系式產生的r個校正因子來區分無錯和在碼字中的n個不同位置的一位錯。

30、它必需滿足以下關系式：2r>=n+1 或 2r>=k+r+1海明碼的編碼效率為：R=k/(k+r)式中 k為信息位位數r為增加冗余位位數 2.海明碼的生成與接收方法一：1)海明碼的生成。

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

32、海明碼的監督關系式為：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6求：海明碼碼字。

33、解：1)由監督關系式知冗余碼為a2a1a0。

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

35、設S2=S1=S0=0,由監督關系式得：a2=a4+a5+a6=1a1=a3+a5+a6=0a0=a3+a4+a6=1因此，海明碼碼字為："0010101"2)海明碼的接收。

36、例2.已知：海明碼的監督關系式為：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6接收碼字為："0011101"(n=7)。

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