KodelmPzh2007Tavasz

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

KodelmPzh2007Tavasz

1.feladat

Adja meg GF(8) konjugált gyökcsoportjait!

---

Megoldás

A gyökcsoportok elemeinek képzése: [math]y^\alpha, y^{2\alpha}, y^{4\alpha}, ..., y^{(2^l)\alpha}[/math]

[math]y, y^2, y^4, y^8 = y[/math] , mivel GF(8)-ban mod 7-tel számoljuk a kitevőket. Így az egyik csoport { [math]{y, y^2, y^4}[/math] }

[math]y^3, y^6, y^{12} = y^5, y^{10} = y^3[/math] Így a másik csoport { [math]y^3, y^6, y^5[/math] }

Egy harmadik lehetséges csoport az { [math]y^0[/math] }, ami ugye { [math]1[/math] }

2.feladat

Adja meg a vektorreprezentációját a következő polinomnak [math]a(x) = y^6x^5 + y^4x^4 + y^2x^3 + y^3x^2 + y^4x + y^5![/math]

---

Megoldás

Hatványtábla, ahol az irreducibilis polinom : [math]y^3+y+1[/math], és GF(8)terében vagyunk

1	[math]1[/math]	[math] y^0[/math]
2	[math]y[/math]	[math] y[/math]
3	[math]y+1[/math]	[math] y^3[/math]
4	[math]y^2[/math]	[math] y^2[/math]
5	[math]y^2+1[/math]	[math] y^6[/math]
6	[math]y^2+y[/math]	[math] y^4[/math]
7	[math]y^2+y+1[/math]	[math] y^5[/math]

• Az [math]y, 1[/math] és [math]y^2[/math] triviális.
• [math]y^3 = y^3+y+1 +(y+1)[/math]
• [math]y^4 = y*(y^3+y+1) = y^4+y^2+y+(y^2+y)[/math]
• [math]y^5 = y^2*(y^3+y+1) = y^5+y^3+y^2 = y^5+(y+1)+y^2[/math]
• [math]y^6 = y^3*(y^3+y+1) = y^6+y^4+y^3 = y^6+y^2+y+y+1 = y^6+(y^2+1)[/math]

Így [math]\;\underline{a} = (5,6,4,3,6,7)[/math]

3.feladat

Van egy GF(7), C(6,2) paraméterű Reed-Solomon-kód, amelynek primitív eleme a 3. Ismerjük a hibák helyeit: [math]i_1[/math] = 2, [math]i_2[/math] = 3. Határozzuk meg a hibalokátor polinomot! L(x) = ?

[math]\displaystyle{\frac{0 \:1\: 2\: 3\: 4\: 5\: 6}{1\:3\: 2\: 6\: 4\: 5\: 1}}[/math] Ahol a felső sor jelzi a primitív elem kitevőjét, míg az alsó sor a hatvány modulo hetes értékét, így például [math]3^2 = 9 = 2 \;mod7 [/math] Tudjuk, hogy [math]\displaystyle{i_1 = \log_3 \,x^{-1}}[/math], ahol x a hibalokátor polinom gyöke. [math]\displaystyle{x_1^{-1} = 2 \;\; x_1 = 4}[/math] és [math]\displaystyle{ x_2^{-1} = 6 \;\; x_2 = 6}[/math] Ebből [math]L(x) = (x-4)(x-6) = x^2+4x+3[/math]

6.feladat

Kódosztásos DS (CDMA/DS) [math]T_{symb} = 16* T_{chip}[/math]. Maximum hány felhasználó lehet a rendszerben?

[math]\displaystyle{N = \frac{T_s}{T_c}}[/math] és [math]max 2^l = M \leq N [/math], ahol M a felhasználók száma ezúttal. Mivel N = 16, ami kettő negyedik hatványa, így M = 16 szintén. Így a térben 16 db ortogonális kód van. (Mivel 16 dimenziós is egyben.) Ha M = 22 a felhasznló, akkor a jelzaj-viszony változása: [math]\frac{M-1}{N} = \frac{21}{16}[/math]

