2749772002

2

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

Gdy na przykład otrzymamy słowo 10010001 to od razu wiemy, że pierwsza cyfra wiadomości może być błędna. Ale cały czas nie wiemy czy błąd powstał w pierwszej czy drugiej części słowa.    □

Przykład 1.2. Lepszą metodą do wykrywania pojedynczych błędów jest tzw. binarny kod badania parzystości. Polega on na dodaniu na końcu każdego wysyłanego słowa sumy cyfr mod 2. Jeśli suma cyfr przesłanej wiadomości jest nieparzysta, to odbiornik ”wie”, że przy przesyłaniu musiał wystąpić błąd. Ale nawet, jeśli suma ta jest parzysta, to nie możemy być pewni, że błąd się nie pojawi.    □

Początki teorii kodowania przypadają na koniec lat czterdziestych u-biegłego wieku. Opublikowaną w 1948 roku pracą pt.”Mathematical theory of communication” C.E.Shannona zainicjował powstanie teorii informacji. Rok później ukazał się artykuł M.J.E.Golay’a pt.”Notes on digital coding”. Natomiast w 1950 roku R.W.Hamming napisał ”Error detecting and error correcting codes”.

Zasadnicza idea kodowania polega na przesyłaniu wraz z wiadomością pewnej informacji "nadmiarowej”, nie wnoszącej nic do treści samej wiadomości. Odebrana, wydłużona w ten sposób wiadomość odwzorowywana jest za pomocą przekształcenia dekodującego na ciąg pierwotnej długości. Dodatkowa informacja powinna umożliwić w procesie dekodowania bezbłędne odtworzenie wysłanego słowa, jeśli w czasie transmisji wystąpiło ”mało” błędów.

Przez analizę informacji zawartych w dodatkowo przesyłanych znakach odbiorca może wykryć, a w niektórych przypadkach nawet skorygować powstały na skutek zakłóceń w kanale transmisyjnym błąd. W związku z tym kody dzielimy na kody wykrywające błędy i na kody korygujące błędy. Kody wykrywające błędy mają po pierwsze na celu ustalenie czy w otrzymanej wiadomości wystąpił błąd pojedynczy, ponieważ takie błędy są najbardziej prawdopodobne. Następnie będą starać się wykrywać błędy podwójne, potrójne i tak dużo jak to będzie możliwe. Natomiast w przypadku kodów korygujących w procesie dekodowania należy błędy wykryć, zlokalizować a następnie poprawić.