Een binaire goppa-code, doorgaans alleen goppa-code genoemd, is een foutcorrigerende code. De code is genoemd naar de Russische wiskundige Velerii Denisovich Goppa. In McEliece-cryptografie wordt bijvoorbeeld gebruikgemaakt van binaire goppa-codes. Een binaire goppa-code is niet hetzelfde als een algebraïsche goppa-code.
Voorwaardes Er zijn verschillende definities te geven voor een goppa-code. Hier wordt toegewerkt naar een polynomiale definitie. Voordat we dat kunnen doen zijn er enkele parameters nodig. De volgende gegevens zijn gebruikelijk voor een goppa-code: Kies met . De code is gedefinieerd over het lichaam . Noem de rij afzonderlijke elementen uit dat lichaam, lexicografisch geordend. Voor het aantal fouten die gecorrigeerd kunnen worden door de code, kiezen we . Voor is bijvoorbeeld of . Zoek een irreducibele monische polynoom van graad . Laat .
In dit geval geldt dat .
Definitie Een definitie van de goppa-code , is nu
De polynomen , kunnen gezien worden als vectoren over .
Ze vormen een pariteitscontrole-matrix voor de code .
Algoritme van Patterson In 1975 heeft Patterson een algoritme ontwikkeld om in polynomiale tijd fouten te kunnen corrigeren uit de goppa-code.
Voordat het algoritme weergegeven kan worden, is de definitie nodig van de norm van een polynoom.
Norm van een polynoom Voor een polynoom geldt dat de norm , met de graad van .
Bij rationale functies geldt . Bijvoorbeeld .
Algoritme Het doel is om maximaal fouten te verbeteren uit eengoppa-code . We starten met een woord , met maximaal fouten. Dat betekent dat er een coodewoord is zodat er in het codewoord hoogstens maal een 1 met een 0 verwisseld is, of andersom.
Bereken over het lichaam . Als deze som nul is in het lichaam, dan zijn er blijkbaar geen fouten in de code. Het algoritme geeft dan output . Bereken de wortel van over het lichaam . Noem deze berekende wortel en bekijk deze in het lichaam . De graad van is kleiner dan . De vectoren en genereren een rooster . De norm van een vector is per definitie gelijk aan de norm van de polynoom . Zo is de lengte van de vector gelijk aan . Vind met behulp van basisreductie een basis van minimale lengte. Deze zal kleiner of gelijk zijn aan . Bereken Deel door de coëfficiënt van de hoogste macht van x, zodat monisch wordt. Ontbindt in lineaire factoren van de vorm . Dit zullen factoren zijn. Output , is de gecorrigeerd code , met een correctie op de plaatsen , waar .
Voor een uitgebreid voorbeeld van dit algoritme wordt verwezen naar het artikel van Bernstein.
Categorie:Discrete wiskunde Categorie:Algebraïsche getaltheorie