错误校正码

一个纠错码(ECC)是一种以二进制数传输消息的编码方案，这样即使某些位被错误地翻转，消息也可以恢复。它们几乎用于所有的消息传输情况，特别是在数据存储中，ecc防止数据损坏。

假设Alice试图通过嘈杂的电话向Bob发送一条消息，并希望确保Bob正确地接收到该消息。为了确保这一点，Alice有几个选项，最明显的是Bob重复消息以供Alice确认。不幸的是，这并不总是可行的(如在单向通信链接中)，或者如果Alice同时向几个人分发相同的消息，则代价可能很高。另一个可能的选择是Alice多次重复消息，但这是相当低效的。

或者，Alice可以选择使用不容易与他人混淆的单词，这样即使Bob稍微听错了一个单词，Bob也可以从上下文猜出意思。例如，这就是北约语音字母表背后的概念:字母表由“Alpha”、“Bravo”、“Charlie”等表示。这些单词是特意选择来区别于其他单词的，因此，例如，听到“vo”就足以猜出想要的字母是b。请注意，这几乎适用于下面的任何一对单词:几乎没有一对单词有相似的发音，所以单个音节往往足以猜出想要的字母。

纠错码的操作方式与Alice相同，但使用的是二进制数字而不是单词。每一个字母(或者更一般地说，一组可能的消息中的每一个)都被编码为二进制数，位是连续传输的。从这个意义上说，“有噪声的电话”就相当于有一个比特被错误传输的概率(例如，它被传输为1，而实际上是0，反之亦然)。ECC的目标是传输一个可以被准确解释的消息，即使有些比特被意外翻转。

ECC最简单的例子类似于Alice重复消息:当一个比特要被传输时，它被多次传输(通常是3次)，而传输次数更多的比特被解释为预期的消息。更具体地说:

例如，一条“10101”的消息可能被传输为111010111000110，其中加粗的位是意外翻转的。这将被正确地解释为

将被解释为“10101”，预期的消息。因此，尽管有两个比特被错误地翻转，但这种传输方法会产生正确的消息。更具体地说，如果翻转位的概率是 $p$，错误传输位的概率为 $p ^ 3 + 3 ^ 2 (1 - p)$的概率，明显小于 $p$这将导致像往常一样只传输一次比特(因为 $p$非常小)。

该代码称为(1)重复代码，即发送三个位，其中一个是所需的数据位。当传输的一个比特翻转时，它可以纠正消息一位错误-意思是纠正能力这段代码的1位。如果最多翻转了两个位，它还可以检测到发生的错误检测能力这段代码是2位。

然而，这种编码方案是相当低效的，因为它要求发送方传输三倍于消息长度的消息，以实现单位校正。更正式,编码速率这段代码的 $\压裂{1}{3}$—数据位数除以传输位数。

重复代码的一个更简单的例子是奇偶校验码，其中每个比特传输两次:

它可以检测，但不能纠正单位错误。这个代码的重要性在于a的概念校验位，这是一个加位，使每个编码中的1的数量是偶数。通过这样做，任何带有奇数个1的消息都可以立即被识别为错误的。更一般地说，可以添加奇偶校验位，使1的数量特定的职位偶数，也使任何在这些位置上有奇数个1的消息立即被识别为错误。

一种更有效的编码方案是汉明码，这类似于开头部分的语音字母。在汉明码中，每一个可能的消息字符串都被编码为一个特定的二进制数，其中特别选择的一组数字使它们在某种意义上都具有显著的差异;换句话说，每对编码的消息在某种程度上都有本质上的不同。

测量是汉明距离．两个数之间的汉明距离是它们不同的比特数。例如，1101010和1111000是相隔2的汉明距离:

1101010

1111000

这里的关键是，如果任何一对编码在汉明距离方面的距离足够远，则可以通过查看哪个码字最接近所传输的消息来检测和纠正错误。例如，考虑编码

在这种编码中，编码之间的最小汉明距离是2，这意味着单位错误可以是检测到——也就是说，如果在一个字母的传输过程中有一个位翻转，就可以确定出错了。然而，无法确定最初的信息是什么;例如，发送的“010”消息可能是由于发送“a”、“B”或“D”而导致的单位错误。

