Transmisja danych w sieciach komputerowych - Kodowanie korekcyjne CRC

1. Kodery korekcyjne są to urządzenia lub algorytmy, które służą do wykrywania i korygowania błędów, które mogą wystąpić podczas transmisji danych. Błędy mogą być spowodowane przez zakłócenia, zniekształcenia, utratę sygnału lub inne czynniki. Cel stosowania koderów korekcyjnych jest zwiększenie niezawodności i jakości transmisji danych.

Sposób implementacji koderów korekcyjnych polega na dodawaniu do przesyłanych danych dodatkowych bitów, zwanych bitami nadmiarowymi lub bitami parzystości, które pozwalają na sprawdzenie poprawności otrzymanych danych. Istnieją różne metody kodowania korekcyjnego, takie jak kody Hamminga, kody cykliczne, kody BCH, kody Reeda-Solomona, kody turbo i inne. Każda z nich ma swoje zalety i wady, zależne od stopnia korekcji, złożoności obliczeniowej, szybkości transmisji i innych parametrów.

2. Automatyczne żądanie powtórzeń (ang. Automatic Repeat reQuest, ARQ) jest to technika kontroli błędów w transmisji danych, która polega na automatycznym wysyłaniu przez odbiorcę żądania ponownego przesłania danych, jeśli wykryje on błąd w otrzymanym pakiecie. ARQ jest często stosowane w połączeniach bezprzewodowych, gdzie występuje duża szansa na zakłócenia sygnału.

ARQ wymaga, aby nadawca i odbiorca stosowali ten sam protokół komunikacyjny, który określa sposób wykrywania błędów, formatowanie pakietów, numerowanie sekwencyjne, potwierdzanie odbioru, czas oczekiwania i procedury ponownego wysyłania. Istnieją trzy podstawowe rodzaje ARQ: stop-and-wait ARQ, go-back-n ARQ i selective-repeat ARQ. Różnią się one sposobem reagowania na błędy i wykorzystywania przepustowości kanału.

3. Systemy zabezpieczania przed błędami są to systemy transmisyjne, które stosują kodowanie korekcyjne w celu poprawy jakości transmisji danych. Ze względu na zasadę działania rozróżnia się trzy klasy systemów zabezpieczania przed błędami:
  • Systemy otwarte są to systemy, w których nadawca i odbiorca nie wymieniają się żadnymi informacjami zwrotnymi. Nadawca wysyła dane zakodowane za pomocą kodu korekcyjnego, a odbiorca próbuje je zdekodować i skorygować ewentualne błędy. Systemy otwarte są proste i tanie, ale mają ograniczoną zdolność korekcji i nie mogą dostosować się do zmian warunków transmisji.
  • Systemy ze sprzężeniem informacji są to systemy, w których odbiorca wysyła do nadawcy informację zwrotną o jakości otrzymanych danych. Informacja ta może być w postaci potwierdzenia odbioru, żądania powtórzenia, wskaźnika błędów lub innych danych. Systemy ze sprzężeniem informacji pozwalają na poprawę jakości transmisji przez dostosowanie parametrów kodowania, zmianę szybkości transmisji, zmianę kanału lub inną akcję korygującą. Systemy ze sprzężeniem informacji są bardziej skomplikowane i droższe niż systemy otwarte, ale mają większą zdolność korekcji i adaptacji.
  • Systemy ze sprzężeniem zwrotnym decyzji są to systemy, w których odbiorca wysyła do nadawcy informację zwrotną o swojej decyzji o poprawności otrzymanych danych. Informacja ta może być w postaci bitu potwierdzenia, bitu błędu lub innych danych. Systemy ze sprzężeniem zwrotnym decyzji pozwalają na poprawę jakości transmisji przez wykorzystanie informacji o poprzednich decyzjach odbiorcy do lepszego dekodowania i korekcji bieżących danych. Systemy ze sprzężeniem zwrotnym decyzji są najbardziej skomplikowane i droższe, ale mają największą zdolność korekcji i adaptacji.
