Error Correction Design Principle of Hamming Check Code

This article does not describe the calculation method of Hamming code,为了节省您的时间,Please learn Hamming code first/How parity is calculated,If you are curious about the error correction design ideas of its Hamming code, read this article again！

The information is in bitsn,校验位数为k,correct state1位,So total digits：n+k+1.
To use the check digit to check out all the positions should be satisfied2^k>=n+k+1

Parity check can be used to determine whether there is an error,But how to uniquely locate the wrong location of a certain one？In order to reflect such inherent information through the check code,The location and meaning of the checksum itself are crucial.
海明校验码P1,P2,P3,...,Pi位置分别位于：1,2,4,8,2^k-1.
Its intrinsic meanings represent weights respectively：2^0,2^1,2^2,...,2^k The role in binary is equivalent to that in decimal"个十百千万...",Based on these weights, any one-digit number can be combinedx∈[0,2^k]
When a certain correction codeSi(Based on detection codePiand maintained groupsgiXOR is calculated,Please refer to the textbook for details)The calculated result is not as expected,Then the check can be concludedPicode or is responsible for detection小组giThere must have been anomalous data.（For the calculation method of Hamming code, please refer to the textbook of computer composition principle,This article is intended to deepen understanding）

Each check code is responsible for detection小组The included location of is determined,spousal rule如下：
P1 testing groupg1包含：1,3,5,7,9,11... 位.
P2 testing groupg2包含：2,3,6,7,10,11,14 ... 位.
P3 testing groupg3包含：4,5,6,7,12,13,14,15 ... 位.

为什么要这样设计呢？

The explanation given here in the textbook is more difficult to understand.Here it can be explained in another easy-to-understand way：
Change the corresponding position to binary
P1 testing groupg1包含：1(00001),3(00011),5(00101),7(01001),9(10001) ... 位.
P2testing groupg2包含：2(00010),3(00011),6(00110),7(0111),10(01010) ... 位.
P3testing groupg3包含：4(00100),5(00101),6(00110),7(00111),12(01100) ... 位.

可一看到The pattern of the check code and the group element responsible for detection is ：The binary corresponding to each element must be used in the representation processPithe weight represented（之前说过PiEquivalent to weights in binary,The status is similar to the ten million in the decimal system）.比如5对应的二进制(000101)的第2位是0,,而P2代表2^1,所以P2Incapable of expressing5这个位置,Naturally, it cannot be responsible for detection and correction5这个位置.而P1代表2^0、P3代表2^2,且5(000101)的第1、3位是1,所以P1和P3Can be responsible for detection5这个位置.

7	6	5	4	3	2	1
D4	D3	D2	P3	D1	P2	P1

For example, the correct Hamming code for a certain transmission is 0100101,If the Hamming code received after transmission is 0100111,Its error position can be determined according to the following steps：   

二进制编号	1	2	3	4	5	6	7
Correct Hamming code	0	1	0	0	1	0	1
接收到的汉明码	0	1	0	0	1	1	1

Then the new detection bit is
S3=4⊕5⊕6⊕7,即S3=0⊕1⊕1⊕1 = 1  

S2=2⊕3⊕6⊕7,即S2=1⊕0⊕1⊕1 = 1

S1=1⊕3⊕5⊕7,即S1=0⊕0⊕1⊕1 = 0
可以看到S3和S2出现异常,而S1未出现异常,可以分析：
一定是P3和P2The jointly detected data is abnormal and the data must not be thereP1in the maintained data,
根据spousal rule,The essence of the above is：The binary representation of this anomalous data has definitely arrived2^2、2^1,and not used2^0次方.In fact, this data isS3 S2 S1combination of itself,即：110 ,也就是第6data bits were abnormal.

 At this time, I have to admire the ingeniousness of the Hamming code design,Make full use of the location and the characteristics of its binary itself.