《計算機組成與體系結構（原書第4版）》 —2.7.2　漢明碼

2.7.2　漢明碼

與磁盤系統相比，數據通信通道更容易出錯，同時也更能容忍錯誤。在數據通信中，只要有檢測錯誤的能力就可以。如果通信設備確定一個消息包含一個錯誤位，那么它要做的就是請求重傳。存儲系統和主存沒有這么奢侈。磁盤有時可以是一個金融交易或其他不可重現的實時數據集合的唯一存儲庫。因此，存儲設備和主存必須具備不僅可以檢測還能糾正一定數量錯誤的能力。

錯誤恢復編碼在過去一個世紀已被深入研究。漢明碼是最有效的編碼之一，也是最老的編碼。漢明碼是對奇偶校驗概念的改進，可以提升錯誤檢測和校正能力，添加到信息字中的奇偶校驗位的數量會成比例地增加。在可能發生隨機錯誤的情況下使用漢明碼。對于隨機錯誤，我們假定每位的失敗具有固定的發生概率，且與其他位故障無關。計算機主存通常會遇到這樣的錯誤，所以在下面的討論中，我們會在主存位錯誤檢測和糾正的環境下介紹漢明碼。

漢明碼使用的奇偶校驗位也稱為校驗位或冗余位。存儲器字本身由m位組成，但是考慮到錯誤檢測和糾正增加了r位冗余位。因此，最后的字叫作碼字，是一個包含m個數據位和r個校驗位的n位單元。每個數據字是由n=m+r位組成的唯一碼字，如下所示：

漢明距離是指在兩個碼字中有多少位不同。例如，如果我們有以下的兩個碼字：

我們看到它們有3個位置（由*標記）不同，所以這兩個碼字的漢明距離是3。（請注意，還沒有討論過如何創建碼字，我們會盡快做這件事。）

兩個碼字之間的漢明距離在錯誤檢測的環境中很重要。如果兩個碼字的漢明距離為d，那么將一個碼字轉換到另一個碼字有d位單位錯誤的情況就不會被檢測到。因此，如果我們希望創建一個編碼，它可以保證檢測到所有位的錯誤（1位一個錯誤），那么任何兩個碼字之間的漢明距離必須至少為2。如果認為一個n位字不是合法的碼字，那么這個碼字就被認為是一個錯誤的碼字。

若給定一個計算校驗位的算法，則可以構建完整合法的碼字列表。在這個編碼中所有兩個碼字之間的最小漢明距離稱為編碼的最小漢明距離。編碼的最小漢明距離通常由符號D（min）表示，它可以決定其錯誤檢測和糾正能力。簡單來說，對于任何碼字X若想被接收為另一個有效的碼字Y，則在X中必須出現至少D（min）個錯誤。因此，為了檢測k（或更少）位錯誤，該碼的漢明距離必須為D（min）=k+1。漢明碼可以始終檢測D（min）-1個錯誤并糾正(D(min)-1)/2個錯誤　符號? 表示向下取整的函數，是小于等于這個括起來的數的最大整數。例如，8.3=8和 8.9=8。。因此，代碼的漢明距離必須至少為2k+1以能夠糾正k個錯誤。

碼字由使用r個奇偶校驗位的信息字構成。在我們繼續討論錯誤檢測和糾正之前，來看一個簡單的例子。最常見的錯誤檢測使用附加到數據上的單個奇偶校驗位（回顧關于ASCII字符表示的討論）。在這個碼字的任何一位中，一位錯誤會產生錯誤的奇偶校驗。

例2.40假設存儲器具有2個數據位和1個附加在碼字尾部的偶校驗位（因此碼中1數量必須為偶數）。有2個數據位，共有4個可能的字。我們這里列出數據字、對應的奇偶校驗位以及為這4個可能字中的每一個產生的碼字：

得到的碼字有3位。3位允許有8種不同的位模式，如下所示（有效碼字用*標記）：

如果遇到碼字001，則它是無效的，因為它表示出錯已經發生在碼字的某個地方。例如，假設存儲在存儲器中的正確碼字為011，但是一個錯誤使碼字變為001。這個錯誤可以檢測到，但無法糾正。不可能確切地確定有幾位發生了翻轉，即指明哪些位是錯誤的。糾錯碼需要多于1位的奇偶校驗位，如下討論所示。

