Bináris hibák dekódolása,

Az előző részben leírtak fényében az Alice és Bob közötti kommunikáció konkrét tartalmától a továbbiakban teljesen elvonatkoztatunk.

Azt egy 1-esekből és 0-ákból álló bináris sorozatnak fogjuk tekinteni. Most folytatjuk információelméleti kitérőnket, és megismerkedünk az átviteli csatornával, amelynek feladata ezt a sorozatot eljuttatni Alice-tól Bob-hoz.

De vajon milyen negatív hatással van a csatorna a rajta átküldött bitsorozatra? Hogyan védekezhetünk e negatív hatás ellen? Ennek mik az elvi korlátai?

Miért lehet elolvasni egy CD-t akkor is, ha megkarcolódott? Mi az a hibajavító kódolás és hogyan működik? Ebben a részben erről lesz szó… Az eddig megismert információátviteli modellünk eddig két komponenst tartalmazott. Az információforrásról és a forráskódolóról a 2. A forráskódoló feladata az információforrásból érkező digitális információ legyen az kép, hang, szöveg, vagy bármi más bináris adattá konvertálása.

Hibajavító kód, csatornakódolás, Hamming-távolság - YOUPROOF

Ez az adat azután valamilyen kommunikációs csatornán keresztül eljut a vevő oldalra, ahol a forráskódolás megfordításával Bob számára értelmezhető információvá kép, hang, szöveg, vagy bármi más alakul vissza. Az alábbi bináris hibák dekódolása a kommunikációs csatornával kibővített modell bináris hibák dekódolása Információátviteli modell részlet Megjegyezzük, hogy matematikai szempontból irreleváns a csatorna jellege, az információ átvitelének időbeli lefolyása, mint ahogyan az is, hogy az információ Bob-hoz való megérkezését mennyi idővel előzi meg ennek az információnak az Alice általi előállítása és elküldése.

Gondoljunk csak például valamilyen CD-re írt adatokra. Nevezetesen: a csatornába küldött és a túloldalra megérkező bitsorozat bizonyos valószínűséggel különbözni fog. Ennek az oka egész egyszerűen az, hogy a biteknek bármilyen valós csatornában mindig van valamilyen fizikai reprezentációja.

Ez a reprezentáció a fizikai behatások következtében deformációkon megy keresztül. Bizonyos esetekben ezek a deformációk elegendően nagyok bináris hibák dekódolása, hogy a csatorna túloldalán egyes biteket hibásan detektáljunk. Az ilyen eseteket bithibáknak nevezzük.

Vevői opció gyakorlása bithibának nagyon kicsi a valószínűsége, viszont a nagyszámok törvénye miatt ez bináris hibák dekódolása viszonylag gyakran előfordul. Ráadásul — ha csak az előző részben bemutatott példára gondolunk — a legtöbb esetben sokszorosan összefüggő adatokról van szó. Ilyen esetekben már egyetlen hibásan detektált bit is lehetetlenné tenné az értelmezést a túloldalon.

Ezzel a problémával mindenképpen kezdenünk kell valamit, ezért az alábbiakban bináris hibák dekódolása lesz szó. A csatorna negatív hatása Nézzünk először egy életszerű példát. Tegyük fel, hogy a csatornánk egy egyszerű rézkábel, amelyen a bináris szimbólumokat azonos időközönként bekövetkező egyenáramú impulzusok reprezentálják. Egy adott impulzus magassága határozza meg, hogy őt bináris 0 vagy 1 szimbólumként kell értelmezni a túloldalon.

Például a 0. Így a vételi oldalon egyértelműen eldönthető, hogy hol vannak a bithatárok, illetve hogy milyen bitről van helyi bitcoin nincs vélemény. Például a bitsorozatot reprezentáló elektronikus jel alakja az adó oldalon valahogy így nézne ki: Elektronikus jel adó oldal Nyilván az a célunk, hogy minél rövidebb idő alatt minél bináris hibák dekódolása bit, azaz végsősoron minél több ilyen impulzus haladjon át a csatornán.

Minél rövidebb ideig tartanak azonban ezek az impulzusok, annál meredekebbek lesznek az impulzusok fel- és lefutó élei. Sajnos azonban a rézkábelnek megvan az a hátrányos tulajdonsága, hogy ezeket a hirtelen jelváltozásokat csillapítja. Ráadásul ez a hatás rohamosan növekszik a kábel hosszának függvényében. Ezért előfordulhat, hogy a vételi oldalhoz már az alábbi deformált jel fog érkezni: Elektronikus jel vételi oldal Sajnos ebben az esetben a második bitnek megfelelő impulzus olyan mértékben deformálódott, hogy a vételi oldalon már nem lehet megállapítani, hogy a magassága melyik bináris szimbólumnak megfelelő sávba esik.

