汉明码(Hamming)的编码和译码算法本文所讨论的汉明码是一种性能良好的码，它是在纠错编码的实践中较早发现的一类具有纠单个错误能力的纠错码，在通信和计算机工程中都有应用。例如：在“计算机组成原理”课程中，我们知道当计算机存储或移动数据时，可能会产生数据位错误，这时可以利用汉明码来检测并纠错。简单的说，汉明码是一个错误校验码码集，由Bell实验室的R.W.Hamming发明，因此定名为汉明码。如果对汉明码作进一步推广，就得出了能纠正多个错误的纠错码，其中最典型的是BCH码，而且汉明码是只纠1bit错误的BCH码，可将它们都归纳到循环码中。各种码之间的大致关系显示如下。汉明码的编码算法输入：信源消息u（消息分组u）输出：码字v处理：信源输出为一系列二进制数字0和1。在分组码中，这些二进制信息序列分成固定长度的消息分组（messageblocks）。每个消息分组记为u，由k个信息位组成。因此共有2k种不同的消息。编码器按照一定的规则将输入的消息u转换为二进制n维向量v，这里n>k。此n维向量v就叫做消息u的码字（codeword）或码向量（codevector）。因此，对应于2k种不同的消息，也有2k种码字。这2k个码字的集合就叫一个分组码（blockcode）。若一个分组码可用，2k个码字必须各不相同。因此，消息u和码字v存在一一对应关系。由于n符号输出码字只取决于对应的k比特输入消息，即每个消息是独立编码的，从而编码器是无记忆的，且可用组合逻辑电路来实现。定义：一个长度为n，有2k个码字的分组码，当且仅当其2k个码字构成域GF(2)上所有n维向量组成的向量空间的一个K维子空间时被称为线性（linear）(n,k)码。汉明码（n，k，d）就是线性分组(n,k)码的一种。其编码算法即为使用生成矩阵G：v=u·G。例1-1：针对汉明码Hamming(7,4,3)而言，u=(u0,u1,u2,u3)，v=(v0,v1,v2,v3,v4,v5,v6)，则我们有(v0,v1,v2,v3,v4,v5,v6)=(u0,u1,u2,u3)·G。Hamming(7,4,3)的生成矩阵G为：G=，(v0,v1,v2,v3,v4,v5,v6)=(u0,u1,u2,u3)·，所以我们有：v0=u0,v1=u1,v2=u2,v3=u3,v4=u0+u1+u2,v5=u1+u2+u3,v6=u0+u1+u3,例如u=1101，对应→v=1101001。处理完毕。■其他汉明码照此处理，甚至其他线性分组(n,k)码都照此办理即可。线性分组(n,k)码的校正子（伴随式）有2n-k个，设该码的纠错能力为t，那么重量小于或者等于t的所有错误模式（图样）都要有唯一的校正子（伴随式）与之对应，因而，对于二进制(n,k)码，有汉明限：2n-k≥，当2n-k=时，(n,k)码称为完备码（PerfectCode）。完备码的伴随式得到了充分的利用，不存在解码不唯一的问题，然而完备码不一定是纠错能力强的码，因为它的最小距离dmin未必最大。完备码也是稀少的，已知的二进制完备码有t=1的汉明码（HammingCode）和t=3的格雷码（GolayCode），以及n为奇数的简单重复(n,1)码。三进制完备码有t=2的（11,6,5）格雷码。纠错能力t=1的完备码统称为汉明码。由定义可知，(n,k)汉明码应当满足下列条件：2n-k=1+n，令校验位长m=n-k，那么容易知道：n=2m-1,k=2m-1-m,dmin=3。汉明码的校验矩阵H具有特殊的性质：它的m维列向量正好是除零向量以外的所有可能的向量组合，共有2m-1个，恰好构成了H矩阵的列数n。格雷码通常是指线性分组（23,12）码，最小距离dmin=7，纠错能力t=3。由于223-12=2048=1+，所以格雷码是完备码，其码重（码的重量）分布见下面表0-1。表0-1格雷码的码重分布码重0781112151623码个数1253506128812885062531备注：1、汉明码的生成矩阵：Hamming(7,4,3)的生成矩阵GHamming(17,12,3)的生成矩阵GHamming(13,9,3)的生成矩阵GHamming(15,11,3)的生成矩阵GHamming(16,11,4)的生成矩阵G2、除了分组码之外，还有卷积码。卷积码编码器同样接受k比特分组的信息序列u，并产生n符号组的编码序列（码序列）v（卷积码编码中，符号u和v用来表示分组的序列而非单个分组）。但是，每一个编码分组不仅取决于当前单位时间对应的k比特消息组，而且与前m个消息组有关。此时，编码器的存储级数(memoryorder)为