錯誤檢測與糾正碼

---

---

我們知道，對應於兩個不同範圍的模擬電壓，位元0和1。因此，在從一個系統到另一個系統的二進位制資料傳輸過程中，也可能會新增噪聲。因此，在另一個系統接收到的資料中可能會出現錯誤。

這意味著位元0可能會變為1，或者位元1可能會變為0。我們無法避免噪聲的干擾。但是，我們可以首先透過檢測是否存在任何錯誤並糾正這些錯誤來恢復原始資料。為此，我們可以使用以下程式碼。

• 錯誤檢測碼
• 錯誤糾正碼

錯誤檢測碼

錯誤檢測碼用於檢測接收到的資料（位元流）中存在的錯誤。這些程式碼包含一些位元，這些位元被包含（附加）到原始位元流中。如果在原始資料（位元流）傳輸過程中發生錯誤，這些程式碼會檢測到該錯誤。

示例 - 奇偶校驗碼，漢明碼。

錯誤糾正碼

錯誤糾正碼用於糾正接收到的資料（位元流）中存在的錯誤，以便我們獲得原始資料。錯誤糾正碼也使用類似於錯誤檢測碼的策略。

示例 - 漢明碼。

因此，為了檢測和糾正錯誤，在傳輸時會在資料位後面附加額外的位。

奇偶校驗碼

很容易將一個奇偶校驗位包含（附加）到原始位元流的MSB左側或LSB右側。根據所選奇偶校驗的型別，奇偶校驗碼有兩種型別，即偶校驗碼和奇校驗碼。

偶校驗碼

如果二進位制碼中存在偶數個1，則偶校驗位的取值為零。否則，它應該為一。這樣，偶校驗碼中存在偶數個1。偶校驗碼包含資料位和偶校驗位。

下表顯示了每個3位二進位制碼對應的偶校驗碼。這裡，偶校驗位包含在二進位制碼的LSB右側。

這裡，偶校驗碼中存在的位元數為4。因此，這些偶校驗碼中可能的偶數個1為0、2和4。

• 如果另一個系統接收了這些偶校驗碼之一，則接收到的資料中沒有錯誤。除偶校驗位之外的位與二進位制碼的位相同。
• 如果另一個系統接收到的不是偶校驗碼，則接收到的資料中存在錯誤。在這種情況下，我們無法預測原始二進位制碼，因為我們不知道錯誤的位位置。

因此，偶校驗位僅用於檢測接收到的奇偶校驗碼中的錯誤。但它不足以糾正錯誤。

奇校驗碼

如果二進位制碼中存在奇數個1，則奇校驗位的取值為零。否則，它應該為一。這樣，奇校驗碼中存在奇數個1。奇校驗碼包含資料位和奇校驗位。

下表顯示了每個3位二進位制碼對應的奇校驗碼。這裡，奇校驗位包含在二進位制碼的LSB右側。

這裡，奇校驗碼中存在的位元數為4。因此，這些奇校驗碼中可能的奇數個1為1和3。

• 如果另一個系統接收了這些奇校驗碼之一，則接收到的資料中沒有錯誤。除奇校驗位之外的位與二進位制碼的位相同。
• 如果另一個系統接收到的不是奇校驗碼，則接收到的資料中存在錯誤。在這種情況下，我們無法預測原始二進位制碼，因為我們不知道錯誤的位位置。

因此，奇校驗位僅用於檢測接收到的奇偶校驗碼中的錯誤。但它不足以糾正錯誤。

漢明碼

漢明碼可用於檢測和糾正接收到的資料中存在的錯誤。此程式碼使用多個奇偶校驗位，我們必須將這些奇偶校驗位放置在2的冪次方位置。

使以下關係成立（有效）的最小'k'值就是所需的奇偶校驗位數。

$$\mathrm{2^{k} \: \geq \: n \: + \: k \: + \: 1}$$

其中，

'n'是二進位制碼（資訊）中的位元數

'k'是奇偶校驗位的數量

因此，漢明碼中的位元數等於n + k。

設漢明碼為$\mathrm{b_{n+k}b_{n+k-1} \: ..... \: b_{3}b_{2}b_{1}}$和奇偶校驗位$\mathrm{p_{k}, \: p_{k-1}, \: .... \: p_{1}}$。我們只能將'k'個奇偶校驗位放在2的冪次方位置。在其餘的位元位置，我們可以放置二進位制碼的'n'個位元。

根據需要，我們可以在形成漢明碼時使用偶校驗或奇校驗。但是，為了找出接收到的資料中是否存在任何錯誤，應使用相同的奇偶校驗技術。

請按照此過程查詢奇偶校驗位。

