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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

Дефиниция[редактиране | edit source]

Означаваме 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). Бележи се още ||α|| и означава броят на ненулевите компоненти на вектора α.

Общи свойства[редактиране | edit source]

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

Свойства за двоични вектори[редактиране | edit source]

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

  • ρ(α, β) = ∑ni=1 |ai - bi| и така ||α|| = ∑ni=1 ai
  • ρ(α, β) = ||α + β||
  • ρ(α, β) = ||α|| + ||β|| - 2||α ∧ β||
  • ρ(α, β) = ρ(α + γ, β + γ)

Алгоритмични примери[редактиране | edit source]

Функцията hamming_distance() в езика Python изчислява Хеминг разстоянието между два низа (или други повторими обекта) с еднаква дължина, създавайки последователност от булеви стойности индикиращи несъответствия или съответствия между съответстващи позиции при двете въведения и след това събира последователността със False или True стойности които биват интерпретирани като нула и единица както следва.

def hamming_distance(s1, s2):
    assert len(s1) == len(s2)
    return sum(ch1 != ch2 for ch1, ch2 in zip(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;
}

Литература[редактиране | edit source]

  • Красимир Манев, "Увод в дискретната математика" ISBN 954-535-136-5