Lineær kode

I matematik , mere præcist i kodeteori , er en lineær kode en korrektionskode, der har en bestemt egenskab af linearitet.

Mere præcist er en sådan kode struktureret som et vektorunderrum af et begrænset dimensionelt vektorrum over et endeligt felt . Den endelige vektorrum anvendes ofte F 2 n den sædvanlige udtryk er da, at af binær lineær kode . Det er beskrevet af tre parametre [ n , k , δ]. n beskriver dimensionen af det rum, der indeholder det. Denne mængde kaldes kodelængden . k repræsenterer kodens dimension, der svarer til størrelsen på ordene, når de først er afkodet, og δ beskriver den mindste afstand i Hamming- forstand mellem hvert ord i koden.

Lineære koder repræsenterer størstedelen af de korrigerende koder, der anvendes i industrien. Denne tilgang dækker især koderne, der foreslår en simpel detektion, og der anmodes derefter om en ny transmission. Andre koder gør det muligt at korrigere ændringer ved hjælp af fin redundansstyring.

Påmindelse: F 2 er det unikke legeme med to elementer, og F 2 n er et vektorrum med dimension n . Hvis basen felt er F d , feltet indeholder d elementer, den dedikerede sigt er basen lineær kode d . Teorien om endelige felter forsikrer, at d er en styrke af et primtal, og at der findes et unikt felt, der besidder denne kardinal.

Intuitiv tilgang

Korrektionskode

En lineær kode er et specielt tilfælde af en korrektionskode . Målet er at tillade korrektion af fejl efter transmission af en besked . Denne korrektion er mulig ved at tilføje overflødige oplysninger. Beskeden er indlejret i et større sæt, størrelsesforskellen indeholder redundans. Et simpelt eksempel er gentagelseskoden , meddelelsen sendes for eksempel tre gange, afkodningen sker ved afstemning. Her er det større sæt tredobbelt i forhold til den oprindelige meddelelses.

Lad os huske de grundlæggende elementer i formalisering. Der findes et sæt E bestående af sekvenser med længden k , det vil sige at startende fra rang k , er alle værdierne i sekvensen nul og med værdi i et alfabet. Disse elementer er rummet for de meddelelser, vi ønsker at kommunikere. For at give meddelelsen den ønskede redundans findes der et injektions kort φ af E med værdier i F , rummet for sekvenser af længde n med værdier i et alfabet. Funktionen φ kaldes kodning , φ ( E ) kaldes koden , et element af φ ( E ) ord i koden , n længden af koden og k dimensionen af koden.

For at muliggøre kraften i matematiske værktøjer kan det være klogt at bruge algebraiske strukturer . alfabeterne af E og F er valgt som det samme endelige felt . Elementerne i E (resp. F ) er de endelige sekvenser af længden k (resp. N ), E og F arver naturligvis en struktur af vektorrummet med den endelige dimension og af en kanonisk basis , den af rummet. Endelige sekvenser af værdier I et felt. Kodningsapplikationen vælges lineært .

Rummet F er forsynet med en afstand kaldet Hamming-afstand, der stammer fra en pseudonorm , Hamming-vægten . Hamming-vægten p for et punkt i F svarer til antallet af dets koordinater, der ikke er nul. Hamming-afstanden mellem to elementer af F er vægten i Hamming-følelsen af deres forskel.

Ansøgningsdomæne

Lineære koder svarer til et meget stort flertal af typer korrigerende koder. De bruges til påvisning af ændringer, med som tilknyttet korrektionsmetode en retransmissionsanmodning, den mest almindelige anvendte teknik er derefter kontrolsummen . De bruges i en lang række situationer, fra nogle få isolerede fejl til store ændringer eller sletningsfænomener.

Selvom den anvendte ramme er meget udbredt, opfylder den ikke desto mindre alle behov. Vi kan nævne to hovedemner, der er lidt behandlet af teorien om lineære koder. En god kode opfylder et optimalkriterium, det siges at være perfekt. Rammen for lineær kodeteori tilbyder kriterier til validering af denne optimitet. Det tilbyder dog ikke en metode til at designe denne type kode.

En generel metode til fejlkorrektion er tilgængelig, syndromafkodning . Denne metode består i at oprette en tabel, der knytter sig til hver fejl, dens løsning. Tabellen vokser eksponentielt med antallet af bogstaver, der sandsynligvis er i fejl. I tilfælde af en stor korrektionskapacitet er denne tilgang ikke længere operationel.