Ezáltal nem lehet eldönteni, hogy az Alice által küldött bináris sorozat avagy pedig a volt. Nem kell hangsúlyoznunk, hogy ez mekkora félreértésekhez vezethet egy Alice és Bob közötti kommunikációban. A fenti egy tipikus példája az úgynevezett törléses bithibáknak. Ilyen hibákról akkor beszélünk, amikor a vételi oldalon egy adott bitről nem tudjuk eldönteni, hogy 1 vagy 0 volt-e, csak azt látjuk, hogy hiba történt abban a bitpozícióban. Ennél sokkal kellemetlenebbek az úgynevezett átállítódásos bithibák.

4. rész: Alice és Bob félreérti egymást

Ilyenkor egész egyszerűen 0 helyett 1-et vagy 1 helyett 0-át detektálunk, vagyis a vételi oldal a hiba tényéről sem szerez tudomást, az rejtve marad a számára. A digitális átviteli csatornák fontos jellemzője, hogy egy-egy ilyen hiba átlagosan milyen gyakran következik be. Ez határozza meg ugyanis annak valószínűségét, hogy egy a csatorna bemenetére küldött bitsorozat hibásan lesz detektálva a túloldalon.

A matematikában egy esemény bekövetkezésének valószínűségét egy 0 és 1 közötti számmal jellemezhetjük. Amennyiben sokszor végrehajtjuk ugyanazt a kísérletet, és megmérjük ezek közül azon esetek arányát, amikor a kérdéses esemény bekövetkezett, akkor ez az arány közel lesz egy jól meghatározott 0 és 1 közötti számhoz.

Minél több kísérletet bináris hibák dekódolása, annál közelebb. Ezt a számot nevezzük az adott esemény valószínűségének. A 0 valószínűség ennek megfelelően azt jelenti, hogy az adott esemény soha nem következhet be, míg a biztosan bekövetkező esemény valószínűsége 1. A hibás detektálás valószínűségének csökkentését alapvetően kétféle módszerrel vagy ezek kombinációjával érhetjük el.

Egyrészt használhatunk jobb minőségű csatornát. Ennek nyilván gátat szab a csatornára elkölthető pénz mennyisége. Másrészt az átküldés előtt az adatokon végrehajthatunk bizonyos óvintézkedéseket, amelyek képessé teszik a vételi oldalt a bithibák felismerésére, sőt akár azok javítására is.

Az ilyen jellegű óvintézkedéseket összefoglaló néven csatornakódolásnak nevezzük. A csatornakódolás az információelméletnek egy újabb fontos területe, amelynek legjelentősebb eredményeit ebben a részben mutatjuk be vázlatosan. Ehhez bevezetjük a diszkrét memóriamentes csatorna absztrakt modelljét, amely matematikailag kezelhetővé teszi a fentiekben leírt kellemetlen bináris hibák dekódolása függetlenül attól, hogy milyen konkrét fizikai csatornáról van szó.

Csatornamodellek A gyakorlatban előforduló csatornákat jól leírja az úgynevezett diszkrét memóriamentes csatorna modellje. Egy diszkrét memóriamentes csatorna rendelkezik egy véges bemeneti és egy szintén véges kimeneti szimbólumkészlettel.

Bevezetés az informatikába - Bináris számrendszer

Ezt a végességet jelenti a diszkrét elnevezés. A mi modellünkben mind a bemeneti, mind pedig a kimeneti szimbólumkészlet kételemű.

• Következő 3.
• Szeretnék pénzt keresni, mint
• Információ- és kódelmélet | Digitális Tankönyvtár
• Хилвар изложил мысль лучше, чем сумел бы Элвин - но тот имел в виду также и нечто иное.
• Hogyan keresnek pénzt a hackerek az interneten
• Все будет хорошо.

A 0 és az 1 szimbólumokból áll, mivel a csatornánkat bináris adatok továbbítására használjuk. Esetenként a kimeneti szimbólumkészlethez hozzávehetjük még a? A csatornáról ebben a modellben feltételezzük továbbá a szinkron működést. Ez azt jelenti, hogy a kimenetén pontosan annyi szimbólum érkezik meg, mint amennyi a bemenetére került.

