資料編碼理論/漢明碼

簡介

資訊從一個地方傳輸到另一個地方會面臨許多困難。其中最主要的是噪聲。例如假設01010101從一端傳送。由於噪聲，它可能會被接收為11010101，第一個數字被噪聲改變了。顯然，如果傳送的不是接收的，那麼通訊就會有問題。為了解決這類問題，人們開發了糾錯碼。

在實際應用中，將訊息以塊形式傳送是有意義的，即一系列一個接一個的數字，例如11111100。眾所周知，電子資料是用0和1表示的。每個數字（0或1）稱為一個位元。一個位元組由8個位元組成。一個位元組允許我們用$2^{8}=256$個符號來表示。假設資料一次傳送一個位元組。如前所述，由於噪聲，傳送的可能不總是接收的。

計算機科學家提出了一種簡單的錯誤檢測方法，稱為奇偶校驗。透過這種方法，我們只用前7個位元來表示資料。最後一個位元總是被選擇，以便與其他七個位元一起，位元組中1的個數為偶數。當資料到達另一端時，接收方計算位元組中1的個數。如果是奇數，那麼位元組一定是受到噪聲汙染的，因此接收方可以要求重新傳輸。

這種方法只能檢測錯誤，但不能糾正它們，只能要求重新傳輸。如果重新傳輸很昂貴（例如衛星），奇偶校驗就不理想。而且它的錯誤檢測能力也很低。如果兩個位元被噪聲改變，那麼接收方會認為訊息是正確的。更復雜的糾錯碼解決了這些問題。

漢明碼

漢明碼是對奇偶校驗方法的改進。它可以糾正1個錯誤，但要付出代價。在奇偶校驗方案中，一個位元組中的前7個位元是實際資訊，所以$2^{7}=128$個不同的符號可以用一個位元組來表示。但對於漢明碼，每個資料塊包含7個位元（而不是8個），並且一個塊中只有4個位元用於表示資料，因此只有$2^{4}=16$個符號可以用一個塊來表示。因此，為了用漢明碼傳送相同數量的資訊，我們需要傳送更多位元。無論如何，讓我們看看漢明碼是如何工作的。

在本節中，我們將看到漢明碼具有某些驚人的特性，儘管我們現在還不會討論它為什麼有效。事實上，如果傳輸中只引入了一個錯誤，即只有一個位元被改變，那麼接收方採用的解碼方法一定會能夠糾正它。很容易理解，如果出現了2個或更多個錯誤，那麼糾正甚至檢測都可能是不可能的。

現在，我們將描述漢明碼的工作原理，但直到後面我們才會開發它背後的數學原理。因此，如果需要，可以跳過本節。

我們讓a、b、c和d分別取值為0或1，這些被稱為資訊位元。漢明碼是一個包含7個位元的塊，形式為

(a + b + d, a + c + d, a, b + c + d, b, c, d) (mod 2)

..給出矩陣表示可以看出，數字a、b、c和d分別出現在第3、5、6和7個分量中。所有其他分量都是a、b、c和d的組合。因此，我們將第3、5、6和7個分量稱為資訊分量，所有其他分量都是校驗分量，這些分量攜帶額外的資訊，使我們能夠檢測和糾正單個錯誤。我們將依次解釋上面的奇怪符號。 (mod 2) 符號表示我們取括號中用逗號分隔的每個值，並檢視其模2的值（稍後我們將看到一個例子）。

我們用向量形式表示了包含7個位元的塊，其中每個分量對應於一個位元。例如，令a = b= c = d = 1，那麼我們得到

(1 + 1 + 1, 1 + 1 + 1, 1 , 1 + 1 + 1, 1, 1, 1) (mod 2)

即

(1, 1, 1, 1, 1, 1, 1)

因此，1111111是我們傳送的位元塊。

為了檢測單個錯誤，也非常簡單。假設接收到的碼字為$a_{1}a_{2}...a_{7}$，我們計算3個值

$b_{0}=a_{1}+a_{3}+a_{5}+a_{7}{\pmod {2}}$

$b_{1}=a_{2}+a_{3}+a_{6}+a_{7}{\pmod {2}}$

$b_{2}=a_{4}+a_{5}+a_{6}+a_{7}{\pmod {2}}$

