Basics - Hamming Code

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.

Info

This is only a very short and brief introduction into the topic.

Notation

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

Info

Example:
Perfect Hamming Code $(7, 4, 3)$

Some definitions

$G$ - Systematic Generator Matrix
$G'$ - Non-Systematic Generator Matrix
$H$ - Systematic Parity-Check Matrix
$H'$ - Non-Systematic Parity-Check Matrix

Construction

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_{n-k}\end{matrix}\right)$ - The parity-check 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

Tip

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 $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 row-echelon form (RREF).

Systematic

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.

Non-Systematic

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'$ ).

Extended Hamming Code SEC-DED

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.

Info

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.

Parity examples

Binary word	# Bits set	Sequence with parity bit appended
$(0010)$	1	$(0010\textbf{0})$ (odd)
$(1010)$	2	$(1010\textbf{1})$ (odd)
$(1110)$	3	$(1110\textbf{1})$ (even)
$(1111)$	4	$(1111\textbf{0})$ (even)

Encoding

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$

Decoding

Again very briefly, the process of decoding is done via multiplication of the codeword vector $\overrightarrow{x}$ with the parity-check 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 sub-paragraph on how to detect and correct errors.

Error detection and correction

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.

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 $H$	multiple errors
> 1	0 (even)	!= 0	multiple errors

References

Literature

D. Schönfeld, H. Klimant, R. Piotraschke. Informations- und Kodierungstheorie. 4. Auflage, Springer Vieweg, Wiesbaden 2012, ISBN 978-3-8348-0647-5