Linjekode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. januar 2021; verifikation kræver 1 redigering .

I matematik og informationsteori er en linjekode en type blokkode, der bruges i fejldetekterings- og korrektionskredsløb. Lineære koder gør det i sammenligning med andre koder muligt at implementere mere effektive algoritmer til kodning og afkodning af information.

Grundlæggende

I processen med lagring af data og transmission af information via kommunikationsnetværk opstår der uundgåeligt fejl. Dataintegritetskontrol og fejlkorrektion er vigtige opgaver på mange niveauer af arbejde med information (især OSI - modellens fysiske , datalink- og transportlag ).

I kommunikationssystemer er flere strategier til håndtering af fejl mulige:

fejldetektion i datablokke og automatisk anmodning om gentransmission af beskadigede blokke - denne tilgang bruges hovedsageligt på datalink- og transportlagene;
fejldetektion i datablokke og kassering af dårlige blokke - denne tilgang bruges nogle gange i streamingmediesystemer, hvor transmissionsforsinkelse er vigtig, og der ikke er tid til gentransmission;
fejlkorrektion ( engelsk forward error correction ) påføres på det fysiske lag.

Fejldetekterings- og korrektionskoder

Korrektionskoder - koder, der bruges til at opdage eller rette fejl, der opstår under transmissionen af information under påvirkning af interferens , såvel som under dens lagring.

For at gøre dette, når de skriver (transmitterer) til de nyttige data, tilføjer de specielt struktureret redundant information, og når de læser (modtager), bruges den til at opdage eller rette fejl. Naturligvis er antallet af fejl, der kan rettes, begrænset og afhænger af den specifikke kode, der anvendes.

Tæt relateret til fejlkorrigerende koder er fejldetektionskoder . I modsætning til førstnævnte kan sidstnævnte kun fastslå tilstedeværelsen af en fejl i de overførte data, men ikke rette den.

Faktisk tilhører de anvendte fejldetekteringskoder 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).

Ifølge metoden til at arbejde med data er fejlkorrigerende koder opdelt i blokkoder , 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

Lad den kodede information opdeles i bitlængdefragmenter, som konverteres til bitlængdekodeord . Så er den tilsvarende blokkode normalt angivet . I dette tilfælde kaldes nummeret kodesatsen . $k$ $n$ $(n,k)$ $R={\frac {k}{n}}$

Hvis koden efterlader de originale bits uændrede og tilføjer checks , kaldes en sådan kode systematisk , ellers ikke-systematisk . $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.

Det er let at se, at disse krav modsiger hinanden. Derfor er der et stort antal koder, som hver især egner sig til dens række af opgaver.

Næsten alle anvendte 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 mellemrum

Generering af matrix

Lad vektorerne være grundlaget for det lineære rum . Ifølge definitionen af basis kan enhver vektor repræsenteres som en lineær kombination af basisvektorer: , eller i matrixform , som: $\overrightarrow {x_{1}}=(x_{{11}},..,x_{{1n}}),\overrightarrow {x_{2}}=(x_{{21}},..,x_{ {2n}}),..,\overrightarrow {x_{k}}=(x_{{k1}},..,x_{{kn}})$ $C$ $\overrightarrow {v}\i C$ $\overrightarrow {v}={c_{1}}\overrightarrow {x_{1}}+{c_{2}}\overrightarrow {x_{2}}+...+{c_{k}}\overrightarrow {x_ {k}}$

$\overrightarrow {v}=({c_{1}},{c_{2}},..,{c_{k}}){\begin{bmatrix}x_{{11}}&x_{{12}}& ..&x_{{1n}}\\x_{{21}}&x_{{22}}&..&x_{{2n}}\\..&..&..&..\\x_{{k1 }}&x_{{k2}}&..&x_{{kn}}\\\end{bmatrix}}=\overrightarrow {c}G$ ,

hvor kaldes det lineære rums generatormatrix . $G={\begin{bmatrix}x_{{11}}&x_{{12}}&..&x_{{1n}}\\x_{{21}}&x_{{22}}&..&x_{{2n }}\\..&..&..&..\\x_{{k1}}&x_{{k2}}&..&x_{{kn}}\\\end{bmatrix}}$

Denne relation etablerer en forbindelse mellem vektorerne af koefficienter og vektorerne . Ved at liste alle vektorer af koefficienter kan du få alle vektorer . Med andre ord genererer matrixen et lineært rum. $\overrightarrow {c}=({c_{1}},{c_{2}},..,{c_{k}})$ $\overrightarrow {v}\i C$ $\overrightarrow {c}=({c_{1}},{c_{2}},..,{c_{k}})$ $\overrightarrow {v}\i C$ $G$