那麼我們宣佈錯誤發生在第 $2^{2}{b_{2}}+2{b_{1}}+b_{0}$ 位。

假設傳送 1111111，但接收 1111011。接收者計算

$b_{0}=1+1+0+1=1{\pmod {2}}$

$b_{1}=1+1+1+1=0{\pmod {2}}$

$b_{2}=1+0+1+1=1{\pmod {2}}$

所以錯誤發生在第 $2^{2}{b_{2}}+2{b_{1}}+b_{0}=4+1=5$ 位，正如預測的那樣！

如果傳輸過程中沒有錯誤，那麼 $2^{2}{b_{2}}+2{b_{1}}+b_{0}=0$。

總結
如果要傳送一個包含 4 個位元的資訊塊。假設這 4 個位元是 abcd。

• 傳送： abcd

• 我們計算併發送 (a + b + d, a + c + d, a, b + c + d, b, c, d) (mod 2)

• 解碼

$b_{0}=a_{1}+a_{3}+a_{5}+a_{7}{\pmod {2}}$

$b_{1}=a_{2}+a_{3}+a_{6}+a_{7}{\pmod {2}}$

$b_{2}=a_{4}+a_{5}+a_{6}+a_{7}{\pmod {2}}$

• $e=2^{2}{b_{2}}+2{b_{1}}+b_{0}$

如果 e = 0 則假設沒有錯誤，否則宣佈在第 e 位發生了單個錯誤。

練習

...計算一些碼字並解碼它們

基礎

糾錯碼的數學理論應用了有限域的概念，也稱為伽羅瓦域（以著名的法國數學家埃瓦里斯特·伽羅瓦（1811-1832）命名）。特別是，2 元集 {0,1} 支援大小為 2 的有限域的結構。一般來說，有限域可以有q 個元素，其中q 是一個素數冪（有限域中不可能有其他數量的元素；任何兩個具有相同數量元素的有限域在本質上是相同的，即同構）。例如，一個 7 元域可能包含元素 0,1,2,3,4,5,6，其算術運算 + - * 是模 7 進行的。

我們將大小為q 的有限域表示為 $\mathbb {F} _{q}$ 或 GF(q)。GF 代表伽羅瓦域。

一些定義

碼 & 碼字

令A 為一個有限集，稱為字母表；它應該至少包含兩個不同的元素。令n 為一個自然數。在字母表A 上長度為n 的碼是A 中元素的 n 長序列的任何集合C；C 中的序列稱為C 的碼字。

如果字母表A = {0,1} 那麼A 上的碼稱為二進位制碼。

例如，令C 為字母表A := GF(5) := {0,1,2,3,4} 上的碼。令C := {000,111,222,333,444}。它具有碼字 000, 111, 222, 333 和 444。

現在我們應該討論碼的一些性質。首先，我們可以有碼字之間的距離概念。

漢明距離

令C 為一個碼，並且x 和y（粗體表示每個碼字類似於向量）是C 的碼字。x 和y 的漢明距離表示為

d(x,y)

是x 和y 不同的位置數。

例如，d(000,111) = 3。

漢明距離享有以下三個基本度量性質

1. d(x,y) = 0 <==> 'x' = 'y'
2. d(x,y) = d(y,x)
3. d(x,y) ≤ d(x,z) + d(z,y); 三角不等式

最小距離

編碼C的最小距離，記作d(C)，是在C中兩個不同碼字之間可能的最小的距離

例如，設C = {000,111,110,001}，則d(C) = d(000,001) = 1，因為任何其他碼字之間的距離都大於或等於1。

最小距離的意義

編碼C的最小距離與其糾錯能力密切相關。讓我們用一個假設的編碼C來說明原因。假設該編碼的最小距離為5，即d(C) = 5。如果傳送了碼字x，並且傳輸過程中只引入了最多2個錯誤，則可以糾正這些錯誤。

假設傳送了x，但接收到了x + e，其中e對應於具有最多2個非零分量的向量。我們看到x + e 比任何其他碼字更接近x！這是因為d(C) = 5。

例如，設C = {00000,11111,22222}，傳送00000，但接收到00012。很容易看出00000是離00012最近的碼字。因此我們把00012解碼為00000，實際上糾正了2個錯誤。但是，如果產生了3個或更多個錯誤，並且我們使用最近的碼字進行解碼，那麼我們可能會遇到麻煩。例如，如果傳送11111，但接收到11222。我們把11222解碼為22222，但這是錯誤的！

