Enkeltfag Engelsk 5 ECTS

Algebraiske Fejlrettende Koder

Overordnede kursusmål

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 på en BluRay der stadig kan spille selvom den har en ridse, 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.

See course description in English

Forklare den matematiske model i fejlrettende koder og dens relevans i kommunikation.
Udlede, med en konstruktiv metode, at der eksisterer koder med gode parameter.
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ézout’s sætning om skæringspunkter af algebraiske kurver, og 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 evaluer deres effektivitet.
Arbejde effektivt i en gruppe på et projekt med en matematisk og algoritmisk kerne.
Skrive en rapport om et emne i diskret matematik og algebra.

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.

01018, Forståelse af grundbegreber fra algebra: lineær algebra, endelige legemer, kvotientringe, isomorfisætningen, polynomiumsringe. Lidt erfaring med programmering.

Kurset består af forelæsninger, grupperegninger og projektarbejde i grupper.