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.
Læringsmål
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 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 algebraiske fejlrettende
koder.
Kursusindhold
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.
Litteraturhenvisninger
Lærebog udarbejdet af forelæserne (elektronisk, gratis tilgængelig)
Bemærkninger
Se også Algebra-forskningsgruppens hjemmeside:
http://algebra.compute.dtu.dkSidst opdateret
02. maj, 2024