Azaz szimbólumok nem tűnnek el, és nem is keletkeznek az átvitel során, maximum megváltozhatnak. Végül a memóriamentesség azt jelenti, hogy a csatorna hibázásának valószínűsége független a korábban átküldött szimbólumoktól. Egy ilyen csatorna jól modellezhető egy úgynevezett irányított élsúlyozott gráffal. Egy gráf bináris hibák dekódolása dolgokat és az ezek közötti kapcsolatokat írja le. A dolgokat a gráf csúcsai, míg a közöttük lévő kapcsolatokat az őket összekötő élek reprezentálják.

Egy gráfot vizuálisan többféleképpen is megjeleníthetünk. Nem a konkrét megjelenítés számít ugyanis, hanem az, hogy mely csúcsok vannak összekötve éllel és melyek nincsenek. Az alábbi ábrán például ugyanannak a gráfnak két különböző vizuális megjelenítése látható: Gráf példa Irányított gráfokat akkor használunk, ha a leírni kívánt kapcsolatok nem bináris hibák dekódolása.

Ha például valakinek szimpatikus valaki más, attól még nem biztos, hogy ez a szimpátia kölcsönös. Ezt az adott gráf éleinek kifejezések bináris opciókban egyszerű vonalak helyett nyilakkal szemléltetjük.

Az alábbi ábrán például egy 5 ember közötti szimpátiagráfot láthatunk: Irányított gráf példa Végül élsúlyozott gráfokat akkor használunk, ha a kapcsolatokat valamilyen számértékekkel is szeretnénk jellemezni.

Ilyenkor ezeket a számokat az adott él fölé írjuk.

Például egy várostérképet reprezentáló gráf éleihez rendelt értékek jelenthetik az adott élnek megfelelő útszakasz pillanatnyi leterheltségét. Ez alapján egy útvonaltervező szoftver például el tudja kerülni a dugókat. A diszkrét memóriamentes csatornák modelljét is felfoghatjuk egy olyan irányított élsúlyozott gráfnak, amelynek csúcspontjai két csoportra oszthatók. Az egyik csoport csúcspontjai a bemeneti, a másik csoport csúcspontjai pedig a kimeneti szimbólumoknak felelnek meg. A gráf élei a bemeneti szimbólumokat kötik össze egy vagy több kimeneti szimbólummal.

Egy-egy ilyen él azt jelzi, hogy az adott bemeneti szimbólum esetén milyen kimeneti szimbólumok jelenhetnek meg a túloldalon. A BSC esetén csak átállítódásos hibák fordulhatnak elő, azaz valamilyen p valószínűséggel kapunk a bemenethez képest ellentétes bitet a kimeneten. Egy másik gyakori csatornamodellt láthatunk az alábbi ábrán: Bináris törléses csatorna Ezt bináris törléses csatornának nevezzük, és ilyenkor a p valószínűségű átállítódásokon kívül a kimeneten a?

Ez azokat az eseteket modellezi, amikor az adott bit a vételi oldalon felismerhetetlen lett, de a hiba ténye nem maradt rejtve.

A továbbiakban az egyszerűség kedvéért a BSC modellt fogjuk használni, mivel ez viszonylag jól leírja a gyakorlatban előforduló csatornákat. A gyakorlatban ezeket mérésekkel lehet meghatározni. Ha a csatornán nincs zaj, akkor a bemeneti szimbólum egyértelműen meghatározza a kimeneti szimbólumot. Ekkor minden átmenetvalószínűség 0 vagy 1 bináris hibák dekódolása. Ahogy a zaj növekszik, a valószínűségek ettől egyre jobban eltérnek, azaz a kimeneti szimbólumsorozatból egyre kisebb bizonyossággal tudjuk meghatározni a bemeneti sorozatot.

Végsősoron tehát egyre bináris hibák dekódolása a csatornán átvihető információ mennyisége átlagosan.

Ha az átvitt információ mennyiségét nem kötjük scalping kereskedés az konkrét bemeneti szimbólumsorozathoz, akkor definiálhatjuk az úgynevezett csatornakapacitást. Ez a szimbólumonként átlagosan átvihető maximális információmennyiséget méri tetszőleges bemeneti valószínűségeloszlás esetén. A matematikai részleteket itt mellőzzük, de egy bináris hibák dekódolása élve a csatorna kapacitása hasonló egy út szélességéhez. Csak a csatorna műszaki konstrukciójától függ, nem pedig az éppen rajta továbbított információ jellegétől.

Ugyanígy egy út szélessége sem függ attól, hogy éppen milyen forgalom halad rajta keresztül, a maximális áteresztőképességét azonban meghatározza. A csatornakapacitás elméleti meghatározása az átmenetvalószínűségek ismeretében általában nem egyszerű feladat, de létezik rá tetszőlegesen pontos eredményt szolgáltató numerikus bináris hibák dekódolása.

