Lineær kode

I kodningsteorien, en lineær kode er en speciel blok kode , hvor kodeordene er elementer af en finite-dimensionalt vektorrum over en finit felt . En kode er lineær, hvis og kun hvis den er et underrum af . ${\ displaystyle \ mathbb {F} _ {q} ^ {n}}$ ${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle \ mathbb {F} _ {q} ^ {n}}$

Lineære koder har den fordel, at metoder til lineær algebra kan anvendes. De er derfor lette at kode og afkode. De fleste af de vigtige koder er lineære: Hamming-kode , paritetskontrolkode med lav densitet , Reed-Muller-kode , Hadamard-kode , alle cykliske koder (inklusive BCH , Reed-Solomon-koder , Golay-koder og Goppa Koder ).

Er vektorrumdimensionen for den lineære kode er lig , kaldes den en kode eller en Hamming-afstand på lige kode . ${\ displaystyle C}$${\ displaystyle k}$${\ displaystyle C}$${\ displaystyle [n, k]}$${\ displaystyle d}$${\ displaystyle [n, k, d]}$

egenskaber

Da er et underrum af , er der et grundlag for . Hvis du sammenfatter dette grundlag i en matrix${\ displaystyle C}$${\ displaystyle V}$${\ displaystyle g_ {1}, \ prikker, g_ {k}}$${\ displaystyle C}$

${\ displaystyle G = {\ begin {pmatrix} g_ {1} \\\ vdots \\ g_ {k} \ end {pmatrix}}}$

sammen opnår man en producentmatrix . Koden har også en kontrolmatrix . Det gælder for dem, hvis og kun hvis der er et kodeord. Den rang af sige , der er af . Den Hammingafstand af er det mindste antal af lineært afhængige søjler i kontrolgruppen matrix. ${\ displaystyle H}$${\ displaystyle Hc ^ {T} = 0}$${\ displaystyle c}$${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle H}$${\ displaystyle nk}$${\ displaystyle C}$

Den Hamming vægt af et kodeord er lig med antallet af dem, der er forskellig fra nul. F.eks. Har kodeordet en Hamming-vægt på 4. Hamming-afstanden for koden er lig med den mindste Hamming-vægt af alle kodeord undtagen nul-ordet. ${\ displaystyle c = (c_ {1}, \ prikker, c_ {n})}$${\ displaystyle c_ {i}}$${\ displaystyle (430540)}$${\ displaystyle \ mathbb {F} _ {7} ^ {6}}$

Hvis kodeordens individuelle koordinater er permuteret, opnås en såkaldt ækvivalent kode . Med dette og ved hjælp af lineær algebra kan man finde en ækvivalent for hver lineær kode, som har en generatormatrix af formen . Hvor er den - identitet matrix , og er en - matrix. Derefter kaldes det producentmatrix i reduceret form. De første koordinater kan fortolkes som informationssymboler og de sidste som kontrolsymboler. Er en generatormatrix i reduceret form, kan en kontrolmatrix findes med det samme . En lineær kode er allerede bestemt af dens generatormatrix eller dens kontrolmatrix. ${\ displaystyle G = (\ mathbb {E} _ {k} | P)}$${\ displaystyle \ mathbb {E} _ {k}}$${\ displaystyle (k \ gange k)}$${\ displaystyle P}$${\ displaystyle (k \ times (nk))}$${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle nk}$${\ displaystyle G}$${\ displaystyle H}$${\ displaystyle H = (- P ^ {T} | \ mathbb {E} _ {nk})}$

eksempel

Den binære - Hamming-kode har følgende generatormatrix i reduceret form og den tilhørende kontrolmatrix: ${\ displaystyle [7,4,3]}$

