Rettelse kode

Korrektionskode (også fejlkorrigerende kode ) er en kode designet til at opdage og rette fejl .

Hovedteknikken er at tilføje specielt struktureret redundant information (f.eks. checknummer ) til nyttelasten ved skrivning (transmittering) og ved læsning (modtagelse) ved at bruge sådan redundant information til at opdage og rette fejl. Antallet af fejl, der kan rettes, er begrænset og afhænger af den specifikke kode, der bruges.

Fejldetekteringskoder (som kun kan fastslå en fejl) hører til de samme klasser af koder som fejlkorrigerende koder. Faktisk kan enhver fejlkorrigerende kode også bruges til at opdage fejl (ved at gøre det, vil den være i stand til at opdage flere fejl, end den var i stand til at rette). Fejlkorrigerende koder bruges i digitale kommunikationssystemer , herunder: satellit, radiorelæ, mobil, datatransmission over telefonkanaler såvel som i informationslagringssystemer, herunder magnetiske og optiske. Fejldetekterende koder bruges i forskellige niveauer af netværksprotokoller .

I overensstemmelse med den måde, de arbejder med data på, er fejlkorrigerende koder opdelt i blok , som opdeler information i fragmenter af konstant længde og behandler hver af dem separat, og foldningskoder , som arbejder med data som en kontinuerlig strøm .

Bloker koder

En blokkode, der opdeler information i bitlængdefragmenter og konverterer dem til bitlængdekodeord, betegnes normalt ; nummeret kaldes kodesatsen . Hvis koden efterlader de originale bits uændrede og tilføjer kontroller, kaldes en sådan kode systematisk , ellers - ikke- systematisk . $k$ $n$ $(n,\;k)$ $R=\frac{k}{n}$ $k$ $nk$

Du kan indstille blokkoden på forskellige måder, herunder en tabel, hvor hvert sæt informationsbits er knyttet til en bit af kodeordet. God kode skal dog mindst opfylde følgende kriterier: $k$ $n$

evnen til at rette så mange fejl som muligt,
så lidt redundans som muligt,
nem indkodning og afkodning.

Ovenstående krav modsiger generelt hinanden, så der er et stort antal koder, som hver især egner sig til en bestemt række opgaver. Næsten alle brugte koder er lineære , dette skyldes det faktum, at ikke-lineære koder er meget sværere at studere, og det er svært for dem at give en acceptabel nem kodning og afkodning.

Lineære koder af generel form

En lineær blokkode er en sådan kode, at sættet af dets kodeord danner et -dimensionelt lineært underrum i -dimensionelt lineært rum , isomorf med rummet af -bitvektorer . $k$ $C$ $n$ $k$

Dette betyder, at indkodningsoperationen svarer til multiplikationen af den oprindelige -bit-vektor med en ikke-degenereret matrix , kaldet generatormatrixen. $k$ $G$

For et underrum ortogonalt med hensyn til og en matrix , der definerer grundlaget for dette underrum, og for enhver vektor , gælder følgende: $C$ $C^{\perp}$ $H$ $\overrightarrow{v}\i C$

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

. Minimum afstand og korrigerende kraft

Hamming-afstanden (Hamming-metrikken) mellem to kodeord er antallet af forskellige bits i de tilsvarende positioner: $\overrightarrow{u}$ $\overrightarrow{v}$

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

Den mindste Hamming-afstand er en vigtig egenskab ved en lineær blokkode. Det viser, hvor "langt" koderne er fra hinanden. Den definerer en anden, ikke mindre vigtig egenskab - korrigerende evne : $d_\min=\min_{u\ne v}d_H(\overhøjrepil{u},\;\overhøjrepil{v})$

t=\venstre\lgulv\frac{d_\min-1}{2}\højre\rgulv

Korrektionskraften bestemmer, hvor mange kodetransmissionsfejl (af typen ) der kan garanteres at blive rettet. Det vil sige, at vi omkring hvert kodeord har -naboskab , som består af alle mulige muligheder for at sende kodeordet med antallet af fejl ( ) ikke mere end . Ingen to kvarterer af to kodeord skærer hinanden, da afstanden mellem kodeord (det vil sige centrene af disse kvarterer) altid er større end to af deres radier . $1\venstrehøjrepil 0$ $EN$ $t$ $På$ $EN$ $1\venstrehøjrepil 0$ $t$ $d_H(A,\;B)\geqslant d_\min>2t$

