Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

10. Kódok

10. Kódok

10.1.

10.1.1 a) (1–p)k. b) kp(1–p)k–1. c) 1-i=03kipi1-pk-i

10.1.2 1-hibajelző: a), b), e), f). — 1-hibajavító: e).

10.1.3 Az általánosítás: (i) tetszőleges számú rögzített helyen a jegyeket megváltoztathatjuk, azaz minden kódszóhoz ugyanazt a vektort hozzáadhatjuk (a kódszavakat „eltoljuk”); (ii) a kódszavak jegyeit tetszőlegesen (de azonos módon) permutálhatjuk; valamint (i)-et és (ii)-t kombináltan is alkalmazhatjuk (azaz vehetjük a kétféle transzformáció kompozícióját). Az így nyert kódokat az eredetivel ekvivalenseknek nevezzük.

10.1.4 b) Pontosan a páratlan m-ek ilyenek.

10.1.5 Legyen A, illetve B azoknak a helyeknek a halmaza, ahol az u_ és v_ vektorok jegyei azonosak, illetve ellentétesek. A feltétel szerint |A|=kd, |B|=d. Jelöljük j-vel, ahány A-beli helyen a w_ vektor jegye nem ugyanaz, mint a másik két vektoré. Ekkor B-ben az u_ és w_ vektorok qj, a v_ és w_ vektorok pedig rj jegyben kell hogy különbözzenek, és nyilván (qj)+(rj)=d. Innen j=(r+qd)/2, tehát nincs megfelelő w_ ha r+qd páratlan szám és k-djdq-j ilyen w_ van, ha r+qd páros.

10.1.6 Az előző feladathoz hasonló gondolatmenetet kell alkalmazni.

10.1.7 Ha d páratlan volt, akkor a minimális távolság eggyel nő, páros d-re pedig nem változik.

10.1.8 A t=1 speciális esetre látott gondolatmenetet kell adaptálnunk. Jelöljük Hc_-vel a c_ kódszó t sugarú környezetét, azaz a tőle legfeljebb t távolságra levő Tk-beli vektorok halmazát (beleértve magát a c_ vektort is). Mivel a c_-től (illetve bármelyik Tk-beli vektortól) pontosan i távolságra ki darab vektor található, ezért a tőle legfeljebb t távolságra levő vektorok száma Hc_=i=0tki  A feltétel szerint a Hc_ halmazok páronként diszjunktak és a számuk 2n, így az egyesítésük elemszáma 2nHc_Tk=2k 

10.1.9 Az n=2 esetben: a) 1, b) 3, c) 3, d) 6, e) 3t. Ha n=3, akkor: a) 1, b) 3, c) 3, d) 7. — Az n=2 esetre és a 2-hibajavításra részletezzük a bizonyítást (a t-hibajavítás tetszőleges t-re ennek mintájára tárgyalható, és hasonlóan kell okoskodni — csak jóval több számolgatás kíséretében — n=3 mellett is a 2-hibajavításnál). Hat ellenőrző jegy valóban elég, mert megfelel például a φ : α1α2α1α2α1α2α1α2ββ kód, ahol β=α12. Azonnal látszik, hogy a négy kódszó közül bármelyik kettőnek a távolsága legalább 5, tehát a kód valóban 2-hibajavító. Ugyanakkor öt ellenőrző jegy még nem lehet elég a 2-hibajavításhoz, mert T7-ben már három olyan vektor sem található, amelyek közül bármelyik kettő távolsága legalább 5. Ha ugyanis c_2-c_1-ben és c_3-c_2-ben is a hét jegy között legalább öt darab 1-es szerepel, akkor ezek közül legalább három azonos helyen fordul elő, és így c_3-c_1=c_3-c_2+c_2-c_1-ben ezeken a helyeken 0 áll, vagyis c_3-c_1-ben legfeljebb négy 1-es található.

10.2.

10.2.1 Lássuk be, hogy κ=i=02n-12k-i és λ=j=02n-12k-2j 

10.2.2 Két, illetve három n×n-es egységmátrix egymás alatt.

10.2.3 Lineáris: b), e) és f). Generátormátrixok:

b) 100010001100011 e) 100010011001011011 f) 100010011100111001

A dekódolási táblát csak e)-re adjuk meg (a másik két kód nem is lesz 1-hibajavító):

10.2.4 Egy A : TnTk lineáris leképezés injektivitása ekvivalens azzal, hogy dimIm A=n  továbbá dimIm A éppen az A mátrixának a rangja.

10.2.6 A dimenzió n–1 vagy n.

10.2.7 a) I-ben a minimális távolság legalább d1+d2, II-ben pontosan min(d1, d2), III-ban pedig pontosan min(2d1, d2). — b) I-nél a két generátormátrixot egymás alá kell írni, azaz a (k1+k2n méretű G1G2 mátrixot kapjuk. II-nél a két generátormátrix direkt összegét kell venni, vagyis a (k1+k2)×(n1+n2) méretű G100G2 mátrix az eredmény. III-nál ez annyiban módosul, hogy a G1 alá a 0 blokk helyére még egy G1 kerül: G10G1G2 

10.2.8

a) Legyen g=i=0sδixi  ekkor a generátormátrix j-edik oszlopában a j+i-edik elem δi, i=0,1,…,s, a többi elem pedig 0 (tehát a „főátló” minden eleméről „lelóg” a g polinom egy-egy példánya).

b) Az injektivitással lehet baj. Legyen g és h legnagyobb közös osztója d, ekkor

Ebből a degfin–1 feltétel figyelembevételével akkor és csak akkor következik f1=f2, ha n≤deg(h/d)=k–degd, azaz degds.

c) Legyen d=(g,h) és D a d-vel osztható legfeljebb k–1-edfokú polinomok halmaza. Ekkor |D|=2k–degd=2n, tehát D éppen a d által generált polinomkód kódszavaiból áll, továbbá nyilván d|h. A gf polinom h-val való osztási maradéka mindenképpen osztható d-vel, tehát K_D Mivel emellett |K|=|D|, ezért K=D.

10.2.9 Legyen a kód generátormátrixa G, ekkor olyan H kell, amelyre HG=En×n. Ez n darab, n egyenletből álló és k ismeretlenes lineáris egyenletrendszert jelent, amelyek mindegyikének az együtthatómátrixa GT. Mivel G rangja n, ezért ezek az egyenletrendszerek megoldhatók. A megoldásokat pl. Gauss-kiküszöböléssel gyorsan meg is tudjuk határozni. A megoldások (k>n miatt) nem egyértelműek, de akármelyikből adódó H megfelel. Ugyanezt az eljárást alkalmaztuk a négyzetes mátrixok inverzének a meghatározására (tulajdonképpen megfelelő értelmezés mellett most is a G mátrix egy bal oldali inverzéről van szó).

10.3.

10.3.1 A sorok függetlenségének a feltételezése mellett az oszlopok összefüggősége ekvivalens azzal, hogy több oszlop van, mint sor. A paritásellenőrző mátrixról tudjuk, hogy a rangja megegyezik a sorok számával, tehát a sorai függetlenek, az oszlopok pedig többen vannak, mint a sorok. A megfordításhoz vegyünk egy olyan P mátrixot, amelynek s sora és k oszlopa van, ahol ks=n>0 és r(P)=s. Ekkor a P mátrix KerP magtere egy ks=n dimenziós altér Tk-ban, és így létezik olyan A : TnTk injektív lineáris leképezés, amelyre ImA=Ker P  Ekkor az A lineáris kód paritásellenőrző mátrixa éppen P lesz.

10.3.2 Mivel mindegyik esetben G=En×nBs×n alakú, ezért paritásellenőrző mátrixnak megfelel P=(Bs×nEs×s) (vö. a 10.3.4a feladattal).

10.3.3 I. A második tulajdonság azt fejezi ki, hogy Ker PK (ahol K a kódszavak altere). Itt egyenlőség pontosan akkor teljesül, ha n=dimK=dimKer P=dimTk-rP=k-rP — II. Az I-beli második tulajdonság ekvivalens PG=0-val. — III. A PG=0 mátrixegyenlőség éppen azt jelenti, hogy P sorai merőlegesek Im A-ra, r(P)=s pedig azt, hogy ezek a sorok lineárisan függetlenek. Használjuk még fel, hogy dimImA=dimTk-dimIm A=k-n=s 

10.3.4 Használjuk az előző feladat III. részét, valamint b)-hez még a 4.5.14a feladatot is.

10.3.5 Útmutatás b)-hez: Használjuk a 10.3.3 feladat II. részét. A PG=0 feltétel s darab, k ismeretlenes és n egyenletből álló homogén egyenletrendszert jelent, amelyek közös együtthatómátrixa GT. Mivel a szabad paraméterek száma kr(GT)=kn=s, ezért a megoldások egy s-dimenziós alteret alkotnak Tk-ban, tehát kiválasztható s darab független megoldás. Az egyenletrendszert pl. Gauss-kiküszöböléssel oldhatjuk meg, és biztosan független megoldásokhoz jutunk, ha rendre egy-egy szabad paramétert 1-nek, a többit pedig 0-nak választunk.

