• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Error correcting Codes

Contents

  • Introduction
  • Hamming codes
This blogpost is strongly related to this germand PDF of a pupils' competition in which I have participated in 2008.

Today, we have a lot of data that is stored or transferred in a binary way. Once in a while an error occurs and single bits get switched from 0 to 1 or the other way around. Coding theory tries to find algorithms with which you can detect and correct errors.

Introduction

To keep it simple, we make a small example. We have

\begin{align} \{A, B, C, D, E, F, G, H\} &= \mathcal{F}_3\\ \{A', B', C', D', E', F', G', H'\} &\subsetneq \mathcal{F}_8 \end{align}
\begin{align} c_3 = \{&(1,1,1,1,1,1),\\ &(0,0,0,0,1,1),\\ &(0,0,1,1,0,0),\\ &(0,1,0,1,0,1),\\ &(0,1,1,0,1,0),\\ &(1,0,0,1,1,0),\\ &(1,0,1,0,0,1),\\ &(1,1,0,0,0,0)\} \end{align}

Hamming codes

Hamming codes are a family of \((2^k - 1, 2^{(2^k -1)-k}, 3), \quad k \geq 2\) codes. This means, every hamming code can only correct one error.

The idea behind Hamming codes is to save in one bit if the number of a fixed set of positions of the message is even or odd. This is called parity and done with XOR. The parity-bit is saved at the end of the message (or, just another point of view: the positions that are powers of two (1, 2, 4, 8, ...) of each message are only parity bits. This are obviously \(\lceil \log_2(\text{length of code}) \rceil = \lceil \log(2^k - 1) \rceil = k\)).

Wikipedia has a really nice image for that:

Parity-bits and data bits in a Hamming codeword
Parity-bits and data bits in a Hamming codeword

Now, how are the parity-bits calculated? Well, think of each messages as a vector in \(\{0,1\}^{(2^k - 1) - k}\). Then you define a matrix \(G \in \{0,1\}^{2^k - 1} \times \{0,1\}^{(2^k - 1) - k}\). Now you can get the codewords \(c\) by multiplying the datawords \(d\) (messages) with \(G\): \(c = G \cdot d\). This is the reason why Hamming-Codes are called "linear codes". They can be obtained by a linear function.

How do I get the generator-matrix \(G\)? I don't know it and my internet searches didn't reveal any solution. Do you know one?


Published

Okt 26, 2012
by Martin Thoma

Category

My bits and bytes

Tags

  • coding theory 1
  • mathematics 59

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor