InfElmTetel36

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

vissza InfelmTetelek-hez <style> li {margin-top: 4px; margin-bottom: 4px;} </style>

Definíciók

Csatornakód

Legyen [math] \bold{U} [/math] a csatornán átküldhető betűk halmaza.
Ekkor [math] \bold{U}^n [/math] a csatorna [math]n[/math] hosszúságú szavainak halmaza.
Legyen [math] \bold{C} \subset \bold{U}^n [/math] a felhasznált kódszavak halmaza.
Legyen [math] \bold{C} [/math] mérete [math] |\bold{C}| = M. \bold{C} = \{ \underline{c}_1, ..., \underline{c}_M \} [/math]
Ekkor [math] \underline{c}_i \in \bold{C} [/math] egy felhasznált kódszó.
Legyen [math] c_{i_j} [/math] az i. kódszó j. betűje.

Ekkor [math] \bold{C} [/math]-t csatornakódnak nevezzük.

Kódóló

A forrás jelfolyam, amit megfelelő kódolás után át szeretnénk küldeni a csatornán. Legyen [math] \bold{Y} [/math] a forrásábécé. Legyen [math] k [/math] a forrásblokkok hossza. Ekkor kódolónak nevezzük az invertálható [math] f:\bold{Y}^k\longmapsto\{\underline{c}_1, ..., \underline{c}_M \} [/math] függvényt, amely a k hosszú forrásblokkokhoz kódszavakat rendel.

Dekódoló

A dekódoló a csatornából kilépő üzenet alapján próbálja meg kideríteni, hogy mi volt az eredeti üzenet.
A dekódoló két részből áll a döntőből és a kódoló inverzéből.
A döntő eldönti a fogadott kódszó alapján, hogy milyen kódszót küldtek a csatornán.

A döntőt a [math] g: V^n \rightarrow \{\underline{c}_1, ..., \underline{c}_M \} [/math] leképezés adja meg, a döntési tartományok: [math] D_m=\{\underline{v} \in V^n: g(\underline{v})=\underline{c}_m \} \text{ ahol } m=1,2,\ldots,M [/math]

Hibás dekódolás valószínűsége

Egy adott kód hibás detektálásának valószínűsége

[math] P_{e,m} [/math] annak a valószínűsége, hogy hibát vétünk, feltéve, hogy az m. kódszót továbbítottuk.
Egy [math] y_m [/math] kódra megkaphatjuk úgy, kiszámítjuk, hogy mennyi a valószínűsége annak, hogy [math] y_m [/math] kódra a csatorna olyan kódot ad, amelyre a döntő nem [math] y_m [/math] kódra dönt. Másszóval: az [math] y_m [/math] kódra kapott kód kivül esik [math] y_m [/math] döntési tartományán.

[math] P_{e,m} = \sum_{f^{-1}(y')\neq y_m} p(y' | y_m) = \sum_{y' \notin D_m} p(y' | y_m) [/math]

Hibás dekódolás valószínűsége

[math] P_e = \sum_{m=1}^{M} p(y_m) P_{e,m} [/math]

Annak az átlagos valószínűségét, hogy egy üzenet javíthatatlanul megsérül a csatornán, és ezért hibásan dekódoljuk [math] \bar{P_e} [/math]-vel jelöljük, és átlagos hibának nevezzük.

Átlagos hiba

A hiba valószínűségére olyan mérőszámot szeretnénk, ami független az üzenetek valószínűségétől, ezért az átlagos hibát használjuk:

[math] \hat{P_e}= \frac{1}{M} \sum_{m=1}^{M} P_{e,m} [/math]

Jelsebesség

Ha továbbra is [math] n [/math] a csatorna kódszavainak hossza, és </math> M </math> az átvihető üzenetek száma, akkor: Jelsebességnek (vagy _kódolási sebességnek_) nevezzük az [math] R = \frac{log M}{n} [/math] értéket.

A jelsebesség tehát azt mutatja meg, hogy egy csatornahasználattal (a kódszó egy betűjével) hány bit információt viszünk át.
No garancia megjegyzés: Bináris kód esetében ez értelemszerűen legfeljebb 1. A maximumát akkor veszi fel, ha az összes lehetséges kódszót felhasználjuk. Látható, hogy ilyenkor nincs hibajavító képessége a kódnak.

Csatornakódolási tétel

Vegyünk egy [math]C[/math] kapacitású diszkrét memóriamentes csatornát.

Bármely [math]r\lt C[/math] és [math]\epsilon\gt 0[/math] számhoz létezik olyan [math]C=\{\underline{c}_1,\ldots,\underline{c}_M\}[/math] csatornakód [math]n[/math] hosszú kódszavakkal, hogy
[math] \bar{P_e} \lt \epsilon [/math]
[math] M \gt 2^{rn}[/math]

azaz a [math]R=\frac{\log{M}}{n}[/math] jelsebesség nagyobb, mint [math]r[/math].

No garancia megjegyzés: Tehát egy C kapacitású csatornán át akarunk vinni információt r<C jelsebességgel, és [math]\epsilon[/math] hibát tudunk elfogadni. Ekkor található olyan kód, ahol legfeljebb [math]\epsilon[/math] lesz a hiba valószínűsége, és r kisebb lesz a kód R jelsebességénél.

Bizonyításvázlat

TODO: a könyvben elég ronda a bizonyítás, hogy kellene ennek előállítani a vázlatát?

-- Sales - 2006.06.26.