6. fejezet - Csatornakódolás

6.1. 6.1. Hibajavítás, kódtávolság

Szimmetrikus bináris csatorna esete, azaz a csatorna átviteli mátrixa legyen a következő:

6.1. ábra - Bináris szimmetrikus csatorna

Bináris szimmetrikus csatorna

Probléma: Milyen feltételek mellett és hogyan oldható meg a csatornában az átvitelnél keletkezett hibák jelzése és javítása?

6.1. Példa. A bit háromszorozás módszere (Commodore-64 kazettás egység):

Ha a dekódolás a több azonos bit szerint történik, akkor a legfeljebb két hiba jelezhető és egy hiba javítható.

Ha akkor a helyes átvitel (javítással) valószínűsége

6.1. Definíció. Az üzenetszó ( bit) kódszó ( bit) átalakítást (kódolást) kódnak nevezzük.

6.2. Megjegyzés. Ez egy blokkos kódolás.

Legyen és adott a következő két művelet:

a „kizáró vagy” művelet (jele: ) vagy másképpen a modulo 2 összeadás (jele: ), és a hagyományos szorzás a másik művelet.

Ekkor és Abel-csoport. Továbbá, test. Értelmezzük az esetén az előbbi műveleteket bitenként, ekkor vektortér az test felett.

6.3. Definíció. Legyen jelentse az egyes bitek számát.

Ekkor norma.

6.4. Definíció. A mennyiséget Hamming-féle távolságnak nevezzük.

6.5. Lemma. A Hamming-féle távolság kielégíti a távolság tulajdonságait.

6.6. Lemma. A Hamming-féle távolság invariáns az eltolásra, azaz

Bizonyítás.

6.7. Definíció. A kódszavakból álló kód esetén a kódszavak távolságai közül a minimálisat kódtávolságnak nevezzük, azaz a kódtávolságra

6.8. Megjegyzés. Legyen a csatornaábécé Jelölések: (az eredeti üzenet), (az -nak megfelelő csatorna kódszó), (a -nek megfelelő csatornán áthaladt jelsorozat, azaz az átvitelnél keletkezik). Ekkor

Ha a eredetijének azt a kódszót tekintjük, amelyre a feltételes valószínűség a lehető legnagyobb, azt maximum likelihood kódolásnak nevezzük.

Tegyük fel, hogy akkor

maximális, ha minimális.

Ez azt jelenti, hogy bináris szimmetrikus csatorna esetén a minimális távolságon alapuló dekódolás (javítás) megegyezik a maximum likelihood kódolás alapján történővel.

6.9. Tétel. Legyen egy vett szóban a hibák száma legfeljebb Tetszőleges kódszó esetén a legfeljebb számú hiba a minimális távolságon alapuló hibajavítás módszerével akkor és csak akkor javítható, ha a kódtávolság

Bizonyítás. Elégségesség: Ha és ( a hibavektor), akkor

bármely esetén, ha

azaz

Szükségesség: Ha és minimális távolságon alapuló dekódolása mindig helyes eredményre vezet, akkor

azaz a -ből torzult szó a -től legalább távolságra van. Mivel azt akarjuk, hogy a dekódolás -be történjen, ezért