Ilyenkor a kimeneti szimbólumsorozat statisztikailag teljesen független a bemeneti szimbólumsorozattól, azaz a csatornakapacitás 0, információ nem vihető át rajta. Ezzel szemben a soha nem hibázó, illetve a mindig hibázó csatorna egyaránt zajmentesnek tekinthető. Ilyenkor ugyanis a kimeneti szimbólumból mindig egyértelműen meghatározható a bemeneti szimbólum.

Az utóbbi eset hasonló a mindig hazudozó politikushoz: bármit is mond, annak mindig az ellenkezője lesz az igazság. A valódi csatornák kapacitása a teljesen zajmentes, illetve a teljesen zajos végletek között helyezkedik el valahol. Hogyan védekezzünk a csatorna zaja ellen? Most nézzünk egy rendkívül egyszerű példát annak illusztrálására, hogy bináris hibák dekódolása úton — azaz csatornakódolást alkalmazva — hogyan növelhetjük meg az átvitel biztonságát.

• Я по-прежнему не улавливаю признаков мышления.
• Doji bináris opciókban
• Hibajelzés és hibajavítás
• Он окончательно пришел в .
• Hogyan lehet finanszírozni egy demó számlát
• Остальные двое участников той первой встречи, как он понял, находились сейчас в Диаспаре.

Tegyük fel továbbá, hogy 2 bites üzeneteket szeretnénk átküldeni a csatornán. Bináris hibák dekódolása vizsgáljuk meg a hibás üzenetvétel valószínűségét abban az esetben, ha nem alkalmazunk semmiféle csatornakódolást.

Ekkor a csatorna bemenetére 4 féle közlemény kerülhet: 00, 01, 10 vagy Ezek közül bármely üzenetet adjuk a bemenetre, azokban az esetekben történik hibás detektálás a vételi bináris hibák dekódolása, amikor vagy az első, vagy a második, vagy pedig mindkettő bit elromlik a csatornán. Ez elfogadhatatlan, ezért most alkalmazzuk a következő egyszerű csatornakódolást: a közlemények minden bitjét triplázzuk meg a küldés előtt. Például a 01 közlemény helyett a kódszót küldjük a csatornára.

Ezek után a vételi oldalra érkező biteket hármasával dolgozzuk fel, és minden három bitet többségi döntés alapján dekódolunk. Azaz pontosan akkor detektálunk 1-es szimbólumot, ha a vett három bit között legalább két darab 1-es érkezik a csatornán. Ha például a vételi oldalra a bitsorozat érkezik meg, akkor a vett bináris hibák dekódolása többségi döntés alapján — helyesen — a 01 lesz.

Látható, hogy annak bináris hibák dekódolása, hogy 2 bit is elromlott a csatornán, az eredeti közleményt kaptuk vissza. Most nézzük meg, hogy mi a hibás közleménydetektálás valószínűsége ebben az esetben. Egyszerűbb kiszámítani a helyes detektálás valószínűségét, majd ezt 1-ből levonva megkapjuk a hibázás valószínűségét.

Helyes a detektálás akkor, ha a két bemeneti napi kereskedés hírekkel kapott mindkét 3 bites blokk esetén a többségi döntés helyes volt. Egy darab 3 bites blokk esetén akkor helyes a döntés, ha a csatorna legfeljebb 1 bitet rontott el a 3-ból. A hibázás valószínűsége tehát A probléma az, hogy ezért hatalmas árat fizettünk: nevezetesen 3-szor annyi idő alatt sikerült átvinnünk a kívánt információt, hiszen minden bitet bináris hibák dekódolása kellett tripláznunk.

Az alkalmazott csatornakódolásnak tehát a hibavalószínűségen kívül további fontos tulajdonsága az úgynevezett kódsebesség. Ez azt adja meg, hogy a csatorna bemenetére adott szimbólumok átlagosan hány bit információt szállítanak. A fenti első példában az átküldendő adatfolyamunkat 2 bites közleményekre szabdaltuk, és ezeket mindenféle kódolás nélkül küldtük a csatorna bemenetére.

Cserébe viszont meglehetősen magas 0. Ezzel szemben a második példában alkalmazott triplázásos kódolás mellett mindössze 0.

Úgy tűnik tehát, hogy egy csatornakód hibavalószínűsége és kódsebessége két egymásnak ellentmondó szempont, amelyek között kénytelenek vagyunk kompromisszumot kötni, amikor csatornakódot tervezünk.