資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究漢明碼用於單錯誤糾正，雙錯誤檢測
漢明碼是一種分組碼，能夠檢測最多兩個同時發生的位元錯誤並糾正單個位元錯誤。它是由 R.W. 漢明為糾錯而開發的。
在這種編碼方法中，源透過在訊息中插入冗餘位來對訊息進行編碼。這些冗餘位是在訊息本身中生成並插入到特定位置的額外位，以實現錯誤檢測和糾正。當目標接收此訊息時，它會執行重新計算以檢測錯誤並找到出現錯誤的位位置。
漢明碼用於單錯誤糾正
漢明碼糾正單一錯誤的過程包括兩部分，即傳送端編碼和接收端解碼。
使用漢明碼編碼訊息
傳送方用於編碼訊息的過程包括以下步驟：
步驟 1 - 計算冗餘位的數量。
步驟 2 - 確定冗餘位的位置。
步驟 3 - 計算每個冗餘位的值。
一旦將冗餘位嵌入到訊息中，就會將其傳送到目標。
步驟 1 - 計算冗餘位的數量。
如果訊息包含 *m* 個數據位，則會向其新增 *r* 個冗餘位，以便能夠指示至少 *(m + r + 1)* 個不同的狀態。這裡，*(m + r)* 指示每個位元位置的錯誤位置，一個額外的狀態指示沒有錯誤。由於 *r* 個位元可以指示 *2r* 個狀態，因此 *2r* 必須至少等於 *(m + r + 1)*。因此，以下等式應成立：
2r ≥ 𝑚 + 𝑟 + 1
**示例 1** - 如果資料為 7 位，即 *m = 7*，則滿足上述等式的 *r* 的最小值為 4，(24 ≥ 7 + 4 + 1)。編碼訊息中的位元總數，*(m + r) = 11*。這被稱為 (11,4) 碼。
步驟 2 - 確定冗餘位的位置。
將 *r* 個冗餘位放置在 2 的冪次方的位元位置，即 1、2、4、8、16 等。在本文的其餘部分中，它們被稱為 *r1*（在位置 1）、*r2*（在位置 2）、*r3*（在位置 4）、*r4*（在位置 8）等等。
**示例 2** - 如果 *m = 7* 對應於 4，則冗餘位的位置如下：
步驟 3 - 計算每個冗餘位的值。
冗餘位是奇偶校驗位。奇偶校驗位是一個額外的位，它使 1 的數量為偶數或奇數。兩種型別的奇偶校驗是：
**偶校驗** - 這裡訊息中的位元總數變為偶數。
**奇校驗** - 這裡訊息中的位元總數變為奇數。
每個冗餘位 ri 根據其位元位置計算奇偶校驗，通常是偶校驗。它涵蓋所有位元位置，其二進位制表示在第 *ith* 位置包含 1，除了 *ri* 的位置。因此：
*r1 * 是所有資料位的奇偶校驗位，其二進位制表示在最低有效位包含 1，不包括 1（3、5、7、9、11 等）
*r2* 是所有資料位的奇偶校驗位，其二進位制表示在從右起第 2 位包含 1，不包括 2（3、6、7、10、11 等）
*r3* 是所有資料位的奇偶校驗位，其二進位制表示在從右起第 3 位包含 1，不包括 4（5-7、12-15、20-23 等）
**示例 3** - 假設訊息 1100101 需要使用偶校驗漢明碼進行編碼。這裡，*m = 7* 並且 *r* 為 4。冗餘位的值如下：
因此，傳送的訊息將是 11000101100。
漢明碼訊息解碼
接收方收到傳入訊息後，會執行重新計算以檢測錯誤並進行糾正。重新計算的步驟如下：
步驟 1 - 計算冗餘位的數量。
步驟 2 - 確定冗餘位的位置。
步驟 3 - 奇偶校驗檢查。
步驟 4 - 錯誤檢測和糾正
步驟 1) 計算冗餘位的數量
使用與編碼中相同的公式，確定冗餘位的數量。
2r ≥ 𝑚 + 𝑟 + 1
其中 *m* 是資料位的數量，*r* 是冗餘位的數量。
步驟 2) 確定冗餘位的位置
將 *r* 個冗餘位放置在 2 的冪次方的位元位置，即 1、2、4、8、16 等。
步驟 3) 奇偶校驗檢查
根據資料位和冗餘位使用與生成 c1、c2、c3、c4 等相同的規則計算奇偶校驗位。因此
c1 = 奇偶校驗(1、3、5、7、9、11 等)
c2 = 奇偶校驗(2、3、6、7、10、11 等)
c3 = 奇偶校驗(4-7、12-15、20-23 等)
步驟 4) 錯誤檢測和糾正
計算奇偶校驗位二進位制值的十進位制等價物。如果為 0，則沒有錯誤。否則，十進位制值給出出現錯誤的位位置。例如，如果 *c1c2c3c4* = 1001，則表示位置 9（1001 的十進位制等價物）處的數位有錯誤。該位被翻轉（從 0 變為 1 或從 1 變為 0）以獲得正確的訊息。
**示例 4** - 假設接收到的傳入訊息為 11110101101。
步驟 1 - 首先使用公式 2r ≥ m + r + 1 計算冗餘位的數量。這裡，m + r + 1 = 11 + 1 = 12。使得 2r ≥ 12 的 *r* 的最小值為 4。
步驟 2 - 冗餘位的位置如下：
步驟 3 - 執行偶校驗檢查：
c1 = 偶校驗(1、3、5、7、9、11) = 0
c2 = 偶校驗(2、3、6、7、10、11) = 0
c3 = 偶校驗(4、5、6、7) = 0
c4 = 偶校驗(8、9、10、11) = 0
步驟 4 - 由於校驗位 c1c2c3c4 的值為 0000 = 0，因此此訊息中沒有錯誤。
漢明碼用於雙錯誤檢測
透過新增一個奇偶校驗位作為 MSB（它是所有其他位的異或），可以修改漢明碼以糾正單個錯誤並檢測雙錯誤。
**示例 5** - 如果我們考慮示例 3 中傳送的碼字 11000101100，在新增 P = 異或(1,1,0,0,0,1,0,1,1,0,0) = 0 後，要傳送的新碼字將是 011000101100。
在接收端，錯誤檢測如以下表格所示：
13K+ 次瀏覽
