# 7.4 Error detection and corrction

影響存儲單元數據路徑的電信號的動態物理相互作用可能會導致存儲和檢索二進制信息時偶爾出現錯誤。因此，我們將可以通過採用error-detecting和error-correcting來提高存儲單元的可靠性。

最常見的錯誤檢測方案是奇偶校驗位，奇偶校驗位隨數據字一起生成並存儲在存儲器中。從內存中讀取後檢查單詞的奇偶校驗。如果讀出的位奇偶校驗正確，則數據字被接受。如果奇偶校驗結果發生反轉，則會檢測到錯誤，但無法更正。

糾錯碼生成多個奇偶校驗位，這些奇偶校驗位與數據字一起存儲在內存中。每個校驗位都是數據字中一組位的奇偶校驗。

當從內存中讀回該字時，相關的奇偶校驗位也會從內存中讀取，並與從已讀取數據生成的一組新校驗位進行比較。

當一個位的值在寫入或讀取操作期間從 1 變為 0 或從 0 變為 1 時，將發生單個錯誤。如果識別出錯誤的特定位，則可以通過對錯誤位進行補碼來糾正錯誤。

### Hamming

會添加 k 個奇偶校驗位到 n 位的資料字，構成一個 n + k 位的新字。位位置按照從 1 到 n + k 的順序編號。那些編號為 2 的整數次冪的位置被保留為奇偶校驗位，其餘的位置則為資料位。這種編碼方式可以與任何長度的單詞一起使用。
舉例：在課本上給的bit position 包含了四個奇偶校驗位，
P1、P2、P4和P8分別位於位置1、2、4和8。

數據字在剩下的位置。 每個奇偶校驗位都是計算
P =位（3，5，7、9、11）的 XOR = 0
P2 = 位（3、6、7、10、11）的 XOR = 0
P4 = 位 (5,6,7,12) 的 XOR = 1000 = 1
P8 = 位 (9,10,11,12) 的 XOR = 0100 = 1
執行exclusive-OR operation會讓1變亮中的奇數's，偶數's的奇數
所以會使的奇偶校驗位的總數1彙總是偶數

接著我們再把8bit+4個奇偶校驗位存在記憶體裡
(圖片下方的Bit positon)

當從內存讀取 12 位時，將再次檢查它們是否存在錯誤。 對等點
在相同的位組合上進行檢查，包括奇偶校驗位。C1、C2、C4、C8的狀況，
下面三種狀況
由於位是以偶校驗存儲的, 結果, C=C8C4C2C1 = 0000，表示
沒有錯誤發生. 但是，如果 CT 0，那麼 4 位二進制數
校驗位給出錯誤位的位置。 例如，考慮以下三種情況:
1.與原本相同 - No error
2.bit 1的輸出結果不同，bit 1是有輸入出錯誤的狀況的
3.bit 5的輸出結果不同，bit 5是有輸入出錯誤的狀況的

#### 所以換個說法，Hamming 其實就是把原始資料重複好幾次來校正是否有錯誤

沒有錯誤，我們有 C = 0000;在位 1 中有一個錯誤，我們得到 C = 0001;
在第5位有一個錯誤，我們得到C=0101 當二進制數C不等於0000時，
它給出位在錯誤中的位置。 這個錯誤可以通過補充以下內容來糾正:

數據字或奇偶校驗位中可能發生的錯誤。
Hamming 代碼可用於任何長度的數據字。而一般來說，Hamming由k校驗位和n數據位組成，共計n+k位。 A.
值C由k位組成,範圍爲0至2k-1.

這些值，通常是零，用來指示沒有檢測到錯誤，留下2k-1
值來指示哪n+k位是錯誤. 這些2k-1值中的每一個可以
用來唯一地描述錯誤中的位。 因此，k的範圍必須等於或大於nk，給定關係
用k來解n，我們得到:
這個關係給出了一個公式，用於確定可以執行以下操作的數據位數:
和k校驗位一起使用。

例如，當 k = 3 時，數據位數n<(23-1-3)=4。
對於 k=4,我們有 24-1-4=11,給出的值是:
n < 11. 數據字可少於11位，但必須至少有5位。
否則，只需要3個校驗位. 這就說明對8個數據位使用4個校驗位是合理的。

在 Hamming 代碼中 ck 奇偶校驗位，我們注意到
代碼中的分組和二進制計數序列中的 1 位的位置
h 位組以 1、2、4、8 的冪開始

### Hamming code的特性

Hamming code 只能檢測並糾正一個錯誤。通過在編碼字中添加另一個奇偶校驗位，其可用於糾正單錯誤和檢測雙錯誤。如果我們包括這個額外的奇偶校驗位，那麼之前的 12 位編碼字將變為 001110010100P13，其中 P13 是根據其他 12 位的異或計算得出的。這會產生 13 位字 0011100101001（偶校驗）。

當從內存中讀取 13 位字時，將評估校驗位，以及整個 13 位的奇偶校驗 P。如果 P = 0，則奇偶校驗正確（偶校驗），但如果 P = 1，則 13 位的奇偶校驗不正確（奇校驗）。可能會出現以下四種情況：

如果 P = 0，則奇偶校驗是正確的（偶校驗），但如果 P = 1，則奇偶校驗值大於 1。
這13位是不正確的（奇偶校驗）。 可能會出現以下四種情況:
如果 C = 0 ， P = 0，則不會發生錯誤。
如果 C 不等於 0 和 P = 1，則發生一個可以更正的錯誤。
如果 C 不等於 0 和 p = 0，則會出現一個雙重錯誤，該錯誤被檢測到，但不能更正
如果 C = 0， P = 1， 有一個錯誤會出現P13。
這個方法是有可能會偵測到兩個以上的錯誤的。

Intergrated circuits 會使用修改過的Hamming code來檢查奇偶校驗位。一個錯誤可以立刻被糾正，兩個以上可以被檢測到修改過的hamming code可以更有效對奇偶校驗做XOR的運算。

使用 8 位數據字和 5 位校驗字的典型集成電路是 74637 型 IC。其他集成電路可用於 16 位和 32 位數據字。這些電路可以與存儲單元結合使用，以在寫入和讀取操作期間糾正單個錯誤或檢測雙重錯誤。