4. Sumy kontrolne są to proste metody wykrywania błędów w transmisji danych, polegające na obliczaniu wartości liczbowej na podstawie przesyłanych danych i dołączaniu jej do nich jako dodatkowego bitu lub bajtu. Odbiorca oblicza sumę kontrolną na podstawie otrzymanych danych i porównuje ją z sumą kontrolną wysłaną przez nadawcę. Jeśli sumy kontrolne się zgadzają, oznacza to, że dane są prawdopodobnie poprawne. Jeśli sumy kontrolne się różnią, oznacza to, że wystąpił błąd w transmisji.

Sumy kontrolne są łatwe do obliczenia i implementacji, ale mają niską skuteczność w wykrywaniu błędów, ponieważ mogą nie wykryć niektórych rodzajów błędów, takich jak błędy symetryczne, błędy wielobitowe czy błędy przesunięcia bitów. Sumy kontrolne nie pozwalają również na korekcję błędów, tylko na ich wykrycie.

5. Kody cykliczne są to specjalne rodzaje kodów liniowych, które mają tę własność, że każda cykliczna permutacja słowa kodowego jest również słowem kodowym. Cykliczna permutacja polega na przesunięciu bitów słowa kodowego o pewną liczbę pozycji w lewo lub w prawo, przy czym bity wychodzące poza granicę słowa są przenoszone na drugi koniec. Przykładem kodu cyklicznego jest kod CRC.

Kody cykliczne mają wiele zalet, takich jak łatwość generowania, dekodowania i korekcji, wysoka zdolność wykrywania i korygowania błędów, niska złożoność obliczeniowa i sprzętowa, możliwość stosowania operacji algebraicznych i wielomianowych. Kody cykliczne są szeroko stosowane w transmisji danych, takiej jak komunikacja satelitarna, sieci komputerowe, pamięci masowe, systemy radiowe i telewizyjne.

6. Kontrola cykliczno-nadmiarowa jest to metoda wykrywania błędów w transmisji danych, oparta na kodach cyklicznych. Polega ona na dodawaniu do przesyłanych danych dodatkowych bitów, zwanych bitami CRC, które są obliczane na podstawie danych za pomocą specjalnego wielomianu generacyjnego. Odbiorca oblicza bity CRC na podstawie otrzymanych danych i porównuje je z bitami CRC wysłanymi przez nadawcę. Jeśli bity CRC się zgadzają, oznacza to, że dane są prawdopodobnie poprawne. Jeśli bity CRC się różnią, oznacza to, że wystąpił błąd w transmisji.

CRC jest jedną z najczęściej stosowanych metod wykrywania błędów w transmisji danych, ponieważ ma wysoką skuteczność w wykrywaniu błędów pojedynczych, podwójnych i grupowych, niską złożoność obliczeniową i sprzętową, możliwość stosowania różnych wielomianów generacyjnych dostosowanych do różnych zastosowań i warunków transmisji. CRC nie pozwala jednak na korekcję błędów, tylko na ich wykrycie.

7. Cykliczna kontrola redundancji CRC:

Zalety i wady cyklicznej kontroli redundancji CRC można podsumować następująco:

- Zalety:
    - Wysoka skuteczność w wykrywaniu błędów pojedynczych, podwójnych i grupowych
    - Niska złożoność obliczeniowa i sprzętowa
    - Możliwość stosowania różnych wielomianów generacyjnych dostosowanych do różnych zastosowań i warunków transmisji
    - Łatwość implementacji i testowania
    - Szerokie zastosowanie w różnych dziedzinach transmisji danych
- Wady:
    - Brak możliwości korekcji błędów, tylko wykrycie
    - Możliwość nie wykrycia niektórych rodzajów błędów, takich jak błędy symetryczne, błędy wielobitowe czy błędy przesunięcia bitów
    - Zależność od wyboru odpowiedniego wielomianu generacyjnego, który może być trudny do znalezienia lub zoptymalizowania
    - Konieczność dodawania dodatkowych bitów do przesyłanych danych, co zmniejsza efektywność transmisji

8. Suma kontrolna CRC jest generowana za pomocą metody wielomianu generacyjnego, która polega na następujących krokach:

