汉明码的改进及在存储器中的实现

蒋 婷，徐 睿，周昕杰

（中国电子科技集团公司第58研究所，江苏 无锡 214000）

汉明码的改进及在存储器中的实现

蒋 婷，徐 睿，周昕杰

（中国电子科技集团公司第58研究所，江苏 无锡 214000）

随着信息技术的发展，数据的传输及存储的量越来越大。而在数据传输中，出错的概率也越来越大。为保证数据的正确性，汉明码被广泛的采用。文章首先介绍了普通汉明码的形成原理，在此基础上对其进行了改进，使得校验位不再受特定位限制，且编码时可以减少码位的运算次数，提高了系统性能。为减少系统开销，在存储器中实现时，对电路进行了优化，使得编码电路和译码电路能够共用。该设计为大规模存储器的设计提供了良好的基础。

汉明码；存储器；纠错电路

1 引言

随着信息技术的发展，数据的传输及存储的量越来越大。而在数据传输中，出错的概率也越来越大。为保证数据的正确性，仅仅依赖器件和设备的可靠性运算是不可行的。为了纠正数据在传输过程中出现的错误，往往在信息中加入某种冗余代码，以保护数据的正确性。本文依据最常用的汉明码，首先对传统的汉明冗余码进行改进，然后用电路的形式在存储器中实现了改进的汉明码，以保证大容量存储器在存储和对出过程中的准确性。此举提高了存储器的可靠性，使存储器能适应在不同恶劣条件下的应用。

2 普通汉明码的编译原理

汉明码是1950年由汉明（Hamming）提出的纠正单个错误的群码。对于任意i值，其方法能产生（2i-1）位的编码，其中包括i个校验位和2i-1-i个信息位。信息位较少的距离为3的编码，可由位数较多的汉明码经删除若干信息位而得到。对接收到的汉明码字，我们需要验证其所有的奇偶校验组，如果都是偶校验，那么就假设接收到的码字都是正确的。如果有一组或多组是奇校验位，那么就认为出现了单个错误。具有奇校验的组模式必然与奇偶校验矩阵的某一列相匹配，对应的位置号被认为是包含了错误的信息值，将此错误取反，即可纠正。在计算机存储系统中，特别是存储电路占了大部分系统故障的大型计算机中，距离为3和4的汉明码常常用于检错和纠错[1]。对于非常长的存储字，这些码特别具有吸引力，它有良好的性能，而且编译/码电路简单，易于在工程中的实现。汉明码的原则是在m位原码的基础上增加n位的校验码，并使得式2n≥m+n+1成立。例如，对于8位原始数据，需要4位汉明码对其实现纠正，且冗余码的码校验位存于第 2n位（n=0,1,2,3…）[2～4]。

以8位数据00110010为例，对普通汉明码的编译码原理进行说明。根据普通汉明码的编码原理，整个传输的数据为PP0P011P0010。其中，P 位为校验码位，位于整个传输数据的第1、2、4、8位。普通汉明码的生成方式如下：

汉明码校验位第1位由整个传输数据的第1、3、5、7、9、11位决定（XXX1≤1210进制，此处的X为0或1）。如果这些位上“1”的个数为奇数，则第1位校验码为1，偶数则为0。按此传输数据中数据，校验位第1位为“0”。

汉明码校验位第2位由整个传输数据的第2、3、6、7、10、11位决定（XX1X≤1210进制，此处的X为0或1）。如果这些位上“1”的个数为奇数，则第1位校验码为1，偶数则为0。按此传输数据中数据，校验位第2位为“1”。

汉明码校验位第3位由整个传输数据的第4、5、6、7、12位决定（X1XX≤1210进制，此处的X为0或1）。如果这些位上“1”的个数为奇数，则第1位校验码为1，偶数则为0。按此传输数据中数据，校验位第3位为“0”。

汉明码校验位第4位由整个传输数据的第8、9、10、11、12位决定（1XXX≤1210进制，此处的X为0或1）。如果这些位上“1”的个数为奇数，则第1位校验码为1，偶数则为0。按此传输数据中数据，校验位第4位为“1”。所以，最后生成的汉明码为：010001110010。

接下来举例说明普通汉明码的译码纠错原理，如表1所示。假设第5位出错，第1位和第3位汉明码将受到影响。状态位第S1位和第S3位发生改变。假设状态位“T”表示正确，“F”表示出错；用1表示状态位“F”，用0表示状态位“T”。则状态位为1010，表明原传输码第5位出错。同样，假设第8位出错，第4位校验码将受到影响，状态位第4位发生变化，状态位为0001，表明原传输码第8位出错。以上就是普通汉明码编码实现的基本原理，其校验位是安插在原始数据中的第2n位（n=0、1、2、3…）。

3 改进后汉明码的编译原理

改进后的汉明码与普通汉明码最大的区别在于，校验位的位置不在第2n位（n=0、1、2、3…），而是在原始数据之后。以8位传输数据为例，其校验位在第9、10、11、12位。

以8位数据00110010为例，对改进后汉明码的编译码原理进行说明。根据改进汉明码的编码原理，整个传输的数据为00110010PPPP。其中，P 位为校验码位，位于整个传输数据的最后四位。改进后汉明码的生成方式如下：

汉明码校验位第1位由整个传输数据的第1、3、5、7位（XXX1≤810进制，此处的X为0或1）和第9位决定。如果这些位上“1”的个数为奇数，则第1位校验码为1，偶数则为0。按此传输数据中数据，校验位第1位为“0”。

?

汉明码校验位第2位由整个传输数据的第2、3、6、7位（XX1X≤810进制，此处的X为0或1）和第10位决定。如果这些位上“1”的个数为奇数，则第1位校验码为1，偶数则为0。按此传输数据中数据，校验位第2位为“0”。

