Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

10. Kódok

10. Kódok

• 10.2.1 Egy kód megadása azt jelenti, hogy a 2n darab Tn-beli elemhez rendre hozzárendelünk különböző Tk-beli elemeket. Így az első elem képe 2k-féle lehet, a másodiké 2k-1-féle stb., tehát κ=i=02n-12k-i 

A lineáris kódokat egy bázison (pl. az egységvektorokon) történő megadással jellemezhetjük. Az injektivitás itt azt jelenti, hogy a leképezés magtere 0, azaz a báziselemek képei függetlenek. Így az első bázisvektor képe tetszőleges nemnulla vektor lehet, a továbbiakban pedig csak arra kell ügyelni, hogy a j+1-edik bázisvektor képe ne essen az első j bázisvektor képe által generált altérbe (j=1,2,…,n-1). Az első bázisvektor képe ennek megfelelően 2k-1-féle lehet, a másodiké 2k-2-féle és általában a j+1-ediké 2k-2j-féle. Innen λ=j=0n-12k-2j 

A két képlet alapján κ/λ azoknak a (2k-i) tényezőknek a szorzata, ahol 0≤i<2n és i nem kettőhatvány, tehát κ/λ valóban egész szám.

• 10.4.3 a) A 10.4.1 Tétel utáni példa mintájára vehető m1=x4+x+1. A Θ=Δ3 elemre Θ515=1, ezért Θ gyöke az f=x4+x3+x2+x+1 (körosztási) polinomnak. Ez könnyen láthatóan irreducibilis F2 felett, így m3 =f. A Ψ=Δ5 elemre Ψ315=1, ezért Ψ gyöke a h=x2+x+1 irreducibilis polinomnak, ahonnan m5=h. Innen s=4+4+2=10.

• b) Mivel a 3 és az 5 is relatív prím a Tq test multiplikatív csoportjának az elemszámához, a 2q-1-hez, ezért Δ3 és Δ5 is generátorelem ebben a csoportban. Ebből következik, hogy az F2 testnek a Δ3-nal, illetve a Δ5-nel való bővítése kiadja az egész Tq testet (sőt az összeadásra tulajdonképpen nincs is szükség), ezért Δ3 és Δ5 minimálpolinomja is q-adfokú.

A 10.4.2 feladat szerint azt kell még belátnunk, hogy Δ, Δ3 és Δ5 közül semelyik kettőnek sem ugyanaz a minimálpolinomja. Ehhez először azt igazoljuk, hogy ha Δi generátorelem a Tq test multiplikatív csoportjában (azaz i és 2q-1 relatív prímek), akkor mi összes gyökét a Δ-nak az i·2j kitevőjű hatványai adják, ahol 0≤j<q. A 10.4.2 Tétel bizonyításánál láttuk, hogy Θ és Θ2 minimálpolinomja ugyanaz. Ebből következik, hogy mi-nek a megadott q darab Δ-hatvány valóban gyöke. Belátjuk még, hogy ezek mind különbözők, és így szükségképpen mi-nek mind a q darab gyökét megkaptuk. A Δ két hatványa pontosan akkor egyenlő, ha a kitevők különbsége osztható o(Δ)=2q-1-gyel. Ha 0≤u<j<q, akkor i2j-i2u=i 2u(2j-u-1)-ben az első két tényező relatív prím a 2q-1-hez, a harmadik tényező pedig kisebb 2q-1-nél, így a szorzat nem lehet osztható 2q-1-gyel. Ezzel megmutattuk, hogy a megadott Δ-hatványok mind különbözők, és így ezek adják az mi polinom gyökeit.

Most belátjuk, hogy a Δ, Δ3 és Δ5 elemeknek páronként különböző a minimálpolinomja. Ha m1=m3 lenne, akkor Δ3 szerepelne az m1 gyökei között, azaz 3=2j teljesülne, ami lehetetlen (itt a kitevőknél a modulo 2q-1 kongruencia helyett azért lehetett az egyenlőséget nézni, mert mind a 3, mind pedig a 2j kitevő 0 és 2q-1 közé esett). Ugyanígy az m1=m5 feltételezés is ellentmondásra vezet. Végül tegyük fel, hogy m3=m5, azaz Δ5 gyöke m3-nak. Az m3 gyökei Δ-nak az alábbi kitevőjű hatványai:

