Javító kód

A korrekciós kód (a hibajavító kód is ) egy olyan kód , amelyet a hibák észlelésére és kijavítására terveztek .

A fő technika az, hogy speciálisan strukturált redundáns információkat (például csekkszámot ) adunk a hasznos adathoz íráskor (küldés), illetve olvasáskor (fogadáskor), az ilyen redundáns információk felhasználásával a hibák észlelésére és kijavítására. A javítható hibák száma korlátozott, és a használt kódtól függ.

A hibaészlelő kódok (melyek csak a hiba tényét tudják megállapítani) a hibajavító kódokkal azonos kódosztályokba tartoznak. Valójában bármilyen hibajavító kód a hibák észlelésére is használható (ezáltal több hibát képes észlelni, mint amennyit ki tudott javítani). A hibajavító kódokat digitális kommunikációs rendszerekben használják , ideértve a következőket: műholdas, rádiórelé, cellás, telefoncsatornákon keresztüli adatátvitel, valamint információtároló rendszerekben, beleértve a mágneses és optikai rendszereket is. A hibaérzékelő kódokat a hálózati protokollok különböző szintjein használják .

A hibajavító kódok az adatokkal való munkamódszer szerint vannak felosztva blokkra , amely az információt állandó hosszúságú töredékekre osztja, és mindegyiket külön-külön dolgozza fel, valamint konvolúciós blokkra, amelyek folyamatos adatfolyamként dolgoznak az adatokkal. .

Blokkkódok

Az információt bithosszúságú töredékekre bontó és bithosszúságú kódszavakká alakító blokkkódokat általában jelölik ; a számot kódsebességnek nevezzük . Ha a kód változatlanul hagyja az eredeti biteket, és ellenőrzéseket ad hozzá, akkor az ilyen kódot szisztematikusnak , egyébként nem szisztematikusnak nevezzük . $k$ $n$ $(n,\;k)$ $R=\frac{k}{n}$ $k$ $nk$

A blokkkódot különböző módokon állíthatja be, beleértve egy táblázatot is, ahol minden információs bitkészlet a kódszó egy bitjéhez van társítva . A jó kódnak azonban meg kell felelnie legalább a következő kritériumoknak: $k$ $n$

a lehető legtöbb hiba kijavításának képessége,
a lehető legkevesebb redundancia,
a kódolás és dekódolás egyszerűsége.

A fenti követelmények általában ellentmondanak egymásnak, ezért nagyszámú kód létezik, amelyek mindegyike egy bizonyos feladatkörre alkalmas. Szinte minden használt kód lineáris , ez annak a ténynek köszönhető, hogy a nemlineáris kódokat sokkal nehezebb tanulmányozni, és nehéz számukra elfogadható könnyű kódolást és dekódolást biztosítani.

Általános formájú lineáris kódok

A lineáris blokkkód olyan kód, amelynek kódszavainak halmaza -dimenziós lineáris alteret képez a -dimenziós lineáris térben , amely izomorf a -bites vektorok terével . $k$ $C$ $n$ $k$

Ez azt jelenti, hogy a kódolási művelet megfelel az eredeti bites vektor szorzatának egy nem degenerált mátrixszal , amelyet generátormátrixnak neveznek. $k$ $G$

Az altérhez képest merőleges altérre és egy mátrixra , amely meghatározza ennek az altérnek az alapját , valamint bármely vektorra a következő igaz: $C$ $C^{\perp}$ $H$ $\overrightarrow{v}\in C$

{\overrightarrow {v}}H^{T}={\overrightarrow {0}}

. Minimális távolság és korrekciós teljesítmény

A Hamming-távolság (Hamming-metrika) két kódszó között a különböző bitek száma a megfelelő pozíciókban: $\overrightarrow{u}$ $\overrightarrow{v}$

d_H(\overrightarrow{u},\;\overrightarrow{v})=\sum_s{|u^{(s)}-v^{(s)}|}

A minimális Hamming-távolság a lineáris blokkkód fontos jellemzője. Megmutatja, milyen „távol” vannak a kódok egymástól. Meghatároz egy másik, nem kevésbé fontos jellemzőt - a korrekciós képességet : $d_\min=\min_{u\ne v}d_H(\overrightarrow{u},\;\overrightarrow{v})$

t=\left\lfloor\frac{d_\min-1}{2}\right\rfloor

A korrekciós teljesítmény határozza meg, hogy hány (típusú ) kódátviteli hiba garantálható kijavítása. Ez azt jelenti, hogy minden kódszó körül van -neighborhood , amely a kódszó továbbítására szolgáló összes lehetséges opcióból áll, legfeljebb hibával ( ) . Két kódszó két szomszédsága sem metszi egymást, mivel a kódszavak közötti távolság (vagyis e szomszédság középpontjai) mindig nagyobb, mint két sugaruk . $1\bal jobbra nyíl 0$ $A$ $t$ $Nál nél$ $A$ $1\bal jobbra nyíl 0$ $t$ $d_H(A,\;B)\geqslant d_\min>2t$