如果有效的碼字受到兩位錯誤的影響，則上述示例會發生什么？例如，假設碼字內011轉換成000。這個錯誤不能檢測到。如果檢查上述示例中的代碼，將看到D（min）是2，這意味著該代碼僅能保證檢測單個位的錯誤。

我們已經說過了一個編碼的錯誤檢測和糾正能力取決于D（min），從錯誤檢測的角度來看，我們在例2.40中已經看到了這種關系。糾錯需要該編碼包含額外的冗余位，如果編碼是檢測和糾正k個錯誤，那么應確保最小漢明距離D（min）=2k+1。這種漢明距離保證所有合法的碼字都有足夠遠的距離，即使有k個變化，得出的無效碼字也更接近一個唯一有效的碼字。這是很重要的，因為糾錯中使用的方法是將無效碼字轉換為不同位數最少的有效碼字。在例2.41中說明了這個想法。

例2.41假設我們有以下代碼（不用擔心如何生成此代碼，我們很快就會解決這個問題）：

首先，我們來確定D（min）。通過檢查所有可能的碼字對，我們發現最小漢明距離D（min）=3。因此，這段代碼最多可以檢測兩個錯誤并糾正1位錯誤。如何糾正？假設我們讀取的無效碼字是10000。它必須至少有一個錯誤，因為這與任何有效碼字都不匹配。我們現在確定碼字與每個合法碼字之間的漢明距離：它與第一個碼字有1位不同，與第二個是4位，與第三個是2位，與最后一個是3位。因此可生成一個差異向量\[1，4，2，3\]。要想對此碼字進行更正，我們使用最接近的合法碼字自動更正，從而修正為00000。請注意，此“修正”不一定正確！我們假設發生了最小數量的可能錯誤，即1個可能的錯誤。原始碼字可能為10110，當發生兩個錯誤時可能變為10000。

假設確實發生了兩個錯誤。例如，假設我們讀取的無效代碼字是11000。如果我們計算的距離向量為\[2，3，3，2\]，我們看到沒有“最近”的碼字，無法進行修正。如本例所示，如果發生多個錯誤，最小漢明距離3允許只校正一個錯誤，并且不能保證糾正。

在我們的討論中，已經簡單介紹了各種各樣的編碼，但沒有給出如何生成編碼的任何細節。用于生成編碼的方法有很多種，也許更直觀的方法之一是用于編碼設計的漢明碼算法，我們現在介紹它。在解釋算法的實際步驟之前，我們會介紹一些背景資料。

假設我們希望設計的代碼包含m個數據位和r個校驗位，它允許修正單個位錯誤。這意味著有2m個合法的碼字，每個都有唯一的校驗位組合。因為我們專注于單個位錯誤，所以來檢查一組無效碼字與所有合法碼字距離為1的字。

每個有效碼字都有n位，并且這些位都可能會出現錯誤。因此，每個有效碼字有n個距離為1的非法碼字。因此，如果我們關心每一個合法碼字和每一個由一個錯誤組成的無效碼字，我們會得到與每個碼字相關聯的n+1個位模式（1個合法字和n個不合法的字）。因為每個碼字由n位組成，其中n=m+r，所以總共可能有2n個位模式。得到以下不等式：

其中n+1是每個碼字的位模式的數量，2m是合法碼字的數量，2n是可能位模式的總數。因為n=m+r，所以我們可以將不等式重寫為：

或者

這個不等式是很重要的，因為它規定了所需檢查位數量的下限（我們總是盡可能少地使用檢查位）來構造一個具有m個數據位和r個校驗位的代碼，它可校正所有單個位錯誤。

假設我們有長度m=4的數據字，然后：

這意味著r必須大于或等于3。我們選擇r=3。這意味著要建立一個4位數據字的代碼，它應該能糾正單個位的錯誤，我們必須添加3個校驗位。

漢明算法

漢明算法為設計編碼糾正單個位錯誤提供了一種簡單的方法。要為任何大小的內存字構造糾錯代碼，請按照下列步驟操作：

1.確定編碼所需的校驗位數r，然后為n個位（其中n=m+r）編號，從右到左，以1（不是0）開始。

2.位數為2的冪的位是奇偶校驗位，其他是數據位。

