Hibajavító kódok -- bemutató

Készítette: Dr. Nagy Gábor Péter, SZTE Bolyai Intézet.

Összefoglaló

  1. A feladat
  2. Az ábécé
  3. Az üzenet
  4. A zaj
  5. Kódolás ismétlő kóddal
  6. Dekódolás ismétlő kóddal
  7. Kódolás a Golay-kóddal
  8. Dekódolás a Golay-kóddal
  9. Konklúzió

A feladat

Ábécének nevezzük írásjeleknek egy véges halmazát. A feladatunk az, hogy egy adott ábécé segítségével összeállított szöveges üzenetet továbbítsunk digitális eszközök között.

A továbbítás során a külső zaj hatására a küldött és a fogadott jelsorozat különbözik.

A cél olyan eljárás kidolgozása, ami a fellépő hibákat minél nagyobb számban képes kijavítani.

Az ábécé

Ábécéként rögzítsük írásjeleknek az alábbi sorozatát:

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

Ez az ábécé 128 írásjelet tartalmaz, beleértve a szóközt (első karakter) és a sortörés jelét is (nagy Z után).

Az üzenet

Mivel a szöveget digitális eszközök között továbbítjuk, át kell alakítani 0-k és 1-ek sorozatává.

Ehhez minden írásjelnek megfeleltetünk egy 0 és 127 közötti számot, majd vesszük ennek a felírását 2-es számrendszerben.

Sima szöveg Digitalizált szöveg 
Petőfi Sándor: János vitéz (részlet)

Tüzesen süt le a nyári nap sugára
Az ég tetejéről a juhászbojtárra.
Fölösleges dolog sütnie oly nagyon,
A juhásznak úgyis nagy melege vagyon.

Szerelem tüze ég fiatal szivében,
Ugy legelteti a nyájt a faluvégen.
Faluvégen nyája mig szerte legelész,
Ő addig subáján a fűben heverész.

Tenger virág nyílik tarkán körülötte,
De ő a virágra szemét nem vetette;
Egy kőhajtásnyira foly tőle a patak,
Bámuló szemei odatapadtanak.

De nem ám a patak csillámló habjára,
Hanem a patakban egy szőke kislyányra,
A szőke kislyánynak karcsu termetére,
Szép hosszú hajára, gömbölyű keblére.

Mert a pázsit fölött heverésző juhász
Kukoricza Jancsi, ki is lehetne más?
Ki pedig a vízben a ruhát tisztázza,
Iluska az, Jancsi szivének gyöngyháza.

"Szivemnek gyöngyháza, lelkem Iluskája!"
Kukoricza Jancsi így szólott hozzája:
"Pillants ide, hiszen ezen a világon
Csak te vagy énnekem minden mulatságom.

Vesd reám sugarát kökényszemeidnek,
Gyere ki a vízből, hadd öleljelek meg;
Gyere ki a partra csak egy pillanatra,
Rácsókolom lelkem piros ajakadra!"

0111001 0000110 0011010 0010101 0001000 0001011 0000000 
0111101 0000010 0010001 0000101 0010010 0011000 1010100 
0000000 0110000 0000010 0010001 0010010 0011001 0000000 
0011111 0001011 0011010 0000111 0100011 0000000 1011000 
0011000 0000111 0011001 0100011 0001111 0000110 0011010 
1011001 1000111 1000111 0111100 0011101 0100011 0000110 
0011001 0000110 0010001 0000000 0011001 0011101 0011010 
0000000 0001111 0000110 0000000 0000001 0000000 0010001 
0100010 0000010 0011000 0001011 0000000 0010001 0000001 
0010110 0000000 0011001 0011011 0001001 0000010 0011000 
0000001 1000111 0100100 0100011 0000000 0000111 0001001 
0000000 0011010 0000110 0011010 0000110 0001101 0000111 
0011000 0010101 0001111 0000000 0000001 0000000 0001101 
0011011 0001010 0000010 0011001 0100011 0000011 0010010 
0001101 0011010 0000010 0011000 0011000 0000001 1010010 
1000111 0101011 0010100 0001111 0010100 0011001 0001111 
0000110 0001001 0000110 0011001 0000000 0000101 0010010 
0001111 0010010 0001001 0000000 0011001 0011101 0011010 
0010001 0001011 0000110 0000000 0010010 0001111 0100010 
0000000 0010001 0000001 0001001 0100010 0010010 0010001 
1010011 1000111 0100100 0000000 0001101 0011011 0001010 
0000010 0011001 0100011 0010001 0000001 0001110 0000000 
0011100 0001001 0100010 0001011 0011001 0000000 0010001 
0000001 0001001 0100010 0000000 0010000 0000110 0001111 
0000110 0001001 0000110 0000000 0011111 0000001 0001001 
[...]

A sima szöveg 1073 karakterből áll.

A digitalizált szöveg 7511 bitet (0/1 karaktert) tartalmaz.

A zaj

Annak a százalékos valószínűsége, hogy egy bitet a zaj megváltoztat, legyen p=%.

A zaj áltak átírt bitek aránya: 2.94%. A zaj által elrontott írásjelek aránya: 18.64%.

Meg tudjuk ezt magyarázni?

Zajos sima szöveg Zajos digitalizált szöveg
Petőfi Sáődor* János /btéé (résáéZt)
7Güzege9 süt ie a nyeri nap ü-gáraéAz dgÜtetejérőlma juhánzboítárfd87FölösÍeges dolog sütnie óly nagyonW
A juhásznakmúgBbs nagy Jekese Ragyon.

SzefelZmÜoüze ég fiatal sbivqbeó,
UgLÜlegelteti aáöyájt a fnluvégen.
Faluv
gen nyája 8ig szcrte legelész,
Ő addig ssbhján a fűben reve(dsz.

Tengkr viŐág nyílik tarkán körül?tte,
fe ő b virogra szemét nem vetehQe;
*gyákdhajtásnyira goly +őle a patnk,
éámuln szemei oantap dtdagk.
!De Ker ámÜa patah csiilámlM habjárn**Hanem a paűa6bbn egy szőke ki)lyányra,Y*Üszőke kislyánLaak IarcguftermetérB,
*zéq hosszú hajbra* gömb:lyű kpaléreo

Mkrt a pázsit fölöttmhZverésző jthász
KuIoQicya JnscPi, h3 ir lehetne más?
Kiapeabs vízben a ruiyt tirCtázza.
IluskŰcaz
Jandsi szivdnek gyrngyheCg.
W"Szivennek gwönEyh zb, lelűen Ilusíája!"
Kuűor-dza Jancsi így sF-lmtL hoyzájx:
"Pillants ije, hiszenmezen a világom
Bsak te vgg" ennekes minden mulatgá5or*

Vesd rcám signrátmkőkényüzdmeidőék!
Gyere ki afvíMbnl, haéd öleljelekÜme1/
íwere ki a partra csak ejy pillanatra,
RáysókLlo8alelkem ÓiŐoP aHxkadra!"
0111001 0000110 0011010 0010101 0001000 0001011 0000000
0111101 0000010 0010101 0000101 0010010 0011000 1110100
0000000 0110000 0000010 0010001 0010010 0011001 0000000
1011101 0000011 0011010 0000111 0000111 0000000 1011000
0011000 0000111 0011001 0000010 0000111 1000110 0011010
1011001 1000111 1001111 0101100 0011101 0100011 0000110
0001001 0000110 1010001 0000000 0011001 0011101 0011010
0000000 0001011 0000110 0000000 0000001 0000000 0010001
0100010 0000110 0011000 0001011 0000000 0010001 0000001
0010110 0000000 0011101 1011011 0001001 0000010 0011000
0000001 0000111 0100100 0100011 0000000 0000101 0001001
1000000 0011010 0000110 0011010 0000110 0001101 0000111
0011000 0010101 0001111 0010000 0000001 0000000 0001101
0011011 0001010 0000010 0010001 0100011 0000011 0010010
0001100 0011010 0000010 0011000 0001000 0000101 1010000
1001111 0101011 0010100 0001111 0010100 0011001 0101111
0000110 0001001 0000110 0011001 0000000 0000101 0010010
0001111 0010010 0001001 0000000 0011001 0011101 0011010
0010001 0001011 0000110 0000000 0010011 0001111 0100010
0000000 0010001 0000001 0001001 0100010 0010010 0010001
1000011 1000111 0100100 0000000 0001101 0011011 0001010
0000010 0011001 0100011 0010001 0000001 0001110 0010000
0011100 0001001 0100110 0000011 0011001 0000000 0010001
0000001 0001001 0100010 0000000 0110000 0000110 0001110
0000110 0011001 0000110 0000000 0111011 0000001 0001001
[...]

