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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
3-битовый двоичный куб. Все вершины, соединённые ребром имеют расстояние Хемминга равное 1.
Пример двух расстояний: 100 → 011 имеют расстояние 3 (красные рёбра); 010 → 111 имеют расстояние 2 (синие рёбра).
4-битовый двоичный четырёхмерный куб (тессеракт) где наглядны расстояния Хемминга.
Примеры расстояний в двоичном тессеракте: 0100 → 1001 с расстоянием 3 (красные линии); 0110 → 1110 расстояние 1 (синяя линия).

Расстоя́ние Хэ́мминга — число позиций, в которых соответствующие символы двух слов одинаковой длины различны[1]. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.

Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в Bell Labs для определения меры различия между кодовыми комбинациями (двоичными векторами) в векторном пространстве кодовых последовательностей, в этом случае расстоянием Хэмминга между двумя двоичными последовательностями (векторами) и длины называется число позиций, в которых они различны — в такой формулировке расстояние Хэмминга вошло в словарь алгоритмов и структур данных национального института стандартов и технологий США (англ. NIST Dictionary of Algorithms and Data Structures). Расстояние Хэмминга является частным случаем метрики Минковского (при соответствующем определении вычитания):

.

В некоторых системах счисления, например, в коде Грея кодированные числа, различающиеся на 1, имеют расстояние Хемминга равное 1, говорят что такие числа являются «соседними», и вообще, два слова, не обязательно двоичные, расстояние Хемминга между которыми равно 1 называют «соседними».

Соседнее кодирование важно при проектировании логических устройств, где необходимо исключить логические гонки.

Примеры[править | править вики-текст]

Свойства[править | править вики-текст]

Множество слов равной длины образуют метрическое пространство где для каждой пары элементов пространства определено число — расстояние Хэмминга удовлетворяющее аксиомам метрики:

  1. (аксиома тождества).
  2. (аксиома симметрии).
  3. (аксиома треугольника или неравенство треугольника).
  • Из аксиом следует неотрицательность расстояния, поскольку
    .
  • Если неравенство треугольника представить в виде
    для всех и ,
тогда из аксиомы тождества и неравенства треугольника следует аксиома симметрии.

Расстояние Хэмминга всегда:

где  — длина слов в символах.

Расстояние Хэмминга в биоинформатике и геномике[править | править вики-текст]

Для нуклеиновых кислот (ДНК и РНК) возможность гибридизации двух полинуклеотидных цепей с образованием вторичной структуры — двойной спирали — зависит от степени комплементарности нуклеотидных последовательностей обеих цепей. При увеличении расстояния Хэмминга количество водородных связей, образованных комплементарными парами оснований уменьшается и, соответственно, уменьшается стабильность двойной цепи. Начиная с некоторого граничного расстояния Хэмминга гибридизация становится невозможной.

При эволюционном расхождении гомологичных ДНК-последовательностей расстояние Хэмминга является мерой, по которой можно судить о времени, прошедшем с момента расхождения гомологов, например, о длительности эволюционного отрезка, разделяющего гены-гомологи и ген-предшественник.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Hamming distance: The number of digit positions in which the corresponding digits of two binary words of the same length are different (Federal Standard 1037C).

Литература[править | править вики-текст]

  • Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.