Korrigeringskod

Korrigeringskod (även felkorrigerande kod ) är en kod utformad för att upptäcka och korrigera fel .

Huvudtekniken är att lägga till speciellt strukturerad redundant information (till exempel checknummer ) till nyttolasten vid skrivning (sändning) och vid läsning (mottagning), med hjälp av sådan redundant information för att upptäcka och korrigera fel. Antalet fel som kan korrigeras är begränsat och beror på vilken kod som används.

Feldetekteringskoder (som bara kan fastställa ett fel) tillhör samma klasser av koder som felkorrigeringskoder. Faktum är att vilken felkorrigerande kod som helst kan också användas för att upptäcka fel (genom att göra det kommer den att kunna upptäcka fler fel än vad den kunde fixa). Felkorrigerande koder används i digitala kommunikationssystem , inklusive: satellit, radiorelä, mobil, dataöverföring över telefonkanaler, såväl som i informationslagringssystem, inklusive magnetiska och optiska. Felupptäckande koder används i olika nivåer av nätverksprotokoll .

Beroende på hur de arbetar med data är felkorrigerande koder indelade i block , som delar upp information i fragment med konstant längd och bearbetar var och en av dem separat, och faltningskoder , som arbetar med data som en kontinuerlig ström .

Blockera koder

En blockkod som bryter information i bitlängdsfragment och omvandlar dem till bitlängdskodord betecknas vanligtvis ; numret kallas kodkursen . Om koden lämnar de ursprungliga bitarna oförändrade och lägger till kontroller kallas en sådan kod systematisk , annars - icke- systematisk . $k$ $n$ $(n,\;k)$ $R=\frac{k}{n}$ $k$ $nk$

Du kan ställa in blockkoden på olika sätt, inklusive en tabell där varje uppsättning informationsbitar är associerade med en bit av kodordet. Bra kod måste dock uppfylla åtminstone följande kriterier: $k$ $n$

förmågan att rätta till så många fel som möjligt,
så lite redundans som möjligt,
enkel kodning och avkodning.

Ovanstående krav motsäger i allmänhet varandra, så det finns ett stort antal koder, som var och en är lämplig för ett visst antal uppgifter. Nästan alla använda koder är linjära , detta beror på att icke-linjära koder är mycket svårare att studera, och det är svårt för dem att ge en acceptabel enkel kodning och avkodning.

Linjära koder av allmän form

En linjär blockkod är en sådan kod att uppsättningen av dess kodord bildar ett -dimensionellt linjärt delrum i -dimensionellt linjärt utrymme , isomorft till utrymmet av -bitvektorer . $k$ $C$ $n$ $k$

Detta betyder att kodningsoperationen motsvarar multiplikationen av den ursprungliga -bitvektorn med en icke-degenererad matris , kallad generatormatrisen. $k$ $G$

För ett underutrymme ortogonalt med avseende på och en matris som definierar grunden för detta underrum, och för vilken vektor som helst , gäller följande: $C$ $C^{\perp}$ $H$ $\overrightarrow{v}\i C$

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

. Minsta avstånd och korrigerande kraft

Hamming-avståndet (Hamming-metriken) mellan två kodord är antalet olika bitar i motsvarande positioner: $\overrightarrow{u}$ $\overrightarrow{v}$

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

Minsta Hamming-avstånd är en viktig egenskap hos en linjär blockkod. Den visar hur "långt" koderna är från varandra. Den definierar en annan, inte mindre viktig egenskap - korrigerande förmåga : $d_\min=\min_{u\ne v}d_H(\överhögerpil{u},\;\överhögerpil{v})$

t=\vänster\lgolv\frac{d_\min-1}{2}\höger\rgolv

Korrigeringskraften avgör hur många kodöverföringsfel (av typen ) som kan garanteras korrigeras. Det vill säga, runt varje kodord har vi -neighborhood , som består av alla möjliga alternativ för att överföra kodordet med antalet fel ( ) högst . Inga två grannskap av två kodord skär varandra, eftersom avståndet mellan kodorden (det vill säga mitten av dessa grannskap) alltid är större än två av deras radier . $1\vänsterhögerpil 0$ $A$ $t$ $På$ $A$ $1\vänsterhögerpil 0$ $t$ $d_H(A,\;B)\geqslant d_\min>2t$

