When transmitting bit sequences there’s always a chance of errors occurring. For this we have Hamming Codes, which help you to detect faulty bits and recover the original sequence.
You will learn about a customized extended linear Hamming Code that is capable of both error detection and error correction.
This is only a very short and brief introduction into the topic.
The notation of Hamming Codes consists of two parameters $(n, k)$
.
Sometimes, a third parameter $d$
is added for the minimum distance, which for Hamming Codes is at least 3.
The number of parity bits needed is defined by $r$
.
$n$
 Total length of encoded word
$k$
 Length of source word
$d$
 Minimum distance between codewords
$r$
 Number of parity bits in the codeword
Example:
Perfect Hamming Code $(7, 4, 3)$
$G$
 Systematic Generator Matrix
$G'$
 NonSystematic Generator Matrix
$H$
 Systematic ParityCheck Matrix
$H'$
 NonSystematic ParityCheck Matrix
In order to encode and decode we need two matrices (definition in systematic form):
$G := \left(\begin{matrix}I_{k}\,\,A^{T}\end{matrix}\right)$
 The generator matrix
$H := \left(\begin{matrix}A\,\,I_{nk}\end{matrix}\right)$
 The paritycheck matrix
The construction starts with $G'$
. We have to follow some rules in order to create an optimal $G'$
:
Column with all zero is skipped
Every column contains an odd number of 1’s
Total number of 1’s reaches the minimum
Only distinct columns, no duplicates
When creating the matrix add bigger numbers on the left side so that the smallest one is on the right side.
Depending on using the systematic or nonsystematic approach we have to bring the $G'$
matrix to standard from.
For this, we use row reduction to convert the matrix into a matrix where the first $m\times m$
part forms an identity matrix.
The final form is called reduced rowechelon form (RREF).
Follow these steps until you receive the RREF form in order to convert your $G'$
matrix:
Perform elementary row operations to yield a 1 in the first row, first column.
Create 0 in all the rows of the first column except the first row by adding the first row to each other row.
Perform elementary row operations to yield a 1 in the second row, second column.
Create 0 in all the rows of the second column except the first row by adding the second row to each other row.
…
When your $G'$
matrix is in standard form $G$
you can transform it into $H$
.
For this, cut the identity matrix and transpose the $A$
part left.
Then, add a new identity matrix at the end of your $H$
matrix.
If you need $H'$
for your calculation you can derive it from $G'$
.
For this, extract the parity columns of $G'$
(the so called $A$
part) and transpose it.
Next, add the identity matrix from left to right and add the parity columns at the correct position (at the positions of the $d$
compared to $G'$
).
Hamming Codes can, by default, only detect or correct one error.
In order to achieve both we can add an extra parity bit, the overall parity bit.
With this we are now able to correct a single error and detect double errors.
These codes are called Single Error Correction Double Error Detection codes.
Example:
The standard Hamming Code extends to $(8, 4)$
.
To update your $G'$
matrix you add the next matching column at the end.
Perform the elementary row operations in order to create $G$
and $H$
.
For $H$
(and $H'$
as well), we fill the fourth row with all $1$
for standard Hamming Codes.
Binary word  # Bits set  Sequence with parity bit appended 

 1 

 2 

 3 

 4 

Briefly, the process of encoding is done via multiplication of the input vector $\overrightarrow{a}$
with the generator matrix $G$
.
Apply modulo 2 to all entries in the resulting vector to get the final codeword $\overrightarrow{x}$
.
Formular: $\overrightarrow{x} = (\overrightarrow{a}\cdot G)\,mod\,2$
Again very briefly, the process of decoding is done via multiplication of the codeword vector $\overrightarrow{x}$
with the paritycheck matrix $H$
.
Apply modulo 2 to all entries in the resulting vector to get the syndrome vector $\overrightarrow{z}$
.
Formular: $\overrightarrow{z} = (H\cdot \overrightarrow{x})\,mod\,2$
If the syndrome $\overrightarrow{z}$
is all 0 no error occurred.
In this case just remove all parity bits from $\overrightarrow{x}$
in order to get the original input vector $\overrightarrow{a}$
(positions depend on the scheme used).
Otherwise, see the next subparagraph on how to detect and correct errors.
Given the syndrome $\overrightarrow{z}$
was not 0 we have to look up the corresponding column in $H$
.
When a match is found we know which position in $\overrightarrow{x}$
is flipped and needs to be corrected.
When working with extended Hamming Code, we have several possibilities for further proceeding on errors.
If it was a single error, simply flip the bit in error (position from $H$
) and continue with the execution.
If however the error could not be corrected, we possibly have to try again.
If it is still uncorrectable we have multiple errors.
# Errors  Overall parity  Syndrome  Error description 

0  0 (even)  = 0  no error 
1  1 (odd)  = 0  additional parity bit is in error 
1  1 (odd)  != 0  single error 
> 1  1 (odd)  != 0 and not in  multiple errors 
> 1  0 (even)  != 0  multiple errors 
D. Schönfeld, H. Klimant, R. Piotraschke. Informations und Kodierungstheorie. 4. Auflage, Springer Vieweg, Wiesbaden 2012, ISBN 9783834806475