Így, miután torz kódkombinációt kapott a -tól , a dekódoló úgy dönt, hogy az eredeti kódkombináció volt , így nem javít ki több hibát. $Nál nél$ $A$ $t$

Például, ha csak két kódszó van , és a Hamming-távolság közöttük egyenlő 3, akkor a szó egy bitjének hibája javítható, mivel a kapott szó ebben az esetben is közelebb van a kódszóhoz , mint a -hoz . De ha a csatorna két bitben hibázott (amiben eltért a -tól ), akkor a hibás átvitel eredménye közelebb lesz a -hoz, és a dekóder úgy dönt, hogy a szót továbbították . $A$ $B$ $A$ $A$ $B$ $A$ $B$ $A$ $B$ $A$ $B$

Hamming kódok

A Hamming kódok a legegyszerűbb lineáris kódok, amelyek minimális távolsága 3, azaz egy hiba kijavítására alkalmas. A Hamming-kód úgy ábrázolható, hogy a szindróma a következő:

\overrightarrow{s}=\overrightarrow{r}H^T

ahol a kapott vektor, egyenlő lesz annak a pozíciónak a számával, amelyben a hiba történt. Ez a tulajdonság nagyon egyszerűvé teszi a dekódolást. $\overrightarrow{r}$

Általános módszer a sorkódok dekódolására

Bármely kód (beleértve a nemlineárist is) dekódolható egy szabályos táblázat segítségével, ahol a vett szó minden értéke a legvalószínűbb továbbított szónak felel meg . Ez a módszer azonban már viszonylag kis kódszavakhoz is hatalmas táblákat igényel. $\overrightarrow{r}_i$ $\overrightarrow{u}_i$

Lineáris kódoknál ez a módszer jelentősen leegyszerűsíthető. Ebben az esetben minden kapott vektorra kiszámítjuk a szindrómát . Mivel , ahol a kódszó és a hibavektor, akkor . Ezután a szindróma táblázat segítségével meghatározunk egy hibavektort, amelynek segítségével meghatározzuk a továbbított kódszót. Ebben az esetben a táblázat sokkal kisebb, mint az előző módszer használatakor. $\overrightarrow{r}_i$ $\overrightarrow{s}_i=\overrightarrow{r}_i H^T$ $\overrightarrow{r}_i=\overrightarrow{v}_i+\overrightarrow{e}_i$ $\overrightarrow{v}_i$ $\overrightarrow{e}_i$ $\overrightarrow{s}_i=\overrightarrow{e}_i H^T$

Lineáris ciklikus kódok

Annak ellenére, hogy a lineáris kódok dekódolása sokkal könnyebb, mint a legtöbb nemlineáris kód dekódolása, a legtöbb kód esetében ez a folyamat még mindig meglehetősen bonyolult. A ciklikus kódok az egyszerűbb dekódoláson kívül más fontos tulajdonságokkal is rendelkeznek.

A ciklikus kód egy lineáris kód , amelynek a következő tulajdonsága van: ha kódszó, akkor ciklikus permutációja is kódszó. $\overrightarrow{v}$

A ciklikus kód szavait kényelmesen polinomként ábrázolhatjuk. Például egy kódszó polinomként van ábrázolva . Ebben az esetben a kódszó ciklikus eltolása egyenértékű a polinom modulo -val való szorzásával . $\overrightarrow{v}=(v_0,\;v_1,\;\ldots,\;v_{n-1})$ $v(x)=v_0+v_1 x+\ldots+v_{n-1}x^{n-1}$ $x$ $x^n-1$

Leggyakrabban bináris ciklikus kódokat használnak (vagyis 0 vagy 1 értéket vehetnek fel). $v_0,\;v_1,\;\ldots$

Polinom generálása

Megmutatható, hogy egy adott ciklikus kód minden kódszava egy bizonyos generáló (generátor) polinom többszöröse . A generátorpolinom egy osztó . $g(x)$ $x^n-1$

Generáló polinom segítségével a kódolás ciklikus kóddal történik. Különösen:

a nem szisztematikus kódolás úgy történik, hogy a kódolt vektort megszorozzuk a következővel: ; $g(x)$ $v(x)=u(x)g(x)$
A szisztematikus kódolás úgy történik, hogy a kódolt szóhoz „hozzáadjuk” az osztás maradékát -val , azaz . $x^{nk}u(x)$ $g(x)$ $v(x)=x^{nk}u(x)+[x^{nk}u(x)\,\bmod\,g(x)]$

CRC kódok

A CRC kódok ( angolul ciklikus redundáns ellenőrzés - ciklikus redundáns ellenőrzés) olyan szisztematikus kódok, amelyeket nem a hibák kijavítására, hanem azok észlelésére terveztek. A fent vázolt szisztematikus kódolási módszert alkalmazzák: az "ellenőrző összeget" úgy számítják ki, hogy elosztják -val . Mivel nincs szükség hibajavításra, az átvitel érvényesítése ugyanúgy elvégezhető. $x^{nk}u(x)$ $g(x)$

Így a polinom alakja egy adott CRC-kódot határoz meg. Példák a legnépszerűbb polinomokra: $g(x)$

Kód név	Fokozat	Polinom
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	16	$x^{16}+x^{15}+x^{2}+1$
CRC- CCITT	16	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^ {8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

BCH kódok

A Bose-Chowdhury-Hockwingham (BCH) kódok a ciklikus kódok egy alosztálya. Megkülönböztető jellemzőjük az a képesség, hogy egy adottnál nem kisebb távolságú BCH kódot hoznak létre. Ez azért fontos, mert általánosságban elmondható, hogy a minimális kódtávolság meghatározása nagyon nehéz feladat.

Reed-Solomon hibajavító kódok

A Reed-Solomon kódok nem bináris ciklikus kódok, amelyek lehetővé teszik az adatblokkokban lévő hibák javítását. A kódvektor elemei nem bitek, hanem bitcsoportok (blokkok). Nagyon gyakoriak a bájtokkal ( oktettekkel ) működő Reed-Solomon kódok .

Matematikailag a Reed-Solomon kódok BCH kódok .

A blokkkódok előnyei és hátrányai

Bár a blokkkódok általában jól működnek a ritkán előforduló, de nagy hibasorozatokkal, kevésbé hatékonyak a gyakori, de kisebb hibák esetén (például egy AWGN -csatornában).

Konvolúciós kódok

A konvolúciós kódok, ellentétben a blokkkódokkal, nem osztják szét az információt töredékekre, és úgy dolgoznak vele, mint egy folyamatos adatfolyammal. Az ilyen kódokat általában egy diszkrét lineáris időinvariáns rendszer állítja elő . Ezért a legtöbb blokkkóddal ellentétben a konvolúciós kódolás nagyon egyszerű művelet, ami a dekódolásról nem mondható el.

A konvolúciós kódkódolást egy shift regiszter segítségével hajtják végre , amelyből a leágazásokat modulo two összegzi. Két (leggyakrabban) vagy több ilyen összeg lehet.

A konvolúciós kódokat általában a Viterbi algoritmussal dekódolják , amely megpróbálja visszaállítani a továbbított sorozatot a maximális valószínűségi kritérium szerint .

A konvolúciós kódok hatékonyan működnek fehér zajcsatornában, de nem kezelik jól a hibakitöréseket. Sőt, ha a dekóder hibát követ el, mindig hibaüzenetet produkál a kimenetén.

lépcsőzetes kódolás. Iteratív dekódolás

A különböző kódolási módszerek előnyeit összefűzött kódolás alkalmazásával lehet kombinálni . Ebben az esetben az információ először egy kóddal, majd egy másik kóddal van kódolva, ami egy termékkódot eredményez .

Például népszerű a következő konstrukció: az adatokat Reed-Solomon kóddal kódolják, majd interleavelve (közel, egymástól távol elhelyezett karakterekkel) és konvolúciós kóddal kódolják. A vevőnél először a konvolúciós kódot dekódolják, majd fordított interleavelést hajtanak végre (ebben az esetben a konvolúciós dekódoló kimenetén lévő hibakitörések a Reed-Solomon kód különböző kódszavaira esnek), majd a Reed- A Salamon kód dekódolásra kerül.

Egyes termékkódokat kifejezetten iteratív dekódolásra tervezték, amelyben a dekódolás több lépésben történik, mindegyik az előzőből származó információk felhasználásával. Ez nagy hatékonyságot tesz lehetővé, de a dekódolás erőforrásigényes. Ezek a kódok tartalmazzák a turbó kódokat és az LDPC kódokat (Gallager kódok).

A kódok hatékonyságának értékelése

A kódok hatékonyságát a javítható hibák száma, a hozzáadandó redundáns információ mennyisége, valamint a kódolás és dekódolás megvalósításának összetettsége (mind hardver, mind számítógépes szoftver ) határozza meg.

Hamming kötött és tökéletes kódok

Legyen egy korrekciós képességű bináris blokkkód . Ekkor az egyenlőtlenség (amelyet Hamming-korlátnak neveznek) teljesül: $(n,k)$ $t$

\sum_{i=0}^t {n\choose i}\leqslant 2^{nk}.

Azokat a kódokat, amelyek teljesítik ezt az egyenlőségi korlátot, tökéletesnek nevezzük. A tökéletes kódok közé tartoznak például a Hamming-kódok . A gyakorlatban gyakran használt , nagy korrekciós erővel rendelkező kódok (például Reed-Solomon kódok ) nem tökéletesek.

Irodalom

Blahut R. A hibaellenőrző kódok elmélete és gyakorlata. — M .: Mir , 1986. — 576 p.
McWilliams F. J., Sloan N. J. A. Hibajavító kódok elmélete. Moszkva: Rádió és kommunikáció, 1979.
Morelos-Zaragoza R. A hibajavító kódolás művészete. Módszerek, algoritmusok, alkalmazás / per. angolról. V. B. Afanasjev . - M . : Technosfera, 2006. - 320 p. — (A kommunikáció világa). - 2000 példányban. — ISBN 5-94836-035-0 .