Graphical depiction of the 4 data bits d_{1} to d_{4} and 3 parity bits p_{1} to p_{3} and which parity bits apply to which data bits
In coding theory, Hamming(7,4) is a linear errorcorrecting code that encodes 4 bits of data into 7 bits by adding 3 parity bits. It is a member of a larger family of Hamming codes, but the term Hamming code often refers to this specific code that Richard W. Hamming introduced in 1950. At the time, Hamming worked at Bell Telephone Laboratories and was frustrated with the errorprone punched card reader, which is why he started working on errorcorrecting codes.^{[1]}
The Hamming code adds three additional check bits to every four data bits of the message. Hamming's (7,4) algorithm can correct any singlebit error, or detect all singlebit and twobit errors. In other words, the minimal Hamming distance between any two correct codewords is 3, and received words can be correctly decoded if they are at a distance of at most one from the codeword that was transmitted by the sender. This means that for transmission medium situations where burst errors do not occur, Hamming's (7,4) code is effective (as the medium would have to be extremely noisy for 2 out of 7 bits to be flipped).
Goal
The goal of Hamming codes is to create a set of parity bits that overlap such that a singlebit error (the bit is logically flipped in value) in a data bit or a parity bit can be detected and corrected. While multiple overlaps can be created, the general method is presented in Hamming codes.

Bit #

1

2

3

4

5

6

7

Transmitted bit

p_1

p_2

d_1

p_3

d_2

d_3

d_4

p_1

Yes

No

Yes

No

Yes

No

Yes

p_2

No

Yes

Yes

No

No

Yes

Yes

p_3

No

No

No

Yes

Yes

Yes

Yes

This table describes which parity bits cover which transmitted bits in the encoded word. For example, p_{2} provides an even parity for bits 2, 3, 6, & 7. It also details which transmitted by which parity bit by reading the column. For example, d_{1} is covered by p_{1} and p_{2} but not p_{3} This table will have a striking resemblance to the paritycheck matrix (H) in the next section.
Furthermore, if the parity columns in the above table were removed


d_1

d_2

d_3

d_4

p_1

Yes

Yes

No

Yes

p_2

Yes

No

Yes

Yes

p_3

No

Yes

Yes

Yes

then resemblance to rows 1, 2, & 4 of the code generator matrix (G) below will also be evident.
So, by picking the parity bit coverage correctly, all errors with a Hamming distance of 1 can be detected and corrected, which is the point of using a Hamming code.
Hamming matrices
Hamming codes can be computed in linear algebra terms through matrices because Hamming codes are linear codes. For the purposes of Hamming codes, two Hamming matrices can be defined: the code generator matrix G and the paritycheck matrix H:

\mathbf{G} := \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}, \qquad \mathbf{H} := \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix}.
Bit position of the data and parity bits
As mentioned above, rows 1, 2, & 4 of G should look familiar as they map the data bits to their parity bits:

p_{1} covers d_{1}, d_{2}, d_{4}

p_{2} covers d_{1}, d_{3}, d_{4}

p_{3} covers d_{2}, d_{3}, d_{4}
The remaining rows (3, 5, 6, 7) map the data to their position in encoded form and there is only 1 in that row so it is an identical copy. In fact, these four rows are linearly independent and form the identity matrix (by design, not coincidence).
Also as mentioned above, the three rows of H should be familiar. These rows are used to compute the syndrome vector at the receiving end and if the syndrome vector is the null vector (all zeros) then the received word is errorfree; if nonzero then the value indicates which bit has been flipped.
The 4 data bits — assembled as a vector p — is premultiplied by G (i.e., Gp) and taken modulo 2 to yield the encoded value that is transmitted. The original 4 data bits are converted to 7 bits (hence the name "Hamming(7,4)") with 3 parity bits added to ensure even parity using the above data bit coverages. The first table above shows the mapping between each data and parity bit into its final bit position (1 through 7) but this can also be presented in a Venn diagram. The first diagram in this article shows three circles (one for each parity bit) and encloses data bits that each parity bit covers. The second diagram (shown to the right) is identical but, instead, the bit positions are marked.
For the remainder of this section, the following 4 bits (shown as a column vector) will be used as a running example:

\mathbf{p} = \begin{pmatrix} d_1 \\ d_2 \\ d_3 \\ d_4 \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}
Channel coding
Mapping in the example x. The parity of the red, green, and blue circles are even.
Suppose we want to transmit this data (1011
) over a noisy communications channel. Specifically, a binary symmetric channel meaning that error corruption does not favor either zero or one (it is symmetric in causing errors). Furthermore, all source vectors are assumed to be equiprobable. We take the product of G and p, with entries modulo 2, to determine the transmitted codeword x:

