2749772004

Kody wykrywające i korygujące błędy - konspekt wykładu 2006/07

Podstawowe definicje i własności

Załóżmy, że informacja jest kodowana przy zastosowaniu symboli należących do skończonego ciała A = GF(q) o q = p^m elementach. Formalnie kod możemy zdefiniować w następujący sposób.

Definicja 1.3. Podzbiór C wolnego monoidu A* nazywamy kodem nad alfabetem A, jeśli dla dowolnych n,m € Z⁺, C\,..., Cm, d\,..., d_m e C C A*,

C\... Cjfi — d\... dfi n — m, d^.

Oznacza to, że jakiekolwiek słowo w wolnej półgrupie nad zbiorem C może być odczytane jednoznacznie jako konkatenacja słów ze zboru C. Elementy zbioru C będziemy nazywać słowami kodowymi.

Przykład 1.4. Wyróżnijmy pewien element alfabetu A i nazwijmy go przecinkiem. Kod przecinkowy nad A złożony jest ze słów, w których przecinek występuje dokładnie raz na końcu słowa. □

Ze względu na sposób dołączania dodatkowych znaków do przesyłanej wiadomości stosowane w praktyce kody dzielimy na dwie klasy: kody blokowe i kody rekurencyjne. W przypadku kodów blokowych przesyłaną informację można podzielić na bloki zawierające k symboli, które mogą być kodowane i dekodowane niezależnie od innych bloków. Po dodaniu symboli dodatkowych słowa kodowe tworzą niepusty podzbiór C n-wymiarowej przestrzeni wektorowej nad ciałem A = GF(q). Mówimy wówczas, że kod jest długości n. Natomiast w przypadku kodów rekurencyjnych, słowa kodowe nie są stałej długości, lecz nieskończony ciąg symboli informacji przekształcany jest w nieskończony ciąg symboli wiadomości. Elementy kodu uzależnione są od bieżącego elementu informacji oraz od pewnej liczby elementów poprzednich. Na przykład ciąg zamieniany jest w ciąg *0)*o>*i>*m • • •, gdzie i'_n jest funkcją zmiennych «o> *i, • • •,

Jeśli \C\ = 1 to C nazywamy kodem trywialnym. Jeśli q = 2 to C jest kodem binarnym.

Kod blokowy, w którym można odróżnić elementy informacyjne od kontrolnych nazywamy kodem systematycznym. Oznacza to, że symbole na pewnych k pozycjach są symbolami informacji oraz istnieje dokładnie jedno słowo kodowe dla każdego możliwego wyboru współrzędnych na tych k pozycjach.