Tjek matrix

En anden måde at definere lineære rum på er at beskrive dem i form af en afkrydsningsmatrix.

Lade være et lineært k-dimensionelt underrum af et n-dimensionelt rum over et begrænset felt og være et ortogonalt komplement til . Så ifølge en af sætningerne i lineær algebra er dimensionen . Derfor er der r basisvektorer i. Lad grundlaget være i . $\mathbb {C}$ $\mathbb {F} _{q}$ ${\mathbb {W}}$ $\mathbb {C}$ ${\mathbb {W}}$ $r=nk$ ${\mathbb {W}}$ $\overrightarrow {h}_{1}=({{h_{1}}_{1}},...,{{h_{1}}_{n}}),\overrightarrow {h}_{2 }=({{h_{2}}_{1}},...,{{h_{2}}_{n}}),...,\overrightarrow {h}_{r}=({ {h_{r}}_{1}},...,{{h_{r}}_{n}})$ ${\mathbb {W}}$

Så opfylder enhver vektor følgende system af lineære ligninger : ${\overrightarrow {v}}\in \mathbb {C}$

${\begin{cases}h_{{11}}x_{1}+h_{{12}}x_{2}+...+h_{{1n}}x_{n}=0\\h_{{21 }}x_{1}+h_{{22}}x_{2}+...+h_{{2n}}x_{n}=0\\...\\h_{{r1}}x_{1 }+h_{{r2}}x_{2}+...+h_{{rn}}x_{n}=0\end{cases}}$

Eller i matrixform : $\overrightarrow {v}H^{T}=0$

hvor er tjekmatricen. $H={\begin{bmatrix}\overrightarrow {h}_{1}\\\overrightarrow {h}_{2}\\...\\\overrightarrow {h}_{r}\\\end{bmatrix }}={\begin{bmatrix}h_{{11}}&h_{{12}}&..&h_{{1n}}\\h_{{21}}&h_{{22}}&..&h_{{ 2n}}\\..&..&..&..\\h_{{r1}}&h_{{r2}}&..&h_{{rn}}\\\end{bmatrix}}$

Det reducerede system af lineære ligninger skal betragtes som et kontrolsystem for alle vektorer i det lineære rum, derfor kaldes matrixen en kontrolmatrix. ${\mathbb {H}}$

Formel definition

En lineær kode med længden n og rang k er et lineært underrum C med dimensionen k af vektorrummet , hvor er et endeligt felt af q elementer. En sådan kode med en parameter q kaldes en q-ær kode (f.eks. hvis q = 5, så er dette en 5-ær kode). Hvis q = 2 eller q = 3, så er koden henholdsvis binær eller ternær . ${\mathbb {F}}_{q}^{n}$ $\mathbb {F} _{q}$

En lineær (blok) kode er en kode, således at sættet af dets kodeord danner et -dimensionelt lineært underrum (lad os kalde det ) i et -dimensionelt lineært rum , isomorft med rummet af -bitvektorer . $k$ $C$ $n$ $k$

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

Lade være et ortogonalt underrum med hensyn til , Og være en matrix, der definerer grundlaget for dette underrum. Så for enhver vektor er det sandt: $C^{\perp}$ $C$ $H$ $\overrightarrow {v}\i C$

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

Egenskaber og vigtige teoremer

Minimum afstand og korrigerende kraft

Hamming-afstanden ( Hamming metric ) mellem to kodeorderantallet af forskellige bits i de tilsvarende positioner, det vil sige antallet af "enheder" i vektoren. $\overrightarrow {v_{1}}$ $\overrightarrow {v_{2}}$ $\overrightarrow {v_{1}}\oplus \overrightarrow {v_{2}}$

Den mindste linjekodeafstand er minimum af alle Hamming-afstande for alle kodeordspar. $d$

Vægten af en vektor er Hamming-afstanden mellem denne vektor og nulvektoren, med andre ord antallet af ikke-nul-komponenter af vektoren. $w$

Sætning 1:

Minimumsafstanden for en linjekode er lig med minimum af Hamming-vægtene af kodeord, der ikke er nul: $d$

$d=\min _{{\overrightarrow {c}\in C,\overrightarrow {c}\not =\overrightarrow {0}}}(w(\overrightarrow {c}))$

Bevis:

