漢明碼的改進(jìn)及在存儲(chǔ)器中的實(shí)現(xiàn)

蔣 婷，徐 睿，周昕杰

（中國(guó)電子科技集團(tuán)公司第58研究所，江蘇 無(wú)錫 214000）

漢明碼的改進(jìn)及在存儲(chǔ)器中的實(shí)現(xiàn)

蔣 婷，徐 睿，周昕杰

（中國(guó)電子科技集團(tuán)公司第58研究所，江蘇 無(wú)錫 214000）

隨著信息技術(shù)的發(fā)展，數(shù)據(jù)的傳輸及存儲(chǔ)的量越來(lái)越大。而在數(shù)據(jù)傳輸中，出錯(cuò)的概率也越來(lái)越大。為保證數(shù)據(jù)的正確性，漢明碼被廣泛的采用。文章首先介紹了普通漢明碼的形成原理，在此基礎(chǔ)上對(duì)其進(jìn)行了改進(jìn)，使得校驗(yàn)位不再受特定位限制，且編碼時(shí)可以減少碼位的運(yùn)算次數(shù)，提高了系統(tǒng)性能。為減少系統(tǒng)開銷，在存儲(chǔ)器中實(shí)現(xiàn)時(shí)，對(duì)電路進(jìn)行了優(yōu)化，使得編碼電路和譯碼電路能夠共用。該設(shè)計(jì)為大規(guī)模存儲(chǔ)器的設(shè)計(jì)提供了良好的基礎(chǔ)。

漢明碼；存儲(chǔ)器；糾錯(cuò)電路

1 引言

隨著信息技術(shù)的發(fā)展，數(shù)據(jù)的傳輸及存儲(chǔ)的量越來(lái)越大。而在數(shù)據(jù)傳輸中，出錯(cuò)的概率也越來(lái)越大。為保證數(shù)據(jù)的正確性，僅僅依賴器件和設(shè)備的可靠性運(yùn)算是不可行的。為了糾正數(shù)據(jù)在傳輸過(guò)程中出現(xiàn)的錯(cuò)誤，往往在信息中加入某種冗余代碼，以保護(hù)數(shù)據(jù)的正確性。本文依據(jù)最常用的漢明碼，首先對(duì)傳統(tǒng)的漢明冗余碼進(jìn)行改進(jìn)，然后用電路的形式在存儲(chǔ)器中實(shí)現(xiàn)了改進(jìn)的漢明碼，以保證大容量存儲(chǔ)器在存儲(chǔ)和對(duì)出過(guò)程中的準(zhǔn)確性。此舉提高了存儲(chǔ)器的可靠性，使存儲(chǔ)器能適應(yīng)在不同惡劣條件下的應(yīng)用。

2 普通漢明碼的編譯原理

漢明碼是1950年由漢明（Hamming）提出的糾正單個(gè)錯(cuò)誤的群碼。對(duì)于任意i值，其方法能產(chǎn)生（2i-1）位的編碼，其中包括i個(gè)校驗(yàn)位和2i-1-i個(gè)信息位。信息位較少的距離為3的編碼，可由位數(shù)較多的漢明碼經(jīng)刪除若干信息位而得到。對(duì)接收到的漢明碼字，我們需要驗(yàn)證其所有的奇偶校驗(yàn)組，如果都是偶校驗(yàn)，那么就假設(shè)接收到的碼字都是正確的。如果有一組或多組是奇校驗(yàn)位，那么就認(rèn)為出現(xiàn)了單個(gè)錯(cuò)誤。具有奇校驗(yàn)的組模式必然與奇偶校驗(yàn)矩陣的某一列相匹配，對(duì)應(yīng)的位置號(hào)被認(rèn)為是包含了錯(cuò)誤的信息值，將此錯(cuò)誤取反，即可糾正。在計(jì)算機(jī)存儲(chǔ)系統(tǒng)中，特別是存儲(chǔ)電路占了大部分系統(tǒng)故障的大型計(jì)算機(jī)中，距離為3和4的漢明碼常常用于檢錯(cuò)和糾錯(cuò)[1]。對(duì)于非常長(zhǎng)的存儲(chǔ)字，這些碼特別具有吸引力，它有良好的性能，而且編譯/碼電路簡(jiǎn)單，易于在工程中的實(shí)現(xiàn)。漢明碼的原則是在m位原碼的基礎(chǔ)上增加n位的校驗(yàn)碼，并使得式2n≥m+n+1成立。例如，對(duì)于8位原始數(shù)據(jù)，需要4位漢明碼對(duì)其實(shí)現(xiàn)糾正，且冗余碼的碼校驗(yàn)位存于第 2n位（n=0,1,2,3…）[2～4]。

