Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

10. fejezet - 10. KÓDOK

10. fejezet - 10. KÓDOK

A kódelmélet feladata olyan eljárások kidolgozása, amelyek az elektronikus átvitelnél a (kis valószínűséggel, de esetleg mégis bekövetkező) hibákat kiszűrik, azaz a fogadó fél ezeket észreveszi („hibajelzés”), sőt akár rekonstruálni tudja a helyes üzenetet („hibajavítás”). Ennek érdekében az eredeti adatoknak megfelelő „közleményszavak” helyett kicsit hosszabb „kódszavak” kerülnek továbbításra. A kódolásnál általában az a cél, hogy minél kevesebb „ellenőrző jeggyel” minél több hiba jelzését, illetve javítását tudjuk elérni. Egy másik fontos követelmény, hogy a „kódolási” és „dekódolási” eljárások elvi és gyakorlati szempontból egyaránt (azaz mind a matematikai elméletet, mind pedig az elektronikai megvalósítást tekintve) nagy tömegű adatátvitel esetén is biztonságosan és hatékonyan működjenek.

Az alábbiakban az algebrai kódelmélet alapfogalmait tárgyaljuk, és bemutatunk néhány hatékony kódot. Megjegyezzük, hogy a kódoknak számos más (nem algebrai jellegű) típusa is létezik, valamint a kriptográfiában a titkosírásoknál is szokás a rejtjelezési eljárást kód(olás)nak nevezni, ezekkel azonban nem foglalkozunk.

10.1. Hibajelzés, hibajavítás

Az elektronikus eszközök az adatokat általában 0–1 sorozatokként tárolják. Bevezető illusztrációként szorítkozzunk arra a nagyon speciális esetre, amikor az átvitelnél összesen legfeljebb egyetlen bit továbbítása hibás, és nézzünk két egyszerű eljárást, hogyan lehet kideríteni, hogy valóban történt-e hiba, illetve hogyan lehet a hibás bitet megkeresni (azaz a hibát kijavítani).

Küldjük el a teljes üzenetet kétszer egymás után. Ha az átvitelnél legfeljebb egy bit továbbítása hibás, akkor a dupla üzenet két fele legfeljebb egyetlen jegytől eltekintve teljesen egyforma. Ezek szerint, ha a két rész egyforma, akkor nem történt hiba, ha pedig valahol eltérés van, akkor a továbbítás hibás volt. Sajnos azonban a hibát nem tudjuk kijavítani, hiszen lehet, hogy az éppen az „ellenőrző” részben keletkezett. Ezen úgy segíthetünk, ha az eredeti üzenetet még egyszer megismételjük, vagyis összesen háromszor küldjük el. Ekkor a három rész közül a feltevésünk szerint (legalább) kettő teljesen egyforma, és így ezek adják a helyes üzenetet.

Természetesen a fenti eljárások meglehetősen gazdaságtalanok. A kódelmélet egyik fő feladata éppen az, hogy olyan eljárásokat dolgozzon ki, amelyek minél kevesebb „ellenőrző jeggyel” minél több hibát tudnak jelezni, illetve kijavítani (emellett természetesen az is fontos, hogy mindezt minél egyszerűbben és „automatikusabban” tegyék meg).

A bevezető után lássunk hozzá a megfelelő matematikai elmélet kiépítéséhez. Ezután is mindig feltesszük, hogy a továbbítandó adatok bináris formában, azaz 0–1 sorozatként állnak rendelkezésre. Tördeljük ezt a sorozatot n hosszúságú blokkokra, ezek lesznek a „közleményszavak”. Minden közleményszó helyett egy k>n hosszúságú 0–1 sorozat, a közleményszónak megfelelő „kódszó” kerül továbbításra.

10.1.1 Definíció

Legyen n<k, és jelöljük az n, illetve k hosszúságú 0–1 sorozatok halmazát Tn-nel, illetve Tk-val. Ekkor kódon egy ϕ:TnTkinjektív leképezést értünk (azaz különböző elemek képe is különböző).

