Vendte bit
Syndrom
Modtaget
Databit pr. sendt bit

Mere om fejlkorrigerende koder

Simulator til fejlkorrigerende koder

Enhver besked, der rejser gennem en ledning, luften eller en ridset disk, får fejl med på vejen: bit skifter fra 0 til 1 og tilbage. En fejlkorrigerende kode tilføjer nogle få omhyggeligt valgte ekstra bit, så modtageren kan finde og reparere skaden uden at spørge igen. Skriv fire databit, se Richard Hammings kode gøre dem til syv, vend en hvilken som helst bit, og se tre overlappende cirkler pege direkte på fejlen. Send derefter en hel besked gennem en støjfyldt kanal, og sammenlign, hvad der kommer frem med og uden koden. Skriv fire databit, fx 1011, og appen tilføjer tre paritetsbit, så der dannes et Hamming-kodeord på 7 bit. Klik på en bit, i cirklerne eller i rækken, for at vende den, som støj ville gøre; klik igen for at vende den tilbage. Hver cirkel skal indeholde et lige antal 1-taller: de cirkler, der ikke stemmer, peger på den forkerte bit, og dekoderen vender den tilbage. Slå den ekstra paritetsbit til for at se to fejl blive opdaget i stedet for rettet forkert. Send nedenfor en tekst gennem en støjfyldt kanal med og uden koden.

Sådan virker det

  1. Skriv fire databit, og se kodeordet på syv bit med dets tre paritetsbit, i cirkler og på en række.
  2. Klik på bit for at vende dem, og se, hvilke cirkler der ikke stemmer, hvor syndromet peger hen, og om dekoderen reparerer ordet.
  3. Slå den ekstra paritetsbit til, send så en besked gennem den støjfyldte kanal, og sammenlign resultaterne med og uden koden.

Sådan finder Hamming-koden en fejl

De syv bit er nummereret fra 1 til 7. Bit 1, 2 og 4 er paritetsbit, og de fire databit sidder på 3, 5, 6 og 7. Paritetsbit 1 gør antallet af 1-taller lige blandt position 1, 3, 5 og 7, de positioner, hvis nummer i binær form ender på 1; bit 2 gør det samme for 2, 3, 6 og 7, og bit 4 for 4, 5, 6 og 7. Tegnet som tre overlappende cirkler sidder hver bit i præcis de cirkler, der kontrollerer den. Når én bit vendes, bliver de cirkler, der indeholder den, ulige. Læs de kontroller, der ikke stemmer, som et binært tal, syndromet, og du får positionen af den forkerte bit.

Hvad én ekstra bit giver

Med to vendte bit peger syndromet på en tredje, uskyldig bit, og dekoderen gør det hele værre. En ottende bit, der gør hele ordet lige, løser det: én fejl ændrer den samlede paritet, to fejl lader den forblive lige, mens nogle cirkler ikke stemmer. Den udvidede kode, kendt som SECDED (rettelse af enkeltfejl, opdagelse af dobbeltfejl), retter én fejl og opdager pålideligt to, så modtageren kan bede om den blok igen. Det er koden, der bruges i serveres ECC-hukommelse. Over en støjfyldt kanal gør koden mange spredte fejl til få, så længe to vendte bit sjældent lander i samme blok.

Ofte stillede spørgsmål

Hvorfor sidder paritetsbittene på position 1, 2 og 4?

Fordi det er potenserne af to, og hver af dem har et enkelt 1-tal i binær form. Paritetsbit 2ᵏ kontrollerer hver position, hvis binære tal har et 1-tal på plads k. En vendt bit på position 6 = 110 binært bryder kontrollerne for 2 og 4 og lader 1 være, og de kontroller, der ikke stemmer, staver 110, selve positionen.

Hvad koster beskyttelsen?

(7,4)-koden sender 7 bit for hver 4 databit, en rate på 4/7: 75 % ekstra. Den udvidede kode sender 8 for 4, det dobbelte. Længere Hamming-koder er billigere: 15 bit bærer 11 databit, 31 bærer 26. Moderne koder som LDPC- og polarkoder, der bruges i wi-fi og 5G, kommer meget tæt på den bedste rate, som Claude Shannon i 1948 beviste var mulig.

Hvad sker der med tre fejl?

Den almindelige Hamming-kode kan narres fuldstændigt: to kodeord adskiller sig altid i mindst tre bit, så tre vendte bit kan gøre ét gyldigt kodeord til et andet, og ingen kontrol fejler overhovedet. Appen melder dette som »Fejl ikke opdaget«. Rigtige systemer holder sådanne tilfælde sjældne ved at vælge en kode, der er stærk nok til støjniveauet.

Hvor bruges fejlkorrigerende koder?

Næsten overalt, hvor digitale data sendes eller lagres: ECC-computerhukommelse, harddiske og SSD'er, cd'er, dvd'er og Blu-ray-diske, QR-koder, der stadig kan læses, selv om et stykke er revet af, mobiltelefoner og wi-fi, digitalt tv og beskeder fra rumsonder som Voyager, der stadig sender data fra et sted uden for solsystemet.

Bliver min besked sendt nogen steder hen?

Nej. Den støjfyldte kanal simuleres i din browser, og din besked og dine indstillinger bliver i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor