Kodowanie Hamminga
Dzięki kodowi Hamminga jesteśmy w stanie nie tylko wykryć błąd pojedynczy w ciągu zero-
jedynkowym, ale także wskazać który bit jest niepoprawny.
Jak to uzyskać?
Mamy dowolny, ale i-bitowy, ciąg zero-jedynkowy, np. 00110110, liczba bitów ‘i’ = 8.
Aby móc wskazać na którym miejscu wystąpił błąd potrzebujemy dodać do tego ciągu kilka
dodatkowych bitów kontrolnych, które określą nam, w którym miejscu wystąpił błąd. Mamy 8 miejsc
więc wydawało by się, że wystarczą 3 dodatkowe bity, gdyż 2
3
= 8. Nie jest to jednak prawdą z dwóch
powodów:
- ciąg 000 traktowany jest jako brak błędu, czyli możemy zapisać tylko 7 numerków.
- po dodaniu 3 bitów cały ciąg ma ich 11 czyli potrzebujemy aż dwunastu kombinacji (kombinacja
000, oraz 001, 010, itd.)
Jednak nie cza się martwić bo after some algebra dochodzimy do wzorku:
2
k
≥ i + k + 1
Gdzie: ‘k’ – liczba bitów kontrolnych, które trzeba dodać; ‘i’ – liczba bitów informacyjnych (ile jest w
początkowym ciągu).
W naszym przypadku k = 4, bo 16 ≥ (8 + 4 + 1 = 13).
Co z tego zapamiętać? Wzorek.
W skrócie: Krok 1: Obliczenie długości ciągu kodowego (2
k
≥ i + k + 1)
Co teraz?
Konstruujemy tabelkę jak poniżej.
Dla uproszczenia filozofii przyjmę, że ‘i’ = 3, czyli mamy ciąg informacyjny 3-bitowy. Wymaga to, aby
dodać ‘k’ = 3 bitów kontrolnych, na których zapiszemy 8 różnych wartości błędów (oczywiście 000
oznacza, że błędu nie ma). Można więc powiedzieć, że nasz ciąg wygląda tak:
I
1
i
2
i
3
k
1
k
2
k
3
, lecz potraktujemy go jako zwykły ciąg ‘a’ = a
1
a
2
a
3
a
4
a
5
a
6
.
Błąd na pozycji
K
1
K
2
K
3
Żadnej – brak błędu
0
0
0
1
0
0
1
2
0
1
0
3
0
1
1
4
1
0
0
5
1
0
1
6
1
1
0
Jak taką tabelkę skonstruować. Ano nazywamy kolumny jak wyżej, kolejnymi indeksami ciągu
kontrolnego. Natomiast ciąg k
0
k
1
k
2
to po prostu wartość binarna numeru pozycji, na której wystąpił
błąd, czyli np. 3
dec
= 011
bin
.
Z tabelki wyznaczamy tak zwany syndrom (wektor) ‘s’ = [s
1
, s
2
, s
3
].
Syndrom przyjmuje wartość 0 lub 1.
0 – nie wykryto błędu, 1 – błąd wykryto, standardowo.
