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

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

Дефиниция

Означаваме 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||α ∧ β||
• ρ(α, β) = ρ(α + γ, β + γ)

Литература

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