Fejlkorrigerende koder forklaret

Ingen kanal er perfekt. Kosmisk stråling vender bit i hukommelsen, ridser sletter dele af en disk, og radiosignaler fader ud. I stedet for at håbe på det bedste tilføjer digitale systemer redundans på en snedig måde, så modtageren kan regne ud, hvad der blev sendt, selv når noget af det kommer forkert frem. Matematikken bag disse koder, som begyndte i slutningen af 1940'erne, beskytter i det stille næsten hver eneste bit, vi lagrer eller sender.

Tre overlappende cirkler med de syv bit i et Hamming-kodeord, hvor én cirkel er fremhævet, fordi en paritetskontrol fejler
Tre overlappende cirkler med de syv bit i et Hamming-kodeord, hvor én cirkel er fremhævet, fordi en paritetskontrol fejler

At opdage fejl med paritet

Den enkleste beskyttelse er en enkelt paritetsbit: tilføj et 1-tal eller et 0, så det samlede antal 1-taller er lige. Hvis én bit vendes undervejs, bliver antallet ulige, og modtageren ved, at noget gik galt. Paritet kan ikke sige, hvilken bit der er forkert, og to vendte bit ophæver hinanden ubemærket, men det er billigt, og det blev brugt i årtier i hukommelse og serielle forbindelser. At opdage en fejl er dog kun det halve arbejde: bagefter skal dataene sendes igen.

At rette ved gentagelse

For at rette en fejl uden at spørge igen har modtageren brug for nok redundans til at stemme den ned. Sendes hver bit tre gange, 000 eller 111, kan modtageren tage flertallet: én vendt bit i en tripel bliver rettet. Prisen er høj: tre bit for hver databit, og to vendte bit i samme tripel vinder stadig. Spørgsmålet, der satte gang i kodningsteorien, var, om man kunne gøre det bedre.

Hammings kode

I 1947 arbejdede Richard Hamming hos Bell Labs på en relæcomputer, der læste programmer fra hulkort. Når den fandt en fejl i weekenden, stoppede den bare, og om mandagen kom Hamming tilbage til spildte kørsler. Hvis en maskine kan opdage en fejl, spurgte han, hvorfor kan den så ikke finde og rette den? Hans svar, offentliggjort i 1950, sender 4 databit som 7. Tre paritetsbit, på position 1, 2 og 4, kontrollerer hver sin overlappende gruppe af positioner, valgt sådan at hver enkelt fejl bryder en unik kombination af kontroller.

Syndromet

Modtageren genberegner de tre kontroller. Hvis alle stemmer, accepteres ordet. Hvis nogle fejler, giver de fejlende kontroller, skrevet som binære cifre med kontrol 4 som det højeste ciffer, et tal fra 1 til 7: syndromet, som er præcis positionen af den vendte bit. Vendes den tilbage, er kodeordet genskabt. Tricket virker, fordi positionerne er nummereret, så hver positions binære skrivemåde angiver de kontroller, den hører til, og derfor ser koden så pæn ud, når den tegnes som tre overlappende cirkler.

Hamming-afstand

Hamming-afstanden mellem to ord er antallet af positioner, hvor de er forskellige. I (7,4)-koden ligger to kodeord altid mindst 3 fra hinanden. Et ord med én fejl ligger stadig i afstand 1 fra det kodeord, der blev sendt, og mindst 2 fra alle andre, så dekodning til det nærmeste kodeord retter fejlen. Generelt opdager en kode, hvis kodeord ligger mindst d fra hinanden, d − 1 fejl og retter (d − 1)/2 af dem, rundet ned. En samlet paritetsbit over hele ordet hæver afstanden til 4 og giver den udvidede kode, der retter én fejl og opdager to.

Shannons grænse

I 1948, to år før Hammings artikel, beviste Claude Shannon en forbløffende sætning. Hver støjfyldt kanal har en kapacitet, og data kan sendes med en hvilken som helst rate under den med så få fejl, som man ønsker, ved at bruge lange nok koder; over den kan fejl ikke undgås. Shannon viste, at sådanne koder findes, men ikke, hvordan man bygger dem. Det tog et halvt århundrede at finde praktiske koder, der kommer tæt på hans grænse, fra Reed-Solomon-koder i 1960 til turbokoder i 1993 og genopdagelsen af LDPC-koder (low-density parity-check).

Claude Shannon, der i 1948 hos Bell Labs gjorde det præcist, hvor megen information en meddelelse indeholder, og målte den i bits.
Claude Shannon, der i 1948 hos Bell Labs gjorde det præcist, hvor megen information en meddelelse indeholder, og målte den i bits.

Koder overalt omkring os

Reed-Solomon-koder får cd'er til at spille trods ridser og QR-koder til at kunne scannes, selv om op til 30 % af symbolet er beskadiget. Serverhukommelse bruger udvidede Hamming-koder til at rette enkelte bit, der er vendt af kosmisk stråling. Voyagers billeder af de ydre planeter blev beskyttet af Golay- og senere Reed-Solomon-koder, og LDPC- og polarkoderne i 5G og wi-fi presser næsten hver eneste bit ud, som kanalen tillader. Selv stregkoden på en bog og det sidste ciffer i et bankkontonummer er simple fejlopdagende koder.

Udforsk det

Åbn simulatoren til fejlkorrigerende koder for at kode fire valgfrie databit med Hamming (7,4)-koden, vende bit ved at klikke på dem i cirklerne eller i rækken og se de fejlende cirkler og syndromet pege på fejlen, før dekoderen reparerer den. Slå den ekstra paritetsbit til for at se dobbeltfejl blive opdaget, og send en besked gennem en støjfyldt kanal for at sammenligne, hvad der kommer frem med og uden koden.

Ofte stillede spørgsmål

Hvad er forskellen på fejldetektion og fejlkorrektion?

Detektion fortæller kun modtageren, at noget er galt, så den må bede om dataene igen; det gør en paritetsbit eller en kontrolsum. Korrektion lader modtageren genskabe originalen uden at spørge, hvilket kræver mere redundans. Systemer, der ikke kan spørge igen, som en rumsonde millioner af kilometer væk eller en dvd, er afhængige af korrektion.

Hvorfor ikke bare sende alt to gange?

To kopier viser, at der er sket en fejl, men ikke hvilken kopi der er rigtig, og de fordobler omkostningen. Tre kopier giver mulighed for flertalsafstemning, men tredobler den. Hammings kode retter en enkelt fejl pr. blok på syv med mindre end det dobbelte antal bit, og længere koder gør det langt bedre.

Hvem var Richard Hamming?

En amerikansk matematiker, 1915–1998, der arbejdede på Manhattan-projektet og derefter i tredive år hos Bell Labs. Ud over sine koder er han kendt for Hamming-vinduet i signalbehandling, for Hamming-afstanden og for sit foredrag »You and Your Research«. Han modtog Turingprisen i 1968.

Kan en kode rette et vilkårligt antal fejl?

Kun med nok redundans. En kode kan rette op til (d − 1)/2 fejl pr. blok, hvor d er minimumsafstanden mellem kodeord, og længere koder med flere kontrolbit når et større d. Shannons sætning sætter den endelige grænse: ingen kode kan slå kanalens kapacitet.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Åbn simulatoren til fejlkorrigerende koder