10.3.6 b) Válasz: (ha r(P)=s, akkor) az ilyen kódok száma i=0n-12n-2i  (Természetesen az összes ilyen A : TnTk lineáris leképezésnél a képtér, azaz a kódszavak K halmaza mindig ugyanaz, csak maguk a leképezések változnak.) — Útmutatás: A PG=0 mátrixegyenletben most a G az ismeretlen, és olyan megoldásokat keresünk, ahol r(G)=n. Legkényelmesebben a 10.3.4 feladat mintájára érhetünk célt. — Egy másik lehetőség, ha a 10.3.1 feladatnál látott gondolatmenetet követjük.

10.3.7 Ha egy sor lineárisan függ a többitől, akkor ennek a sornak az elhagyása a mátrix magterét nem változtatja meg.

10.3.9 Hasonlóan okoskodhatunk, mint a 10.3.2 Tétel bizonyításánál.

10.3.10 Használjuk fel az előző feladatot. — Másik lehetőség: A paritásellenőrző mátrix helyett a generátormátrixszal is dolgozhatunk. Ha a kódszavak a megfelelő közleményszóval kezdődnek, akkor egy egységvektorhoz tartozó kódszó súlya legfeljebb 1+s, tehát készen vagyunk. Ugyanezt a gondolatot tetszőleges lineáris kód esetén a következőképpen valósíthatjuk meg: vegyünk a generátormátrixban n független sort, és lássuk be, hogy van olyan kódszó, amelynek az ebbe az n sorba eső része egy (tetszőleges) egységvektor.

10.3.11 Az egyik kód generátormátrixa a másiknak egy paritásellenőrző mátrixa és viszont.

10.3.12 Használjuk fel az előző feladatot.

10.3.13 Válasz: 3. (Az 1-hibajavítás miatt a minimális távolságnak legalább 3-nak kell lennie, nagyobb pedig azért nem lehet, mert — mint már a 10.1 pontban is láttuk — ekkor a kódszavak 1 sugarú környezetei kitöltik az egész Tk-t.)

10.3.14 Először mutassuk meg, hogy ha egy lineáris kódban van olyan kódszó, amelynek a komplementere is kódszó, akkor ez minden kódszóra teljesül. Ezután elég például a 0_ kódszó komplementéről, a j_ csupaegy vektorról belátni, hogy kódszó. Ez pontosan azt jelenti, hogy a paritásellenőrző mátrix minden sorában páros sok 1-es szerepel.

10.3.15 A megadásból leolvasható, hogy lineáris kódot definiáltunk. Írjuk fel a G generátormátrixot. Ennek az egységmátrix alatti s×(2s–1) méretű B részében az oszlopok rendre azoknak a 2s-nél kisebb természetes számoknak a kettes számrendszerbeli alakjai, amelyek nem kettőhatványok. Így éppen azok az oszlopok fordulnak elő B-ben, éspedig mindegyik egyszer, amelyekben legalább két darab 1-es áll. Láttuk, hogy a P paritásellenőrző mátrixot megkaphatjuk úgy, hogy B elé egy s×s méretű egységmátrixot helyezünk el, azaz B oszlopai elé az s darab egységvektort is odatesszük. Így P oszlopait úgy kapjuk, hogy Ts minden nemnulla vektorát pontosan egyszer vesszük, azaz valóban egy Hamming-kódról van szó. — A paritásellenőrző mátrix felírása nélkül közvetlenül is beláthatjuk, hogy a kód 1-hibajavító, tehát Hamming-kód. Ehhez azt kell igazolni, hogy minden nemnulla kódszóban legalább három 1-es szerepel. Ha már a közleményszóban legalább három 1-es áll, akkor ezek a kódszóban is megmaradnak, tehát készen vagyunk. Ha a közleményszóban egyetlen 1-es fordul elő, mondjuk αm, akkor az m kettes számrendszerbeli jegyeinek megfelelő γ-k értéke is 1, tehát a kódszóban ekkor is megvan a (legalább) három 1-es. Végül, ha a közleményszóban két 1-es található, mondjuk αm és αq, akkor m és q kettes számrendszerbeli felírása legalább egy jegyben különbözik, és egy ilyen helyiértéknek megfelelő γ értéke szükségképpen 1, azaz most is találtunk (legalább) három 1-est a kódszóban.

10.4.

