纠正代码纠错

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

假设Alice试图通过嘈杂的电话传输消息到Bob，并希望确保Bob正确接收消息。为了确保这一点，Alice有几个选择，最明显的是鲍勃重复艾丽斯的消息确认。遗憾的是，这并不总是可以（如在单向通信链路中），或者如果例如，Alice同时向几个人分发相同的消息，则可能是昂贵的。另一种可能的选项是为了Alice多次重复消息，但这相当效率。

或者，Alice可以选择使用不容易与他人混淆的单词，因此即使鲍勃略微训练一个单词，鲍勃可以弄清楚来自上下文的意图。这是北部的概念，例如北约语音字母表：字母表由“alpha”，“bravo”，“查理”表示，“charlie”等。这些词被专门选择与另一个不同，因此，例如，听到“vo”足以猜测预期的字母是b。注意，实际上是如下任何一对单词：几乎没有配对类似声音，所以单个音节通常足以弄清楚预期的字母。

错误校正码的操作方式与Alice相同，但使用的是二进制数字而不是单词。每一个字母(或者更普遍地说，一组可能的信息中的每一个)被编码为一个二进制数，位被连续传输。从这个意义上说，“嘈杂电话”就相当于有一个比特被错误传输的概率(即它被传输为1，尽管实际上是0，或者相反)。ECC的目标是传输即使某些位被意外翻转也能被准确解释的消息。

ECC的最简单示例类似于Alice重复消息：当要发送比特时，它是多次发送的（通常为3），该比特将被解释为预期消息的比特更长。进一步来说：

例如，“10101”的消息可以作为1110发送1011100011.0.，其中粗体部分被意外翻转。这将被正确解释为

将被解释为“10101”，是预期的消息。因此，尽管两位被错误地翻转，但这种传输方法导致正确的消息。更具体地，如果翻转位的概率是 $P.$，则错误传输位的概率为 $p ^ 3 + 3p ^ 2（1-p）$，这明显小于 $P.$这将是因为常用的曾经发送一次（自从 $P.$它非常小）。

此代码称为（3,1）重复码，表示发送三个位，其中一个是所需的数据位。当其中一个传输位翻转时，它可以更正消息-a单比特错误- 意思是纠正能力这个代码是1位。它还可以检测到最多两位是否翻转时发生错误，这意味着探测能力这个代码是2位。

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

一个更简单的重复代码示例是奇偶校验码，其中每个位被传输两次：

它可以检测但不能纠正单位错误。本规范的重要性在于奇偶校验位，这是一个位的位，以使每个编码中的1s的数量均匀。通过这样做，可以立即将具有奇数1S的任何消息被识别为错误。更一般地，可以添加奇偶校验位以使1S的数量为1具体职位偶数，也使得任何在这些位置上有奇数个一的信息立即被认为是错误的。

一种更有效的编码方案是汉明码，这类似于从开口部分的拼音字母表。在汉明代码中，每个可能的消息字符串都被编码为一定的二进制数，其中包含一组数字，以便在某种意义上显着不同;换句话说，每对编码的消息通过一些测量基本上不同。

测量是汉明距离. 两个数字之间的汉明距离是它们不同的位数。例如，1101010和1111000是相隔2的汉明距离：

11.0.10.10.

11.110.0.0.

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

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

然而，在这种编码中：

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

一般来说，编码可以发现 $K.$-bit误差如果最小汉明距离至少是 $k+1$，及正确的 $K.$-bit误差如果最小汉明距离至少是 $2k+1$。

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

1. 传输二进制数时，使用第1、第2、第4、第8等位（两个的所有幂）作为奇偶校验位，所有其他位置作为数据位。
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. 传输整个消息。如果发生数据位中的错误，则一些奇偶校验位将显示错误（因为这些集合中的一些奇数为1S）。他们的总和是错误的位置。要是一奇偶校验位显示错误，该奇偶校验位实际上是错误的。

关键的一点是，每一位都被编码在一组唯一的奇偶校验位中：具体地说，对于这些奇偶校验位，位位置的二进制表示为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}$一个字母表的不同成员只需使用 $N$奇偶校验位。这是对重复代码的一个巨大改进 $n> 二,$;例如，可以用3个奇偶校验位发送每个单词需要4位信息（因此可以编码16个码字）的编码，总共7位，而不是 $4\cdot 3=12$从上一节中的重复方案中的比特。由于它可以纠正单位错误并检测双位错误，这使得汉明代码比重复代码更有效，同时实现相同的目的。

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

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

列的顺序无关紧要，但它便于编写 $m$在此表单（具有最右边的3列3-Identity Matrix）作为真实目标是找到发电机矩阵 $G$，这使 $MG^T=0$。这可以通过沿左手侧转换来形成 $m$（与身份矩阵不同的零件），并将相应的标识矩阵添加到剩下：

$G = \开始{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}$

可以很容易地检查此算法是否会导致 $MG^T=0$如预期的。然后汉明的代码采取一点向量 $\过右箭头{x}$到 $\超级arraw {x} g$; 例如

$\开始{pmatrix} 1 0 1 1 \端{pmatrix} \ RIGHTARROW \开始{pmatrix} 1 0 1 1 \端{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＆0＆0 \ END {PMATRIX}$

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

这导致了汉明[7,4]码，原来和最着名的汉明代码。

• 哈夫曼编码