以8位數(shù)據(jù)00110010為例，對(duì)普通漢明碼的編譯碼原理進(jìn)行說(shuō)明。根據(jù)普通漢明碼的編碼原理，整個(gè)傳輸?shù)臄?shù)據(jù)為PP0P011P0010。其中，P 位為校驗(yàn)碼位，位于整個(gè)傳輸數(shù)據(jù)的第1、2、4、8位。普通漢明碼的生成方式如下：

漢明碼校驗(yàn)位第1位由整個(gè)傳輸數(shù)據(jù)的第1、3、5、7、9、11位決定（XXX1≤1210進(jìn)制，此處的X為0或1）。如果這些位上“1”的個(gè)數(shù)為奇數(shù)，則第1位校驗(yàn)碼為1，偶數(shù)則為0。按此傳輸數(shù)據(jù)中數(shù)據(jù)，校驗(yàn)位第1位為“0”。

漢明碼校驗(yàn)位第2位由整個(gè)傳輸數(shù)據(jù)的第2、3、6、7、10、11位決定（XX1X≤1210進(jìn)制，此處的X為0或1）。如果這些位上“1”的個(gè)數(shù)為奇數(shù)，則第1位校驗(yàn)碼為1，偶數(shù)則為0。按此傳輸數(shù)據(jù)中數(shù)據(jù)，校驗(yàn)位第2位為“1”。

漢明碼校驗(yàn)位第3位由整個(gè)傳輸數(shù)據(jù)的第4、5、6、7、12位決定（X1XX≤1210進(jìn)制，此處的X為0或1）。如果這些位上“1”的個(gè)數(shù)為奇數(shù)，則第1位校驗(yàn)碼為1，偶數(shù)則為0。按此傳輸數(shù)據(jù)中數(shù)據(jù)，校驗(yàn)位第3位為“0”。

漢明碼校驗(yàn)位第4位由整個(gè)傳輸數(shù)據(jù)的第8、9、10、11、12位決定（1XXX≤1210進(jìn)制，此處的X為0或1）。如果這些位上“1”的個(gè)數(shù)為奇數(shù)，則第1位校驗(yàn)碼為1，偶數(shù)則為0。按此傳輸數(shù)據(jù)中數(shù)據(jù)，校驗(yàn)位第4位為“1”。所以，最后生成的漢明碼為：010001110010。

接下來(lái)舉例說(shuō)明普通漢明碼的譯碼糾錯(cuò)原理，如表1所示。假設(shè)第5位出錯(cuò)，第1位和第3位漢明碼將受到影響。狀態(tài)位第S1位和第S3位發(fā)生改變。假設(shè)狀態(tài)位“T”表示正確，“F”表示出錯(cuò)；用1表示狀態(tài)位“F”，用0表示狀態(tài)位“T”。則狀態(tài)位為1010，表明原傳輸碼第5位出錯(cuò)。同樣，假設(shè)第8位出錯(cuò)，第4位校驗(yàn)碼將受到影響，狀態(tài)位第4位發(fā)生變化，狀態(tài)位為0001，表明原傳輸碼第8位出錯(cuò)。以上就是普通漢明碼編碼實(shí)現(xiàn)的基本原理，其校驗(yàn)位是安插在原始數(shù)據(jù)中的第2n位（n=0、1、2、3…）。

3 改進(jìn)后漢明碼的編譯原理

改進(jìn)后的漢明碼與普通漢明碼最大的區(qū)別在于，校驗(yàn)位的位置不在第2n位（n=0、1、2、3…），而是在原始數(shù)據(jù)之后。以8位傳輸數(shù)據(jù)為例，其校驗(yàn)位在第9、10、11、12位。

以8位數(shù)據(jù)00110010為例，對(duì)改進(jìn)后漢明碼的編譯碼原理進(jìn)行說(shuō)明。根據(jù)改進(jìn)漢明碼的編碼原理，整個(gè)傳輸?shù)臄?shù)據(jù)為00110010PPPP。其中，P 位為校驗(yàn)碼位，位于整個(gè)傳輸數(shù)據(jù)的最后四位。改進(jìn)后漢明碼的生成方式如下：

漢明碼校驗(yàn)位第1位由整個(gè)傳輸數(shù)據(jù)的第1、3、5、7位（XXX1≤810進(jìn)制，此處的X為0或1）和第9位決定。如果這些位上“1”的個(gè)數(shù)為奇數(shù)，則第1位校驗(yàn)碼為1，偶數(shù)則為0。按此傳輸數(shù)據(jù)中數(shù)據(jù)，校驗(yàn)位第1位為“0”。

?

漢明碼校驗(yàn)位第2位由整個(gè)傳輸數(shù)據(jù)的第2、3、6、7位（XX1X≤810進(jìn)制，此處的X為0或1）和第10位決定。如果這些位上“1”的個(gè)數(shù)為奇數(shù)，則第1位校驗(yàn)碼為1，偶數(shù)則為0。按此傳輸數(shù)據(jù)中數(shù)據(jù)，校驗(yàn)位第2位為“0”。

漢明碼校驗(yàn)位第3位由整個(gè)傳輸數(shù)據(jù)的第4、5、6、7位（X1XX≤810進(jìn)制，此處的X為0或1）和第11、12位決定。如果這些位上“1”的個(gè)數(shù)為奇數(shù)，則第1位校驗(yàn)碼為1，偶數(shù)則為0。按此傳輸數(shù)據(jù)中數(shù)據(jù)，校驗(yàn)位第3位為“0”。

漢明碼校驗(yàn)位第4位由整個(gè)傳輸數(shù)據(jù)的第8位（1XXX=810進(jìn)制，此處的X為0或1）和第9、10、11、12位決定。如果這些位上“1”的個(gè)數(shù)為奇數(shù)，則第1位校驗(yàn)碼為1，偶數(shù)則為0。按此傳輸數(shù)據(jù)中數(shù)據(jù)，校驗(yàn)位第4位為“0”。所以，最后生成的漢明碼為：001100100000。

4 改進(jìn)后漢明碼在存儲(chǔ)器中的實(shí)現(xiàn)

現(xiàn)在存儲(chǔ)器的容量越來(lái)越大，應(yīng)用的領(lǐng)域越來(lái)越廣。當(dāng)在惡劣環(huán)境中應(yīng)用時(shí)，對(duì)存儲(chǔ)器的可靠性要求也越來(lái)越高，存儲(chǔ)器在數(shù)據(jù)存儲(chǔ)和傳輸?shù)倪^(guò)程中，誤碼率也隨之增加，此時(shí)就要求存儲(chǔ)器中加入冗余糾錯(cuò)的模塊。而漢明碼在存儲(chǔ)器冗余糾錯(cuò)中常常被使用。圖1中顯示了存儲(chǔ)器中漢明碼編碼/譯碼模塊的位置，圖中EN為編碼/譯碼控制信號(hào)。EN為1時(shí)，數(shù)據(jù)輸入，經(jīng)過(guò)漢明碼編碼模塊輸出至存儲(chǔ)單元。當(dāng)EN為0時(shí)，數(shù)據(jù)輸入，經(jīng)過(guò)漢明碼譯碼模塊，將數(shù)據(jù)傳輸至靈敏放大器，經(jīng)由寄存器，發(fā)送到I/O端口。

以8位的存儲(chǔ)器為例，在設(shè)計(jì)漢明碼模塊時(shí)，為減小系統(tǒng)開銷，我們將電路進(jìn)行了優(yōu)化，使得編碼和譯碼電路能夠共用。編碼電路如圖2所示。首先將H（9︰12）碼位設(shè)為0，與H（1︰8）一起組成原始數(shù)據(jù)，經(jīng)過(guò)編碼電路，形成S（1︰4）。將H（1︰8）、S（1︰4）存入存儲(chǔ)單元中。