Teorien om cykliske koder, der i vid udstrækning benytter egenskaberne for endelige felter, opfylder disse to behov. En cyklisk kode er en lineær kode med en yderligere algebraisk struktur.

Definitioner

Lad p være et primtal , med en styrke på p , n et strengt positivt heltal og k et heltal mindre end n . En lineær kode C for dimension k og længde n er et vektorunderrum af F d n for dimension k . Hvis d er lig med to, siges koden at være binær . Ellers taler vi om en grundlæggende lineær kode d .

Her, F d angiver den unikke område med d elementer (cf artiklen endelige område ). Bemærk, at vektorrum af sekvenser med værdier i F d identificeres med F d n . Vektorrummet F d n er udstyret med Hamming afstand .

Hvad angår de andre korrektionskoder, gælder begrebet parametre . For at tage højde for strukturen på vektorrummet ændres det dog lidt:

De parametre af en kode er betegnet [ n , k , δ] hvor δ betegner den mindste afstand mellem to punkter af koden.

Parameterdefinitionen for lineære koder er derfor ikke kompatibel med den mere generiske, der bruges til korrigerende koder. Af denne grund er parametrene for en lineær kode traditionelt betegnet [ n , k , δ] og parametrene for en generel korrektionskode { n , M , δ}.

Som før er der en kodningsapplikation : φ.

Den kodende kort φ af et lineært kode er en injektiv lineær afbildning fra F d k til F d n .

Den matrix G af φ i de kanoniske baser siges generator matrix af koden C . Den kontrollerer følgende lighed:

{\ displaystyle \ forall x \ in \ mathbb {F} _ {d} ^ {k} \ quad Gx = \ varphi (x) \ in C \ subset \ mathbb {F} _ {d} ^ {n}}

Monitorering for verifikation og eventuelle korrektioner er givet ved en lineær afbildning h af F d n i F d n-k , hvis kerne C . Teorien om lineær algebra viser, at en sådan anvendelse findes, blot for eksempel til at overveje en projektor på en underrum supplerende til C parallelt med C .

Matrixen H for h i kanoniske baser kaldes kontrolmatrixen for C- koden . Det kontrollerer følgende egenskaber:

\ forall x \ in \ mathbb {F} _d ^ {n} \ quad H. ^ tx = 0 \; \ Leftrightarrow \; x \ i C

Udtrykket paritetsmatrix bruges også til at betegne kontrolmatrixen .

Bemærk: Disse notationer bruges i resten af artiklen.

Ejendomme

Alle egenskaber ved lineær algebra gælder for lineære koder. Koden er således både lettere at implementere og afkode. Derudover gør værktøjer til generering af vektorrum såsom dobbeltrummet eller tensorproduktet det muligt at designe nye koder, sommetider mere velegnede til industrielle begrænsninger.

Genererer matrix

Kodningsapplikationen er lineær, den repræsenteres og beregnes derfor takket være dens generatormatrix . En kode er helt defineret af dens generatormatrix, dimension kx n. Desuden afhænger egenskaberne for dens kode kun af geometrien φ ( E ). Hvis f er en isomorfisme af E , er koden defineret af kortet φ af den samme som for φ. Dette giver anledning til følgende definition:

To koder på samme alfabet F d af længden k defineret af to generator matricer G og G 'således at der eksisterer et invertibel kvadratisk matrix P af orden k kontrollere G = G' . P siges at være ækvivalent .

Der er en særlig enkel form til matrixen G :

En lineær kode, hvis generatormatrix i k første rækker har en identitetsmatrix i rækkefølge k , kaldes en systematisk kode .

Artiklen tilknyttet dette afsnit demonstrerer en vigtig egenskab:

Enhver lineær kode svarer til en systematisk kode.

Denne skrivning fremskynder og forenkler kodning og afkodning. Matrixen tager derefter følgende form:

G = {I_k \ vælg C}

Koordinaterne for matricen C svarer til redundans, deres mål er påvisning og korrektion af eventuelle fejl:

De sidste n - k koordinater på et ord af den systematiske kode kaldes kontrol bits eller undertiden checksum .

Kontrolmatrix

I det lineære tilfælde er koden et vektorunderrum af dimension k . Der eksisterer derefter et surjectivt lineært kort over F i et rum med dimension n - k, der for kernen har nøjagtigt koden:

En kontrolmatrix for en kode φ ( E ) er en matrix H med dimension n x n - k således at:

