Wat is een hammingcode?
Een Hamming-code is een methode voor het detecteren en corrigeren van fouten in een binaire overdracht. Dit gebeurt door het opnemen van extra binaire cijfers in de reeks die worden gebruikt voor controle, evenals een algoritme dat de detectielogica biedt. Een dergelijke code kan twee fouten in elke reeks bits vinden en één bit repareren die mogelijk onjuist is. De meest gebruikelijke Hamming-code staat bekend als de Hamming (7,4), waarbij de vier het oorspronkelijke aantal startbits aangeeft en de zeven het totale aantal bits in de reeks voorstelt nadat de extra controlebits zijn opgenomen.
De techniek dankt zijn naam aan de maker, Richard Hamming, die de methode in 1950 publiceerde. De manier waarop de Hamming-code werkt, is door een reeks bits te nemen en extra controlebits in te voegen, pariteitsbits genoemd. De controlebits worden altijd geïnjecteerd op een positie die een macht van twee is, dus een willekeurig aantal bits kan worden geverifieerd door extra pariteitsbits op te nemen. Dit kan doorgaan totdat het laatste pariteitsbit dat is toegevoegd in de reeks zich in een positie bevindt die een macht van twee is die kleiner is dan of gelijk is aan de uiteindelijke positie in de reeks.
Met alle pariteitsbits op hun plaats, zijn de resterende posities de feitelijke databits. Gegeven het voorbeeld van vier bits, dan zouden bitposities één, twee en vier de pariteitsbits zijn, terwijl posities drie, vijf, zes en zeven de gegevens zijn. Zodra deze volgorde is vastgesteld, werkt de logica van de Hamming-code.
In een Hamming-code worden alle pariteitsbits die aan de reeks zijn toegevoegd, gebruikt om enkele bitposities te controleren waar ze zich in de buurt van bevinden, inclusief zichzelf. De pariteitsbit in positie één controleert elke andere bitpositie, die in wezen elke oneven genummerde positie in de reeks is. Het tweede pariteitsbit, in positie twee, controleert positie twee en drie, slaat dan twee posities over, controleert twee meer posities, slaat twee meer over, enzovoort. Als er een pariteitsbit in positie vier is, werkt het op dezelfde manier doordat het posities vier tot en met zeven controleert, vervolgens vier posities overslaat, vier meer controleert en verder. Elk pariteitsbit in de reeks gaat op deze manier door de hele reeks.
Het proces waarbij een Hamming-code een fout detecteert en corrigeert, is door de bits in de controlesequentie op te tellen voor elke pariteitscontrole, die elk uit een even getal moeten komen. Gegeven het zeven-bit voorbeeld, voor de eerste pariteitscontrole, worden bits één, drie, vijf en zeven opgeteld. Als het totaal een even getal is, wordt de pariteit uitgecheckt, maar als het totaal oneven is, is er een fout. Omdat de pariteitscontroles elkaar overlappen, zullen twee van dergelijke fouten verschijnen. Wanneer de twee-pariteitsbitposities die geen totalen opleveren, bij elkaar worden opgeteld, onthult het de bit die moet worden gecorrigeerd.
Overweeg in het zeven-bits Hamming-codevoorbeeld dat het bit op positie nummer vijf onjuist is. De som van de bits in positie één, drie, vijf en zeven zal uitkomen als een oneven getal, evenals de som van de bits in positie vier tot en met zeven. Dit geeft aan dat pariteitscontroles voor de controlebits op positie één en vier zijn mislukt. Wanneer één en vier bij elkaar worden opgeteld, is het totaal vijf, wat de positie is voor het onjuiste bit in de transmissie dat moet worden gecorrigeerd.