Hamming Code 漢明碼--Python
源自於 https://yaojordan.medium.com/%E8%A8%88%E6%A6%82-hamming-code-%E6%BC%A2%E6%98%8E%E7%A2%BC-78102d680c78
Hamming code is a set of error-correction codes that can be used to detect and correct the errors that can occur when the data is moved or stored from the sender to the receiver.
就是一種錯誤檢查碼，在資料中插入一些檢查碼，看看傳輸過程中有沒有發生錯誤
Hamming code要多長？
公式：2^k ≥ N+k+1，N:資料長度，k: Hamming code長度
直接看題目會比較好理解
EX: 一個二進位值為10101111的8 bits位元組，以偶數同位的漢明碼予以編碼， 以下何者為正確的編碼後二進位值?
Step 1. 先求Hamming code長度
根據上面提到的公式，2^k ≥ 8+k+1，可以求出k=4
也就是說加上Hamming code之後會有12 bits
Step 2. 畫張表格
有12 bits，所以畫12格
重點：Hamming code要填在2的冪次的位置，所以這個例子1、2、4、8格要留空，接著再將原先的值填入表格
Step 3. 求Hamming code
畫一個計算用的圖，將Hamming code的bit欄位由大到小排列，然後將bit數為1的欄位轉成二進制寫出來
將上面紅色的值做XOR運算，其實只要看1有幾個就可以算出來，
偶數個1則為0，奇數個1則為1
現在可以知道我們的Hamming code是0001
Step 4. 將Hamming code填入表中
對照算式上面的欄位，依序將值填入8、4、2、1欄
由此可知，編碼後的二進制值為101001001111
現在來看編碼後的值要怎麼糾錯並改正
EX: 一個漢明碼編碼後的值為1101110101， 請問哪個bit有錯誤，並將其更正
Step 1. 畫張表格
有10 bits，那就畫10格
Step 2. 把bit為1的欄位轉成二進制，做XOR運算
求出來的值為0110，也就是6，表示第6個bit有錯誤
如果沒錯誤的話，求出的值會是0000
Step 3. 更正
將原先數值的第6個bit由1改成0 (反之亦然)
1101110101 -> 1101100101
import tkinter as tk
from tkinter import ttk, messagebox
import math
# --- 核心邏輯函式 (功能保持不變) ---
def hex_to_binary_string(hex_str):
"""將 16 進制轉為 8 bits 的二進制字串，並確保是 16 位元組長度 (2位元組)"""
try:
data_int = int(hex_str, 16)
return format(data_int, '016b')
except ValueError:
return None
def calculate_k(N):
"""根據公式 $2^k \ge N + k + 1$ 計算漢明碼長度 k"""
k = 1
while 2**k < N + k + 1:
k += 1
return k
def encode_hamming(data_binary):
"""將二進制資料進行偶數同位漢明碼編碼"""
N = len(data_binary)
k = calculate_k(N)
total_bits = N + k
encoded_list = [None] * total_bits
data_idx = 0
for i in range(1, total_bits + 1):
if i & (i - 1) == 0:
encoded_list[i-1] = 'P'
else:
if data_idx < N:
encoded_list[i-1] = data_binary[data_idx]
data_idx += 1
else:
encoded_list[i-1] = '0'
for i in range(k):
p_pos = 2**i
count = 0
for j in range(1, total_bits + 1):
if (j & p_pos) != 0:
if encoded_list[j-1] == '1':
count += 1
elif encoded_list[j-1] != 'P':
pass
parity_bit = '0' if count % 2 == 0 else '1'
encoded_list[p_pos - 1] = parity_bit
return "".join(encoded_list), k
def decode_and_correct(encoded_binary):
"""接收編碼後的二進制值，進行糾錯。"""
total_bits = len(encoded_binary)
k_approx = 0
while 2**k_approx < total_bits:
k_approx += 1
k = k_approx - 1
syndrome = 0
syndrome_bits = []
for i in range(k):
p_pos = 2**i
count = 0
for j in range(1, total_bits + 1):
if (j & p_pos) != 0:
if encoded_binary[j-1] == '1':
count += 1
error_bit = 1 if count % 2 != 0 else 0
syndrome += error_bit * p_pos
syndrome_bits.append(str(error_bit))
syndrome_bits.reverse()
syndrome_str = "".join(syndrome_bits)
corrected_binary = list(encoded_binary)
if syndrome != 0 and syndrome <= total_bits:
error_index = syndrome - 1
corrected_binary[error_index] = '0' if corrected_binary[error_index] == '1' else '1'
return syndrome, "".join(corrected_binary), syndrome_str
# --- Tkinter 界面邏輯 ---
class HammingCodeApp:
def __init__(self, master):
self.master = master
master.title("漢明碼編碼與糾錯程式")
# 設置風格
style = ttk.Style()
style.configure('TLabel', foreground='black', font=('Arial', 10))
# 為了表格對齊，使用等寬字體設定
style.configure('Red.TLabel', foreground='red', font=('Monospaced', 10, 'bold'))
# 創建主框架
main_frame = ttk.Frame(master, padding="10")
main_frame.pack(fill='both', expand=True)
# 創建左右分欄框架
self.split_frame = ttk.Frame(main_frame)
self.split_frame.pack(fill='both', expand=True, pady=10)
# 左側框架 (編碼)
self.left_frame = ttk.Frame(self.split_frame, padding="10")
self.left_frame.pack(side='left', fill='both', expand=True, padx=(0, 5))
# 右側框架 (糾錯)
self.right_frame = ttk.Frame(self.split_frame, padding="10")
self.right_frame.pack(side='right', fill='both', expand=True, padx=(5, 0))
# ------------------------------------
# 1. 左側 - 編碼部分 (Encoding)
# ------------------------------------
encode_group = ttk.LabelFrame(self.left_frame, text="一、漢明碼編碼 (偶數同位)", padding="10")
encode_group.pack(fill='x', pady=5)
# 輸入
input_row = ttk.Frame(encode_group)
input_row.pack(fill='x', pady=5)
ttk.Label(input_row, text="輸入 2 位元組 (4位) 16 進制數字:").pack(side='left', padx=(0, 10))
self.hex_input = ttk.Entry(input_row, width=8)
self.hex_input.pack(side='left', padx=(0, 10))
self.hex_input.insert(0, "AB4F")
# 設置按鈕寬度為 20 (確保大小相同)
ttk.Button(input_row, text="執行編碼步驟", command=self.run_encoding, width=20).pack(side='left')
# 輸出步驟標籤
self.output_frame_encode = ttk.LabelFrame(self.left_frame, text="編碼步驟輸出", padding="10")
self.output_frame_encode.pack(fill='both', expand=True, pady=5)
self.results_labels = []
# ------------------------------------
# 2. 右側 - 糾錯部分 (Decoding/Correction)
# ------------------------------------
decode_group = ttk.LabelFrame(self.right_frame, text="二、糾錯與改正", padding="10")
decode_group.pack(fill='x', pady=5)
# 輸入
input_row_decode = ttk.Frame(decode_group)
input_row_decode.pack(fill='x', pady=5)
ttk.Label(input_row_decode, text="輸入編碼後二進制值 (用於測試):").pack(side='top', anchor='w')
self.encoded_input = ttk.Entry(input_row_decode, width=28)
self.encoded_input.pack(side='top', fill='x', pady=5)
self.encoded_input.insert(0, "11011101010010110100")
# 設置按鈕寬度為 20 (確保大小相同)
ttk.Button(input_row_decode, text="執行糾錯步驟", command=self.run_correction, width=20).pack(side='top', fill='x')
# 輸出步驟標籤
self.output_frame_decode = ttk.LabelFrame(self.right_frame, text="糾錯步驟輸出", padding="10")
self.output_frame_decode.pack(fill='both', expand=True, pady=5)
self.correction_labels = []
def clear_labels(self, frame, label_list):
"""清除舊的輸出標籤"""
for label in label_list:
label.destroy()
label_list.clear()
def add_result_label(self, frame, text, style='TLabel', label_list=None):
"""添加新的輸出標籤，使用等寬字體輔助表格對齊"""
if text.startswith(" 位置:") or text.startswith(" 資料:") or text.startswith(" 接收值:"):
# 對於表格輸出，使用等寬紅字，不設置 wraplength
label = ttk.Label(frame, text=text, style='Red.TLabel')
elif style == 'Red.TLabel':
# 其他紅色文字使用等寬紅字，設置 wraplength
label = ttk.Label(frame, text=text, style='Red.TLabel', wraplength=350)
else:
# 一般文字
label = ttk.Label(frame, text=text, style=style, wraplength=350)
label.pack(anchor='w', pady=2)
if label_list is not None:
label_list.append(label)
def run_encoding(self):
"""執行編碼流程"""
self.clear_labels(self.output_frame_encode, self.results_labels)
hex_data = self.hex_input.get().strip()
if len(hex_data) != 4 or not all(c in '0123456789abcdefABCDEF' for c in hex_data):
messagebox.showerror("輸入錯誤", "請輸入 4 位 (2 位元組) 的 16 進制數字。")
return
data_binary = hex_to_binary_string(hex_data)
N = len(data_binary)
k = calculate_k(N)
total_bits = N + k
# --- Step 1: 求 Hamming code 長度 ---
step1_text = f"Step 1. 求 Hamming code 長度: N={N}, k={k}"
self.add_result_label(self.output_frame_encode, step1_text, label_list=self.results_labels)
self.add_result_label(self.output_frame_encode, f" 公式: 2^k ≥ {N} + {k} + 1 -> {2**k} ≥ {N + k + 1}", style='Red.TLabel', label_list=self.results_labels)
self.add_result_label(self.output_frame_encode, f" 總位元數: {total_bits} bits", style='Red.TLabel', label_list=self.results_labels)
# --- Step 2: 畫表格 (包含 P 碼標籤和對齊) ---
encoded_pre, _ = encode_hamming(data_binary)
# 準備帶有 P1, P2, P4... 標籤的列表
encoded_list_labels = []
data_idx = 0
p_index = 0
for i in range(1, total_bits + 1):
if i & (i - 1) == 0: # Parity position (2^n)
p_pos = 2**p_index
encoded_list_labels.append(f'P{p_pos}')
p_index += 1
else: # Data position
encoded_list_labels.append(data_binary[data_idx])
data_idx += 1
# 使用固定寬度 3 (<3) 確保對齊
pos_str = "".join([f"{i+1:<3}" for i in range(total_bits)])
data_pos_str = "".join([f"{label:<3}" for label in encoded_list_labels])
step2_text = "Step 2. 畫表格及填入原資料"
self.add_result_label(self.output_frame_encode, step2_text, label_list=self.results_labels)
# 使用 Monospaced 字體和固定寬度確保對齊
self.add_result_label(self.output_frame_encode, f" 位置: {pos_str}", style='Red.TLabel', label_list=self.results_labels)
self.add_result_label(self.output_frame_encode, f" 資料: {data_pos_str}", style='Red.TLabel', label_list=self.results_labels)
self.add_result_label(self.output_frame_encode, f" 原資料 (16 bits): {data_binary}", style='Red.TLabel', label_list=self.results_labels)
# --- Step 3: 求 Hamming code (包含公式說明 - 合併到一行) ---
encoded_final, k = encode_hamming(data_binary)
step3_text = "Step 3. 求 Hamming code (偶數同位) - 互斥公式說明"
self.add_result_label(self.output_frame_encode, step3_text, label_list=self.results_labels)
# 生成 XOR 互斥公式 (合併成單一字串)
XOR_SYMBOL = '\u2295' # XOR 符號
xor_formula_list = []
for i in range(k):
p_pos = 2**i
contributing_positions = []
for j in range(1, total_bits + 1):
# 檢查 j 是否包含 p_pos，且 j 不是檢查碼本身的位置
if (j & p_pos) != 0 and j != p_pos:
contributing_positions.append(f"Bit({j})")
# 組合成 Px = Bit(a) ⊕ Bit(b) ...
formula = f"P{p_pos} = {f' {XOR_SYMBOL} '.join(contributing_positions)}"
xor_formula_list.append(formula)
# 輸出主說明和合併後的公式，使用 | 符號分隔公式
formula_output = " P碼公式 (XOR運算)：" + " | ".join(xor_formula_list)
# 由於公式很長，必須使用 wraplength，但因為 Label 使用等寬字體，公式之間不會有額外空行
self.add_result_label(self.output_frame_encode, formula_output, style='Red.TLabel', label_list=self.results_labels)
# 原有的 Step 3 結果輸出
hamming_code = ""
for i in range(k):
p_pos = 2**i
hamming_code += encoded_final[p_pos - 1]
self.add_result_label(self.output_frame_encode, f" 計算結果: P 碼依序為 {hamming_code}", style='Red.TLabel', label_list=self.results_labels)
# --- Step 4: 最終輸出 ---
encoded_hex = hex(int(encoded_final, 2))[2:].upper()
step4_text = "Step 4. 將 Hamming code 填入表中"
self.add_result_label(self.output_frame_encode, step4_text, label_list=self.results_labels)
self.add_result_label(self.output_frame_encode, f" 編碼後二進制值: {encoded_final}", style='Red.TLabel', label_list=self.results_labels)
self.add_result_label(self.output_frame_encode, f" 最終編碼結果 (16進制): 0x{encoded_hex}", style='Red.TLabel', label_list=self.results_labels)
self.encoded_input.delete(0, tk.END)
self.encoded_input.insert(0, encoded_final)
def run_correction(self):
"""執行糾錯流程"""
self.clear_labels(self.output_frame_decode, self.correction_labels)
encoded_data = self.encoded_input.get().strip()
if not all(c in '01' for c in encoded_data) or len(encoded_data) < 4:
messagebox.showerror("輸入錯誤", "請輸入有效的二進制編碼值 (至少 4 位)。")
return
# --- 模擬 Step 1: 畫表格 - 確保對齊 ---
total_bits = len(encoded_data)
# 使用固定寬度 3 (<3) 確保對齊
pos_str = "".join([f"{i+1:<3}" for i in range(total_bits)])
data_str = "".join([f"{bit:<3}" for bit in list(encoded_data)])
self.add_result_label(self.output_frame_decode, "Step 1. (模擬) 畫表格並填入接收到的值", label_list=self.correction_labels)
self.add_result_label(self.output_frame_decode, f" 位置: {pos_str}", style='Red.TLabel', label_list=self.correction_labels)
self.add_result_label(self.output_frame_decode, f" 接收值: {data_str}", style='Red.TLabel', label_list=self.correction_labels)
# --- Step 2 & 3 (保持不變) ---
syndrome_pos, corrected_binary, syndrome_str = decode_and_correct(encoded_data)
self.add_result_label(self.output_frame_decode, "Step 2. 進行 XOR 運算求糾錯碼 (Syndrome)", label_list=self.correction_labels)
self.add_result_label(self.output_frame_decode, f" 糾錯碼 (Syndrome) 二進制值: {syndrome_str}", style='Red.TLabel', label_list=self.correction_labels)
if syndrome_pos == 0:
self.add_result_label(self.output_frame_decode, " Syndrome 值為 0，表示無錯誤。", style='Red.TLabel', label_list=self.correction_labels)
else:
self.add_result_label(self.output_frame_decode, f" Syndrome 十進制值為 {syndrome_pos}，表示第 {syndrome_pos} 個位元有錯誤！", style='Red.TLabel', label_list=self.correction_labels)
self.add_result_label(self.output_frame_decode, "Step 3. 更正錯誤", label_list=self.correction_labels)
if syndrome_pos != 0 and syndrome_pos <= total_bits:
original_bit = encoded_data[syndrome_pos - 1]
corrected_bit = corrected_binary[syndrome_pos - 1]
corrected_hex = hex(int(corrected_binary, 2))[2:].upper()
self.add_result_label(self.output_frame_decode, f" 原第 {syndrome_pos} 位: {original_bit} -> 更正後為: {corrected_bit}", style='Red.TLabel', label_list=self.correction_labels)
self.add_result_label(self.output_frame_decode, f" 更正後的二進制值: {corrected_binary}", style='Red.TLabel', label_list=self.correction_labels)
self.add_result_label(self.output_frame_decode, f" 最終更正結果 (16進制): 0x{corrected_hex}", style='Red.TLabel', label_list=self.correction_labels)
else:
corrected_hex = hex(int(encoded_data, 2))[2:].upper()
self.add_result_label(self.output_frame_decode, f" 無錯誤，最終結果 (16進制): 0x{corrected_hex}", style='Red.TLabel', label_list=self.correction_labels)
# --- 執行主程式 ---
root = tk.Tk()
app = HammingCodeApp(root)
root.mainloop()
沒有留言:
張貼留言