x \ in \ varphi (E) \ Leftrightarrow H. ^ tx = 0

I tilfælde af en systematisk kode giver udtrykket af generatormatricen straks udtrykket for en kontrolmatrix.

I tilfælde af en systematisk kode, hvis G er udtrykket for en generatormatrix, er følgende udtryk det for en kontrolmatrix:

hvis \ quad G = {I_k \ vælg C} \ quad så \ quad H = (-C \; I_ {nk}) \;

Her betegner jeg k identitets kvadratisk matrix for ordre k . Denne matrix giver en relativt enkel måde at beregne minimumafstanden på:

Minimumsafstanden δ for en lineær kode er lig med dimensionen af det mindste vektorunderrum S af F genereret af elementer på det kanoniske grundlag og således, at begrænsningen af kontrolmatrixen til S ikke er injektionsdygtig .

Hamming afstand

I tilfælde af en lineær kode udtrykkes Hamming-afstanden som en afstand, der skyldes en pseudonorm. Den Hamming vægt , som associerer antallet af ikke-nul koordinater med en kode, her spiller rollen som pseudo-normen.

Hvis ω betegner Hamming-vægten for en lineær kode C , defineres Hamming-afstanden d ved hjælp af følgende formel:

\ forall x, y \ i C \ quad d (x, y) = \ omega (xy) \;

Lineariteten af den underliggende struktur introducerer en direkte egenskab:

Den mindste afstand δ mellem to punkter i koden er lig med minimumet af vægten af kodeordene, der ikke er nul.

For at være overbevist om dette er det tilstrækkeligt at bemærke, at hvis x og y er to ord i koden, så er deres forskel også et ord i koden.

Singleton terminal og MDS kode

Det maksimale antal utvivlsomt korrigerbare fejl t følger direkte fra minimumafstanden δ. Faktisk er t det største heltal strengt mindre end δ / 2. Den ideelle situation er en, hvor boldene lukkede center ord af koden og radius t danne en skillevæg af F . Vi taler derefter om perfekt .

Følgende markering er verificeret for alle lineære koder. Det kaldes Singleton terminal :

nk \ ge \ delta-1

Hvis Singleton-grænsen nås, siges koden at være MDS.

Dobbelt kode

Kodens lineære struktur giver naturligvis opfattelsen af dobbelt kode. Den symmetriske bilineær formular kanonisk og sætter den dobbelte kode C .

Den dobbelte kode for en lineær kode C for dimension k er det ortogonale underrum af C i det rum, der er forsynet med sin kanoniske symmetriske bilineære form. Det er en kode af samme længde n og dimension n - k . Det bemærkes ofte . En kode siges at være autodual, hvis den er lig med dens dobbelte. $\ scriptstyle {C ^ {\ perp}}$

I tilfælde af en systematisk kode, hvortil det altid er muligt at komme tilbage, bliver C- kontrolmatricen en generatormatrix af dens dobbelte. Det er så tilstrækkeligt at omarrangere databasen for at få en systematisk kode. Tilsvarende er en generatormatrix af C en dobbelt lydkontrolmatrix.

Det er muligt at beregne den mindste afstand fra , men det er ikke tilstrækkeligt at vide, at af : det er nødvendigt at kende tællerpolynomet af vægten af . MacWilliams ' identitet giver derefter det, hvorfra vi simpelthen trækker den mindste afstand fra sidstnævnte. $\ scriptstyle C ^ {\ bot}$ $VS$ $VS$ $VS$ $\ scriptstyle C ^ {\ bot}$

Produktkode

Den lineære algebra tilbyder mange andre teknikker, der er i overensstemmelse med koden. Den tensor produkt er et eksempel. Med to vektorrum forbinder han en tredje isomorf til de lineære kort over det første rum i det andet.

Hvis C 0 (hhv. C 1 ) er en lineær kode med parameteren [ n 0 , k 0 , d 0 ] (hhv. [ N 1 , k 1 , δ 1 ]), derpå tensor produktet af de to koder er en kode for parameter [ n 0 . n 1 , k 0 . k 1 , δ 0 .δ 1 ]. Denne kode kaldes produktkoden for C 0 og C 1 .

Det bruges til at rette enhver konfiguration med mindre end δ 0 .δ 1/4 fejl.

Fejlhåndtering

Opdagelse

Den enkleste fejlhåndteringsteknik er begrænset til validering. Hvis meddelelsen ikke er en del af koden, erklæres den for forkert. Generelt er en ny transmission anmodning korrigerende teknik.

