A hibajavító kódokat
Hibajavító kódok (hibajavító kód hibajavító kódok zaj-rezisztens kódok ..) - kódok arra szolgálnak, hogy kijavítsák a hibákat keletkező információk továbbítására hatása alatt beavatkozást, valamint a tárolás.
Ebből a célból a felvétel (transzfer) a hasznos adatokat add speciális szerkezetű redundáns információ, és az olvasás (fogadó) használják felismerni és javítani a hibákat. Természetesen a hibák száma korrigálható korlátozott, és függ az adott kódot.
A kód, hibajavítást szorosan kapcsolódó hibajelző kódot. Ellentétben az első, az utóbbit csak megállapítására, hogy a hibák a továbbított adatokat, de nem oldja meg.
Tény, hogy a hibajelző kódot használják tartoznak azonos kategóriába tartozó kód, mint a hibajavító kódokat. Sőt, bármilyen kódot, kijavítani a hibákat, és fel lehet használni a hibákat. Így van értelme vizsgálni ezeket a fogalmakat együtt.
A találmány egy működtető eljárás az adatok hibajavító kódok vannak osztva a blokk. elosztjuk az információkat darabokra konstans hosszúságú és kezelni mindegyiket külön-külön, és konvolúció. adatok feldolgozására, mint folyamatos.
Példaként egy egyszerű blokk-kódot, akkor adja meg a code-ismétlés. ahol minden egyes szimbólum vagy blokk információ átvitelére van többször. Azonban ez a kód nagyon alacsony hatásfokú (cm. Alább).
blokk kódok
Hagyja, hogy a kódolt információt töredékekre van osztva k bit, amelyek alakítjuk kódszavak n bit hosszúságú. Ezután a megfelelő blokkban kódot általában jelöljük (n, k). Továbbá számos \ frac hívják a kódot arány.
Ha a forráskód k bit érintetlen marad, és hozzáteszi n - kproverochnyh. ezt nevezik szisztematikus kódot. egyébként rendszertelen.
Tegyen fel egy blokk-kód különböző lehet, beleértve a táblázatban, ahol az egyes készlet k információt leképezett bitek n bit a kódszó. Azonban egy jó kódot kell felelnie legalább a következő feltételeknek:
- képességét, hogy helyes, amennyire csak lehetséges, a hibák száma,
- redundancia a lehető legkevésbé,
- enyhíteni a kódolás és dekódolás.
Könnyen belátható, hogy a fenti követelmények ellentmondásosak. Éppen ezért van egy nagy számú kódot, amelyek mindegyike alkalmas alkalmazási területei.
Gyakorlatilag az összes használt kódok lineáris. Ez annak a ténynek köszönhető, hogy a nemlineáris kódok sokkal nehezebb, hogy megvizsgálja és nehéz őket, hogy elfogadható könnyű kódolás és dekódolás.
Lineáris kódok általános formája
A lineáris blokk-kód - a kód olyan, hogy annak több kód-szó képez k-dimenziós lineáris altér (nevezzük C) n-dimenziós vektortér. izomorf a tér k bit vektorok.
Ez azt jelenti, hogy a kódolási művelet megfelel megszorozzuk k-bites kezdővektort egy nonsingular mátrix G. nevezett a generátor mátrixot.
Legyen C ^ - ortogonális tekintetében a altér C. és H - mátrix meghatározása alapján ez az altér. Ekkor minden vektor \ overrightarrow \ C igaz:
Minimális távolság és korrekciós képesség
A Hamming-távolság (a Hamming metrikus) közötti két kódszó \ overrightarrow és \ overrightarrow a számos különböző bitek a megfelelő pozíciókban, azaz a száma „egyesek” egy vektor \ overrightarrow \ Oplus \ overrightarrow.
A minimális Hamming-távolság (Dmin) egy fontos jellemzője a lineáris blokk-kódot. Ez határozza meg a másik, nem kevésbé fontos jellemzője - korrigáló képesség:
- t = \ cal \ frac-1> \ cal. Itt a szög, zárójelben kerekítés „lefelé”.
Korrekciós képessége határozza meg, hogy hány kódot hibákat lehet garantálni a helyes.
Itt egy példa. Tegyük fel, hogy van két kódszót A és B, a Hamming-távolság közöttük egyenlő 3. Ha az A szó került át, és a csatorna hibájának egy kicsit, akkor lehet korrigálni, hiszen ebben az esetben is a szó legközelebb a vett kódszó A mint a B. De ha csatornát hibák történtek két bit, a dekóder tudja számítani, hogy továbbították szó B.
Hamming kódok
Hamming kódok - egyszerű lineáris kódok minimális távolság 3, amely képes kijavítani egy hibát. Hamming-kód is képviselteti magát olyan formában, hogy a szindróma
- \ Overrightarrow = \ overrightarrow H ^ T. ahol \ overrightarrow - vett vektor,
alapértelmezett a pozíció, ahol a hiba történt. Ez a funkció lehetővé teszi, hogy egy nagyon egyszerű dekódolást.
General Linear Codes dekódoló eljárás
Bármely szám (beleértve a nem-lineáris) lehet dekódolni segítségével rendszeresen asztalhoz, ahol az egyes értékek a vett szó \ overrightarrow megfelel a legvalószínűbb által továbbított szó \ overrightarrow. Azonban ez a módszer nem igényel hatalmas asztal kódszó már viszonylag kis hosszúságú.
Lineáris kódok, ez a módszer nagymértékben egyszerűsíthető. Így minden egyes vett vektor \ overrightarrow számított szindróma \ overrightarrow = \ overrightarrow H ^ T. Mivel a \ overrightarrow = \ overrightarrow + \ overrightarrow. ahol \ overrightarrow - egy kódszó, és \ overrightarrow - vektor hibák, \ overrightarrow = \ overrightarrow H ^ T. Ezután, szindróma táblázat határozza meg hibavektort, alkalmazásával határozzuk meg a továbbított kódszó. Ugyanannál az asztalnál egy sokkal kisebb, mint az előző módszerrel.
Lineáris gyűrűs kódok
Annak ellenére, hogy a dekódolás lineáris kódok már sokkal könnyebb dekódolni a legtöbb nem-lineáris, ez a folyamat még mindig elég nehéz a legtöbb kódokat. Ciklikus kódok más, mint egy egyszerű dekódolási rendelkeznek más fontos tulajdonságokkal.
A ciklikus kód egy lineáris kód, az alábbi tulajdonságokkal: ha \ overrightarrow egy kódszó, ez is egy ciklikus permutációja kódszót.
ciklikus kódszó módon jelen formájában polinomok. Például, a kódszó \ overrightarrow = (v_0, v_1. V_) képviseli, mint egy polinom v (x) = v0 + V1X +. + Vn - 1xN - 1. Ebben az esetben, a ciklikus eltolása a kódszó egyenértékű megszorozzuk a polinom által x modulo xn - 1.
A következőkben, hacsak másként nem jelezzük, azt feltételezzük, hogy a ciklikus kód bináris. azaz v0, v1, ... vehet értéke 0 vagy 1.
generáló polinom
Belátható, hogy az összes kódszót egy adott ciklikus kódot többszörösei egy adott előállító polinomug (x). Generálása polinom osztója xn - 1.
A generátor polinommal végezzük kódolását ciklikus kódot. Különösen:
Kódok CRC (ciklikus redundancia ellenőrzés - ciklikus redundancia-ellenőrzés) kódok rendszeres, nem arra tervezték, hogy kijavítsa a hibákat, és felismerni őket. Ezek használata szisztematikus kódolási eljárás fentebb leírt: „ellenőrző összeg” hányadosaként számítottuk ki xn - ku (x) a g (x). Tekintettel arra, hogy a hibák kijavítását nem szükséges, validálása átvitel lehet elvégezni ugyanúgy.
Így, az a fajta polinom g (x) meghatározza egy adott kódot CRC. Példák a legnépszerűbb polinomok:
Kódok Bose-Chaudhuri-Hocquenghem (BCH) olyan alosztályát bináris ciklikus kódok. A megkülönböztető jellemzője - a lehetőséget az épület egy BCH kód minimális távolság nem kevesebb, mint a megadott. Ez azért fontos, mert általában elmondható, hogy a meghatározás a minimális távolság a kód egy nagyon nehéz feladat.
Matematikailag építési BCH kódok és azok dekódolási bomlás közben generátor polinom g (x) a tényezők a Galois mezőben.
Reed-Solomon kódok
Reed-Solomon-kód (RS kódok) gyakorlatilag nem bináris BCH kódok, azaz a kód vektor elemek nem bit és csoportok bitek. Nagyon gyakori Reed-Solomon kódok, dolgozó bájt (oktett).
Előnyök és hátrányok a blokk kódok
Bár a blokk-kódok általában jól egy pár, de nagy tételben hibákat. hatékonyságukat gyakori, de kis hiba (például egy csatornát, fehér zaj), kevésbé magas.
konvolúciós kódok
Konvolúciós kódok, ellentétben a blokk, nem osztja az információkat darabokra, és dolgozni vele, mint egy folyamatos adatáramlást.
Konvolúciós kódok. Általában egy diszkrét lineáris idő-invariáns rendszerben. Ezért, ellentétben a legtöbb blokk kódok, konvolúciós kódolás - egy nagyon egyszerű művelet, amely nem a dekódolást.
Konvolúciókód kódolás alkalmazásával végezzük a léptetőregiszter, a csapokat, amelyek összeadódnak modulo két. Ezeket a mennyiségeket a két (leggyakrabban) vagy több.
Dekódolás konvolúciós kódot általában a Viterbialgoritmusos, amely igyekszik rekonstruálni az átvitt szekvenciát a maximális valószínűség.
Előnyök és hátrányok a konvolúciós kódok
Konvolúciós kódok hatékonyan működik egy csatornát, fehér zaj, de nem megbirkózni tör a hibákat. Továbbá, ha a dekóder rossz, a kimenet mindig egy burst hibát.
Láncolt kódolás. Turbo-kódok
Előnyei különböző kódolási módszerek kombinálhatók alkalmazásával láncolású kódolás. Ha ez az információ az első kódolt egyetlen kódot, majd a másik, az eredmény egy code-termék.
Például, a népszerű design a következő: az adatok kódolva Reed-Solomon-kódot, majd összeszőjük (a szimbólumok, amelyek közel vannak, messze vannak elhelyezve egymással), és vannak kódolva konvolúciós kódot. A vevőnél első dekódolja a konvolúciós kódot, majd végzett deinterleave (a tört hibák kimenetén konvolúciós dekóder esnek különböző kódszó a Reed-Solomon-kód), majd végzett a Reed-Solomon kód dekódolása.
Egyes kódok termék-kifejezetten iteratív dekódoló. ahol a dekódolás végezzük több menetben, amelyek mindegyike származó információt használja az előzőt. Ezeket a kódokat „turbó-kód”, és lehetővé teszi a nagyobb hatékonyság, de a dekódolás igényel sok erőforrást.
Hatékonyságának értékelése kódok
Hatékonyság kódok száma határozza meg a hibákat, hogy javítani tudja az egyik, az összeg a redundáns információ, amely előírja, hogy az adagolás és összetettségét kódolási és dekódolási (hardveres és egy számítógépes program).
Border Hamming és perfekt kódok
Legyen egy bináris blokk (n, k) kód hibajavító képességét t. Ezután az egyenlőtlenség (az úgynevezett Hamming külföldön):
Kódok megfelelnek ennek a határ közötti egyenlőség, az úgynevezett tökéletes. Ahhoz, hogy tökéletes kódok közé tartozik például, Hamming kódok. Gyakran használják a gyakorlatban kód nagy hibajavító képességgel (mint például a Reed-Solomon-kód) nem tökéletes.
energia nyereség
Mivel a zajmentes kódolás lehetővé teszi a hibák kijavítására, ha használják az adóteljesítmény lehet csökkenteni, így az adatátviteli sebesség nem változott. Energia nyereség meghatározása a különbség értéke \ frac jelenlétében és távollétében a kódot. Itt Eb - bit energia (teljesítmény jelet osztva a sebességet információcsere) és N0 - zaj spektrális teljesítménysűrűség.
Használata a hibajavító kódokat
Hibajavító kódokat használják:
Kódok, hibákat, amelyek használják a hálózati protokollok a különböző szinteken.