\mathbf{x} = \mathbf{G} \mathbf{p} = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2 \\ 3 \\ 1 \\ 2 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix}
This means that 0110011
would be transmitted instead of transmitting 1011
.
Programmers concerned about multiplication should observe that each row of the result is the least significant bit of the Population Count of set bits resulting from the row and column being Bitwise ANDed together rather than multiplied.
In the diagram to the right, the 7 bits of the encoded word are inserted into their respective locations; from inspection it is clear that the parity of the red, green, and blue circles are even:

red circle has 2 1's

green circle has 2 1's

blue circle has 4 1's
What will be shown shortly is that if, during transmission, a bit is flipped then the parity of 2 or all 3 circles will be incorrect and the errored bit can be determined (even if one of the parity bits) by knowing that the parity of all three of these circles should be even.
Parity Check
If no error occurs during transmission, then the received codeword r is identical to the transmitted codeword x:

\mathbf{r} = \mathbf{x}
The receiver multiplies H and r to obtain the syndrome vector z, which indicates whether an error has occurred, and if so, for which codeword bit. Performing this multiplication (again, entries modulo 2):

\mathbf{z} = \mathbf{H}\mathbf{r} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2 \\ 4 \\ 2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}
Since the syndrome z is the null vector, the receiver can conclude that no error has occurred. This conclusion is based on the observation that when the data vector is multiplied by G, a change of basis occurs into a vector subspace that is the kernel of H. As long as nothing happens during transmission, r will remain in the kernel of H and the multiplication will yield the null vector.
Error correction
Otherwise, suppose a single bit error has occurred. Mathematically, we can write

\mathbf{r} = \mathbf{x} +\mathbf{e}_i
modulo 2, where e_{i} is the i_{th} unit vector, that is, a zero vector with a 1 in the i^{th}, counting from 1.

\mathbf{e}_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}
Thus the above expression signifies a single bit error in the i^{th} place.
Now, if we multiply this vector by H:

\mathbf{Hr} = \mathbf{H} \left( \mathbf{x}+\mathbf{e}_i \right) = \mathbf{Hx} + \mathbf{He}_i
Since x is the transmitted data, it is without error, and as a result, the product of H and x is zero. Thus

\mathbf{Hx} + \mathbf{He}_i = \mathbf{0} + \mathbf{He}_i = \mathbf{He}_i
Now, the product of H with the i^{th} standard basis vector picks out that column of H, we know the error occurs in the place where this column of H occurs.
For example, suppose we have introduced a bit error on bit #5

\mathbf{r} = \mathbf{x}+\mathbf{e}_5 = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix}
A bit error on bit 5 causes bad parity in the red and green circles
The diagram to the right shows the bit error (shown in blue text) and the bad parity created (shown in red text) in the red and green circles. The bit error can be detected by computing the parity of the red, green, and blue circles. If a bad parity is detected then the data bit that overlaps only the bad parity circles is the bit with the error. In the above example, the red & green circles have bad parity so the bit corresponding to the intersection of red & green but not blue indicates the errored bit.
Now,

\mathbf{z} = \mathbf{Hr} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}
which corresponds to the fifth column of H. Furthermore, the general algorithm used (see Hamming code#General algorithm) was intentional in its construction so that the syndrome of 101 corresponds to the binary value of 5, which indicates the fifth bit was corrupted. Thus, an error has been detected in bit 5, and can be corrected (simply flip or negate its value):

\mathbf{r}_{\text{corrected}} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ \overline{1} \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix}
This corrected received value indeed, now, matches the transmitted value x from above.
Decoding
Once the received vector has been determined to be errorfree or corrected if an error occurred (assuming only zero or one bit errors are possible) then the received data needs to be decoded back into the original 4 bits.
First, define a matrix R:

\mathbf{R} = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}
Then the received value, p_{r}, is equal to Rr. Using the running example from above

