Foutdetectie en -correctie

In de informatietheorie en codeertheorie zijn foutdetectie en -correctie of foutcontrole technieken die een betrouwbare levering van digitale gegevens via onbetrouwbare communicatiekanalen mogelijk maken. Veel communicatiekanalen zijn onderhevig aan kanaalruis en daarom kunnen er fouten worden geïntroduceerd tijdens de verzending van de bron naar een ontvanger. Met technieken voor foutdetectie kunnen dergelijke fouten worden gedetecteerd, terwijl foutcorrectie in veel gevallen de reconstructie van de oorspronkelijke gegevens mogelijk maakt.

Foutdetectie

is het detecteren van fouten veroorzaakt door ruis of andere storingsbronnen tijdens de transmissie van de zender naar de ontvanger.

Foutcorrectie

is het detecteren van fouten en het reconstrueren van de originele, foutloze gegevens.

Alle foutdetectie- en correctieschema's voegen wat redundantie (extra gegevens) toe aan een bericht, die ontvangers kunnen gebruiken om de consistentie van het afgeleverde bericht te controleren en om gegevens te herstellen waarvan is vastgesteld dat ze beschadigd zijn. Foutdetectie- en correctieschema's kunnen zowel systematisch als niet-systematisch zijn. In een systematisch schema verzendt de zender de originele gegevens en voegt een vast aantal controlebits (of pariteitsgegevens) toe, die door een deterministisch algoritme uit de gegevensbits worden afgeleid. Als alleen foutdetectie nodig is, kan een ontvanger eenvoudig hetzelfde algoritme toepassen op de ontvangen databits en de uitvoer ervan vergelijken met de ontvangen controlebits; als de waarden niet overeenkomen, is er ergens tijdens de verzending een fout opgetreden. In een systeem dat een niet-systematische code gebruikt, wordt het oorspronkelijke bericht omgezet in een gecodeerd bericht met dezelfde informatie en dat minstens evenveel bits heeft als het oorspronkelijke bericht.

Goede foutcontroleprestaties vereisen dat het schema en algoritme worden geselecteerd op basis van de kenmerken van het communicatiekanaal. Gangbare kanalen omvatten geheugenloze modellen waarbij fouten willekeurig en met een bepaalde waarschijnlijkheid optreden, en dynamische modellen waarbij fouten voornamelijk in bursts optreden. Daardoor kunnen foutdetecterende en corrigerende schemas en algoritmes in het algemeen worden onderscheiden tussen willekeurige foutdetectie/correctie en burst-foutdetectie/correctie. Sommige codes kunnen ook geschikt zijn voor een combinatie van willekeurige fouten en burst-fouten.

Als de kanaalkarakteristieken niet kunnen worden vastgesteld of zeer variabel zijn, kan een foutdetectieschema worden gecombineerd met een systeem voor hertransmissie van foutieve gegevens. Dit staat bekend als automatisch herhaalverzoek (ARQ) en wordt vooral op internet gebruikt.

Zie ook

• ECC-geheugen, een soort werkgeheugen met foutcorrectie
• Pariteitscontrole met pariteitsbits als methode om fouten te detecteren.
• Cyclic redundancy check, een foutdetectiecode die dikwijls gebruikt wordt in digitale netwerken en opslagmedia