Podręcznik

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

Liniowość odwzorowania oznacza, że istnieje taka macierz A o współczynnikach w ciele GF(p^k) mająca n wierszy i m kolumn, że dla wektora a ∈ (GF(p^k))^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 b_r(\(f\)(a))) to oglądając b_r(\(f\)(a)) będziemy mogli stwierdzić czy nastąpiły przekłamania.

Powiemy, że kod \(f\)GF(p^k))^m → (GF(p^k))ⁿ wykrywa fakt popełnienia co najwyżej r błędów jeśli dla każdego a ∈ (GF(p^k))^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(p^k))^m,  a ≠ b.

Praktycznie więc wykrywanie błędu może polegać na porównaniu b_r(\(f\)(a)) z wszystkimi możliwymi słowami kodującymi \(f\)(c) dla c ∈ (GF(p^k))^m. Jeśli nie stwierdzamy zgodności, to stwierdzamy, że słowo b_r(\(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 b_r(\(f\)(a))) to oglądając  b_r(\(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 \(f\)GF(p^k))^m → (GF(p^k))ⁿ 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(p^k))^m kodujemy przy tym słowo a takim ciągiem a ∈ (GF(p^k))ⁿ , ż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(p^k))ⁿ  z metryką Hamminga d_H. Warunek (1) oznacza, że każde dwie kule rodziny kul K(\(f\)(x),r); a ∈ GF(p^k))^m są rozłączne. Jeśli tak jest to aby stwierdzić jaka informacja została nadana wystarczy zastosować do słowa odebranego b_k(\(f\)(a)); a ∈ (GF(p^k))^m regułę decyzyjną d: GF(p^k))ⁿ→GF(p^k))ⁿ  zdefiniowaną wzorem

d(b_r(f(a))) = a 

wtedy i tylko wtedy, gdy

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

Innymi słowy jako informację nadaną przyjmujemy takie a  (GF ( p^k ))^m , że odebrane słowo b_r (f(a))  (GF( p^k ))ⁿ jest najbliższe f(a) tzn.

_{\(\underset{a,b \in (GF(p^k))^m, a \neq b}{\forall}\)} d_H (f(a), b)  d_H ( 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 ( p^k ))^m ) tworzymy otoczenie (w metryce Hamminga), którego elementy (oprócz f(a)) nie są wykorzystywane do kodowania słów z a  (GF ( p^k ))^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.

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

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)