数据编码理论
简介[编辑 | 编辑源代码]
信息从一个地方传输到另一个地方会面临许多困难。其中最主要的是噪声。例如假设01010101从一端发送。由于噪声，它可能会被接收为11010101，第一个数字被噪声改变了。显然，如果发送的不是接收的，那么通信就会有问题。为了解决这类问题，人们开发了纠错码。
在实际应用中，将消息以块形式发送是有意义的，即一系列一个接一个的数字，例如11111100。众所周知，电子数据是用0和1表示的。每个数字（0或1）称为一个比特。一个字节由8个比特组成。一个字节允许我们用 2 8 = 256 {\displaystyle 2^{8}=256} 个符号来表示。假设数据一次发送一个字节。如前所述，由于噪声，发送的可能不总是接收的。
计算机科学家提出了一种简单的错误检测方法，称为奇偶校验。通过这种方法，我们只用前7个比特来表示数据。最后一个比特总是被选择，以便与其他七个比特一起，字节中1的个数为偶数。当数据到达另一端时，接收方计算字节中1的个数。如果是奇数，那么字节一定是受到噪声污染的，因此接收方可以要求重新传输。
这种方法只能检测错误，但不能纠正它们，只能要求重新传输。如果重新传输很昂贵（例如卫星），奇偶校验就不理想。而且它的错误检测能力也很低。如果两个比特被噪声改变，那么接收方会认为消息是正确的。更复杂的纠错码解决了这些问题。
汉明码[编辑 | 编辑源代码]
汉明码是对奇偶校验方法的改进。它可以纠正1个错误，但要付出代价。在奇偶校验方案中，一个字节中的前7个比特是实际信息，所以 2 7 = 128 {\displaystyle 2^{7}=128} 个不同的符号可以用一个字节来表示。但对于汉明码，每个数据块包含7个比特（而不是8个），并且一个块中只有4个比特用于表示数据，因此只有 2 4 = 16 {\displaystyle 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 {\displaystyle a_{1}a_{2}...a_{7}} ，我们计算3个值
b 0 = a 1 + a 3 + a 5 + a 7 ( mod 2 ) {\displaystyle b_{0}=a_{1}+a_{3}+a_{5}+a_{7}{\pmod {2}}}
b 1 = a 2 + a 3 + a 6 + a 7 ( mod 2 ) {\displaystyle b_{1}=a_{2}+a_{3}+a_{6}+a_{7}{\pmod {2}}}
b 2 = a 4 + a 5 + a 6 + a 7 ( mod 2 ) {\displaystyle b_{2}=a_{4}+a_{5}+a_{6}+a_{7}{\pmod {2}}}
那么我们宣布错误发生在第 2 2 b 2 + 2 b 1 + b 0 {\displaystyle 2^{2}{b_{2}}+2{b_{1}}+b_{0}} 位。
假设发送 1111111，但接收 1111011。接收者计算
b 0 = 1 + 1 + 0 + 1 = 1 ( mod 2 ) {\displaystyle b_{0}=1+1+0+1=1{\pmod {2}}}
b 1 = 1 + 1 + 1 + 1 = 0 ( mod 2 ) {\displaystyle b_{1}=1+1+1+1=0{\pmod {2}}}
b 2 = 1 + 0 + 1 + 1 = 1 ( mod 2 ) {\displaystyle b_{2}=1+0+1+1=1{\pmod {2}}}
所以错误发生在第 2 2 b 2 + 2 b 1 + b 0 = 4 + 1 = 5 {\displaystyle 2^{2}{b_{2}}+2{b_{1}}+b_{0}=4+1=5} 位，正如预测的那样！
如果传输过程中没有错误，那么 2 2 b 2 + 2 b 1 + b 0 = 0 {\displaystyle 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 ( mod 2 ) {\displaystyle b_{0}=a_{1}+a_{3}+a_{5}+a_{7}{\pmod {2}}}
b 1 = a 2 + a 3 + a 6 + a 7 ( mod 2 ) {\displaystyle b_{1}=a_{2}+a_{3}+a_{6}+a_{7}{\pmod {2}}}
b 2 = a 4 + a 5 + a 6 + a 7 ( mod 2 ) {\displaystyle b_{2}=a_{4}+a_{5}+a_{6}+a_{7}{\pmod {2}}}
e = 2 2 b 2 + 2 b 1 + b 0 {\displaystyle e=2^{2}{b_{2}}+2{b_{1}}+b_{0}}
如果 e = 0 则假设没有错误，否则宣布在第 e 位发生了单个错误。
练习[edit | edit source]
...计算一些码字并解码它们
基础[edit | edit source]
纠错码的数学理论应用了有限域的概念，也称为伽罗瓦域（以著名的法国数学家埃瓦里斯特·伽罗瓦（1811-1832）命名）。特别是，2 元集 {0,1} 支持大小为 2 的有限域的结构。一般来说，有限域可以有q 个元素，其中q 是一个素数幂（有限域中不可能有其他数量的元素；任何两个具有相同数量元素的有限域在本质上是相同的，即同构）。例如，一个 7 元域可能包含元素 0,1,2,3,4,5,6，其算术运算 + - * 是模 7 进行的。
我们将大小为q 的有限域表示为 F q {\displaystyle \mathbb {F} _{q}} 或 GF(q)。GF 代表伽罗瓦域。
一些定义[edit | edit source]
码 & 码字
令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。
汉明距离享有以下三个基本度量性质
d(x,y) = 0 <==> 'x' = 'y'
d(x,y) = d(y,x)
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。使用最近邻解码，它能纠正多少个错误？
线性编码[编辑 | 编辑源代码]
从这里开始，假设基本的线性代数知识。
符号
设 F q n {\displaystyle \mathbb {F} _{q}^{n}} 和 GF ( q ) n {\displaystyle {\mbox{GF}}(q)^{n}} 都表示n维向量空间，其分量来自 {0,1,2,..,q - 1}，算术运算在模q下进行
如果线性编码C是q元 [n,k,d] 编码，则
C是一组长度为n的向量，
每个分量（码字中的）都取自 GF(q)，
C 中的所有码字都由k个线性无关向量跨越，并且
d(C) = d
注意，如果x 和y 是码字，那么x + y 也是码字。换句话说，我们可以将C 视为 F q n = G F ( q ) n {\displaystyle \mathbb {F} _{q}^{n}=GF(q)^{n}} 的一个向量子空间，维度为k。因此，可以通过提供一个跨越码字的k个向量的基来完全确定C。设 { v i {\displaystyle v_{i}} | i = 1, 2, ..., k} 是C的基，我们称矩阵
G = ( v 1 v 2 . . . v k ) {\displaystyle G={\begin{pmatrix}v_{1}\\v_{2}\\...\\v_{k}\end{pmatrix}}}
为C的生成矩阵。
例如，设C是一个由 {10034,01013,00111} 跨越的5元 [5,3,3] 编码，那么生成矩阵为
G = ( 1 0 0 3 4 0 1 0 1 3 0 0 1 1 1 ) {\displaystyle 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 {\displaystyle q^{k}} 个不同的码字，因为每个码字c 都是以下形式
c = a 1 v 1 + a 2 v 2 + . . + a k v k {\displaystyle c=a_{1}v_{1}+a_{2}v_{2}+..+a_{k}v_{k}}
其中 a i {\displaystyle a_{i}} 可以取值 0, 1, .., q - 1（因为算术运算在模 q 下进行）。因此，此代码可以表示 q k {\displaystyle q^{k}} 个符号。
我们可以看到，G 的行空间包含所有码字，因此，假设要发送 c 1 c 2 . . c k {\displaystyle c_{1}c_{2}..c_{k}} ，我们可以通过以下方式计算相应的码字 c：
c = ( c 1 c 2 . . c k ) G {\displaystyle c={\begin{pmatrix}c_{1}&c_{2}&..&c_{k}\end{pmatrix}}G}
例如，假设 C 和 G 如上所示，我们希望发送 012 给接收者，我们计算码字：
( 0 1 2 ) ( 1 0 0 3 4 0 1 0 1 3 0 0 1 1 1 ) = ( 0 1 2 3 0 ) {\displaystyle {\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 x _ T = 0 _ {\displaystyle H{\underline {x}}^{T}={\underline {0}}} 当且仅当 x 是一个码字。因此，如果接收到 y 且 H y _ T ≠ 0 _ {\displaystyle H{\underline {y}}^{T}\neq {\underline {0}}} ，那么我们可以自信地说 y 已经被噪声污染。
为了找到这样的 H，假设 C 是一个 q 元 [n,k,d] 代码，且 C 由 v i {\displaystyle 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 ( mod q ) {\displaystyle <(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}}}
如果
例如，假设 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 看作是 G F ( q ) n {\displaystyle GF(q)^{n}} 中的线性变换。根据定义，kerH = C，根据秩零度定理
n = d i m ( i m H ) + k {\displaystyle n=dim(imH)+k}
所以 H 的秩为 n - k。实际上，H 的行空间是由 n - k 个线性无关的向量组成的， w i {\displaystyle w_{i}} ，其中 i = 1,2,..,n - k， w i {\displaystyle w_{i}} 与 C 中的每个码字正交。
注意，C = imH 和 kerH 是向量子空间（练习）。实际上，我们记
k e r H = C ⊥ {\displaystyle kerH=C^{\bot }}
其中 C ⊥ {\displaystyle C^{\bot }} 表示任何向量都与 C 中每个向量正交的向量子空间。
因此，我们需要找到 C ⊥ {\displaystyle C^{\bot }} 的基，并将 H 设为以这些基向量为行的矩阵！如果 C 的生成矩阵 G 处于标准形式，那么 H 就很容易计算。实际上，如果
G = ( I k | N ) {\displaystyle G=(I_{k}|N)\!}
那么
H = ( − N T | I n − k ) {\displaystyle H=(-N^{T}|I_{n-k})\!}
例如，令 G 如上所示，即
G = ( 1 0 0 3 4 0 1 0 1 3 0 0 1 1 1 ) {\displaystyle G={\begin{pmatrix}1&0&0&3&4\\0&1&0&1&3\\0&0&1&1&1\end{pmatrix}}}
那么我们可以得出结论
H = ( − 3 − 1 − 1 1 0 − 4 − 3 − 1 0 1 ) {\displaystyle H={\begin{pmatrix}-3&-1&-1&1&0\\-4&-3&-1&0&1\end{pmatrix}}}
考虑模 5 的值（回想一下 G 生成一个 5 元码），我们得到
H = ( 2 4 4 1 0 1 2 4 0 1 ) {\displaystyle H={\begin{pmatrix}2&4&4&1&0\\1&2&4&0&1\end{pmatrix}}}
我们称 H 为奇偶校验矩阵，因为 H 可以告诉我们一个码字是否被污染了。
为了验证每个码字 H x T = 0 {\displaystyle Hx^{T}=0} ，我们只需要将 H 乘以 G 的每一行（转置），因为 G 的行张成 C（练习）。
练习[edit | edit source]
1. 令 H 为码 C 的奇偶校验矩阵，即对于 C 的所有码字 x，HxT = 0。将 H 看作线性变换。证明 C = imH 和 kerH 是向量子空间。
2. 如果 G（生成矩阵）处于标准形式，证明如上构造的 H 张成与 G 的行空间正交的所有向量。
汉明码为什么有效[edit | edit source]
二进制汉明码是一个 [7,4,3] 码。由于最小距离为 3，因此它可以纠正 1 个错误。汉明码的特殊之处在于它告诉接收方错误的位置。为了构造汉明码，先构造奇偶校验矩阵更容易
H = ( 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 ) {\displaystyle 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 + ej，其中 ej 是仅在第 j 位为 1 的向量。换句话说，在第 j 位发生了错误。
现在注意到
H ( x _ + e _ j ) T = H x _ T + H e _ j T = 0 _ + H e _ j T = H e _ j T {\displaystyle 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 e _ j T {\displaystyle H{\underline {e}}_{j}^{T}} 只是 H 的第 j 列，它就是 j 的二进制表示。