然而，在这种编码中:

编码之间的最小汉明距离为3，这意味着单位错误可以被纠正，双位错误可以被检测。这是上一节中的(3,1)代码。

一般来说，编码可以检测 $k$-比特错误，如果最小汉明距离是最小的 $k + 1$,正确的 $k$-比特错误，如果最小汉明距离是最小的 $2 k + 1$．

汉明码采用了这种思想，并结合奇偶校验位的思想，允许奇偶校验位重叠。更具体地说，它们遵循以下算法:

1. 当传输二进制数时，使用第1位、第2位、第4位、第8位等(2的所有幂)位作为奇偶校验位，所有其他位置作为数据位。
2. 的奇偶校验位 $2 ^ n$是否所有位的和(取模2)的位置有 $n$最低有效位设置为1。例如，第2位的奇偶校验位是位置上的位的和 $3=11_2, 6=110_2, 7=111_2, 10=1010_2, 11=1011_2， \ldots . \$因为这些位置的第2位都是1。
3. 发送整个消息。如果数据位发生错误，一些奇偶校验位将显示错误(因为在这些集合中有奇数个1)。它们的和就是错误的位置。如果只有一个奇偶校验位显示错误，该奇偶校验位实际上是错误的。

关键的一点是，每个位都编码在一组唯一的奇偶校验位中:具体地说，比特位置的二进制表示为1的那些位。例如，第14位包含在8、4和2的奇偶校验位中，因为 $14 = 1110 _2$．如果校验位8、4和2显示错误，则第14位出错。

一般来说,与 $n$奇偶校验位, $(2 ^ n - 1) - n = 2 ^ n-n-1$比特可用于数据，这意味着 $2 ^ {2 ^ n-n-1}$字母表的不同成员可以使用just进行编码 $n$奇偶校验位。这是对重复代码的巨大改进 $n > 2$；例如，一种编码，其中每个单词需要4位信息(因此最多可以编码16个码字)，可以用3个奇偶校验位传输，共7位，而不是 $4 \ cdot 3 = 12$从上一节的重复方案。因为它可以纠正单位错误和检测双位错误，这使得汉明码在达到相同目的的同时比重复码更有效。

汉明码可以手工构造，但用线性代数构造汉明码要容易得多。考虑一个矩阵 $米$它的列是奇偶校验位的所有可能的非零向量。例如，对于3个奇偶校验位，矩阵为

$M = \开始{pmatrix} 1 &1&0&1&1&0&0 \ \ 1 &0&1&1&0&1&0 \ \ 0 &1&1&1&0&0&1 \ {pmatrix}结束$

列的顺序无关紧要，但是写起来很方便 $米$在这种形式(最右边的3列是3-单位矩阵)中，真正的目标是找到生成矩阵 $G$,满足 $MG ^ T = 0$．这可以通过对左边的转置得到 $米$(与单位矩阵不同的部分)，并将适当的单位矩阵加到左：

$G = \ {pmatrix}开始1 &0&0&0&1&1&0 &1&0&0&1&0&1 \ \ \ \ 0 0 0 &0&0&1&1&1&1 &0&1&0&0&1&1 \ \ \ {pmatrix}结束$

可以很容易地检查这个算法的结果 $MG ^ T = 0$根据需要。一个汉明码需要一个位向量 $\ overrightarrow {x}$来 $G \ overrightarrow {x}$；如。

${pmatrix} 1 0 1 1 \ \开始结束{pmatrix} {pmatrix} 1 0 1 1 \ \ rightarrow \开始结束{pmatrix} \ {pmatrix} 1 &0&0&0&1&1&0 \ \ 0开始&1&0&0&1&0&1 \ \ 0 &0&1&0&0&1&1 \ \ 0 &0&0&1&1&1&1 \结束{pmatrix} = {pmatrix} 1 &0&1&1&0&1&0 \ \开始结束{pmatrix}$

所以“1011”被编码为“1011010”。

这导致了汉明(7 4)代码它是汉明密码的始祖，也是最著名的密码。

• 哈夫曼编码