Kódolás ismétlő kóddal

Az első ötlet az ismétlő kód: Ismételjünk meg minden bitet háromszor!

Az ár: Háromszor olyan hosszú bináris jelsorozatot kell átvinni.

Az ismétlő kód paraméterei
A kód hossza: 3
A kód dimenziója: 1
A generátor mátrix:
1
1
1

Digitalizált szöveg Az ismétlő kóddal kódolt digitalizált szöveg 
01110010 00011000 11010001 01010001 00000010 11000000 
00111101 00000100 01000100 00101001 00100011 00010101 
00000000 00110000 00000100 01000100 10010001 10010000 
00000111 11000101 10011010 00001110 10001100 00000101 
10000011 00000001 11001100 10100011 00011110 00011000 
11010101 10011000 11110001 11011110 00011101 01000110 
00011000 11001000 01100010 00100000 00001100 10011101 
00110100 00000000 01111000 01100000 00000000 01000000 
00010001 01000100 00001000 11000000 10110000 00000100 
01000000 10010110 00000000 01100100 11011000 10010000 
01000110 00000000 11000111 01001000 10001100 00000000 
01110001 00100000 00001101 00000110 00110100 00011000 
01101000 01110011 00000101 01000111 10000000 00000010 
00000000 01101001 10110001 01000000 10001100 10100011 
00000110 01001000 01101001 10100000 01000110 00001100 
[...]

000111111111000000111000 000000000111111000000000 
111111000111000000000111 000111000111000000000111 
000000000000000000111000 111111000000000000000000 
000000111111111111000111 000000000000000111000000 
000111000000000111000000 000000111000111000000111 
000000111000000000111111 000000000111000111000111 
000000000000000000000000 000000111111000000000000 
000000000000000111000000 000111000000000111000000 
111000000111000000000111 111000000111000000000000 
000000000000000111111111 111111000000000111000111 
111000000111111000111000 000000000000111111111000 
111000000000111111000000 000000000000000111000111 
111000000000000000111111 000000000000000000000111 
111111000000111111000000 111000111000000000111111 
000000000111111111111000 000000000111111000000000 
[...]

Dekódolás ismétlő kóddal

A zaj áltak átírt bitek aránya: 0%. A zaj által elrontott írásjelek aránya: 0%.

A zajos kódolt digitalizált szöveg A zajos kódolt szöveg hibajavítás után
 

 

Encoding with the Hamming Code

Can we do 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: 7
Dimension of the code: 4
The generator matrix:
1000
0100
0010
0001
1101
1011
0111

Digitalized text Digitalized text encoded with Hamming code 
0111 0010 0001 1000 1101 0001 0101 0001 0000 0010 
1100 0000 0011 1101 0000 0100 0100 0100 0010 1001 
0010 0011 0001 0101 0000 0000 0011 0000 0000 0100 
0100 0100 1001 0001 1001 0000 0000 0111 1100 0101 
1001 1010 0000 1110 1000 1100 0000 0101 1000 0011 
0000 0001 1100 1100 1010 0011 0001 1110 0001 1000 
1101 0101 1001 1000 1111 0001 1101 1110 0001 1101 
0100 0110 0001 1000 1100 1000 0110 0010 0010 0000 
0000 1100 1001 1101 0011 0100 0000 0000 0111 1000 
0110 0000 0000 0000 0100 0000 0001 0001 0100 0100 
0000 1000 1100 0000 1011 0000 0000 0100 0100 0000 
1001 0110 0000 0000 0110 0100 1101 1000 1001 0000 
0100 0110 0000 0000 1100 0111 0100 1000 1000 1100 
0000 0000 0111 0001 0010 0000 0000 1101 0000 0110 
0011 0100 0001 1000 0110 1000 0111 0011 0000 0101 
[...]