A kód értelmezési tartományának, vagyis Tn-nek az elemeit közleményszavaknak, az Im ϕ képhalmaznak az elemeit pedig kódszavaknak nevezzük.❶

A kódszavak tehát a Tk halmaznak egy 2n elemű (egyelőre tetszőleges) részhalmazát alkotják.

Megjegyzések: 1. Mint látni fogjuk, legtöbbször csak a kódszavak alkotta Im ϕ=K halmaz tulajdonságai lesznek lényegesek, maga a ϕ leképezés, azaz, hogy Tn melyik eleméhez melyik kódszót rendeljük hozzá, nem igazán számít. Ennek megfelelően szokás a kód fogalmát is csak a K halmazzal, a ϕ leképezés nélkül definiálni, ekkor a kód egyszerűen egy 2n elemű részhalmaz Tk-ban. (Mi továbbra is tartjuk magunkat a 10.1.1 Definícióhoz.)

2. A kiépítendő elmélet jelentős része (értelemszerű módosításokkal) átvihető lenne arra az esetre is, amikor a továbbítandó jelek a 0 és 1 helyett a 0,1,…,p–1 „jegyek” közül kerülnek ki, ahol p tetszőleges prím, esetleg prímhatvány. Mi azonban csak az ún. bináris kódokkal foglalkozunk.

Legyen a továbbiakban T=F2, a modulo 2 maradékosztályok teste. Ekkor az iménti Tn, illetve Tk jelölés összhangban van a korábbiakkal, azzal a kiegészítő megjegyzéssel, hogy mind a közleményszavakat, mind pedig a kódszavakat (egyelőre) általában nem oszlopvektorokkal, hanem inkább n, illetve k hosszúságú sorozatokkal fogjuk jelölni. (Ez az írásmód természetesebben felel meg a probléma jellegének, emellett kényelmesebb is.)

A következő ponttól kezdve majd azt is ki fogjuk használni, hogy Tn és Tk vektorterek T felett, és a ϕ kódok alkalmas lineáris leképezések lesznek Tn-ről Tk-ba.

Az egész fejezet során a szereplő vektorok, illetve mátrixok mindig automatikusan a T=F2 test felettieknek értendők.

Most rátérünk a hibajelzés és hibajavítás pontos értelmezésére. Kezdjük a hibajelzéssel. Tegyük fel, hogy egy c_Im φ kódszó továbbításakor hiba történt, azaz a c_ kódszó helyett egy tőle különböző z_ Tk vektor érkezett meg a fogadó félhez. Ha z_ maga is kódszó, akkor a hiba nem derül ki, azonban ha z_ nem kódszó, akkor világos, hogy hiba történt.

Mivel egy bit hibás továbbításának a valószínűsége igen kicsi (különben az egész átviteli rendszer gyakorlatilag használhatatlan lenne), ezért hiba esetén is a z_ és c_ vektorok általában csak kevés komponensben különböznek. Így a hibajelzéshez elég azt biztosítani, hogy ha egy kódszóban csak „kevés jegyet” változtatunk meg, akkor nem kapunk (egy másik) kódszót.

10.1.2 Definíció

Egy kód t-hibajelző, ha akármelyik kódszavának (legalább 1, de) legfeljebb t tetszőleges komponensét megváltoztatva sohasem kapunk kódszót.❶

A hibajelzés csak regisztrálja a tényt, hogy hiba történt. A hibajavítás azt jelenti, hogy ezen túlmenően azt is meg tudjuk határozni, melyik kódszó lett eltorzítva.

10.1.3 Definíció

Egy kód t-hibajavító, ha bármely két (különböző) kódszavának legfeljebb t tetszőleges komponensét megváltoztatva sohasem kapjuk ugyanazt a vektort.❶

Nyilván a t-hibajavítás lényegesen erősebb követelmény a t-hibajelzésnél, és mindkettő szorosan összefügg a kódszavak „távolságával”.

10.1.4 Definíció

Egy v_Tk vektor súlya (vagy Hamming-súlya) a benne levő 1-esek száma, két vektor távolsága (vagy Hamming-távolsága) pedig azoknak a komponenseknek a száma, ahol a két vektor eltér.❶