- Wybór wielomianu generacyjnego G(x) o stopniu n, który będzie służył do obliczania bitów CRC. Przykładem takiego wielomianu jest G(x) = x^16 + x^12 + x^5 + 1, który jest stosowany w standardzie Ethernet.
- Przedstawienie danych D, które mają być przesłane, jako wielomian D(x) o stopniu k. Przykładem takiego wielomianu jest D(x) = x^7 + x^6 + x^4 + x^2 + 1, który odpowiada ciągowi bitów 11010101.
- Przesunięcie danych D(x) o n pozycji w lewo, czyli dodanie n zer na końcu. W ten sposób otrzymujemy wielomian D'(x) o stopniu k+n. Przykładem takiego wielomianu jest D'(x) = x^23 + x^22 + x^20 + x^18 + x^16 + x^7 + x^6 + x^4 + x^2 + 1, który odpowiada ciągowi bitów 110101010000000000000000.
- Podzielenie wielomianu D'(x) przez wielomian G(x) za pomocą operacji modulo 2, czyli dodawania i odejmowania bez przenoszenia. W ten sposób otrzymujemy resztę z dzielenia R(x) o stopniu mniejszym niż n. Przykładem takiej reszty jest R(x) = x^11 + x^10 + x^7 + x^6 + x^4 + x^2 + 1, która odpowiada ciągowi bitów 11011010101.
- Dołączenie reszty R(x) do danych D(x) jako bitów CRC. W ten sposób otrzymujemy wielomian C(x) o stopniu k+n, który jest podzielny przez wielomian G(x). Przykładem takiego wielomianu jest C(x) = x^23 + x^22 + x^20 + x^18 + x^16 + x^11 + x^10 + x^7 + x^6 + x^4 + x^2 + 1, który odpowiada ciągowi bitów 1101010111011010101.

Suma kontrolna CRC jest więc równa reszcie R(x), która jest obliczana na podstawie danych D(x) i wielomianu generacyjnego G(x) za pomocą operacji modulo 2. Suma kontrolna CRC jest dołączana do danych D(x) jako dodatkowe bity, które pozwalają na sprawdzenie poprawności otrzymanych danych przez odbiorcę.

9. Twierdzenie Shannona jest to podstawowe twierdzenie teorii informacji, które określa maksymalną szybkość transmisji danych bez błędów przez kanał komunikacyjny o danej przepustowości i szumie. Twierdzenie Shannona ma postać:

C = B log2 (1 + S/N)

gdzie:

C jest maksymalną szybkością transmisji danych bez błędów, wyrażoną w bitach na sekundę (bps)
B jest przepustowością kanału, wyrażoną w hercach (Hz)
S jest mocą sygnału, wyrażoną w watach (W)
N jest mocą szumu, wyrażoną w watach (W)
log2 jest logarytmem o podstawie 2


Twierdzenie Shannona pokazuje, że maksymalna szybkość transmisji danych bez błędów zależy od stosunku sygnału do szumu (S/N) i przepustowości kanału. Im większy jest stosunek sygnału do szumu i im większa jest przepustowość kanału, tym większa jest maksymalna szybkość transmisji danych bez błędów. Twierdzenie Shannona jest granicznym przypadkiem, który nie uwzględnia kodowania korekcyjnego ani innych metod poprawy jakości transmisji.

Model systemu transmisyjnego z kodowaniem nadmiarowym
Model systemu transmisyjnego z kodowaniem nadmiarowym jest to uproszczony model procesu transmisji danych z zastosowaniem kodowania korekcyjnego. Model ten składa się z następujących elementów:

Źródło informacji, które generuje dane do przesłania
Koder, który dodaje do danych bity nadmiarowe za pomocą kodu korekcyjnego
Kanał transmisyjny, który przenosi dane z kodem korekcyjnym z nadajnika do odbiornika, przy czym mogą wystąpić błędy w transmisji
Dekoder, który odbiera dane z kodem korekcyjnym i próbuje je zdekodować i skorygować ewentualne błędy
Odbiorca informacji, który otrzymuje dane po dekodowaniu i korekcji
Model systemu transmisyjnego z kodowaniem nadmiarowym ilustruje, jak kodowanie korekcyjne może poprawić jakość transmisji danych przez dodawanie redundancji do danych i wykorzystanie tej redundancji do wykrywania i korygowania błędów.

