Skip to main content
LibreTexts - Ukrayinska

4.4: Відстань Хеммінга

  1. Last updated
  2. Save as PDF
  • Page ID
    29955

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Нам потрібна певна техніка для того, щоб сказати, наскільки схожі два бітові візерунки. У випадку фізичних величин, таких як довжина, цілком природно думати про два вимірювання як близькі або приблизно рівні. Чи є подібний сенс, в якому дві моделі бітів близькі?

    Спочатку спокусливо сказати, що два бітові візерунки близькі, якщо вони представляють цілі числа, які є сусідніми, або числа з плаваючою комою, які близькі. Однак це поняття не є корисним, оскільки воно базується на певних значеннях, що приписуються бітовим шаблонам. Неочевидно, що два бітові шаблони, які відрізняються в першому біті, повинні бути більш-менш «відмінними» один від одного, ніж два, які відрізняються останнім бітом.

    Більш корисним визначенням різниці між двома бітовими шаблонами є кількість бітів, які відрізняються між ними. Це називається дистанцією Хеммінга, після Річарда Хеммінга (1915 — 1998)\(^1\). Таким чином 0110 і 1110 розділені на відстань Хеммінга одного. Дві однакові візерунки розділені на відстань Хеммінга нуль.

    Зауважте, що відстань Хеммінга може бути визначена лише між двома бітовими візерунками з однаковою кількістю бітів. Немає сенсу говорити про відстань Хеммінга одного рядка бітів, або між двома бітовими рядками різної довжини.

    Використовуючи це визначення, ефект помилок, що вводяться в каналі, може бути описаний відстанню Хеммінга між двома бітовими паттернами, один на вході в канал, а інший на виході. Відсутність помилок означає відстань Хеммінга нуль, а одна помилка означає відстань Хеммінга один. Якщо виникають дві помилки, це, як правило, означає відстань Хеммінга дві. (Однак зауважте, що якщо дві помилки трапляються з одним і тим же бітом, друга скасує першу, а відстань Хеммінга фактично дорівнюватиме нулю.)

    Дія кодера також можна оцінити з точки зору відстані Хеммінга. Для того, щоб забезпечити виявлення помилок, необхідно, щоб кодер створював бітові шаблони, щоб будь-які два різних входи були розділені на виході відстань Хеммінга принаймні два - інакше одна помилка може перетворити одне юридичне кодове слово в інше. Для забезпечення захисту від подвійних помилок поділ будь-яких двох дійсних кодових слів має бути не менше трьох. Для того, щоб корекція однієї помилки була можливою, всі дійсні кодові слова повинні бути розділені на відстань Хеммінга не менше трьох.

    \(^1\)See a biography of Hamming at http://www-groups.dcs.st-andrews.ac....s/Hamming.html