Goppa -kod - Goppa code

I matematik är en algebraisk geometrisk kod ( AG-kod ), annars känd som en Goppa-kod , en allmän typ av linjär kod konstruerad med hjälp av en algebraisk kurva över ett ändligt fält . Sådana koder introducerades av Valerii Denisovich Goppa . I särskilda fall kan de ha intressanta extrema egenskaper . De ska inte förväxlas med binära Goppa -koder som används till exempel i McEliece -kryptosystemet . ${\ displaystyle X}$ ${\ displaystyle \ mathbb {F} _ {q}}$

Konstruktion

Traditionellt är ett AG-kod konstruerad av ett icke-singulär projektiv kurva X över ett finit fält genom användning av ett antal fasta distinkt - rationella punkter på : ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle \ mathbf {X}}$

{\ displaystyle {\ mathcal {P}}: = \ {P_ {1}, \ ldots, P_ {n} \} \ subset \ mathbf {X} (\ mathbb {F} _ {q}).}

Låt vara en divisor på X , med ett stöd som endast består av rationella punkter och som är oskarp från (dvs. ). ${\ displaystyle G}$ ${\ displaystyle P_ {i}}$ ${\ displaystyle {\ mathcal {P}} \ cap \ operatorname {supp} (G) = \ varnothing}$

Enligt satsen Riemann – Roch finns det ett unikt ändligt dimensionellt vektorutrymme, med avseende på delaren . Vektorutrymme är ett underrum av funktionsområdet för X . ${\ displaystyle L (G)}$ ${\ displaystyle G}$

Det finns två huvudtyper av AG-koder som kan konstrueras med hjälp av ovanstående information.

Funktionskod

Funktionskoden (eller dubbelkoden ) med avseende på en kurva X , en divisor och uppsättningen är konstruerad enligt följande. ${\ displaystyle G}$ ${\ displaystyle {\ mathcal {P}}}$

Låt , vara en delare, med den definierade som ovan. Vi brukar beteckna en Goppa -kod med C ( D , G ). Vi vet nu allt vi behöver för att definiera Goppa -koden: ${\ displaystyle D = P_ {1} +\ cdots +P_ {n}}$ ${\ displaystyle P_ {i}}$

{\ displaystyle C (D, G) = \ vänster \ {\ vänster (f (P_ {1}), \ ldots, f (P_ {n}) \ höger) \: \ f \ i L (G) \ höger \} \ delmängd \ mathbb {F} _ {q}^{n}}

För en fast grund för L ( G ) över , den motsvarande Goppa kod i spänns över genom vektor ${\ displaystyle f_ {1}, \ ldots, f_ {k}}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle \ mathbb {F} _ {q}^{n}}$ ${\ displaystyle \ mathbb {F} _ {q}}$

{\ displaystyle \ left (f_ {i} (P_ {1}), \ ldots, f_ {i} (P_ {n}) \ right)}

Därför,

{\ displaystyle {\ begin {bmatrix} f_ {1} (P_ {1}) & \ cdots & f_ {1} (P_ {n}) \\\ vdots && \ vdots \\ f_ {k} (P_ {1} ) & \ cdots & f_ {k} (P_ {n}) \ end {bmatrix}}}

är en generatormatris för ${\ displaystyle C (D, G).}$

På motsvarande sätt definieras det som bilden av

{\ displaystyle {\ begin {cases} \ alpha: L (G) \ to \ mathbb {F} ^{n} \\ f \ mapsto (f (P_ {1}), \ ldots, f (P_ {n} )) \ end {case}}}

Följande visar hur kodens parametrar förhåller sig till klassiska parametrar för linjära system för divisorer D på C (jfr Riemann – Roch -satsen för mer). Notationen ℓ ( D ) betyder dimensionen för L ( D ).

Proposition A. Goppakodens dimension är

{\ displaystyle C (D, G)}

{\ displaystyle k = \ ell (G)-\ ell (GD).}

Bevis. Eftersom vi måste visa det ${\ displaystyle C (D, G) \ cong L (G)/\ ker (\ alpha),}$

{\ displaystyle \ ker (\ alpha) = L (GD).}

Låt då så . Sålunda, Omvänt antar sedan sedan ${\ displaystyle f \ in \ ker (\ alpha)}$ ${\ displaystyle f (P_ {1}) = \ cdots = f (P_ {n}) = 0}$ ${\ displaystyle \ operatorname {div} (f)> D}$ ${\ displaystyle f \ i L (GD).}$ ${\ displaystyle f \ i L (GD),}$ ${\ displaystyle \ operatorname {div} (f)> D}$

{\ displaystyle P_ {i} <G, \ quad i = 1, \ ldots, n.}

( G "fixar" inte problemen med , så f måste göra det istället.) Det följer det ${\ displaystyle -D}$ ${\ displaystyle f (P_ {1}) = \ cdots = f (P_ {n}) = 0.}$

Proposition B. Det minimala avståndet mellan två kodord är

{\ displaystyle d \ geqslant n- \ deg (G).}

Bevis. Antag att Hamming vikt av är d . Det betyder att för index vi har för Then , och ${\ displaystyle \ alpha (f)}$ ${\ displaystyle nd}$ ${\ displaystyle i_ {1}, \ ldots, i_ {nd}}$ ${\ displaystyle f (P_ {i_ {k}}) = 0}$ ${\ displaystyle k \ in \ {1, \ ldots, nd \}.}$ ${\ displaystyle f \ in L (G-P_ {i_ {1}}-\ cdots -P_ {i_ {nd}})}$