資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究糾錯碼 - 海明碼
錯誤和糾錯碼
當位元在計算機網路上傳輸時，由於干擾和網路問題，它們可能會被損壞。損壞的位元會導致接收方收到偽資料，這些資料被稱為錯誤。
糾錯碼 (ECC) 是一系列由特定演算法生成的數字，用於檢測和消除透過噪聲通道傳輸的資料中的錯誤。糾錯碼能夠確定已損壞的位元的確切數量以及損壞位元的位置，但在演算法的限制範圍內。
ECC 可以廣泛地分為兩種型別 -
分組碼 - 訊息被分成固定大小的位元塊，並在其中新增冗餘位元以進行錯誤檢測或糾正。
卷積碼 - 訊息包含任意長度的資料流，奇偶校驗符號是透過對資料流進行布林函式的滑動應用生成的。
海明碼
海明碼是一種分組碼，能夠檢測多達兩個同時發生的位元錯誤並糾正單個位元錯誤。它由 R.W. 海明開發用於糾錯。
在這種編碼方法中，源透過在訊息中插入冗餘位元來對訊息進行編碼。這些冗餘位元是在訊息本身的特定位置生成並插入的額外位元，用於啟用錯誤檢測和糾正。當目標收到此訊息時，它會執行重新計算以檢測錯誤並找到出錯的位元位置。
海明碼編碼訊息
傳送方用於編碼訊息的過程包括以下步驟 -
步驟 1 - 計算冗餘位元的數量。
步驟 2 - 安排冗餘位元的位置。
步驟 3 - 計算每個冗餘位元的值。
一旦冗餘位元嵌入到訊息中，它就會發送給使用者。
步驟 1 - 計算冗餘位元的數量。
如果訊息包含 *m*𝑚 個數據位元，則向其新增 *r*𝑟 個冗餘位元，以便 *m*𝑟 能夠指示至少 (*m* + *r*+ 1) 種不同的狀態。這裡，(*m* + *r*) 表示在每個 (*𝑚* + *𝑟*) 位元位置中錯誤的位置，而一個額外的狀態表示沒有錯誤。由於，*r*𝑟 個位元可以指示 2r𝑟 個狀態，因此 2r𝑟 必須至少等於 (*m* + *r* + 1)。因此，以下等式應該成立 2r ≥ m+r+1
步驟 2 - 安排冗餘位元的位置。
將 *r* 個冗餘位元放置在 2 的冪次方位元位置，即 1、2、4、8、16 等。在本文的其餘部分，它們被稱為 *r1*（在位置 1）、*r2*（在位置 2）、*r3*（在位置 4）、*r4*（在位置 8）等等。
步驟 3 - 計算每個冗餘位元的值。
冗餘位元是奇偶校驗位元。奇偶校驗位元是一個額外的位元，它使 1 的數量為偶數或奇數。兩種型別的奇偶校驗是 -
偶校驗 - 這裡訊息中的總位元數變為偶數。
奇校驗 - 這裡訊息中的總位元數變為奇數。
每個冗餘位元 ri 是基於其位元位置計算的奇偶校驗，通常是偶校驗。它涵蓋所有位元位置，這些位置的二進位制表示在其 ith 位置包含 1，除了 ri 的位置。因此 -
r1 是所有資料位元的奇偶校驗位元，這些資料位元的位置的二進位制表示在最低有效位包含 1，不包括 1（3、5、7、9、11 等）
r2 是所有資料位元的奇偶校驗位元，這些資料位元的位置的二進位制表示在從右數起的第 2 位包含 1，不包括 2（3、6、7、10、11 等）
r3 是所有資料位元的奇偶校驗位元，這些資料位元的位置的二進位制表示在從右數起的第 3 位包含 1，不包括 4（5-7、12-15、20-23 等）
海明碼解碼訊息
接收方一旦收到傳入的訊息，就會執行重新計算以檢測錯誤並糾正錯誤。重新計算的步驟如下 -
步驟 1 - 計算冗餘位元的數量。
步驟 2 - 安排冗餘位元的位置。
步驟 3 - 奇偶校驗檢查。
步驟 4 - 錯誤檢測和糾正
步驟 1 - 計算冗餘位元的數量
使用與編碼相同的公式，確定冗餘位元的數量。
2r ≥ m + r + 1 其中 *m* 是資料位元的數量，*r* 是冗餘位元的數量。
步驟 2 - 安排冗餘位元的位置
將 *r* 個冗餘位元放置在 2 的冪次方位元位置，即 1、2、4、8、16 等。
步驟 3 - 奇偶校驗檢查
基於資料位元和冗餘位元計算奇偶校驗位元，使用與生成 c1、c2、c3、c4 等相同的規則。因此
c1 = 奇偶校驗(1、3、5、7、9、11 等)
c2 = 奇偶校驗(2、3、6、7、10、11 等)
c3 = 奇偶校驗(4-7、12-15、20-23 等)
步驟 4 - 錯誤檢測和糾正
計算奇偶校驗位元二進位制值的十進位制等效值。如果為 0，則沒有錯誤。否則，十進位制值給出出錯的位元位置。例如，如果 c1c2c3c4 = 1001，則表示位置 9（1001 的十進位制等效值）處的位元有錯誤。翻轉該位元以獲取正確的訊息。
51K+ 次檢視