Efter at have modtaget en forvrænget kodekombination fra , beslutter dekoderen, at den oprindelige kodekombination var , og korrigerede derved ikke flere fejl. $På$ $EN$ $t$

For eksempel, hvis der kun er to kodeord og med en Hamming-afstand mellem dem lig med 3, kan en fejl i en bit af ordet rettes, da det modtagne ord selv i dette tilfælde er tættere på kodeordet end på . Men hvis kanalen introducerede fejl i to bits (hvor den afveg fra ), så vil resultatet af en fejlagtig transmission være tættere på end , og dekoderen vil beslutte, at ordet blev transmitteret . $EN$ $B$ $EN$ $EN$ $B$ $EN$ $B$ $EN$ $B$ $EN$ $B$

Hamming-koder

Hamming-koder er de enkleste lineære koder med en minimumsafstand på 3, det vil sige i stand til at rette en fejl. Hamming-koden kan repræsenteres på en sådan måde, at syndromet er:

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

hvor er den modtagne vektor, vil være lig med nummeret på den position, hvor fejlen opstod. Denne egenskab gør afkodning meget let. $\overrightarrow{r}$

Generel metode til afkodning af linjekoder

Enhver kode (inklusive ikke-lineær) kan afkodes ved hjælp af en almindelig tabel, hvor hver værdi af det modtagne ord svarer til det mest sandsynlige overførte ord . Denne metode kræver dog allerede brug af store tabeller for relativt små kodeord. $\overrightarrow{r}_i$ $\overhøjrepil{u}_i$

For lineære koder kan denne metode forenkles betydeligt. I dette tilfælde beregnes syndromet for hver modtaget vektor . Siden , hvor er kodeordet og er fejlvektoren, så . Derefter bestemmes en fejlvektor ved hjælp af syndromtabellen, ved hjælp af hvilken det transmitterede kodeord bestemmes. I dette tilfælde er bordet meget mindre end ved brug af den tidligere metode. $\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ære cykliske koder

På trods af at afkodning af lineære koder er meget nemmere end at afkode de fleste ikke-lineære koder, er denne proces for de fleste koder stadig ret kompliceret. Cykliske koder har udover enklere afkodning andre vigtige egenskaber.

En cyklisk kode er en lineær kode med følgende egenskab: hvis er et kodeord, så er dens cykliske permutation også et kodeord. $\overrightarrow{v}$

Ordene i en cyklisk kode er bekvemt repræsenteret som polynomier. For eksempel er et kodeord repræsenteret som et polynomium . I dette tilfælde er det cykliske skift af kodeordet ækvivalent med at multiplicere polynomiet med modulo . $\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$

Oftest bruges binære cykliske koder (det vil sige, at de kan antage værdierne 0 eller 1). $v_0,\;v_1,\;\ldots$

Generering af polynomium

Det kan vises, at alle kodeord i en bestemt cyklisk kode er multipla af et bestemt genererende (generator) polynomium . Generatorpolynomiet er en divisor . $g(x)$ $x^n-1$

Ved hjælp af et genererende polynomium udføres kodning af en cyklisk kode. I særdeleshed:

ikke-systematisk kodning udføres ved at gange den kodede vektor med : ; $g(x)$ $v(x)=u(x)g(x)$
systematisk kodning udføres ved at "føje" til det kodede ord resten af divisionen med , dvs. $x^{nk}u(x)$ $g(x)$ $v(x)=x^{nk}u(x)+[x^{nk}u(x)\,\bmod\,g(x)]$

CRC-koder

CRC - koder ( engelsk cyclic redundancy check - cyclic redundant check) er systematiske koder designet til ikke at rette fejl, men til at opdage dem. De bruger den systematiske kodningsmetode, der er skitseret ovenfor: "kontrolsummen" beregnes ved at dividere med . Da der ikke kræves fejlkorrektion, kan transmissionsvalidering udføres på samme måde. $x^{nk}u(x)$ $g(x)$

Således angiver formen af polynomiet en specifik CRC-kode. Eksempler på de mest populære polynomier: $g(x)$

Kodenavn	Grad	Polynomium
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-koder

