海明碼 校驗位數公式的了解

#問題

設海明碼的校驗位數為

，資料位數為

，它們需滿足一個位數公式

最初看到公式時我感到很疑惑啊，百思不得其解，主要的問題是最後那個1哪來的。

看着公式望了半天，一點頭緒都沒有，好腦袋不如爛筆頭，于是我開始手寫舉例試着了解海明碼的校驗邏輯。

不寫不知道，一寫吓一跳。寫着寫着就發現了，原來這個1來的如此妖娆。

#引入(海明碼原理介紹)

我們先來複習一下二進制的劃分，假設現在有七位二進制資料

，用

序号來指向。為什麼選擇七位呢？因為它們的序号剛好可以用三位二進制來表示。

我們再來看看海明碼的糾錯方法。

表示序号的三個二進制位，每一個二進制位取值為1的序号個數都是4個(圖中列标紅)。這冥冥之中的平衡一定可以好好利用。

我們分别把二進制3-1列取值為1的序号納入集合A、B、C。

則集合取值

A={7,6,5,4}

B={7,6,3,2}

C={7,5,3,1}

有一種大家很熟悉，校驗一個序列值的方法叫做奇偶校驗，偶校驗計算方式是序列中所有值異或為0。

如果我們按照A、B、C的集合來分類，每個集合都進行偶校驗，就可以得到3個偶校驗值，它們需要等于0。由于

是固定的，是以A、B、C需要作為校驗位參與運算。也就是需滿足

根據異或運算的性質，自己與自己本身異或為0。是以可以得到A、B、C的計算公式

海明碼考慮的情況是一位糾錯。當某一位出錯後，A、B、C和它們對應集合資料位的異或就不再是本身與本身的異或，并且最終結果會變為1。

也就是說，接收到資料後，若

，則表示A對應集合有一位元素資料位出錯了(集合對應的元素就是一列中二進制表示為1的元素)。同理，最後運算結果為0的集合對應的元素是沒有問題的，這樣就可以篩查出是具體哪一位元素出錯，進而進行糾錯。

比如

出錯，那麼A=1代表第一列元素出錯，B=0代表第二列元素沒錯，C=1代表第三列元素出錯。滿足所有交集的元素隻有一個，也就是被篩查出來的

。可以看見這種方法非常直接，因為将ABC排列成二進制數，所代表的序号就是出錯的那一位。

如下圖，紅色方塊代表本列有出錯元素，A列确定了

，C列确定了

，交集

；而綠色方塊代表一定沒有出錯的元素，B列排除了

。随後

就被篩選出來了。

#探明

在上面講述海明碼糾錯過程中，可能有同學已經發現問題所在了。

我們新增了三位校驗位，可是隻對七位數進行了糾錯。

是以公式裡的那個1，其實來自于我們沒有畫出的序号0！

我們回望A、B、C的分類，每一集合都有4個元素，看似非正常律，似乎冥冥之中決定了我們可以使用海明碼這樣的糾錯方式。

偏偏卦不可算盡，雖然每集合都有4個元素，但元素的分布律不是均等的，不僅不是均等的，還遺漏了一個0。

是以

個校驗位，雖然能表示

個序号，但最終隻能帶來

的糾錯能力。

同時我們需要将校驗位加入傳輸資料，也就是真正的有效資料

需滿足

#ps 會什麼會少一個呢？其實很簡單，隻要理清楚概念。k個校驗位，輸出的序列(比如ABC)，含義是第ABC(二進制)個序号的數值有錯，而不是總共有多少個數字之類。是以看看000代表的含義就知道少掉的一種情況去哪了——它代表序列校驗正确。

#pps 海明碼校驗位的位置在這個問題上沒有啥作用，最初我覺得它一定有什麼深層含義，想了半天也沒想出什麼

#ppps 或許以後有時間還可以寫篇部落格，叫做《海明碼的哲學原理》。