\mathbf{p_r} = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}
Multiple bit errors
A bit error on bit 4 & 5 are introduced (shown in blue text) with a bad parity only in the green circle (shown in red text)
It is not difficult to show that only single bit errors can be corrected using this scheme. Alternatively, Hamming codes can be used to detect single and double bit errors, by merely noting that the product of H is nonzero whenever errors have occurred. In the diagram to the right, bits 4 & 5 were flipped. This yields only one circle (green) with an invalid parity but the errors are not recoverable.
However, the Hamming (7,4) and similar Hamming codes cannot distinguish between singlebit errors and twobit errors. That is, twobit errors appear the same as onebit errors. If error correction is performed on a twobit error the result will be incorrect.
MATLAB implementation
MATLAB supports Hamming code. The command [H,G] = hammgen(3) will return the parity check and generator matrices respectively. Coding can be implemented as follows: uncodedWord = gf([0 1 0 0],1), codedWord = uncodedWord * G. Or as follows: codedWord = encode(uncodedWord,7,4,'hamming/binary').
The following code calculates the block error rate for Hamming(7,4) code with maximum likelihood detector in AWGN channel by MonteCarlo method:
% plots BLER (Block error rate) for Hamming74 code in complex AWGN channel
% with {+1,1} (BPSK) modulation
tStart_global = tic; % start ticker to count time consumed
c=clock; % get current time
strTime=sprintf('Start time Date Time: D%dH%dM%dS%d ',c(3),c(4),c(5),fix(c(6)) )
trialNumberFull = 10^5; % Trials for each snr point %for 1e5: 171.66 seconds, i.e. 0.047683 hours
snrdBVector = [10:1:10]; % Vector of SNR in dB
numberOfCodeWords = 2^4; % since 4 information bits in Hamming74 code
blockLength = 7; % since 7 bits is length of code of Hamming74 code
for codeWordNumber = 1: numberOfCodeWords % Create matrix which rows are all codeWords
uncoded = bitget(codeWordNumber  1, 4:1:1);
codedWordsArray(codeWordNumber, :) = 12*encode(uncoded,7,4,'hamming/binary');
end;
bler = zeros(1 , numel( snrdBVector ));
for counter = 1:numel( snrdBVector ) % Loop of SNR in dB
sigm=10^(snrdBVector(counter)/20); % noise power for complex noise
sigm = sigm / sqrt(2); % noise part for real/imaginary parts of noise
for trialNumber = 1: trialNumberFull
sentCodeWordNumber = randi([1 numberOfCodeWords]); %Random codeWord number
codedData = codedWordsArray(sentCodeWordNumber, :);% Get correspong sequence of {+1,1}
noiseVec = sigm * randn([ 1 blockLength]); %noise generatation
receivedData = codedData + noiseVec;
%MLD decoding
d = codedWordsArray  repmat(receivedData,numberOfCodeWords,1);
M = sum(d.*d,2);
[min_M,positionOfMin] = min(M); % codeWord number positionOfMin is result of MLD decoding
if ( positionOfMin ~= sentCodeWordNumber) % compare sent and decoded
bler(counter) = bler(counter) + 1; % if different add error count
end;
end;
bler(counter) = bler(counter) / trialNumberFull;
end;
c=clock; strTime=sprintf('End time Date Time: D%dH%dM%dS%d ',c(3),c(4),c(5),fix(c(6)) )
t=toc(tStart_global); calcTimeStr = sprintf('All time consumed %.2f seconds, i.e. %f hours\n', t, t/3600)
bler % Output to display
fname = sprintf('BLER in AWGN for Hamming74 code trials 1e%d', log10(trialNumberFull ) );
fp = fopen([fname '.csv'], 'wt');
fprintf(fp, ' SNR,'); fprintf(fp,' %.1f,', snrdBVector); fprintf(fp, '\n');
fprintf(fp, 'BLER,'); fprintf(fp,' %f,', bler); fclose(fp);
fig1=figure; semilogy(snrdBVector, bler);
title(fname); xlabel('SNR'); ylabel('BLER'); set(gca,'XTick',snrdBVector);
grid on; saveas(fig1,fname); saveas(fig1,fname,'jpg');
The result of calculations with 1e8 and 1e9 trials are the following:
SNR, 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0
BLER, 0.687724, 0.642019, 0.588242, 0.526217, 0.456242, 0.379902, 0.300021, 0.221384, 0.149660, 0.090407, 0.047446, 0.020810, 0.007305, 0.001962, 0.0003766, 0.00004826, 0.00000364, 1.55e7
All codewords
Since the source is only 4 bits then there are only 16 possible transmitted words. Included is the 8bit value if an extra parity bit is used (see Hamming(7,4) code with an additional parity bit). (The data bits are shown in blue; the parity bits are shown in red; and the extra parity bit shown in green.)
Data
({\color{blue}d_1}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})

Hamming(7,4)

Hamming(7,4) with extra parity bit (Hamming(8,4))

Transmitted
({\color{red}p_1}, {\color{red}p_2}, {\color{blue}d_1}, {\color{red}p_3}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})

Diagram

Transmitted
({\color{red}p_1}, {\color{red}p_2}, {\color{blue}d_1}, {\color{red}p_3}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4}, {\color{green}p_4})

Diagram

0000

0000000


00000000


1000

1110000


11100001


0100

1001100


10011001


1100

0111100


01111000


0010

0101010


01010101


1010

1011010


10110100


0110

1100110


11001100


1110

0010110


00101101


0001

1101001


11010010


1001

0011001


00110011


0101

0100101


01001011


1101

1010101


10101010


0011

1000011


10000111


1011

0110011


01100110


0111

0001111


00011110


1111

1111111


11111111


References

^ "History of Hamming Codes". Retrieved 20080403.
External Links

A programming problem about the Hamming Code(7,4)
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.