Den hyppigst anvendte metode består i at tilføje til meddelelsen et eller flere kontrolbits svarende til summen i den endelige del af meddelelsens koefficienter. Denne teknik er analog med bevis af ni .

Selvom det betyder at øge antallet af kontrolbits, kan denne metode øge dens pålidelighedsgrad. Hvis sandsynligheden er høj nok til at antage, at en enkelt fejl kan glide ind i meddelelsen, så opfylder en kontrolbit betingelsen.

I tilfælde af en enkelt kontrolbit er kodeparametrene [ n , n - 1, 2]. En sådan kode kan ikke rette fejlen alene. Faktisk for hver fejl er der n - 1 punkter i koden, der er tæt på. Yderligere oplysninger er nødvendige for selvkorrektion.

Implementeringen er enkel, beregningen af billedet af meddelelsen ved hjælp af kontrolmatrixen giver informationen. Hvis billedet er null, svarer meddelelsen til en kode, og den er uden fejl. Ellers erklæres en fejl.

Rettelse

Spørgsmålet behandles kun her i tilfælde af systematiske koder. Ikke kun er det den løsning, der overvejes af branchen, men derudover svarer enhver anden konfiguration til denne.

Oprindeligt er det kun muligt at overveje problemet med nulvektoren. Den modtagne besked har derfor som k første koordinater 0 og kontrolbits c, som ikke alle er nul. Denne situation svarer til en fejl, fordi billedet af nulvektoren ved generatormatricen giver nulvektoren, og derfor er kontrolbitene alle nul for en kode, der har sine første k nul-koordinater.

Korrektionen svarer til meddelelsen m mindre Hamming vægt og har billedet ved check matrix - H . c . Hvis antallet af ændringer, der genererede vektoren (0, c ) er mindre end (δ - 1) / 2, så der findes en unik m , således at H . m = - H . c . Her H . c betegner ved misbrug vektoren H. (0, c ). Den tilknyttede kode er m - c, og den oprindelige besked er m . Vi verificerer, at H. ( M - c ) = 0 og m - c er en kode. Det er da muligt, for hver værdi af H . c , for at knytte en korrektion m .

Værdien H. (0, c ), hvor H er en systematisk kontrolmatrix og c et sæt ikke-nul kontrolbits kaldes et syndrom .

I det generelle tilfælde, hvis det er en modtaget besked, der ikke er en del af koden, dens billede ved check matrix er en værdi svarende til en H . c givet. Det ser ud til, at m er den mindste korrektion, der gælder for l for at få en kode. Faktisk H ( l + m ) er lig med H . c - H . c og minimumet er en konsekvens af det foregående afsnit.

Bestemmelse af værdien m for H . c afhænger i høj grad af valg af kode. Det svarer til det klassiske problem, der er dækket af lineær optimering . I praksis er det sjældent, at sådanne metoder anvendes. Enten reduceres kontrolbitene i antal, og kombinatorikken reduceres, eller rummet er stort, og koden har andre egenskaber, som ofte er polynomiske og beskrevet i artiklens cykliske kode .

Implementeringen, da pladsen på kontrolbitene er reduceret, udføres generelt af en hash-tabel . Denne tabel etablerer en sammenhæng mellem hvert syndrom og meddelelsen om, at minimumsvægt har syndromet som et billede af kontrolmatrixen.

En implementering af korrektionen ved hjælp af en hash-tabel, der tilvejebringer en sammenhæng mellem syndromer og minimumsvægtmeddelelser kaldes syndromdekodning .

Se også

Bibliografi

(in) Jessie MacWilliams og Neil Sloane , Theory of Error-Correcting Codes, North-Holland , 1977 ( ISBN 978-0-44485009-6 )
A. Spătaru, Fundament for Information Transmission Theory , PPUR , 1987 ( ISBN 978-2-88074133-4 )
Michel Demazure , Algebra forløb: primality, divisibility, codes [ detail of editions ]

eksterne links

CIRC-korrektionskode af JP Zanotti, University of Toulon
Algebra og fejlkorrektion af Dany-Jack Mercier, Antilles-Guyane University
Lineær kode af G. Zemor, University Bordeaux I
Christine Bachoc, ” Code kursus ” , på Bordeaux Jeg universitet , 2004-2005
Korrektionskode af M. Coste, A. Paugam, R. Quarez, University of Rennes