沒有完美的糾錯編碼（儘管我們稱一些為完美編碼）。沒有編碼能夠糾正所有可能的錯誤向量。但也可以合理地假設每次傳輸只產生少量錯誤，因此我們只需要能夠糾正少量錯誤的編碼。

最近鄰解碼

如果m > n，那麼可以合理地假設發生n個錯誤的可能性比發生m個錯誤的可能性更大。在任何通訊通道中，可以合理地假設錯誤越多，可能性越小。因此，使用最近鄰解碼來解碼接收到的塊非常合理，即如果接收到了y，我們會尋找一個碼字x（屬於C），使得d(x,y) 最小。

使用上述方案，很容易看出，如果編碼C的最小距離d(C) = 2t + 1，則最多可以糾正t個錯誤。

練習

如果編碼C的最小距離d(C) = 2t + 2。使用最近鄰解碼，它能糾正多少個錯誤？

線性編碼

從這裡開始，假設基本的線性代數知識。
符號

設$\mathbb {F} _{q}^{n}$ 和 ${\mbox{GF}}(q)^{n}$ 都表示n維向量空間，其分量來自 {0,1,2,..,q - 1}，算術運算在模q下進行

如果線性編碼C是q元 [n,k,d] 編碼，則

1. C是一組長度為n的向量，
2. 每個分量（碼字中的）都取自 GF(q)，
3. C 中的所有碼字都由k個線性無關向量跨越，並且
4. d(C) = d

注意，如果x 和y 是碼字，那麼x + y 也是碼字。換句話說，我們可以將C 視為 $\mathbb {F} _{q}^{n}=GF(q)^{n}$ 的一個向量子空間，維度為k。因此，可以透過提供一個跨越碼字的k個向量的基來完全確定C。設 {$v_{i}$ | i = 1, 2, ..., k} 是C的基，我們稱矩陣

$G={\begin{pmatrix}v_{1}\\v_{2}\\...\\v_{k}\end{pmatrix}}$

為C的生成矩陣。

例如，設C是一個由 {10034,01013,00111} 跨越的5元 [5,3,3] 編碼，那麼生成矩陣為

$G={\begin{pmatrix}1&0&0&3&4\\0&1&0&1&3\\0&0&1&1&1\end{pmatrix}}$

資訊率
一個q元 [n,k,d] 編碼可以有 $q^{k}$ 個不同的碼字，因為每個碼字c 都是以下形式

$c=a_{1}v_{1}+a_{2}v_{2}+..+a_{k}v_{k}$

其中 $a_{i}$ 可以取值 0, 1, .., q - 1（因為算術運算在模 q 下進行）。因此，此程式碼可以表示 $q^{k}$ 個符號。

我們可以看到，G 的行空間包含所有碼字，因此，假設要傳送 $c_{1}c_{2}..c_{k}$，我們可以透過以下方式計算相應的碼字 c：

$c={\begin{pmatrix}c_{1}&c_{2}&..&c_{k}\end{pmatrix}}G$

例如，假設 C 和 G 如上所示，我們希望傳送 012 給接收者，我們計算碼字：

${\begin{pmatrix}0&1&2\end{pmatrix}}{\begin{pmatrix}1&0&0&3&4\\0&1&0&1&3\\0&0&1&1&1\end{pmatrix}}={\begin{pmatrix}0&1&2&3&0\end{pmatrix}}$

注意，碼字的前 3 位實際上是我們想要傳送的訊息，所以如果我們不需要任何糾錯能力，則不需要後 2 位。

如果生成矩陣的形式為 (I|N)（在生成矩陣的左側有一個單位矩陣），則線性程式碼處於標準形式。上面的矩陣 G 處於標準形式。事實證明，如果 G 處於標準形式，則接收者可以輕鬆地讀取預期訊息。它還有另一個將在下一節討論的優勢。

解碼

使用線性程式碼的一個優點是檢測錯誤很容易。實際上，我們可以找到一個矩陣 H 使得 $H{\underline {x}}^{T}={\underline {0}}$ 當且僅當 x 是一個碼字。因此，如果接收到 y 且 $H{\underline {y}}^{T}\neq {\underline {0}}$，那麼我們可以自信地說 y 已經被噪聲汙染。

