024 025

nago typu zakłóceń. Oprócz.oczywistej metody jakiego projektowania . linii przesyłowych, aby zmniejszyć do minimum możliwości wystąpienia zniekształceń, Istnieje też inna metoda zwiększania niezawodności transmisji. Ogólnie polega ona na kodowaniu przesyłanych symboli przy użyciu większej niż jest to konieczne ilości bitów, czyli wprowadzeniu rozwlekłości, tak aby pomimo określonej ilości przekłamań można było odtworzyć bezbłędnie nadany symbol lub przynajmniej stwierdzić, że wystąpiło przekłamanie.

Bardzo prostą i często stosowaną metodą uzyskiwania kodu odpornego na zakłócenia jest'zastosowanie tzw. bitu parzystości. Metoda ta polega na dopisaniu do przesyłanej liczby jednego bitu takiego, aby suma jedynek w całej liczbie była zawsze parzysta (lub nieparzysta). Po stronie odbiorczej sprawdzana jest parzystość sumy jedynek. Jeżeli w czasie transmisji wystąpił pojedynczy błąd, zostanie on wykryty w tym sensie,że będzie wiadomo, te wystąpił, ale nie będzie możliwości (po stronie odbiorczej) Jego automatycznej korekcji. Wystąpienie dwóch błędów nie zostanie wykryte. Często zabezpieczenie bitem parzystości jest wystarczające, gdyż w typowych systemach transmisji prawdopodobieństwo wystąpienia pojedynczego błędu jest bardzo małe, a jednocześnie dwóch (o ile nie są skorelowane) znikome.

Aby dokładniej omówić kody wykrywające i korygujące błędy, wprowadzimy pojęcie odległości pomiędzy dwoma słowami kodu, przez którą będziemy rozumieli liczbę pozycji, na których w obu słowach występują różne cyfry (odległość Hamminga). Np. odległość pomiędzy słowami Oi91 1 0111 wynosił, zaś pomiędzy 1111 i 0001 wynosi 3.

Własności wykrywania i korygowania błędów zależą od minimalnej odległości pomiędzy wszystkimi parami słów w danym kodzie. Jeżeli odległość ta Jest równa 1, kod nie ma żadnych własności wykrywania błędów, ponieważ pojedynczy błąd może spowodować otrzymanie innego używanego słowa i błąd nie zostanie wykryty. Przy minimalnej odległości równej 2 (np. kod z bitem parzystości) kod ma już zdolność wykrywania pojedynczych błędów, zaś przy minimalnej odległości równej 3 zdolność do wykrywania i korygowania pojedynczych błędów. Jeżeli minimalna odległość wynosi 3, to pojedynczy błąd powoduje, że odebrane słowo jest położone w odległości 1 od słowa nadanego, ale na pewno w odległości co najmniej 2 od pozostałych. Ta różnica odległości pozwala odtworzyć nadane słowo. Poniżej podane są własności korekcyjne kodów w zależności od minimalnej odległości słów:

Minimalna odległość Własności kodów

1    Brak zdolności wykrywania błędów.

2    Wykrywanie pojedynczych błędów.

3    Korekcja pojedynczych albo wykrywanie    podwójnych

błędów.

4    Korekcja pojedynczych albo wykrywanie    potrójnych

błędów.

5    Korekcja podwójnych błędów albo wykrywanie poczwórnych błędów.

itd. ■    '

prsyfcłaŁitiy _at    __.______,_____,__,__________

• Dla. przesyłania 4-ch symboli A, B, C, D użyto następującego kodu dwój

kowego A - OOOOO B - 00111 O - 11001 D - 11110

Po stronie odbiorczej odebrano słowo 11101. Jakie słowo nadano, Jeżeli zakłada się, że czasie transmisji powstać mogły przekłamania tylko Jednego bitu?

Minimalna odległość w powyższym kodzie wynosi 3« czyli kod ten ma własność korekcji pojedynczych błędów. Odebrane słowo 11101 znajduje się w odległości 1 od słowa 11001, czyli nadano literę C.    tt

Spośród wielu możliwych kodów, dogodnym w konstrukcji i zapewniającym łatwą korekcję pojedynczych błędów (minimalna odległość równa się 3) Jest tzw. kod HammInga £11J. W kodzie tym wyróżnia się bity niosące informacje 1 bity służące do kontroli przekłamań (bity parzystości). Po odebraniu słowa kodowego przeprowadza się kontrolę parzystości w określonych grupach bitów. Liczba grup Jest równa liczbie bitóf parzystości, przy czym grupę tworzy się z Jednego bitu parzystości i wybranych bitów informacyjnych.

Kod Hammlnga jest tak skonstruowany, że wyniki badania parzystości w poszczególnych grupach wskazują pozycję, w odebranym słowie, na której nastąpiło przekłamanie.

Jeżeli ustalimy, ze ilość bitów parzystości wynosi r, to tworząc r grup i badając w nich parzystość możemy otrzymać 2^r różnych wiadomości o błędach, przy czym Jedna wiadomość Jest wskazaniem braku błędu. Stąd stosując r bitów parzystości potrafimy wskazać 2^r - 1 pozycji, na których wystąpiły błędy, uwzględniając zarówno pozycje bitów informacyjnych Jak i bitów parzystości. W konsekwencji maksymalna ilość bitów informacyjnych

Vx w?¹¹⁰⁸¹¹

^amax

= 2

(1.7)

Np. gdy r = 3, to maksymalna ilość bitów informacyjnych wynosi 4.

Grupy, w których sprawdzana jest parzystość, można skonstruować nawisie sposobów, ale musi być spełniona zasada, że błędy na różnych pozycjach powinny dać inny rozkład wyników kontroli parzystości w poszczególnych grupach.

Przykład 1.18

Zaprojektować kod Ha min Inga wykrywający pojedyncze błędy dla przypadku przesłania 16 wiadomości.    .

'Dla przesłania 16 wiadomości należy użyć 4 bitów Informacyjnych i stąd na podstawie równania (1.7) otrzymujemy r = 3. Tak więc projektowany kod zawiera 4 bity informacyjne i 3 bity parzystości, które oznaczymy odpowiednio przez x^, Xj, x₂, x^ i yj, y₂, y^. W tablicy na rys. 1.12 przed-