脑补汉明码

wx_8888

汉明码译码方法

汉明码，(Hamming Code)是由Richad Hamming1950年提出的，它属于线性分组编码方式。

设原代码的码长为k比特，附加纠错编码部分为r比特，当码字n=2r-1，r=n-k，r=1，2⋯时就称这种线性分组码为汉明码。其基本原理是，将信息码元与监督码元通过线性方程式联系起来，每一个监督位被编在传输码字的特定比特位置上。系统对于错误的数位无论是原有信息位中的，还是附加监督位中的都能把它分离出来。

　设数据位数为m，校验位数为k，则总编码位数为n，n＝m+k，有Hamming不等式：

　　对于这个不等式可以理解为：由于n位码长中有一位出错，可能产生n个不正确的代码（错误位也可能发生在校验位），所以加上k位校验后，就需要定位昭m+k（＝n）个状态。用2k个状态中的一个状态指出“有无错”，其余2k－1个状态便可用于错误的定位。要能充分地进行错误定位，则须满足式（10－1）的关系。由此不等式得到校验位数与可校验的最大信息位之间的关系见表。

　　表 Hamming校验位数与可校验的最大信息位数之间的关系

　　Hamming码无法实现2位或2位以上的纠错，Hamming码只能实现一位纠错。

下面介绍汉明码距与编码纠错能力的关系。

　　汉明码距指的是长度相同的两个符号序列（码字）a和b之间对应位置上不同码元的个数，用符号D（a，b）表示，如两个二元序列：

　　a=101111

　　b＝111100

　　则得D（a，b）＝3。

　　有了汉明码距的概念，我们就可以用汉明码距来描述码的纠错检测能力。如果一组编码的码长为n，将这些资源全部利用上，可以对2n个符号进行编码，但这样一来这个编码就没有任何抗干扰能力，因为合法码字之间的最小汉明码距为1，任何一个符号的编码的任意一位发生错误，就变成了另外一个符号的编码，它也是一个合法的码字。接收端不能判断是不是有错误发生。

　　我们可以在2n个可用的码字中间选择一些码字来对信源符号进行编码，把这些码字称为合法码字，而其他没有使用的码字称为非法码字。这样合法码字之间的汉明距离就会拉开，有些合法码字发生错误后有可能变成非法码字，接收端收到这些非法码字后就可以判断出传输过程中出现了错误。码字之间的最小汉明距离越大，编码的抗干扰能力就越强。如果编码的最小汉明距离为2，那么任何合法码字发生一位错误都会变成非法码字，但不能确定是由哪一个合法码字错误而来，因此这个编码可以发现一位错误；如果编码的最小汉明距离为3，那么任何合法码字发生一位错误都会变成非法码字，而且距离原来的码字距离为1，而距离其他任何合法码字的最小距离为2，因此可以确定这个非法码字是由哪一个合法码字发生错误而来，这个编码用作纠错编码可以发现一位错误并纠正一位错误。如果发生了两位错误，也可以发现，但是如果试图纠正这个错误就会产生新的错误；如果把这种编码只当作检错编码，则可以发现两个错误。筇此类推，可以总结出编码的最小汉明码距与编码纠错检错能力之间的关系：

　　①要发现（检测）e个随机错误，则要求码的最小距离dmin≥e＋1；

　　②要纠正e个随机错误，则要求码的最小距离dmin≥2e＋1；

　　③要纠正e个随机错误，同时检测f（≥c）个错误，则要求码的最小距离dmin≥e＋f＋1。

　　如果一个分组码的数据位长度为k，校验位长度为r，总的编码长度为n，n＝k+r，则总的可以编码的合法码字的个数为2k，总的码字个数为2n，可以看出，检验位的长度越长，合法码字所占的比例就越小，如果这些码字能够尽可能地在所有的码字中均匀分布的话，合法码字之间的最小汉明码距就越大，编码的抗干扰能力也就越强，因此设计编码方法的最重要的任务就是尽量使合法码字尽可能地均匀分布。