為了找到這樣的 H，假設 C 是一個 q 元 [n,k,d] 程式碼，且 C 由 $v_{i}$ i = 1, 2, .., k 跨越。

定義 - 內積 & 正交性
將任何兩個向量的內積定義為：

$<(x_{1},x_{2},..,x_{n}),(w_{1},w_{2},..,w_{n})>=x_{1}w_{1}+x_{2}w_{2}+..+x_{k}w_{k}\ {\pmod {q}}$

如果 <v,w> = 0，則稱兩個向量 v 和 w 是正交的。

例如，假設 C 是一個 7 元 [7,4,3] 程式碼，那麼：

<(0,1,2,4,5,6,3), (1,4,5,0,3,2,0)> = 4 + 10 + 15 + 12 = 41 ≡ 6 (mod 7)

首先要注意的是，H 必須是一個 n 行 j 列的矩陣，其中 j 為任意整數。可以將 H 看作是 $GF(q)^{n}$ 中的線性變換。根據定義，kerH = C，根據秩零度定理

$n=dim(imH)+k$

所以 H 的秩為 n - k。實際上，H 的行空間是由 n - k 個線性無關的向量組成的，$w_{i}$，其中 i = 1,2,..,n - k，$w_{i}$ 與 C 中的每個碼字正交。

注意，C = imH 和 kerH 是向量子空間（練習）。實際上，我們記

$kerH=C^{\bot }$

其中 $C^{\bot }$ 表示任何向量都與 C 中每個向量正交的向量子空間。

因此，我們需要找到 $C^{\bot }$ 的基，並將 H 設為以這些基向量為行的矩陣！如果 C 的生成矩陣 G 處於標準形式，那麼 H 就很容易計算。實際上，如果

$G=(I_{k}|N)\!$

那麼

$H=(-N^{T}|I_{n-k})\!$

例如，令 G 如上所示，即

$G={\begin{pmatrix}1&0&0&3&4\\0&1&0&1&3\\0&0&1&1&1\end{pmatrix}}$

那麼我們可以得出結論

$H={\begin{pmatrix}-3&-1&-1&1&0\\-4&-3&-1&0&1\end{pmatrix}}$

考慮模 5 的值（回想一下 G 生成一個 5 元碼），我們得到

$H={\begin{pmatrix}2&4&4&1&0\\1&2&4&0&1\end{pmatrix}}$

我們稱 H 為奇偶校驗矩陣，因為 H 可以告訴我們一個碼字是否被汙染了。

為了驗證每個碼字 $Hx^{T}=0$，我們只需要將 H 乘以 G 的每一行（轉置），因為 G 的行張成 C（練習）。

練習

1. 令 H 為碼 C 的奇偶校驗矩陣，即對於 C 的所有碼字 x，Hx^T = 0。將 H 看作線性變換。證明 C = imH 和 kerH 是向量子空間。

2. 如果 G（生成矩陣）處於標準形式，證明如上構造的 H 張成與 G 的行空間正交的所有向量。

漢明碼為什麼有效

二進位制漢明碼是一個 [7,4,3] 碼。由於最小距離為 3，因此它可以糾正 1 個錯誤。漢明碼的特殊之處在於它告訴接收方錯誤的位置。為了構造漢明碼，先構造奇偶校驗矩陣更容易

$H={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}$

我們不會討論如何找到 G，留作練習。注意 H 的 列 只是數字 1,2,.., 和 7 的二進位制表示，按遞增順序排列。這就是漢明碼如何告訴我們錯誤在哪裡。

設 x 是漢明碼的碼字，假設接收到了 x + e_j，其中 e_j 是僅在第 j 位為 1 的向量。換句話說，在第 j 位發生了錯誤。

現在注意到

$H({\underline {x}}+{\underline {e}}_{j})^{T}=H{\underline {x}}^{T}+H{\underline {e}}_{j}^{T}={\underline {0}}+H{\underline {e}}_{j}^{T}=H{\underline {e}}_{j}^{T}$

但是 $H{\underline {e}}_{j}^{T}$ 只是 H 的第 j 列，它就是 j 的二進位制表示。