7.1. ábra. Hibajavítás a hírközlési láncban
Tekintsünk egy digitális hírközlési csatornát, amely a bemenetén megjelenő bináris (0–1 értékű) sorozatokat továbbítja. Ez a csatorna a modulátor, az átviteli közeg és a demodulátor együttese. A modulátor a bemenetén megjelenő 0, ill. 1 értékeket az átviteli közegen továbbítható jelpárba képezi le. Az átvitel során ezek a jelek torzulnak, zajjal terhelődnek. A demodulátor a vett jelek végtelen méretű halmazát – egy döntési szabály alkalmazásával – ismét 0, ill. 1 értékre képezi. Ezen döntés azonban nem hibamentes. Az átviteli hibavalószínűség megfelelő értékre csökkentésének általában nem járható útja az adási teljesítmény növelése. Továbbá, mivel az információforrásnak időegységenként adott számú bitet kell továbbítania, ezért a jelidőket sem növelhetjük meg. Szerencsére van egy módszer, amellyel hibázó csatorna esetén is elérhetjük a tervezett átviteli hiba-valószínűséget: ez a hibakorlátozó kódolás.
A hibakorlátozó kódolás két feladata a hibajelzés és a hibajavítás. A hibajelzés folyamata az, hogy a vevő a hibajelző kód segítségével detektálja a vételi hibát, majd értesíti az adót egy visszairányú csatornán a detektált vételi hibáról, amely erre legtöbbször újraadást kezdeményez. Hibajavításon azt értjük, hogy a hibajavító kódolás alapján a vevő alkalmassá válik bizonyos meghibásodási esetek javítására. Gyakoriak a hibrid kódolási eljárások, amelynél a vevő először hibajavítást végez, majd a javítást ellenőrzi hibadetektálással.
7.1. ábra. Hibajavítás a hírközlési láncban
A forrás k hosszúságú
Azt mondjuk, hogy a csatorna az m-edik pozícióban hibázott, ha vm ≠ cm.
Jelölje t az összes ilyen hibázások számát c átvitelekor.
Általában, tetszőleges c és v szavak Hamming-távolsága – d(c,v) – azon pozíciók száma, amelyben azok különböznek.
Tehát
Kódon (blokk-kódon) n hosszúságú vektorok C részhalmazát értjük, amelynek mérete k hosszúságú bináris üzenetek esetén 2k. Gyakran C(n,k) alakban jelöljük a kódot, ahol n és k a kód paraméterei. A kód elemei a kódszavak. A kódolás kölcsönösen egyértelmű leképezés, amely az egyes üzeneteket kódszavakra képezi le, tehát különböző üzenetek különböző kódszavakra képződnek le.
Dekódoláson ebben a fejezetben két lépés egymás utáni végrehajtását értjük. Először a v vett szót egy dekódolási döntési szabály alapján a c' dekódolt kódszóba képezzük le, majd a kódolás inverzének megfelelően ehhez a c' kódszóhoz egy u' üzenetet rendelünk.
A leggyakrabban alkalmazott dekódolási döntési szabály az, hogy a v vett szóhoz Hamming-távolságban legközelebbi c' kódszót kell választani, azaz
Ez a döntési szabály általános csatorna esetén szuboptimális a dekódolási hibavalószínűség minimalizálását illetően. Akkor optimális, ha a csatorna emlékezet nélküli, bináris és szimmetrikus, azaz, ha az egyes kódszóbitek meghibásodása függetlenül, azonos valószínűséggel történik.
Az eddigiekből következik, hogy két fő feladatot kell elvégezni a hibajavító kódolással kapcsolatban. Konstruálni kell olyan kódot, amelyben a kódszavak közötti Hamming-távolság a lehető legnagyobb. Ha adott egy kód, olyan dekódolási döntési szabályt kell konstruálni, hogy a vett szóhoz minimális távolságra levő kódszó megtalálásához ne kelljen végigvizsgálni az összes kódszót. Kisméretű kódok esetén a végigvizsgálás még lehetséges. Ha a kódszóhossz, azaz a kód n paramétere viszonylag kicsi (pl. n ≤ 10), akkor ún. táblázatos dekódolást végezhetünk. A táblázatban az összes lehetséges vett szóhoz megadjuk a dekódolt kódszót, valamint az ahhoz tartozó üzenetet. (Gyakorlati alkalmazásokban természetesen csak a dekódolt üzenetet adjuk meg.) Az eljárás szemléltetéséül tekintsük az 7.1. példát.
7.1. példa.
Tekintsük az alábbi kódolás szerinti C(5,2) kódot:
| u | c |
| 0 0 | 0 0 0 0 0 |
| 0 1 | 0 1 1 0 1 |
| 1 0 | 1 0 1 1 0 |
| 1 1 | 1 1 0 1 1 |
| v | c' | u' |
| 0 0 0 0 0 | 0 0 0 0 0 | 0 0 |
| 1 0 0 0 0 | 0 0 0 0 0 | 0 0 |
| 0 1 0 0 0 | 0 0 0 0 0 | 0 0 |
| 1 1 0 0 0 | 0 0 0 0 0 | 0 0 |
| 0 0 1 0 0 | 0 0 0 0 0 | 0 0 |
| 1 0 1 0 0 | 1 0 1 1 0 | 1 0 |
| 0 1 1 0 0 | 0 1 1 0 1 | 0 1 |
| 1 1 1 0 0 | 0 1 1 0 1 | 0 1 |
| 0 0 0 1 0 | 0 0 0 0 0 | 0 0 |
| 1 0 0 1 0 | 1 0 1 1 0 | 1 0 |
Általában azonban a tárkapacitás nem elég nagy a táblázatos dekódoláshoz. Ha viszont k kicsi értékű (k ≪ n), akkor még nagy kódszóhossz esetén is csak kevés kódszó van, és ekkor kódszavanként külön-külön ki lehet számítani a távolságot – gyakorlatilag megvalósítható dekódolóval. Tipikus kódparaméterek esetén azonban egyik út sem járható. Gondoljunk arra, hogy pl. k = 50 bit üzenethosszúság esetén 250 ≈ 1015 méretű a kód! A megoldás megértéséhez további alapfogalmakat kell megismernünk.
Egy kód kódszavai közötti minimális Hamming-távolság a kód igen fontos jellemzője, amelyet kódtávolságnak nevezünk és dmin-nel jelölünk.
Tehát formálisan:
Hibajelzés során a feladat annak megállapítása, hogy a vett szó kódszó-e vagy sem.
Az átküldött kódszó bitjei a hibák helyén invertálva jelennek meg a vett szóban.
Ha a hibák száma legfeljebb t lehet egy kódszó vétele során, továbbá, ha
7.1. tétel: Egy dmin kódtávolságú C kód minden, legfeljebb dmin−1 számú hibát jelezni tud.
Ha egy kód minden, legfeljebb t számú hibát jelezni (ill. javítani) tud, de van legalább egy olyan t+1 számú hibát tartalmazó hibaminta, amire ez nem áll fenn, akkor röviden azt mondjuk, hogy a kód hibajelző (ill. hibajavító) képessége t. Például a 7.1. példabeli kód hibajelző képessége a 7.1. tétel alapján 2.
Hibajavítás esetén azt kérdezzük, hogy ha t a hibák száma, akkor mi biztosítja azt, hogy a v vett szóból a c küldött kódszó egyértelműen visszaállítható legyen.
Ennek a formális feltétele az, hogy minden más c' kódszóra fennálljon a
Innen a d(c,c') > 2·d(v,c) átrendezett alakot kapjuk.
Ez az egyenlőtlenség biztosan teljesül, ha a kódtávolságból adódó d(c,c') ≥ dmin, c ≠ c' összefüggést is figyelembe véve a
7.2. tétel: Egy dmin kódtávolságú C kód hibajavító képessége int[(dmin−1)/2].
A 7.1. példabeli kód hibajavító képessége 1, vagyis ha egyetlen bithiba van, legyen az bármelyik kódszópozíción, a kód azt javítani tudja. A 7.2. tételből következik, hogy ha egy kód minden, legfeljebb t hibát javítani képes, akkor dmin > 2·t+1 áll fenn a kódtávolságára.
Felvetődik ezek után a kérdés: hogyan konstruálhatunk elegendően nagy kódtávolságú kódokat? Ezzel kapcsolatosan a következő pontban egy fontos kódosztály, a lineáris kódok alapfogalmait tekintjük át. A lineáris kódok előnye, hogy matematikai leírásmódjuk egyszerűbb, számos kódkonstrukció és hatékony dekódolási eljárás létezik erre a kódosztályra, továbbá implementálásuk is egyszerűbb, mint az általános nemlineáris kódoké.
7.2. példa.
Tekintsük a 7.1. példa kódját.
Észrevehetjük, hogy a kódolást elvégezhetjük egy c = uG mátrixszorzással, ahol G egy
Egy C bináris kódot lineáris kódnak nevezünk, ha a C halmaz lineáris tér, azaz ha minden c,c'∈C esetén c+c'∈C is fennáll. Innen következik, hogy a csupa zérus 0 szó is eleme kell, hogy legyen a lineáris kódnak, hiszen tetszőleges c bináris szó esetén fennáll a c + c = 0 egyenlőség. A lineáris kódok jelentőségét az adja, hogy az egyes üzenetekhez tartozó kódszavak viszonylag egyszerűen generálhatók, valamint egyszerűbb a hibadetektálás és a hibajavítás.
A valós vektortérben megszokott fogalmak a bináris vektorok terében is érvényesek.
Ennek megfelelően alkossák a g1,g2,…,gk C-beli vektorok a 2k elemet tartalmazó C lineáris tér egy bázisát, azaz ezen vektorok segítségével egyértelműen előállíthatunk tetszőleges c∈C elemet a
A C kódot tehát tömören megadhatjuk – k megfelelően kiválasztott kódszavával –, és nem szükséges felsorolni valamennyi, azaz 2k kódszavát. Továbbá a kódolás is egyszerű szabály szerint történik. Vegyük észre, hogy egy kódhoz számtalan generátormátrix tartozik, azaz ahány különböző bázisa lehet egy lineáris térnek. Viszont egy adott kódoláshoz, azaz üzenet↔kódszó összerendeléshez csak egy adott generátormátrix tartozik.
Ha megnézzük a 7.1. példabeli kódunkat, észrevehetjük, hogy a kódolást úgy választottuk, hogy a kódszavak első két bitje azonos legyen a megfelelő üzenet két bitjével. Ez előnyös, mivel a dekódolás második lépése, az üzenet-hozzárendelés a dekódolt kódszóhoz triviális, hiszen ez egyszerűen a dekódolt kódszó első k bitjének leválasztását jelenti. Ezt a kódolást más esetben is megtehetjük.
Egy C(n,k) kód szisztematikus, ha kódszavának első k bitje megfelel az üzenetnek.
Szisztematikus kód esetén már egyértelmű a generátormátrix, és a mátrixszorzás szabályai alapján nyilvánvalóan a következő alakú:
A c első k koordinátájából álló szegmensét üzenetszegmensnek, az utolsó n−k koordinátájából álló szegmensét pedig paritásszegmensnek nevezzük.
Egy C lineáris kódhoz hozzárendelhetjük a H, (n−k)×n méretű bináris mátrixot, amelynek az a tulajdonsága, hogy detektálni tudja az n hosszúságú bináris vektorok 2n méretű halmazában a C kódszavait.
A detektálás alapja az, hogy a
7.3. példa.
Tekintsük a 7.1. példa C kódját, és annak 7.2. példabeli generátormátrixát.
A bevezetett jelöléseket használva:
A következőkben azt mutatjuk meg, hogyan használható a H mátrix a dekódolásnál.
Legyen az átküldött kódszó c, a vett szó v. Az e = v − c vektort hibavektornak nevezzük.
Például, ha c = (10110), a vett szó pedig v = (11110), akkor a hibavektor e = (01000), azaz a 2. koordináta hibásodott meg.
Vegyük észre, hogy fentiek felhasználásával
7.2. ábra. A szindrómaszámítás dimenzionális szemléltetése
Például a 7.3. példabeli H mátrix esetén az e = (01000) hibavektor szindrómája s = (101). A szindrómavektor hossza n−k, azaz esetünkben 5−2 = 3.
A szindróma felhasználásával a lineáris kódok egy táblázatos dekódolása adható meg.
A dekódolási táblázat felépítése a következő:
| szindróma | min. hibaszámú hibavektor | |
|---|---|---|
| s0 = 0 | e0 = 0 | |
| s1 | e1 | |
| . | . | |
| . | . | |
| . | . | |
| s2n−k−1 | e2n−k−1 | |
Ezek után a szindrómadekódolás lépései a következők:
| s | e |
| 0 0 0 | 0 0 0 0 0 |
| 1 0 0 | 0 0 1 0 0 |
| 0 1 0 | 0 0 0 1 0 |
| 1 1 0 | 1 0 0 0 0 |
| 0 0 1 | 0 0 0 0 1 |
| 1 0 1 | 0 1 0 0 0 |
| 0 1 1 | 0 0 0 1 1 |
| 1 1 1 | 0 1 0 1 0 |
A következő pontban egyszerű és közismert lineáris kódok alapvető tulajdonságait tekintjük át.
7.5. példa.
A (000) és (111) szavakat tartalmazó kód a legegyszerűbb 1 hibát javító kód.
Így pl. ha a vett szó (110), akkor a (111) kódszót dekódoljuk, és az 1 üzenetre döntünk.
∎
A kódtávolság 4, amit a következőképp láthatunk be. Tekintsük a páros paritású esetet. Tartalmazzon az U üzenetmátrix egyetlen 1-et. Ekkor az 1-nek megfelelő sorban, ill. oszlopban a paritásbit 1, továbbá a jobb alsó sarokba kerülő paritásbit is 1. Tehát ezen kódszóban 4 db. 1 lesz, azaz a csupa zérus kódszótól való távolsága 4 (a Hamming-távolságot a mátrixok megfelelő koordinátáinak egybevetésével nyerjük). Tetszőleges kód esetén két tetszőleges kódszó Hamming-távolsága nyilván azonos a különbségükben található nemzérus elemek számával. Továbbá lineáris kódok esetén a kódszavak különbsége is kódszó. Következésképpen a kódszópárok közötti minimális távolság azonos a legkevesebb 1-et tartalmazó nemzérus kódszó 1-eseinek a számával. Az esetek végigpróbálásával könnyen belátható, hogy a kétdimenziós paritáskód esetén 4-nél kevesebb 1-et tartalmazó nemzérus kódszó nincsen, így a a kódtávolság valóban 4.
7.3. ábra. Kétdimenziós paritáskód
7.6. példa.
Ezen konstrukciónak megfelelően egy 1 hibát javító C(7, 4) kód H mátrixa lehet a következő:
A megkonstruált kód egy (7, 4) paraméterű Hamming-kód. Észrevehetjük, hogy ez a kódkonstrukció egyféle értelemben optimális. Nevezetesen, ha a feladat n = 7 hosszúság mellett 1 hibát javító kódok konstruálása, akkor ezen kódok között nincsen olyan kód, amely 24 = 16-nál nagyobb méretű. Természetesen a konstrukció általánosítható (n = 2r−1, k = 2r−1−r) paraméterek esetére, ahol r ≥ 3 egész szám.