Készítette: Dr. Nagy Gábor Péter, SZTE Bolyai Intézet.
Á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.
Á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).
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 á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) |
0111001 0000110 0011010 0010101 0001000 0001011 0000000 |
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
|
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 [...] |
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 |
---|---|
|
|
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
|
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 [...] |
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 |
---|---|
|
|
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
|
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 [...] |
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 |
---|---|
|
|