5-05 Scan Man

Så er Charlie tilbage på banen! Jeg så flere matematikholdige emner, men det var ikke oplagt for mig, hvad de blev brugt til. Fejlkorrigerende koder blev omtalt i starten. Geografiske netværk, “Supply Chain analysis” (for at finde noget fælles for de steder, der blev begået røverier imod.) Stregkoder og gendannelse af dem, hvis de er beskadiget (“Data recovery software”). Fraktal analyse (af lejligheden, hvor “the scan man” boede). I får noget om fejlkorrigerende koder – og lige en bemækning om “the scan man”. Det var vel tydeligt for enhver, at man havde lånt fra Dustin Hoffmans RainMan i filmen af samme navn. Jeg synes nu ikke, det, som Charlie antydede, vrimler med den slags folk i matematikmiljøerne, altså folk med “savant” egenskaber – at kunne tælle papirclips (eller tændstikker som i Rainman) er ikke nogen decideret fordel for en matematiker. Men andre karakteristika fra autismespektret findes i mere eller mindre udtalt grad. Og Asperger syndrom påstår man jo, at Einstein og Bill Gates (og en hel del skuespillere og komponister i øvrigt) har eller havde. Jo, det er dejligt at være i et rummeligt miljø!

Fejlkorrigerende koder
Jeg låner her fra min kollega Olav Geils glimrende noter – se flere eksempler på Olavs “populariseringshjemmeside”

Hvis man vil sende en besked og risikerer, der sker fejl undervejs, vil man gerne kunne finde den oprindelige besked igen.
Hvis det drejer sig om sædvanlig tekst, er vi allesammen gode til at gennemskue, at L3sb3th nok skal oversættes tilbage til Lisbeth. Vi ved, hvilke ord der er mulige/tilladt, og når vi ser et, der ikke er, leder vi efter noget, der ligner. Men hvad nu, hvis det er et signal – noget lyd eller måske en sum penge. Så giver alle beløb mening, men måske er 123 blevet til 193 undervejs.
I kodningsteori tilføjer man noget information, som gør, at der “bliver længere mellem” de mulige/tilladte strenge af tal, bogstaver eller hvordan man nu transmitterer.

Eksempel: Vi vil sende 123. Vi dobler beskeden op – sender det samme to gange: 123123. hvis modtageren ser 193123, ved de, der er noget galt med andet ciffer, men ikke, hvilket der er rigtigt – de kan ikke korrigere. Man må være lidt smartere.
her kommer et eksempel fra Olavs noter:
Binære Hammingkoder:
Vi vil sende beskeden (0,1,1,0) og koder den ved at tilføje tre binære tal e,f,g – vi vil sende (0,1,1,0,e,f,g). En besked, (a,b,c,d,e,f,g) skal opfylde, at a+b+c+e er lige, a+b+d+f er lige, og a+c+d+g er lige (giver 0 til rest ved division med 2…)
Vi skal have 0+1+1+e lige, så e=0.
0+1+0+f lige, så f=1
0+1+0+g lige, så g=1.
Vi sender altså (0,1,1,0,0,1,1)

Hvad hjælper det nu?
Lad os sige, du modtager (0,1,1,1,0,1,1). Det er klart, at der er noget galt, for a+b+d+f=3 – ulige og a+c+d+g=3, ulige (men a+b+c+e=2, lige). Hvad er der nu galt? Man går nu ud fra, at der kun er sket en enkelt fejl. Ved at skifte d fra 1 til 0 passer checksummerne og vi har en lovlig besked – et lovligt kodeord.

Denne kode er lineær: Tager man to lovlige kodeord, (a,b,c,d,e,f,g) og (A,B,C,D,E,F,G) og danner ordet (a+A,b+B,c+C,d+D,e+E,f+F,g+G), får man et nyt lovligt kodeord. Afstanden mellem to ord er antallet af pladser, hvor de er forskellige: Afstanden mellem de to lovlige ord (0,0,0,0,0,0,0) og (0,1,1,0,0,1,1) ovenfor er 4. Man kan vise, at afstanden mellem to lovlige ord er mindst 3. Denne minimumsafstand siger, hvor mange fejl, koden kan håndtere, i.e., korrigere ordet tilbage til det rigtige. Med en minimumsafstand på d, kan man korrigere (d-1)/2 fejl (rundet nedad, hvis d er lige). Her altså 1 fejl.
En god kode tilføjer få bogstaver og har stor minimumsafstand, og det er natuligvis en kunst at lave sådanne koder. Læs mere i Olavs noter. Følg linket ovenfor og se “kort foredrag, pdf-fil” eller “langt foredrag, pdf-fil”. Noget af matematikken i det er, at man i stedet for at se på rester ved division med 2 (lige/ulige), ser på rester ved division med andre tal. Den slags regning, modulo et helt tal, kender nogen maaske fra kryptering, men kodningsteori er en lige så aktiv og anvendt branche.