Kod Hamminga

Kod Hamminga jest binarnym kodem, który umożliwia odtworzenie danych po wystąpieniu błędu
transmisji. Zakodowana informacja składa się z n-bitowego kodu i k bitów parzystości. Bity
parzystości umieszczone są na pozycjach o numerach 2

i

, i=0,1,2,… i każdy z nich kontrolują określone

bity. Na kontrolowanych pozycjach występuje parzysta ilośd „1”. Oto pozycje kontrolowane przez
kolejne bity parzystości:

– bit 1 - 1, 3, 5, 7, 9, 11

– bit 2 – 2, 3, 6, 7, 10, 11

– bit 4 – 4, 5, 6, 7

– bit 8 – 8, 9, 10, 11

W ogólności bit n jest kontrolowany przez bity b

1

,b

2

,….b

k

, gdzie b

1

+b

2

+…+b

k

=n.

Np. bit 10 kontrolowany jest przez bity 2 i 8, bo 2+8=10, bit 6 przez bity 2 i 4 , bo 2+4=6, bit 7 przez
bity 1, 2, 4, bo 1+2+4=7.

Rozważmy kodowanie znaku ASCII zapisanego na 7 bitach. Na pozycjach 1, 2, 4, 8 znajdują się bity
kontrolne. Na pozostałych bitach zapisywany jest kod litery.

Przykład:

Litera:

b

Kod ASCII:

98

Kod ASCII binarnie:

1100010

1

2

3

4

5

6

7

8

9

10

11

0

0

1

1

1

0

0

1

0

1

0



Bit 1 - Na pozycjach 3,5,7,9,11 są dwie wartości „1”, jest to liczba parzysta, więc bit 1
przyjmuje wartośd „0”.



Bit 2 - Na pozycjach 3,6,7,10,11 są dwie wartości „1”, więc bit 2 przyjmuje wartośd „0”.



Bit 4 - Na pozycjach 5,6,7 jest jedna wartośd „1”, jest to liczba nieparzysta, więc bit 4
przyjmuje wartośd „1”.



Bit 8 - Na pozycjach 9,10,11 jest jedna wartośd „1”, jest to liczba nieparzysta, więc bit 8
przyjmuje wartośd „1”.

Kod Hamminga litery b to: 00111001010.
Jeśli w transmisji wystąpiłby błąd na jednej pozycji, to niektóre bity parzystości byłyby niepoprawne.
Suma pozycji niepoprawnych bitów parzystości wskazuje przekłamaną pozycję. Należy ją wówczas

1,3,5,7,9,11
1

4,5,6,7

8,9,10,11

2,3,6,7,10,11

poprawid i kodowanie jest poprawne. Jeśli np. w transmisji litery b wystąpiłby błąd i otrzymalibyśmy

taki kod

: 0011100

0

010

, to niepoprawny byłby jedynie 8 bit parzystości. Należałoby zatem

zamienid „0” występujące na pozycji 8 na „1”, w wyniku czego uzyskujemy poprawny kod litery b –

0011100

1

010.

Jeśli po transmisji uzyskalibyśmy kod:

00111001000

to niepoprawne byłyby bity parzystości o

numerach 2 (bo na pozycjach 2,3,6,7,10,11 jest tylko jedna „1” – na pozycji 3) oraz 8 (bo na pozycjach
8,9,10,11 jest tylko jedna „1” – na pozycji 8), więc przekłamana pozycja to 2+8=10. Po zamianie bitu
o numerze 10 z „0” na „1” otrzymujemy poprawny kod.