Hamming code

Hamming code is een set van error-correctie code s die kunnen worden gebruikt om bitfouten op te sporen en te corrigeren die kunnen optreden wanneer computergegevens worden verplaatst of opgeslagen. Hamming code is genoemd naar R. W. Hamming van Bell Labs.

Net als andere foutcorrectiecodes maakt Hamming code gebruik van het concept van pariteit en pariteitsbits, dat zijn bits die aan gegevens worden toegevoegd zodat de geldigheid van de gegevens kan worden gecontroleerd wanneer ze worden gelezen of nadat ze zijn ontvangen in een datatransmissie. Door meer dan één pariteitsbit te gebruiken, kan een foutcorrectiecode niet alleen een enkele bitfout in de data-eenheid identificeren, maar ook de plaats ervan in de data-eenheid.

In de datatransmissie wordt het vermogen van een ontvangststation om fouten in de ontvangen gegevens te corrigeren forward error correction (FEC) genoemd en kan het de doorvoer op een dataverbinding verhogen wanneer er veel ruis aanwezig is. Om dit mogelijk te maken, moet een zendstation extra gegevens (de zogenaamde error correction bits ) aan de transmissie toevoegen. De correctie betekent echter niet altijd een kostenbesparing ten opzichte van het eenvoudig opnieuw verzenden van de informatie. Hamming-codes maken de implementatie van FEC minder duur door het gebruik van een block parity-mechanisme.

Het berekenen van de pariteit houdt in dat het aantal enen in een gegevenseenheid wordt geteld, en dat een nul of een één (een parity bit ) wordt toegevoegd om de telling oneven (voor oneven pariteit) of even (voor even pariteit) te maken. Bijvoorbeeld, 1001 is een 4-bit data-eenheid die twee één bits bevat; aangezien dat een even getal is, zou een nul worden toegevoegd om de even pariteit te handhaven, of, als oneven pariteit werd gehandhaafd, zou nog een één worden toegevoegd. Om de even pariteit te berekenen wordt de XOR operator gebruikt; om de oneven pariteit te berekenen wordt de XNOR operator gebruikt. Enkelvoudige bit-fouten worden gedetecteerd wanneer de pariteitstelling aangeeft dat het aantal enen onjuist is, wat erop wijst dat een gegevensbit door ruis in de lijn is omgedraaid. Hamming-codes detecteren tweebitsfouten door meer dan één pariteitsbit te gebruiken, die elk worden berekend op verschillende combinaties van bits in de gegevens. Het aantal vereiste pariteitsbits hangt af van het aantal bits in de gegevenstransmissie, en wordt berekend met de Hamming-regel:

p
d + p + 1 < = 2 (1)

Waar d het aantal databits is en p het aantal pariteitsbits. Het totaal van de twee wordt het Hamming codewoord genoemd, dat wordt gegenereerd door de gegevensbits te vermenigvuldigen met een generatormatrix.