接下來(lái)舉例說(shuō)明改進(jìn)后漢明碼的譯碼糾錯(cuò)原理，如表2所示。假設(shè)第5位出錯(cuò)，第9位和第11位的校驗(yàn)碼將受到影響。狀態(tài)位第S1位和第S3位發(fā)生改變。假設(shè)狀態(tài)位“T”表示正確，“F”表示出錯(cuò)；用1表示狀態(tài)位“F”，用0表示狀態(tài)位“T”。則狀態(tài)位為1010，表明原傳輸碼第5位出錯(cuò)。同樣，假設(shè)第7位出錯(cuò)，第9、10、11位的校驗(yàn)碼將受到影響，狀態(tài)位第1、2、3位發(fā)生變化，狀態(tài)位為1110，表明原傳輸碼第7位出錯(cuò)。同理可以驗(yàn)證第9位和第12位出錯(cuò)。

以上就是改進(jìn)后漢明碼的譯碼糾錯(cuò)原理。與普通漢明碼相比，改進(jìn)后的漢明碼的校驗(yàn)位不再受2n位（n=0、1、2、3…）的限制。并且在7位原碼的編譯中，改進(jìn)的漢明碼進(jìn)行了19次的碼位運(yùn)算，與普通漢明碼的20次碼位運(yùn)算相比，減小了1次，也減小了系統(tǒng)的開銷[5]。

當(dāng)EN為0時(shí)，模塊將進(jìn)行譯碼操作。為減小系統(tǒng)開銷，在設(shè)計(jì)上優(yōu)化后，譯碼模塊將和編碼模塊公用編碼電路，結(jié)構(gòu)圖如圖3所示。其實(shí)現(xiàn)原理為：將12位的數(shù)據(jù)從存儲(chǔ)單元中讀出，經(jīng)過(guò)靈敏放大器，將數(shù)據(jù)輸入至漢明碼譯碼模塊。經(jīng)過(guò)編譯，形成S（1︰4）的狀態(tài)碼。4位的狀態(tài)碼經(jīng)過(guò)一系列的邏輯組合電路，生成8位數(shù)據(jù)位D（1︰8），將8位數(shù)據(jù)位與H（1︰8）位相異或，得到的數(shù)據(jù)就為最后輸出的正確數(shù)據(jù)。

5 小結(jié)

在大規(guī)模數(shù)據(jù)傳輸和存儲(chǔ)設(shè)備中，漢明碼由于良好的性能，而且編譯/碼電路簡(jiǎn)單，易于在工程中的實(shí)現(xiàn)，被廣泛地采用。文章首先簡(jiǎn)單介紹了漢明碼的編碼/譯碼的基本原理，原始漢明碼的編碼與整個(gè)傳輸信息位長(zhǎng)度有關(guān)，并固定了校驗(yàn)位在第2n位（n=0、1、2、3…）。在此基礎(chǔ)上，我們改進(jìn)了漢明碼的編碼方式，使編碼方式只與原始信息位和一位相關(guān)校驗(yàn)位相關(guān)，且將校驗(yàn)位置于傳輸?shù)脑即a之后，不受2n位（n=0、1、2、3…）位的限制。在存儲(chǔ)器中實(shí)現(xiàn)時(shí)，首先對(duì)漢明碼模塊的工作方式進(jìn)行了介紹，也對(duì)整個(gè)編碼/譯碼電路進(jìn)行了優(yōu)化，使得編碼和譯碼電路可以共用，降低了系統(tǒng)的開銷。該設(shè)計(jì)為大規(guī)模存儲(chǔ)器的設(shè)計(jì)提供了良好的基礎(chǔ)。

［1］John F Wakerly. 數(shù)字設(shè)計(jì)原理與實(shí)踐[M].北京：機(jī)械工業(yè)出版社，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］章學(xué)靜，薛琳，李金平，等. 漢明碼及編譯碼算法的研究與實(shí)現(xiàn)[J]. 北京聯(lián)合大學(xué)學(xué)報(bào)（自然科學(xué)版），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—），女，浙江東陽(yáng)人，工程師，現(xiàn)在中國(guó)電子科技集團(tuán)公司第58研究所從事集成電路設(shè)計(jì)工作。

電 路 設(shè) 計(jì)