Dette er et matematik-kursus der udspringer fra ingeniør-anvendelsen Fejlrettende Koder. De faglige værktøjer vi beskæftiger os med er diskret matematik, algebra og algebra.

Fejlrettende Koder handler ikke om programmering men derimod om repræsentation af digital information således at det bliver robust overfor fejl. Disse bliver brugt overalt: fx datalagring på din computer, eller sattelit-tv der stadig fungerer i stormvejr på trods af atmosfærisk støj, eller højhastigheds internet og mobiltelefoni. Det er ikke overdrevet at sige, at informationsalderen var umulig uden Fejlrettende Koder.

Mange af de bedste fejlrettende koder vi kender udspringer fra dybsindig algebra. Dette kursus er en introduktion til den fundamentale matematiske model i kodningsteori og til matematikken bag disse algebraiske koder. For at modtageren kan rette fejl der måtte opstå har han brug for effektive algoritmer til at jonglere med de algebraiske objekter; vi vil beskæftige os med både teoretisk algebra og med et computer-algebra system.

Kort sagt: vi vil bruge algebra og udvikle algebraiske værktøjer til at finde gode løsninger på matematiske problemstillinger, der er inspireret af anvendelser af Fejlrettende Koder. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• Forklare den matematiske model i fejlrettende koder og dens relevans i kommunikation.
• Udlede, med en konstruktiv metode, at der eksisterer koder med gode parametre.
• Give en (eksponentialtids) algoritme til maximum likelihood afkodning.
• Definere Reed-Solomon koder ved hjælp af polynomier i én variabel og udlede deres grundlæggende parametre.
• Bevise matematisk korrektheden af en afkodningsalgoritme for Reed-Solomon-koder, og forstå hvordan man implementerer denne i et computer-algebra system.
• Definere hvorledes en transmission kan fejle og estimere sandsynligheden for disse hændelser i en simpel fejl-model.
• Definere Reed-Muller koder ved hjælp af polynomier i flere variable og udlede deres grundlæggende parametre.
• Bevise Bézouts sætning om skæringspunkter af algebraiske kurver, samt forklare dens rolle i Algebraisk Geometri-koder.
• Definere Algebraiske Geometri-koder ved hjælp af algebraiske kurver, udlede deres grundlæggende parametre, og beskrive en afkodningsalgoritme for dem.
• Udføre et projekt om algebraiske koder og evaluere deres effektivitet.
• Definere lokalt gendannende koder og relatere dem til anvendelser i cloud lagring.
• Skrive en rapport om et emne i algebraiske fejlrettende koder.

Kurset forløber med forelæsninger og grupperegninger. Vi lægger ud med at introducere den matematiske model indenfor lineær algebra over endelige legemer, og vi undersøger de overordnede rammer indenfor den: Gilbert-Varshamov grænsen og eksponentialtids-afkodning. Dernæst introduceres væsentlige algebraiske koder, Reed-Solomon-koder, hvor univariate polynomier benyttes som algebraisk værktøj. Vi ser på en effektiv afkodningsalgoritme til disse koder, samt hvordan den kan implementeres i et computer-algebra-system. Dernæst generaliserer vi til Reed-Muller-koderne vha. multivariate polynomier. Dette motiverer brugen af algebraiske kurver som fører til Algebraiske-Geometri koder, hvor Bézouts sætning er et væsentligt værktøj til analyse. Til sidst vil vi studere en ny anvendelse af algebraiske koder i cloud lagring. Lærebogen er elektronisk og gratis tilgængelig. Se også Algebra-forskningsgruppens hjemmeside: http:/​/​algebra.compute.dtu.dk 19. maj, 2025