数据编码理论/汉明码

简介

信息从一个地方传输到另一个地方会面临许多困难。其中最主要的是噪声。例如假设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 的二进制表示。