024 025

24

nago typu zakłóceń. Oprócz oczywistej metodyJbąkiego 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, że wystąpił, sile nie będzie możliwości (po stronie odbiorczej) Jego automatycznej korekcji, ^stą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ść Bamminga). Np. odległość pomiędzy słowami 0101 i 0111 wynosił, zaś pomiędzy 1111 i 0001 wynosi 3»

Własności wykrywania 1 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. ■ ' ,

^g^7^kł**.l?‘ff-_ł>W *    ___________—,_^ ...

- Dla. przesyłania 4-ch symboli A, B, C, D użyto następującego kodu dwójkowego A - 00000 B - Ó0111 0 - 11001 D - 11110

Po stronie odbiorczej odebrano słowo 11101. Jakie słowo nadano, jeżeli zakłada się, że 4 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 Hammlnga £11J. V 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 bitfy parzystości, przy czym grupę tworzy się z Jednego bitu parzystości 1 wybranych bitów Informacyjnych.

Sod 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 1 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ąi 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 1 bitów parzystości. W konsekwencji maksymalna ilość bitów informacyjnych W wynosi:

“max ■ ²¹ “ 1 " ^r    C1.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 Hammlnga 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 1 3 bity parzystości, które oznaczymy odpowiednio przez Xj, x₂, x₁ i yj, y₂, y^. W tablicy na rys. 1.12 przed-