漢明碼
編輯在計算機科學和電信中,漢明碼是線性糾錯碼家族。 漢明碼可以檢測一位和兩位錯誤,或者在不檢測未糾正錯誤的情況下糾正一位錯誤。 相比之下,簡單的奇偶校驗碼不能糾正錯誤,只能檢測奇數位的錯誤。 漢明碼是完美的代碼,也就是說,它們實現了塊長度和最小距離為三的代碼的最高可能率。Richard W. Hamming 于 1950 年發明了漢明碼,作為一種自動糾正穿孔卡讀卡器引入的錯誤的方法 . 在他的原始論文中,Hamming 詳細闡述了他的總體思路,但特別關注將三個奇偶校驗位添加到四位數據的 Hamming(7,4) 碼。
在數學上,漢明碼是一類二進制線性碼。 對于每個整數 r ≥ 2,都有一個碼字,塊長度 n = 2r ? 1,消息長度 k = 2r ? r ? 1。因此漢明碼 s 的速率為 R = k / n = 1 ? r / ( 2r ? 1),這對于最小距離為 3 的代碼(即從任何代碼字到任何其他代碼字所需的最少比特更改次數為 3)和塊長度為 2r ? 1 的代碼來說是最高可能的。奇偶校驗 -漢明碼的校驗矩陣是通過列出長度為r的所有非零列來構造的,這意味著漢明碼的對偶碼是縮短的阿達瑪碼。 奇偶校驗矩陣具有任意兩列成對線性無關的性質。
由于漢明碼添加到數據中的冗余有限,它們只能在錯誤率較低時檢測和糾正錯誤。 計算機內存(通常是RAM)就是這種情況,比特錯誤極其罕見,漢明碼被廣泛使用,而具有這種糾錯系統的RAM就是ECC RAM(ECC內存)。 在這種情況下,通常使用具有一個額外奇偶校驗位的擴展漢明碼。 擴展的漢明碼實現了四的漢明距離,這使得解碼器能夠區分何時最多出現一個一位錯誤以及何時發生任何兩位錯誤。 從這個意義上說,擴展漢明碼是單糾錯雙檢錯,簡稱SECDED。
歷史
編輯漢明碼的發明者理查德·漢明 (Richard Hamming) 于 1940 年代后期在貝爾實驗室工作,研究的是貝爾 V 型計算機,這是一種基于繼電器的機電式機器,循環時間以秒為單位。 輸入通過八分之七英寸寬的穿孔紙帶輸入,每行最多有六個孔。 在工作日,當檢測到繼電器出現錯誤時,機器會停止并閃爍指示燈,以便操作員糾正問題。 在下班后和周末,當沒有操作員時,機器會繼續進行下一項工作。
Hamming 在周末工作,并且由于檢測到錯誤而不得不從頭開始重新啟動他的程序,這讓他越來越沮喪。 在一次錄音采訪中,漢明說,所以我說,“該死,如果機器能檢測到錯誤,為什么它不能定位錯誤的位置并糾正它?”。 在接下來的幾年里,他致力于糾錯問題,開發了一系列越來越強大的算法。 1950 年,他發表了現在稱為漢明碼的內容,至今仍在 ECC 內存等應用中使用。
早于漢明的代碼
在漢明碼之前使用了許多簡單的錯誤檢測代碼,但在相同的空間開銷下,沒有一個像漢明碼那樣有效。
奇偶校驗
奇偶校驗添加一位,指示前面數據中的個數(值為 1 的位位置)是偶數還是奇數。 如果在傳輸中改變了奇數位,消息將改變奇偶校驗,此時可以檢測到錯誤; 然而,改變的位可能是奇偶校驗位本身。 最常見的約定是奇偶校驗值為 1 表示數據中有奇數個 1,奇偶校驗值為 0 表示有偶數個 1。 如果更改的位數為偶數,則校驗位有效,不會檢測到錯誤。
此外,奇偶校驗不指示哪個位包含錯誤,即使它可以檢測到錯誤。 數據必須完全丟棄并從頭開始重新傳輸。 在嘈雜的傳輸介質上,成功的傳輸可能需要很長時間,或者可能永遠不會發生。 然而,雖然奇偶校驗的質量很差,但由于它只使用一個位,因此這種方法的開銷最少。
五選二代碼
五分之二代碼是一種編碼方案,它使用由三個 0 和兩個 1 組成的五個位。 這提供了十種可能的組合,足以表示數字 0–9。 該方案可以檢測所有單個位錯誤、所有奇數位錯誤和一些偶數位錯誤(例如兩個 1 位的翻轉)。 但是它仍然無法糾正任何這些錯誤。
重復
當時使用的另一個代碼多次重復每個數據位,以確保它被正確發送。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/195925/