Onderzoek foutenverbeterende codes

Vele lezers zullen enige weken geleden fraaie foto’s van de ringen van Saturnus in de krant hebben gezien. Deze foto’s zijn naar de aarde geseind door een van de Voyager satellieten. Het signaal, een lange reeks van twee soorten symbolen die we hier 0 en 1 zullen noemen, werd omgezet in de foto’s die wij zagen. Dit laatste gebeurde op het Jet Propulsion Laboratory van hot California Institute of Technology, een laboratorium waar ook twee leden van de groep discrete wiskunde van onze TH enige tijd hebben gewerkt. Hoe komt zo’n signaal tot stand? De door de satelliet gemaakte foto’s worden verdeeld in een rooster van kleine hokjes, waarna van elk hokje de zwartingsgraad wordt gemeten, in een schaal van 0 t/m 63. Elk van deze getallen is in het tweetallig stelsel (= binair) een rijtje van zes nullen en enen (bv. 45 = 1.25 + 0.24 + 1.23 + 1.22 + 0.2+1 101101). Zo geeft één foto aanleiding tot een reeks van duizenden nullen en enen die naar de aarde moet worden geseind. Bij aankomst in Californië is het signaal zó zwak dat het eerst moet worden versterkt. Door thermische ruis in de ontvanger wordt daardoor het signaal verminkt hetgeen in de praktijk tot gevolg heeft dat een deel van de nullen wordt geïnterpreteerd als enen, en omgekeerd. Als bv. in het bovengenoemde getallenvoorbeeld de eerste 1 in een 0 wordt omgezet is de zwartingsgraad 45 veranderd in 13. Dit soort fouten zou zeer bizarre foto’s tot gevolg kunnen hebben. De meest eenvoudige manier om dit onaangename verschijnsel te bestrijden is herhaling. leder symbool (0 of 1) wordt niet één keer maar bijvoorbeeld vijf keer geseind. De ontvanger zal i.p.v. 11111 soms iets anders ontvangen, maar zeer zelden een reeks van vijf symbolen met minder dan drie enen. Door een meerderheidsbesluit wordt uitgemaakt of het bedoelde signaal 0 of 1 was. Het is duidelijk dat dit systeem de kwaliteit van de foto’s aanzienlijk zal verbeteren maar dat de tijd die benodigd is voor het zenden van één foto nu vijf keer zo groot is als eerst het geval was. De vraag is of we deze kwaliteitsverbetering tot stand kunnen brengen zonder dat het zo erg veel meer tijd kost. Het antwoord op deze vraag is ja en dat is de basis van de theorie van foutenverbeterende codes, één van de belangrijkste interessegebieden van de groep Discrete Wiskunde.