Omgedraaide bits
Syndroom
Ontvangen
Databits per verzonden bit

Meer over foutcorrigerende codes

Simulator voor foutcorrigerende codes

Elk bericht dat door een draad, de lucht of een bekraste schijf reist, loopt fouten op: bits springen van 0 naar 1 en terug. Een foutcorrigerende code voegt een paar zorgvuldig gekozen extra bits toe, zodat de ontvanger de schade kan vinden en herstellen zonder opnieuw te vragen. Typ vier databits, zie hoe de code van Richard Hamming er zeven van maakt, draai elk bit om dat je wilt en zie hoe drie overlappende cirkels de fout rechtstreeks aanwijzen. Stuur daarna een heel bericht door een kanaal met ruis en vergelijk wat er aankomt met en zonder de code. Typ vier databits, bijvoorbeeld 1011, en de app voegt drie pariteitsbits toe tot een Hammingcodewoord van 7 bits. Klik op een bit, in de cirkels of in de rij, om het om te draaien zoals ruis zou doen; klik nog eens om het terug te draaien. Elke cirkel moet een even aantal enen bevatten: de cirkels die niet kloppen wijzen het foute bit aan, en de decoder draait het terug. Zet het extra pariteitsbit aan om te zien dat twee fouten worden gedetecteerd in plaats van verkeerd gecorrigeerd. Stuur daaronder een tekst door een kanaal met ruis, met en zonder de code.

Hoe het werkt

  1. Typ vier databits en bekijk het codewoord van zeven bits met zijn drie pariteitsbits, in cirkels en in een rij.
  2. Klik op bits om ze om te draaien en zie welke cirkels niet kloppen, waar het syndroom naar wijst en of de decoder het woord herstelt.
  3. Zet het extra pariteitsbit aan, stuur dan een bericht door het kanaal met ruis en vergelijk de resultaten met en zonder de code.

Hoe de Hammingcode een fout vindt

De zeven bits zijn genummerd van 1 tot 7. De bits 1, 2 en 4 zijn pariteitsbits, en de vier databits staan op 3, 5, 6 en 7. Pariteitsbit 1 maakt het aantal enen even op de posities 1, 3, 5 en 7, de posities waarvan het nummer in binaire vorm op 1 eindigt; bit 2 doet hetzelfde voor 2, 3, 6 en 7, en bit 4 voor 4, 5, 6 en 7. Getekend als drie overlappende cirkels staat elk bit in precies de cirkels die het controleren. Als één bit omdraait, worden de cirkels waarin het staat oneven. Lees de controles die niet kloppen als een binair getal, het syndroom, en je krijgt de positie van het foute bit.

Wat één extra bit oplevert

Met twee omgedraaide bits wijst het syndroom naar een derde, onschuldig bit, en maakt de decoder het erger. Een achtste bit dat het hele woord even maakt, lost dat op: één fout verandert de totale pariteit, twee fouten laten die even terwijl sommige cirkels niet kloppen. De uitgebreide code, bekend als SECDED (enkele fouten corrigeren, dubbele fouten detecteren), corrigeert één fout en detecteert twee fouten betrouwbaar, zodat de ontvanger dat blok opnieuw kan opvragen. Het is de code die in het ECC-geheugen van servers wordt gebruikt. Over een kanaal met ruis maakt de code van veel verspreide fouten er een paar, zolang twee omgedraaide bits zelden in hetzelfde blok terechtkomen.

Veelgestelde vragen

Waarom staan de pariteitsbits op de posities 1, 2 en 4?

Omdat dat de machten van twee zijn, en elk ervan heeft binair één enkele 1. Pariteitsbit 2ᵏ controleert elke positie waarvan het binaire getal een 1 heeft op plaats k. Een omgedraaid bit op positie 6 = 110 binair breekt de controles van 2 en 4 en laat 1 met rust, en de controles die niet kloppen spellen 110, de positie zelf.

Wat kost de bescherming?

De (7,4)-code verstuurt 7 bits voor elke 4 databits, een verhouding van 4/7: 75% extra. De uitgebreide code verstuurt er 8 voor 4, het dubbele. Langere Hammingcodes zijn goedkoper: 15 bits dragen 11 databits, 31 dragen er 26. Moderne codes zoals LDPC- en polaire codes, die in wifi en 5G worden gebruikt, komen heel dicht bij de beste verhouding waarvan Claude Shannon in 1948 bewees dat die mogelijk is.

Wat gebeurt er bij drie fouten?

De gewone Hammingcode kan volledig om de tuin worden geleid: twee codewoorden verschillen altijd in minstens drie bits, dus drie omgedraaide bits kunnen het ene geldige codewoord in een ander veranderen, en geen enkele controle faalt. De app meldt dit als ‘Fout niet opgemerkt’. Echte systemen houden zulke gevallen zeldzaam door een code te kiezen die sterk genoeg is voor het ruisniveau.

Waar worden foutcorrigerende codes gebruikt?

Bijna overal waar digitale gegevens reizen of worden opgeslagen: ECC-computergeheugen, harde schijven en ssd's, cd's, dvd's en blu-raydiscs, QR-codes, die leesbaar blijven als er een stuk af is gescheurd, mobiele telefoons en wifi, digitale televisie en berichten van ruimtesondes zoals Voyager, die nog steeds gegevens sturen van buiten het zonnestelsel.

Wordt mijn bericht ergens naartoe gestuurd?

Nee. Het kanaal met ruis wordt in je browser gesimuleerd, en je bericht en instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor