Kódelmélet vizsga 2007. 06. 06.
Ez az oldal a korábbi SCH wikiről lett áthozva.
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.
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:
- Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{ y, y^2, y^4 \}}
- Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{ y^3, y^6, y^5 \}}
- Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{ 1 = y^7 \}}
t = 2 hivát javító kell ,ezért y első Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2\cdot2=4} darab hatványa mindenképp gyöke kell legyen a generátorpolinomnak. (Ez eddig a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle y, y^2, y^3, y^4} 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é Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle y^6, y^5} .
A generátorpolinom fokszáma (gyökök száma) végülis 6 lett, azaz Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n-k=6} , továbbá Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n = q^m - 1 = 8 - 1 = 7} , tehát ez a kód Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle C(7,1)} .
b) A generátorpolinom: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle g(x) = \sum_{i=1}^{6}(x-y^i) = \ldots = x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1}
(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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x^n - 1 = (x-1)\sum_{i=0}^{n-1}x^i} azonosságot, miután észrevesszük, hogy a paritásellenőrzőpolinom épp Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x-1} lesz.)
c) A paritásellenőrző polinom: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle h(x) = x - 1 }
(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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k=1} , tehát most Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \underline{u}= (7) = (111)} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle c(x)=u(x)g(x)} alapján kijön, hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \underline{c} = (111,111,111,111,111,111,111)} . (Megj.: a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle C_{BCH}(7,1)} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2^{k(L-1)}} , azaz ebben az esetben, mivel Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k=2,L=2} a sorok száma Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2^{2\cdot 1} = 4} .
b) Viterbi komplexitása Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(V2^{kL})} , ahol Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle V} az üzenet hossza, ami most 4. A megoldás az, hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(4\cdot2^4)=O(64)} (ami mellesleg hülyeség matematikailag, mert Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(1)=O(64)} , 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
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle p_b=\phi\left(-\frac{1}{\sqrt{N_0 + \frac{M-1}{N}}}\right)} , ahol
- Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \phi:\mathbb{R}\mapsto[0,1]} a normális eloszlás eloszlásfüggvénye (nem sűrűség, ezért nem maradhat le a minusz..)
- Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle N_0 \geq 0} az AGWN(additiv Gaussian White Noise) szórása a csatornán, avagy a zajteljesítmény
- Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle N=\frac{T_s}{T_c}} a szimbóluim- és a chipidő hányadosa
- Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle M} a felhasználók száma
4. feladat (14 pont)
C(7,3) RS kódot Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \lambda=8} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle l = \lambda\cdot t} , ahol Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} az eredeti kód hibajavító képessége. Az RS-kód MDS, ezért Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t=\lfloor\frac{n-k}{2}\rfloor} , ebben az esetben Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t=2} , tehát Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle l=8\cdot2=16} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \lambda\ *\ n} 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.
