Kódelmélet vizsga 2007. 06. 06.
Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.
Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.
Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót
Tartalomjegyzék
Rendelekzésre álló idő: 50 perc
1. feladat (28 pont)
Tervezzen 2 hibát javító BCH-kódot GF(8) felett!
- Mik a kód paraméterei?
- Adja meg a generátorpolinomot!
- Adja meg a paritásellenőrző polinomot!
- Adja meg bináris alakban a csupa hetest tartalmazó üzenetvektorhoz tartozó kódszóvektort!
Megoldás
a) Ehhez először is meg kell határozni a generátorpolinom gyökeinek számát:
Fel kell írni GF(8) konjugált gyökcsoportjait, ezek a következők:
- [math]\{ y, y^2, y^4 \}[/math]
- [math]\{ y^3, y^6, y^5 \}[/math]
- [math]\{ 1 = y^7 \}[/math]
t = 2 hivát javító kell ,ezért y első [math]2\cdot2=4[/math] darab hatványa mindenképp gyöke kell legyen a generátorpolinomnak. (Ez eddig a [math]y, y^2, y^3, y^4[/math] nagytest-elemeket jelenti) Hogy azonban GF(2) feletti generátorpolinomot kapjunk, azon gyökcsoportok összes elemét is be kell vennünk a gyökök közé, amelyek tartalmaznak olyan testeleme(ke)t, ami(ke)t már beválasztottunk a gyökök közé, így kerül a gyökök közé [math]y^6, y^5[/math].
A generátorpolinom fokszáma (gyökök száma) végülis 6 lett, azaz [math]n-k=6[/math], továbbá [math]n = q^m - 1 = 8 - 1 = 7[/math], tehát ez a kód [math]C(7,1)[/math].
b) A generátorpolinom: [math]g(x) = \sum_{i=1}^{6}(x-y^i) = \ldots = x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1[/math]
(Látható, hogy GF(2) feletti polinommá egyszerűsödött. Ezt az ember vagy kiszámolja favágó módszerrel (az az általánosan célravezető megoldás), de konkrétan ebben az esetben ki lehet használni a tetszőleges test feletti polinomokra érvényes [math]x^n - 1 = (x-1)\sum_{i=0}^{n-1}x^i[/math] azonosságot, miután észrevesszük, hogy a paritásellenőrzőpolinom épp [math]x-1[/math] lesz.)
c) A paritásellenőrző polinom: [math]h(x) = x - 1 [/math]
(a generátorpolinomba be nem vett nagytest-elemek lesznek a gyökei, ebben az esetben ez csak az egységelem volt)
d) Az üzenetvektor hossza [math]k=1[/math], tehát most [math]\underline{u}= (7) = (111)[/math] és [math]c(x)=u(x)g(x)[/math] alapján kijön, hogy [math]\underline{c} = (111,111,111,111,111,111,111)[/math]. (Megj.: a [math]C_{BCH}(7,1)[/math] kód egy olyan kód, ami 7-szer megismétli az üzenet egyetlen szimbólumát)
2. feladat (28 pont)
A C(2/4),L=2, G= {11,9,7,14}
- Hány vízszintes vonal van a trellis diagrammon?
- Mekkora a komplexitása a Viterbi algoritmusnak az 10011111 bemeneti szó esetén?
Megoldás
a) A trellis vízszintes sorainak száma megegyezik az állapotok számával, ami [math]2^{k(L-1)}[/math], azaz ebben az esetben, mivel [math]k=2,L=2[/math] a sorok száma [math]2^{2\cdot 1} = 4[/math].
b) Viterbi komplexitása [math]O(V2^{kL})[/math], ahol [math]V[/math] az üzenet hossza, ami most 4. A megoldás az, hogy [math]O(4\cdot2^4)=O(64)[/math] (ami mellesleg hülyeség matematikailag, mert [math]O(1)=O(64)[/math], de erre egyből meg lehet kapni a pontot, ha pedig az ember ehelyett valami matematikailag is értelmeset ír, akkor eredményhirdetésen el kell magyarázni...)
3. feladat (20 pont)
Adja meg véletlen kódolás esetén a CDMA/DS rendszer bithibavalószínűségét! (+ jelölések magyarázata)
Megoldás
[math]p_b=\phi\left(-\frac{1}{\sqrt{N_0 + \frac{M-1}{N}}}\right)[/math], ahol
- [math]\phi:\mathbb{R}\mapsto[0,1][/math] a normális eloszlás eloszlásfüggvénye (nem sűrűség, ezért nem maradhat le a minusz..)
- [math]N_0 \geq 0[/math] az AGWN(additiv Gaussian White Noise) szórása a csatornán, avagy a zajteljesítmény
- [math]N=\frac{T_s}{T_c}[/math] a szimbóluim- és a chipidő hányadosa
- [math]M[/math] a felhasználók száma
4. feladat (14 pont)
C(7,3) RS kódot [math]\lambda=8[/math] interleaving technikával kódolunk
- Mekkora a bursthibajavító képessége az így kapott kódnak?
- Hogy kell hogy a kódszavakat elküldjük ahhoz, hogy ezt elérjük?
Megoldás
a) A bursthibajavító képesség [math]l = \lambda\cdot t[/math], ahol [math]t[/math] az eredeti kód hibajavító képessége. Az RS-kód MDS, ezért [math]t=\lfloor\frac{n-k}{2}\rfloor[/math], ebben az esetben [math]t=2[/math], tehát [math]l=8\cdot2=16[/math] a bursthibajavító képessége a kódnak.
b) Összevárunk lambda darab kódszót, ezeket egymás fölé írjuk, így kapunk egy [math]\lambda\ *\ n[/math] méretű mátrixot. No ezt küldjük át oszloponként (tehát először minden kódszó első szimbólumát, aztán minden kódszó második szimbólumát, stb)
5. feladat (10 pont)
Miért csak 2D esetben vizsgáltuk az optimális pontelhelyezést a digitális modulációnál?
Megoldás
Na, erre a megoldásra titokzatos módon 10-ből 9 pontot kaptam, ami fura, mert a pontozás általában maxpont vagy zéró. Mindenesetre a következőt írtam:
A jelenleg használt kódolási technológiáknál a jelalakot két folytonos mennyiséggel (amplitudo, és fázis) definiálják. Ezért a lehetséges jelalakok e két dimenzió által meghatározott térben helyezkednek el.
HA olyan modulációs technikát alkalmaz(hat)nánk, ahol a jelalakot három folytonos paraméter írná le, akkor kellene 3D-s optimalizációt csinálni.
Én oda írtam még, hogy a probléma komplexitása nyilvánvalóan nő a dimenziók számával.
-- HuszarFerenc - 2007.06.06.
Szerintem (és ezt el is fogadták): ugyebár a célunk az adott sávszélen való minél több adat áttolása. A kérdés az, hogy egy vivőfrekin hány dimenziót tudunk ábrázolni? Pontosan kettőt, az amplitudót és a fázist. Tehát ha pl 3D-t akarnánk, ahhoz már egy újabb freki kéne, nem lennénk beljebb.
-- MolnarP - 2007.06.06.
Megjegyzés
Megjegyzés a megoldásokhoz: A lent leírt megoldásokra megadták a max. pontot. Az interleaving-esre nem tudom a hivatalos választ, az utolsónál egy ponttal kevesebbet kaptam, mint a max, tehát aki tudja miért, az írja meg! -- HuszarFerenc - 2007.06.06.
