Wprowadzenie do Kontroli Błędów

Błędy w kanale transmisyjnym

Kanał komunikacyjny wykorzystujący kabel miedziany, światłowód lub łącze bezprzewodowe jest podczas transmisji narażony na szumy, interferencje i inne zakłócenia. Te czynniki mogą zniekształcić sygnał i sprawić, że odbiornik błędnie zinterpretuje jeden lub więcej bitów przesyłanych danych.

Błąd bitowywystępuje, gdy nadane '1' zostaje odebrane jako '0' lub odwrotnie. Skutek zależy od pola albo próbki zawierającej ten bit, dlatego odbiornik potrzebuje metody kontroli błędów do wykrywania lub korygowania uszkodzonych danych. Liczba i rozkład błędów wpływają również na dobór kodu. Integralność danych jest podstawowym wymaganiem telekomunikacji.

Redundancja w kontroli błędów

Podstawową strategią obsługi błędów transmisyjnych jest wprowadzenie redundancji(nadmiarowości). Oznacza to dodanie do oryginalnego strumienia danych dodatkowych informacji według reguł kodowania. Odbiornik wykorzystuje ją, aby sprawdzić poprawność danych, a w kodzie korekcyjnym także odtworzyć określoną liczbę uszkodzonych bitów.

Odbiornik ponownie oblicza zależność kontrolną na podstawie odebranego bloku i porównuje wynik z redundancją przesłaną wraz z blokiem. Niezgodność oznacza konieczność odrzucenia lub korekcji bloku, zależnie od zastosowanego kodu.

ARQ: wykrywanie i retransmisja

To podejście, znane jako ARQ (automatyczne żądanie powtórzenia), wykorzystuje kanał zwrotny. Odbiornik informuje, czy blok przeszedł kontrolę, a nadawca wysyła kolejny blok lub powtarza uszkodzony.

1. Nadawca wysyła blok danych wraz z redundancją (np. sumą kontrolną).
2. Odbiornik sprawdza, czy dane są poprawne, używając redundantnych informacji.
3. Jeśli dane są poprawne, odbiornik wysyła pozytywne potwierdzenie (ACK). Nadawca wysyła wtedy kolejny blok.
4. Jeśli dane są uszkodzone, odbiornik wysyła negatywne potwierdzenie (NACK). Nadawca ponownie przesyła ten sam blok.

ARQ może odzyskać uszkodzone bloki, gdy dostępne są ścieżka zwrotna i procedura retransmisji. TCP wykorzystuje potwierdzenia i retransmisje do zapewnienia niezawodnego strumienia bajtów. Każda retransmisja zwiększa opóźnienie, co ogranicza efektywność łączy z częstymi błędami lub długim czasem propagacji, w tym niektórych łączy satelitarnych.

FEC: korekcja błędów w przód

Ta metoda, zwana FEC (korekcja błędów w przód), przenosi korekcję błędów do odbiornika. Nadawca dodaje wystarczająco dużo informacji nadmiarowej, aby odbiornik mógł wykryć i samodzielnie skorygować określoną liczbę błędów.

Metoda jest użyteczna, gdy kanał zwrotny jest niedostępny lub niepraktyczny:

• Transmisje jednokierunkowe: takie jak telewizja cyfrowa czy radio.
• Łącza o wysokim opóźnieniu: takie jak komunikacja z sondami kosmicznymi, gdzie retransmisja powodowałaby długie opóźnienie propagacji.
• Systemy czasu rzeczywistego: gdzie nie ma czasu na oczekiwanie na retransmisję, na przykład w streamingu audio/wideo.

Odległość Hamminga w kontroli błędów

Zdolność kodu do wykrywania i korygowania błędów jest określona przez jego minimalną odległość Hamminga ($d_{min}$). Większa odległość między prawidłowymi słowami kodowymi zwiększa liczbę błędów, które dekoder może tolerować przed pojawieniem się niejednoznaczności.

Warunki wykrywania i korekcji

1. Wykrywanie błędów: Aby móc wykryć do $e$ błędów bitowych w słowie kodowym, minimalna odległość Hamminga kodu musi wynosić:

   $d_{min} \ge e + 1$

   Na przykład, prosty bit parzystości tworzy kod o $d_{min} = 2$, więc może niezawodnie wykryć $e=1$ pojedynczy błąd bitowy.
2. Korekcja błędów: Aby móc skorygować do $t$ błędów bitowych w słowie kodowym, minimalna odległość Hamminga kodu musi wynosić:

   $d_{min} \ge 2t + 1$

   Na przykład, prosty kod powtórzeniowy (np. wysyłanie '000' dla '0' i '111' dla '1') ma $d_{min} = 3$. Ten kod może skorygować $t=1$ pojedynczy błąd bitowy.