0111001 0010011 0001111 1000110 1101100 0001111 
0101010 0001111 0000000 0010011 1100011 0000000 
0011100 1101100 0000000 0100101 0100101 0100101 
0010011 1001001 0010011 0011100 0001111 0101010 
0000000 0000000 0011100 0000000 0000000 0100101 
0100101 0100101 1001001 0001111 1001001 0000000 
0000000 0111001 1100011 0101010 1001001 1010101 
0000000 1110000 1000110 1100011 0000000 0101010 
1000110 0011100 0000000 0001111 1100011 1100011 
1010101 0011100 0001111 1110000 0001111 1000110 
1101100 0101010 1001001 1000110 1111111 0001111 
1101100 1110000 0001111 1101100 0100101 0110110 
0001111 1000110 1100011 1000110 0110110 0010011 
0010011 0000000 0000000 1100011 1001001 1101100 
0011100 0100101 0000000 0000000 0111001 1000110 
[...]

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 Hamming code corrects 1 errors per codewords (of length 7).

Noisy encoded digital text Error corrected noisy encoded text
 

 

Kódolás a Golay-kóddal

Csinálhatjuk ennél jobban is? IGEN! Használjuk a (kiterjesztett) Golay-kódot.

Az ár: Kétszer olyan hosszú bináris jelsorozatot kell átvinni.

A Golay-kód paraméterei
A kód hossza: 24
A kód dimenziója: 12
A generátor mátrix:
100000000000
010000000000
101000000000
010100000000
101010000000
110101000000
111010100000
011101010000
001110101000
000111010100
100011101010
110001110101
011000111010
001100011101
000110001110
000011000111
000001100011
000000110001
000000011000
000000001100
000000000110
000000000011
000000000001
111111111111

Digitalizált szöveg A Golay-kóddal kódolt digitalizált szöveg 
011100100001 100011010001 010100010000 001011000000 
001111010000 010001000100 001010010010 001100010101 
000000000011 000000000100 010001001001 000110010000 
000001111100 010110011010 000011101000 110000000101 
100000110000 000111001100 101000110001 111000011000 
110101011001 100011110001 110111100001 110101000110 
000110001100 100001100010 001000000000 110010011101 
001101000000 000001111000 011000000000 000001000000 
000100010100 010000001000 110000001011 000000000100 
010000001001 011000000000 011001001101 100010010000 
010001100000 000011000111 010010001000 110000000000 
011100010010 000000001101 000001100011 010000011000 
011010000111 001100000101 010001111000 000000000010 
000000000110 100110110001 010000001000 110010100011 
000001100100 100001101001 101000000100 011000001100 
[...]

011010111111111100000111 101000001110101100100111 
010000111000001001100001 001001000001111010000001 
001100001000010011100001 010100100011111010011001 
001000000001100011101100 001111110101010010111111 
000000000011111001001010 000000000101011100011001 
010100101101001001110110 000111100111100101100001 
000001100110110000001001 010010011110010011011100 
000011011000010001110000 111110010110101011011110 
101011011101010010100001 000110101010110110101001 
100001100100110101100111 110100110101011001010001 
111010000111100000010111 101000100101001111100110 
111000011101000110000111 111010011110001100010100 
000111111101110000101000 101010011101001011001100 
001010111000110000000001 111100100111101110001111 
001110110011101110000001 000001100011101100010000 
[...]

Dekódolás a Golay-kóddal

A zaj áltak átírt bitek aránya: 0%. A zaj által elrontott írásjelek aránya: 0%.

Míg a háromszoros ismétlő kód (3 bites) kódszavanként 1 hibát tud kijavítani, a Golay-kód (24 bites) kódszavanként 3 hibát tud javítani.

A zajos kódolt digitalizált szöveg A zajos kódolt szöveg hibajavítás után
 

 

Konklúzió