2749772008

7

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

Kod C długości n, odległości równej d i mający M słów kodowych będziemy nazywali (n, M, d)-kodem.

Załóżmy, że kod C nad ciałem GF(q) długości n zawierający M słów może poprawić t błędów. Wówczas kule o promieniu t wokół słów kodowych są rozłączne. Każda z takich M kul zawiera 1 + (q — 1)    +... + (q — 1)*

wektorów. Ponieważ całkowita liczba elementów przestrzeni GF{q)ⁿ wynosi qⁿ otrzymujemy następujące ograniczenie na liczbę słów kodowych.

Twierdzenie 1.19. (Ograniczenie Hamming’a.)

Kod długości nnad ciałem GF(q), zawierający M słów kodowych i poprawiający t błędów musi spełniać następującą nierówność

(1)

W szczególności dla kodów binarnych musi być spełniona nierówność:

< 2ⁿ.

M( 1 +

Kody, dla których w ograniczeniu (1) zachodzi równość nazywamy kodami doskonałymi.

Definicja 1.20. Współczynnikiem sprawności (n, M, d)-koduC nazywamy łiczbę

n

0 <R

Wartość współczynnika R wskazuje na poziom efektywności kodu. Im większy współczynnik sprawności kodu tym w słowach kodowych jest mniej symboli sprawdzających a więcej symboli informacji. Kod jest tym lepszy im większa jest wartość R. Oznacza to, że dla zadanej długości lepsze kody mają większą liczbę słów kodowych.

W analizie systemów przesyłania stosuje się uproszczone modele kanału transmisyjnego. Najbardziej rozpowszechniony jest model tzw. kanału symetrycznego. Z założenia taki kanał nie gubi i nie dodaje symboli do przesyłanej informacji oraz każdy z możliwych błędów jest tak samo prawdopodobny.