Kódolástechnika alapfogalmak

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

Üzenet(vektor)

• [math]\overline{u} \in \{0,1\}^k[/math]
• [math]dim(\overline{u})=k[/math]
• sorvektor: [math]\overline{u}=(0100010)[/math]

Kódszó(vektor)

• [math]\overline{c} \subset \{0,1\}^n[/math]
• [math]dim(\overline{c})=n\gt k[/math] (redundancia: n-k)

Kódolás

• [math]\Psi: \{0,1\}^k \rightarrow C=\{\overline{c}^{(1)},\overline{c}^{(2)}, \ldots, \overline{c}^{(M)}\}[/math]
• [math]M=2^k[/math] a kódszavak száma
• [math] C(n,k)[/math]: kód, amelynek paraméterei: [math]{n}[/math] (kódszavak hossza) és [math]{k}[/math] (üzenetek hossza)

Vett vektor

• [math]\overline{v} \in \{0,1\}^n[/math]
• [math]dim(\overline{v})=n[/math]

Detekció

• [math]\varphi: \{0,1\}^n \rightarrow C[/math]
• [math]\varphi(\overline{v})=\overline{c}'[/math]

Dekódolás

• [math]\Psi^{-1}: C \rightarrow \{0,1\}^k[/math]
• [math]\Psi^{-1}(\overline{c}')=\overline{u}'[/math]

BSC

• Bináris szimmetrikus csatorna (az alap csatorna modell)
• "perverz" módon invertálhatja a rajta áthaladó biteket: bithibákat okoz

QSC

• Q-áris szimmetrikus csatorna
• nem biteket, hanem [math]c \in \{0,1,\ldots ,q-1\}[/math] szimbólumokat küldünk át rajta
• szimbólumhibákat okoz

Kódséma

Ezen a helyen volt linkelve a kodsema.png 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)

• megj1.: a kurzus a dobozok (kódolás, detekció, dekódolás) algoritmikus megvalósításáról szól
• megj2.: bizonyos kódoknál (pl. Reed-Solomon kódok) a csatorna QSC

Kódtávolság

• [math]d_{min}=min_{\overline{c}, \overline{c}' \in C;\overline{c} \neq \overline{c}'}(\overline{c},\overline{c}')[/math] a kódszavak közötti legkisebb távolság : minimális Hamming távolság

Hibajelzés

• [math]d_{min}-1[/math]

Hibajavítás

Egyszerű hibázás

• ismerjük a hiba helyét és értékét
• [math]t=\lfloor \frac{d_{min}-1}{2} \rfloor[/math]

Törléses hiba

• a hiba helyét ismerjük, az értékét nem
• [math]t=d_{min}-1[/math]

Optimális kód

• olyan kód, amelyben a [math]d_{min}[/math] maximális

MDS-kód

• Maximum Distance Separable (maximális kódtávolságú)
• ha a <a href="https://wiki.sch.bme.hu/bin/view/Infoalap/KodElmKepletek#Singleton_korl%E1t">Singleton korlát</a>ban egyenlőség áll, [math]d_{min}=n-k+1[/math]
• minden MDS-kód perfekt kód

Perfekt kód

• ha a <a href="https://wiki.sch.bme.hu/bin/view/Infoalap/KodElmKepletek#Hamming_korl%E1t">Hamming korlát</a>ban egyenlőség van

Kódtervezés (általános séma)

• adott: a csatorna bithibavalószínűsége [math]P_b=\Phi(-\sqrt{SNR})\approx10^{-1}[/math]
• ([math]SNR[/math]: jel/zaj arány; [math]\Phi[/math]: standard normális eloszlásfüggvény)
• kell: előírt minőségű szolgáltatás (QoS) [math]P_b'\leq 10^{-4}[/math]
• [math]P_{blokkhiba}=\sum_{i=t+1}^{n} {n \choose i} P_b^i (1-P_b)^{n-i}=\sum_{j=1}^{k} {k \choose j} P_b'^i (1-P_b')^{k-j}[/math]
• [math]P_b'[/math] a [math]P_b[/math] és a [math]t[/math] függvénye [math]\rightarrow t \rightarrow n, k [/math] meghatározandó

-- adamo - 2006.05.01. -- RebeliSzaboTamas - 2008.01.19.