All the Dimat

Számelmélet

1. Definiálja az oszthatóságot egész számok körében!

Az \(a\) egész osztja a \(b\) egészet: \(a \;|\; b\) ha létezik olyan \(c\) egész, hogy \(a \cdot c = b\).

2. Mondja ki a maradékos osztás tételét!

\(\Z \ni a\), \(b \neq 0:\;\exists!\,q, r\in\Z\)

\[ a = b\cdot q + r\quad(0 \leq r < |b|) \]

3. Definiálja a legnagyobb közös osztót!

Legyenek \(a, b \in\Z\). Ekkor \(d\in\Z^+\) az \(a\) és \(b\) legnagyobb közös osztója, ha:

\(d \mid a \;\) és \(\; d \mid b\);
\(\forall k\in\Z:\; k \mid a,\;k \mid b\implies k \mid d\).

Jelölése: \(d = (a, b) = \text{lnko}(a, b) = \gcd(a, b)\)

Továbbá: \((0, 0) := 0\)

4. Mondja ki a lineáris diofantikus egyenletek megoldhatóságáról szóló tételt!

Minden \(a\), \(b\), \(c\) egész számok esetén pontosan akkor léteznek \(x\), \(y\) egészek, hogy

\(x \cdot a + y \cdot b = c\), ha \((a, b) | c\)

