Coderingstheorie: hoe wiskunde fouten in digitale data herstelt
Stel je voor dat je een belangrijk telefoonnummer doorgeeft via een slechte verbinding, met ruis en haperingen. Om te voorkomen dat er een verkeerd cijfer aankomt, herhaal je het nummer niet zomaar, maar voeg je een extra controlecijfer toe dat wiskundig afhangt van de andere cijfers. Komt er onderweg iets fout, dan klopt dat controlecijfer niet meer en weet de ontvanger dat er iets moet worden gecorrigeerd, soms zelfs precies wélk cijfer. Dat is in de kern wat coderingstheorie doet, maar dan op de schaal van miljarden bits per seconde.
Coderingstheorie is het wiskundige vakgebied dat zich bezighoudt met het betrouwbaar versturen en opslaan van digitale informatie, ook als het transportkanaal of het opslagmedium ruis, storingen of beschadigingen veroorzaakt. Het combineert algebra, kansrekening en informatietheorie om zogeheten foutcorrigerende codes te ontwerpen: manieren om berichten zo te verpakken dat fouten niet alleen ontdekt, maar ook automatisch hersteld kunnen worden. Zonder deze wiskunde zouden wifi, satelliet-tv, cd's en zelfs simpele QR-codes onbetrouwbaar of onbruikbaar zijn.
Wat is het precies?
Het basisidee is redundantie: je stuurt bewust meer informatie mee dan strikt nodig is, zodat de ontvanger fouten kan opsporen en herstellen. Het eenvoudigste voorbeeld is een pariteitsbit: bij elk stukje data van bijvoorbeeld zeven bits voeg je een achtste bit toe die aangeeft of het totale aantal enen even of oneven is. Verandert er onderweg één bit door ruis, dan klopt die pariteit niet meer en weet je dat er een fout is. Dat is foutdetectie, maar nog geen correctie: je weet dát er iets mis is, niet wát.
Richard Hamming loste dat op met wat nu de Hamming-code heet: door meerdere, slim gekozen controlebits te combineren, kun je niet alleen zien dát er een fout zit, maar ook precies welke bit is omgeklapt, en die dan terugzetten. De afstand tussen twee geldige codewoorden, de zogeheten Hamming-afstand, bepaalt hoeveel fouten een code kan opsporen en corrigeren: hoe verder codewoorden uit elkaar liggen, hoe meer fouten er tussen kunnen zitten zonder dat de ontvanger het verkeerde woord kiest.
Modernere codes gaan veel verder dan losse bits. Blokcodes zoals Reed-Solomoncodes werken met hele groepen symbolen tegelijk en zijn bijzonder goed in het herstellen van 'burst errors', aaneengesloten stukken beschadigde data, zoals een kras op een cd. Convolutionele codes verwerken een continue stroom bits, waarbij elk uitgezonden symbool afhangt van meerdere voorgaande bits, wat helpt tegen ruis die geleidelijk optreedt. De nieuwste generaties, zoals LDPC-codes (low-density parity-check) en polaire codes, gebruiken slimme netwerken van eenvoudige controlevergelijkingen die met iteratieve algoritmes worden gedecodeerd, en benaderen daarmee de theoretische grens die Claude Shannon in 1948 vaststelde: de maximale hoeveelheid informatie die betrouwbaar over een ruizig kanaal kan, de zogeheten Shannon-limiet.
Wat wil men ermee bereiken?
Het uiteindelijke doel is simpel te formuleren, maar wiskundig lastig te bereiken: zo dicht mogelijk bij de Shannon-limiet communiceren met zo min mogelijk extra overhead en zo min mogelijk rekenkracht voor het coderen en decoderen. Elke bit aan redundantie kost immers bandbreedte, opslagruimte of energie, dus onderzoekers zoeken voortdurend naar codes die minder 'ruis' nodig hebben om dezelfde betrouwbaarheid te bereiken.
Coderingstheorie maakt daarnaast fysiek onbetrouwbare technologie bruikbaar. Radiosignalen verzwakken, geheugenchips krijgen af en toe een bitflip door kosmische straling, en optische schijven raken bekrast. In plaats van te proberen het fysieke kanaal perfect te maken, wat vaak onmogelijk of onbetaalbaar is, accepteert men de ruis en rekent men die er met wiskunde weer uit. Dat is precies waarom het vakgebied al sinds de jaren veertig van de vorige eeuw relevant blijft: van telegraafkabels tot 5G-netwerken en diepe-ruimtemissies.
Voorbeelden uit de praktijk
Cd's, dvd's en blu-ray (vanaf 1982): Philips en Sony introduceerden de cd met een foutcorrectiesysteem genaamd CIRC, gebaseerd op Reed-Solomoncodes, ontwikkeld door Irving Reed en Gustave Solomon in 1960. Dankzij deze codes blijft een cd met een lichte kras of vingerafdruk toch foutloos afspeelbaar.
QR-codes: de zwart-witblokjes die je met een telefooncamera scant, bevatten eveneens Reed-Solomon foutcorrectie. Bij het hoogste correctieniveau kan een aanzienlijk deel van de code, tot ruwweg een kwart tot een derde, beschadigd of onleesbaar zijn terwijl scannen nog steeds lukt.
NASA's Voyager-missies (sinds 1977): de twee Voyager-sondes sturen al bijna vijftig jaar signalen naar de aarde die door de enorme afstand extreem zwak zijn. NASA gebruikte convolutionele codes, later gecombineerd met Reed-Solomoncodes, om ook uit een bijna onmeetbaar signaal nog betrouwbare data te destilleren.
Mobiele netwerken (5G, vanaf 2016): de standaardisatieorganisatie 3GPP koos polaire codes, uitgevonden door Erdal Arikan in 2008, voor het besturingskanaal van 5G, en LDPC-codes voor het datakanaal. Polaire codes waren de eerste codes waarvan wiskundig bewezen is dat ze de Shannon-limiet exact kunnen benaderen.
Computergeheugen (ECC-RAM): servers en veel professionele computers gebruiken geheugen met ingebouwde foutcorrectie, gebaseerd op uitbreidingen van de Hamming-code uit 1950. Dat voorkomt dat een toevallige bitflip, bijvoorbeeld door kosmische straling, tot een crash of stille datacorruptie leidt.
Hoe ver is de techniek?
Coderingstheorie is een volwassen vakgebied met een lange, goed gedocumenteerde geschiedenis. Belangrijke mijlpalen: Shannons grondleggende artikel uit 1948, Hammings eerste praktische foutcorrigerende code in 1950, Reed en Solomons codes uit 1960, en de introductie van turbocodes in 1993 door Claude Berrou, Alain Glavieux en Punya Thitimajshima, de eerste codes die de Shannon-limiet in de praktijk dicht benaderden. Sindsdien zijn LDPC-codes (oorspronkelijk bedacht door Robert Gallager in de jaren zestig, maar pas in de jaren negentig praktisch bruikbaar) en polaire codes (2008) de standaard geworden in respectievelijk wifi, satelliet-tv en 5G.
Voor de meeste alledaagse toepassingen is de techniek dus allang uitontwikkeld en overal om ons heen aanwezig, meestal onzichtbaar. Actief onderzoek richt zich nu vooral op nieuwe randgevallen: codes voor 6G-netwerken, extreem energiezuinige decodering voor kleine sensoren (het internet der dingen), en foutcorrectie voor kwantumcomputers, wat een fundamenteel ander en nog volop in ontwikkeling zijnd vakgebied is omdat kwantuminformatie zich niet zomaar laat kopiëren zoals klassieke bits. Ook experimentele toepassingen zoals DNA als opslagmedium, waarbij data in synthetische DNA-strengen wordt gecodeerd, leunen zwaar op coderingstheorie, maar zijn nog verre van commercieel rijp vanwege hoge kosten en trage lees- en schrijfsnelheden.
Wie werken eraan?
De wetenschappelijke basis werd gelegd bij Bell Labs in de Verenigde Staten, waar zowel Shannon als Hamming werkten. Vandaag de dag wordt onderzoek breed verspreid gedaan aan universiteiten wereldwijd, waaronder MIT, Stanford, ETH Zürich en EPFL in Zwitserland. Nederland heeft een sterke traditie op dit gebied: de Technische Universiteit Eindhoven heeft van oudsher een vooraanstaande onderzoeksgroep in coderingstheorie en cryptografie, en het Centrum Wiskunde & Informatica (CWI) in Amsterdam doet fundamenteel onderzoek naar informatie- en coderingstheorie.
Op industrieel vlak zijn chipmakers en telecombedrijven zoals Qualcomm en Huawei belangrijke spelers geweest bij de standaardisatie van polaire en LDPC-codes voor 5G binnen 3GPP, de internationale telecomstandaardisatieorganisatie. Ruimtevaartorganisaties als NASA en het Europese ESA blijven coderingstechnieken doorontwikkelen voor missies waarbij signalen extreem zwak zijn. De IEEE Information Theory Society coördineert internationaal het academische onderzoeksveld via congressen en het toonaangevende tijdschrift IEEE Transactions on Information Theory.