Hamming code verification [simple and detailed]

Haiming code

1. What is Hamming code :

A man named Richard Hanming Grandpa is 1950 Test and error correction method proposed in , It has a Error correction ability .

2. The calculation method of Hamming code :

Set the binary code to be detected as n position ,K by Detection bit ( Provide error correction ), in total n+k A code

The relationship satisfied by the middle detection bit :$2^k$>=(n+k+1) === This relationship is also to find different code lengths n The number of bits to be detected k

1. Coding rules of Hamming code

set up k individual Inspection position by Pk,Pk-1...P1,

n individual Data bits by Dn-1,Dn-2,....D1,D0 Corresponding Haiming code by Hn+k,Hn+k+1,....H1

that Inspection position And Haiming code Location correspondence of :

(1)Pi In the second of Hamming code $2^{i-1}$ Location , such as P2, $2^{2-1}$ Then the position of Hamming code is $H_{{}_2}$

(2) Be careful : Any bit of Hamming code is checked by several check bits

The corresponding relationship among them :

Verified The Hamming code of Subscript be equal to All involved Check this bit Of Inspection position Sum of subscripts

Check bit By oneself Self verification

Eg: $H_{12}$, His subscript is 12, The corresponding is 8+4( The above formula solves , To correspond to binary ) That is the first of Hamming code 8 And the 4 Inspection position

Examples of practical applications :

about 8 Data bits of bits , Hamming code verification requires 4 Check bits ($2^k$>=n+k+1,$2^4$>=8+4+1)

Make Data bits by :$D_7$、$D_6$、$D_5$、$D_4$、$D_3$、$D_2$、$D_1$、$D_0$

​ Check bit by :$P_4$、$P_3$、$P_2$、$P_1$、$P_4$

​ Formed Haiming code :$H_{12}$、$H_{12}$、$H_{11}$、$H_{10}$…$H_1$

The specific process :

(1) determine D And P Position in Hamming code

$H_{12}$	$H_{11}$	$H_{10}$	$H_9$	$H_8$	$H_7$	$H_6$	$H_5$	$H_4$	$H_3$	$H_2$	$H_1$
$D_7$	$D_6$	$D_5$	$D_4$	$P_4$	$D_3$	$D_2$	$D_1$	$P_3$	$D_0$	$P_2$	$P_1$

Be careful : In the middle of $H_8$,$H_3$

(2) Calculate the check bits

first Inspection position $P_1$ It's located in $H_1$ The location of , His inspection position is $H_1$,$H_3$,$H_5$,$H_7$,$H_9$,$H_{11}$ Namely Read one , One person away

the second Inspection position $P_2$ It's located in $H_2$ The location of , His inspection position is $H_2$,$H_3$,$H_6$,$H_7$,$H_{10}$,$H_{11}$ Namely Read two , Partition 2 position

Third Inspection position $P_3$ It's located in $H_4$ The location of , His inspection position is $H_4$,$H_5$,$H_6$,$H_7$,$H_9$,$H_{12}$ Namely Read four , Four digits apart

The fourth one Inspection position $P_4$ It's located in $H_8$ The location of , His inspection position is $H_8$,$H_9$,$H_{10}$,$H_{11}$,$H_{12}$ Namely read 8 position , Partition 8 position

And so on ,

​ The first n Of parity bits Hemingway yes : from Oneself Start , read $2^{n-1}$ position , Partition $2^{n-1}$ position … Until the end

(3) The data corresponding to the check bit is Exclusive or operation

The general default is Even check , Sure Find out Each check bit is responsible for detecting Hemingway — use Odd check , The even check value of each check bit Take the opposite that will do

$$
&P1=D0⊕D1⊕D3⊕D4⊕D6 \
&P2=D0⊕D2⊕D3⊕D5⊕D6 \
&P3=D1⊕D2⊕D3⊕D7 \
&P4=D4⊕D5⊕D6⊕D7 \

$$

(4) Check error

 It is very simple to check the data using Hamming code ,
     According to the above method , We can easily know which Hamming bit each check bit is responsible for detecting ,
     Just XOR it .

$$

&G4=P4⊕D4⊕D5⊕D6⊕D7\
&G3=P3=D1⊕D2⊕D3⊕D7 \
&G2=D2⊕D2⊕D3⊕D5⊕D6 \
&G1=D1⊕D1⊕D3⊕D4⊕D6 \end
$$

(5) determine

1. Normal condition :

If the Even check , be G4G3G2G1 All for 0 Means data There is no mistake ,

​ Odd check It should be all 1, Otherwise, an error occurs .

2. Wrong situation

When something goes wrong , take G4G3G2G1 The value of is converted to Decimal system You know what happened Wrong place

​ Such as G4G3G2G1=0110, It indicates that the H6 There is an error in the data of this location , As long as it is reversed, it can be corrected .

The end

Reference link ： Haiming code （ Hamming code ） Detailed explanation