Azonban az 5 ezek közül (a 0 és 2q-1 közötti értékek közül) egyikkel sem egyezhet meg (az utolsóval q>3 miatt nem), tehát ebben az esetben is ellentmondásra jutottunk.

• 10.4.5 a) Tudjuk, hogy a 2q elemű test összes részteste 2v elemű, ahol v|q, és minden ilyen v-hez pontosan egy 2v elemű Tv résztest tartozik. A Tv test Gv multiplikatív csoportja egy 2v-1 elemű részcsoport a Tq test (ciklikus) multiplikatív csoportjában, így Gv-t a Δ-nak a (2q-1)/(2v-1)-edik hatványa generálja. Ez azt jelenti, hogy Tv nemnulla elemei azok a Δi hatványok, ahol (2q-1)/(2v-1)|i. Más szóval, valamely i-re Δi pontosan azokban a Tv résztestekben van benne, amelyekre (2q-1)/(2v-1)|i. Tudjuk, hogy degmi a Δi-t tartalmazó legszűkebb résztestnek a(z F2 test feletti) dimenziója. A legszűkebb résztestet éppen a legkisebb megfelelő v érték szolgáltatja, tehát degmi valóban a legkisebb ilyen tulajdonságú v, amint állítottuk.

• b) A 10.4.2 Tétel bizonyításánál láttuk, hogy Θ és Θ2 minimálpolinomja ugyanaz. Ebből következik, hogy mi-nek gyöke minden olyan Δ-hatvány, ahol a kitevő i·2j alakú. Nézzük meg, hány különböző ilyen hatvány keletkezik. Az első ismétlődés akkor következik be, amikor i·2v-i először osztható o(Δ)=2q-1-gyel, vagyis a legkisebb olyan v-re, amikor (2q-1)/(2v-1)|i. Az a) részben láttuk, hogy ez a v éppen degmi . Ez azt jelenti, hogy a szóban forgó Δ-hatványok között éppen degmi darab különböző található, ezek valamennyien gyökei mi-nek, vagyis valóban ezek adják mi összes gyökét.

• 10.4.6 Először megmutatjuk, hogy minden i≤2t-1-re degmi=q. Ellenkező esetben a 10.4.5a feladat szerint lenne a q-nak olyan valódi v osztója, amelyre (2q-1)/(2v-1)|i. Ekkor vq/2, és így

ugyanakkor a feltétel szerint i≤2t-1≤2q/2-1, ami ellentmondás.

Most belátjuk, hogy mi≠ml, ahol i és l különböző páratlan számok 1 és 2t-1 között. Indirekt tegyük fel, hogy mi=ml. Ekkor Δl szerepel mi gyökei között, azaz a 10.4.5b feladat szerint li·2j mod 2q-1 teljesül valamilyen 0≤j<q-ra. Ha jq/2, akkor i·2j≤(2q/2-1)2q/2<2q-1, tehát a kongruencia helyett egyenlőségnek kellene teljesülnie, ami nyilván nem lehet. Ha j>q/2, akkor írjuk át a kongruenciát i2j-y2q=l-y alakba. Itt a bal oldal osztható 2j-vel, de ( j<q miatt) nem lehet nulla, ezért abszolút értéke legalább 2j> 2q/2. A jobb oldal abszolút értéke azonban ennél kisebb, hiszen 0<l≤2t-1<2q/2, valamint (j<q miatt) 0≤y<i< 2q/2. Mindenképpen ellentmondásra jutottunk, tehát valóban miml .

Ezzel igazoltuk, hogy m1,m3,…,m2t-1 páronként különböző q-adfokú polinomok, amiből a 10.4.2 feladat alapján következik, hogy s=tq.

• 10.4.9 a) A továbbiakban Tk[x]-et az Rk=T[x]/(xk-1) maradékosztálygyűrűvel azonosítjuk, azaz a legfeljebb k-1-edfokú polinomokat mint az xk-1-gyel való osztási maradékokat tekintjük. Ennek az az előnye, hogy Tk[x]-en a szorzás is értelmes, tehát egy gyűrűt (sőt algebrát) kapunk.

Ennek alapján a ciklikus kód definíciója pontosan azt jelenti, hogy egy kódszó x-szerese is kódszó: x( γ01x+…+γk-1xk-1)=γ0x1x2+…+

k-2xk-1k-1xkk-10x+γ1x2+…+γk-2xk-1.

