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

Количество бит, которые различаются между двумя строками

Минимальное расстояние между любыми двумя вершинами — это расстояние Хэмминга между двумя двоичными строками.

В теории информации расстояние Хэмминга между двумя строками или векторами одинаковой длины — это число позиций, в которых соответствующие символы различны. Другими словами, оно измеряет минимальное количество замен, необходимых для преобразования одной строки в другую, или, что эквивалентно, минимальное количество ошибок , которые могли бы преобразовать одну строку в другую. В более общем контексте расстояние Хэмминга — это одна из нескольких метрик строк для измерения расстояния редактирования между двумя последовательностями. Оно названо в честь американского математика Ричарда Хэмминга .

Основное применение — теория кодирования , а точнее, блочные коды , в которых строки одинаковой длины являются векторами над конечным полем .

Определение

Расстояние Хэмминга между двумя строками символов одинаковой длины — это число позиций, в которых соответствующие символы различны. ^[1]

Примеры

Символы могут быть буквами, битами или десятичными цифрами, среди прочих возможностей. Например, расстояние Хэмминга между:

• « ка рол ин » и « ка тр ин » — это 3.
• « кэрол ин » и « керст ин » — это 3 .
• « К атр ин » и « керст ин » — это 4.
• 0000 и 1111 — это 4.
• 2 17 3 8 96 и 2 23 3 7 96 равно 3.

Характеристики

Для фиксированной длины n расстояние Хэмминга является метрикой на множестве слов длины n (также известном как пространство Хэмминга ), поскольку оно удовлетворяет условиям неотрицательности, симметрии, расстояние Хэмминга двух слов равно 0 тогда и только тогда, когда два слова идентичны, и оно также удовлетворяет неравенству треугольника : ^[2] Действительно, если мы зафиксируем три слова a , b и c , то всякий раз, когда есть разница между i -й буквой a и i -й буквой c , то должна быть разница между i -й буквой a и i -й буквой b или между i- й буквой b и i- й буквой c . Следовательно, расстояние Хэмминга между a и c не больше суммы расстояний Хэмминга между a и b и между b и c . Расстояние Хэмминга между двумя словами a и b можно также рассматривать как вес Хэмминга a − b для соответствующего выбора оператора −, подобно тому, как разницу между двумя целыми числами можно рассматривать как расстояние от нуля на числовой прямой. ^{[ необходимо пояснение ]}

Для двоичных строк a и b расстояние Хэмминга равно числу единиц ( количество популяций ) в XOR b . [ ^3] Метрическое пространство двоичных строк длиной n с расстоянием Хэмминга известно как куб Хэмминга ; как метрическое пространство оно эквивалентно набору расстояний между вершинами в графе гиперкуба . Можно также рассматривать двоичную строку длины n как вектор в , рассматривая каждый символ в строке как действительную координату; при таком вложении строки образуют вершины n -мерного гиперкуба , а расстояние Хэмминга строк эквивалентно манхэттенскому расстоянию между вершинами. ${\displaystyle \mathbb {R} ^{n}}$

Обнаружение и исправление ошибок

Минимальное расстояние Хэмминга или минимальное расстояние (обычно обозначаемое как d _min ) используется для определения некоторых существенных понятий в теории кодирования , таких как коды обнаружения и исправления ошибок . В частности, код C называется кодом обнаружения ошибок k тогда и только тогда, когда минимальное расстояние Хэмминга между любыми двумя его кодовыми словами не менее k +1. ^[2]

Например, рассмотрим код, состоящий из двух кодовых слов "000" и "111". Расстояние Хэмминга между этими двумя словами равно 3, и, следовательно, это k = 2 обнаружения ошибок. Это означает, что если один бит перевернут или два бита перевернут, ошибка может быть обнаружена. Если перевернут три бита, то "000" становится "111", и ошибка не может быть обнаружена.

Говорят, что код C исправляет k ошибок , если для каждого слова w в базовом пространстве Хэмминга H существует не более одного кодового слова c (из C ), такого что расстояние Хэмминга между w и c не превышает k . Другими словами, код исправляет k ошибок, если минимальное расстояние Хэмминга между любыми двумя его кодовыми словами не менее 2 k +1. Это также понимается геометрически, так как любые замкнутые шары радиуса k с центрами на различных кодовых словах не пересекаются. ^[2] В этом контексте эти шары также называются сферами Хэмминга . ^[4]