Afstanden mellem to vektorer opfylder ligheden , hvor er vektorens Hamming-vægt . Fra det faktum, at forskellen mellem to kodeord i en lineær kode også er et kodeord for en lineær kode, følger sætningen: $d(\overhøjre pil {x},\overhøjre pil {y})$ $d(\overrightarrow {x},\overrightarrow {y})=w(\overrightarrow {x}-\overrightarrow {y})$ $w(\overrightarrow {t})$ $\overrightarrow {t}$ $d=\min _{{\overrightarrow {c}\in C,\overrightarrow {c}\not =\overrightarrow {0}}}w(\overrightarrow {c})$

Den mindste Hamming-afstand er en vigtig egenskab ved en lineær blokkode. Den definerer en anden, ikke mindre vigtig egenskab - korrigerende evne : $d$

$t=\venstre\lgulv {\frac {d-1}{2}}\højre\rgulv$ , her angiver vinkelparenteserne afrunding "ned".

Korrektionskraften bestemmer, hvad der er det maksimale antal fejl i et kodeord, som koden kan garanteres at rette.

Lad os forklare med et eksempel. Antag, at der er to kodeord A og B, Hamming-afstanden mellem dem er lig med 3. Hvis ord A blev transmitteret, og kanalen introducerede en fejl i en bit, kan den rettes, da selv i dette tilfælde er det modtagne ord tættere på kodeord A end B. Men hvis to-bit fejl blev indført af kanalen, kan dekoderen antage, at ord B blev transmitteret.

Antallet af detekterede fejl er antallet af fejl, ved hvilke dekoderen kan detektere en fejlsituation (og f.eks. starte gentransmission af meddelelsen). Dette nummer er

f=d-1

Sætning 2 (uden bevis):

Hvis nogen kolonner i kontrolmatrixen H af en lineær (n, k)-kode er lineært uafhængige, så er den mindste kodeafstand mindst d. Hvis der er d lineært afhængige kolonner, er den mindste kodeafstand nøjagtigt d. $l\leqslant d-1$

Sætning 3 (uden bevis):

Hvis minimumsafstanden for en lineær (n, k) kode er d, så er alle kolonner i kontrolmatrixen H lineært uafhængige, og der er d lineært afhængige kolonner. $l\leqslant d-1$

Hamming-koder

Historisk set burde " Hamming-koder " hedde R. Fisher-koder og blev introduceret i 1942 (Fisher RA Theory of confouding in factor to thr theory). 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

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

, hvor er den accepterede vektor,

\overrightarrow{r}

vil være lig med det positionsnummer, hvor fejlen opstod. Denne egenskab gør afkodning meget let.

Reed-Muller kode

Reed-Muller-koden er en lineær binær blokkode. Med en bestemt konstruktionsmetode kan det være systematisk. Generelt er Reed-Muller-koden ikke cyklisk. Reed-Muller-koderne er givet af følgende parametre: for alle værdier afog, kaldet koderækkefølgen, mindre end: $m$ $r$ $m$

kodeords længde

n=2^{m};

informationsdelens længde

k=1+C_{m}^{1}+\dots +C_{m}^{r};

test del længde

nk=1+C_{m}^{1}+\dots +C_{m}^{mr-1};

minimum kodeafstand

d_{min}=2^{mr}.

Reed-Muller-koden bestemmes ved hjælp af en generatormatrix bestående af basisvektorer, som er bygget efter reglen:

lad være en vektor, hvis alle komponenter er lig med 1;

V_{0}

lad være rækkerne i en matrix, hvis kolonner alle er binære længdesæt

{\displaystyle V_{1},\ V_{2},\dots V_{m))

m.

Reed-Muller-koden af th orden indeholder vektorer og alle komponentprodukter eller et mindre antal af disse vektorer som basis. $r$ ${\displaystyle V_{0},\ V_{1},\dots V_{m))$ $r$

Generel metode til indkodning af linjekoder

En lineær kode af længden n med k informationssymboler er et k-dimensionelt lineært underrum, så hvert kodeord er en lineær kombination af underrummets basisvektorer : $\overrightarrow {g_{1}}=(g_{{11}},..,g_{{1n}}),\overrightarrow {g_{2}}=(g_{{21}},..,g_{ {2n}}),..,\overrightarrow {g_{k}}=(g_{{k1}},..,g_{{kn}})$

$\overrightarrow {c}={m_{1}}\overrightarrow {g_{1}}+{m_{2}}\overrightarrow {g_{2}}+...+{m_{k}}\overrightarrow {g_ {k}}$ .

