
代號:
頁次:
-
五、錯誤更正碼(Error Correction Codes, ECC)是用來解決在資料傳輸的過程
中,因資料損毀、雜訊等原因造成資料錯誤的問題。Single-ErrorCorrecting
(SEC)Codes 是一常用的錯誤更正碼,顧名思義,這種 SEC 編碼方式只
能更正一個位元的錯誤。以下是一種 SEC 錯誤更正碼的例子。
如圖所示,A, B 以及 C為三個彼此之間互有交集的集合,為了區別,我
們在三個集合的不同交集區域標上 1~7 個編號,分別代表 1 2 7
, , ,x x x…,每
一個區域的值可為0或是1。此SEC碼的編碼規則如下:如果 1 2 7
( , , , )x x x…
是一組碼字(Codeword),則 A, B, C 三個集合中的“1”的個數必須為偶
數。此種檢查 A, B, C 集合中的“1”的個數必須為偶數的機制也稱 Even-
parity Check。
請驗證(1,1,0,1,0,1,0)為一碼字。(4分)
為了方便說明,我們以c
記為碼字,而以e
記為錯誤向量。對於所給定
的碼字 (1,1,0,1,0,1,0)c
,在其上隨意加入一個位元的錯誤,例如
(0,0,0,0,0,1,0)e
(註:因為有 7個位置,因此共有 7種可能),那麼
r c e
則為所接收的訊息,也就是
(1,1,0,1,0,0,0)=(1,1,0,1,0,1,0)+(0,0,0,0,0,1,0)r c e
請證明針對一組碼字 (1,1,0,1,0,1,0)c
,任何一個位元的錯誤都能被偵
測且更正回來。(8分)
若我們將 3個Even-parity Check 方程式以矩陣的形式表示如下:
那麼,如果r
是一個碼字,則 0
T
Hr
。此即為一種(7, 4)線性區塊
碼。請證明此(7, 4)線性區塊碼的最小漢明距離(Minimum Hamming
Distance)最少為 3。(8分)