Codeconcatenatie: twee eenvoudige codes samen sterker dan één ingewikkelde
Stel je voor dat een tekst twee keer wordt nagekeken voordat hij de deur uitgaat. Eerst controleert een corrector op kleine tikfouten: een verkeerde letter hier, een omgedraaid woord daar. Daarna leest een tweede lezer de hele tekst nog eens door om grotere fouten eruit te vissen die de eerste corrector heeft gemist. Geen van beide controles is perfect, maar de combinatie van de twee vangt bijna alles. Dat is in essentie wat codeconcatenatie doet, alleen dan niet met tekst maar met digitale data die over een storingsgevoelig kanaal moeten reizen.
Codeconcatenatie, in het Engels concatenated coding, is een techniek uit de informatietheorie om fouten in digitale data automatisch te herstellen. In plaats van één zeer krachtige maar onwerkbaar ingewikkelde foutcorrectiecode te bouwen, stapelt men twee eenvoudigere codes op elkaar: een 'buitenste' en een 'binnenste'. Samen bereiken ze bijna dezelfde betrouwbaarheid als één superieure code, maar dan met apparatuur die daadwerkelijk te bouwen en te betalen is. De techniek is niet nieuw — ze stamt uit 1966 — maar duikt tot op de dag van vandaag op in nieuwe toepassingen, van ruimtevaart tot DNA-opslag en kwantumcomputers.
Wat is het precies?
Om codeconcatenatie te begrijpen, helpt het eerst te weten wat een foutcorrigerende code is. Dat is een manier om aan data extra, overbodige informatie toe te voegen, zodat een ontvanger fouten niet alleen kan opmerken maar ook zelf kan herstellen — zonder dat er iets opnieuw hoeft te worden verstuurd. Denk aan een boodschap die je drie keer herhaalt: als er ergens een woord verminkt raakt, kan de ontvanger aan de hand van de andere twee versies raden wat er had moeten staan. Echte foutcorrectiecodes zijn efficiënter dan simpelweg alles drie keer sturen, maar het principe — redundantie toevoegen — is hetzelfde.
In 1966 bedacht de Amerikaanse ingenieur G. David Forney Jr., destijds promovendus aan het Massachusetts Institute of Technology (MIT), een manier om twee van zulke codes te combineren. Eerst wordt de data door een buitenste code gehaald, vaak een zogeheten Reed-Solomon-code. Die werkt niet met losse nullen en enen maar met grotere symbolen (groepjes bits) en is sterk in het herstellen van 'burst-fouten': een aaneengesloten stuk data dat in één keer verloren gaat, bijvoorbeeld door een kras op een schijfje. Het resultaat gaat vervolgens door een binnenste code, bijvoorbeeld een zogeheten convolutionele code, die juist goed is in het opvangen van willekeurige, verspreide bitfoutjes zoals ruis op een radiosignaal veroorzaakt.
Bij het ontvangen wordt de volgorde omgedraaid: eerst haalt de binnenste decoder de kleine, verspreide fouten eruit, waarna de buitenste decoder de grotere, hardnekkigere fouten opruimt die er nog doorheen zijn geglipt. Het slimme zit hem erin dat elke laag afzonderlijk relatief simpel te decoderen is, terwijl de twee samen een prestatie neerzetten die in de buurt komt van de theoretische limiet voor foutloze communicatie over een ruisend kanaal — een grens die in 1948 werd vastgelegd door wiskundige Claude Shannon en sindsdien de Shannon-limiet heet.
Wat wil men ermee bereiken?
Het doel is steeds hetzelfde: data betrouwbaar laten aankomen of bewaard blijven, ook als het overdrachtskanaal of het opslagmedium verre van perfect is. Dat is vooral belangrijk wanneer opnieuw versturen geen optie is, of wanneer het fysieke medium van nature ruis of slijtage kent.
Denk aan een radiosignaal dat miljarden kilometers door de ruimte heeft gereisd en bij aankomst nog maar een fractie van zijn oorspronkelijke sterkte heeft; aan een schijfje dat bekrast of met vingerafdrukken besmeurd raakt; aan een DNA-molecuul dat na jaren opslag chemisch is aangetast; of aan een qubit in een kwantumcomputer, dat al na een fractie van een seconde zijn kwantumtoestand verliest door contact met de omgeving (een verschijnsel dat decoherentie heet). In al die gevallen belooft codeconcatenatie een praktische, bouwbare oplossing: geen wonderoplossing die alle fouten wegtovert, maar een haalbare manier om heel dicht bij de theoretisch best mogelijke betrouwbaarheid te komen.
Voorbeelden uit de praktijk
De techniek is verre van hypothetisch en zit al decennia in apparatuur die de meeste mensen dagelijks gebruikt of waarvan ze de resultaten zien.
- Voyager 2 (NASA/JPL, jaren tachtig): voor de ontmoeting met Uranus in 1986 werd de foutcorrectie van het ruimtesondesignaal versterkt met een concatenatie van een Reed-Solomon-code en een convolutionele code. Daardoor kon de sonde, met een radiosignaal dat inmiddels extreem zwak was geworden, toch nog bruikbare beelden en meetgegevens naar de aarde sturen — een aanpak die ook bijdroeg aan het succes van de Neptunus-passage in 1989.
- De compact disc (Philips en Sony, commercieel geïntroduceerd in 1982): gebruikt een concatenated code die bekendstaat als CIRC (Cross-Interleaved Reed-Solomon Code). Dankzij deze gelaagde foutcorrectie kan een cd nog steeds foutloos afspelen ondanks kleine krasjes of stofdeeltjes.
- Onderzoek naar DNA-dataopslag: onderzoeksgroepen van Microsoft Research en de University of Washington experimenteren sinds het midden van de jaren 2010 met het opslaan van digitale bestanden in synthetische DNA-strengen, waarbij gelaagde foutcorrectiecodes helpen om de oorspronkelijke data te reconstrueren, ook als individuele DNA-fragmenten beschadigd raken of verkeerd worden afgelezen. Ook aan de ETH Zürich wordt, onder meer door onderzoeker Robert Grass, gewerkt aan robuustere DNA-opslag, bijvoorbeeld door DNA in te kapselen in silica.
- Kwantumfoutcorrectie: in 1995 introduceerde natuurkundige Peter Shor het idee van 'geneste' of geconcateneerde kwantumcodes, waarbij een kwantumfoutcorrigerende code in zichzelf wordt herhaald om fragiele qubits beter te beschermen. Dat basisidee speelt nog altijd een rol in het onderzoek naar foutbestendige kwantumcomputers.
- Satelliettelevisie (DVB-S-standaard, jaren negentig): ook deze Europese standaard voor digitale satelliet-tv leunde op een concatenatie van Reed-Solomon- en convolutionele codes, rechtstreeks afgeleid van de techniek die eerder in de ruimtevaart was beproefd.
Hoe ver is de techniek?
Voor de klassieke toepassingen is codeconcatenatie allang geen nieuwigheid meer: in ruimtevaart en optische opslag wordt de techniek al sinds de jaren tachtig op grote schaal en betrouwbaar gebruikt. In veel nieuwere communicatiestandaarden, zoals moderne mobiele netwerken en wifi, hebben andere codefamilies — zogeheten turbocodes (sinds 1993), LDPC-codes en polaire codes — de klassieke concatenatie echter grotendeels verdrongen, omdat ze met de rekenkracht van nu nog dichter bij de Shannon-limiet komen.
Het onderliggende idee van concatenatie leeft echter voort in twee toekomstgerichte onderzoeksvelden. Bij DNA-opslag is de techniek nog volop in de onderzoeksfase: het schrijven en lezen van DNA is nog traag en duur vergeleken met gewone harde schijven, en het ontwerpen van goede foutcorrectieschema's — waaronder concatenated codes — is een van de belangrijkste obstakels die onderzoekers nog moeten overwinnen voordat DNA-opslag commercieel haalbaar wordt. Er zijn al kleinschalige demonstraties geweest waarbij tekst en afbeeldingen succesvol in DNA werden opgeslagen en teruggelezen, maar grootschalige, betaalbare toepassing ligt naar verwachting nog jaren verderop.
Bij kwantumcomputers is geconcateneerde foutcorrectie een van de belangrijkste strategieën — naast de zogeheten surface codes — op weg naar een grootschalige, foutbestendige kwantumcomputer. Halverwege de jaren 2020 heeft nog geen enkel systeem de schaal en betrouwbaarheid bereikt die nodig is om deze bescherming volledig praktisch te maken; het aantal qubits en hun foutenpercentage moeten beide nog aanzienlijk verbeteren. Dit blijft dus nadrukkelijk een open technisch probleem, geen afgeronde technologie.
Wie werken eraan?
Aan de ruimtevaartkant hebben instanties als NASA en het Jet Propulsion Laboratory (JPL) decennialang ervaring opgebouwd met concatenated codes voor communicatie met verre sondes; internationale standaarden hiervoor worden mede vastgelegd door het Consultative Committee for Space Data Systems (CCSDS), het samenwerkingsverband van ruimtevaartorganisaties wereldwijd. In de opslagindustrie waren Philips en Sony de pioniers achter de foutcorrectie van de compact disc. Op het gebied van DNA-opslag lopen Microsoft Research en de University of Washington voorop in de Verenigde Staten, met de ETH Zürich als belangrijk Europees onderzoekscentrum. Bij kwantumfoutcorrectie zijn academische groepen aan onder meer Caltech en MIT actief, naast de kwantumonderzoeksafdelingen van bedrijven als IBM en Google. Op het bredere vlak van coderingstheorie speelt de beroepsvereniging IEEE, die vaktijdschriften en standaarden op dit gebied publiceert, wereldwijd een verbindende rol.