Felhasználva, hogy a kód lineáris, azaz kódszavak összege is kódszó, azonnal adódik, hogy a ciklikus kódok úgy is jellemezhetők, hogy egy kódszó bármely polinomszorosa is kódszó. Így egy kód pontosan akkor ciklikus, ha a kódszavak egy ideált alkotnak Rk-ban.

Mivel T[x]-ben van maradékos osztás, ezért minden ideálja főideál, és így ugyanez érvényes Rk-ban is. Ez azt jelenti, hogy ciklikus kód esetén K egy alkalmas g polinom többszöröseiből áll. A 10.2.8c feladat alapján feltehető, hogy g|xk-1 és K éppen a g polinom által generált polinomkód kódszavaiból áll.

Végül, a megfordításhoz azt igazoljuk, hogy egy ilyen polinomkód valóban ciklikus. Ez onnan adódik, hogy ha gf kódszó, akkor ennek a ciklikus permutációja x(gf)=g(xf) is kódszó. (Ha az xf polinom foka n, akkor helyette az (xk-1)/g polinommal való osztási maradékát kell venni.)

• 10.4.10 A 10.3.9 feladat szerint olyan m×k méretű kvázi-paritásellenőrző mátrixot kell gyártani, amelynek bármelyik d-1 oszlopa független. Az első oszlop legyen egy tetszőleges nemnulla vektor. Tegyük fel, hogy az első j oszlopot már elkészítettük. Ekkor 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. Ezzel kizártuk a nullvektort, a j darab eddigi oszlopvektort, ezek j2 darab páronkénti összegét,j3 darab hármankénti összegét stb. Így összesen legfeljebb i=0d-2ji vektort zártunk ki (lehet, hogy csak kevesebbet, mert ezek között az öszegek között — id/2 esetén — már előfordulhatnak egybeesők). Ha i=0d-2ji<2m akkor biztosan nem zártuk ki Tm összes vektorát, tehát tudunk egy alkalmas j+1-edik oszlopot választani. A feltétel alapján ez még j=k-1-re is megvalósítható, tehát valóban egy megfelelő m×k méretű kvázi-paritásellenőrző mátrixhoz jutunk.

• 10.4.11 a) A q szerinti teljes indukciót formálisan a (tulajdonképpen tiltott) q=1 esettel érdemes kezdeni, amelyre az állítás nyilvánvaló. Tegyük fel, hogy q-ra igaz az állítás, azaz a nemnulla kódszavak súlyának a minimuma 2q-1. Amikor q-ról q+1-re lépünk, akkor a generátormátrixnak kétszer annyi sora és eggyel több oszlopa lesz. Legyen G1, q=1_ a_1a_q, ekkor G1, q+1=1_0_a_11_1_a_1 a_qa_q, azaz az új mátrixban az utolsó q oszlopnak és az első oszlopnak az alsó és felső fele egyaránt a régi mátrix megfelelő oszlopa, a második oszlop felső és alsó fele pedig csupa 0, illetve csupa 1. Ez azt jelenti, hogy az új kódszavakat részben a régiek megduplázásával kapjuk, részben pedig úgy, hogy egy régi kódszó után annak komplementerét írjuk. Az utóbbi módon gyártott vektorok súlya nyilván 2q, a duplázottak súlya pedig a kétszerese az eredeti kódszavak súlyának, vagyis az indukciós feltevés szerint (a nemnulla kódszavakra) legalább 2·2q-1=2q.

• b) Jelöljük a kódszavak közötti minimális távolságot d(m,q)-val. A d(m,q)=2q-mállítást (pl.) q+m szerinti teljes indukcióval bizonyíthatjuk. Az m=1 esetet már az a) részben igazoltuk, tehát feltehetjük, hogy q>m≥2. A G(m,q) mátrix oszlopait permutáljuk úgy, hogy a végére kerüljenek mindazok az oszlopok, amelyeknek a felső része csupa 0 (ez az eredeti számozás szerinti második oszlop, valamint annak valahány további oszloppal való szorzata). Ekkor — felhasználva az a) rész meggondolásait is — az alábbi blokkokból álló mátrixot kapjuk: Gm, q-10Gm, q-1Gm-1, q-1. Ez a 10.2.7 feladat III. konstrukciójának felel meg. Ezért

és így az indukciós feltétel szerint