InfElmTetel36

A VIK Wikiből

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.


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



Definíciók

Csatornakód

Legyen U a csatornán átküldhető betűk halmaza.
Ekkor Un a csatorna n hosszúságú szavainak halmaza.
Legyen CUn a felhasznált kódszavak halmaza.
Legyen C mérete |C|=M.C={c_1,...,c_M}
Ekkor c_iC egy felhasznált kódszó.
Legyen cij az i. kódszó j. betűje.

Ekkor C-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 Y a forrásábécé. Legyen k a forrásblokkok hossza. Ekkor kódolónak nevezzük az invertálható f:Yk{c_1,...,c_M} 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 g:Vn{c_1,...,c_M} leképezés adja meg, a döntési tartományok: Dm={v_Vn:g(v_)=c_m} ahol m=1,2,,M

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

Pe,m 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 ym kódra megkaphatjuk úgy, kiszámítjuk, hogy mennyi a valószínűsége annak, hogy ym kódra a csatorna olyan kódot ad, amelyre a döntő nem ym kódra dönt. Másszóval: az ym kódra kapott kód kivül esik ym döntési tartományán.

Pe,m=f1(y)ymp(y|ym)=yDmp(y|ym)

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

Pe=m=1Mp(ym)Pe,m

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 Pe¯-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:

Pe^=1Mm=1MPe,m

Jelsebesség

Ha továbbra is n 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 R=logMn é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 C kapacitású diszkrét memóriamentes csatornát.

Bármely r<C és ϵ>0 számhoz létezik olyan C={c_1,,c_M} csatornakód n hosszú kódszavakkal, hogy
Pe¯<ϵ
M>2rn

azaz a R=logMn jelsebesség nagyobb, mint r.


No garancia megjegyzés: Tehát egy C kapacitású csatornán át akarunk vinni információt r<C jelsebességgel, és ϵ hibát tudunk elfogadni. Ekkor található olyan kód, ahol legfeljebb ϵ 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.