3.分配奇偶校驗位以檢查位的位置，如下所示：位b是被奇偶校驗位b1，b2，…，bj檢查的，即b1+b2+…+bj=b（其中“+”表示模2的和）。

我們現在舉一個例子說明這些步驟和糾錯的實際過程。

例2.42使用剛剛描述的漢明碼和偶數校驗位編碼8位的ASCII字符K。（高階位將為零），引入一個單個位錯誤，然后指示如何定位錯誤。

我們首先確定K的碼字。

步驟1：確定必要的校驗位的位數，將這些位加到數據位中，并給所有的n位編號。

因為m=8，所以有（8+r+1）≤2r，這意味著r必須大于或等于4。我們選擇r=4。

步驟2：從1開始從右到左編號n位數，結果是：

奇偶校驗位用框標記。

步驟3：分配奇偶校驗位以檢查不同位的位置。

為了執行這一步，我們首先將所有位的位置寫成2的冪的和：

數字1包含在位置1、3、5、7、9和11中，因此，這個奇偶校驗位將反映這些位置中位的奇偶性。類似地，2包含在位置2、3、6、7、10和11中，因此，位置2中的奇偶位反映了這組位的奇偶性。位置4為位置4、5、6、7和12提供奇偶校驗，位置8為位置8、9、10、11和12提供奇偶校驗，如果在非框空白處寫數據位，然后加入奇偶校驗位，我們得到以下的碼字結果：

因此，字符K的碼字為010011010110。

我們在b9位置引入一個錯誤，生成碼字010111010110。如果我們使用奇偶校驗位來檢查不同位組，可以發現有以下結果。

位置1檢查位置1、3、5、7、9和11：使用偶校驗位，這會產生錯誤。

位置2檢查位置2、3、6、7、10和11：這是正確的。

位置4檢查位置4、5、6、7和12：這是正確的。

位置8檢查位置8、9、10、11和12：這會產生一個錯誤。

奇偶校驗位1和8顯示錯誤。這兩個奇偶校驗位都檢查位置9和11，所以單個位錯誤一定在位置9或11中。但是，因為位置2也檢查了位置11，并表示在其檢查的位的子集中沒有發生錯誤，所以錯誤必然發生在位置9。（我們知道這個錯誤，因為這個錯誤是我們造成的。但是，請注意，即使我們不知道錯誤在哪里，使用這個方法也能確定錯誤的位置并通過簡單地翻轉位來糾正錯誤。）

根據奇偶位被定位的方式，檢測和糾正錯誤位的一個更簡單的方法是把表示錯誤的奇偶校驗位的位置相加。我們發現奇偶校驗位1和8產生了一個錯誤，且1+8=9，這正是發生錯誤的地方。

例2.43使用漢明算法查找3位存儲字的所有碼字，假設使用奇校驗。

我們有8個可能的字：000，001，010，011，100，101，110和111。首先需要確定所需的校驗位數。因為m=3，所以有（3+r+1）≤2r，這意味著r必須大于或等于3。我們選擇r=3。因此，每個碼字都有6位，并且校驗位在位置1、2和4，如下所示：

從以前的例子中我們知道：

●位置1檢查位置1、3和5的奇偶性

●位置2檢查位置2、3和6的奇偶性

●位置4檢查位置4、5和6的奇偶性

因此，我們為每個內存字提供以下碼字：

我們的碼字集合是001011、001100、010010、010101、100001、100110、111000、111111。如果其中任何一個字的某一位被翻轉，我們可以準確地確定是哪個位翻轉并改正它。例如，要發送111，我們實際發送代碼字111111。如果接收到110111，則奇偶校驗位1（它檢查位置1、3和5）是對的，奇偶校驗位2（它檢查位置2、3和6）是對的，但是奇偶校驗位4顯示錯誤，因為只有位置5和6是1，這違反了奇校驗。位置5不可能不正確，因為奇偶校驗位1檢查是正確的。位置6不可能錯誤，因為奇偶校驗位2檢查是正確的。因此，位置4是錯誤的，所以它應從0變為1，得到正確的碼字111111。

在下一章中，您將看到使用簡單的二進制電路實現一個漢明碼是多么容易。由于其簡單性，所以可以廉價地加入漢明碼保護并且對性能影響很小。

其他

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。