Felrättande koder förklarade
Ingen kanal är perfekt. Kosmisk strålning vänder bitar i minnet, repor raderar delar av en skiva och radiosignaler bleknar. I stället för att hoppas på det bästa lägger digitala system till redundans på ett klurigt sätt, så att mottagaren kan räkna ut vad som skickades även när en del av det kommer fram fel. Matematiken bakom dessa koder, som började i slutet av 1940-talet, skyddar i det tysta nästan varje bit vi lagrar eller skickar.
Upptäcka fel med paritet
Det enklaste skyddet är en enda paritetsbit: lägg till en etta eller en nolla så att det totala antalet ettor blir jämnt. Om en bit vänds på vägen blir antalet udda, och mottagaren vet att något gick fel. Paritet kan inte säga vilken bit som är fel, och två vända bitar tar ut varandra obemärkt, men den är billig och användes i årtionden i minnen och seriella länkar. Att upptäcka ett fel är dock bara halva jobbet: sedan måste data skickas igen.
Rätta genom upprepning
För att rätta ett fel utan att fråga igen behöver mottagaren tillräckligt med redundans för att rösta ner det. Om varje bit skickas tre gånger, 000 eller 111, kan mottagaren gå på majoriteten: en vänd bit i en trippel rättas. Priset är högt: tre bitar för varje databit, och två vända bitar i samma trippel vinner ändå. Frågan som startade kodningsteorin var om det gick att göra bättre.
Hammings kod
År 1947 arbetade Richard Hamming vid Bell Labs med en relädator som läste program från hålkort. När den hittade ett fel under helgen stannade den helt enkelt, och Hamming kom tillbaka på måndagen till bortkastade körningar. Om en maskin kan upptäcka ett fel, frågade han sig, varför kan den då inte hitta och rätta det? Hans svar, publicerat 1950, skickar 4 databitar som 7. Tre paritetsbitar, på positionerna 1, 2 och 4, kontrollerar var sin överlappande grupp av positioner, valda så att varje enskilt fel bryter en unik kombination av kontroller.
Syndromet
Mottagaren räknar om de tre kontrollerna. Om alla stämmer godtas ordet. Om några misslyckas ger de misslyckade kontrollerna, skrivna som binära siffror med kontroll 4 som den högsta siffran, ett tal från 1 till 7: syndromet, som är exakt positionen för den vända biten. Att vända tillbaka den återställer kodordet. Tricket fungerar eftersom positionerna är numrerade så att varje positions binära form räknar upp de kontroller den hör till, och därför ser koden så prydlig ut när den ritas som tre överlappande cirklar.
Hammingavstånd
Hammingavståndet mellan två ord är antalet positioner där de skiljer sig åt. I (7,4)-koden ligger två kodord alltid minst 3 ifrån varandra. Ett ord med ett fel ligger fortfarande på avståndet 1 från kodordet som skickades och minst 2 från alla andra, så avkodning till närmaste kodord rättar det. Allmänt upptäcker en kod vars kodord ligger minst d ifrån varandra d − 1 fel och rättar (d − 1)/2 av dem, avrundat nedåt. En extra paritetsbit över hela ordet höjer avståndet till 4 och ger den utökade koden som rättar ett fel och upptäcker två.
Shannons gräns
År 1948, två år före Hammings artikel, bevisade Claude Shannon en häpnadsväckande sats. Varje brusig kanal har en kapacitet, och data kan skickas med vilken takt som helst under den med så få fel man vill, genom att använda tillräckligt långa koder; över den går fel inte att undvika. Shannon visade att sådana koder finns men inte hur man bygger dem. Att hitta praktiska koder som kommer nära hans gräns tog ett halvt sekel, från Reed-Solomon-koder 1960 till turbokoder 1993 och återupptäckten av LDPC-koder (low-density parity-check).
Koder runt omkring oss
Reed-Solomon-koder gör att cd-skivor spelar trots repor och att QR-koder går att skanna med upp till 30 % av symbolen skadad. Serverminnen använder utökade Hammingkoder för att rätta enstaka bitar som vänts av kosmisk strålning. Voyagers bilder av de yttre planeterna skyddades av Golaykoder och senare Reed-Solomon-koder, och LDPC- och polära koder i 5G och wifi kramar ur nästan varje bit som kanalen tillåter. Till och med streckkoden på en bok och den sista siffran i ett bankkontonummer är enkla felupptäckande koder.
Utforska själv
Öppna simulatorn för felrättande koder för att koda valfria fyra databitar med Hamming (7,4)-koden, vända bitar genom att klicka på dem i cirklarna eller i raden och se de misslyckade cirklarna och syndromet peka på felet innan avkodaren reparerar det. Slå på den extra paritetsbiten för att se dubbelfel upptäckas, och skicka ett meddelande genom en brusig kanal för att jämföra vad som kommer fram med och utan koden.
Ofta ställda frågor
Vad är skillnaden mellan felupptäckt och felrättning?
Upptäckt talar bara om för mottagaren att något är fel, så den måste begära data igen; det gör en paritetsbit eller en kontrollsumma. Rättning låter mottagaren återskapa originalet utan att fråga, vilket kräver mer redundans. System som inte kan fråga igen, till exempel en rymdsond miljontals kilometer bort eller en dvd, förlitar sig på rättning.
Varför inte bara skicka allt två gånger?
Två kopior visar att ett fel har inträffat men inte vilken kopia som är rätt, och de fördubblar kostnaden. Tre kopior möjliggör en majoritetsomröstning men tredubblar den. Hammings kod rättar ett enskilt fel per block om sju med mindre än dubbla antalet bitar, och längre koder klarar sig mycket bättre.
Vem var Richard Hamming?
En amerikansk matematiker, 1915–1998, som arbetade i Manhattanprojektet och sedan i trettio år vid Bell Labs. Förutom för sina koder är han känd för Hammingfönstret inom signalbehandling, för Hammingavståndet och för sin föreläsning ”You and Your Research”. Han fick Turingpriset 1968.
Kan en kod rätta hur många fel som helst?
Bara med tillräckligt med redundans. En kod kan rätta upp till (d − 1)/2 fel per block, där d är minsta avståndet mellan kodord, och längre koder med fler kontrollbitar når större d. Shannons sats sätter den yttersta gränsen: ingen kod kan överträffa kanalens kapacitet.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna simulatorn för felrättande koder