KodelmPzh2007Tavasz

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.

KodelmPzh2007Tavasz

1.feladat

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

---

Megoldás

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

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

$y^{3},y^{6},y^{12}=y^{5},y^{10}=y^{3}$ Így a másik csoport { $y^{3},y^{6},y^{5}$ }

Egy harmadik lehetséges csoport az { $y^{0}$ }, ami ugye { $1$ }

2.feladat

Adja meg a vektorreprezentációját a következő polinomnak $a(x)=y^{6}x^{5}+y^{4}x^{4}+y^{2}x^{3}+y^{3}x^{2}+y^{4}x+y^{5}!$

---

Megoldás

Hatványtábla, ahol az irreducibilis polinom : $y^{3}+y+1$, és GF(8)terében vagyunk

1	$1$	$y^{0}$
2	$y$	$y$
3	$y+1$	$y^{3}$
4	$y^{2}$	$y^{2}$
5	$y^{2}+1$	$y^{6}$
6	$y^{2}+y$	$y^{4}$
7	$y^{2}+y+1$	$y^{5}$

• Az $y,1$ és $y^{2}$ triviális.
• $y^{3}=y^{3}+y+1+(y+1)$
• $y^{4}=y*(y^{3}+y+1)=y^{4}+y^{2}+y+(y^{2}+y)$
• $y^{5}=y^{2}*(y^{3}+y+1)=y^{5}+y^{3}+y^{2}=y^{5}+(y+1)+y^{2}$
• $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)$

Így $\;{\underline {a}}=(5,6,4,3,6,7)$

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: $i_{1}$ = 2, $i_{2}$ = 3. Határozzuk meg a hibalokátor polinomot! L(x) = ?

Értelmezés sikertelen (formai hiba): {\displaystyle \displaystyle{\frac{0 \:1\: 2\: 3\: 4\: 5\: 6}{1\:3\: 2\: 6\: 4\: 5\: 1}}} 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 $3^{2}=9=2\;mod7$ Tudjuk, hogy $\displaystyle {i_{1}=\log _{3}\,x^{-1}}$, ahol x a hibalokátor polinom gyöke. $\displaystyle {x_{1}^{-1}=2\;\;x_{1}=4}$ és $\displaystyle {x_{2}^{-1}=6\;\;x_{2}=6}$ Ebből $L(x)=(x-4)(x-6)=x^{2}+4x+3$

6.feladat

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

$\displaystyle {N={\frac {T_{s}}{T_{c}}}}$ és $max2^{l}=M\leq N$, 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: ${\frac {M-1}{N}}={\frac {21}{16}}$

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)

$C({\frac {2}{2}})$, 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?

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

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

$2^{(L-1)k}$, mivel ennyi az állapotok száma.

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

$2^{(L-1)k}+1$, 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 $g(x)=x^{3}+y^{6}x^{2}+yx+y^{2}$. Az üzenetvektor bináris formája ${\underline {u}}=(111,111,111,111)$. 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 $g(x)=\prod _{i=1}^{n-k}(x-y^{i})$ alakban írható fel. É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 \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}

Így ez egy RS-kód.

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

Értelmezés sikertelen (formai hiba): {\displaystyle 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)}

10.feladat

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

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