Например, рассмотрим тот же 3-битный код, состоящий из двух кодовых слов "000" и "111". Пространство Хэмминга состоит из 8 слов 000, 001, 010, 011, 100, 101, 110 и 111. Кодовое слово "000" и слова с одиночной битовой ошибкой "001", "010", "100" все меньше или равны расстоянию Хэмминга от 1 до "000". Аналогично, кодовое слово "111" и его слова с одиночной битовой ошибкой "110", "101" и "011" все находятся в пределах 1 расстояния Хэмминга от исходного "111". В этом коде одиночная битовая ошибка всегда находится в пределах 1 расстояния Хэмминга от исходных кодов, и код может быть исправляющим 1 ошибку , то есть k=1 . Поскольку расстояние Хэмминга между «000» и «111» равно 3, а они составляют весь набор кодовых слов в коде, минимальное расстояние Хэмминга равно 3, что удовлетворяет 2k+1 = 3 .

Таким образом, код с минимальным расстоянием Хэмминга d между его кодовыми словами может обнаружить максимум d -1 ошибок и исправить ⌊( d -1)/2⌋ ошибок. ^[2] Последнее число также называется радиусом упаковки или способностью кода исправлять ошибки . ^[4]

История и применение

Расстояние Хэмминга названо в честь Ричарда Хэмминга , который ввел эту концепцию в своей фундаментальной статье о кодах Хэмминга « Коды обнаружения и исправления ошибок » в 1950 году. ^[5] Анализ веса Хэмминга битов используется в нескольких дисциплинах, включая теорию информации , теорию кодирования и криптографию . ^[6]

Он используется в телекоммуникациях для подсчета количества перевернутых битов в двоичном слове фиксированной длины в качестве оценки ошибки, и поэтому иногда называется расстоянием сигнала . ^[7] Для q -ичных строк в алфавите размером q  ≥ 2 расстояние Хэмминга применяется в случае q-ичного симметричного канала , в то время как расстояние Ли используется для фазовой манипуляции или, в более общем случае, каналов, восприимчивых к ошибкам синхронизации, поскольку расстояние Ли учитывает ошибки ±1. ^[8] Если или оба расстояния совпадают, потому что любая пара элементов из или отличается на 1, но расстояния различны для больших . ${\displaystyle q=2}$ ${\displaystyle q=3}$ ${\textstyle \mathbb {Z} /2\mathbb {Z} }$ ${\textstyle \mathbb {Z} /3\mathbb {Z} }$ ${\displaystyle q}$

Расстояние Хэмминга также используется в систематике как мера генетического расстояния. ^[9]

Однако для сравнения строк разной длины или строк, где можно ожидать не только замен, но и вставок или удалений, более подходящей является более сложная метрика, такая как расстояние Левенштейна .

Пример алгоритма

Следующая функция, написанная на Python 3, возвращает расстояние Хэмминга между двумя строками:

def  hamming_distance ( string1 :  str ,  string2 :  str )  ->  int : """Вернуть расстояние Хэмминга между двумя строками.""" если  len ( string1 )  !=  len ( string2 ): raise  ValueError ( "Строки должны быть одинаковой длины." ) dist_counter  =  0 для  n  в  диапазоне ( len ( string1 )): если  строка1 [ n ]  !=  строка2 [ n ]: dist_counter  +=  1 вернуть  dist_counter

Или, в более коротком выражении:

сумма ( char1  !=  char2  для  char1 ,  char2  в  zip ( string1 ,  string2 ,  strict = True ))

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

def  hamming_distance ( s1 :  str ,  s2 :  str )  ->  int : """Возвращает расстояние Хэмминга между последовательностями одинаковой длины.""" if len ( s1 ) != len ( s2 ): raise ValueError ( "Не определено для последовательностей неравной длины." ) return sum ( char1 != char2 for char1 , char2 in zip ( s1 , s2 ))                 

где функция zip() объединяет две коллекции одинаковой длины в пары.

Следующая функция C вычислит расстояние Хэмминга двух целых чисел (рассматриваемых как двоичные значения, то есть как последовательности битов). Время выполнения этой процедуры пропорционально расстоянию Хэмминга, а не количеству битов на входах. Она вычисляет побитовое исключающее ИЛИ двух входов, а затем находит вес Хэмминга результата (количество ненулевых битов) с помощью алгоритма Вегнера (1960), который многократно находит и очищает ненулевой бит младшего порядка. Некоторые компиляторы поддерживают функцию __builtin_popcount , которая может вычислить это с помощью специализированного процессорного оборудования, если оно доступно.