Eller ved at bruge generatormatrixen:

$\overrightarrow {c}=\overrightarrow {m}G=({m_{1}},{m_{2}},..,{m_{k}}){\begin{bmatrix}g_{{11}} &g_{{12}}&..&g_{{1n}}\\g_{{21}}&g_{{22}}&..&g_{{2n}}\\..&..&..&. .\\g_{{k1}}&g_{{k2}}&..&g_{{kn}}\\\end{bmatrix}}$ , hvor $\overrightarrow {m}=({m_{1}},..,{m_{k}}),{m_{1}},..,{m_{k}}\in {\mathbb {Q}}$

Dette forhold er den kodningsregel, ifølge hvilken informationsordet er afbildet til koden $\overrightarrow {m}=({m_{1}},..,{m_{k}})$ $\overrightarrow {c}=({c_{1}},..,{c_{n}})$

Generel metode til at opdage fejl i lineær kode

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 enorme tabeller for kodeord af relativt lille længde. $\overrightarrow {r_{i}}$ $\overrightarrow {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 fejlkorrektion i lineære koder allerede er meget nemmere end korrektion i 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},...,v_{{n-1}})$ $v(x)=v_{0}+v_{1}x+...+v_{{n-1}}x^{{n-1}}$ $x$ $x^n-1$

I fremtiden, medmindre andet er angivet, vil vi antage, at den cykliske kode er binær , det vil sige ... kan antage værdierne 0 eller 1 . $v_{0},v_{1}$

Generering af polynomium

Det kan vises, at alle kodeord i en bestemt cyklisk kode er multipla af et bestemt genererende 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)\mod g(x)]$

CRC-koder

CRC - koder (cyklisk redundanskontrol - cyklisk redundant kontrol) 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 g(x) en specifik CRC-kode. Eksempler på de mest populære polynomier:

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 binære 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.

Matematisk bruger konstruktionen af BCH-koder og deres afkodning nedbrydningen af det genererende polynomium til faktorer i Galois-feltet . $g(x)$

Reed-Solomon-koder

Reed-Solomon- koder (RS-koder) er faktisk ikke- binære BCH-koder, det vil sige, at elementerne i kodevektoren ikke er bits, men grupper af bit. Reed-Solomon-koder er meget almindelige og arbejder med bytes ( oktetter ).

Fordele og ulemper ved linjekoder

+ På grund af linearitet, for at huske eller opregne alle kodeord, er det nok at lagre en væsentlig mindre del af dem i koderens eller dekoderens hukommelse, nemlig kun de ord, der danner grundlaget for det tilsvarende lineære rum. Dette forenkler i høj grad implementeringen af kodnings- og afkodningsenheder og gør lineære koder meget attraktive set ud fra praktiske applikationer.

- Selvom lineære koder som regel klarer sjældne, men store fejludbrud , er deres effektivitet med hyppige men små fejl (for eksempel i en kanal med AWGN ) mindre høj.

Præstationsvurdering

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 . Følgende ulighed gælder så (kaldet Hamming-grænsen ): $(n,k)$ $t$

\sum _{i=0}^{t}{C_{n}^{i}}\leq 2^{nk}

Koder, der opfylder denne lighedsgrænse, siges at være 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.

Energigevinst

Ved transmission af information over en kommunikationskanal afhænger fejlsandsynligheden af signal-støjforholdet ved demodulatorindgangen, så ved et konstant støjniveau er sendereffekten af afgørende betydning. I satellit- og mobilsystemer såvel som andre former for kommunikation er spørgsmålet om energibesparelser akut. Derudover tillader tekniske begrænsninger i visse kommunikationssystemer (for eksempel telefon) ikke en ubegrænset stigning i signalstyrken.

Da fejlkorrigerende kodning giver mulighed for fejlkorrektion, kan dens anvendelse reducere sendereffekten og forlade informationshastigheden uændret. Energiforstærkningen er defineret som forskellen mellem s/n-forholdene i nærvær og fravær af kodning.

Ansøgning

Linjekoder gælder:

i digitale kommunikationssystemer , herunder: satellit, radiorelæ, mobil, datatransmission over telefonkanaler;
i informationslagringssystemer, herunder magnetiske og optiske;
i netværksprotokoller på forskellige niveauer .

Litteratur

Forklarende ordbog over computersystemer. Ed. V. Illingworth m.fl.: Pr. fra engelsk. - M.: Mashinostroenie , 1990. 560 s.: ill.