Drukuj ten rozdziałDrukuj ten rozdział

Podręcznik

4. Kody wykrywające i korygujące błędy

4.3. Podstawowe twierdzenia o kodach wykrywających i korygujących błędy

Definicja (m,n) kodu i kodu liniowego. Zakładamy, że chcemy przesyłać słowa nad alfabetem GF(pk) (alfabetem jest ciało skończone mające  pk elementów, gdzie p jest liczbą pierwszą w szczególności może to być ciało GF(2) = Z2 = {0,1}. Słowa przesyłane mają długość m, chcemy więc przesyłać słowa z (GF(pk))m. Koncepcja kodu wykrywającego lub korygującego błędy polega na wykorzystaniu kodu redundancyjnego fsmutnyGF(pk))m → (GF(pk))n, gdzie n > m. Taki kod nazywamy (m,n) kodem. Obiektami kodowanymi są tu słowa o długości m nad alfabetem GF(pk) a słowami kodowymi słowa z (GF(pk))m. Zbiory (GF(pk))m i (GF(pk))n są przestrzeniami liniowymi nad ciałem GF(pk). Jeśli odwzorowanie fsmutnyGF(pk))m → (GF(pk))n jest liniowe to kod nazywamy kodem liniowym. 

Liniowość odwzorowania oznacza, że istnieje taka macierz A o współczynnikach w ciele GF(pk) mająca n wierszy i m kolumn, że dla wektora a ∈ (GF(pk))m mamy

f(a) = A ⋅ a

gdzie wektor a jest traktowany jako macierz kolumnowa.

Kod wykrywający błędy powinien zachowywać się tak, że gdy odbieramy zamiast słowa kodowego f(a) słowo z przekłamaniami na pewnej niewielkiej liczbie co najwyżej r pozycji (oznaczmy to słowo z przekłamaniami przez br(f(a))) to oglądając br(f(a)) będziemy mogli stwierdzić czy nastąpiły przekłamania.

Powiemy, że kod fsmutnyGF(pk))m → (GF(pk))n wykrywa fakt popełnienia co najwyżej r błędów jeśli dla każdego a ∈ (GF(pk))m zmiana cyfr na co najwyżej r pozycjach w słowie kodowym f(a) nie powoduje przejścia słowa kodowego w słowo f(b) dla pewnego b ∈ (GF(pk))m,  a ≠ b.

Praktycznie więc wykrywanie błędu może polegać na porównaniu br(f(a)) z wszystkimi możliwymi słowami kodującymi f(c) dla c ∈ (GF(pk))m. Jeśli nie stwierdzamy zgodności, to stwierdzamy, że słowo br(f(a)) zawiera przekłamanie.

Kod korygujący błędy powinien zachowywać się tak, że gdy odbieramy zamiast słowa kodowego f(a) słowo z przekłamaniami na pewnej niewielkiej liczbie co najwyżej r pozycji (tzn. słowo br(f(a))) to oglądając  br(f(a)) będziemy mogli skorygować błędy (stosując pewien algorytm) uzyskując słowo f(a) a więc w konsekwencji stwierdzamy, że zostało nadane słowo a.

Zasadnicza koncepcja na jakiej opierają się kody korekcyjne jest taka: Niech fsmutnyGF(pk))m → (GF(pk))n będzie (m,n) kodem kodującym słowa o długości m za pomocą słów o długości n, gdzie n > m. Zakładamy, że podczas transmisji słowa f(a) o długości m może powstać co najwyżej r błędów. Dla każdego a ∈ (GF(pk))m kodujemy przy tym słowo a takim ciągiem a ∈ (GF(pk))n , że

\underset{a,b \in (GF(p^k))^m, a \neq b}{\forall} = K(f(a),r) ∩ K(f(b),r) = ∅\qquad(1)

gdzie K(x,r) oznacza kulę o promieniu r w przestrzeni metrycznej GF(pk))n  z metryką Hamminga dH. Warunek (1) oznacza, że każde dwie kule rodziny kul K(f(x),r); a ∈ GF(pk))m są rozłączne. Jeśli tak jest to aby stwierdzić jaka informacja została nadana wystarczy zastosować do słowa odebranego bk(f(a)); a ∈ (GF(pk))m regułę decyzyjną d: GF(pk))n→GF(pk))n  zdefiniowaną wzorem

