Beugró - Kódelmélet
1. Definiálja a Hamming-távolságot
Definíció: Hamming-távolság
Legyen \(\Sigma\) egy véges halmaz (ábécé). Adott két \(n\) hosszú \(\,u, v \in \Sigma^n\,\) szó. Ekkor a szavak Hamming-távolsága:
\(d(u, v) = \#\{1 \le i \le n: u_i \ne v_i\}\)
Példa feladat
Mennyi lesz \(\;d(010, 110) = \;?\;\) és \(\;d(0000, 0009) = \;?\)
(Azt kell nézni, hogy hány helyen tér el.)
\(d(010, 110) = 1\)
\(d(0000, 0009) = 1\)
2. Definiálja a kódok minimális távolságát
Definíció: Kódok minimális távolsága
Legyen \(\Sigma^n\) a \(n\) hosszú szavak ábécéje. Ekkor \(\mathcal{C} \subset \Sigma^n\) egy kód. Ennek elemei a kódszavak.
Egy \(\mathcal{C}\) kód kódtávolsága a kódszavak közti minimális távolság:
\(d(\mathcal{C}) = \min\{d(u, v):\; u, v \in \mathcal{C},\; u \ne v\}\)
Példa feladat
Mennyi lesz \(\mathcal{C} = \{010, 101, 111\}\) kód minimális távolsága?
\(d(010, 101) = 3\)
\(d(010, 111) = 2\)
\(d(101, 111) = 1\)
A minimális távolság az \(1\) lesz.
3. Mondja ki a kód kódtávolsága és a hibajelző, hibajavító képesség közötti összefüggést
Definíció: A kód kódtávolsága és a hibajelző, hibajavító képesség közötti összefüggés
Egy \(\mathcal{C}\) kód \(d = d(\mathcal{C})\) kódtávolsággal:
-
\(d - 1\) hibát tud jelezni
-
\(t = \left\lfloor\dfrac{d - 1}{2}\right\rfloor\) hibát tud javítani
Példa feladat
Hány hibát jelez ill. javít a \(\mathcal{C}\) kód, ha \(d(\mathcal{C}) = 8\;\)?
Jelez: \(8 - 1 = 7\)
Javít: \(\left\lfloor\dfrac{8 - 1}{2}\right\rfloor = \lfloor3,5\rfloor = 3\)
4. Definiálja a Hamming-súlyt
Definíció: Hamming-súly
Egy \(u \in \mathbb{F}^{n}_{q}\) szó \(w(u)\) Hamming-súlya a nem-nulla koordinátáinak száma:
\(w(u) = \#\{1 \le i \le n:\; u_i \ne 0\}\)
Példa feladat
Mennyi lesz \(\;w(010) = \;?\;\) és \(\;w(0009) = \;?\)
\(w(010) = 1\)
\(w(0009) = 1\)
5. Definiálja a kódok súlyát
Definíció: Kód súly
Egy \(\,\mathcal{C} \subset \mathbb{F}^{n}_{q}\;\) kód \(w(\mathcal{C})\) Hamming-súlya \(\;w(\mathcal{C}) = \min\{w(c):\; c \in \mathcal{C} \;\backslash\; \{0\}\}\)
Példa feladat
Mennyi lesz \(\mathcal{C} = \{000, 010, 101, 111\}\) kód súlya?
\(w(010) = 1\)
\(w(101) = 2\)
\(w(111) = 3\)
A kód súlya 1.
6. Definiálja a lineáris kódok fogalmát
Definíció: Lineáris kód
Egy \(\;\mathcal{C} \subset \mathbb{F}^{n}_{q}\;\) kód 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.
Speciálisan \(\#\mathcal{C} = q^k\). Ekkor \(\mathcal{C}\) egy \((n, k)\) kód.
Példa feladat
Lineáris lesz-e a \(\mathcal{C} = \{110, 101, 111\} \subset \Z^{3}_{2}\) kód?
Akkor altér, ha minden alábbi teljesül:
- Tartalmazza a zérus vektort
- Zárt az összeadásra \(\mod q\) (azaz minden elem minden lehetséges összeadását tartalmazza)
- Zárt a skalárral való szorzásra
\(\mathcal{C}\) nem tartalmazza a zérus vektort. Valamint az összeadás sem teljesül: \(110 + 101 = 211 \mod 2 = 011,\; 011 \not\in \mathcal{C}\). Így \(\mathcal{C}\) nem lineáris kód.
7. Definiálja lineáris kódok generátormátrixát
Definíció: Lineáris kód generátormátrixa
Legyen \(n\) a kódszavak hossza és \(k\) a kód dimenziója. 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}_{\,q}^{\,n \times k}\).
Példa feladat
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?
8. Definiálja lineáris kódok ellenőrzőmátrixát
Definíció: Lineáris kód ellenőrzőmátrixa
Legyen \(n\) a kódszavak hossza és \(k\) a kód dimenziója. Legyen \(\mathcal{C}\) egy lineáris \((n, k)\) kód. Ekkor \(\mathcal{C}\) ellenőrző mátrixa az a \(H \in \mathbb{F}_{\,q}^{\,(n - k) \times n}\), ha
\(c \in \mathcal{C} \Longleftrightarrow H \cdot c = 0\).
Példa feladat
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?