Kody korekcyjne wyjaśnione

Żaden kanał nie jest doskonały. Promieniowanie kosmiczne odwraca bity w pamięci, rysy wymazują fragmenty płyty, a sygnały radiowe zanikają. Zamiast liczyć na szczęście, systemy cyfrowe w sprytny sposób dodają nadmiarowość, aby odbiorca mógł ustalić, co zostało wysłane, nawet jeśli część dotarła błędnie. Matematyka tych kodów, zapoczątkowana pod koniec lat 40. XX wieku, po cichu chroni niemal każdy bit, który przechowujemy lub wysyłamy.

Trzy nakładające się koła z siedmioma bitami słowa kodowego Hamminga, z jednym kołem wyróżnionym tam, gdzie kontrola parzystości się nie zgadza
Trzy nakładające się koła z siedmioma bitami słowa kodowego Hamminga, z jednym kołem wyróżnionym tam, gdzie kontrola parzystości się nie zgadza

Wykrywanie błędów za pomocą parzystości

Najprostszą ochroną jest pojedynczy bit parzystości: dodaj 1 lub 0 tak, aby łączna liczba jedynek była parzysta. Jeśli po drodze jeden bit się odwróci, liczba staje się nieparzysta i odbiorca wie, że coś poszło nie tak. Parzystość nie powie, który bit jest błędny, a dwa odwrócenia znoszą się niezauważenie, ale jest tania i przez dziesięciolecia stosowano ją w pamięciach i łączach szeregowych. Wykrycie błędu to jednak tylko połowa pracy: potem dane trzeba wysłać ponownie.

Korekcja przez powtarzanie

Aby poprawić błąd bez ponownego pytania, odbiorca potrzebuje dość nadmiarowości, by go przegłosować. Wysyłanie każdego bitu trzy razy, 000 lub 111, pozwala odbiorcy wybrać większość: jedno odwrócenie w trójce zostaje poprawione. Cena jest wysoka: trzy bity na każdy bit danych, a dwa odwrócenia w tej samej trójce nadal wygrywają. Pytanie, od którego zaczęła się teoria kodowania, brzmiało: czy da się to zrobić lepiej?

Kod Hamminga

W 1947 roku Richard Hamming pracował w Bell Labs przy komputerze przekaźnikowym, który czytał programy z kart perforowanych. Gdy w weekend wykrył błąd, po prostu się zatrzymywał, a Hamming wracał w poniedziałek do zmarnowanych obliczeń. Skoro maszyna potrafi wykryć błąd, pytał, to dlaczego nie potrafi go zlokalizować i poprawić? Jego odpowiedź, opublikowana w 1950 roku, wysyła 4 bity danych jako 7. Trzy bity parzystości, na pozycjach 1, 2 i 4, sprawdzają każdy inną, nakładającą się grupę pozycji, dobraną tak, aby każdy pojedynczy błąd psuł unikalną kombinację kontroli.

Syndrom

Odbiorca ponownie oblicza trzy kontrole. Jeśli wszystkie się zgadzają, słowo zostaje przyjęte. Jeśli niektóre się nie zgadzają, zapisanie niezgodnych kontroli jako cyfr dwójkowych, z kontrolą 4 jako najwyższą cyfrą, daje liczbę od 1 do 7: syndrom, który jest dokładnie pozycją odwróconego bitu. Odwrócenie go z powrotem przywraca słowo kodowe. Sztuczka działa, bo pozycje są ponumerowane tak, że zapis dwójkowy każdej z nich wymienia kontrole, do których należy, i dlatego kod wygląda tak schludnie, gdy narysuje się go jako trzy nakładające się koła.

Odległość Hamminga

Odległość Hamminga między dwoma słowami to liczba pozycji, na których się różnią. W kodzie (7,4) dowolne dwa słowa kodowe dzieli co najmniej 3. Słowo z jednym błędem jest nadal w odległości 1 od wysłanego słowa kodowego i co najmniej 2 od każdego innego, więc dekodowanie do najbliższego słowa kodowego je poprawia. Ogólnie kod, którego słowa kodowe dzieli co najmniej d, wykrywa d − 1 błędów i poprawia (d − 1)/2 z nich, w zaokrągleniu w dół. Dodanie bitu parzystości całego słowa zwiększa odległość do 4, dając kod rozszerzony, który poprawia jeden błąd i wykrywa dwa.

Granica Shannona

W 1948 roku, dwa lata przed pracą Hamminga, Claude Shannon udowodnił zdumiewające twierdzenie. Każdy kanał z szumem ma przepustowość, a dane można przesyłać z dowolną szybkością poniżej niej z tak małą liczbą błędów, jak się chce, używając dostatecznie długich kodów; powyżej niej błędów nie da się uniknąć. Shannon pokazał, że takie kody istnieją, ale nie jak je zbudować. Znalezienie praktycznych kodów zbliżających się do jego granicy zajęło pół wieku: od kodów Reeda-Solomona w 1960 roku, przez kody turbo w 1993 roku, po ponowne odkrycie kodów LDPC (low-density parity-check).

Claude Shannon, który w 1948 w Bell Labs precyzyjnie określił, ile informacji zawiera komunikat, i mierzył ją w bitach.
Claude Shannon, który w 1948 w Bell Labs precyzyjnie określił, ile informacji zawiera komunikat, i mierzył ją w bitach.

Kody wokół nas

Dzięki kodom Reeda-Solomona płyty CD grają mimo rys, a kody QR dają się zeskanować nawet przy uszkodzeniu do 30% symbolu. Pamięć serwerów korzysta z rozszerzonych kodów Hamminga, aby naprawiać pojedyncze bity odwrócone przez promieniowanie kosmiczne. Zdjęcia planet zewnętrznych wykonane przez Voyagera chroniły kody Golaya, a później kody Reeda-Solomona, a kody LDPC i polarne w 5G i Wi-Fi wyciskają niemal każdy bit, na jaki pozwala kanał. Nawet kod kreskowy na książce i ostatnia cyfra numeru konta bankowego to proste kody wykrywające błędy.

Wypróbuj to

Otwórz symulator kodów korekcyjnych, aby zakodować dowolne cztery bity danych kodem Hamminga (7,4), odwracać bity, klikając je w kołach lub w wierszu, i obserwować, jak niezgodne koła i syndrom wskazują błąd, zanim dekoder go naprawi. Włącz dodatkowy bit parzystości, aby zobaczyć wykrywanie podwójnych błędów, i wyślij wiadomość przez zaszumiony kanał, aby porównać, co dociera z kodem i bez niego.

Często zadawane pytania

Czym różni się wykrywanie błędów od ich korekcji?

Wykrywanie mówi odbiorcy tylko, że coś jest nie tak, więc musi on poprosić o dane ponownie; robi to bit parzystości lub suma kontrolna. Korekcja pozwala odbiorcy odtworzyć oryginał bez pytania, co wymaga większej nadmiarowości. Systemy, które nie mogą poprosić ponownie, takie jak sonda kosmiczna oddalona o miliony kilometrów czy płyta DVD, polegają na korekcji.

Dlaczego po prostu nie wysłać wszystkiego dwa razy?

Dwie kopie pokazują, że wystąpił błąd, ale nie to, która kopia jest poprawna, a przy tym podwajają koszt. Trzy kopie umożliwiają głosowanie większościowe, ale go potrajają. Kod Hamminga poprawia pojedynczy błąd w bloku siedmiu bitów przy mniej niż dwukrotnej liczbie bitów, a dłuższe kody radzą sobie znacznie lepiej.

Kim był Richard Hamming?

Amerykańskim matematykiem (1915–1998), który pracował przy Projekcie Manhattan, a potem przez trzydzieści lat w Bell Labs. Oprócz swoich kodów znany jest z okna Hamminga w przetwarzaniu sygnałów, z odległości Hamminga i z wykładu „You and Your Research”. W 1968 roku otrzymał Nagrodę Turinga.

Czy kod może poprawić dowolną liczbę błędów?

Tylko przy wystarczającej nadmiarowości. Kod może poprawić do (d − 1)/2 błędów w bloku, gdzie d to minimalna odległość między słowami kodowymi, a dłuższe kody z większą liczbą bitów kontrolnych osiągają większe d. Twierdzenie Shannona wyznacza ostateczną granicę: żaden kod nie przekroczy przepustowości kanału.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz symulator kodów korekcyjnych