汉明距离及其在纠错中的应用

FEC方案的种类很多，例如卷积码和Turbo码。汉明码（Hamming Code）是这些方案中的一种。虽然汉明码并没有非常普遍地实现，但是其他的纠错方案都是基于汉明码所提出的基本概念。因此，我们在这一节将介绍汉明码。

汉明码中的基本概念是将数据块彼此进行区分，这样在发生传输错误时，接收到的数据块仍然可以和原始数据关联起来。可以通过在数据块中加入被称为校验位的冗余比特来实现。某个数据块和其他数据块不同的最小比特数称为汉明距离（Hamming Distance）。汉明距离指出可以被修正的错误比特位数。举例来说，如果汉明距离为3，那么当有1bit数据在传输时发生变化时，接收到的数据块相比于其他可能的数据块更像原数据块，这是因为它和原数据块只有1bit不同，而与其他的数据块至少有2bit不同。因此，单一比特的错误可以被纠正过来。

假设将所有数据按照每2bit分成数据块。通过这2bit就会得到四种不同的组合。现在对每2bit数据块使用3bit的校验位来纠正传输错误。在这种情况下，可以为每2bit的数据建立一个代码（Codeword），这些代码彼此至少有3bit不同，如表4-3所示。当这5bit数据中的一位在任何符号上发生变化时，结果将会只是与源码存在1bit的区别，但与其他代码则至少有2bit的不同。举例来说，要传输00，5bit数据即00000将会被发送。如果这些比特中的一位在接收时出错，例如00010，接收到的代码将不是表4-3所示的有效数据和校验位组合中的一组。然而，它与00000的距离只有1，而它却与其他的有效代码间存在至少2bit的差异。因此，假设只存在1bit的错误，我们就能在移除接收数据块的冗余比特后推断出传输的数据块是00。当接收到的数据有不止1bit的错码时，我们就无法将其和任何有效的代码联系起来。例如，01001不是有效的代码，同时和00000及01111的汉明距离均为2，这可能出现在传输其中任一代码出现2bit错误的情况中。因此，我们能够检测到但无法修正这一错误。在出现更多位数的错码的情况下，这一方案就无法检测到错码，甚至会将接收到的数据与错误的代码进行关联。

表4-3 数据块和编码

汉明码是一种遵循这一基本概念的块编码系统。在拥有m位校验位时，最小汉明距离为3，同时2^m-1bit数据块中出现单一比特错码可以被纠正。校验码的插入位置相当于2的幂，从最低位开始。这确保了当它们在代码中的位置表示为二进制形式，只有处于检验位相对位置的比特为1，其余的为0。

例如，假设使用4个校验位。它们被插入在传输数据块中2⁰、2¹、2²和2³的位置。以二进制的形式它们分别表示为0001、0010、0100和1000。这些比特串被称为位置串，它们的长度等于校验位的数量。包括校验位在内的数据块中的最大比特数不能超过2^m-1，因为这是mbit所能表示出的最大可能值。

在汉明码生成过程中，数据比特首先被插入不是为校验位准备的位置。之后数据块中的所有“1”比特的位置串进行异或操作。结果中的每比特是相关校验位的值。举例来说，如果结果为1001，这表明最高和最低校验位是1，而其他的为0。在这之后，如果将所有“1”比特的位置串进行异或，包括校验位，除非出现传输错误，这一结果应该等于0。若有单一比特错误，这种操作的结果给出了传输中变化的比特的位置串。(www.xing528.com)

在例4-1中，位于位置5、9、11和15的比特位为1。如果将这些位置串的比特进行异或，得到的结果为8，这表明只有最高校验位为1，其他的校验位为0。基于此，例4-1中所示的数据块将会进行传输。假设在传输中第7位的比特出现变化。当对7的位置串比特应用异或操作时，结果显然等于7，这表明第七位的比特在传输中发生了改变。

例4-1

校验位数m：4

最大数据块长度：2⁴-1=15

数据块：10001010010