A távolság tehát a különbségvektor súlya. (Természetesen — T= F2 miatt — különbségvektor helyett összegvektort is mondhattunk volna.)

Az u_, v_Tk vektorok távolságát Tu_, v_-vel jelöljük. Az így definiált távolság valóban rendelkezik a távolság szokásos tulajdonságaival, és Tk erre a távolságra nézve metrikus tér (lásd a 8.2.6 Definíciót).

10.1.5 Tétel

Egy kód pontosan akkor t-hibajelző, ha a kódszavak közötti minimális távolság legalább t+1, és pontosan akkor t-hibajavító, ha a kódszavak közötti minimális távolság legalább 2t+1.❶

Bizonyítás: Mindkét állítás a 10.1.2–10.1.4 Definíciók közvetlen következménye. Ugyanis egy kód pontosan akkor t-hibajelző, ha bármely kódszóra igaz, hogy a tőle (legalább 1, de) legfeljebb t távolságra levő vektorok egyike sem kódszó. Hasonló módon egy kód pontosan akkor t-hibajavító, ha az egyes kódszavaktól legfeljebb t távolságra levő vektorok diszjunkt halmazokat alkotnak.❷

Példák kódokra

Kezdjük a sort a bevezetőben már jelzett két eljárással.

P1. Kétszeri ismétlés: A (megfelelő) kódszót úgy képezzük, hogy a közleményszót még egyszer megismételjük (tehát összesen kétszer írjuk le egymás után), azaz

Itt k=2n, a kódszavak azok a vektorok, amelyeknek minden 1≤jn-re a j-edik és az n+j-edik komponense megegyezik. Ez a kód 1-hibajelző, a kódszavak minimális távolsága 2. (Természetesen a kód számos „többhibát” is jelez, de ha véletlenül pl. éppen az első és az n+1-edik jegy volt hibás, akkor ez a 2-hiba nem derül ki, mert így egy másik kódszóhoz jutottunk.)

P2. Háromszori ismétlés: A (megfelelő) kódszót úgy képezzük, hogy a közleményszót összesen háromszor írjuk le egymás után, azaz

Itt k=3n, a kódszavak azok a vektorok, amelyeknek minden 1≤jn-re a j-edik, az n+j-edik és a 2n+j-edik komponense megegyezik. Ez a kód 1-hibajavító és 2-hibajelző, a kódszavak minimális távolsága 3.

Az előzőknél lényegesen „gazdaságosabb” az alábbi kód:

P3. Paritásvizsgálat: A (megfelelő) kódszót úgy képezzük, hogy a közleményszó után egyetlen további bitet írunk, éspedig a közleményszó jegyeinek az összegét, azaz 1-et vagy 0-t aszerint, hogy a közleményszóban páratlan vagy páros sok 1-es szerepelt:

Itt k=n+1, a kódszavak azok a vektorok, amelyekben páros sok 1-es fordul elő, vagyis amelyeknek a súlya páros. Ez a kód is 1-hibajelző, a kódszavak minimális távolsága 2.

Az n, k és s=kn paraméterek szokásos elnevezéseit az alábbiakban foglaljuk össze:

10.1.6 Definíció

Egy TnTk kód esetén k a kód(szavak) hossza, n az információs jegyek száma vagy a kód dimenziója és s=kn az ellenőrző jegyek száma.❶

A dimenzió elnevezést az magyarázza, hogy a legtöbb kód esetén a kódszavak alteret alkotnak Tk-ban (lásd a lineáris kódokat a következő pontban), és ekkor ennek az altérnek a dimenziója valóban n.

Egy kód hatékonyságát az méri, hogy egyrészt hány hibát tud (biztosan) jelezni, illetve javítani (azaz milyen nagy a kódszavak közötti minimális távolság), másrészt ezt milyen kis s=kn értékkel éri el. Az iménti P1 és P3 példa kódja is 1-hibajelző, ugyanakkor a kétszeri ismétlésnél az ellenőrző jegyek száma n, míg a paritásvizsgálatnál mindössze 1, tehát az utóbbi lényegesen hatékonyabb.

