Wat is Hamming-code?
De bekendste foutcorrigerende code die fouten van 1 bit corrigeert. Met r controlebits is een codewoord 2^r − 1 bits lang, waarvan 2^r − 1 − r bits gegevens dragen. De Hamming-code (7, 4), met r = 3, voegt 3 controlebits toe aan 4 bits gegevens. Elke controlebit is de pariteit van een overlappende groep bits, en het resultaat van het opnieuw uitvoeren van de controles bij de ontvanger (het syndroom) geeft de positie van de foute bit als binair getal. De minimale Hamming-afstand is 3, en SECDED, dat 1 bit totale pariteit toevoegt, kan ook fouten van 2 bits detecteren. Ze wordt bijvoorbeeld gebruikt voor ECC in servergeheugen.
Japanse benaming: ハミング符号
“Hamming-code” komt voor in 5 oefenvragen uit 2 onderwerpen, bijv. Basis van informatietheorie en codering, Logische schakelingen.
Vakgebied: Basis van informatietheorie en codering
Hoe de (7, 4)-code werkt
De bitposities worden genummerd van 1 tot 7, en de posities die machten van 2 zijn, 1, 2 en 4, zijn de controlebits. Controle 1 maakt het aantal enen even over de posities waarvan het nummer binair geschreven een 1 op de plaats van de eenheden heeft (1, 3, 5, 7), controle 2 over die met een 1 op de plaats van de tweeën (2, 3, 6, 7), en controle 4 over die met een 1 op de plaats van de vieren (4, 5, 6, 7). Alleen de controles die horen bij de binaire cijfers die 1 zijn in het nummer van de foute positie, falen, dus het optellen van de gewichten van de falende controles geeft de foute positie.
Coderatio en lengte
Met r controlebits is het codewoord 2^r − 1 bits lang, en hoe langer de code, zoals bij (7, 4), (15, 11) en (31, 26), hoe hoger de coderatio: 4/7 ≈ 0,57, 11/15 ≈ 0,73 en 26/31 ≈ 0,84. Daar staat tegenover dat één codewoord slechts 1 bit kan corrigeren, dus hoe langer het codewoord, hoe groter de kans dat het een fout van 2 of meer bits krijgt.
Veelgestelde vragen
Wat gebeurt er met een Hamming-code als er een fout van 2 bits optreedt?
In een Hamming-code zonder totale pariteit wijst het syndroom bij een fout van 2 bits toch naar een positie die niet nul is, zodat een correcte bit wordt omgeslagen en de fout groeit tot 3 bits. Om dat te voorkomen gebruiken geheugens en vergelijkbare componenten SECDED, dat totale pariteit toevoegt, en melden ze een fout van 2 bits als fout in plaats van haar te corrigeren.
Worden Hamming-codes vandaag nog gebruikt?
Ja. Ze zijn eenvoudig en snel te berekenen, dus ze worden veel gebruikt waar de vertraging klein moet blijven, zoals ECC voor geheugen en de bescherming van caches en registers. Waar veel fouten efficiënt moeten worden gecorrigeerd, zoals in communicatie, worden krachtigere codes zoals LDPC-codes gebruikt.