int hamming_distance ( беззнаковый x , беззнаковый y ) { int dist = 0 ;         // Операторы ^ устанавливают в 1 только те биты, которые отличаются for ( unsigned val = x ^ y ; val > 0 ; ++ dist ) { // Затем мы считаем бит, установленный в 1, используя способ Питера Вегнера val = val & ( val - 1 ); // Устанавливаем в ноль наименьший разряд val 1 }                       // Возвращаем количество отличающихся бит return dist ; }  

Более быстрой альтернативой является использование инструкции ассемблера подсчета населения ( popcount ). Некоторые компиляторы, такие как GCC и Clang, делают ее доступной через встроенную функцию:

// Расстояние Хэмминга для 32-битных целых чисел int hamming_distance32 ( unsigned int x , unsigned int y ) { return __builtin_popcount ( x ^ y ); }          // Расстояние Хэмминга для 64-битных целых чисел int hamming_distance64 ( unsigned long long x , unsigned long long y ) { return __builtin_popcountll ( x ^ y ); }            

Смотрите также

• Математический портал

• Ближайшая строка
• Расстояние Дамерау–Левенштейна
• Евклидово расстояние
• Проблема разрыва-Хэмминга
• Код Грея
• индекс Жаккара
• Расстояние Яро–Винклера
• Расстояние Левенштейна
• Расстояние Махаланобиса
• Мангеймское расстояние
• Индекс сходства Сёренсена
• Разреженная распределенная память
• Лестница слов

Ссылки

1. Ваггенер, Билл (1995). Методы импульсно-кодовой модуляции. Springer. стр. 206. ISBN 978-0-442-01436-0. Получено 13 июня 2020 г. .
2. Робинсон, Дерек Дж. С. (2003). Введение в абстрактную алгебру . Вальтер де Грюйтер . С. 255–257. ISBN 978-3-11-019816-4.
3. Уоррен-младший, Генри С. (2013) [2002]. Hacker's Delight (2-е изд.). Addison Wesley – Pearson Education, Inc. стр. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
4. Cohen, G. ; Honkala, I.; Litsyn, S.; Lobstein, A. (1997), Covering Codes , North-Holland Mathematical Library, т. 54, Elsevier , стр. 16–17, ISBN 978-0-08-053007-9
5. Hamming, RW (апрель 1950 г.). «Error detection and error Correcting codes» (PDF) . The Bell System Technical Journal . 29 (2): 147–160. doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . ISSN  0005-8580. S2CID  61141773. Архивировано (PDF) из оригинала 2022-10-09.
6. Jarrous, Ayman; Pinkas, Benny (2009). "Безопасные вычисления на основе расстояний Хэмминга и их приложения". В Abdalla, Michel; Pointcheval, David; Fouque, Pierre-Alain; Vergnaud, Damien (ред.). Прикладная криптография и сетевая безопасность . Конспект лекций по информатике. Том 5536. Берлин, Гейдельберг: Springer. стр. 107–124. doi : 10.1007/978-3-642-01957-9_7 . ISBN 978-3-642-01957-9.
7. Айала, Хосе (2012). Интегральные схемы и системное проектирование . Springer . стр. 62. ISBN 978-3-642-36156-2.
8. Рот, Рон (2006). Введение в теорию кодирования . Cambridge University Press . стр. 298. ISBN 978-0-521-84504-5.
9. Пилчер, Кристофер Д.; Вонг, Джозеф К.; Пиллаи, Сатиш К. (2008-03-18). «Вывод динамики передачи ВИЧ из филогенетических последовательностей». PLOS Medicine . 5 (3): e69. doi : 10.1371/journal.pmed.0050069 . ISSN  1549-1676. PMC 2267810. PMID 18351799  . 

Дальнейшее чтение

•  В этой статье использованы материалы из Федерального стандарта 1037C. Администрация общих служб . Архивировано из оригинала 2022-01-22.
• Вегнер, Питер (1960). "Метод подсчета единиц в двоичном компьютере". Сообщения ACM . 3 (5): 322. doi : 10.1145/367236.367286 . S2CID  31683715.
• MacKay, David JC (2003). Теория информации, вывод и алгоритмы обучения. Кембридж: Cambridge University Press . ISBN 0-521-64298-1.