Az informatikában és az információelméletben fontos gyakorlati kérdés a hibák felismerése és kijavítása. A hibafelismerés egy képesség az adó és a vevő közötti átvitel folyamán a zaj vagy egyéb zavar okozta rendellenességek miatti torzulások jelzésére. A hibajavítási képesség lehetővé teszi a hiba helyének felismerését és kijavítását is.
 |
Ezt a szócikket át kellene olvasni, ellenőrizni a szöveg helyesírását és nyelvhelyességét, a tulajdonnevek átírását. Esetleges további megjegyzések a vitalapon. |
Ha az adott cél hibajavítás, akkor önmagában a hibafelismerési képesség megléte látszólag nem elegendő. A hibajavítási módszerek általában számítás igényesek, vagy számos, az alkalmazások számára szükségtelen, redundáns adat hozzáadást jelentik. Néhány alkalmazás esetén, különösen adó-vevő rendszerek esetén, a hibafelismerő rendszer, az úgynevezett (automatic repeat request – ARQ) automatikus ismétlés kérés rendszerrel együttesen alkalmazva – a módszer alapja, hogy igény esetén a küldő képes a küldött üzenetet vagy annak egy részét ismételten elküldeni – bár kevésbé hatékonyan, de képes hibajavításra, a nagy mennyiségű, ismételten elküldött adat segítségével.
Számos módszer létezik a hibák felismerésére, néhány közülük meglehetősen egyszerű.
Ismétlő módszerek
A megoldások több változata ismert. Az elküldött adatok bitsorozatát bitek blokkjaira tördelik, és küldésnél minden blokkot egy előre megadott számszor újraküldenek. Például, úgy küldjük el a "1011" bitsorozatot, hogy minden bitnégyest háromszor küldünk el.
Tegyük fel, hogy elküldtük a "1011 1011 1011" sorozatot, amit "1010 1011 1011" sorozatnak veszünk. Mivel egy csoport eltér a másik kettőtől, megállapítható, hogy az átvitel hibás volt. Ez a megoldás nem túl hatékony; a hiba felderítése azon a feltételezésen alapul, hogy a vett csoportok eltérnek (például ha a "1010 1010 1010" csoportokat vettük, akkor ez a módszer helyes átvitelnek detektálja).
Bár ez a megoldás igen egyszerű, mégis használatos: néhány eljárás az állomás számok küldésénél ezt használja.
Paritásellenőrző módszerek
Adott az elküldendő adatok folyama, amelyet bitek blokkjaira tördelnek, és minden egyes blokkban lévő 1 értékű bitet megszámolnak. A blokkhoz tartozó "paritásbit" értékét beállítják vagy törlik, attól függően, hogy a számlálás eredménye páros vagy páratlan volt. Ha az így ellenőrzött blokkok átlapolják egymást, akkor a paritásbitekkel még a hiba helye is behatárolható, és esetleg még javítható is, ha a hiba csak egy bitnél jelentkezik: ez a Hamming kódolás alapelve.
A paritásellenőrző módszereknek vannak korlátai: egy paritásbit csak egyetlen egybites hiba felismerését garantálhatja. Ha két vagy több bit sérül, akkor a paritásellenőrzés helyes eredményt adhat, annak ellenére, hogy az átvitel hibás volt.
Ciklikus redundancia-ellenőrzés (Cyclic redundancy check – CRC)
Sokkal átfogóbb hibafelismerő (és javító) módszert tesznek lehetővé a véges testek és a felettük értelmezett polinomok bizonyos tulajdonságainak kihasználása.
A ciklikus redundancia-ellenőrzés az adatblokkot egy polinom együtthatóinak tekinti, amelyet eloszt egy előre meghatározott, állandó polinommal. Az osztás eredményének együtthatói alkotják a redundáns adatbiteket, a CRC-t.
- A vett adat ellenőrzéséhez elegendő megszorozni a CRC-t az előre meghatározott polinommal.
- Ha a szorzás eredménye a hasznos adat, akkor az adatok hiba nélkül érkeztek meg.
- Másik lehetséges ellenőrzési mód a CRC újbóli kiszámítása a hasznos bitekből, és a vett CRC-vel való összehasonlítása.
A fenti módszerek képesek arra, hogy felismerjék, ha az adatok hibásan érkeztek, azonban ez gyakran nem elegendő. Gondoljunk egy olyan alkalmazásra, mint például egy egyirányú, rádión keresztüli géptávíró kapcsolat (SITOR). Ha az üzenetet gyorsan kell venni, és hiba nélkül, teljes üzenetnek meg kell érkeznie, akkor nem elegendő csupán azt tudni, hogy az üzenet hibamentes, a második feltétel, a teljesség ebből még nem következik, az üzenet lehet hibamentes, de hiányos.
Előnyös lenne a vevő oldal számára, ha valahogyan megállapíthatná, hogy hiba történt, és azt ki is tudná javítani. Bizonyos eljárások ezt lehetővé is teszik. Például a NATO fonetikus ábécéjének használatával – ha a küldő a "WIKI" szót szeretné elküldeni, akkor az ábécé használatával a "WHISKEY INDIA KILO INDIA" üzenet kerülne ténylegesen elküldésre, és vevő oldalon (*-gal jelöljük a hibásan vett betűket) a "W***KEY I**I* **LO **DI*" betűsorozat érkezik. A hibajavítások lehetségesek, mivel a használt "ábécé"-ben csak egy szó kezdődik "W"-vel és végződik "KEY"-el, és hasonlóképen javítható a többi vett szó. Ez az elv néhány hibajavító kódban (error correcting code – ECC) meg is jelenik.
A hibajavító kódoknak azonban megvannak a saját korlátaik: néhány képes adott számú bithibát javítani, és csak jelezni tudja a többi bithibát. Vannak egy hibát felismerni és javítani képes (single error correcting – SEC) kódok, vannak kettős hibát (double error detecting – DED) felismerni és javítani képes kódok is. Vannak olyan kódok is, amelyek képesek több hibát is felismerni és javítani.
Az internet
Egy tipikus TCP/IP protokollokat használó hálózatban a hibafelismerés több szinten is megvalósul:
- Minden Ethernet framehez tartozik egy CRC-32 ellenőrző összeg. Azokat a kereteket, amelyeknek az ellenőrző összege hibás, a vevő nem veszi figyelembe.
- A IPv4 protokoll fejrészében külön ellenőrző összeg van, amely a fejrészt védi (kivéve a ellenőrző összeg mezőt). A csomagok amelyek hibás ellenőrző összeggel érkeztek, figyelmen kívül maradnak.
- Az IPv6 protokoll fejrészében lévő ellenőrző összeg figyelmen kívül marad, mivel a leggyakrabban használt adatkapcsolati rétegek protokolljai saját hibavédelemmel rendelkeznek.
- A UDP protokollnak opcionális az ellenőrző összeg kezelése. A hibás ellenőrző összegű csomagok figyelmen kívül maradnak.
- A TCP protokoll a fejrész hasznos részére külön ellenőrző összeget képez (kivéve az ellenőrző összeget), ami a forrás- és célcímet is tartalmazza. A fogadó figyelmen kívül hagyja a hibás csomagokat, és ha a küldő vesz egy háromszoros nyugta üzenetet vagy egy időzítés lejár, akkor ezeket a csomagokat újraküldi.
Mélyűri telekommunikáció
A NASA bonyolultabb hibajavító kódokat használ. Az 1969 és 1977 között a Mariner űrhajók Reed-Muller kódokat használtak. Ennél az űrhajónál a zajok eloszlását a jól ismert "harang-görbe" szerintinek, normál eloszlásúnak tekintették, így a Reed-Muller kódok elég jól megfeleltek.
A Voyager–1 és a Voyager–2 űrszondák már színes képeket közvetítettek a Jupiterről és a Szaturnuszról 1979-ben és 1980-ban.
- A színes képek háromszoros adatmennyiséget jelentenek, így a Golay (24,12,8) code került felhasználásra.
- Ez a Golay kód csak 3 hibát képes javítani, viszont magasabb adat rátát enged meg az átvitel folyamán.
- A Voyager 2 az Uránuszhoz és a Neptunuszhoz repült, az átvitel folyamán használt kódot átkapcsolták egy Reed-Solomon kód-konvolúciós kódokból összevont kódra, hogy megerősítsék a kód hibajavítási képességét.
- Az aktuálisan vett jel alapján a hibajavítást egy erre a célra használt hardver egység végezte.
- A NASA néhány mélyűri űrhajóján, mint Voyager-program űrhajóin, a Cassini-Huygens-en (Szaturnusz), a New Horizons-on (Plútó) és a Deep Space–1-en – a hardverrel támogatott ECC eljárás nem volt megvalósítható a küldetés teljes időtartama alatt.
- A megoldásról, amely egy hardver-szoftver támogatott hibajavító eljárás, illetve a problémákról részleteket angol nyelven a Archiválva 2007. szeptember 27-i dátummal a Wayback Machine-ben honlapon találhatunk.
A különböző mélyűri és bolygókutató küldetések alapján a új hibajavító rendszereket kellett találni. A kutatás sikerrel járt, és a "one size fits all" azaz az "egy méret mindenre" hibajavító módszerek megfelelőnek látszanak, bár néhány probléma még továbbra is megoldatlan.
- A földhöz közeli küldetések alapján kiderült, hogy a "zajok" jellemzői megváltoznak, ha a jobban eltávolodunk a külső bolygóktól.
- Pontosabban, ha az űrhajón lévő, a földtől távoli adó kis teljesítménnyel dolgozik, a hibajavítás problémái főleg abban jelentkeznek, hogy a zaj szintje a földtől való távolság növekedésével együtt növekszik.
Műholdas műsorszórás (DVB)
A műholdak transzpondereinek sávszélességének növelésére folyamatos igény van, amelyet részint a televíziós csatornák (ideértve új csatornákat és a High Definition TV-t) részint az IP adatkapcsolatok táplálnak. A transzponderek hozzáférhetőségeinek és sávszélességeinek a bővítése korlátozott, mivel a transzponderek kapacitását elsődlegesen az alkalmazott modulációs módszer és az alkalmazott hibajavító kódolási (FEC) ráta határozza meg.
Scientific-Atlanta (jelenleg a Cisco Systems-hez tartozik) kidolgozott egy új kódolási eljárást a kapacitás növelésére: a Turbo kódokat összekapcsolta egy minimális komplexitású Reed-Solomon kódokkal.
Áttekintés
- A QPSK a tradicionális Reed Solomon és Viterbi kódokhoz kapcsolódik, és az elmúlt 20 évben a digitális műholdas televíziózásban használatos, gyakorlatilag egyeduralkodó megoldás volt.
- A korszerűbb modulációs megoldások, mint például a 8PSK, a 16QAM és a 32QAM lehetővé tették a műholdas iparban a transzponderek hatékonyságának néhány nagyságrenddel való növelését.
- A transzponderek átviteli rátájának növelése után a vivő teljesítménynövelése következhet – költségkihatásaival együtt – azonban itt korlátot jelentenek a jelenleg használt antennák.
- Az elvégzett tesztek alapján valószínűsíthetően a turbó kódok használatával újabb hatékonyság növekedés érhető el.
Az információelmélet alapján bizonyos, hogy egy adott hibavalószínűség esetén lehetséges olyan hibajavító kódot konstruálni, ami a hibavalószínűséget csökkenti, bár járulékos információmennyiség hozzáadásával ( redundáns adatok), ami nagy hibavalószínűség esetében nem előnyös. A Shannon korlát egy elérhető alsó korlátot határoz meg a hibajavításra (ez az elfogadható zajszint), ha állandó (mennyiségű) a redundancia, de nem ad útmutatást arra, hogy milyen kell lennie az optimális kódolónak.
A hibajavító kódok feloszthatók a blokk kódok és a konvolúciós kódok csoportjaira. Más hibajavító blokk kódok, mint a Reed-Solomon kódok átalakítják a bitek egy csoportját a bitek egy nagyobb csoportjába, olyan módon, hogy a blokkonként felismerhető és javítható hibák száma nagyobb legyen.
Sajnos, a gyakorlati tapasztalatok azt mutatják, hogy a hibák inkább hibacsomókban lépnek fel, mint véletlenszerűen elszórtan. Ezt jelenséget gyakran kompenzálják a kódolás után bitek beszúrásával (shuffling vagy interleaving). A megoldással a hibacsomósodást egybites hibává lehet átalakítani. A dekódolás előtt egy fordított folyamattal a beszúrt bitek eltávolíthatók.
- ellenőrző bit
- ellenőrző szám
- konvolúciós kódok általában az iteratív Viterbi dekódolási technikákkal dekódolhatók
- differenciális tér-idő kódok, a tér-idő blokk kódok egy csoportja.
- Erasure kódok a Fountain kódok kiterjesztései
- előremutató hibajavítás
- csoport kódok
- Golay kód, a bináris Golay kódok közül a leggyakrabban használt kódok
- Goppa kód a McEliece-féle titkosító rendszer által használt kód
- Hagelbarger kód
- Hamming kód
- hosszirányú ellenőrző összeg (Longitudinal redundancy check – LRC)
- alacsony sűrűségű paritásellenőrző kód
- LT kódok
- Online kódok
- paritásbit
- Raptor kódok a nagysebességű (csaknem valós idejű) Fountain kódok
- Reed-Solomon hibajavítás
- Reed-Muller kód
- tér-idő kód
- tér-idő trellis kód
- Tornádó kódok az optimális Fountain kódok
- Turbó kód
- Vericode rendelkezik hibajavító képességgel, és a rövidhullámú RTTY eljárások használják
- Viterbi algoritmus
- Walsh kód a celluláris telefonrendszerekben használatos, magas zajvédettsége, és ECC képességei miatt is
- Alice és Bob - 4. rész: Alice és Bob félreérti egymást
- David MacKay: The on-line textbook: Information Theory, Inference, and Learning Algorithms
- Memory errors and SECDED
- Hibajavítási szabványok: az 1037C számú Amerikai Nemzeti Szabvány, illetve a MIL-STD-188 katonai szabvány.
- Kutatói konferenciák a hibajavítás területén: 4th INTERNATIONAL SYMPOSIUM ON TURBO CODES (4. nemzetközi szimpózium a turbó kódokról) https://web.archive.org/web/20060528070056/http://www.turbo-coding-2006.org/
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
