糾錯碼中的漢明碼


當我們考慮具有相同長度的兩個碼字時,漢明碼可用於任何長度的資料單元。兩個碼字之間的漢明距離表示其特定項不同的位置數。

示例


漢明距離為3。

漢明碼也稱為線性分組碼。(n, k) 漢明碼系列由 m 定義。

  • 分組長度 n = 2m - 1。

  • 訊息位數 k = 2m - m - 1。

  • 奇偶校驗位數 = n - k = m。

其中 m ≥ 3

  • 最小距離min = 3。

  • 位元速率 = 碼效率 = $\frac{k}{n} = \frac{2^{m}-m-1}{2^{m}-1} = 1 - \frac{m}{2^{m}-1}$ 當 m >> 1 時

    則位元速率 r = 1,其中 k 是訊息位,n 是每個分組傳輸的位數。


結構

奇偶校驗(冗餘)位插入到資料單元之間或資料單元的末尾。

為了評估,需要多個冗餘位來準確表示給定的資料位數 m。我們應該找到 m 和 r 之間的關係。

如果總傳輸量為 m + r,則 r 必須表示 m + r + 1 個不同的狀態。一個狀態定義為無錯誤,m + r 個狀態表示 m + r 個位置中每個位置的錯誤位置。

因此,r 位應發現 m + r + 1 個狀態,而 r 位可以表示 2r 個多個狀態。所以 2r ≥ m + r + 1。

假設 m = 7,則滿足此方程式的最小 r 值為 4。

  11
  10
   9
   8
   7
   6
   5
   4
   3
   2
    1
   d
   D
r4
   D
   D
   D
   D
r3   D
r2
r1

在這個 r 位放在 2n 位置上。例如,20 = 1,21 = 2,22 = 4 等位置

在漢明碼中,每個 r 位都是 VRC(垂直冗餘校驗)。

r1 位是透過使用所有二進位制表示在最右位置包含 1 的位位置計算的,即 1, 3, 5, 7, 9, 11。

r2 位是透過使用在 2, 3, 6, 7, 10, 11 位置具有 1 的所有位置計算的,依此類推。r3 位將處理 4, 5, 6 位置的位。r4 在 8, 9, 10, 11 位置進行校驗。

示例

1011

   11                1001             0111                 0101                  0011               0001

   d
   D
   D
  r4
   d
   d
   d
  r3   d
   r2
  r1

r2 將負責它

1011                1010

   11                             10                                 0111     0110                                                             0111     0010

   d
   D
   D
   r6
   d
   d
   d
  r4   d
   r2
  r1

等等。

計算 r 值

我們將原始字元的每個位放在 11 位單元的合適位置。我們可以計算多個位組合的偶校驗。每個合併的校驗值是相關 r 位的值。

示例

計算支援合併位 3、5、7、9、11 等的偶校驗。最後 11 位程式碼透過傳輸線路傳送。

更新於:2021年5月5日

2K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告