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 .
Sometimes, a third parameter is added for the minimum distance, which for Hamming Codes is at least 3.
The number of parity bits needed is defined by .
Example:
Perfect Hamming Code
In order to encode and decode we need two matrices (definition in systematic form):
The construction starts with . We have to follow some rules in order to create an optimal :
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 non-systematic approach we have to bring the matrix to standard from.
For this, we use row reduction to convert the matrix into a matrix where the first part forms an identity matrix.
The final form is called reduced row-echelon form (RREF).
Follow these steps until you receive the RREF form in order to convert your matrix:
When your matrix is in standard form you can transform it into .
For this, cut the identity matrix and transpose the part left.
Then, add a new identity matrix at the end of your matrix.
If you need for your calculation you can derive it from .
For this, extract the parity columns of (the so called 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 compared to ).
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 .
To update your matrix you add the next matching column at the end.
Perform the elementary row operations in order to create and .
For (and as well), we fill the fourth row with all for standard Hamming Codes.
Parity examples
| Binary word | # Bits set | Sequence with parity bit appended |
|---|---|---|
| 1 | (odd) | |
| 2 | (odd) | |
| 3 | (even) | |
| 4 | (even) |
Briefly, the process of encoding is done via multiplication of the input vector with the generator matrix .
Apply modulo 2 to all entries in the resulting vector to get the final codeword .
Again very briefly, the process of decoding is done via multiplication of the codeword vector with the parity-check matrix .
Apply modulo 2 to all entries in the resulting vector to get the syndrome vector .
If the syndrome is all 0 no error occurred.
In this case just remove all parity bits from in order to get the original input vector (positions depend on the scheme used).
Otherwise, see the next sub-paragraph on how to detect and correct errors.
Given the syndrome was not 0 we have to look up the corresponding column in .
When a match is found we know which position in is flipped and needs to be corrected.
When working with extended Hamming Code, we have several possibilities for further proceeding on errors.
$H$) and continue with the execution.Error pattern in extended Hamming codes
| # 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 |