In de it wordt meer wiskunde toegepast dan menigeen denkt. Zo is het toepassen van in de wiskunde bekende algoritmes van wezenlijk belang voor allerlei technologieën.
De kop boven dit artikel zal de lezer misschien verbazen. Bij vernieuwingen op it-gebied denken we allereerst aan technische hoogstandjes als het verhogen van de schrijfdichtheid, het lager ‘laten vliegen’ van de harde-schijfkoppen, het verhogen van toerentallen, het opvoeren van processorsnelheden en het vergroten van overdrachtsnelheden. In de technische innovatie wordt echter vaak gebruik gemaakt van ontwikkelingen op het gebied van de wiskunde zonder dat we ons dat meteen realiseren. Een sprekend recent voorbeeld is de ontwikkeling van het EMC2 Centera-systeem. Dit systeem gebruikt een versleutelingstechnologie op basis van MD5, een 128-bit hash-algoritme. De basis hiervan is niet de techniek, maar de wiskunde.
Praktijktoepassing wiskunde in IT
De Vlaming Paul Charpentier, tegenwoordig werkzaam voor Hypertrust, vertelde tijdens een congres in Brussel dat hij onder de douche op het idee kwam een van de bekende hash-algoritmen uit de wiskunde toe te passen bij het ontwikkelen van een elektronische vingerafdruk. Met zijn team ontwikkelaars verbaasde hij zich erover dat niemand hier nog aan gedacht had. Het resultaat werd uiteindelijk verkocht aan EMC2, dat het toepaste in het Centera-systeem.
Veel van de tegenwoordig geproduceerde data is van het ‘fixed-content’ type. Dit is data die niet regelmatig wijzigt. Met een hash-algoritme wordt aan elk document een unieke handtekening toegekend. Zolang de inhoud van het document niet wijzigt, verandert ook de handtekening niet, zelfs als de naam en de extensie veranderen. Typerend voor onze it-systemen is dat dezelfde informatie gemiddeld zeven maal wordt opgeslagen. De vingerafdrukmethode maakt het mogelijk dat te reduceren, wat onder andere kostbare schijfruimte bespaart en de back-uptijd verkleint. EMC2 was zo succesvol met deze toepassing (er zijn inmiddels vele petabytes geïnstalleerd) dat concurrenten HP en IBM ook op deze trein gesprongen zijn en met vergelijkbare oplossingen zijn gekomen. Een ander bedrijf, DCT (Data Center Technologies), kwam op het idee (vast geen toeval) om een back-upappliance te ontwikkelen op basis van een vergelijkbare techniek. DCT is inmiddels gekocht door softwaregigant Symantec-Veritas.
Deze toepassingen van de wiskunde staan echter niet op zichzelf. Hardware- en softwarecompressietechnieken maken al vanaf het begin gebruik van methoden en technieken uit de wiskunde, bijvoorbeeld de Lempel-Zev-algoritmen en de Huffman Coding. De methodieken voor foutcorrectie in geheugens van onze mobieltjes en pc’s, en het corrigeren van krassen op onze moderne cd’s en dvd’s (Reed Solomon Codes) zijn ook op wiskunde gebaseerd. Hetzelfde geldt voor de op dit moment sterk in de belangstelling staande dataencryptiemethodieken waarvan de oorsprong in de theorieën voor abstracte getallen liggen.
Op bezoek in het Walhalla van de moderne wiskunde
Aanleiding voor Computable eens een kijkje te nemen in het walhalla van de moderne wiskunde. Vorige week promoveerde Dion Gijswijt aan de Universiteit van Amsterdam op het onderwerp foutcorrigerende codes. De 27-jarige Dion deed zijn promotieonderzoek aan de Universiteit van Amsterdam en het Centrum voor Wiskunde en Informatica. Dions onderzoek valt onder de categorie zuiver wetenschappelijk onderzoek en de directe link met de hedendaagse it is niet direct aanwezig. Dr. Gijswijt verbaasde zich daarom aanvankelijk over de belangstelling van de kant van Computable.
Het proefschrift, waarvan de officiële naam luidt: ‘Matrix Algebras and Semidefinite Programming Techniques for Codes’, gaat over het maken van foutcorrigerende codes. “Een goede code kenmerkt zich doordat hij veel fouten kan corrigeren en daarbij relatief weinig bandbreedte gebruikt”, aldus Dion. Hierbij wordt niet alleen gekeken naar de ons bekende binaire codes (0 en 1) maar men kijkt veel algemener. Zo maakt men ook gebruik van Ternaire codes (0,1,2). Dit laatste is wat moeilijker in it-technologie te realiseren.
Om dit artikel nog enigszins leesbaar te houden beperken we ons tot de binaire code. Deze bestaat uit een collectie van rijtjes nullen en enen van een bepaalde vaste lengte n. Een voorbeeld van een dergelijke (lineaire) code is Hammingcode, in tabel I. Deze Hammingcode heeft een lengte (n) van 7 en bestaat uit 16 codewoorden. De eerste vier bits uit de code zijn ‘informatiebits’; de overige drie zijn parity bits. Bij de Hammingcode verschillen twee willekeurige woorden (inclusief de parity bits) altijd minstens 3 bits: de minimumafstand van de code (d) is 3. Daardoor kan deze code 1 fout corrigeren. Meer algemeen geldt dat als het minimum van een code d=2e+1 bedraagt er e fouten kunnen worden gecorrigeerd.
Om een databestand tegen fouten te beschermen, kan de data worden opgesplitst in stukken van 4 bits waar drie parity bits aan worden toegevoegd, wat betekent dat het aldus gecodeerde databestand 75 procent langer wordt. De winst is echter dat fouten kunnen worden opgespoord en gecorrigeerd.
Door langere codes te gebruiken kan het rendement verbeterd worden. Bij ECC-geheugen (Error-Correcting Code) bijvoorbeeld worden 8 extra bits gebruikt om een groep van 64 bits tegen één fout te beschermen.
Hoe meer codewoorden er voor een gegeven woordlengte n kunnen worden gemaakt, hoe hoger de ‘informatierate’. Het maximaal aantal codewoorden in een code met lengte n en afstand d wordt wiskundig in de verzamelingenleer aangeven met A(n,d). De grootte van A kan niet in algemene zin bepaald worden.
Veel onderzoeken zijn erop gericht te zoeken naar ‘goede codes’ met zoveel mogelijk codewoorden. Het onderzoek van dr. Dion Gijswijt benadert het probleem van de andere kant. Men probeert de bovengrenzen van A(n,d) aan te geven. Dit wil zeggen dat men probeert te bewijzen dat er geen codes kunnen bestaan van een lengte n en afstand d met meer dan een bepaald aantal codewoorden. Voor de genoemde Hamming-code is dit relatief simpel: men kan bewijzen dat er geen code kan bestaan van lengte 7 en afstand 3 met meer dan 16 codewoorden. Voor grotere waarden van n en d en als men zich ook nog eens niet beperkt tot uitsluitend de binaire code wordt het verhaal aanzienlijk complexer.
De basis van het onderzoek
In de zeventiger jaren is door Delsarte, werkzaam bij het Philips Nat.lab., een methode ontwikkeld om een goede bovengrens te bepalen. Deze methode staat te boek als de meest succesvolle. Zijn methode gebruikt lineaire programmering en relaties tussen tweetallen codewoorden. Dions onderzoek is er opgericht de door Delsarte vastgestelde grenzen, die enigszins ‘ruim’ lijken, verder te verfijnen. Hierbij is voortgebouwd op een eerder door zijn promotor uitgebrachte publicatie (A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51) over dit onderwerp.
In zijn proefschrift verfijnt Dion de methode Delsarte. Hij gebruikt daarbij de zogeheten semidefiniete programmering (waarvan lineaire programmering een speciaal geval is), wat het mogelijk maakt de relaties tussen drietallen codewoorden te beschouwen. Door het gebruik van deze methode blijkt het mogelijk om een groot aantal bovengrenzen voor de getallen A(n,d) te verscherpen.
De directe toepasbaarheid van de methode in de huidige it-technologie is er nog niet. Toch is voldoende duidelijk dat wiskundig onderzoek uit het verleden herhaaldelijk de weg naar de praktijk heeft gevonden en daar enorme invloed heeft gehad. Om in wiskundige stijl te blijven: het is lastig te bewijzen dat het nooit toegepast zal worden en het tegendeel is evenmin te bewijzen.
Gert Brouwer