Foutcorrigerende codes uitgelegd
Geen enkel kanaal is perfect. Kosmische straling draait bits om in het geheugen, krassen wissen delen van een schijf uit en radiosignalen vervagen. In plaats van op het beste te hopen, voegen digitale systemen op een slimme manier redundantie toe, zodat de ontvanger kan achterhalen wat er is verzonden, zelfs als een deel ervan fout aankomt. De wiskunde van deze codes, die eind jaren 1940 begon, beschermt in stilte bijna elk bit dat we opslaan of versturen.
Fouten detecteren met pariteit
De eenvoudigste bescherming is één pariteitsbit: voeg een 1 of een 0 toe zodat het totale aantal enen even is. Als er onderweg één bit omdraait, wordt het aantal oneven en weet de ontvanger dat er iets misging. Pariteit kan niet zeggen welk bit fout is, en twee omgedraaide bits heffen elkaar ongemerkt op, maar het is goedkoop en werd tientallen jaren gebruikt in geheugen en seriële verbindingen. Een fout detecteren is wel maar het halve werk: daarna moeten de gegevens opnieuw worden verzonden.
Corrigeren door herhaling
Om een fout te corrigeren zonder opnieuw te vragen, heeft de ontvanger genoeg redundantie nodig om de fout weg te stemmen. Als elk bit drie keer wordt verzonden, 000 of 111, kan de ontvanger de meerderheid volgen: één omgedraaid bit in een drietal wordt gecorrigeerd. De prijs is hoog: drie bits voor elk databit, en twee omgedraaide bits in hetzelfde drietal winnen nog steeds. De vraag waarmee de coderingstheorie begon, was of het beter kon.
De code van Hamming
In 1947 werkte Richard Hamming bij Bell Labs aan een relaiscomputer die programma's van ponskaarten las. Als die in het weekend een fout vond, stopte hij gewoon, en Hamming trof op maandag verspilde berekeningen aan. Als een machine een fout kan detecteren, vroeg hij zich af, waarom kan ze die dan niet lokaliseren en corrigeren? Zijn antwoord, gepubliceerd in 1950, verstuurt 4 databits als 7. Drie pariteitsbits, op de posities 1, 2 en 4, controleren elk een andere overlappende groep posities, zo gekozen dat elke enkele fout een unieke combinatie van controles breekt.
Het syndroom
De ontvanger berekent de drie controles opnieuw. Als ze allemaal kloppen, wordt het woord geaccepteerd. Als er enkele falen, levert het opschrijven van de mislukte controles als binaire cijfers, met controle 4 als hoogste cijfer, een getal van 1 tot 7 op: het syndroom, dat precies de positie van het omgedraaide bit is. Door dat bit terug te draaien wordt het codewoord hersteld. De truc werkt omdat de posities zo zijn genummerd dat de binaire schrijfwijze van elke positie de controles opsomt waar ze bij hoort; daarom ziet de code er zo netjes uit als je haar tekent als drie overlappende cirkels.
Hammingafstand
De Hammingafstand tussen twee woorden is het aantal posities waarop ze verschillen. In de (7,4)-code liggen twee codewoorden altijd minstens 3 uit elkaar. Een woord met één fout ligt nog steeds op afstand 1 van het verzonden codewoord en op minstens 2 van elk ander, dus decoderen naar het dichtstbijzijnde codewoord corrigeert de fout. In het algemeen detecteert een code waarvan de codewoorden minstens d uit elkaar liggen d − 1 fouten en corrigeert ze er (d − 1)/2 van, naar beneden afgerond. Een extra pariteitsbit over het hele woord verhoogt de afstand tot 4, wat de uitgebreide code oplevert die één fout corrigeert en twee detecteert.
De limiet van Shannon
In 1948, twee jaar vóór het artikel van Hamming, bewees Claude Shannon een verrassende stelling. Elk kanaal met ruis heeft een capaciteit, en gegevens kunnen met elke snelheid daaronder worden verzonden met zo weinig fouten als je wilt, door lang genoeg codes te gebruiken; daarboven zijn fouten onvermijdelijk. Shannon toonde aan dat zulke codes bestaan, maar niet hoe je ze bouwt. Het vinden van praktische codes die dicht bij zijn limiet komen, kostte een halve eeuw, van Reed-Solomon-codes in 1960 tot turbocodes in 1993 en de herontdekking van low-density parity-check-codes.
Codes overal om ons heen
Dankzij Reed-Solomon-codes spelen cd's door krassen heen en zijn QR-codes nog te scannen als tot 30% van het symbool beschadigd is. Servergeheugen gebruikt uitgebreide Hammingcodes om losse bits te herstellen die door kosmische straling zijn omgedraaid. De foto's die Voyager van de buitenplaneten maakte, werden beschermd door Golaycodes en later door Reed-Solomon-codes, en de LDPC- en polaire codes van 5G en wifi persen er bijna elk bit uit dat het kanaal toelaat. Zelfs de streepjescode op een boek en het laatste cijfer van een bankrekeningnummer zijn eenvoudige foutdetecterende codes.
Probeer het zelf
Open de simulator voor foutcorrigerende codes om vier databits naar keuze te coderen met de Hamming (7,4)-code, bits om te draaien door erop te klikken in de cirkels of in de rij, en te zien hoe de cirkels die niet kloppen en het syndroom de fout aanwijzen voordat de decoder die herstelt. Zet het extra pariteitsbit aan om te zien hoe dubbele fouten worden gedetecteerd, en stuur een bericht door een kanaal met ruis om te vergelijken wat er aankomt met en zonder de code.
Veelgestelde vragen
Wat is het verschil tussen foutdetectie en foutcorrectie?
Detectie vertelt de ontvanger alleen dat er iets mis is, zodat die de gegevens opnieuw moet opvragen; een pariteitsbit of een controlesom doet dat. Correctie laat de ontvanger het origineel reconstrueren zonder te vragen, en daarvoor is meer redundantie nodig. Systemen die niet opnieuw kunnen vragen, zoals een ruimtesonde op miljoenen kilometers afstand of een dvd, vertrouwen op correctie.
Waarom niet gewoon alles twee keer versturen?
Twee kopieën laten zien dat er een fout is opgetreden, maar niet welke kopie juist is, en ze verdubbelen de kosten. Drie kopieën maken een meerderheidsstemming mogelijk, maar verdrievoudigen de kosten. De code van Hamming corrigeert één fout per blok van zeven met minder dan het dubbele aantal bits, en langere codes doen het veel beter.
Wie was Richard Hamming?
Een Amerikaanse wiskundige (1915–1998) die aan het Manhattanproject werkte en daarna dertig jaar bij Bell Labs. Behalve om zijn codes is hij bekend om het Hammingvenster in de signaalverwerking, om de Hammingafstand en om zijn lezing ‘You and Your Research’. Hij ontving in 1968 de Turing Award.
Kan een code elk aantal fouten corrigeren?
Alleen met genoeg redundantie. Een code kan tot (d − 1)/2 fouten per blok corrigeren, waarbij d de minimale afstand tussen codewoorden is, en langere codes met meer controlebits halen een grotere d. De stelling van Shannon legt de uiteindelijke grens vast: geen enkele code kan de capaciteit van het kanaal overtreffen.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open de simulator voor foutcorrigerende codes