10.4.1 A 32 elemű test multiplikatív csoportjának elemszáma 31, ami prímszám, ezért ezt a csoportot az egységelemen kívül bármelyik eleme generálja. Így generátorelemnek egy tetszőleges ötödfokú irreducibilis polinom, például az x5+x2+1 egyik gyökét vehetjük. Ekkor a Δ5=1+Δ2 számolási szabályt kell ismételten alkalmazni. Ennek alapján a paritásellenőrző mátrixnak például a 3. oszlopa a következő lesz: a felső részbe Δ2, az alsóba Δ6=Δ+Δ3 kerül, azaz a felső öt elem rendre 0,0,1,0,0, az alsó öt pedig 0,1,0,1,0.

10.4.2 Láttuk, hogy s=deggt, ahol gt=[m1, m3,…, m2t–1]. Mivel mindegyik mi irreducibilis, ezért gt a fenti mi-k közül a különbözőknek a szorzata, továbbá degmiq. Így s=deggt=tq pontosan akkor teljesül, ha az mi-k mind különbözők és mindegyiknek a foka q.

10.4.3 a) A 16 elemű testet a 10.4.1 Tétel utáni példa mintájára kezeljük, és használjuk ki, hogy (Δ3)5=(Δ5)3=1. — b) Mutassuk meg, hogy Δ3 és Δ5 is generátorelem a Tq test multiplikatív csoportjában, és így a minimálpolinomjuk szükségképpen q-adfokú. Ezután igazolnunk kell még a három minimálpolinom különbözőségét, ehhez lássuk be, hogy mi összes gyökei a Δ-nak az i·2j kitevőjű hatványai, ahol 0≤j<q.

10.4.4 Az előző feladathoz hasonlóan kapjuk, hogy m3m1, és így s=degg=degm1+degm3=q+deg(Δ3). Ha Δ3 nem lenne q-adfokú, akkor a foka valódi osztója lenne a q-nak, és így deg(Δ3)≤q/2, tehát s≤3q/2 következne. Ugyanakkor tudjuk, hogy s≥2q–1, ami ellentmondás.

10.4.5 a) Használjuk fel, hogy minden v|q-ra a Tq testnek pontosan egy 2v elemű részteste van, és ennek nemnulla elemei a Δ-nak a j(2q–1)/(2v–1) kitevőjű hatványai.

b) Lássuk be, hogy ezek mind gyökei mi-nek, továbbá páronként különbözők. Ez utóbbihoz használjuk fel, hogy Δ két hatványa pontosan akkor egyenlő, ha a kitevők különbsége osztható 2q–1-gyel.

10.4.6 Meg kell mutatni, hogy teljesülnek a 10.4.2 feladat feltételei. Támaszkodjunk a 10.4.5 feladatra is.

10.4.7 a) A c_=γ0 . . . γk-1Tk vektor akkor és csak akkor páros súlyú, ha γ01+…+γk–1≡0 (mod 2), azaz az 1 gyöke a C01x+…+γk–1xk–1 polinomnak, vagyis x–1=x+1|C. Mivel a kódszavak K halmaza pontosan g többeseiből áll, ezért a feltétel ekvivalens azzal, hogy 1+x|g. — b) A páros súlyú elemek száma éppen |Tk|/2, azaz ekkor az ellenőrző jegyek száma s=1. Ezt a)-val összevetve kapjuk az állítást.

10.4.8 A Tq test multiplikatív csoportjának bármely elemét a |Tq|–1=2q–1=k-adik hatványra emelve az egységelemet kapjuk. Ez azt jelenti, hogy a multiplikatív csoport bármely eleme gyöke az xk–1 polinomnak, és így mindegyik mi minimálpolinom osztja xk–1-et. Ekkor viszont a legkisebb közös többszörösük, azaz a generáló polinom is osztja xk–1-et.

10.4.9 a) Lássuk be, hogy egy ciklikus kód kódszavai ideált alkotnak az Rk=T[x]/(xk–1) maradékosztálygyűrűben, és ezt az ideált egy olyan g polinom generálja, amely osztója xk–1-nek.

b) Az a) részből és az előző feladatból következik.

10.4.10 Olyan (kvázi-)paritásellenőrző mátrixot kell gyártani, amelynek bármelyik d–1 oszlopa független. Ha már az első j oszlopot elkészítettük, akkor a j+1-ediket úgy kell megválasztani, hogy az ne legyen felírható az első j oszlop közül semelyik legfeljebb d–2-nek a lineáris kombinációjaként. A feltétel alapján ez még j=k–1-re is megvalósítható.

10.4.11 Az a) résznél q szerinti, a b) résznél pedig (pl.) q+m szerinti teljes indukcióval bizonyítsunk.