Kody i szyfry

Niech będzie dowolnym ustalonym alfabetem. Wprowadźmy w tym alfabecie metrykę dyskretną ρ_d: V × V → R⁺. Z twierdzenia 1 z Dodatku (p. Metryka Hamminga) wynika, że funkcja ρ_H: Vⁿ × Vⁿ → R⁺ zdefiniowana wzorem: dla każdego y, x ∈ Vⁿ

ρ_H (x, y) $= \displaystyle\sum^n_{i+1}$ ρ_d (x_i, y_i)

jest metryką. Nazywamy ją metryką lub odległością Hamminga w przestrzeni Vⁿ (Vⁿ jest to przestrzeń wszystkich słów o długości n nad alfabetem V). Najczęściej rozważamy metrykę Hamminga dla Vⁿ = {0, 1}. Oczywiście ρ_H: Vⁿ × Vⁿ → N ∪ {0} czyli ρ_H jest funkcją o wartościach w zbiorze liczb całkowitych nieujemnych.

Waga słowa binarnego. Wagą słowa binarnego z przestrzeni {0,1}ⁿ (lub ogólniej z {0,1}^*) nazywamy liczbą jedynek w tym słowie. W ten sposób definiujemy na {0,1}^* funkcję w: {0,1}^* → N ∪ {0}. Oczywiście dla a ∈ {0,1}ⁿ mamy w(a) = ρ_H (0, a) gdzie ρ_H jest metryką Hamminga. Można wyrazić metrykę Hamminga ρ_H w {0,1}ⁿ za pomocą funkcji wagi w.

Niech x, y ∈ {0,1}ⁿ, x = (x₁, x₂, ..., x_n), y = (y₁, y₂, ..., y_n), wówczas mamy

$ρ(x, y)\overset{df}{=} \displaystyle\sum^n_{i=1} ρ_d(x_i, y_j) \overset{df}{=} \displaystyle\sum^n_{i=1} w(x_i-_2y_i) = w(x-y)=w(x+y)$

gdzie x_i - ₂ y_i oznacza różnicę modulo 2, x − y oznacza różnicę modulo 2 po współrzędnych a x + y sumę modulo 2 po współrzędnych.