Simulator för felrättande koder
Varje meddelande som färdas genom en tråd, luften eller en repig skiva får fel på vägen: bitar slår om från 0 till 1 och tillbaka. En felrättande kod lägger till några noggrant valda extra bitar så att mottagaren kan hitta och reparera skadan utan att fråga igen. Skriv fyra databitar, se Richard Hammings kod göra dem till sju, vänd vilken bit du vill och se tre överlappande cirklar peka rakt på felet. Skicka sedan ett helt meddelande genom en brusig kanal och jämför vad som kommer fram med och utan koden. Skriv fyra databitar, till exempel 1011, så lägger appen till tre paritetsbitar och bildar ett Hammingkodord på 7 bitar. Klicka på en bit, i cirklarna eller i raden, för att vända den som brus skulle göra; klicka igen för att vända tillbaka den. Varje cirkel måste innehålla ett jämnt antal ettor: cirklarna som inte stämmer pekar ut den felaktiga biten, och avkodaren vänder tillbaka den. Slå på den extra paritetsbiten för att se två fel upptäckas i stället för att felaktigt rättas. Skicka längre ner en text genom en brusig kanal med och utan koden.
Hur det fungerar
- Skriv fyra databitar och se kodordet på sju bitar med sina tre paritetsbitar, i cirklar och på en rad.
- Klicka på bitar för att vända dem och se vilka cirklar som inte stämmer, vart syndromet pekar och om avkodaren reparerar ordet.
- Slå på den extra paritetsbiten, skicka sedan ett meddelande genom den brusiga kanalen och jämför resultaten med och utan koden.
Hur Hammingkoden hittar ett fel
De sju bitarna är numrerade från 1 till 7. Bitarna 1, 2 och 4 är paritetsbitar, och de fyra databitarna sitter på 3, 5, 6 och 7. Paritetsbit 1 gör antalet ettor jämnt bland positionerna 1, 3, 5 och 7, de positioner vars nummer slutar på 1 i binär form; bit 2 gör samma sak för 2, 3, 6 och 7, och bit 4 för 4, 5, 6 och 7. Ritade som tre överlappande cirklar ligger varje bit i exakt de cirklar som kontrollerar den. När en bit vänds blir cirklarna som innehåller den udda. Läs kontrollerna som inte stämmer som ett binärt tal, syndromet, så får du positionen för den felaktiga biten.
Vad en extra bit ger
Med två vända bitar pekar syndromet på en tredje, oskyldig bit, och avkodaren gör saken värre. En åttonde bit som gör hela ordet jämnt löser det: ett fel ändrar den totala pariteten, två fel lämnar den jämn medan vissa cirklar inte stämmer. Den utökade koden, känd som SECDED (rättning av enkelfel, upptäckt av dubbelfel), rättar ett fel och upptäcker två på ett pålitligt sätt, så att mottagaren kan begära det blocket igen. Det är koden som används i ECC-minnet i servrar. Över en brusig kanal gör koden många spridda fel till några få, så länge två vända bitar sällan hamnar i samma block.
Ofta ställda frågor
Varför sitter paritetsbitarna på positionerna 1, 2 och 4?
Eftersom det är tvåpotenserna, och var och en har en enda etta i binär form. Paritetsbit 2ᵏ kontrollerar varje position vars binära tal har en etta på plats k. En vänd bit på position 6 = 110 binärt bryter kontrollerna för 2 och 4 och lämnar 1 i fred, och kontrollerna som inte stämmer stavar 110, själva positionen.
Vad kostar skyddet?
(7,4)-koden skickar 7 bitar för varje 4 databitar, en kodtakt på 4/7: 75 % extra. Den utökade koden skickar 8 för 4, det dubbla. Längre Hammingkoder är billigare: 15 bitar bär 11 databitar, 31 bär 26. Moderna koder som LDPC- och polära koder, som används i wifi och 5G, kommer mycket nära den bästa takt som Claude Shannon 1948 bevisade var möjlig.
Vad händer vid tre fel?
Den vanliga Hammingkoden kan luras helt: två kodord skiljer sig alltid i minst tre bitar, så tre vända bitar kan förvandla ett giltigt kodord till ett annat, och inte en enda kontroll misslyckas. Appen visar detta som ”Fel inte upptäckt”. Verkliga system håller sådana fall sällsynta genom att välja en kod som är tillräckligt stark för brusnivån.
Var används felrättande koder?
Nästan överallt där digitala data färdas eller lagras: ECC-datorminnen, hårddiskar och SSD:er, cd-, dvd- och Blu-ray-skivor, QR-koder, som förblir läsbara även när en del har rivits av, mobiltelefoner och wifi, digital-tv och meddelanden från rymdsonder som Voyager, som fortfarande skickar data från bortom solsystemet.
Skickas mitt meddelande någonstans?
Nej. Den brusiga kanalen simuleras i din webbläsare, och ditt meddelande och dina inställningar stannar i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor