Error Correcting Codes -- a Demonstration (switch to Hungarian)

By Gábor P. Nagy, University of Szeged Bolyai Institute.

Content

  1. The Goal
  2. The Alphabet
  3. The Message
  4. The Noise
  5. Encoding with the Repetion Code
  6. Decoding with the Repetion Code
  7. Encoding with the Hamming Code
  8. Decoding with the Hamming Code
  9. Encoding with the extended Golay Code
  10. Decoding with the extended Golay Code
  11. Conclusion

The Goal

An Alphabet is a finite set of symbols. We want to transmit a text message, written with the given alphabet, between digital devices.

During transmission, a noise causes that the sent and received sequence of symbols differ.

Our goal is to find methods which are able to correct high percentage of the occuring errors.

The Alphabet

[ aábcdeéfghiíjklmnoóöőpqrstuúüűvwxyzAÁBCDEÉFGHIÍJKLMNOÓÖŐPQRTSUÚÜŰVWXYZ
0123456789.,:;?!()+-*/=€$'******************************]

The number of admitted letters:  .

The Message

Plain text Digitalized text
John Lennon: Imagine

Imagine there's no heaven
It's easy if you try
No hell below us
Above us only sky
Imagine all the people
Living for today...

Imagine there's no countries
It isn't hard to do
Nothing to kill or die for
And no religion too
Imagine all the people
Living life in peace...

You may say I'm a dreamer
But I'm not the only one
I hope someday you'll join us
And the world will be as one

Imagine no possessions
I wonder if you can
No need for greed or hunger
A brotherhood of man
Imagine all the people
Sharing all the world...

You may say I'm a dreamer
But I'm not the only one
I hope someday you'll join us
And the world will live as one
 

Length of the plain text message:  . Bit length of the digitalized text:  .

The Noise

Input the error probability per bit in percent: %

Ratio of bits changed by the noise: 0%. Ratio of letters changed by the noise: 0%.

Can you explain this?

Noisy plain text Noisy digitalized text
 
 

Encoding with Repetition Code

The trick: Repeat every bit three times!

The price: You have to transmit a three times longer binary sequence.

The parameters of the repetition code
Length of the code: 0
Dimension of the code: 0
The generator matrix:
1
1
1

Digitalized text Digitalized text encoded with repetition code
 
 

Decoding with Repetition Code

Ratio of bits changed by the noise: 0%. Ratio of letters changed by the noise: 0%.

Noisy encoded digital text Error corrected noisy encoded text
 

 


Encoding with the Hamming Code

Can we do that better? YES! Use the Hamming code.

The price: You have to transmit a 7/4-times longer binary sequence.

The parameters of the repetition code
Length of the code: 0
Dimension of the code: 0
The generator matrix:
1000
0100
0010
0001
1101
1011
0111

Digitalized text Digitalized text encoded with Hamming code
 
 

Decoding with the Hamming Code

Ratio of bits changed by the noise: 0%. Ratio of letters changed by the noise: 0%.

While the threefold repetition code corrects 1 error per codeword (of length 3), the Golay code corrects 1 errors per codewords (of length 7).

Noisy encoded digital text Error corrected noisy encoded text
 

 


Encoding with the extended Golay Code

Can we do that better? YES! Use the (extended) Golay code.

The price: You have to transmit a twice longer binary sequence.

The parameters of the repetition code
Length of the code: 0
Dimension of the code: 0
The generator matrix:
100000000000
010000000000
101000000000
010100000000
101010000000
110101000000
111010100000
011101010000
001110101000
000111010100
100011101010
110001110101
011000111010
001100011101
000110001110
000011000111
000001100011
000000110001
000000011000
000000001100
000000000110
000000000011
000000000001
111111111111

Digitalized text Digitalized text encoded with extended Golay code
 
 

Decoding with the extended Golay Code

Ratio of bits changed by the noise: 0%. Ratio of letters changed by the noise: 0%.

While the threefold repetition code corrects 1 error per codeword (of length 3), the Golay code corrects 3 errors per codewords (of length 24).

Noisy encoded digital text Error corrected noisy encoded text
 

 

Conclusion