糾錯碼

• 1.糾錯碼有什么作用
• 2.主要概念
• • **碼字：m位數據位和r位校驗位組成的n個位單元稱為n位碼字
  • **海明碼距：兩個碼字間不同的位數的個數
• 3.檢錯、糾錯
• • (解釋上面的兩個Why）用圖示的方法理解檢錯能力、糾錯能力與碼距之間的關系
• 4.舉例說明
• • **奇偶校驗：
• 5.一般性方法（這描述的是一種推廣，如何通過增加碼距來使設計方案獲得更好的檢錯、糾錯能力？）
• • 如何構造一個可以糾正(不是檢測)m位數據位中至多有d位錯誤的校驗碼呢？這種校驗碼至少需要多少個校驗位呢？
  • 使用該公式求當要求糾正1（即公式中k取1）位錯誤時所需要的校驗位的個數

1.糾錯碼有什么作用

• 由于電源的尖峰電壓或其他原因，計算機主存的數據在傳輸的過程中偶爾也會出錯。為了防止這些錯誤產生不良后果，我們在主存中采用檢錯和糾錯的方式來處理錯誤。

2.主要概念

**碼字：m位數據位和r位校驗位組成的n個位單元稱為n位碼字

**海明碼距：兩個碼字間不同的位數的個數

?值得注意的是，當存在很多碼字的時候，我們將這些碼字看作是一個集合，該集合的海明碼距的值就是其中任意兩個碼字產生的最小的海明碼距。

3.檢錯、糾錯

檢錯：檢查d位錯誤，編碼的碼距要d+1位。 Why?
糾錯：糾正d位錯誤，編碼的碼距要2d+1位 。 Why?

(解釋上面的兩個Why）用圖示的方法理解檢錯能力、糾錯能力與碼距之間的關系

• 如圖，a₁和a₂代表合法的碼字，它們之間的距離代表了它們的海明碼距，所以說當海明碼距為d時任何小于d位的錯誤都不會使之前的碼字變成一個合法碼字，因此可以用這種原理判斷是否出錯(如果出錯的位數不小于d的時候，一個合法碼字會變成另一個合法碼字，這種錯誤會被當做未出錯來處理)。同樣的道理，為了使碼字出錯之后還可以糾正，我們可以通過將錯誤碼字修改成最“近”的合法碼字的方法來糾正錯誤。如圖中的c₁，我們可以推斷出這個錯誤的碼字更有可能是從合法碼字a1發生錯誤而產生的，所以我們將錯誤碼字c₁修改成a₁來糾正錯誤。因此我們就要保證海明碼距的大小至少是需要糾正的位數的2倍還多出1.
• 因此總的來說碼距越大，檢錯的和糾錯的能力也就越強。

4.舉例說明

**奇偶校驗：

• 一位的奇偶校驗：給數據位添加一個bit的奇偶校驗位的校驗碼被稱為奇偶校驗。根據原數據位中1的位數是奇數或是偶數來設置奇偶校驗位是0或1。
• 奇偶校驗是海明碼距為2的校驗法，也就是說任意一個合法碼字兩個bit位出現錯誤就會變成另一個合法碼字。
• 如， 11010101，對它進行奇校驗，變成011010101（校驗位添加在了最前面，以保證1的個數是奇數個），當它的任意一個位發生改變時，便會導致1的個數變成了偶數而引發錯誤。
• 因此，通過上面的分析可以知道奇偶校驗是一種具有一位錯誤檢錯能力的校驗碼(因為2-1 = 1),但是奇偶校驗沒有糾錯能力(因為(2-1)/2 = 0.5, 0.5 < 1,所以說連一位錯誤都沒辦法糾正)。

5.一般性方法（這描述的是一種推廣，如何通過增加碼距來使設計方案獲得更好的檢錯、糾錯能力？）

如何構造一個可以糾正(不是檢測)m位數據位中至多有d位錯誤的校驗碼呢？這種校驗碼至少需要多少個校驗位呢？

• m位數據位就存在2^m個合法碼字，假設需要r位校驗位，則總共有n = m + r個位。由于校驗位的取值是由數據位直接決定的而且唯一對應（這是一個好的校驗算法必須要做到的事情），所以2ⁿ個碼字中只有2^m個合法碼字。
• 其次，在糾錯碼的應用中通常有多個錯誤碼字對應同一個合法的碼字(使用上面的圖來說明就是a₁和a₂都對應這三個錯誤碼)，一般情況會是多少個呢？我們嘗試著去想，可能是1位錯、2位錯、3位錯、、、d位錯（因為我們可以糾正到d位，d也可以是1、2或3），所以總共會有${\sum }_{k=1}^d{C}_n^k$個錯誤的碼字與一個合法的碼字對應（這里的$C_n^k$是確保錯誤發生的隨機性，計算k個錯誤發生在n個位置的所有可能性）。為了加上一個合法碼字可將公式改寫為${\sum }_{k=0}^d{C}_n^k$，該公式表明一個合合法碼字所對應的所有碼字，因為總共有2^m個合法碼字，所以總共有2^m${\sum }_{k=0}^d{C}_n^k$個不同的碼字。
• 我們現在只要保證n位的糾錯碼能夠表示上述所說的所有不同的碼字就行，即得到不等式
  $$2^m\sum _{k=0}^d{C}_n^k\le 2^n$$
  解這個不等式就能構求出n的最小值，從而求出r的最小值。

使用該公式求當要求糾正1（即公式中k取1）位錯誤時所需要的校驗位的個數

數據位數m需要的校驗位r總長n校驗位與數據位之比(%)

8	4	12	50
16	5	21	31
32	6	38	19
64	7	71	11
128	8	136	6

能得到幾個結論。第一，字長越長，校驗位也需要變長。第二，字長越長，校驗位在字長中的占比的百分比會變小。

**用相同的思想推出能檢測出d位錯誤（不糾正，只發現錯誤）的檢錯碼的推導不等式是
$$(2^m+1)\sum _{k=0}^{d?1}{C}_n^d+1\le 2^n$$
（該公式沒有做系統的推導和證明僅做參考）

總結

以上是生活随笔為你收集整理的计算机组成原理-检错码、纠错码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。