• 根據位元位置b₃、b₅、b₇等中存在的1的數量，找到p₁的值。所有這些位元位置（字尾）在其等效的二進位制表示中，在2⁰的位值處都有'1'。
• 根據位元位置b₃、b₆、b₇等中存在的1的數量，找到p₂的值。所有這些位元位置（字尾）在其等效的二進位制表示中，在2¹的位值處都有'1'。
• 根據位元位置b₅、b₆、b₇等中存在的1的數量，找到p₃的值。所有這些位元位置（字尾）在其等效的二進位制表示中，在2²的位值處都有'1'。

• 類似地，找到奇偶校驗位的其他值。

按照以下步驟查詢**校驗位**。

• 根據位位置 b₁、b₃、b₅、b₇ 等中存在的 1 的數量，找到 c₁ 的值。所有這些位位置（字尾）在其等效的二進位制表示中，在 2⁰ 的位值處都為 '1'。
• 根據位位置 b₂、b₃、b₆、b₇ 等中存在的 1 的數量，找到 c₂ 的值。所有這些位位置（字尾）在其等效的二進位制表示中，在 2¹ 的位值處都為 '1'。
• 根據位位置 b₄、b₅、b₆、b₇ 等中存在的 1 的數量，找到 c₃ 的值。所有這些位位置（字尾）在其等效的二進位制表示中，在 2² 的位值處都為 '1'。
• 類似地，找到校驗位的其他值。

接收到的資料中校驗位的十進位制等效值給出錯誤所在的位位置的值。只需對該位位置中存在的值取反即可。因此，在移除奇偶校驗位後，我們將獲得原始的二進位制程式碼。

示例 1

讓我們找到二進位制程式碼 d₄d₃d₂d₁ = 1000 的漢明碼。考慮偶校驗位。

給定二進位制程式碼中的位數為 n=4。

我們可以使用以下數學關係找到所需的奇偶校驗位數。

$$\mathrm{2^{k} \: \geq \: n \: + \: k \: + \: 1}$$

在上述數學關係中代入 n=4。

$$\mathrm{\Rightarrow \: 2^{k} \: \geq \: 4+k+1}$$

$$\mathrm{\Rightarrow \: 2^{k} \: \geq \: 5+k}$$

滿足上述關係的 k 的最小值為 3。因此，我們需要 3 個奇偶校驗位 p₁、p₂ 和 p₃。因此，漢明碼中的位數將為 7，因為二進位制程式碼中有 4 位，奇偶校驗位有 3 位。我們必須將奇偶校驗位和二進位制程式碼的位放置在漢明碼中，如下所示。

**7 位漢明碼**為 -

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1} \: = \: d_{4}d_{3}d_{2}p_{3}d_{1}p_{2}bp_{1}}$$

透過代入二進位制程式碼的位，漢明碼將為

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1} \: = \: 100p_{3}Op_{2}p_{1}}$$

現在，讓我們找到奇偶校驗位。

$$\mathrm{p_{1} \: = \: b_{7} \: \oplus \: b_{5} \: \oplus \: b_{3} \: = \: 1 \: \oplus \: 0 \: \oplus \: 0 \: = \: 1}$$

$$\mathrm{p_{2} \: = \: b_{7} \: \oplus \: b_{6} \: \oplus \: b_{3} \: = \: 1 \: \oplus \: 0 \: \oplus \: 0 \: = \: 1}$$

$$\mathrm{p_{3} \: = \: b_{7} \: \oplus \: b_{6} \: \oplus \: b_{5} \: = \: 1 \: \oplus \: 0 \: \oplus \: 0 \: = \: 1}$$

透過代入這些奇偶校驗位，**漢明碼**將為 -

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1} \: = \: 1001011}$$

示例 2

在上面的示例中，我們得到的漢明碼為 -

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001011}$$.

現在，讓我們找到接收到的程式碼為 - 時的錯誤位置。

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001111}$$

現在，讓我們找到校驗位。

$$\mathrm{c_{1} \: = \: b_{7} \: \oplus \: b_{5} \: \oplus \: b_{3} \: \oplus \: b_{1} \: = \: 1 \: \oplus \: 0 \: \oplus \: 1 \: \oplus1 \: = \: 1}$$

$$\mathrm{c_{2} \: = \: b_{7} \: \oplus \: b_{6} \: \oplus \: b_{3} \: \oplus \: b_{2} \: = \: 1 \: \oplus \: 0 \: \oplus \: 1 \: \oplus \: 1 \: = \: 1}$$

$$\mathrm{c_{3} \: = \: b_{7} \: \oplus \: b_{6} \: \oplus \: b_{5} \: \oplus \: b_{4} \: = \: 1 \: \oplus \: 0 \: \oplus \: 0 \: \oplus \: 1 \: = \: 0}$$

校驗位的十進位制值給出接收到的漢明碼中錯誤的位置。

$$\mathrm{c_{3}c_{2}c_{1} \: = \: \left ( 011 \right )_{2} \: = \: \left ( 3 \right )_{10}}$$

因此，錯誤出現在漢明碼的第三位 (b₃) 中。只需對該位中存在的值取反，並刪除奇偶校驗位以獲得原始的二進位制程式碼。