d(br(f(a))) = a 

wtedy i tylko wtedy, gdy

 dH(f(a),br,f(a)) = \underset{x \in (GF(p^k))^m}{min}{<d<sub><em>d<sub>H</sub></em>(<span class="equation">f</span>(<em>x</em>),<em>b<sub>r</sub></em>(<span class="equation">f</span>(<em>a</em>)) }\qquad(2)

Innymi słowy jako informację nadaną przyjmujemy takie a (GF ( pk ))m , że odebrane słowo br (f(a)) (GF( pk ))n jest najbliższe f(a) tzn.

\underset{a,b \in (GF(p^k))^m, a \neq b}{\forall} dH (f(a), b) dH ( f(x), b)\qquad (3)

Jest oczywiste, że powyższa reguła decyzyjna przy warunku (1) jest poprawna w tym sensie, że pozwala na odtworzenie wiadomości nadanej przy ograniczonej do r ilości błędów transmisji.

Warto zauważyć, że istotą powyższego pomysłu na kod korekcyjny jest to, że wokół każdego słowa kodującego f(a) (gdzie a (GF ( pk ))m ) tworzymy otoczenie (w metryce Hamminga), którego elementy (oprócz f(a)) nie są wykorzystywane do kodowania słów z a (GF ( pk ))m . Możemy jednak odebrać (w wyniku wprowadzenia błędów podczas przesyłania słowa f(a)) dowolny element z tego otoczenia a mimo to nie tracimy orientacji w sytuacji, potrafimy wykryć i skorygować przekłamania.

Niech będzie dany (m,n) kod f : (GF ( pk ))m (GF ( pk ))n i ustalona liczba r  0, n . Kod f wykrywa fakt popełnienia co najwyżej r błędów wtedy i tylko wtedy gdy dla każdego a, b (GF ( pk )m , a b mamy f (a) K ( f (b), r) (czyli dH ( f (a), f (b)) r ).
Kod f : (GF ( pk ))m (GF ( pk ))n koryguje popełnienia co najwyżej r błędów wtedy i tylko wtedy, gdy dla każdego a, b (GF ( pk ))m , a b mamy dH ( f (a), f (b)) 2r 1 (lub równoważnie spełniony jest warunek (1)).
Klasycznym przykładem kodu korekcyjnego jest kod s krotnie powtórzony. Powstaje on przez przyporządkowanie słowu kodowanemu a (GF ( pk ))m słowa kodowego \underset{s}{\underbrace{aa...aa}} (GF ( pk ))ms . Zdolności korekcyjne tak zdefiniowanego kodu są oczywiste. Widać s od razu, że popełnienie co najwyżej r błędów w słowie kodowym (gdzie r < \frac{s}{2} ) nie przeszkadza w poprawnym odczytaniu takiego słowa kodowego. Kod s krotnie powtórzony jest (m, s m) kodem.

Kod blokowy. Niech V będzie ustalonym alfabetem. Kodem blokowym nazywamy kod f : Vm Vn , w którym słowom o długości m (obiektom kodowanym) przyporządkowujemy słowa o długości n, gdzie n m .

(m,n) kod jest kodem blokowym.

Kod blokowy nazywamy kodem grupowym, jeśli słowa kodowe kodu tworzą grupę addytywną.

Różnych typów kodów korekcyjnych (ang. ECC od Error Correcting Codes) jest dosyć dużo. Z bardziej znanych warto wymienić:

  • kody cykliczne (kody CRC - ang. Cyclic Redundancy Check)
  • kody Hamminga
  • kody Reeda-Solomona
  • kody Bose-Chaudhuri-Hocquenghema (kody BCH)
Kodowanie stosowane w płytach kompaktowych (płytach CD) to kod Reeda-Solomona, a ściślej CIRC (CIRC - ang. cross interleaved Reed-Solomon code).