最新新闻Information announcement.

主页 > 公司动态 > 最新新闻 >

汉明码Hamming原理与实例

发布时间:2019-04-16

汉明码(Hamming Code)也叫海明码,是Richard Hamming(贝尔实验室)于1950年发明的,汉明码也是利用了奇偶校验位概念,通过在数据位后增加一些比特以验证数据的有效性,故汉明码也属于线性纠错码(可纠错1-bit错误检出2-bit错误)。汉明码无法实现2位及2位以上纠错。

一、汉明码原理

汉明码运算需要构造G生成矩阵和H监督矩阵,关于构造方法可参考相关计算机原理书籍,这里只需了解些简单的概念即可。

设数据位数为m,校验位数为k,则总编码位数为n,所以,n=m+k,则,

有Hamming不等式:

2^k-1>=n

也可表示为:2^k>=m+k+1,该不等式用于对比运算计算数据位数和检验位数,举个例子假设数据位为64,那么校验位则为("2^k-k>=65" =>k=7)。

校验位数一般指最小值,因为k越小总信息位会越小,传输开销自然越小。

信息位数一般指最大值,但由于2^k-k只能在固定的离散值里取值,所以信息位也可能不是最大值,比如信息位为24,计算需要校验位5,但同样可信息位为25时,校验位同样是5。

校验位数VS信息位数关系如下表:

校验位数k   信息位(最大)m   编码长度n  
1   0   1  
2   1   3  
3   4   7  
4   11   15  
5   26   31  
6   57   63  
7   120   127  

注:汉明码的特性决定,一般不会做太多信息位的校验,信息位越长出现多余两个错误的概率会越高,这将带来纠错的难度。

二、汉明码实例

下文示例为(30,24)汉明码计算方法,用在MIPI DSI包头部分(MIPI Alliance Specification for Display Serial Interface,Chapter 9),DSI包头格式固定为24bits Data+8bits ECC,8bitsECC中预设P6=P7=0,所以实际n=30,m=24,k=6。

检验位计算方法参考MIPI DSI table22生成矩阵(Px vs [DataBit0~DataBitx]),比如P5=D10^D11^....D23,表示对应DataBit23的P5列,只有这些DataBit位为1。

int main() { char res; char in[20]={0}; char D0,D1,D2,D3,D4,D5,D6,D7,D8,D9,D10,D11,D12,D13,D14,D15,D16,D17,D18,D19,D20,D21,D22,D23; char P0,P1,P2,P3,P4,P5,P6,P7; cout<<"Checking Codes(eg.0x1234AF, \"-\" for exit): 0x"; cin>>in; if(in[0]=='-') { return 0; } for(int i=0;i<6;i++){ if((in[i]>='0') && (in[i]<='9')) { in[i] = in[i]-0x30; }else if((in[i]>='A') && (in[i]<='F')){ in[i] = in[i]-'A'+10; }else { return 0; } } D0=in[1]&0x01; D1=(in[1]&0x02)>>1; D2=(in[1]&0x04)>>2; D3=(in[1]&0x08)>>3; D4=in[0]&0x01; D5=(in[0]&0x02)>>1; D6=(in[0]&0x04)>>2; D7=(in[0]&0x08)>>3; D8=in[3]&0x01; D9=(in[3]&0x02)>>1; D10=(in[3]&0x04)>>2; D11=(in[3]&0x08)>>3; D12=in[2]&0x01; D13=(in[2]&0x02)>>1; D14=(in[2]&0x04)>>2; D15=(in[2]&0x08)>>3; D16=in[5]&0x01; D17=(in[5]&0x02)>>1; D18=(in[5]&0x04)>>2; D19=(in[5]&0x08)>>3; D20=in[4]&0x01; D21=(in[4]&0x02)>>1; D22=(in[4]&0x04)>>2; D23=(in[4]&0x08)>>3; P7=0; P6=0; P5=D10^D11^D12^D13^D14^D15^D16^D17^D18^D19^D21^D22^D23; P4=D4^D5^D6^D7^D8^D9^D16^D17^D18^D19^D20^D22^D23; P3=D1^D2^D3^D7^D8^D9^D13^D14^D15^D19^D20^D21^D23; P2=D0^D2^D3^D5^D6^D9^D11^D12^D15^D18^D20^D21^D22; P1=D0^D1^D3^D4^D6^D8^D10^D12^D14^D17^D20^D21^D22^D23; P0=D0^D1^D2^D4^D5^D7^D10^D11^D13^D16^D20^D21^D22^D23; res = ((P7&0x01)*8+(P6&0x01)*4+(P5&0x01)*2+(P4&0x01))*16+(P3&0x01)*8+(P2&0x01)*4+(P1&0x01)*2+(P0&0x01); printf("Result:0x%02X\r\n",res); return 0; }

参考资料: