Направо към съдържанието

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

от Уикипедия, свободната енциклопедия

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

Означаваме 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.

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

[редактиране | редактиране на кода]

Тук α, β и γ са вектори от 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