海明碼校驗

一、什麼是海明碼校驗

海明碼是一種能夠檢測和糾錯數據傳輸錯誤的編碼方法，由理查德·海明於1949年發明。在數字通信領域廣泛應用，尤其是在無線通信和存儲設備中。

海明碼的基本原理是增加冗餘的位數到原數據中，然後進行傳輸。接收方收到數據後，就會進行校驗，如果發現了錯誤，則利用冗餘位進行糾錯。

二、海明碼校驗的原理

海明碼校驗是在數據傳輸時在原數據中加入校驗位，使得數據中包含更多的信息，同時也增加了一些冗餘的比特位。

比如，一個4位的數據，可以增加3個冗餘位，將7位的編碼進行傳輸，其中，第1位和第2位表示第1個冗餘位，第3位和第4位表示第2個冗餘位，第5、6、7位表示數據本身的位。

接收方在收到數據後，會根據校驗位計算出實際數據的比特位，如果校驗成功，則數據被認為是正確的，否則將進行糾錯操作。

三、海明碼校驗的實現

1. 編碼

def hamming_encode(data: str) -> str:
    n = len(data)
    # 確定r的取值範圍，即滿足 2**r >= n + r + 1 的最小整數r
    for r in range(n):
        if 2**r >= n + r + 1:
            break
    encoded = [""] * (n + r)
    # 將校驗位對應的位置填充為0
    for i in range(n + r):
        if i+1 & i+1-2 == 0:
            continue
        encoded[i] = data[0]
        data = data[1:]
    # 計算校驗位，將值放在對應位置
    for i in range(r):
        pos = 2**i - 1
        count = 0
        j = pos
        while j < n + r:
            count += int(encoded[j])
            j = j + pos + 1
        encoded[pos] = '1' if count % 2 == 1 else '0'
    return "".join(encoded)

2. 校驗

def hamming_decode(data: str) -> str:
    n = len(data)
    # 確定r的取值範圍，即滿足 2**r >= n + r + 1 的最小整數r
    for r in range(n):
        if 2**r >= n + r + 1:
            break
    decoded = ""
    for i in range(r):
        pos = 2**i - 1
        count = 0
        j = pos
        while j < n:
            count += int(data[j])
            j = j + pos + 1
        if count % 2 == 1 and data[pos] == '0':
            data = list(data)
            data[pos] = '1'
            data = "".join(data)
        elif count % 2 == 0 and data[pos] == '1':
            data = list(data)
            data[pos] = '0'
            data = "".join(data)
    for i in range(n):
        if i+1 & i+1-2 == 0:
            continue
        decoded += data[i]
    return decoded

四、海明碼校驗的應用

海明碼校驗在數字數據傳輸領域中應用廣泛：無線通信、存儲設備、計算機網路等。能夠有效地檢測和糾錯由於傳輸雜訊而引起的錯誤，提高了數據傳輸的可靠性。

一般而言，海明碼校驗在數據傳輸中自動進行，用戶並不需要手動進行操作。但是，如果在使用存儲設備時，發生了數據傳輸錯誤，用戶可以使用特定工具對數據進行海明碼校驗和糾錯操作，從而恢複數據的正確性。