7.feladat

Adott egy konvolúciós kodoló architektúrája. Adja meg a szabványos leírását!

A konvolúciós kodoló architektúrája:

Ezen a helyen volt linkelve a konvkodarch.GIF nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

[math]C(\frac{2}{2})[/math], k=2, mivel kettő hosszú üzenet érkezik mindig (ennyi egy "blokk" mérete), és n = 2, mert kettő darab pontból olvassa le az értéket a kódoló. L = 2, mivel 2 db shift-regiszter van. G{11,13}, mivel a 11 és a 13 binárisan jelzi, hogy melyik egység van bekötve az összeadóhoz és melyik nincs.

8.feladat

Egy 101101 üzenetet küldünk és a Viterbi algoritmussal dekódoljuk.

/a Mekkora ennek a komplexitása?

[math]O(V2^{kL})[/math], ahol [math]V[/math] az órajelütés és [math]L[/math] valamint [math]k[/math] pedig megegyezik a 7-es feladattal. V = 3 [math]\Leftarrow[/math] 10|1101. Így O(48)

/b Mennyi a Trallis-diagram vízszintes vonalainak a száma?

[math]2^{(L-1)k}[/math], mivel ennyi az állapotok száma.

/c Mennyi a kiterjesztett transzfergráf csomópontjainak a száma?

[math]2^{(L-1)k}+1[/math], mivel itt eggyel több állapot van, ugyanis a kezdőállapotot szétszedjük egy kezdő és egy végállapotra.

9.feladat

Adott egy GF(8) kód, melynek generátorpolinoma [math]g(x) = x^3+y^6x^2+yx+y^2[/math]. Az üzenetvektor bináris formája [math]\underline{u} = (1 1 1, 1 1 1, 1 1 1, 1 1 1)[/math]. Mi a kód polinomja? Ciklikus-e a kód? RS-kód-e? Mivel van generátorpolinom, ezért tudjuk, hogy ciklikus a kód. Lehet RS-kód, ha a [math]g(x) = \prod_{i=1}^{n-k} (x-y^i)[/math] alakban írható fel. [math]\prod_{i=1}^{n-k} (x-y^i) = (x-y)(x-y^2)(x-y^3) = (x^2+y˘3x+y^3)(x-y^3) = \: x^3+y^4x^2+y^3x+y^3x+yx+y^6 = x^3+y^6x^2+yx+y^6[/math]

Így ez egy RS-kód.

Az üzenet polinomja így [math]u(x)=y^5x^3+y^5x^2+y^5x+y^5[/math], ahol az [math]y^5[/math]-ök az [math]1\; 1\; 1[/math] bináris alakból adódik, lásd 2.feladat hatványtáblája.

[math]c(x) = g(x)u(x) = (x^3+y^6x^2+yx+y^2)(y^5x^3+y^5x^2+y^5x+y^5)= .... = y^5x^6+x^5+y^2x^4+y^6x^3+yx^2+y^2x+1 \:\Rightarrow \underline(c) = (111,001,100,101,010,100,001)[/math]

10.feladat

Adott egy konolúciós kodoló [math]\displaystyle{T(D, J, N) = \frac{J^3ND^6}{1-JND^2(1+J)}}[/math] Hány bemeneti egyes hatására lehet öt lépéses nyolcsúlyú utat "bejárni"?

Sorbafejtjük: [math]\displaystyle{T(D, J, N) = \frac{J^3ND^6}{1-JND^2(1+J)} = J^3ND^6 + J^4N^2D^8 + J^5N^2D^8+...}[/math], ahol a [math]J[/math] jelenti az ugrások számát, [math]N[/math] a bementi egyesek számát, [math]D[/math] a súlyt.