Разстояние на Хеминг

Разстоянието на Хеминг (на английски: Hamming distance) между два равноразредни вектора е броят на различаващите се компоненти. Тъй като показва броя на компонентите, които трябва да се променят (коригират), за да се получи от единия вектор другия, има важно приложение в теорията на шумозащитните кодове.

Дефиниция

Означаваме J_q = {0, …, q-1}

Нека ℕ = {x∈ℤ | x ≥ 0}

Полагаме векторите:

α = (a₁, …, a_n), a_i∈J_q, i = 1, …, n; т.е. α∈J_qⁿ.
β = (b₁, …, b_n), b_i∈J_q, i = 1, …, n; т.е. β∈J_qⁿ

Разстоянието на Хеминг е функция ρ: J_qⁿ x J_qⁿ → ℕ, където ρ(α, β) е броят на различаващите се компоненти на векторите α и β.

Чрез него дефинираме и тегло на вектор wt(α) = ρ(ō, α), където ō е нулевия вектор (вектор, на когото всичките компоненти са 0). Бележи се още ||α|| и означава броят на ненулевите компоненти на вектора α.

Общи свойства

∀ α,β∈J_qⁿ(ρ(α, β) = ρ(β, α) ≥ 0)
∀ α∈J_qⁿ(ρ(α, α) = 0)
∀ α,β,γ∈J_qⁿ(ρ(α, β) + ρ(β, γ) ≥ ρ(α, γ)) (неравенство на триъгълника)

От горните следва, че разстоянието на Хеминг е метрика във векторното пространство J_qⁿ.

Свойства за двоични вектори

Тук α, β и γ са вектори от J₂ⁿ, α + β е събиране по модул 2 (изключващо „или“, по-познато като XOR) и α ∧ β е конюнкция на вектори.

ρ(α, β) = ∑ⁿ_i=1 |a_i – b_i| и така ||α|| = ∑ⁿ_i=1 a_i
ρ(α, β) = ||α + β||
ρ(α, β) = ||α|| + ||β|| – 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

Тази статия, свързана с математика, все още е мъниче. Помогнете на Уикипедия, като я редактирате и разширите.