Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . ( Май 2015 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В теории информации , то расстояние Хэмминга между двумя строками равной длиной этим количеством положений , в которых соответствующие символы различны. Другими словами, он измеряет минимальное количество замен, необходимых для преобразования одной строки в другую, или минимальное количество ошибок, которые могли бы преобразовать одну строку в другую. В более общем контексте расстояние Хэмминга - это одна из нескольких строковых метрик для измерения расстояния редактирования между двумя последовательностями. Он назван в честь американского математика Ричарда Хэмминга .
Основное приложение - теория кодирования , в частности, блочные коды , в которых строки одинаковой длины являются векторами над конечным полем .
Определение [ править ]
Расстояние Хэмминга между двумя строками символов одинаковой длины - это количество позиций, в которых соответствующие символы различаются. [1]
Примеры [ править ]
Символы могут быть, среди прочего, буквами, битами или десятичными цифрами. Например, расстояние Хэмминга между:
- « Ка рол в » и « ка Чет в » является 3.
- « k a r ol in » и « k e r st in » равны 3.
- « k athr in » и « k erst in » - 4.
- 10 1 1 1 01 и 10 0 1 0 01 равно 2.
- 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 . Расстояние Хэмминга между двумя словами через и Ь также можно рассматривать как вес Хэмминга из в - бпри соответствующем выборе оператора -, так же как разницу между двумя целыми числами можно рассматривать как расстояние от нуля на числовой строке. [ требуется разъяснение ]
Для двоичных строк и б расстояние Хэмминга равно числу единиц ( количества населения ) в виде XOR б . [3] Метрическое пространство двоичных строк длиной n с расстоянием Хэмминга известно как куб Хэмминга ; как метрическое пространство оно эквивалентно множеству расстояний между вершинами в графе гиперкуба . Можно также рассматривать двоичную строку длины n как вектор в , рассматривая каждый символ в строке как действительную координату; с этим вложением струны образуют вершины n- мерного гиперкуба , а расстояние Хэмминга струн эквивалентно манхэттенскому расстоянию между вершинами.
Обнаружение и исправление ошибок [ править ]
Минимальное расстояние Хэмминга используется для определения некоторых существенных понятий в теории кодирования , такие как ошибки обнаружения и коды с исправлением ошибок . В частности, код 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,что удовлетворяет 2k + 1 = 3 .
Таким образом, код с минимальным расстоянием Хэмминга d между своими кодовыми словами может обнаруживать не более d -1 ошибок и может исправлять ошибки ⌊ ( d -1) / 2⌋. [2] Последнее число также называется радиусом упаковки или способностью кода исправлять ошибки . [4]
История и приложения [ править ]
Расстояние Хэмминга названо в честь Ричарда Хэмминга , который ввел понятие в своей фундаментальной работе по кодам Хемминг , обнаружению ошибок и коды с исправлением ошибок , в 1950 году [5] Хэмминг вес анализ бит используются в нескольких областях , включая теорию информации , теории кодирования , и криптография .
Он используется в телекоммуникациях для подсчета количества перевернутых битов в двоичном слове фиксированной длины в качестве оценки ошибки, и поэтому иногда его называют расстоянием до сигнала . [6] Для q- мерных строк в алфавите размера q ≥ 2 расстояние Хэмминга применяется в случае q-арного симметричного канала , в то время как расстояние Ли используется для фазовой манипуляции или, в более общем смысле, каналов, подверженных ошибкам синхронизации. потому что расстояние Ли учитывает ошибки ± 1. [7] Если илиоба расстояния совпадают, потому что любая пара элементов от или отличается на 1, но расстояния разные для больших .
Расстояние Хэмминга также используется в систематике как мера генетического расстояния. [8]
Однако для сравнения строк разной длины или строк, в которых следует ожидать не только подстановок, но также вставок или удалений, более подходящей метрикой является расстояние Левенштейна .
В межсоединениях процессоров динамическое потребление энергии зависит от числа переходов. В схеме сигнализации уровня количество переходов зависит от расстояния Хэмминга между последовательно передаваемыми шинами. [9] Следовательно, уменьшая расстояние Хэмминга, можно уменьшить энергию перемещения данных.
Пример алгоритма [ править ]
Следующая функция, написанная на Python 3, возвращает расстояние Хэмминга между двумя строками:
def hamming_distance ( string1 , string2 ): dist_counter = 0 для n в диапазоне ( len ( string1 )): if string1 [ n ] ! = string2 [ n ]: dist_counter + = 1 return dist_counter
Или, короче:
sum ( xi ! = yi для xi , yi в zip ( x , y ))
Функция hamming_distance()
, реализованная в Python 2.3+ , вычисляет расстояние Хэмминга между двумя строками (или другими повторяемыми объектами) равной длины, создавая последовательность логических значений, указывающих несоответствия и совпадения между соответствующими позициями в двух входах, а затем суммируя последовательность с False. и Истинные значения интерпретируются как ноль и единица.
def hamming_distance ( s1 , s2 ) -> int : "" "Возвращает расстояние Хэмминга между последовательностями одинаковой длины." "" if len ( s1 ) ! = len ( s2 ): raise ValueError ( "Не определено для последовательностей неравной длины. " ) вернуть сумму ( el1 ! = el2 для el1 , el2 в zip ( s1 , s2 ))
где функция zip () объединяет две коллекции одинаковой длины попарно.
Следующая функция C будет вычислять расстояние Хэмминга двух целых чисел (рассматриваемых как двоичные значения, то есть как последовательности битов). Время выполнения этой процедуры пропорционально расстоянию Хэмминга, а не количеству битов на входах. Он вычисляет поразрядное исключающее или двух входов, а затем находит вес Хэмминга результата (количество ненулевых битов), используя алгоритм Вегнера (1960), который неоднократно находит и очищает ненулевой бит младшего порядка. Некоторые компиляторы поддерживают функцию __builtin_popcount, которая может вычислить это, используя специализированное аппаратное обеспечение процессора, если оно доступно.
int hamming_distance ( без знака x , без знака y ) { int dist = 0 ; // Операторы ^ устанавливают в 1 только те биты, которые отличаются для ( 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 ); }
См. Также [ править ]
- Ближайшая строка
- Расстояние Дамерау – Левенштейна
- Евклидово расстояние
- Проблема Гэпа-Хэмминга
- Код Грея
- Индекс Жаккара
- Расстояние Левенштейна
- Расстояние Махаланобиса
- Мангеймское расстояние
- Индекс сходства Соренсена
- Редкая распределенная память
- Лестница слов
Ссылки [ править ]
- ^ Waggener, Билл (1995). Методы импульсной кодовой модуляции . Springer. п. 206. ISBN. 9780442014360. Проверено 13 июня 2020 .
- ^ a b c d Робинсон, Дерек Дж. С. (2003). Введение в абстрактную алгебру . Вальтер де Грюйтер . С. 255–257. ISBN 978-3-11-019816-4.
- ^ Уоррен младший, Генри С. (2013) [2002]. Восторг хакера (2-е изд.). Эддисон Уэсли - Pearson Education, Inc., стр. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
- ^ a b Коэн, G .; Хонкала, I .; Лицын, С .; Лобштейн, А. (1997), Покрывающие коды , Математическая библиотека Северной Голландии, 54 , Elsevier , стр. 16–17, ISBN 9780080530079
- ^ Хэмминг, RW (апрель 1950). «Коды обнаружения и исправления ошибок» (PDF) . Технический журнал Bell System . 29 (2): 147–160. DOI : 10.1002 / j.1538-7305.1950.tb00463.x . ISSN 0005-8580 .
- Перейти ↑ Ayala, Jose (2012). Интегральные схемы и системное проектирование . Springer . п. 62. ISBN 978-3-642-36156-2.
- ^ Рот, Рон (2006). Введение в теорию кодирования . Издательство Кембриджского университета . п. 298. ISBN 978-0-521-84504-5.
- ^ Пилчер, Кристофер Д .; Вонг, Джозеф К .; Пиллаи, Сатиш К. (18.03.2008). «Вывод динамики передачи ВИЧ из филогенетических отношений последовательности» . PLOS Medicine . 5 (3): e69. DOI : 10.1371 / journal.pmed.0050069 . ISSN 1549-1676 . PMC 2267810 . PMID 18351799 .
- ^ " Обзор методов кодирования для уменьшения энергии движения данных ", JSA, 2018
Дальнейшее чтение [ править ]
- Эта статья включает материалы, являющиеся общественным достоянием, из документа Управления общих служб : «Федеральный стандарт 1037C» .
- Вегнер, Питер (1960). «Методика счета единиц в двоичном компьютере». Коммуникации ACM . 3 (5): 322. DOI : 10,1145 / 367236,367286 . S2CID 31683715 .
- Маккей, Дэвид JC (2003). Теория информации, вывод и алгоритмы обучения . Кембридж: Издательство Кембриджского университета . ISBN 0-521-64298-1.