Разстоянието на Хеминг () между два равноразредни вектора е броят на различаващите се компоненти. Тъй като показва броя на компонентите, които трябва да се променят (коригират), за да се получи от единия вектор другия, има важно приложение в теорията на шумозащитните кодове.
Дефиниция Означаваме Jq = {0, …, q-1}
Нека ℕ = {x∈ℤ | x ≥ 0}
Полагаме векторите: α = (a1, …, an), ai∈Jq, i = 1, …, n; т.е. α∈Jqn. β = (b1, …, bn), bi∈Jq, i = 1, …, n; т.е. β∈Jqn
Разстоянието на Хеминг е функция ρ: Jqn x Jqn → ℕ, където ρ(α, β) е броят на различаващите се компоненти на векторите α и β.
Чрез него дефинираме и тегло на вектор wt(α) = ρ(ō, α), където ō е нулевия вектор (вектор, на когото всичките компоненти са 0). Бележи се още ||α|| и означава броят на ненулевите компоненти на вектора α.
Общи свойства ∀ α,β∈Jqn(ρ(α, β) = ρ(β, α) ≥ 0) ∀ α∈Jqn(ρ(α, α) = 0) ∀ α,β,γ∈Jqn(ρ(α, β) + ρ(β, γ) ≥ ρ(α, γ)) (неравенство на триъгълника)
От горните следва, че разстоянието на Хеминг е метрика във векторното пространство Jqn.
Свойства за двоични вектори Тук α, β и γ са вектори от J2n, α + β е събиране по модул 2 (изключващо „или“, по-познато като XOR) и α ∧ β е конюнкция на вектори.
ρ(α, β) = ∑ni=1 |ai – bi| и така ||α|| = ∑ni=1 ai ρ(α, β) = ||α + β|| ρ(α, β) = ||α|| + ||β|| – 2||α ∧ β|| ρ(α, β) = ρ(α + γ, β + γ)
Алгоритмични примери Функцията hamming_distance() в езика Python изчислява Хеминг разстоянието между два низа (или други повторими обекта) с еднаква дължина, създавайки последователност от булеви стойности индикиращи несъответствия или съответствия между съответстващи позиции при двете въведения и след това събира последователността с False или True стойности които биват интерпретирани като нула и единица както следва.
def hamming_distance(s1, s2): assert len(s1) == len(s2) return sum(ch1 != ch2 for ch1, ch2 in s1, s2)
Следната С функция ще изчисли Хеминг разстоянието между две цели числа (смятани за бинарни стойности като последователност от битове). Времето на изпълнение на тази процедура е пропорционално на Хеминг дистанцията, а не на броя битове причислени към входящата информация. Изчислява се XOR стойността на двете въведения и после се намира Хеминг ширината на резултата (номера на всички битове освен 0) използвайки алгоритъм на Wegner (1960) който нееднократно намира и премахва най-ниско стоящия ненулев бит.
unsigned hamdist(unsigned x, unsigned y) { unsigned dist = 0, val = x ^ y; // XOR
// Count the number of set bits while(val) { ++dist; val &= val – 1;
return dist; }
Литература Красимир Манев, „Увод в дискретната математика“ ISBN 954-535-136-5
Категория:Дискретна математика Категория:Информатика