Symulator kodów korekcyjnych
Każda wiadomość, która podróżuje przewodem, powietrzem lub z porysowanej płyty, zbiera po drodze błędy: bity zmieniają się z 0 na 1 i z powrotem. Kod korekcyjny dodaje kilka starannie dobranych dodatkowych bitów, aby odbiorca mógł znaleźć i naprawić uszkodzenie bez ponownego pytania. Wpisz cztery bity danych, zobacz, jak kod Richarda Hamminga zamienia je w siedem, odwróć dowolny bit i obserwuj, jak trzy nakładające się koła wskazują prosto na błąd. Potem wyślij całą wiadomość przez zaszumiony kanał i porównaj, co dociera z kodem i bez niego. Wpisz cztery bity danych, na przykład 1011, a aplikacja doda trzy bity parzystości, tworząc 7-bitowe słowo kodowe Hamminga. Kliknij dowolny bit, w kołach lub w wierszu, aby go odwrócić, tak jak zrobiłby to szum; kliknij ponownie, aby odwrócić go z powrotem. Każde koło musi zawierać parzystą liczbę jedynek: koła, które się nie zgadzają, wskazują błędny bit, a dekoder odwraca go z powrotem. Włącz dodatkowy bit parzystości, aby zobaczyć, że dwa błędy zostają wykryte, a nie błędnie poprawione. Poniżej wyślij tekst przez zaszumiony kanał z kodem i bez niego.
Jak to działa
- Wpisz cztery bity danych i zobacz siedmiobitowe słowo kodowe z trzema bitami parzystości, w kołach i w wierszu.
- Klikaj bity, aby je odwracać, i obserwuj, które koła się nie zgadzają, na co wskazuje syndrom i czy dekoder naprawia słowo.
- Włącz dodatkowy bit parzystości, a potem wyślij wiadomość przez zaszumiony kanał i porównaj wyniki z kodem i bez niego.
Jak kod Hamminga znajduje błąd
Siedem bitów ma numery od 1 do 7. Bity 1, 2 i 4 są bitami parzystości, a cztery bity danych stoją na pozycjach 3, 5, 6 i 7. Bit parzystości 1 sprawia, że liczba jedynek na pozycjach 1, 3, 5 i 7 jest parzysta – to pozycje, których numer w zapisie dwójkowym kończy się na 1; bit 2 robi to samo dla 2, 3, 6 i 7, a bit 4 dla 4, 5, 6 i 7. Na rysunku z trzema nakładającymi się kołami każdy bit leży dokładnie w tych kołach, które go sprawdzają. Gdy jeden bit się odwróci, koła, które go zawierają, stają się nieparzyste. Odczytaj niezgodne kontrole jako liczbę dwójkową, syndrom, a otrzymasz pozycję błędnego bitu.
Co daje jeden dodatkowy bit
Przy dwóch odwróconych bitach syndrom wskazuje trzeci, niewinny bit, a dekoder tylko pogarsza sprawę. Rozwiązuje to ósmy bit, który czyni parzystym całe słowo: jeden błąd zmienia parzystość całości, dwa błędy pozostawiają ją parzystą, choć niektóre koła się nie zgadzają. Kod rozszerzony, znany jako SECDED (korekcja pojedynczych błędów, wykrywanie podwójnych), poprawia jeden błąd i niezawodnie wykrywa dwa, więc odbiorca może poprosić o ten blok ponownie. To właśnie ten kod działa w pamięci ECC serwerów. W zaszumionym kanale kod zamienia wiele rozproszonych błędów w kilka, o ile dwa odwrócenia rzadko trafiają do tego samego bloku.
Często zadawane pytania
Dlaczego bity parzystości są na pozycjach 1, 2 i 4?
Bo to potęgi dwójki, a każda z nich ma w zapisie dwójkowym jedną jedynkę. Bit parzystości 2ᵏ sprawdza każdą pozycję, której numer dwójkowy ma 1 na miejscu k. Odwrócony bit na pozycji 6 = 110 dwójkowo psuje kontrole bitów 2 i 4, a 1 zostawia w spokoju, i niezgodne kontrole układają się w 110, czyli samą pozycję.
Ile kosztuje ta ochrona?
Kod (7,4) wysyła 7 bitów na każde 4 bity danych, co daje sprawność 4/7: 75% więcej. Kod rozszerzony wysyła 8 na 4, czyli dwa razy więcej. Dłuższe kody Hamminga są tańsze: 15 bitów niesie 11 bitów danych, 31 niesie 26. Nowoczesne kody, takie jak LDPC i kody polarne, stosowane w Wi-Fi i 5G, bardzo zbliżają się do najlepszej sprawności, której osiągalność Claude Shannon udowodnił w 1948 roku.
Co się dzieje przy trzech błędach?
Zwykły kod Hamminga można całkowicie oszukać: dowolne dwa słowa kodowe różnią się co najmniej trzema bitami, więc trzy odwrócenia mogą zamienić jedno poprawne słowo kodowe w inne i żadna kontrola nie wykaże niezgodności. Aplikacja pokazuje wtedy „Błąd niezauważony”. Prawdziwe systemy sprawiają, że takie przypadki są rzadkie, dobierając kod wystarczająco silny do poziomu szumu.
Gdzie stosuje się kody korekcyjne?
Niemal wszędzie, gdzie dane cyfrowe są przesyłane lub przechowywane: w pamięci komputerowej ECC, dyskach twardych i SSD, płytach CD, DVD i Blu-ray, kodach QR, które pozostają czytelne nawet z oderwanym fragmentem, telefonach komórkowych i Wi-Fi, telewizji cyfrowej oraz wiadomościach z sond kosmicznych, takich jak Voyager, które wciąż przesyłają dane spoza Układu Słonecznego.
Czy moja wiadomość jest gdzieś wysyłana?
Nie. Zaszumiony kanał jest symulowany w twojej przeglądarce, a twoja wiadomość i ustawienia zostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora