InfElmTetel36

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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \bold{U} } a csatornán átküldhető betűk halmaza.
Ekkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \bold{U}^n } a csatorna Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} hosszúságú szavainak halmaza.
Legyen Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \bold{C} \subset \bold{U}^n } a felhasznált kódszavak halmaza.
Legyen Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \bold{C} } mérete Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle |\bold{C}| = M. \bold{C} = \{ \underline{c}_1, ..., \underline{c}_M \} }
Ekkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \underline{c}_i \in \bold{C} } egy felhasznált kódszó.
Legyen Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle c_{i_j} } az i. kódszó j. betűje.

Ekkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \bold{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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \bold{Y} } a forrásábécé. Legyen Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k } a forrásblokkok hossza. Ekkor kódolónak nevezzük az invertálható Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f:\bold{Y}^k\longmapsto\{\underline{c}_1, ..., \underline{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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle g: V^n \rightarrow \{\underline{c}_1, ..., \underline{c}_M \} } leképezés adja meg, a döntési tartományok: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D_m=\{\underline{v} \in V^n: g(\underline{v})=\underline{c}_m \} \text{ ahol } m=1,2,\ldots,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

Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle P_{e,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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle y_m } kódra megkaphatjuk úgy, kiszámítjuk, hogy mennyi a valószínűsége annak, hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle y_m } kódra a csatorna olyan kódot ad, amelyre a döntő nem Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle y_m } kódra dönt. Másszóval: az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle y_m } kódra kapott kód kivül esik Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle y_m } döntési tartományán.

Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle P_{e,m} = \sum_{f^{-1}(y')\neq y_m} p(y' | y_m) = \sum_{y' \notin D_m} p(y' | y_m) }

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

Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle P_e = \sum_{m=1}^{M} p(y_m) P_{e,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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \bar{P_e} } -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:

Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \hat{P_e}= \frac{1}{M} \sum_{m=1}^{M} P_{e,m} }

Jelsebesség

Ha továbbra is Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle R = \frac{log M}{n} } é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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle C} kapacitású diszkrét memóriamentes csatornát.

Bármely Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle r<C} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \epsilon>0} számhoz létezik olyan Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle C=\{\underline{c}_1,\ldots,\underline{c}_M\}} csatornakód Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} hosszú kódszavakkal, hogy
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \bar{P_e} < \epsilon }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle M > 2^{rn}}

azaz a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle R=\frac{\log{M}}{n}} jelsebesség nagyobb, mint Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle r} .

No garancia megjegyzés: Tehát egy C kapacitású csatornán át akarunk vinni információt r<C jelsebességgel, és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \epsilon} hibát tudunk elfogadni. Ekkor található olyan kód, ahol legfeljebb Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \epsilon} 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.