Nézzük most meg, legalább hány ellenőrző jegy szükséges az 1-hibajavításhoz. Minden kódszóhoz vegyük hozzá a tőle 1 távolságra levő vektorokat (azaz, amelyek a kódszótól egyetlen komponensben különböznek). Az így kapott k+1 elemű halmazok az 1-hibajavítás miatt szükségképpen diszjunktak, számuk 2n, azaz 2n(k+1)≤2k. Innen (k=n+s felhasználásával) 2sn+s+1 adódik. Ez pl. n=500-ra s≥9-et jelent. A 10.3 pontban megmutatjuk, hogy itt elérhető az s=9 egyenlőség (vö. a P2 példa háromszori ismétlés kódjából származó s=1000 értékkel).

Feladatok

10.1.1 Tegyük fel, hogy minden egyes bit átvitelénél (egymástól függetlenül) p a hiba valószínűsége. Mi a valószínűsége annak, hogy egy k-jegyű kódszó átvitelénél

a) nem történik hiba;

b) pontosan 1 jegyben keletkezik hiba;

c) több, mint 3 jegy lesz hibás?

(Érdekes és tanulságos a fenti valószínűségeket valamely konkrét k és p értékek, pl. k=20 és p=10–4 esetén összehasonlítani.)

10.1.2 Tekintsük azokat a kódokat, ahol n=3, a kódszó minden esetben a megfelelő 3-jegyű α1α2α3 közleményszóval kezdődik, majd ezt az alábbi ellenőrző jegy(ek) követi(k) (ezek száma rendre 1, 2, 2, 2, 3, 3, 3):

a) α123+1 b) α1, α23 c) α1, max(α2, α3) d) α1, γ ahol γ=α2,   ha α1=1α3,   ha α1=0 e) α12, α13, α23 f) α1, α12, α123 g) α1, α1·α2, α1·α2·α3

A felsorolt kódok közül melyek lesznek 1-hibajelzők, illetve 1-hibajavítók?

10.1.3 Mutassuk meg, hogy a kód hibajelző, illetve hibajavító „ereje” nem változik meg, ha minden kódszóban

a) az első jegyet az ellenkezőjére változtatjuk;

b) az összes jegyet az ellenkezőjére változtatjuk;

c) az első két jegyet felcseréljük.

Hogyan általánosíthatjuk ezeket az észrevételeket?

10.1.4

a) Bizonyítsuk be, hogy három (Tk-beli) vektor páronkénti távolságainak az összege mindig páros szám.

b) Mely m-ekre igaz, hogy m tetszőleges vektor páronkénti távolságainak az összege mindig páros szám?

10.1.5 Tegyük fel, hogy az u_ és v_ vektorok távolsága Tu_, v_=d Hány olyan w_Tk vektor létezik, amelyre Tu_, w_=q és Tv_, w_=r?

10.1.6 Tegyük fel, hogy három (Tk-beli) vektor páronkénti távolsága d. Mutassuk meg, hogy d páros, és pontosan egy olyan vektor létezik, amely mindhárom adott vektortól d/2 távolságra esik.

10.1.7 Egy TnTk kódban legyen d a kódszavak közötti minimális távolság. Készítsünk egy új TnTk+1 kódot a következőképpen: minden páros súlyú kódszó után írjunk egy 0-t, minden páratlan súlyú kódszó után pedig egy 1-est. Mekkora az új kódban a kódszavak közötti minimális távolság?

10.1.8 Tegyük fel, hogy egy TnTk kód t-hibajavító. Bizonyítsuk be, hogy ekkor i=0tki2k-n 

10.1.9 Legyen n=2. Minimálisan hány ellenőrző jegy szükséges egy

a) 1-hibajelző; b) 1-hibajavító; c) 2-hibajelző; *d) 2-hibajavító; *e) t-hibajavító

kódhoz?

Az e) rész kivételével oldjuk meg a feladatot az n=3 esetben is.