Zysk kodowy  jest to miara poprawy jakości transmisji danych dzięki zastosowaniu kodowania korekcyjnego. Zysk kodowy jest zdefiniowany jako różnica między stosunkiem sygnału do szumu (S/N) wymaganym dla transmisji bez kodowania korekcyjnego a stosunkiem sygnału do szumu wymaganym dla transmisji z kodowaniem korekcyjnym przy tej samej szybkości transmisji i tym samym prawdopodobieństwie błędu. Zysk kodowy jest wyrażany w decybelach (dB).

Zysk kodowy pokazuje, jak wiele można zredukować moc sygnału lub zwiększyć moc szumu, nie pogarszając jakości transmisji, dzięki zastosowaniu kodowania korekcyjnego. Im większy jest zysk kodowy, tym lepszy jest kod korekcyjny. Zysk kodowy zależy od rodzaju kodu korekcyjnego, stopnia korekcji, szybkości transmisji i prawdopodobieństwa błędu.

Kody BCH i Reeda-Solomona są to rodzaje kodów cyklicznych, które mają wysoką zdolność korygowania błędów grupowych, czyli błędów, które występują w ciągłych blokach bitów. Kody BCH i Reeda-Solomona są oparte na teorii ciał skończonych i algebraicznej geometrii.

Kody BCH (ang. Bose-Chaudhuri-Hocquenghem codes) są to kody cykliczne, które pozwalają na korekcję do t błędów w każdym bloku n bitów, gdzie t jest parametrem kodu. Kody BCH są generowane za pomocą specjalnych wielomianów generacyjnych, które są minimalnymi wielomianami o pierwiastkach będących potęgami pierwotnego elementu ciała skończonego. Kody BCH są dekodowane za pomocą algorytmu Berlekampa-Massey lub algorytmu Euclidesa.

Kody Reeda-Solomona (ang. Reed-Solomon codes) są to kody cykliczne, które pozwalają na korekcję do t symboli w każdym bloku n symboli, gdzie t jest parametrem kodu, a symbol jest grupą bitów o określonej długości. Kody Reeda-Solomona są generowane za pomocą specjalnych wielomianów generacyjnych, które są wielomianami interpolacyjnymi przechodzącymi przez określone punkty ciała skończonego. Kody Reeda-Solomona są dekodowane za pomocą algorytmu Berlekampa-Massey lub algorytmu Petersona-Gorenstein-Zierlera.

Kody BCH i Reeda-Solomona mają wiele zalet, takich jak wysoka zdolność korygowania błędów grupowych, możliwość korekcji błędów erasure (utraty symboli), możliwość stosowania różnych parametrów kodu, możliwość stosowania operacji algebraicznych i wielomianowych. Kody BCH i Reeda-Solomona są szeroko stosowane w różnych dziedzinach transmisji danych, takich jak komunikacja satelitarna, sieci komputerowe, pamięci masowe, systemy radiowe i telewizyjne, systemy multimedialne i kryptografia.

10. Reguła dekodowania kodów cyklicznych:
  • Jeśli otrzymane dane są poprawne, to znaczy, że nie ma w nich błędów, to wystarczy usunąć bity nadmiarowe i otrzymać oryginalne dane.
  • Jeśli otrzymane dane są niepoprawne, to znaczy, że zawierają błędy, to trzeba spróbować znaleźć i naprawić błędy za pomocą odpowiedniego algorytmu, taki jak algorytm Berlekampa-Massey, algorytm Euclidesa lub inny. Jeśli uda się znaleźć i naprawić błędy, to należy usunąć bity nadmiarowe i otrzymać oryginalne dane. Jeśli nie uda się znaleźć i naprawić błędów, to należy odrzucić otrzymane dane i poprosić o ponowne przesłanie danych.
Reguła dekodowania kodów cyklicznych pozwala na sprawdzenie i poprawienie jakości transmisji danych za pomocą obliczeń matematycznych i operacji logicznych. Reguła dekodowania kodów cyklicznych zależy od rodzaju kodu cyklicznego, liczby błędów, wzoru matematycznego i algorytmu korekcyjnego.