回覆列表
  • 1 # 使用者6026853154010

    海明碼校驗位數量的確定:

    若有n個位的碼字將各位依次編號為1、2、3、……、n,且每一單個位錯誤對應一個校驗碼序列,一共需要 n +1 個校驗碼序列(表示 n 種單個位錯誤和1種完全正確的形式)。顯然,n+1種校驗碼序列需要至少 位二進位制校驗碼(向上取整)來表示。

    即: ⇔

    例:6位資訊碼如使用海明碼傳輸,顯然 r ≥ ,向上取整之後 r = 4

    理解也很好理解,4位二進位制的標識上限為16種狀態,3位二進位制的標識上限為8種狀態:若用3位二進位制,校驗位需要標識的狀態就有 3 + 6 + 1 = 10種 > 8種,故3位二進位制不夠;若用4位二進位制,校驗位需要標識的狀態就有 4 + 6 + 1 = 11種 < 16種,故4位二進位制是夠的。

    ——————————————————————————————————————

    海明碼的編碼形式為:

    ① 將編號為1、2、4、8、16、……等以2為底的次冪數的位充當校驗位,將其他非校驗位的位充當資訊位,進行填充

    ② 若有10位碼字,設1~10位分別為M1、M2、M3、M4、……、M10;其中用M8、M4、M2、M1 這四位的值來標識這 10 個位可能產生的單個錯誤。如果最終我們需要M8、M4、M2、M1組成的二進位制位序列轉化成十進位制就是出錯位的編號,顯然:

    當M1_接收端 = 1時,代表編號二進位制形式為XXX1的位出現了錯誤,即M1、M3、M5、M7、M9中有一位出錯

    當M2_接收端 = 1時,代表編號二進位制形式為XX1X的位出現了錯誤,即M2、M3、M6、M7、M10中有一位出錯

    當M4_接收端 = 1時,代表編號二進位制形式為X1XX的位出現了錯誤,即M4、M5、M6、M7中有一位出錯

    當M8_接收端 = 1時,代表編號二進位制形式為1XXX的位出現了錯誤,即M8、M9、M10中有一位出錯

    當Mr_接收端 = 0 ( r=1、2、4、8 )時,其表示上述相應位的傳輸沒有錯誤。故我們知道邏輯關係:

    涉及的各個位有一個發生了變化(從0變1或從1變0)→ Mr_ 接收端 從0變1

    涉及的各個位是否有變化可以用連續異或表示,如:M1 ⊕ M3 ⊕ M5 ⊕ M7 ⊕ M9 (影響M1_接收端,1、3、5、7、9的二進位制形式均為XXX1)

    根據觀察,Mr_接收端所標識的所有可能發生錯誤的位,一定包含該位自身,除此之外全部是資訊位(已知)

    我們將全部資訊位的異或結果用K表示( Known ) → 即 M1 ⊕ K(這裡的M1為預備傳送的位)

    由於K有一個定值,而M1的取值我們可以任意取,且一般我們採取偶校驗的方式,即讓 M1 ⊕ K = 0 來表示這些位均沒有出錯。

    校驗和 M1 ⊕ K = 0 → M1= K = M3 ⊕ M5 ⊕ M7 ⊕ M9

    當Mr_傳送端 ( r=1、2、4、8 )均透過上述方式確定之後,經過傳輸後我們獲得的序列記為 N1、N2、N3、……、N10,我們需要再計算一次校驗和。

    Mr校驗和 = Mr ⊕ 相應的K,若 r 位 與 K 中任意1位出現變化,則 Mr接收端的校驗和將會和 Mr_傳送端的值取反,即為1。

    此時我們只需將M8、M4、M2、M1的序列轉化為十進位制,即可知道是哪一個位出現了錯誤,若序列值為0000,則表示沒有出現傳輸錯誤。

  • 中秋節和大豐收的關聯?
  • Windows 10端OneNote好用嗎?7月份都有哪些更新?