Pariteitscontrole: hoe een simpel telletje computers foutbewust maakt
Pariteitscontrole is een van de oudste en eenvoudigste trucs die computers gebruiken om te ontdekken of gegevens onderweg beschadigd zijn geraakt. Het idee is verrassend simpel: tel hoeveel van de enen in een stukje data er zijn, en voeg daar één extra bitje aan toe dat aangeeft of dat aantal even of oneven was. Verandert er ergens onderweg per ongeluk een bit, dan klopt die telling niet meer en slaat het systeem alarm.
Een handige analogie: stel dat iemand je telefonisch een rij van acht lampjes doorgeeft die aan of uit staan, en je moet die exact naspelen. Om fouten op te vangen, spreken jullie af dat het totale aantal 'aan'-lampjes altijd even moet zijn. Is dat na het doorgeven niet zo, dan weet je meteen dat er ergens een lampje verkeerd is doorgekomen, ook al weet je niet welk. Precies dat principe gebruiken computers, netwerken en geheugenchips al sinds de jaren vijftig om stille datafouten op te sporen.
Wat is het precies?
Computers slaan alles op als bits: enen en nullen. Een groepje van bijvoorbeeld acht bits (een byte) kan tekens, getallen of instructies voorstellen. Bij pariteitscontrole telt het systeem hoeveel van die bits een 1 zijn, en voegt het één extra bit toe: de pariteitsbit.
Er zijn twee varianten. Bij even pariteit ('even parity') wordt de pariteitsbit zo gekozen dat het totale aantal enen, inclusief de pariteitsbit zelf, even is. Bij oneven pariteit geldt precies het omgekeerde: het totaal moet oneven zijn. Welke variant gebruikt wordt, spreken zender en ontvanger vooraf af.
De berekening zelf gebeurt met een simpele logische bewerking die XOR heet (exclusive or, 'exclusieve of'). XOR van twee bits levert een 1 op als de bits van elkaar verschillen, en een 0 als ze gelijk zijn. Door alle bits van een byte na elkaar door XOR te halen, rolt er automatisch uit of het aantal enen even of oneven is, en dat resultaat wordt de pariteitsbit.
Bij het versturen of opslaan van data reist die pariteitsbit gewoon mee. De ontvangende kant doet dezelfde optelling opnieuw en vergelijkt de uitkomst met de meegestuurde pariteitsbit. Komen ze niet overeen, dan is er onderweg minstens één bit gekanteld en wordt de data als foutief gemarkeerd.
Belangrijk is de beperking van deze methode: een simpele pariteitsbit ontdekt alleen fouten waarbij een oneven aantal bits is omgeklapt, dus 1, 3, 5 fouten enzovoort. Slaan er toevallig twee bits om (een even aantal), dan compenseren die fouten elkaar in de telling en blijft de pariteit kloppen, terwijl de data wel degelijk beschadigd is. Pariteitscontrole is dus geen garantie, maar een goedkope steekproef die de meest voorkomende, geïsoleerde fouten opvangt.
Wat wil men ermee bereiken?
Elektronica is nooit perfect. Kabels vangen ruis op, geheugenchips worden af en toe geraakt door kosmische straling of elektrische storing, en opslagmedia kunnen slijten. Daardoor kan een enkel bitje ongemerkt van waarde veranderen. Zonder controlemechanisme zou een computer zo'n fout gewoon niet opmerken en foutieve data als correct behandelen.
Het doel van pariteitscontrole is dan ook foutdetectie: niet het voorkomen van fouten, maar het zo snel en goedkoop mogelijk signaleren ervan, zodat een systeem kan besluiten de data opnieuw op te vragen, een waarschuwing te geven, of in ernstige gevallen zichzelf uit te schakelen om verdere schade te voorkomen. Dat laatste gebeurt bijvoorbeeld in servers met foutgevoelig geheugen, waar een niet te herstellen geheugenfout soms bewust tot een systeemstop leidt in plaats van door te draaien met mogelijk corrupte gegevens.
Daarnaast is pariteitscontrole een bouwsteen. De onderliggende wiskunde, het optellen van bits met XOR, vormt de basis van geavanceerdere foutcorrectietechnieken zoals Hamming-codes, die niet alleen fouten detecteren maar ze ook automatisch kunnen herstellen. Ook in opslagsystemen zoals RAID wordt het pariteitsprincipe hergebruikt, niet om bitfouten in een byte te vangen, maar om een hele kapotte harde schijf te kunnen reconstrueren uit de overgebleven schijven.
Voorbeelden uit de praktijk
Pariteitscontrole duikt op veel meer plekken op dan de meeste mensen beseffen:
- Seriële communicatie (RS-232/UART), jaren zestig en zeventig: bij het versturen van tekens via seriële poorten, zoals bij oude modems en terminals, werd een 7-bits ASCII-teken vaak aangevuld met één pariteitsbit. Dit was decennialang de standaardmanier om eenvoudige verbindingen tegen ruis te beschermen, en is in aangepaste vorm nog terug te vinden in sommige industriële en embedded systemen.
- Richard Hamming en Bell Labs, 1950: wiskundige Richard Hamming werkte bij Bell Labs met een vroege rekenmachine die op ponskaarten draaide. Foutjes in de kaarten zorgden geregeld voor verstoorde berekeningen in het weekend, wanneer er geen operator aanwezig was om in te grijpen. Uit frustratie hierover ontwikkelde hij de Hamming-code, een uitbreiding op simpele pariteit die fouten niet alleen kan opsporen maar ook zelf kan corrigeren.
- ECC-geheugen in servers: veel serverhardware gebruikt Error-Correcting Code (ECC) RAM, geheugen dat via Hamming-achtige pariteitsberekeningen kleine bitfouten (bijvoorbeeld veroorzaakt door kosmische straling) automatisch detecteert en herstelt, zonder dat de gebruiker er iets van merkt. Dit wordt vooral toegepast in datacenters en bedrijfskritische systemen waar stabiliteit zwaarder weegt dan de iets hogere kosten.
- RAID-opslagsystemen, sinds 1988: in het invloedrijke paper 'A Case for Redundant Arrays of Inexpensive Disks (RAID)' beschreven onderzoekers David Patterson, Garth Gibson en Randy Katz van de University of California, Berkeley, hoe meerdere goedkope harde schijven samen betrouwbaarder en sneller konden zijn dan één dure schijf. RAID-niveaus zoals RAID 5 en RAID 6 gebruiken pariteitsgegevens die over de schijven verspreid worden, zodat bij uitval van één (of bij RAID 6 zelfs twee) schijven de verloren data alsnog gereconstrueerd kan worden.
- Ruimtevaartcommunicatie, begin jaren zeventig: bij missies zoals de Mariner-verkenners naar Mars werd, gezien de zwakke en ruisgevoelige signalen over enorme afstanden, gebruikgemaakt van foutcorrigerende codes die voortbouwden op het Hamming/pariteitsprincipe, om ook bij matige signaalkwaliteit nog bruikbare data en beelden terug naar de Aarde te krijgen.
Hoe ver is de techniek?
Pariteitscontrole is geen technologie die nog 'in ontwikkeling' is; het is een uitontwikkelde, decennia oude basistechniek die overal in de digitale infrastructuur verweven zit, vaak onzichtbaar voor de eindgebruiker. Er valt op dit basisniveau weinig te 'doorbreken' of te vernieuwen: het is simpele, betrouwbare wiskunde die al sinds de jaren vijftig grotendeels ongewijzigd wordt toegepast.
De beperkingen zijn echter ook al even lang bekend. Een enkele pariteitsbit detecteert alleen een oneven aantal bitfouten, kan een fout niet lokaliseren of herstellen, en biedt geen bescherming tegen doelbewuste manipulatie van data, iemand die weet welke bit hij moet veranderen kan de pariteit gewoon kloppend houden. Daarom wordt pure pariteitscontrole in veeleisende toepassingen allang aangevuld of vervangen door krachtigere technieken.
CRC (Cyclic Redundancy Check) is bijvoorbeeld gangbaar in netwerken en bestandsformaten en kan veel meer soorten fouten opsporen dan een enkele pariteitsbit. Reed-Solomon-codes worden gebruikt in cd's, dvd's en QR-codes om zelfs grotere foutblokken te herstellen. LDPC-codes (Low-Density Parity-Check codes), ondanks de naam een geavanceerdere afstammeling van het pariteitsprincipe, zitten tegenwoordig in wifi, 5G en opslagmedia omdat ze dicht bij de theoretische grens van foutcorrectie presteren. Kortom: de simpele pariteitsbit van weleer leeft voort, maar vaak verstopt binnenin veel geavanceerdere wiskundige constructies.
Wie werken eraan?
Omdat het om een volwassen, gestandaardiseerde basistechniek gaat, is er geen actief onderzoeksveld met concurrerende partijen zoals bij opkomende technologieën. Wel zijn er organisaties die de techniek historisch hebben ontwikkeld of vandaag in standaarden en producten vastleggen.
Bell Labs, met wiskundige Richard Hamming, staat aan de wieg van de moderne foutcorrectiecode. IBM heeft in de decennia daarna veel bijgedragen aan de praktische toepassing van pariteits- en foutcorrectietechnieken in computergeheugen en opslag. JEDEC, de internationale standaardisatieorganisatie voor geheugenchips, legt vast hoe ECC-geheugenmodules (zoals ECC-DIMM's) moeten werken, en chipfabrikanten als Intel en AMD bouwen ondersteuning voor ECC-geheugen in hun serverprocessoren. IEEE beheert netwerkstandaarden waarin foutdetectiemethoden zoals CRC zijn vastgelegd. Het RAID-concept komt voort uit onderzoek aan UC Berkeley, en wordt sindsdien breed toegepast door de hele opslagindustrie. Ook bestandssystemen zoals ZFS, oorspronkelijk ontwikkeld bij Sun Microsystems, gebruiken checksums en pariteitsachtige technieken om stille datacorruptie op schijven te ontdekken.