${\ displaystyle G = (\ mathbb {E} _ {k} | P)}$		${\ displaystyle H = (- P ^ {T} | \ mathbb {E} _ {nk})}$
${\ displaystyle G = {\ begin {pmatrix} {\ color {Brown} 1} & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & {\ color {Brown} 1} & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & \ color {Brown} {1} & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & {\ color {Brown} 1} & 0 & 1 & 1 \\\ end {pmatrix}} \ qquad}$		${\ displaystyle H = {\ begin {pmatrix} 1 & 1 & 1 & 0 & {\ color {Brown} 1} & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & {\ color {Brown} 1} & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & {\ color {Brown} 1} \\\ end {pmatrix }}}$

Kodning

Et ord fra rummet kodes ved at danne produktet . Kodningen af ​​ordet med - Hamming-koden illustreret eksempel, følgende udsagn. ${\ displaystyle x = (x_ {1}, \ prikker, x_ {k})}$${\ displaystyle \ mathbb {F} _ {q} ^ {k}}$${\ displaystyle xG}$${\ displaystyle (0,0,1,1)}$${\ displaystyle [7,4,3]}$

${\ displaystyle {\ begin {align} x \ cdot G & = c \\ {\ begin {pmatrix} 0,0,1,1 \ end {pmatrix}} \ cdot {\ begin {pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\\ end {pmatrix}} & = {\ begin {pmatrix} 0,0,1,1,1,0,0 \ end {pmatrix}} \ end {align}}}$

Da tilføjelsen finder sted herinde, gælder følgende${\ displaystyle \ mathbb {F} _ {2}}$${\ displaystyle 1 + 1 = 0}$

Afkodning

Med afkodningen kaldes tilknytning en modtaget, muligvis defekt inputvektor  til en kodevektor  . Afkodningen er ikke den omvendte funktion af kodningen, som tildeler en vektor til en kodevektor . ${\ displaystyle x}$${\ displaystyle c '}$${\ displaystyle \ mathbb {F} _ {q} ^ {k}}$

Som en dekodningsmetode, der er i kodningsteorien, anvendes mest maksimal sandsynlighed (engelsk: maksimum sandsynlighed afkodning ). En modtaget vektor afkodes i kodevektoren , som sandsynligvis er identisk med den kodevektor  , der  faktisk sendes  . Den vektor, som de færreste steder (fejl) skal rettes for, antages ofte at være den mest sandsynlige. I matematiske termer betyder det at kigge efter  kodevektoren med den mindste Hamming-afstand til den modtagne vektor  . Denne sag er også en metode til henholdsvis nærmeste naboer (engelsk: nærmeste nabo-afkodning ). Ved at kende typen af ​​data, der sendes, eller den kanal, der anvendes, kan anden information bruges til at bestemme sandsynligheden for visse kodevektorer. ${\ displaystyle x}$${\ displaystyle c '}$${\ displaystyle c}$${\ displaystyle c '}$${\ displaystyle x}$

Lad det være den (kode) vektor, der faktisk er sendt og den modtagne vektor. Afkodningen ser efter den kodevektor eller de vektorer, der sandsynligvis blev sendt fra alle kodevektorer . ${\ displaystyle c}$${\ displaystyle x}$${\ displaystyle q ^ {n}}$${\ displaystyle c '}$

${\ displaystyle c '= \ operatorname {argmax} _ {y \ i C} \ left \ {\ operatorname {P} \ left [y = c \ right] \ right \}}$

Med den nærmeste nabo afkodning :

${\ displaystyle c '= \ operatorname {argmin} _ {y \ i C} \ venstre \ {wt (xy) \ højre \}}$

Det skal bemærkes, at denne tildeling ikke er unik for de fleste koder for alle fejlvektorer. Der er så nogle fejlvektorer, der ikke kan tildeles, fordi de har mere end en nærmeste nabo. Hvis en unik afkodning er mulig for hver fejlvektor, kaldes koden perfekt .

Afkodning af syndrom

En mere effektiv fremgangsmåde til dekodning er såkaldt syndrom dekodning . Den syndromet en vektor opnås ved at multiplicere kontrol matrix  med . ${\ displaystyle s_ {x}}$${\ displaystyle x}$${\ displaystyle H}$${\ displaystyle x ^ {T}}$

${\ displaystyle s_ {x} ^ {T} = Hx ^ {T}}$

Lad det være fejlvektoren for . I er netop disse koordinater ikke lig med nul, for hvilke der opstod fejl under overførslen. ${\ displaystyle e = xc}$${\ displaystyle x}$${\ displaystyle e}$

På grund af kodens linearitet gælder følgende for syndromet : ${\ displaystyle x}$

${\ displaystyle s_ {x} ^ {T} = Hx ^ {T} = Hc ^ {T} + He ^ {T}}$

Da syndromet med fejlfri kodevektorer altid er nul, følger det:

${\ displaystyle s_ {x} ^ {T} = Han ^ {T} = s_ {e} ^ {T}}$

Alle (forkerte) ord med den samme fejlvektor er i det samme affine underrum , dvs. syndromet er konstant for sådanne ord . ${\ displaystyle s_ {e} ^ {T} = Han ^ {T}}$

Alle vektorer, der er dukket fra fastlåste vektor ved at subtrahere enhver kodevektor danne et datterselskab klasse af den undergruppe af . Vektoren med den mindste vægt i denne klasse kaldes leder af den sekundære klasse (engelsk: coset leader ). Dette er grunden til, at udtrykket "coset leader decoding" også er udbredt. ${\ displaystyle C}$${\ displaystyle \ mathbb {F} _ {q} ^ {n}}$

For at afkode ser man efter fejlvektoren,  hvis syndrom er identisk med syndromet, og hvis Hamming-vægt er minimal. Denne fejlvektor bruges til at beregne den nærmeste  kodevektor . Så du kan oprette en tabel med op til rækker, der indeholder den tilsvarende fejlvektor med minimal Hamming-vægt for hvert syndrom i en modtaget vektor. Hvis syndromet er lig med 0, behøver intet at blive korrigeret, ellers er afkodning begrænset til at slå fejlvektoren i denne tabel op og rette de opdagede fejl på denne måde. ${\ displaystyle x}$${\ displaystyle c '}$${\ displaystyle e '}$${\ displaystyle x}$${\ displaystyle c '= x-e'}$${\ displaystyle c '}$${\ displaystyle q ^ {nk}}$

Fortolket forskelligt er de sekundære klasser nøjagtigt ækvivalensklasser i ækvivalensrelationen.Lederne er repræsentanter for ækvivalensklasser; man vælger en med en minimal Hamming-vægt. Perfekte koder er kendetegnet ved, at lederne er tydeligt etablerede. ${\ displaystyle x \ equiv y \ Leftrightarrow s_ {x} ^ {T} = s_ {y} ^ {T}}$

Afkodningen af ​​lineære koder er generelt NP-komplet , dvs. der kendes ingen algoritmer med en polynomisk kørselstid. De kendte lineære koder, for eksempel Hamming-koder, skelnes ved, at effektive afkodningsalgoritmer er kendt for dem. Kompleksiteten ved lineær afkodning er grundlaget for McEliece-kryptosystemet , der betragtes som sikkert, men hidtil sjældent er blevet brugt på grund af dets forholdsvis lange nøgler.

eksempel

Vil du afkode Hamming-kode (ovenfra), kommer vi ud fra den antagelse, at kun - Bit- fejl opstår. De mulige fejlvektorer er derefter ${\ displaystyle [7,4,3]}$${\ displaystyle 1}$${\ displaystyle e}$

${\ displaystyle (1,0,0,0,0,0,0)}$

${\ displaystyle (0,1,0,0,0,0,0)}$

${\ displaystyle (0,0,1,0,0,0,0)}$

${\ displaystyle (0,0,0,1,0,0,0)}$

${\ displaystyle (0,0,0,0,1,0,0)}$

${\ displaystyle (0,0,0,0,0,1,0)}$

${\ displaystyle (0,0,0,0,0,0,1)}$

Syndromet beregnes nu for hver af disse fejlvektorer . Dette resulterer i ${\ displaystyle s ^ {T} = Han ^ {T}}$

${\ displaystyle e}$	${\ displaystyle s}$
${\ displaystyle (1,0,0,0,0,0,0)}$	${\ displaystyle (1,1,0)}$
${\ displaystyle (0,1,0,0,0,0,0)}$	${\ displaystyle (1,0,1)}$
${\ displaystyle (0,0,1,0,0,0,0)}$	${\ displaystyle (1,1,1)}$
${\ displaystyle (0,0,0,1,0,0,0)}$	${\ displaystyle (0,1,1)}$
${\ displaystyle (0,0,0,0,1,0,0)}$	${\ displaystyle (1,0,0)}$
${\ displaystyle (0,0,0,0,0,1,0)}$	${\ displaystyle (0,1,0)}$
${\ displaystyle (0,0,0,0,0,0,1)}$	${\ displaystyle (0,0,1)}$

Hvis det forkerte ord derefter modtages, så resultater . Dette resulterer i fejlvektoren og dekodes således . Ordet med almindelig tekst er så . ${\ displaystyle x = (0,1,1,1,1,0,0)}$${\ displaystyle s ^ {T} = Hx ^ {T} = (1,0,1) ^ {T}}$${\ displaystyle e = e ((1,0,1)) = (0,1,0,0,0,0,0)}$${\ displaystyle x}$${\ displaystyle c (x) = (0,1,1,1,1,0,0) - (0,1,0,0,0,0,0) = (0,0,1,1,1 , 0,0)}$${\ displaystyle (0,0,1,1)}$

Eksempel med ufuldstændig afkodning

Den ternære ( ) gentagelseskode af længde 3 er givet: ${\ displaystyle q = 3}$

${\ displaystyle G = {\ begin {pmatrix} 1 & 1 & 1 \ end {pmatrix}} \ qquad}$

${\ displaystyle H = {\ begin {pmatrix} 2 & 1 & 0 \\ 2 & 0 & 1 \\\ slut {pmatrix}}}$

Hver to kolonner er lineært uafhængige, mens alle tre er lineært afhængige. Kodens mindste Hamming-afstand beregnes som det mindste antal lineært afhængige søjler i 3. Dette betyder, at højst en tegnfejl kan rettes. Syndromtabellen ser sådan ud: ${\ displaystyle H}$${\ displaystyle H}$

${\ displaystyle e}$	${\ displaystyle s}$
${\ displaystyle (1,0,0)}$	${\ displaystyle (2.2)}$
${\ displaystyle (2,0,0)}$	${\ displaystyle (1,1)}$
${\ displaystyle (0,1,0)}$	${\ displaystyle (1,0)}$
${\ displaystyle (0,2,0)}$	${\ displaystyle (2.0)}$
${\ displaystyle (0,0,1)}$	${\ displaystyle (0,1)}$
${\ displaystyle (0,0,2)}$	${\ displaystyle (0.2)}$

Ved at bruge lineariteter kunne antallet af rækker halveres, men så skal du teste, om der er et lineært afhængigt syndrom i tabellen.

Overvej nu , . Når syndromet er , korrektionen er: . Beregningen af syndromet af resultater: . Denne værdi er ikke i syndrometabellen, så ordet kan ikke rettes. ${\ displaystyle x = (1,1,0)}$${\ displaystyle y = (1,2,0)}$${\ displaystyle x}$${\ displaystyle Hx ^ {t} = (0.2) ^ {t}}$${\ displaystyle (1,1,0) - (0,0,2) = (1,1,1)}$${\ displaystyle y}$${\ displaystyle Hy ^ {t} = (1,2) ^ {t}}$

Ansøgning

Kodningen og afkodningen, som beskrevet ovenfor, er relativt kompleks. Under kodningen skal generatormatrixen opbevares i hukommelsen, hvilket er problematisk i systemer med begrænsede ressourcer (f.eks. Mobile enheder eller rumsonder). Der kræves en stor tabel til afkodning afhængigt af korrektionshastigheden; hukommelsesforbruget er tilsvarende stort. Af denne grund bruges yderligere egenskaber for koden for at kode og afkode dem effektivt. Binære cykliske koder kan implementeres meget let ved hjælp af skiftregistre og eksklusive-eller porte , for eksempel .

Dobbelt kode

For hver (lineær) kode er der en dobbelt kode (eller også dobbelt kode) , som i sig selv er en lineær kode. Kodeordene i den dobbelte kode er alle ord, der er dobbelte med kodeordene : ${\ displaystyle C}$${\ displaystyle C ^ {\ perp}}$${\ displaystyle \ mathbb {F} _ {q} ^ {n}}$${\ displaystyle C}$

Et indre produkt defineres for dette:

${\ displaystyle \ langle \ cdot; \ cdot \ rangle \ ,: \; \ mathbb {F} _ {q} ^ {n} \ times \ mathbb {F} _ {q} ^ {n} \ to \ mathbb { F} _ {q}}$

som kortlægger vektorerne som følger: ${\ displaystyle x = (x_ {1}, x_ {2}, \ prikker, x_ {n}), y = (y_ {1}, y_ {2}, \ prikker, y_ {n})}$

${\ displaystyle \ langle x; y \ rangle = \ sum _ {i = 1} ^ {n} x_ {i} y_ {i}}$

På trods af den samme definition er dette ikke et skalarprodukt, fordi denne bilineære form ikke er positiv . På grund af egenskaberne ved begrænsede felter er der for det meste vektorer, der ikke er lig nulvektoren, og for hvilke det indre produkt er 0. Tænk for eksempel på den binære vektor . ${\ displaystyle (1,1)}$

Ved hjælp af denne definition resulterer den dobbelte kode som:

${\ displaystyle C ^ {\ perp} = \ {x \ in \ mathbb {F} _ {q} ^ {n} \ mid \ langle x, c \ rangle = 0 \; \ mathrm {f {\ ddot {u }} r \; alle} \; c \ i C \}}$

En generatormatrix af den dobbelte kode er en kontrolmatrix for kildekoden og omvendt.

Den dobbelte kode spiller en vigtig rolle i analysen af ​​kodernes egenskaber.

De såkaldte selv-dobbelte koder er et specielt tilfælde. Dette er koder, der er identiske med deres dobbelte kode. Af dimensionelle grunde har disse altid dimensionen . Det vigtigste eksempel på en selv-dobbelt kode er den udvidede Hamming-kode, hvor den binære [7,4,3] Hamming-kode udvides med en paritetsbit til lige paritet: ${\ displaystyle k = n / 2}$

$"$

litteratur

• Werner Lütkebohmert : Kodningsteori. Algebraisk-geometriske grundlæggende og algoritmer. Vieweg Verlag, Braunschweig et al. 2003, ISBN 3-528-03197-2 ( Vieweg-kursus - avanceret kursus i matematik ).
• JH van Lint : Introduktion til kodningsteori. 3. revideret og udvidet udgave. Springer Verlag, Heidelberg et al. 1999, ISBN 3-540-64133-5 ( Graduerede tekster i matematik 86).
• Florence J. MacWilliams , Neil J. Sloane : Theory of Error-Correcting Codes. 2. Udskrivning. Nord-Holland forlag, Amsterdam 1978, ISBN 0-444-85009-0 ( Nordholland matematisk bibliotek 16).

Individuelle beviser

1. ^ ER Berlekamp, ​​RJ McEliece, HCA von Tilburg: Om den iboende ulastelighed af visse kodningsproblemer . I: IEEE-transaktioner om informationsteori 24 . 1978.