汉明码校验位第3位由整个传输数据的第4、5、6、7位（X1XX≤810进制，此处的X为0或1）和第11、12位决定。如果这些位上“1”的个数为奇数，则第1位校验码为1，偶数则为0。按此传输数据中数据，校验位第3位为“0”。

汉明码校验位第4位由整个传输数据的第8位（1XXX=810进制，此处的X为0或1）和第9、10、11、12位决定。如果这些位上“1”的个数为奇数，则第1位校验码为1，偶数则为0。按此传输数据中数据，校验位第4位为“0”。所以，最后生成的汉明码为：001100100000。

4 改进后汉明码在存储器中的实现

现在存储器的容量越来越大，应用的领域越来越广。当在恶劣环境中应用时，对存储器的可靠性要求也越来越高，存储器在数据存储和传输的过程中，误码率也随之增加，此时就要求存储器中加入冗余纠错的模块。而汉明码在存储器冗余纠错中常常被使用。图1中显示了存储器中汉明码编码/译码模块的位置，图中EN为编码/译码控制信号。EN为1时，数据输入，经过汉明码编码模块输出至存储单元。当EN为0时，数据输入，经过汉明码译码模块，将数据传输至灵敏放大器，经由寄存器，发送到I/O端口。

以8位的存储器为例，在设计汉明码模块时，为减小系统开销，我们将电路进行了优化，使得编码和译码电路能够共用。编码电路如图2所示。首先将H（9︰12）码位设为0，与H（1︰8）一起组成原始数据，经过编码电路，形成S（1︰4）。将H（1︰8）、S（1︰4）存入存储单元中。

接下来举例说明改进后汉明码的译码纠错原理，如表2所示。假设第5位出错，第9位和第11位的校验码将受到影响。状态位第S1位和第S3位发生改变。假设状态位“T”表示正确，“F”表示出错；用1表示状态位“F”，用0表示状态位“T”。则状态位为1010，表明原传输码第5位出错。同样，假设第7位出错，第9、10、11位的校验码将受到影响，状态位第1、2、3位发生变化，状态位为1110，表明原传输码第7位出错。同理可以验证第9位和第12位出错。

以上就是改进后汉明码的译码纠错原理。与普通汉明码相比，改进后的汉明码的校验位不再受2n位（n=0、1、2、3…）的限制。并且在7位原码的编译中，改进的汉明码进行了19次的码位运算，与普通汉明码的20次码位运算相比，减小了1次，也减小了系统的开销[5]。

当EN为0时，模块将进行译码操作。为减小系统开销，在设计上优化后，译码模块将和编码模块公用编码电路，结构图如图3所示。其实现原理为：将12位的数据从存储单元中读出，经过灵敏放大器，将数据输入至汉明码译码模块。经过编译，形成S（1︰4）的状态码。4位的状态码经过一系列的逻辑组合电路，生成8位数据位D（1︰8），将8位数据位与H（1︰8）位相异或，得到的数据就为最后输出的正确数据。

5 小结

在大规模数据传输和存储设备中，汉明码由于良好的性能，而且编译/码电路简单，易于在工程中的实现，被广泛地采用。文章首先简单介绍了汉明码的编码/译码的基本原理，原始汉明码的编码与整个传输信息位长度有关，并固定了校验位在第2n位（n=0、1、2、3…）。在此基础上，我们改进了汉明码的编码方式，使编码方式只与原始信息位和一位相关校验位相关，且将校验位置于传输的原始码之后，不受2n位（n=0、1、2、3…）位的限制。在存储器中实现时，首先对汉明码模块的工作方式进行了介绍，也对整个编码/译码电路进行了优化，使得编码和译码电路可以共用，降低了系统的开销。该设计为大规模存储器的设计提供了良好的基础。

［1］John F Wakerly. 数字设计原理与实践[M].北京：机械工业出版社，2003.

［2］Zhao Jianwu, Shi Yibing, Li Yanjun. Software Implementation of a Novel Approach to Improving Burst Errors Correction Capability of Hamming Code [C]. The Eighth International Conference on Electronic Measurement and Instruments, 2007.

［3］B Fu, P Ampadu. Error control combining Hamming and product codes for energy efficient nanoscale on-chip interconnects [J]. IET Comput. Digit. Tech., 2010, （4）:251-261.

［4］章学静，薛琳，李金平，等. 汉明码及编译码算法的研究与实现[J]. 北京联合大学学报（自然科学版），2008，22 （1）：46-49.

［5］U K Kumar, B S Umashankar. Improved Hamming code for Error Detection and Correction [C]. Wireless pervasive computing, ISWPC’07 2ndInternational Symposium, San Juan, 2007, 498-500.

Improved of Hamming Code and Circuits Realized in Memory

JIANG Ting, XU Rui, ZHOU Xin-jie
（China Electronics Technology Group Corporation No.58Research Institute,Wuxi214035,China）

With the development of information technology, the number of data transmission and storage are more and more large. For ensuring the correctness of data, hamming code is used widely. This paper induces the principles of general hamming code first. On that base, we do the improvement of code: check bits aren’t limited in the specific bits, and the number of operation may be reduced when it’s coding, enhancement the performance of system. For reducing the waste of systems, we optimize the error detection and correction circuit when realized in memory, which circuit of coding and decoding can be used in common. This work supplies a good base for the design of large scale memory.

hamming code; memory; correction circuit

TN303

A

1681-1070（2011）05-0019-04

2011-04-22

蒋 婷（1976—），女，浙江东阳人，工程师，现在中国电子科技集团公司第58研究所从事集成电路设计工作。

电 路 设 计