\[ x_0 = \frac{c}{(a, b)}\cdot x_0' \]

\[ y_0 = \frac{c}{(a, b)}\cdot y_0' \]

\[ x_t = x_0 + \frac{b}{(a, b)}\cdot t \]

\[ y_t = y_0 - \frac{a}{(a, b)}\cdot t \]

5. Definiálja a prímszámokat!

Egy \(p \in \Z \; \land \; p \notin \{-1, 0, 1\}\) szám prímszám, ha:

\(p = a \cdot b \implies p = \pm\,a~~\) vagy \(~~p = \pm\,b\)

6. Mondja ki a számelmélet alaptételét!

Minden \(n \neq 0,\pm\,1\) egész szám sorrendtől és előjeltől eltekintve egyértelműen felírható prímszámok szorzataként:

\[ n = \pm p_1^{\alpha_1} \cdot p_2^{\alpha_2} \dots p_{\ell}^{\alpha_\ell} = \pm\,\underset{i=1}{\overset{\ell}{\Large{\Pi}}}\;p_i^{\alpha i} \]

ahol \(p_1\), \(p_2\), ..., \(p_{\ell}\) pozitív prímek, \(\alpha_1\), \(\alpha_2\), ..., \(\alpha_\ell\) pozitív egészek.

7. Definiálja a kongruencia relációt!

Adott \(n \ne 0\) és \(a, b\) egészek esetén (mondhatjuk, hogy \(a\) kongruens \(b\)-vel modulo \(n\))

\[ n \mid a-b \implies a \equiv b \mod n \]

8. Jellemezze a kongruenciát, mint reláció!

A kongruencia egy ekvivalencia reláció:

Reflexivitás: \(a \equiv a \mod n\) hiszen: \(n | a − a = 0\)
Tranzitivitás: \(a \equiv b \mod n\) és \(b \equiv c \mod n \implies a \equiv c \mod n\)
Szimmetria: \(a \equiv b \mod n \implies b \equiv a \mod n\)

9. Mondja ki a kongruencia és az alapműveletek közötti összefüggésre vonatkozó tételt!

Legyenek \(a, b, c, d, n \in \mathbb{Z}, n \neq 0\)

\(a \equiv b \mod n\) és \(c \equiv d \mod n\) esetén \(a + c \equiv b + d \mod n\)
\(a \equiv b \mod n\) és \(c \equiv d \mod n\) esetén \(a \cdot c \equiv b \cdot d \mod n\)
\(ab \equiv ac \mod n \iff b \equiv c \mod \dfrac{n}{(a,n)}\)

10. Mondja ki a lineáris kongruenciák megoldhatóságára vonatkozó tételt!

Legyenek \(a\), \(b\), \(n\) egész számok, \(n > 1\). Ekkor az \(ax \equiv b \mod n\) megoldható \(\iff (a, n)\;|\; b\). Ez esetben pontosan \((a, n)\) darab inkongruens megoldas van mod \(n\).

11. Mondja ki a kinai maradéktételt!

Legyenek \(1 < n_1, n_2, \dots, n_k\) páronként relatív prím számok, \(c_1, c_2, \dots, c_k\) egészek.

Ekkor a

\[ \begin{drcases}x \equiv c_1 \bmod n_1\\ x \equiv c_2 \bmod n_2 \\ x \equiv c_k \bmod n_k \end{drcases} \]

kongruencia rendszer megoldható, és bármely két megoldás kongruens egymással modulo \(n_1 \cdot n_2 \dots n_k\)

12. Definiálja az Euler-féle \(\varphi\) függvényt!

Df.: \(n \in \N^{+},\, n > 1\) kanonikus alak:

\(\varphi(n) = \#\{ 1 \le a \le n \; | \; lnko (n,a) = 1 \}\)

13. Definiálja egy szám prímtényezős felbontását az Euler-féle \(\varphi\) függvény segítségével!

Legyen \(n\) prímtényezős felbontása \(n = p^{e_1}_1 p^{e_2}_2 \dots p^{e_\ell}_{\ell}\). Ekkor

\[ \varphi (n) = n \cdot \overset{\ell}{\underset{i=1}{\large{\Pi}}} (1 - \dfrac{1}{p_i}) \]

14. Mondja ki az Euler–Fermat-tételt!

Legyenek \(a, n \in \Z, (a, n) = 1\) Ekkor

\[ a^{\varphi(n)} \equiv 1 \bmod n \]

ahol \(\varphi\) az Euler-féle függvény.

15. Definiálja a generátort!

Legyen \(p\) prímszám. Ekkor \(\mathbb{Z}_{p}^{*}\)-ban van generátor (primitív gyök): van olyan \(1 < g < p\) egész, melyre,

\[ \{1 = g^0, g \;\text{mod}\; p, g^2 \;\text{mod}\; p, \dots, g^{p-2} \;\text{mod}\; p\} = \mathbb{Z}_{p}^{*} = \{1, 2, \dots, p-1\} \]

Example

3 generátora mod 7 például:

\[ 3^0 = \;\;1 \equiv 1 \quad\mod 7 \\ 3^1 = \;\;3 \equiv 3 \quad\mod 7 \\ 3^2 = \;\;9 \equiv 2 \quad\mod 7 \\ 3^3 = \;27 \equiv 6 \quad\mod 7 \\ 3^4 = \;81 \equiv 4 \quad\mod 7 \\ 3^5 = 243 \equiv 5 \quad\mod 7 \]

Tehát a 3 hatványaiból ellőállítható a \(\mathbb{Z}_7\) összes eleme, azaz kigenerálja az összes elemét. (Kivéve a 0-t, hiszen azt lehetetlen előállítani ilyen módon.)

16. Definiálja a diszkrét logaritmust! Ha \(g = 3\) generátor modulo \(17\) és \(\log_3 2 = 14\), akkor mennyi lesz \(\log_3 12\)?

Legyen \(p\) prímszám, \(g\) generátor \(p\). Ekkor \(a \in \mathbb{Z}: (p \not|\; a)\; g\) alapú diszkrét logaritmusa (indexe):

\[ \log_g a = n \implies a \equiv g^n \;\text{mod}\; p, \quad 0 \leq n < p - 1 \]

\[ \log_3 2 = 14 \implies 2 \equiv 3^{14} \mod 17 \\ \log_3 12 = x \implies 12 \equiv 3^x \mod 17 \]

\[ \log_3 12 = \log_3 4 + \log_3 3 \\ \log_3 4 = \log_3 2 + \log_3 2 \\ \log_3 2 = 14 \land \log_3 3 = 1 \\ 1 + 14 + 14 = 29 \\ 29 \;\text{mod}\; (p-1) \\ 29 \;\text{mod}\; 16 = 13 \]

17. Milyen műveleteket értelmezünk diszkrét logaritmusokkal?

Legyen \(p\) prímszám, \(g\) generátor \(p\). \(1 \leq a,b < p, n \in \mathbb{Z}\). Ekkor:

Szorzás:

\[ \log_g (a \cdot b) \equiv \log_g a + \log_g b \mod (p-1) \]

Hatványozás:

\[ \log_g (a^n) \equiv n \cdot \log_g a \mod (p-1) \]

Polinomok

\(\mathbb{K}\) my beloved

\(\mathbb{K}\in\{\mathbb{C},\;\R,\;\mathbb{Q},\;\Z,\;\Z_p\}\)

(kivéve ahol explicit ki van kötve másnak)

18. Mi a polinom?

A \(\mathbb{K}\) fölötti polinomok halmaza \(\mathbb{K}[x]\), azaz \(x\) és \(\mathbb{K}\) elemei által a \(+\), \(-\), és a \(\cdot\) kombinálásával alkotott formális kifejezések, másképp fogalmazva:

\[ \mathbb{K}[x] = \{c_nx^n+\dots+c_0 : n \geq 0, c_n, \dots, c_0 \in \mathbb{K}\} \]

Adott polinom \(f = c_nx^n+\dots+c_0\) együtthatói a \(c_n, \dots, c_0\) számok, míg ha \(c_n \neq 0\) is igaz, akkor \(f\) foka \(\deg f = n\) és főegyütthatója \(c_n\).

19. Definiálja a polinomok fokát!

\(f=c_nx^n+\cdots+c_0\quad (c_n,\ldots,c_0\in\mathbb{K},\;c_n\ne0)\)

Ekkor \(\deg f:=n\)

20. Definiálja a maradékos osztást polinomok körében!

Legyen \(f, g \in \mathbb{K}[x], g \neq 0\) Ekkor léteznek olyan \(q, r \in \mathbb{K}[x]\) polinomok, hogy

\[ f = q \cdot g + r \quad\quad \deg r < \deg g \]

21. Mondja ki a gyöktényező kiemelhetőségére vonatkozó tételt!

Legyen \(f\in\mathbb{K}[x]\) és \(x_1\in\mathbb{K}\) (\(x_1\; f\)-nek egy gyöke!)

Ekkor \(f\) felírható az \(f=(x-x_1)\cdot g\quad(g\in \mathbb{K}[x])\)

22. Mondja ki a polinom foka és gyökeinek száma közötti összefüggést!

\(f\in\mathbb{K}[x]\) polinomnak legfeljebb \(\deg f\) gyöke lehet

\(\large{Viszont\;\Z_x\not\in\Z_{p}}\) felett nem igaz

23. Mondja ki az oszthatóságot polinomokra értelmezve!

Legyenek \(f, g \in \mathbb{K}[x]\) \(f\) osztja \(g\)-t (\(f \;|\; g\)), ha létezik olyan \(h \in \mathbb{K}[x]\) hogy \(f \cdot h = g\)

Másképpen:

\[ f, g \in \mathbb{K}[x],\quad \exists h \in \mathbb{K}[x]: f \cdot h = g \implies f \;|\; g \]

24. Definiálja polinomok legnagyobb közös osztóját!

Két polinom \(f\) és \(g\) legynagyobb közös osztója, \(h = (f, g) = lnko(f,g)\) , ha

közös osztó: \(h \mid f \land h \mid g\) ;
legynagyobb : \(\forall q\in\mathbb{K}[x]:\; q\mid f~\land\;q\mid g \implies q\mid h\)
\(h\) föegyütthatója 1.

25. Milyen polinomoknak van legnagyobb közös osztója?

Bármely két \(f\), \(g\) polinomnak létezik legnagyobb közö osztója. (és az meghatározható az euklideszi algoritmussal)

26. Írja le a bővített euklideszi algoritmust polinomok körében!

Minden \(f\), \(g\) polinomok esetén léteznek \(u\), \(v\) polinom hogy \((f, g) = uf + vg\)

27. Definiálja a formális deriváltat!

Polinomokra definiáljuk a \(f'\) formális deriváltat a következő módon:

\((x^n)' = n*x^{n-1}\)
\((c\cdot f)' = c \cdot f'\)
\((f + g)' = f' + g'\)

Ekkor teljesül az alábbi azonosság is:

\((f \cdot g)' = f' \cdot g + f \cdot g'\)

28. Mikor többszörös gyök egy adott gyök?

Egy adott \(f\) polinomnak az \(x_1\) érték többszörös gyöke, ha mind \(f\)-nek, mind \(f'\)-nak gyöke. Speciálisan \(f\) többszörös gyökei az \(\text{lnko}(f, f')\) gyökei.

29. Mikor nincs többszörös gyöke egy polinomnak?

Az \(f\) polinomnak nincs többszörös gyöke ha \(\text{lnko}(f, f') = 1\)

30. Mondja ki az Algebra alaptételét!

Legyen \(f \in \mathbb{C}[x]\) egy pozitív fokú polinom: \(\deg f \geq 1\). Ekkor \(f\)-nek van gyöke.

(Fontos hogy ez csak \(\mathbb{C}[x]\) polinomokra igaz!!)

31. Definiálja az irreducibilis polinom fogalmát!

Egy \(f\) polinom irreducibilis, ha nem bontható szorzatra nem-triviális módon, azaz

\[ f = g * h \implies \deg g = \deg f \; \text{vagy} \; \deg h = \deg f \]

32. Mikor irreducibilis egy polinom?

Egy \(f\) polinom pontosan akkor irreducibilis, ha prím tulajdonságú, azaz

\[ f \;|\; g \cdot h \implies f \;|\; g \lor f \;|\; h \]

33. Mondja ki a számelmélet alaptételét polinomokra!

Minden \(f \in \mathbb{K}[x]\) polinom felírható

\[ f = a \cdot f_1 \dots f_\ell \quad\quad a \in \mathbb{K}, f_1, \dots, f_\ell \in \mathbb{K}[x] \]

alakban, ahol (\(f_1, \dots, f_\ell\)) irreducibilis polinomok melyek együtthatója 1, és a felírás sorrendtől eltekintve egyértelmű.

34. Definiálja a kongruencia relációt polinomok körében!

\(h\in K[x]\) nem nulla polinom.

Ekkor \(f,g\in\mathbb{K}[x]:\)

\[ h\mid f-g\;\implies\;f\equiv g \mod h \]

35. Jellemezze a polinomok kongruenciáját relációként!

A kongruencia ekvivalencia reláció, azaz: \(f, g, h \in \mathbb{K}[x]\) esetén:

Reflexív: \(f \equiv f \mod h\)
Tranzitív: \(f \equiv g \mod h, g \equiv k \mod h \implies f \equiv k \mod h\)
Szimmetrikus: \(f \equiv g \mod h \implies g \equiv f \mod h\)

36. Milyen műveleteket ismerünk polinomok kongruenciájával kapcsolatban?

A kongruencia kompatibilis az összeadással és a szorzással, azaz \(a, b, c, d, n \in \mathbb{K}[x]\) esetén

\(a \equiv b \mod n, c \equiv d \mod n \implies a + c \equiv b + d \mod n\)
\(a \equiv b \mod n, c \equiv d \mod n \implies a \cdot c \equiv b \cdot d \mod n\)

37. Mondja ki a test fogalmát!

Legyen \(\mathbb{K}\) egy test és \(f \in \mathbb{K}[x]\) egy irreducibilis polinom. Ekkor \(\{h \;\text{mod}\; f | h \in \mathbb{K}[x]\}\) testet alkot. Ennek jelölése \(\mathbb{K}[x]/(f)\).

38. Mi a véges test?

Egy számkör véges testet alkot, ha test, és véges sok eleme van.

Example

Véges testek: \(\mathbb{Z}_2, \mathbb{Z}_3, \dots, \mathbb{Z}_p\)

Nem véges testek:

\(\mathbb{C}, \mathbb{R}, \mathbb{Q}\) (testek, de nem végesek)
\(\mathbb{Z}_6, \mathbb{Z}_8, \dots\) (végesek, de nem testek)

39. Mikor véges egy test?

Miden \(q\) prímhatvány esetén létezik \(q\) elemszámú véges test. Ez lényegében egyértelmű, mondhatni triviális, jelölése \(\mathbb{F}_q\).

40. Mondja ki a Lagrange interpolációról szóló tételt!

Legyen

\[ L_i=\underset{j\ne i}{\underset{j=0}{\overset{n}{\prod}}}\dfrac{x-x_i}{x_j-x_i} \qquad f=\underset{j=1}{\overset{n}{\sum}}y_iL_i \]

Legyenek \(x_0,x_1,\ldots,x_n\in \mathbb{C}\) páronként különböző alappontok és \(y_0,y_1,\ldots,y_n\in\mathbb{C}\) tetszőleges értékek.

\[ n\in\N^+:\exists!f\in\mathbb{C}[x]:\; \deg f< n\,;\;f(x_i)=y_i \]

Kódelmélet

41. Definiálja a betűnkénti kódolás fogalmát! Betűnkénti kódolás lesz-e a \(\varphi(a)=01,\;\varphi(b)=11,\;\varphi(c)=01\) függvény?

Df.: Legyen \(\mathcal{X} = \{x_1, x_2, \dots , x_n \}\) halmaz a forrásábécé és \(\mathcal{Y} = \{ y_1, y_2, \dots , y_k \}\) a kódábécé. Ekkor egy \(\varphi : \mathcal{X} \rightarrow \mathcal{Y}^*\) injektív függvényt kódolásnak (vagy betűnkénti kódolásnak) hívunk.

Itt \(\mathcal{Y}^*\) az \(\mathcal{Y}\) elmeiből álló véges szavak halmaza.

A \(\varphi\) függvényt kiterjesztjük a \(\mathcal{X}^*\) halmazra betűnként:

\(\varphi ( u_1, u_2, \dots , u_r ) = \varphi ( u_1 ), \varphi (u_2), \dots , \varphi (u_r)\)

Nem, hiszen a \(\varphi\) nem injektiv, hiszen \(\varphi(a)=\varphi(c)\)

42. Definiálja a felbontható kódolás fogalmát! Felbontható kódolás lesz-e a \(\varphi(a)=01,\;\varphi(b)=11,\;\varphi(c)=10\) függvény?

Df.: Legyen \(\varphi : \mathcal{X} \mapsto \mathcal{Y}^*\) kódolás felbontható (vagy egyértelműen dekódolható), ha

\(u, v \in \mathcal{X}^*, \, u = u_1u_2 \dots u_r, \, v = v_1v_2 \dots v_s\) esetén, ha \(u \neq v\), akkor

\[ \varphi (u_1) \varphi(u_2) \dots \varphi(u_r) \neq \varphi(v_1) \varphi(v_2) \dots \varphi(v_s) \]

Felbontható, hiszen egyenletes kód.

Egyenletes kód

\(\varphi\) minden kódolásának hossza megegyezik (jelen esetben 2)

43. Definiálja a prefix kódok fogalmát! Adjon meg az \(\{a, b, c\}\) forrásábécén egy prefix kódolását!

Note

Egy \(u = abc\) szó esetén:

\(u\) prefixei: \(a, ab, abc\);
\(u\) infixei: \(b, ab, bc, abc\);
\(u\) szuffixei: \(c, bc, abc\).

Df.: Egy \(\varphi\) kódolás prefix kód (vagy prefixmentes kód), ha nem léteznek olyan \(u,v\) különböző kódszavak, hogy \(u\) prefixe \(v\)-nek.

Minden prefix kód felbontható.

\(\mathcal Y = \{0, 1\}\)

\(\varphi(a) = 00\)

\(\varphi(b) = 01\)

\(\varphi(c) = 1\)

44. Definiálja az egyenletes illetve vesszős kódot!

Legyen \(\mathcal{C} \subset \mathcal{Y}^*\) a kódszavak véges halmaza. Ekkor

A \(\mathcal{C}\) kód egyenletes kód, ha minden \(c \in \mathcal{C}\) kódszó hossza azonos.
A \(\mathcal{C}\) kód vesszős kód, ha van olyan \(v \in \mathcal{Y}*\) nemüres szó ("vessző"), mely szuffixe minden \(c \in \mathcal{C}\) kódszónak, de nem valódi prefixe, illetve infixe semelyik kódszónak. (Azaz \(c = uv\) valamely \(u \in \mathcal{Y}^*\) szóra, de \(c \neq uvz\) valamely \(u, z \in \mathcal{Y}^*, z \neq \emptyset\) esetén)

Minden egyenletes illetve vesszős kód prefix kód is.

45. Definiálja a kódfa fogalmát! Rajzolja fel a \(\{100,\;101,\;11,\;000\}\) kód kódfáját!

Egy \(\varphi\) kódfája egy olyan fa, melynek csúcsai a (kódszavak és azok prefixei) és az (\(y_1 y_2 \dots y_s\) és \(y_1 y_2 \dots y_s y_{s+1}\)) csúcsok vannak összekötve.

Gráf

46. Definiálja a Hamming-távolságot! Mennyi lesz \(d(010, 110) =?, d(0000, 0009) =?\)

(\(\sum\) egy ábécé, \(\sum ^n\) az n hosszú karaktersorok halmaza)

Df.: Legyen \(u,v \in \sum ^n\) két szó. A szavak Hamming-távolsága: \(d(u,v) = \# \{i: u_i \neq v_i \}\)

Magyarázó:

Df.: Legyen \(\sum\) egy véges halmaz (ábécé) és tekintsük az \(n\) hosszú szavak halamzát \(\sum^n\). Ekkor a \(C \subset \sum^n\) részhalmaz egy kód, elmei a kódszavak.

\(F_2\)

Tipikusan \(\sum = \mathbb{F}_2\) vagy általában \(\mathbb{F}_{2^k}\)

(itt \(\mathbb F_q\) a véges terek (\(GF(q)\))) (Tereknél pedig, hogy az osztás definiálható legyen, ahhoz az alapnak valamilyen prím hatványnak kell lennie)

47. 2 meg prím, úgyhogy az azért jó

\(d(010, 110)=\#\{1\}=1\)

\(d(0000, 0009)=\#\{4\}=1\)

48. Milyen tulajdonságai vannak a Hamming távolságnak?

Legyen \(d : \sum^n \times \sum^n \rarr \{0, 1, 2, \dots\}\) a Hamming távolság. Ekkor

\(d(u, v) = 0 \iff u = v\)
\(d(u, v) = d(v,u)\)
\(d(u, v) \leq d(u, c) + d(c,v)\) (háromszög egyenlőtlenség)

49. Definiálja egy kód kódtávolságát!

Egy \(\mathcal{C} \subset \sum^n\) kód kódtávolsága a kódszavak közti minimális távolság, azaz:

\[ d(\mathcal{C}) = \min\{d(u, v) : u, v \in \mathcal{C}, u \neq v\} \]

50. Mondja ki a kód kódtávolsága és a hibajelző, hibajavító képesség közötti összefüggést! Hány hibát jelez ill. javít a \(C\) kód, ha \(d(C) = 8\)?

d függvény kiterjesztése halmazra

\(d(\mathcal C) = \min\{d(u, v):q, v \in \mathcal C, u \ne v\}\)

Tehát két helyes kódolás közötti legkisebb Hamming-távolság

\(d\) akkor minden szóra lehívja \(d\)-t és abból a legkissebbet veszi.

Egy \(\mathcal{C}\) kód \(d = d(\mathcal{C})\) kódtávolsággal:

\(d - 1\) hibát tud jelezni;
\(t = \lfloor (d-1) / 2 \rfloor\) hibát tud javítani

Magyarázat

Ha a paritásbites megoldást nézzük, akkor egy hibára jelezni fog a rendszer, de nem tudja megmondani, hogy hol van.

Egyéb példa: ismétlő kódolás (d=3)

0110 -> 000 111 111 000

Ha feltételezzük, hogy \(d-1=2\)-nél nem több hiba (bitflip) fordult elő a stringben, akkor észlelni lehet, hogy hiba történt. pl

000 111 010 000 - hiba történt, láthatóan a harmadik részben, de nem egyértelmű, hogy mi lehetett az eredeti

Ha feltételezzük, hogy \(\lfloor\frac{d-1}{2}\rfloor=1\)-nél nem több hiba fordult elő a stringben, akkor a hibát javítani is lehet. pl

000 111 011 000 - kijavítható az eredeti stringre

51. Definiálja a Singleton-korlátot tetszőleges (nem feltétlen lineáris) kódokra!

Egy \(\mathcal{C} \subset \sum^n\) kód \(d = d(\mathcal{C})\) minimális távolság esetén: \(\#\mathcal{C} \leq (\#\sum)^{n-d+1}\).

52. Definiálja a lineáris kódok fogalmát! Lineáris lesz-e a \(\mathcal C=\{110, 101, 111\}\subset\Z^3_2\) kód?

Egy \(\mathcal{C} \subset \mathbb{F}^n_q\) kód (all outputs) lineáris, ha \(\mathcal{C}\) egy lineáris altér \(\mathbb{F}^n_q\) -ben. Ekkor \(k = \dim \mathcal{C}\) a kód dimenziója. Ekkor \(\# \mathcal{C} = q^k\) és \(\mathcal{C}\) egy \((n, k)\) kód.

Lineáris kódok

Példa:

\(\green{(0, 0, 1)}, \blue{(0, 1, 0)}, \orange{(0, 1, 1)}\)

ezek lineáris kombinációi lineáris alteret alkotnak:

\(\{(0, 0, 0), (0, 1, 0), (0, 0, 1), (0, 1, 1)\} = \mathcal C\)

\(k=\dim (\mathcal C) = 2\), hiszen \(\dim \begin{bmatrix} \blue0 & \green0 & \orange0 \\ \blue0 & \green1 & \orange1 \\ \blue1 & \green0 & \orange1 \end{bmatrix} = 2\)

\(\#C = q^k\)

Ekkor \(\mathcal C\)-t egy \((n, k)\) kódnak nevezzük

Közérthetően

Az outputok előállíthatóak vektorok lineáris kombinációjaként.

Mivel \(000 \notin \mathcal C\), ezért nem lehetséges, hogy \(\mathcal C\) lineáris altér legyen, tehát nem lineáris kód.

53. Definiálja a Hamming súlyt!

Legyen \(\mathcal{C} \subset \mathbb{F}_q^n\) egy kód. Az \(u \in \mathcal{C}\) egy kódszó Hamming súlya: \(w(u) = \#\{i : u_i \neq 0\}\). Tehát azon karakterek száma amelyek nem 0.

Egy lineáris \(\mathcal{C} \subset \mathbb{F}_q^n\) kód súlya: \(w(\mathcal{C}) = \min\{w(c) \;|\; c \in \mathcal{C} \setminus \{0\}\}\)

54. Milyen összefüggést ismer a Hamming súly és a Hamming távolság között lineáris kódok esetén?

Legyen \(\mathcal{C}\) egy lineáris kód. Ekkor \(d(\mathcal{C}) = w(\mathcal{C})\)

55. Definiálja a Hamming korlátot!

Legyen \(C \subset \mathbb{F}_q^n\) egy lineáris \((n,k)\) kód mely \(t\) hibát tud javítani. Ekkor

\[ \underset{i=0}{\overset{t}{\large{\sum}}} \begin{pmatrix}n \\ i\end{pmatrix} (q-i)^i \leq q^{n-k} \]

56. Mikor perfekt egy kód?

Egy kód perfekt, ha a Hamming-korlátot egyenlőséggel teljesíti.

Példa:

Az ismétlődő kód (\(0 \mapsto 000, 1 \mapsto 111\)) perfekt: \(1 + 3 = 2^{3-1}\)

C generátorai

Oké, szóval tudjuk, hogy \(\mathcal{C}\) akkor lineáris, ha lineáris altér is \(\mathbb{F}_q^n\)-ben, a belőlük alkotott mátrix bázis vektorai a \(\mathcal{C}\) generátorai, és a belőlük alkotott mátrix lesz generátormátrix. (Gauss eliminációt érdemes használni bro)

Mivel többféleképpen elő tud álni a bázis(sorrend felcserélhető), így több generátormátrix is létezik.

57. Definiálja lineáris kódok generátormátrixát! Mi lesz a \((b_1, b_2)\mapsto(b_1,\;b_2,\;b_1+b_2)\) bináris lineáris kód generátormátrixa?

Legyen \(\mathcal{C}\) egy lineáris \((n,k)\) kód \(c_1, \dots, c_k\) generátorokkal. Ekkor a \(\mathcal{C}\) egy generátormátrixa \(G = (c_1,\dots,c_k) \in \mathbb{F}^{n \times k}_q\).

Note

Tehát az altér bázisait/generátorait belepakoljuk egy mátrixba, I guess?

Ez egy szisztematikus kódolás

\(G = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \\ \end{bmatrix}\cdot [b_1,\;b_2]^T = [b_1,\;b_2,\;b_1+b_2]^T\)

58. Definiálja a szisztematikus kódolás fogalmát!

Egy (\(u \mapsto Gu\)) kódolás szisztematikus, ha a kódszavak utolsó \(n-k\) elemét elhagyva a kódolandó szót kapjuk, azaz

\[ G = \begin{pmatrix}I_k \\ B\end{pmatrix}\in \mathbb{F}^{n \times k}_q,\quad B \in \mathbb{F}^{(n-k\times k)}_q \]

alakú.

Note

Magyarul, ha kitöröljük a kód utolsó \(n-k\) tagját, akkor az eredeti kódot kapjuk meg. Fogjuk az identitás mátrixot és a végéhez hozzátoldjuk a B-t, that's it

59. Definiálja lineáris kódok ellenőrzőmátrixát! Mi lesz a \((b_1, b_2)\mapsto(b_1,\;b_2,\;b_1+b_2)\) bináris lineáris kód ellenőrző mátrixa?

Df.: Legyen \(\mathcal{C}\) egy \((n,k)\) kód. Ekkor \(\mathcal{C}\) ellenőrző mátrixa az a \(H \in \mathbb{F}^{(n-k) \times n}_q\) mátrix, melyre \(Hc = 0\) pontosan akkor, ha \(c \in \mathcal{C}\), és ez igaz \(\forall c \in \mathcal{C}\).

Note

Itt igazából a lényeg az hogy minden valid kóddal szorozva az ellenőrző mátrix 0, minden érvénytelen kóddal szorozva pedig a valid kódtól való eltérést fogja megadni.

\(\begin{bmatrix} q-1 & q-1 & 1 \\ \end{bmatrix}\cdot\begin{bmatrix} b_1 \\ b_2 \\ b_1+b_2 \end{bmatrix}= \bold{0} \left(=\begin{bmatrix} 0 \\ \end{bmatrix}\right)\)

Példa más számokkal

\(k:=2 = \dim\mathcal{C}\)

\(n:= 4\)

\(M=\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 1 & 1 \\ 1 & 0 \\ \end{bmatrix}\)

\[ \left\{(1,1,1,1), (1,0,1,0), (0,0,0,0), (0,1,0,1)\right\}\subset \Z_2^4 \]

\(E_\text{llenőrző mátrix}= \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}\)

\(\begin{matrix} & \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 1& 1 \\ 1 & 0 \end{bmatrix} \\ \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix} & \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ \end{bmatrix} \mathclap{~~~~~~~=0}\\\end{matrix}\)

\(\dim E = n-k = 4-2=2\)

Az ellenőrző mátrix dimenziója \(n-k\) kell(!), hogy legyen. A generátor mátrix és az ellenőrző mátrix szorzata nullmátrix kell legyen. (valamint minden vektorral nullmátrixot kell adjon)

60. Reed Solomon? Ciklikus kódok? idfk