Sålunda, efter att ha mottagit en förvrängd kodkombination från , beslutar avkodaren att den ursprungliga kodkombinationen var , och korrigerar därmed inga fler fel. $På$ $A$ $t$

Till exempel, om det bara finns två kodord och med ett Hamming-avstånd mellan dem lika med 3, kan ett fel i en bit av ordet korrigeras, eftersom även i detta fall det mottagna ordet är närmare kodordet än . Men om kanalen introducerade fel i två bitar (där den skilde sig från ), kommer resultatet av en felaktig överföring att vara närmare än , och avkodaren kommer att bestämma att ordet överfördes . $A$ $B$ $A$ $A$ $B$ $A$ $B$ $A$ $B$ $A$ $B$

Hamming-koder

Hammingkoder är de enklaste linjära koderna med ett minsta avstånd på 3, det vill säga kan korrigera ett fel. Hamming-koden kan representeras på ett sådant sätt att syndromet är:

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

där är den mottagna vektorn, kommer att vara lika med numret på den position där felet inträffade. Denna egenskap gör avkodningen mycket enkel. $\overrightarrow{r}$

Allmän metod för avkodning av radkoder

Vilken kod som helst (inklusive icke-linjär) kan avkodas med hjälp av en vanlig tabell, där varje värde på det mottagna ordet motsvarar det mest sannolika sända ordet . Den här metoden kräver dock användning av stora tabeller redan för relativt små kodord. $\overrightarrow{r}_i$ $\överhögerpil{u}_i$

För linjära koder kan denna metod förenklas avsevärt. I det här fallet, för varje mottagen vektor , beräknas syndromet . Eftersom , var är kodordet och är felvektorn, då . Sedan, med hjälp av syndromtabellen, bestäms en felvektor, med hjälp av vilken det överförda kodordet bestäms. I det här fallet är tabellen mycket mindre än när du använder den tidigare metoden. $\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$

Linjära cykliska koder

Trots det faktum att avkodning av linjära koder är mycket lättare än att avkoda de flesta icke-linjära koder, är denna process fortfarande ganska komplicerad för de flesta koder. Cykliska koder har, förutom enklare avkodning, andra viktiga egenskaper.

En cyklisk kod är en linjär kod med följande egenskap: om är ett kodord, då är dess cykliska permutation också ett kodord. $\overrightarrow{v}$

Orden i en cyklisk kod representeras lämpligen som polynom. Till exempel representeras ett kodord som ett polynom . I detta fall är kodordets cykliska skiftning ekvivalent med att multiplicera polynomet 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$

Oftast används binära cykliska koder (det vill säga de kan anta värdena 0 eller 1). $v_0,\;v_1,\;\ldots$

Genererar polynom

Det kan visas att alla kodord för en viss cyklisk kod är multipler av ett visst genererande (genererande) polynom . Generatorpolynomet är en divisor . $g(x)$ $x^n-1$

Med hjälp av ett genererande polynom utförs kodning av en cyklisk kod. Särskilt:

icke-systematisk kodning utförs genom att multiplicera den kodade vektorn med : ; $g(x)$ $v(x)=u(x)g(x)$
systematisk kodning utförs genom att ”lägga till” till det kodade ordet resten av divisionen med , det vill säga . $x^{nk}u(x)$ $g(x)$ $v(x)=x^{nk}u(x)+[x^{nk}u(x)\,\bmod\,g(x)]$

CRC-koder

CRC- koder ( engelska cyclic redundancy check - cyclic redundant check) är systematiska koder utformade för att inte korrigera fel, utan för att upptäcka dem. De använder den systematiska kodningsmetoden som beskrivs ovan: "kontrollsumman" beräknas genom att dividera med . Eftersom ingen felkorrigering krävs kan överföringsvalidering göras på samma sätt. $x^{nk}u(x)$ $g(x)$

Således anger formen av polynomet en specifik CRC-kod. Exempel på de mest populära polynomen: $g(x)$

Kodnamn	Grad	Polynom
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 är en underklass av cykliska koder. Deras utmärkande särdrag är förmågan att konstruera en BCH-kod med ett minsta avstånd som inte är mindre än ett givet. Detta är viktigt eftersom det generellt sett är en mycket svår uppgift att bestämma minimikodavståndet.

Reed-Solomon felkorrigeringskoder

Reed-Solomon-koder är icke-binära cykliska koder som låter dig korrigera fel i datablock. Elementen i kodvektorn är inte bitar, utan grupper av bitar (block). Reed-Solomon-koder som fungerar på byte ( oktetter ) är mycket vanliga.

Matematiskt är Reed-Solomon-koder BCH-koder .

Fördelar och nackdelar med blockkoder

Även om blockkoder i allmänhet klarar sig bra med sällsynta men stora felskurar , är de mindre effektiva för frekventa men små fel (till exempel i en AWGN- kanal).

Konvolutionskoder

Konvolutionskoder, till skillnad från blockkoder, delar inte upp information i fragment och arbetar med den som med en kontinuerlig dataström. Sådana koder genereras som regel av ett diskret linjärt tidsinvariant system . Därför, till skillnad från de flesta blockkoder, är faltningskodning en mycket enkel operation, som inte kan sägas om avkodning.

Konvolutionskodskodning utförs med användning av ett skiftregister , vars tappningar summeras modulo två. Det kan vara två (oftast) eller fler sådana summor.

Konvolutionskoder avkodas vanligtvis med Viterbi-algoritmen , som försöker återställa den överförda sekvensen enligt kriteriet för maximal sannolikhet .

Konvolutionskoder fungerar effektivt i en kanal med vitt brus, men hanterar inte bra felskurar. Dessutom, om avkodaren gör ett misstag, producerar den alltid en felskur vid dess utgång.

kaskadkodning. Iterativ avkodning

Fördelarna med olika kodningsmetoder kan kombineras genom att tillämpa konkatenerad kodning . I det här fallet kodas informationen först med en kod och sedan med en annan, vilket resulterar i en produktkod .

Till exempel är följande konstruktion populär: data kodas med Reed-Solomon-koden, interfolieras sedan (med tecken placerade nära, placerade långt från varandra) och kodas med en faltningskod. Vid mottagaren avkodas först faltningskoden, sedan utförs omvänd interfoliering (i detta fall faller felskurarna vid utgången av faltningsavkodaren in i olika kodord i Reed-Solomon-koden), och sedan Reed- Solomon-koden är avkodad.

Vissa produktkoder är speciellt utformade för iterativ avkodning, där avkodningen görs i flera omgångar, var och en med hjälp av information från den föregående. Detta möjliggör stor effektivitet, men avkodning är resurskrävande. Dessa koder inkluderar turbokoder och LDPC-koder (Gallager-koder).

Utvärdering av koders effektivitet

Kodernas effektivitet bestäms av antalet fel som den kan korrigera, mängden redundant information som måste läggas till och komplexiteten i implementeringen av kodning och avkodning (både hårdvara och datorprogramvara ).

Hamming bundna och perfekta koder

Låt det finnas en binär blockkod med korrigerande förmåga . Då gäller ojämlikheten (kallad Hamming-bunden): $(n,k)$ $t$

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

Koder som uppfyller denna likhetsgräns kallas perfekta. Perfekta koder inkluderar till exempel Hamming-koder . Koder med stor korrigerande kraft som ofta används i praktiken (som Reed-Solomon-koder ) är inte perfekta.

Litteratur

Blahut R. Teori och praktik av felkontrollkoder. — M .: Mir , 1986. — 576 sid.
McWilliams F. J., Sloan N. J. A. Teori om felkorrigerande koder. Moskva: Radio och kommunikation, 1979.
Morelos-Zaragoza R. Konsten att felkorrigera kodning. Metoder, algoritmer, tillämpning / per. från engelska. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 sid. — (Kommunikationens värld). - 2000 exemplar. — ISBN 5-94836-035-0 .