Bose-Chowdhury-Hockwingham (BCH) koder er en underklasse af cykliske koder. Deres kendetegn er evnen til at konstruere en BCH-kode med en minimumsafstand, der ikke er mindre end en given. Dette er vigtigt, fordi det generelt er en meget vanskelig opgave at bestemme minimumskodeafstanden.

Reed-Solomon fejlkorrektionskoder

Reed-Solomon-koder er ikke-binære cykliske koder, der giver dig mulighed for at rette fejl i datablokke. Kodevektorens elementer er ikke bit, men grupper af bit (blokke). Reed-Solomon-koder, der fungerer på bytes ( oktetter ), er meget almindelige.

Matematisk er Reed-Solomon-koder BCH-koder .

Fordele og ulemper ved blokkoder

Selvom blokkoder generelt klarer sig godt med sjældne, men store fejlbyger , er de mindre effektive til hyppige, men små fejl (for eksempel i en AWGN -kanal).

Konvolutionskoder

Konvolutionskoder, i modsætning til blokkoder, opdeler ikke information i fragmenter og arbejder med det som med en kontinuerlig datastrøm. Sådanne koder genereres som regel af et diskret lineært tidsinvariant system . Derfor, i modsætning til de fleste blokkoder, er foldningskodning en meget enkel operation, som ikke kan siges om afkodning.

Konvolutionskodekodning udføres ved hjælp af et skifteregister , hvorfra tapene summeres modulo to. Der kan være to (oftest) eller flere sådanne summer.

Konvolutionskoder afkodes normalt ved hjælp af Viterbi-algoritmen , som forsøger at gendanne den transmitterede sekvens i henhold til kriteriet for maksimal sandsynlighed .

Konvolutionskoder fungerer effektivt i en kanal med hvid støj, men håndterer ikke fejlbursts godt. Desuden, hvis dekoderen laver en fejl, producerer den altid en fejlburst ved dens udgang.

kaskadende kodning. Iterativ afkodning

Fordelene ved forskellige kodningsmetoder kan kombineres ved at anvende sammenkædet kodning . I dette tilfælde kodes informationen først med én kode og derefter med en anden, hvilket resulterer i en produktkode .

For eksempel er følgende konstruktion populær: dataene kodes med Reed-Solomon-koden, indflettes derefter (med tegn placeret tæt på, placeret langt fra hinanden) og kodes med en foldningskode. Ved modtageren afkodes først foldningskoden, derefter udføres omvendt interleaving (i dette tilfælde falder fejludbruddene ved outputtet af foldningsdekoderen ind i forskellige kodeord i Reed-Solomon-koden), og derefter Reed- Solomon-koden er afkodet.

Nogle produktkoder er specifikt designet til iterativ afkodning, hvor afkodning udføres i flere omgange, hver ved hjælp af information fra den foregående. Dette giver mulighed for stor effektivitet, men afkodning er ressourcekrævende. Disse koder inkluderer turbokoder og LDPC-koder (Gallager-koder).

Evaluering af koders effektivitet

Effektiviteten af koder bestemmes af antallet af fejl, som den kan rette, mængden af redundant information, der skal tilføjes, og kompleksiteten af implementeringen af kodning og afkodning (både hardware og computersoftware ).

Hamming bundne og perfekte koder

Lad der være en binær blokkode med korrigerende evne . Så gælder uligheden (kaldet Hamming-bundet): $(n,k)$ $t$

\sum_{i=0}^t {n\vælg i}\leqslant 2^{nk}.

Koder, der opfylder denne lighedsgrænse, kaldes perfekte. Perfekte koder omfatter for eksempel Hamming-koder . Koder med stor korrigerende kraft , der ofte bruges i praksis (såsom Reed-Solomon-koder ) er ikke perfekte.

Litteratur

Blahut R. Teori og praksis for fejlkontrolkoder. — M .: Mir , 1986. — 576 s.
McWilliams F. J., Sloan N. J. A. Teori om fejlkorrigerende koder. Moskva: Radio og kommunikation, 1979.
Morelos-Zaragoza R. Kunsten at fejlkorrigere kodning. Metoder, algoritmer, anvendelse / pr. fra engelsk. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 s. — (kommunikationens verden). - 2000 eksemplarer. — ISBN 5-94836-035-0 .